Алгоритм Android DFS Puzzle Game

У меня есть приложение для Android под названием "Острова и мосты", также известное как Хашивокакеро.

Приложение использует двумерный массив, который случайным образом порождает острова каждый раз, когда пользователь перезапускает игру. Он формирует матрицу с числом от 0 до 4, где 0 = ноль и 1-4 = остров. Из одного острова могут выходить 2 моста для соединения. другой, карта на данный момент не разрешима. Чтобы решить игру, пользователю необходимо соединить острова с помощью мостов, поэтому, если остров = 4, ему нужно 4 соединения с ним, если остров = 2, ему нужно 2 соединения и т. д.

в своем исследовании я обнаружил, что лучший алгоритм для решения игры - использовать поиск в глубину - статья

Я рассмотрел другой вопрос о здесь, но, похоже, не нашел решения, поскольку мой массив имеет тип String, а не integer.

ВОПРОС как можно применить алгоритм DFS для соединения островов?

вот скриншот моего приложения.

Алгоритм Android DFS Puzzle Game

Это функция для создания простой матрицы карты 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;
                  }
              }
          }
      }
  }

Разве не было бы проще начать строить доску по одному острову за раз, используя правильные ходы, чтобы существовало решаемое решение? Может захотите полистать: gamedev.stackexchange.com

Morrison Chang 03.08.2018 16:39

Итак, просто чтобы убедиться, что вы говорите, что я должен строить по одному острову, проверяя соединение, затем строить следующий, делать то же самое и так далее?

AutoTester213 03.08.2018 16:43

Верный. Прямо сейчас, если я правильно понимаю ваши правила игры, островки размера 4 по краям делают доску невыигрышной, так как на ней может быть не более 3 соединений.

Morrison Chang 03.08.2018 16:46

Да, правильно, я мог бы использовать жестко запрограммированный массив, чтобы выполнить эту работу, но моя цель - создать карту случайным образом.

AutoTester213 03.08.2018 16:50

Если вы хотите добавить «тупики», чтобы получить интересную доску, добавьте их в конце после того, как вы создали решаемую доску. Удачи.

Morrison Chang 03.08.2018 16:53

@MorrisonChang Я забыл упомянуть, что с одного острова может выходить два моста

AutoTester213 10.08.2018 13:28
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
6
530
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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

отличный ответ, не могли бы вы привести пример кода?

AutoTester213 13.08.2018 15:31

Direction является частью Path.Direction или это образец класса?

AutoTester213 15.08.2018 16:57

Это перечисление 4 направлений (север, восток, юг, запад).

Joris Schellekens 15.08.2018 19:15

Я запускаю код, генерирую первую строку матрицы, и программа вылетает, у меня осталась ошибка Attempt to read from null array.

AutoTester213 16.08.2018 10:12

Я предлагаю вам создать новый вопрос со всем исполняемым кодом, а затем попросить о помощи. В общем, не одобряется просто просить людей решить вашу проблему за вас в StackOverflow.

Joris Schellekens 16.08.2018 11:12

Эта строка здесь приводит к сбою алгоритма для меня if (tmp[0] != r1 || tmp[1] != c1) return false;, я пытался отладить его, я получил следующие значения: tmp: nullr1: 0 и c1: 1

AutoTester213 22.08.2018 10:56

Другие вопросы по теме