Algorithm: objects moving within graphs

Problem: How do I move objects around in a maze like Pac-man?

A maze game (like pac-man) uses a maze. This maze looks like a 2D array of open and closed squares (and it is), but a better way to think about it is as a GRAPH. This isn’t a graph like the 2D plot of data:

In pure math terms, a directed graph is “a set of points connected by lines”. That simple. Just some points, and some lines that connect some of them. If you imagine the points in a pac-man maze are in the center of each square, then there are invisible lines connecting the points through the open hallways.

So moving objects around in a maze becomes “traversing the graph”, moving from point to point along a connecting line.

When your objects live in a maze (or other type of GRAPH), they really have two positions; one in “grid-space” and one in “screen-space”. screen-space is in pixels, of course. Grid-space corresponds to the blocks of the maze you have. You’ll have to keep these two coordinate systems straight, in your head and in the code, or you’ll get very confused.

It can help to make two functions, ScreenToGrid() and GridToScreen(), to keep the translations straight. If your game supports scrolling and zooming of the display, these functions become critical.

Each object should have x and y variables for where they are (this should not be a surprise) . But in this case, those variables should be for the POINT the object is moving to. There should also be x and y for the point the object is leaving, and there should be a float value for the percentage of the distance the object has traveled between the two points. Something like:

int nextX, nextY;
int prevX, prevY;
float percentMoved = 0;

Moving between the points is as simple as incrementing the percent variable:

percentMoved = percentMoved + speed;
if (percentMoved >= 1.0)
percentMoved = percentMoved - 1.0;

prevX = nextX;
prevY = nextY;

// make the decision about what point to move to here
// put the results of that decision into nextX and nextY

Now, how do we know exactly WHERE the object is? We can calculate that with:

float drawX, drawY;
drawX = (percentMoved) * nextX + (1-percentMoved) * prevX;
drawY = (percentMoved) * nextY + (1-percentMoved) * prevY;

Notice how (in the above pseudo-code) drawX is initially still in “grid-space”. We multiply by PIXELS_PER_GRID_SQUARE in order to translate the variable into screen-space.

If you’re making a game even remotely like pac-man, you should use this algorithm. If you’re making a game with halls and corridors (in 2D or 3D), and you need enemies to move through them, you can make a “pathmap” from points connected by lines. This pathmap would be invisible to the player, but it’s a directed graph, which means objects can move along it using this algorithm.

Leave a Reply