Ultimately, the issue is what BYOND can't know ahead of time, that the developer can. You know the specifics of your gameworld, and what goes on within that world. BYOND can't know all of that ahead of time, because you are standing there, throwing wrenches into the works as it were.

A pathfinding algorithm performs a specific searching function. There are many, many different possible search functions that operate in very diverse fashions. Depending on the desired outcome, some search functions may be more desirable than others. Each approach carries with it a strength and at least one weakness.

Since Tom/Dan/Lummox can't know what situation particular applications are going to be fielded in, we get a very generalized approach that always assumes the worst-case scenario.

Of course, the worst-case scenario is in fact, the slowest. BYOND's built-in pathfinding assumes that 1) We need to search until we find a result, or no result can be found. 2) We need to search from the starting point to the endpoint. 3) That we need to perform a search for every single step, and not preserve and use the path we found for the last step.


Now, this has some advantages. First, it will always return the best-result assuming all tiles are just as good as any other tile. It also has the advantage of being able to always respond to obstacles that move and change over time.

The weaknesses, however, are that the graph can't intelligently respond to obstacles that move and change over time. It also doesn't scale very well, as it uses a lot of CPU. On top of all of that, it doesn't actually deal very well with special-case terrain, such as swamps being slower than plains, or walking through lava hurting the NPC. It also has the marked disadvantage of not being able to abandon the pathfinding operation should certain situations arise (for instance, the target being surrounded), which result in some of the worst resource-usage scenarios possible for a pathfinding solution.


Designing your own pathfinding solution is entirely possible, and actually not all that difficult. It just seems that way. You just have to have a very basic grasp on basic CS theory, and understand a little bit about when to use certain techniques, and when to use others.

Now, I want to point out a few techniques that could be used to really drastically slim down the CPU usage of pathfinding algorithms:


Generic Enemy AI:

My advice for generic trash mob AI, would be to make them attempt to run toward the player until they reach an obstacle. When they bump into an obstacle, search for a path from the target to the enemy. Generally speaking, the player is more likely to get surrounded than the enemy, so you won't run into the bogus endpoint scenario nearly as often.

Once you have managed to find a valid path for the mob, start moving them along that path.

Path objects themselves should notify involved turfs that they are being watched as part of a path. Any update to a turf which would affect its pathing attributes, which also has a path observing it, should notify the path and therefore the pathing object that the path is dirty, and should therefore be recalculated. This way, you can keep around path objects whilst doing minimal recalculation of said path.

No-path solutions

A no-path solution is going to be the hardest solution to deal with. Either the player is surrounded by a series of obstacles, the mob is surrounded by a series of obstacles, or there is some kind of blockage that prevents them from getting to the player.

In some cases, you will have to account for no-path solutions. It may be ideal to have the object move as close as they can to the destination, whilst watching the offending obstacles for changes in status. Since we can assume that the player is going to be surrounded by other players, monsters, or scenery, we can even filter by these sorts of things and just fall back to other behavior. The worst thing you can do, is fail a pathfinding operation and just have the mob sit and try to find a path over and over again. After a pathing failure, have them do something else, because failures are crazy expensive.


Heuristics:

Pathing Heuristics are all-important to efficiency. If all tiles are equal to all other tiles, pathfinding solutions can start taking huge amounts of time over larger distances, or in more complex situations.

In general, try to feed your NPCs a heuristic that will give them an incentive to get closer to the player, as well as avoid terrain that will tend to make them take longer to get there. You can ditch pathfinding tests where the heuristic starts to grow beyond a certain threshold of variance, allowing for "dumber AI", which most often will result in players seeing them as less computer-like, and therefore, "smarter".


Get your head out of the grid

Don't think of your world as a grid of tiles. Think of it as a connect-the-dots puzzle of interconnected areas. It doesn't matter that our monster moves on a grid, all that matters is that it gets from point A to point B. Tune your algorithm to think outside the grid as well, and break your world up. For long-distance pathfinding, we don't need to know about the exact topography of an area, we just need a general idea of which areas are interconnected, and how long on average it's going to take to get from C to D within those areas. We don't actually need to know how long it'll take, we just need to have a semi-accurate guess. Look up LOD, and you'll get my hint here.

Also, don't worry about your NPCs being wrong so much. When enemy AI do everything perfectly every time, it wastes CPU time, and it makes interacting with them a system, not a game. In the end, nobody wants to play a system. How often your NPCs go wrong, and investigate dead ends, will often only be of concern when the player is tied to that NPC in order to progress.

If Alyx's AI in the Half Life Epsisodes were buggy and a mess, the game would be unplayable. Though, nobody's going to be too upset when a headcrab plays benny-hill with you, disappears in a maze of background props for a while, then re-emerges randomly to do some ankle-gnawing.

If anything, the headcrabs occasionally losing interest and wandering off for a while could be argued to be a feature of their AI, not a bug.