Cool map Randil!
Now if I remember graph problems correctly, you need to define Vertices and Edges (or as I like to call them Nodes and Paths). Each Vertice is connected to 0 or more other Vertices with an Edge. You can assign each edge a value (distance). The trick then is to find the sequence of visiting a set of vertices or traversing a set of edges such that the sum of the values of each edge is minimized.
So in this case, using this map, you would assign each intersection to a Vertice, and then each path between intersections as an Edge joining the Vertices. The Edge would be given the pixel distance as it's value. You'd also have to define which Edges need to be traversed -- some of the paths in the map do not have dots to be eaten so do not need to be traversed to clear the level.
This does not precisely model the game though. Pretty close, but I think it could be refined more, and if we want "frame perfection" I think it should be more detailed. One thing that would not be modeled correctly is when when you do a 180 turn like in Randil's movie. You do not have to go all the way to the intersection before turning around, so the distance would be slightly less than what this model would say.
Also, I think "distance" value in the edges should be measured in terms of frames rather than pixels. From what I've observed, the number of frames between eating dots actually varies, usually 11 or 12 frames (can be as low as 6 though!). I have not tested it extensively though and can't say if the number of frames between dots is constant going left/right, or doing it at a different time. If it is constant each dot would be a Vertice and the edges would have the distance in frames. Still not perfect, and doesn't really solve the 180 turn around problem either, since the dots are not at one position on the board: pacman's position when the dot is "eaten" is not the same when coming from the right and left, so in the model it would have account for where it is coming from. Let me try to clarify with a diagram:
1 2 3
o--o--o
So in moving from 1 to 2 to 3, the time from eating 2 to 3 would be longer than if you move from 3 to 2 back to 3, because the "eating" gets registered from the left side of the dot rather than the right side.
Do you think this is relevant, or am I missing something that makes this simpler than I think? Am glad other people are interested in this problem!
