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.

Quote:

Original post by WeirdoFu 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.

yeah, but how can i find the shortest path - that's my problem.

[Edited by - nikita on March 31, 2005 12:43:46 PM]

Quote:

Original post by WeirdoFu The issue here is not really choosing the next closest pill.[...]

It is if you measure distance in the typical graph method (how many nodes away, with a node possibly meaning one 'walkable tile' in this case) rather than the typical physics way (sqrt(dx^2 + dy^2)).

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.

Precompute the distances from each pill to each other pill using breadth first search, then use a minimum spanning tree algorithm to find the shortest tree that connects all of the pills (start off at a random pill).

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.

Quote:

Original post by WeirdoFu Hmmm....don't get why everyone is so stuck on pills being node.

yeah, i think i should consider to see the intersections as nodes. that reduces enormously the number of nodes.

but, i have to start from a given position, so i cannot start off at a random pill.

if we see the intersections as nodes and not the pills theyselves, the problem is similar to the eulerian cicle problem (visiting every edge at minimum once).

we could modify the problem and see visiting every edge (with pills) at minimum once.

see http://www.cs.sunysb.edu/~algorith/files/eulerian-cycle.shtml

this method would not take into consideration the advantage of the powerpills.

could that work?

Theres 11 pills.

And like 50-60 intersections. (probably more).

HTF is this going to help?

From,
NIce coder

Think I came off a little too strong in my last post. Just to respond to a few things.

Yes, modern processors run in the GHz range, but unless in program in assembly, there is no reasonable expectation of a GHz processor to run 1 billion operations per second. You will be lucky if an average processor can process 10 million instructions per second because of the miracles of complex instruction sets, not to mention not considering how fast things can be moved around in memory when your program's memory access behavior isn't optimized. All sorts of things can cause slowdowns in a program.

From personal experience, I know that the visual studio's compiler's implementation of STL in C++ is on average 6 times slower than if you were doing the same thing with dynamic memory allocation and your average home brewed data containers.

And before when I said 1 mil operations off the bat, that was in loose terms anyways. Calculating the distance between two given point in a maze is non-trivial just because you can't just do any old euclidean or manhattan distance calculation. Let's say if you do perform a euclidean distance, that involves 1 square root, 1 addition and 2 multiplication operations. A manhattan distance will take 2 subtractions, possibly 2 absolute values and 1 addition. Then for the realistic scenario, will just be...oh well, you get the picture.

Also, I've never seen a pac-man maze with only 11 pills, unless you're only concerned with power pellets.

------------------------------------------------------------------------

nikita:
Yes, the problem pretty much reduces to a Euler cycle. However, if you want to consider the effects of power pellets, you may have to add an extra heuristic into it when solving. Probably reduce the weight on the distance travelled when the last link travelled contains a power pellet. Thus, fitness-wise, you can reward the crossing of a link with a power pellet and slighly penalize crossing links when no power pellet is in effect. Just be careful to include the fact that having multiple power pellets active at once does not give the fitness a bonus.

In the end, its all about how to manipulate the actual distance travelled and the perceived fitness of the choice.