The issue here is not really choosing the next closest pill. The problem with just looking at the pills is that you don't take into the consideration of the topography of the "maz" itself. Yes, choosing the next closest pill in a greedy way may work, but that may mean you have to circle all the way around to get to it, even though you were very close to it, since there could be a wall blocking it. However, in the process of circling around, you would have eating alot of other pills as well, possibly. This is why you consider the topography of the maze instead of just look at the pills. In being able to choose the shortest path to traverse all paths in the maze, you're guaranteed to have eaten all the pills, its as simple as that. If the pills are evenly spaced, then the distance you traverse can then be meassured by the number of pills that can be on the path.

Looking at just the pills may seem like you're simplifying the problem, but all it does is over complicate it computationally. Unless, of course, there are way fewer pills than intersection, which in most pac-man style games is probably a no.

Well, if we look at a pill as a node, then you may have 10 times more nodes than you will need and have a damn hard time processing all of them. Under the assumption that you will get to all pills by traversing all paths at least once reduces the number of nodes that needs to be processed down to just the intersections of the paths.

Even with A* search, you can assign weights to each link individually. No one said the distance between nodes had to be uniform.

For one thing....there will be alot of backtracking involved, that's for sure.

The simplest solution off the top of my head right now is a simple trial and error method that you just keep running for 30 seconds and keep track of the best answer found.

1. Start from a random node/intersection.
2. Probabilistically choose the next node to go to on an untraversed path/link, based on the distance (number of pellets to the next node). You can do this by having the longest paths have higher probability of being chosen or the shortest.
3. Once traverse, mark a link as being traversed.
4. Push the path onto a stack, or just simply the node you came from
5. Repeat steps 2 - 4 until the current node you're at has no more untraversed paths
6. If no more traverable paths at current node, backtrack to the last node visited that still has paths that have not been traversed. Go to step 2.
7. If all paths traversed, then end.

Of course, along the way, you'll have to keep track of the order of the nodes visited, even when backtracking, for that will be your path. You may also choose to keep track of the distance travelled or simply do that at the end when you have the full path.

This should be fairly fast if you code it right. Probably execute it 10 - 100 times a second and always keep track of the best answer found so far. You'll probably not get an optimal solution, but will probably get something pretty good.

Hmmm....don't get why everyone is so stuck on pills being node.

Simply speaking, let's look at an example.
With a 40 x 40 maze, considering that 1 pill occupies a tile and that on average half the tiles have pills, that's 800 pills, which means 800 nodes right off the bat. Then calculating the distance from each pill to each other pill will be 800 * 799 / 2 calculations, which may involve who knows how many other smaller operations. So, we can estimate at simply 320000 operations just to set things up. Then a minimal spanning tree algorithm averages at O(n^2), so that means another 640000 operations at least of varying type. So, the whole set up process will take you around 1 million operations, right off the bat!!!

On the other hand, looking at intersections as nodes, you reduce the node count drastically. In the worst case, you have as many intersections as pills and that becomes an easy problem anyways. But an average pac-man maze will have an intersection count by a factor of 10 less than the total pill count. That gives you way more time to explore other possible solutions and possibly find better ones. so, instead of 800 nodes, we may very well be dealing with 80.

Your average computer would do that in a few ms.

A million ops is really nothing to be conserned about.

A few trillion is.

From,
Nice coder