CODEWITHSUNDEEP
javaartificial-intelligencea-star
GayLord
GayLord

Reputation: 135

How to improve the perfomance of my A* path finder?

So basically I coded an A* pathfinder that can find paths through obstacles and move diagnolly. I basically implemented the pseudocode from Link into real code and also used a binary heap method to add and delete items from the openlist.

Using binary heap led to significant performance boost , about 500 times faster than the insert sorting algorithm I used before.

the problem is that it still takes around on average 1.5 million nanoseconds which is around .0015 of a second.

So the question is, my plan is to make a tower defense game where the pathfinding for each mob needs to update everytime I add a tower to the map. If I were to have around a maximum of 50ish mobs on the map, that means it will take around .0015 * 50 = .075 seconds to update all paths for the entire mob. The game basically ticks( all the ingame stuff updates) every 1/60 seconds which is .016 of a second, so the problem is that it takes longer to update the paths than it takes to tick, which will lead to massive lag. So how should I go about this? DO I need to find a better algorithm for sorting the openlist or somehow divide the pathfinding tasks so that each tick only does X number of pathfinding tasks as opposed to all of them.

Upvotes: 3

Views: 1417

Answers (3)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 85966

Rather than searching from each enemy to the checkpoint, search outwards from the checkpoint to every enemy at once. This way, rather than doing 50 searches, you only need to do one.

More specifically, just do a breadth-first search (or djikstra's, if your graph is weighted) from the player outwards, until every enemy has been reached.

You could alter this strategy to work with A* by changing your heuristic EstimatedDistanceToEnd (aka h(x)) to be the minimum estimate to any enemy, but with a lot of enemies this may end up being slower than the simpler option. The heuristic must be consistent for this to work.

Additionally, make sure you are using the correct tie-breaking criteria.

Also, and most importantly, remember that you don't need to run your pathfinder every single frame for most games - often you can get away with only once or twice a second, or even less, depending on the game.

If that is still too slow, you could look into using D* lite to reuse information between subsequent searches. But, I would bet money that running a single breadth-first search will be more than fast enough.

(copied from my answer to a similar question on gamedev)

Upvotes: 4

themel
themel

Reputation: 8895

Presumably, you can back-search from the exit towards all the creeps, so you need to explore your maze only once.

Upvotes: 0

ryrich
ryrich

Reputation: 2204

Have you considered the Floyd-Warshall algorithm?

Essentially, A* is for path-finding from a single source to one or more destinations. However, in tower defense (depending on your rules of course), it is about multiple sources navigating around a map.

So for this, Floyd's algorithm seems more optimal. However, you could have your A* algorithm find paths for unit groups instead of individual units, which should optimize your calculation times.

Upvotes: 1

Related Questions