At current date, what is the best path finding algorithm overall?. I'd like to be able to abstract the system and implement it with any sort of loose grid, nothing too strict. Another important factor is speed; I must be able to find at least 200 paths without much cost. I thought about finding just a bunch of paths and having units follow a lead unit but game-wise it doesn't seem to work very well, perhaps for long distances it would but if you got ambushed your units would die one by one and that's not good at all... But back on the algorithm, which one should I implement?, is A* still any good for most cases?

Well, whether the terrain changes or not I think the movement and path finding are still 2 separate things, right? but I'm still unsure about implementing A* just yet because of the added complexity when optimizing it for speed... it gets pretty nasty!

At the moment I have a grid-based map but I'm unsure whether this is the best option for an RTS game to begin with. Picture AOE2 for instance. I would pretty much like to port my game into a mobile device in the near future, so I need code that isn't going to require tons of processing power just to do a few trivial tasks.

Quote:Original post by Rasmadrak
AStar is more than good for RTS. Small memory-footprint if done right. :)

Straight A* has a potentially huge memory footprint. Up to the size of the graph that you are searching over [which could very easily be infinite if you are adding time into your calculations in an attempt to coordinate group movement]. Realistically though, it tends to perform 'well enough' if you let it run in the background, and take measures to keep your graphs simple and course. Memory is cheap, and most machines have enough of it that you can throw a couple dozen megabytes at pathfinding without too much concern... but yes, A* is a memory hungry monster in many respects, especially 'optimized for speed' versions, and is perfectly capable of depleting any resources you can throw at it if you aren't careful. Also, it is provably computationally 'optimal', in that it explores a minimum of states [tiles in your map] to discover its final path.

'Computationally optimal' though is a somewhat fishy thing when dealing with games though. The argument for it's optimality is that the cost associated with generating and evaluating states [points on your map] is overwhelmingly large compared to the cost associated with moving data around, and thus should be the operation on which the complexity is based. For most applications in AI, this is a pretty fair assumption, but it isn't so much the case in most applications of finding-a-path-on-a-game-map. The cost of discovering next states [next tiles/triangles/whatever] is extremely fast [a player can go everywhere there isn't a wall, easy as pie], and actually shifts the equation drastically into the other direction in many instances. Moving the data around and operating on the priority queues, performing sorts on working sets, and all that other jazz that comes along with many A* implementations becomes the bottleneck.

To the rescue are a number of off-shoots of the A* algorithm, including IDA* if you are dealing with a grid-based map [lots of same-distance paths], or 'fringe search'/'frontier search'/any of the other names that have been given to it. IDA* completely solves the memory bound, and 'fringe search'/* lightens up the memory bound as well, but not as drastically [IDA* effectively takes no memory at all]. Both strategies result in a much simplified data-handling process that can result in higher performance than the regular A* algorithm for applications where state exploration isn't the big performance hit.

Another thing you might want to consider is sacrificing a bit of optimality, and using a heuristic that isn't an exclusive under approximation. to help your search converge more rapidly [or skip iterations if you are using IDA*]. This means that you loose certainty with respect to the optimality of your paths, but in most every situation, your paths are already going to be sub-optimal due to the steering you are going to be using. Near-optimal is often good enough for games, and can result in substantially more rapid path discovery in some instances.

Personally, I've had a lot of luck with 'fringe search' on geometrically non-uniform maps, and an aggressive IDA* for grids. Also, there are some instances in which over-approximating heuristics can be a pretty big win, but it is something you need to look at on a case-by-case basis. A* is a general solves-any-problem sort of tool, and if you are intending on writing once and using for a wide range of purposes, it is a decent choice.