随机路径一直被卡住

Random path keep getting stuck

本文关键字：一直路径随机更新时间：2023-09-26

嗨，我正在写一个塔防游戏。我目前正在努力构建暴徒将要遵循的道路。

但我的路一直蜷缩着。

路径的工作方式是使用一个2d数组，一个网格。其中40行和40列由包含isPath属性的单元格对象组成。

我创建路径的方法是选择一个随机方向，然后检查我们试图访问的单元格是否已经是路径的一部分，并且它不会与多个单元格（即它来自的单元格）碰撞。如果我在第一列，我们也不想向左走，因为下一个单元格会在最后一列的上排。在最后向右走也是一样。

以下是我迄今为止为路径算法所写的内容

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;
        }
    }
 }

}

我把剩下的代码都放在js中了http://jsfiddle.net/xZ7tH/

我不一定想要一个代码提示，也许只是一个提示，告诉我应该去哪里或应该做什么。

我想观察一下，如果这条路左转超过3圈，那么它就必须向右走。但我认为它会以一条过于线性的路径上升。

知道吗？？

谢谢你的指导！

下面是一个在2d网格上随机行走的Java实现，没有交集。关于它的几个注意事项：

1）我没有重复处理不同方向的代码，而是使用了一个预定义的4个方向列表（[-1,0]、[0,1]、[1,0]、[0，-1]），每次扫描所有可能的方向时都会打乱它以继续。

2）你的解决方案似乎失败了，因为它不涉及任何回溯——每次你到达死胡同时，你都应该回到上一步，并尝试采取另一个方向。我使用递归使回溯变得简单。

3）该算法是递归的，因此对于长路径，它可能会因StackOverflowError而失败。如果需要它来处理长路径，可以考虑使用堆栈来模拟递归。

4）该算法不处理边界矩形。这需要进行细微的更改。

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();
    }
  }
}