Parker's Pathing
· 3 min · graph theory , game development
TLDR — I’ve been gooning for 6 months, but made a game.
Please play my game. It took a lot of time and it is really fun I promise.
For my AP Computer Science Final, I, along with 2 great teammates, made a game where your goal is to traverse the entirety of a grid, with numbered cells dictating where a certain move should land on (e.g. move 5 must land on the cell numbered 5).
One of the main features I wanted was infinite level generation. For those familiar with a bit of graph theory, my idea to make levels was as follows:
- Find a random hamiltonian path of some kind in a 2d matrix
- Label (randomly) some percentange of the path with their indices
This is actually quite a hard problem, and I had 2 ideas of solving this:
- Use some sort of random walk on an infinite grid
- Google it to find something that worked for regular sized grids
Although the first method allowed for irregularity (and therefore uniqueness) in the shape of the puzzle, I had no way of controlling the difficulty nor the dimensions of the resulting puzzle.
I thought of a few ways to potentially combat the grid of exploding in one axis, but in the end I decided not to continue with any of them.
Searching on Google for “random hamiltonian path in 2d grid” gave some pretty promising results. The top two results, stackoverflow.com and clisby.net, both directed me to this paper by Oberdorf et al. referencing a “backbite” move and detailing a rough estimate of how many moves should be performed to ensure a “random” path.
I tried looking for an implementation of this algorithm, but got no good results. So, I will try to explain how the algorithm works in this post.
The “Backbite” Move#
The algorithm for generating a random Hamiltonian path in a 2D grid, as described in the paper, involves two things:
-
Starting with a known Hamiltonian path: usually a simple snake-like traversal of the entire grid.
-
Performing repeated “backbite” operations: these are specific edge-swapping moves that slightly alter the path while keeping it Hamiltonian.
A backbite move works like this:
-
Pick one of the two endpoints of the current path.
-
Choose a random neighbor of that endpoint.
-
If that neighbor is already part of the path, and the move would form a loop of 4 or more points, break the old connection and reconnect it at the new point.
-
Otherwise, ignore the move.
This operation slightly “bends” the path. Doing it thousands of times leads to a path that’s much less structured and more random without ever breaking the Hamiltonian property.
According to the paper, the number of backbite moves needed to fully randomize the path is on the order of the number of cells in the grid squared. So for a 10x10 grid, you might want to do ~10,000 moves.
Implementation Notes#
- To find the edge to remove, traverse down the path until you reach the node with 3 connected neighbors to it, and remove the edge you are on
- Picking a random endpoint is very quite important, if you’re path is directed, consider making a function that reverses the current path at random, so that you only have to implement the backbite move on one end of the path.
Here is my Java code for this algorithm:
public class Path {
private static int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
private Cell start, end;
private Cell[][] data;
private int size;
/**
* Creates a zig-zag Path in a square grid
* @param size size of the square grid
*/
public Path(int size) {
this.size = size;
data = new Cell[size][size];
for(int y = 0; y < size; y++) {
for(int x = 0; x < size; x++) {
if(y % 2 == 0) {
if(x < size - 1) {
data[y][x] = new Cell(x + 1, y);
} else {
data[y][x] = new Cell(x, y + 1);
}
} else {
if(x > 0) {
data[y][x] = new Cell(x - 1, y);
} else {
data[y][x] = new Cell(x, y + 1);
}
}
}
}
start = new Cell(0, 0);
if(size % 2 == 0) {
end = new Cell(0, size - 1);
} else {
end = new Cell(size - 1, size - 1);
}
data[end.getY()][end.getX()] = new Cell(-1, -1);
}
/**
* a modified implementation the backbite move described in
* <a href="https://arxiv.org/pdf/cond-mat/0508094"> this paper </a>
*/
private void backbite() {
boolean valid = false;
Cell oldStart = data[start.getY()][start.getX()];
while(!valid) {
valid = true;
int ran = (int) (Math.random() * 4);
int x = start.getX(), y = start.getY();
int nx = x + dx[ran], ny = y + dy[ran];
if(nx < 0 || nx >= size || ny < 0 || ny >= size
|| (data[y][x].getX() + dx[ran] == nx && data[y][x].getY() + dy[ran] == ny)) {
valid = false;
} else {
data[start.getY()][start.getX()] = new Cell(nx, ny);
}
}
Cell prv = start, cur = oldStart;
while(!cur.equals(data[start.getY()][start.getX()])) {
Cell temp = data[cur.getY()][cur.getX()];
data[cur.getY()][cur.getX()] = prv;
prv = cur;
cur = temp;
}
start = prv;
}
private void reverse() {
Cell cur = data[start.getY()][start.getX()];
Cell prv = start;
while(cur.getX() != -1) {
Cell temp = data[cur.getY()][cur.getX()];
data[cur.getY()][cur.getX()] = prv;
prv = cur;
cur = temp;
}
data[start.getY()][start.getX()] = new Cell(-1, -1);
Cell temp = start;
start = end;
end = temp;
}
/**
* Generates a random hamiltonian path inside from the current path
*/
public void genHamiltonianPath() {
int iterations = (int) (20 * size * size * Math.log(size) * Math.log(size));
for(int i = 0; i < iterations; i++) {
if(Math.random() < 0.5)
reverse();
backbite();
}
}
/**
* Turns the current path into a list of cells
* @return List of cells representing the order of the Hamiltonian path in the grid
*/
public List<Cell> toList() {
List<Cell> ans = new ArrayList<Cell>();
Cell cur = start;
while(cur.getX() != -1) {
ans.add(cur);
cur = data[cur.getY()][cur.getX()];
}
return ans;
}
}
class Cell {
private int x;
private int y;
private boolean isPartOfPath;
public Cell() {
this.x = 0;
this.y = 0;
this.isPartOfPath = false;
}
/**
* constructs a cell with the given coordinates
* @param x the x-coordinate of the cell in the grid
* @param y the y-coordinate of the cell in the grid
*/
public Cell(int x, int y) {
this.x = x;
this.y = y;
this.isPartOfPath = false;
}
public void setPartOfPath(boolean partOfPath) {
this.isPartOfPath = partOfPath;
}
public boolean isPartOfPath() {
return isPartOfPath;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
/**
* checks for equality between current and other Cell
* @param o the other object
* @return true/false if the coordinates are the same
*/
@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()) return false;
Cell cell = (Cell) o;
return x == cell.x && y == cell.y;
}
}