java - 益智游戏安卓DFS算法

标签 java android algorithm depth-first-search

我有一个名为 Islands and bridges 的 Android 应用程序，也称为 Hashiwokakero

该应用程序使用一个二维数组，每次用户重新启动游戏时都会随机生成岛屿它形成一个矩阵，数字从 0 到 4，其中 0 = 空，1-4 = 岛屿一个可以有 2 个桥岛屿连接对方，目前 map 无解。为了解决这个游戏，用户需要使用桥梁连接岛屿，所以如果一个岛屿 = 4 它需要 4 个连接如果一个岛屿 = 2 它需要 2 个连接等等..

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

我在 here 上查看了不同的问题但似乎找不到解决方案，因为我的数组是 String 而不是 integer 类型。

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

这是我的应用程序的屏幕截图。

此函数用于创建一个简单的 4x4 矩阵 map :

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

最佳答案

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

我还编写了一个实用程序类，用于处理需要在其上 build 桥梁的那 block 土地上的常见操作(例如寻找下一个可用岛屿，检查是否可以 build 桥梁等)

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

关于java - 益智游戏安卓DFS算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51674830/

上一篇：将车放置在 $nxn$ 棋盘上以便它们恰好攻击 $m$ 方格的算法

下一篇：string - 通过保持相同序列合并相似文本的算法(例如 : deduplicate log file)

相关文章：

android - 圆形 ImageView 中显示的背景黑色

javascript - 比较两个字符串数组 Javascript 的最快/最有效的方法

algorithm - 平台游戏 - 一种逼真的寻路算法

android - 我的 Tic Tac Toe 应用程序有一个错误

java - 数组上的同步未按预期显示结果

Java JNI 调用比预期慢(至少 2 毫秒/调用)

java - 在java中的cmd中打印一个表

android - 查找由 android 平台主题定义的所有可用样式

android - Application.mk 被 Android Studio 忽略

java - Servlet JDBC 也插入旧值

©2024 IT工具网  联系我们