Random path keep getting stuck

Question

Hi I'm trying to write a Tower defense game. I'm currently trying to build the path which the mobs will follow.

But my path keep getting curled up on itself.

The way the path work is with a 2d array, a grid. with 40 row and 40 col composed of cell object who contain a isPath propertie.

The way I create the path is by choosing a random direction, then checking if the cell we're trying to access is not already part of the path and that it won't collide with more than one cell (which is the cell it came from). I also look if I'm in the first col that we don't want to go left because the next cell would end up in the upper row at the last col. Same thing for going right at the end.

here's what I wrote so far for the path algorythm:

function createPath(){

var indexesOfCellsInLastCol = new Array();
for(var o = NumberOfRow; o < (NumberOfRow * NumberOfRow); o+= NumberOfRow)
    indexesOfCellsInLastCol.push(o);

var indexesOfCellsInFirstCol = new Array();
for(var k = 1; k < (NumberOfRow * NumberOfRow); k+= NumberOfRow)
    indexesOfCellsInFirstCol.push(k);

var usedDirection = [];

var x = 0;
var y = 0;

 // random walk without crossing
 for(var i = 0; i < 50000; i++){
    var direction = Math.floor((Math.random()*4));

    //always start the same way
    if(i < 10){
        if(i == 9){
            grid[2][i].isPath = true;
            grid[1][i].isPath = true;
            x = i;
            y = 2;
        }
        grid[0][i].isPath = true;
    }   
    else
    {
        switch(direction){
            //left
            case 0: 
                if(!contains(usedDirection, 0)){
                    if(collideDirection(y,x - 1) == 1){
                        //check if you are not in first col, because if you go left while you're in first                     col you go back to last row.
                        if(!contains(indexesOfCellsInFirstCol, x) && !grid[y][x - 1].isPath){
                            grid[y][x - 1].isPath = true;
                            x--;
                            usedDirection = [];
                        }
                        else
                            usedDirection.push(0);
                    }
                }
            break;
            //up
            case 1:
                if(!contains(usedDirection, 1)){
                    if(collideDirection(y - 1,x) == 1){
                        if(y - 1 > 1 && !grid[y - 1][x].isPath){
                            grid[y - 1][x].isPath = true;
                            y--;
                            usedDirection = [];
                        }
                        else
                            usedDirection.push(1);
                    }
                }                   
            break;
            //right
            case 2:
                if(!contains(usedDirection, 2)){                
                    if(collideDirection(y,x + 1) == 1){
                        //same as going left whil you're on the first col
                        if(!contains(indexesOfCellsInLastCol, x) && !grid[y][x + 1].isPath){
                            grid[y][x + 1].isPath = true;
                            x++;
                            usedDirection = [];
                        }
                        //don't be no fool and try to repeat your self
                        else
                            usedDirection.push(2);
                    }
                }                   
            break
            //down
            case 3:
                if(!contains(usedDirection, 3)){
                    if(collideDirection(y + 1,x) == 1 ){
                        if((y + 1 < (NumberOfRow - 1)) && !grid[y + 1][x].isPath){
                            grid[y + 1][x].isPath = true;
                            y++;
                            usedDirection = [];
                        }
                        else
                            usedDirection.push(3);
                    }   
                }                   
            break;
        }
    }
 }

}

I've put all the rest of my code in a js fiddle http://jsfiddle.net/xZ7tH/

I don't necessarly want a code anwser maybe just a cue to where i should go or what should I do.

I thought about watching if the path as done more than 3 left turn then it must go right. but i think it would and up in a too much linear path.

Any idea ??

Thanks for your anwsers !

Answer 1

Following is a Java implementation of a random walk on the 2d grid, with no intersections. A few notes about it:

1) Instead of repeating the code that handles different directions, i'm using a predefined list of 4 directions ([-1,0],[0,1],[1,0],[0,-1]) and shuffle it each time I scan all the possible directions to continue with.

2) Your solution seems to fail because it doesn't involve any backtracking - each time you reach a dead end, you should go back to the previous step and try taking another direction. I'm using recursion to make backtracking simple.

3) The algorithm is recursive, so it may fail with StackOverflowError for long paths. If you need it to work for long paths, consider using a stack to simulate the recursion.

4) The algorithm doesn't deal with the bounding rectangle. This requires minor changes.

public class RandomPathCreator {
  private final static List<Location> DIRECTIONS = Arrays.asList(new Location[]{new Location(-1, 0), new Location(0, -1), new Location(1, 0), new Location(0, 1)});

  public static Path randomPath(int len) {
    Path path = new Path();
    path.append(new Location(0,0)); //The random walk starts from [0,0]
    findPath(len, path);
    return path;
  }

  ///////////////////////////////
  // The main logic is here
  ///////////////////////////////
  private static boolean findPath(int len, Path path) {
    if (path.size() == len)
      return true;

    Location lastPos = path.getLast();
    Collections.shuffle(DIRECTIONS);
    for (Location dir : DIRECTIONS) {
      Location newPos = lastPos.add(dir);
      if (path.append(newPos)) {
        if (findPath(len, path))
          return true;
        path.removeLast();
      }      
    }
    return false;
  }

  private static class Location {
    public final int x;
    public final int y;

    public Location(int x, int y) {
      this.x = x;
      this.y = y;
    }

    public Location add(Location other) {
      return new Location(x + other.x, y + other.y);
    }

    @Override
    public int hashCode() {
      return 31 * (31 + x) + y;
    }

    @Override
    public boolean equals(Object obj) {
      Location other = (Location) obj;
      return (x == other.x && y == other.y); 
    }

    @Override
    public String toString() {
      return "Location [x=" + x + ", y=" + y + "]";
    }
  }

  private static class Path {
    private List<Location> list = new ArrayList<Location>();
    private Set<Location> set = new HashSet<Location>();

    public boolean append(Location l) {
      if (set.add(l)) {
        list.add(l);
        return true;
      }
      return false;
    }

    public Location getLast() {
      return list.get(list.size() - 1);
    }

    public void removeLast() {
      Location last = list.remove(list.size() - 1);
      set.remove(last);
    }

    public int size() {
      return list.size();
    }

    @Override
    public String toString() {
      return list.toString();
    }
  }
}