The disadvantage of this in a game is that it makes your pathfinding less predictable to players, though. To take those last two examples as, well, examples, people would probably remark on the little "bump" in the path, especially if this is a very common route.
I don't necessarily disagree with you, but it's still weighing the advantages and the disadvantages. My complaint can, for example, be solved by letting people assign weights to tiles.
The good part about heuristics is that you can adjust the strictness as needed by picking different ones! That particular one was 5 ε IIRC, so if it was slightly too lose for you then you could choose a slomewhat stricter heuristic that, at the cost of additional node checking, would return a path slightly closer to the actual route and smooth that bump right out if you really needed it gone. So in the end you have a heuristic that only checks half as many tiles instead of 1/3rd; it means a fortress that can have twice as many dwarves running before FPS death sets in than with a purely admissible heuristic like manhattan distance.
And there's nothing that says you can't choose a heuristic capable of handling "base weights" that could be preset or player-designated as well; heck, the idea of "Weighting" itself is exactly what heuristics do, they weight certain tiles varying amounts based on their distance from the goal or some other predefined function. Adding an additional input of player weights to let them actually control pathfinding a bit more directly is a pittance to factor in in the vast majority of cases.
A good heuristic can provide massive speedups at the cost of nothing but a little bit of development time and a tiny bit of path regulation (which you can tweak to yourself to reach a point where most people aren't going to be able to tell the difference, and if really necessary you could always add a "player weighting" or "waypoint" system to let players assume direct control of pathfinding if they really depend on it). Sure, it's not that big of a deal if you're running your little test dungeon with 8 units in it. But once you expand that unit count out to 100, or 1000, or 10k (which could be reached in C:DDA with Z-levels on, for example) it starts to matter a bit. Or how about going from 2D to 3D with flying units? That takes your amount needed to check up from n
2 to n
3, and speed will
definitely start to matter at that point. So ask yourself the question, which would make the player more excited, having pathfinding that is always the fastest (even when it leads to results that seem counter-intuitive to humans, as mentioned earlier), or having the unit cap be double what it currently is?
(Of course, if you're deadline is tight and you know that you are never really going to be handling more than a few units then by all means feel free to avoid anything more complex than manhattan distance, but pathfinding quickly becomes such a speed critical segment of many programs, and the work/reward ratio is so great for good heuristics, that it's almost always worth it to spend even a little bit of time picking and implementing one.)
Author
Topic: if self.isCoder(): post() #Programming Thread (Read 903786 times)