Maze solve check

lmccandless

I needed to be able to check if a maze was solvable for a tower defense game, to prevent blocking of the path before placing towers. Couldn't find any examples of grid search algorithms in processing anywhere, so putting this up in case someone needs it.

This is a recursive search meant to find if the grid is solvable as fast as possible, it doesn't provide the fastest possible path.

.solveMaze() returns true if a path is possible and false if not.

I couldn't find any examples of solving a maze with fastest possible path solutions like A* either. If anyone could write a fastest possible route solver for an int grid like this, that'd be great :) I tried to convert the coding train's A* p5.js video to processing but it didn't work, and that video series was particularly hard to follow.

Maze.pde

     RecursiveMazeSolver solver;

int [][] grid;
float emptyAmt = 70.0; // free spaces in %
int cols = 125;
int rows = 125;
int cellSize = 6;

int startx = 2, starty = 2;       // start top left
int endx = cols-2, endy = rows-2; // end bottom right

void setup() {
  colorMode(HSB, 1.0);
  grid = new int[cols][rows];
  newGrid();
  solver = new RecursiveMazeSolver(grid, startx, starty, endx, endy);
  solve();
  //frameRate(1);
 noLoop();
}

void settings() {
  size(cols*cellSize, rows*cellSize);
}

void keyPressed() { // PRESS ANY KEY FOR NEW MAP
  redraw();
}

void newGrid() {
  for (int i = 0; i < cols; i++) 
    for (int j = 0; j < rows; j++) 
      grid[i][j] = min(1, int(random(100)/emptyAmt));

  grid[startx][starty] = 0;
  grid[endx][endy] = 0;
}

void solve() {
  boolean solved = solver.solveMaze();
  println("Solution found: " + solved + ", steps : " + solver.totalSteps);
}

void draw() {
  newGrid();
  solve();
  drawMaze();
}

void drawMaze() {
  clear();
  stroke(0, 0, 0.5,0.5);
  textAlign(RIGHT, BOTTOM);
  for (int i = 0; i < cols; i++) {
    for (int j = 0; j < rows; j++) {
      if (solver.counter[i][j] >0) { 
        float percentCompleted = ((float)solver.counter[i][j])/(solver.totalSteps);
        fill(percentCompleted, 1, 1);
        textSize(11);
      }
      else fill(0, 0, 1-grid[i][j]);
      rect(i*cellSize, j*cellSize, cellSize, cellSize);

      fill(1, 0, 0);
     // text(solver.counter[i][j], i*cellSize+cellSize, j*cellSize+cellSize);
    }
  }
}

RecursiveMazeSolver.pde

    class RecursiveMazeSolver {
  boolean[][] checked;
  int [][] counter;
  final int startX, startY; // Starting X and Y values of maze
  final int endX, endY; 
  int count;
  int totalSteps;
  final int map[][];
  final int mcols, mrows;
  final int fcols, frows;

  RecursiveMazeSolver(int [][] nmap, int sx, int sy, int ex, int ey) {
    map = nmap;
    mcols = map.length;
    mrows = map[0].length;

    checked = new boolean[mcols][mrows];
    counter = new int[mcols][mrows]; 

    fcols = mcols-1;
    frows = mrows-1;

    startX = sx;
    startY = sy; // Starting X and Y values of maze
    endX = ex;
    endY = ey; 
  }

  boolean solveMaze() {
    count = 0;
    for (int row = 0; row < mrows; row++)
      for (int col = 0; col < mcols; col++) {
        checked[col][row] = false;
        counter[col][row] = 0;
      }

    boolean c = recursive(startX, startY);
    totalSteps = counter[startX][startY];
    return c;
  }

  boolean recursive(int x, int y) {
    if (x == endX && y == endY) return true; 
    if (map[x][y] == 1 || checked[x][y]) return false;  

    checked[x][y] = true;
    if ((x > 0) && (recursive(x-1, y))) return markPath(x, y);
    if ((x < fcols-1) &&  (recursive(x+1, y))) return markPath(x, y);
    if ((y > 0) && (recursive(x, y-1))) return markPath(x, y);
    if ((y < frows-1) &&  (recursive(x, y+1)))  return markPath(x, y);
    return false;
  }

  boolean markPath(int x, int y) {
    counter[x][y] = count++;
    return true;
  }
}

jeremydouglass

Interesting -- thank you for sharing!

Is the back-and-forth motion in the found path (e.g. steps 17-30 in the top image) a desired feature for this game, or is it something you are hoping to work around with a better algorithm?

lmccandless

The back and forth nature turns out to be a result of the order the last four if statements inside the recursive function are done. The order above is actually worst possible for the example, it's biased for a target that is north east of the the origin point.

For my game my checks are always going to be biased to move south west so this adjustment to the code is good for me, though it might be nice to have four different recursive functions and automatically detect which biased search to use based on the start and finish locations.

  boolean recursive(int x, int y) { // compare order biased to move towards a southwest target
    if (x == endX && y == endY) return true; 
    if (map[x][y] == 1 || checked[x][y]) return false;  
    checked[x][y] = true;
    if  (((x < fcols-1) && (recursive(x+1, y)))  
      || ((x > 0)       && (recursive(x-1, y)))   
      || ((y < frows-1) && (recursive(x, y+1)))
      || ((y > 0)       && (recursive(x, y-1)))) {
      counter[x][y] = count++;
      return true;
    }
    return false;
  }

Chrisir

See also

http://www.lagers.org.uk/ai4g/index.html

lmccandless

I did try out the PF_PathFinder demo from the path finding library and I had a hard time figuring out how to implement it, the demo code is too big to be clear. I just want to run it on a integer grid, not have to recalculate nodes and edges every frame or load the map from an image or file.

this is where I'm at with my flow field path finding.

Chrisir

That looks awesome!

I was thinking about programming a steam engine based on flow field path finding. It would have to detect where the density / pressure is high and then move the piston and wheels accordingly.

https://cdn4.explainthatstuff.com/how-steam-engine-works.gif

http://www.explainthatstuff.com/steamengines.html

lmccandless

I've always been tempted to recreate a better version of something like this.

I want to get computer control over the intake and exhaust valves, fuel, ignition timing, and port geometry and see how well I can get a neural network or genetic algorithm to tune for power/efficiency.

Or maybe turbine blades (using the fluid portion of the PixelFlow library) like this guy did almost 10 years ago

Chrisir

exactly