Some questions with pacman path finding

Question

I have learned about A*, BFS, DFS and can implement them pretty well. However, some problems arise when I try to do that in solving pacman path finding problem. Let's assuming there're only two types of mazes: one has full items, as in no blank square, everything is either pacman or item-to-collect or wall; and one only has a few items (4 or less).

1. How exactly are BFS and DFS implemented if there're more than one item to collect? In such case, do they still produce optimal result?

2. What's the best algorithm/heuristic for the full-item map? What I've come up with so far is something like greedy heuristic, but it's pretty random due to the map having too many items to collect and hence, not a good idea to solve such maze.

3. Using A*, in the few-item map, is there any good way to determine which item should be taken first? I thought of trying using Mahattan distance as a rough estimate, but that doesn't sound right especially in some tricky situations.

Answer 1

The algorithms don't change if you add more food. The only thing that changes is the state space. You have to think of a new way to represent your problem. When you have only 1 food to eat, you only need the x, y position of pacman. When you have 3 dots to eat, for instance, you have to add these information into your model. You could add 3 boolean variables to indicate that pacman has passed through the dot. Now you state space is a graph made of nodes of the following kinds:

 ((x,y),FALSE,FALSE,FALSE) -> state that indicates that pacman has not eat any food
 ((x,y),FALSE,TRUE,FALSE) -> state that indicates that pacman has eat only one food
 ((x,y),TRUE,TRUE,TRUE) -> this is the goal state

To solve the problem you just run the same algorithm in your new model. BFS ans A* will always give you the optimal solution. The problem is: the more food you put, the slower it gets to find a solution. So these algorithms won't give a answer in a reasonable time. You've got think of new way of doing this.

Answer 2

1) The problem I would have with using BFS or DFS in this situation is how inefficient this will end up being, especially in the full map example. To get either algorithm to work with multiple goals, you could either build the search so it doesn't end after the first path is found, but this still wouldn't give you an "optimal" path for every piece of food on the map, or you could do a path from pacman to nearest food, that food to the next nearest, etc., find those paths, then compare those to find a truly optimal path, but I don't want to think about how long that would take.

2) I would probably stick with a greedy A*, that only looks at the nearest food (I don't see a problem with manhattan distance in most cases, as the map for pacman is already a grid; it would be suboptimal for edge cases where walls stop Pacman from accessing the closest, but this is a hard problem to solve. Manhattan would be a decent one, possibly modified by density of food instead of just distance, something like: (manhattan distance) / (total food within 3x3 square of food)

3) Short of using pathfinding on each item, then choosing the shortest, I think manhattan would do fine in the few item scenario. It wouldn't always choose the best, but 100% optimal AI isn't usually the best goal for gaming.

In this case, I would want to try greedy A* with weight favoring clusters of items as a simple, decently fast solution.

A more complex solution that should return closer to optimal paths for Pacman to follow would be to use an algorithm to find a Minimum Spanning Tree http://en.wikipedia.org/wiki/Minimum_spanning_tree but I don't know how easy that would be to implement. Here's a question discussing the merits of two Minimum Spanning Tree algorithms: Kruskal vs Prim