I play a lot of games. I know how hard they are to make and that even the bad ones are designed by very talented people, certainly more skilled than I am.
So why is pathfinding so hard?
You would think that this problem would be solved by now. And in many games it seems to be. The best RTS of recent years have had negligible path finding problems and even made it possible for larger units to move seamlessly through crowds of smaller units. There are exceptions. The cavalry pathfinding in Age of Empires III leaves a lot to be desired – all the pretty horses run around crazily if a selected group of them is interrupted in its most perfect path. By and large, though, the Ensemble people have no real problem in making sure that your units get where you want them to go.
But I’m playing a RTS now that has some major issues. Vehicles won’t go through infantry, and won’t take an alternate route if the viable path they are rejecting is shorter. Units won’t shunt to the side to let other units pass, and I’m not talking about crowded routes here. There is daylight between the units – enough room for things to move through, I would think.
It’s easy to say that of course the bigger budget games do this well because they are bigger budget games, but since so many of the smaller titles have embraced stuff like physics engines why not look into finding a better pathfinding routine? Am I missing something?
Pathfinding used to be traditionally very hard to do (by “used to be” I mean about 10 years, when I did hobby game coding). It wasn’t easy back when games were basically grids–I’m sure if you search you can find something I think was called the “A+1” algorithm. I imagine it must be harder now when a unit has to find its way around 3D terrain in realtime without an easy reference to passable/impassible terrain. Pathfinding is also probably tied to the guts of the engine, and so it’s hard to pop out and put into another game.
None of this is an excuse for bad pathfinding. Clearly it can be done well, and should be done well for RTS. But to my knowledge, it is hard enough to explain why smaller companies might have to skimp.
The algorithm you are thinking of is A* (pronounced a-star).
Check out Amits’s website on the subject at http://theory.stanford.edu/~amitp/GameProgramming/.
Pathfinding is a “solved” problem from a theoretical perspective, but I suspect that RTS games will usually end up having to “cut corners” due to the real-time requirements, Another issue is that most good pathfinding algorithms are built on heurestics (i.e., intelligent guesswork as to which of different paths is the shortest); if your heurestics are poor, then the pathfinding will also suffer. Though (IMO) reasonably good heurestics should not be a problem in an RTS game.
I think Thomas is thinking of the A* algorithm, btw.
Pathfinding is still nontrivial, but even more distressing is that many companies don’t allocate the production resources needed to the task.
A*! Damn my faulty memory!