🔒 Locked

multi goal pathfinding with A*

Started by Madpierrot Sep 14, 2009 at 6:12 PM 3 replies 15.7k views

Original Post

Sep 14, 2009 at 6:12 PM

I'm using A* for a pacman path finding algorithm that returns the shortest path to eat all the dots. Runs perfectly, but when there are too many dots it bogs down so I'm looking for some ideas for a good heuristic for each state. Ones I've tried that seem to work (and I believe are admissible) are: (sum of distances of pacman to all dots) / (number of dots) and cumulative sum of the minimum of the distance of pacman to a dot, and from that dot to every other dot. So this is like a regular path finding scenario except there are multiple goals. It's similar to the traveling salesman problem (finding the shortest path) except that it's alright to visit the same position on the grid more than once.

Ashaman73

Sep 15, 2009 at 5:05 AM

Multi goal pathfinding is quite easy, I once got the same problem.

Just revert the search. Your goals are the starting points of A*(insert them in your open list) and your goal is your previous starting position.

--
Ashaman

Emergent

Sep 15, 2009 at 8:00 AM

Actually those problems are different. In Ashaman73's, you're trying to reach a terminal set with more than one node. In Madpierrot's, you're trying to visit every node in a certain set.

Despite the allowance for multiple visits it still sounds like TSP to me, but I might give it a bit more thought.

Kylotan

Sep 15, 2009 at 10:33 AM

Definitely looks like Travelling Salesman to me too, so A* is probably not the best tool. Having said that, the second heuristic looks pretty accurate - if you can precalculate the distances (or cache them as you calculate them) to make it a simple integer look-up then this method should be reasonably fast, I'd think.

If you do really just have too many dots to handle, the first thing I'd try and consider is massively reducing the state space by collapsing adjacent dots that lie on the same path (ie. between junctions) into one node so that it can be assumed that if you get one of them, you'll get all of them. On a typical board this might reduce the number of nodes to consider by a factor of 4 or more.

Madpierrot

Sep 15, 2009 at 11:14 PM

Thanks for the replies. I ended up calculating the minimum spanning trees (treating each dot as a node), caching the result and modifying it as the states changed. It still doesn't run quickly enough yet but its getting the job done. Collapsing adjacent dots into one dot is interesting and I may modify my state representation to make that possible.

Thanks for the replies.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.