Some questions with pacman pathfinding

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 the pacman pathfinding problem. Let's assume there are 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's more than one item to collect? In such a case, do they still produce optimal results?

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 Manhattan distance as a rough estimate, but that doesn't sound right especially in some tricky situations.

Answer 1

The algorithms will not change if you add more food. The only thing that changes is the state space. When you have only one food to eat, then you only need the x, y position of PacMan. When you have 3 dots to eat, for instance, you have to add this information into your model. You could add 3 boolean variables to indicate that Pacman has passed through the dot. Now your state space is a graph made of nodes of the following kinds:

 ((x,y),FALSE,FALSE,FALSE) -> state that indicates that Pacman has not eaten any food

 ((x,y),FALSE,TRUE,FALSE) -> state that indicates that Pacman has eaten 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 and A* will always give you the optimal solution. The main obstacle is that when you put more food, the slower it gets to find a solution. So these algorithms won't answer in a reasonable time. You've got to think of a new way of doing this.

If you are looking to learn more about Artificial Intelligence then visit this Artificial Intelligence Course which will cover topics like Euclidean distance, Pearson Correlation Coefficient, Brute Force Algorithms, traveling salesman problem, NeuroEvolution of Augmenting Topologies, Fitness Function, Resolution Algorithm,k-nearest neighbors algorithm, Markov Model, Genetic Algorithm,deep first iterative deeping and many more.