Sign in to follow this  
gusso

what is the best path finding algorithm?

Recommended Posts

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?

Share this post


Link to post
Share on other sites
For general pathfinding on a grid, A* is good enough for many uses. You can't define a single 'best' path-finding algorithm - each has its strengths and weaknesses. If you can give more detail about what exactly you are trying to do, we might be able to give more pertinent advice.

Among other questions, is your playing field static, or must the pathfinding deal with changes to the terrain?

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Quote:
Original post by gusso
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.
Many types of pathfinding can be made very efficient at run time by doing some precalculation (for A* we can precalculate the entire grid), but obviously this is very hard if your terrain can change at any time.

Share this post


Link to post
Share on other sites
Creating dynamic pathfinding is not that hard, simply keep "locks" on the links between the various nodes. I.e, "disable link between A and D if the door is locked".

AStar is more than good for RTS. Small memory-footprint if done right. :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this