代码之家  ›  专栏  ›  技术社区  ›  AutoTester213

益智游戏Android DFS算法

  •  0
  • AutoTester213  · 技术社区  · 6 年前

    我有一个叫岛和桥的android应用程序,也称为 Hashiwokakero

    应用程序使用一个二维数组,每当用户重新启动游戏时,它会随机生成这些岛屿。它形成一个从0到4的矩阵,其中0=空,1-4=岛。可以有两个桥从一个岛连接到另一个岛,此时的地图是不可解的。为了解决这个游戏,用户需要使用桥连接岛屿,所以如果一个岛屿=4,它需要4个连接,如果一个岛屿=2,它需要2个连接,以此类推。。

    在我的研究中,我发现解决这个游戏的最佳算法是使用深度优先搜索- article

    我看了不同的问题 here 但似乎找不到解决方案,因为我的数组是 String 而不是 integer .

    问题 如何应用DFS算法连接岛屿?

    这是我申请表的截图。

    这是创建简单地图4x4矩阵的功能:

    private void InitializeEasy() {
          Random rand = new Random();
          String[][] debug_board_state = new String[4][4];
          setCurrentState(new State(WIDTH_EASY));
          for (int row = 0; row < debug_board_state.length; row++) {
              for (int column = 0; column < debug_board_state[row].length; column++) {
                  debug_board_state[row][column] = String.valueOf(rand.nextInt(5));
    
              }
          }
    
          for (int row = 0; row < debug_board_state.length; row++) {
              for (int column = 0; column < debug_board_state[row].length; column++) {
                  System.out.print(debug_board_state[row][column] + " ");
              }
              System.out.println();
          }
          for (int row = 0; row < WIDTH_EASY; ++row) {
              for (int column = 0; column < WIDTH_EASY; ++column) {
                  for (int colNum = column - 1; colNum <= (column + 1); colNum += 1) {
    
                      getCurrentState().board_elements[row][column] = new BoardElement();
                      getCurrentState().board_elements[row][column].max_connecting_bridges = Integer.parseInt(debug_board_state[row][column]);
                      getCurrentState().board_elements[row][column].row = row;
                      getCurrentState().board_elements[row][column].col = column;
    
                      if (getCurrentState().board_elements[row][column].max_connecting_bridges > 0) {
                          getCurrentState().board_elements[row][column].is_island = true;
                      }
                  }
              }
          }
      }
    
    1 回复  |  直到 5 年前
        1
  •  1
  •   Joris Schellekens    6 年前

    DFS可以应用于游戏状态。

    伪算法:

    1. 选择一个随机的(或其他一些标准)岛屿,仍然需要桥梁
    2. 在这个岛和它的一个邻居(显然是一个也需要一座桥的邻居)之间架起一座桥
    3. 在堆栈上推送游戏的新状态(例如此图的连接矩阵)
    4. 如果游戏包含不一致,从堆栈中弹出1个项目
    5. 返回步骤1,使用堆栈顶部作为当前状态

    正如我提到的,这是一段伪代码。 你需要改进它来处理边缘情况。 您还应该考虑防止分支因子变得过大的策略。

    示例(未彻底测试,未彻底调试):

    int[][] STARTING_CLUES = {
            {2, 0, 0, 3, 0, 3},
            {0, 1, 4, 0, 4, 0},
            {0, 0, 0, 0, 0, 0},
            {3, 0, 3, 0, 2, 0},
            {0, 0, 0, 1, 0, 2},
            {2, 0, 4, 0, 2, 0}
    };
    
    void search(){
    
        Map<Point, List<Direction>> remainingOptions = new HashMap<>();
    
        Stack<Land> gameTree = new Stack<>();
        gameTree.push(new Land(STARTING_CLUES));
    
        while(true){
    
            Land state = gameTree.peek();
            int[] p = state.lowestTodo();
            if (p == null)
                System.out.println("solution found");
    
            // move to next game state
            int r = p[0];
            int c = p[1];
            System.out.println("expanding game state for node at (" + r + ", " + c + ")");
    
            List<Direction> ds = null;
            if(remainingOptions.containsKey(new Point(r,c)))
                ds = remainingOptions.get(new Point(r,c));
            else{
                ds = new ArrayList<>();
                for(Direction dir : Direction.values()) {
                    int[] tmp = state.nextIsland(r, c, dir);
                    if(tmp == null)
                        continue;
                    if(state.canBuildBridge(r,c,tmp[0], tmp[1]))
                        ds.add(dir);
                }
                remainingOptions.put(new Point(r,c), ds);
            }
    
            // if the node can no longer be expanded, and backtracking is not possible we quit
            if(ds.isEmpty() && gameTree.isEmpty()){
                System.out.println("no valid configuration found");
                return;
            }
    
            // if the node can no longer be expanded, we need to backtrack
            if(ds.isEmpty()){
                gameTree.pop();
                remainingOptions.remove(new Point(r,c));
                System.out.println("going back to previous decision");
                continue;
            }
    
            Direction dir = ds.remove(0);
            System.out.println("connecting " + dir.name());
            remainingOptions.put(new Point(r,c), ds);
    
            Land nextState = new Land(state);
            int[] tmp = state.nextIsland(r,c,dir);
            nextState.connect(r,c, tmp[0], tmp[1]);
            gameTree.push(nextState);
    
        }
    
    }
    
    public static void main(String[] args) {
        new Main().search();
    }
    

    我还编写了一个实用程序类,处理在需要建造桥梁的土地上的常见操作(例如查找下一个可用的岛、检查是否可以建造桥梁等)

    public class Land {
    
    private int[][] BRIDGES_TO_BUILD;
    
    private boolean[][] IS_ISLAND;
    private Direction[][] BRIDGES_ALREADY_BUILT;
    
    public Land(int[][] bridgesToDo){
        BRIDGES_TO_BUILD = copy(bridgesToDo);
    
        int R = bridgesToDo.length;
        int C = bridgesToDo[0].length;
        BRIDGES_ALREADY_BUILT = new Direction[R][C];
        IS_ISLAND = new boolean[R][C];
        for(int i=0;i<R;i++) {
            for (int j = 0; j < C; j++) {
                BRIDGES_ALREADY_BUILT[i][j] = null;
                IS_ISLAND[i][j] = bridgesToDo[i][j] > 0;
            }
        }
    }
    
    public Land(Land other){
        BRIDGES_TO_BUILD = copy(other.BRIDGES_TO_BUILD);
        int R = BRIDGES_TO_BUILD.length;
        int C = BRIDGES_TO_BUILD[0].length;
        BRIDGES_ALREADY_BUILT = new Direction[R][C];
        IS_ISLAND = new boolean[R][C];
        for(int i=0;i<R;i++) {
            for (int j = 0; j < C; j++) {
                BRIDGES_ALREADY_BUILT[i][j] = other.BRIDGES_ALREADY_BUILT[i][j];
                IS_ISLAND[i][j] = other.IS_ISLAND[i][j];
            }
        }
    }
    
    public int[] next(int r, int c, Direction dir){
        int R = BRIDGES_TO_BUILD.length;
        int C = BRIDGES_TO_BUILD[0].length;
    
        // out of bounds
        if(r < 0 || r >=R || c < 0 || c >= C)
            return null;
    
    
        // motion vectors
        int[][] motionVector = {{-1, 0},{0,1},{1,0},{0,-1}};
        int i = Arrays.asList(Direction.values()).indexOf(dir);
    
        // calculate next
        int[] out = new int[]{r + motionVector[i][0], c + motionVector[i][1]};
    
        r = out[0];
        c = out[1];
    
        // out of bounds
        if(r < 0 || r >=R || c < 0 || c >= C)
            return null;
    
        // return
        return out;
    }
    
    public int[] nextIsland(int r, int c, Direction dir){
        int[] tmp = next(r,c,dir);
        if(tmp == null)
            return null;
        while(!IS_ISLAND[tmp[0]][tmp[1]]){
            tmp = next(tmp[0], tmp[1], dir);
            if(tmp == null)
                return null;
        }
        return tmp;
    }
    
    public boolean canBuildBridge(int r0, int c0, int r1, int c1){
        if(r0 == r1 && c0 > c1){
            return canBuildBridge(r0, c1, r1, c0);
        }
        if(c0 == c1 && r0 > r1){
            return canBuildBridge(r1, c0, r0, c1);
        }
        if(r0 == r1){
            int[] tmp = nextIsland(r0, c0, Direction.EAST);
            if(tmp[0] != r1 || tmp[1] != c1)
                return false;
            if(BRIDGES_TO_BUILD[r0][c0] == 0)
                return false;
            if(BRIDGES_TO_BUILD[r1][c1] == 0)
                return false;
            for (int i = c0; i <= c1 ; i++) {
                if(IS_ISLAND[r0][i])
                    continue;
                if(BRIDGES_ALREADY_BUILT[r0][i] == Direction.NORTH)
                    return false;
            }
        }
        if(c0 == c1){
            int[] tmp = nextIsland(r0, c0, Direction.SOUTH);
            if(tmp[0] != r1 || tmp[1] != c1)
                return false;
            if(BRIDGES_TO_BUILD[r0][c0] == 0 || BRIDGES_TO_BUILD[r1][c1] == 0)
                return false;
            for (int i = r0; i <= r1 ; i++) {
                if(IS_ISLAND[i][c0])
                    continue;
                if(BRIDGES_ALREADY_BUILT[i][c0] == Direction.EAST)
                    return false;
            }
        }
        // default
        return true;
    }
    
    public int[] lowestTodo(){
        int R = BRIDGES_TO_BUILD.length;
        int C = BRIDGES_TO_BUILD[0].length;
    
        int[] out = {0, 0};
        for (int i=0;i<R;i++) {
            for (int j = 0; j < C; j++) {
                if(BRIDGES_TO_BUILD[i][j] == 0)
                    continue;
                if (BRIDGES_TO_BUILD[out[0]][out[1]] == 0)
                    out = new int[]{i, j};
                if (BRIDGES_TO_BUILD[i][j] < BRIDGES_TO_BUILD[out[0]][out[1]])
                    out = new int[]{i, j};
            }
        }
        if (BRIDGES_TO_BUILD[out[0]][out[1]] == 0) {
            return null;
        }
        return out;
    }
    
    private int[][] copy(int[][] other){
        int[][] out = new int[other.length][other.length == 0 ? 0 : other[0].length];
        for(int r=0;r<other.length;r++)
            out[r] = Arrays.copyOf(other[r], other[r].length);
        return out;
    }
    
    public void connect(int r0, int c0, int r1, int c1){
        if(r0 == r1 && c0 > c1){
            connect(r0, c1, r1, c0);
            return;
        }
        if(c0 == c1 && r0 > r1){
            connect(r1, c0, r0, c1);
            return;
        }
        if(!canBuildBridge(r0, c0, r1, c1))
            return;
    
        BRIDGES_TO_BUILD[r0][c0]--;
        BRIDGES_TO_BUILD[r1][c1]--;
    
        if(r0 == r1){
            for (int i = c0; i <= c1 ; i++) {
                if(IS_ISLAND[r0][i])
                    continue;
                BRIDGES_ALREADY_BUILT[r0][i] = Direction.EAST;
            }
        }
        if(c0 == c1){
            for (int i = r0; i <= r1 ; i++) {
                if(IS_ISLAND[i][c0])
                    continue;
                BRIDGES_ALREADY_BUILT[i][c0] = Direction.NORTH;
            }
        }
    }
    }