Блог

Главная - Вопросы по программированию - Существует ли алгоритм поиска всех возможных маршрутов в настольной игре?

Существует ли алгоритм поиска всех возможных маршрутов в настольной игре?

#javascript #algorithm #path-finding

Вопрос:

Я пытаюсь написать функцию javascript, которая находит все возможные маршруты длиной N на доске (сетка 15х15), где игрок не может двигаться по диагонали. Мне удалось придумать довольно простое рекурсивное решение, но я подозреваю, что оно крайне неоптимизировано.

Вот код:

 search(n, u, v) {

    if (n == 0 || isWall(u, v))
        return;
        
    board[v][u] = 2;
    
    search(n - 1, u, v - 1);
    search(n - 1, u   1, v);
    search(n - 1, u, v   1);
    search(n - 1, u - 1, v);
    
    return;
}

плата представляет собой 2d-массив, содержащий данные платы. Свободные пространства, стены и доступные пространства представлены 0, 1 и 2 соответственно.

Вот пример того, как это выглядит при N=6

Доска для отбора проб

ПРАВКА: Как уже упоминалось ниже, я пытаюсь найти все доступные ячейки за N или менее ходов.

Комментарии:

1. Ну, технически, то, что вы здесь написали, не находит «все возможные маршруты длиной N», а скорее » все доступные ячейки за N или менее ходов «, что значительно проще. Чего ты действительно хочешь?

2. да, можно найти все маршруты, но, как правило, их будет слишком много для повторения. Можно подсчитать маршруты или показать, какие позиции доступны в течение n ходов.

3. en.wikipedia.org/wiki/Dijkstra’s_algorithm

4. Для каждой доступной ячейки вы можете найти кратчайший маршрут к этой ячейке с помощью алгоритма поиска A*. Это дало бы вам маршрут к каждой отдельной ячейке, но это были бы не все маршруты. Этого достаточно?

Ответ №1:

Как писали другие, вы должны использовать обход в ширину, а не обход в глубину.

Во-вторых, вы не должны возвращаться к ячейке, которая уже отмечена значением 2, поэтому ваше условие для продолжения должно заключаться в том, что текущая ячейка имеет значение 0.

Я бы предложил реализовать обход с использованием двух массивов:

 function search(board, n, u, v) {
    let count = 0;
    let frontier = [[u, v]];
    
    while (n-- > 0 amp;amp; frontier.length) {
        let newFrontier = [];
        for (let [u, v] of frontier) {
            if (board[v]?.[u] === 0) {
                board[v][u] = 2;
                count  ;
                newFrontier.push([u, v - 1], [u   1, v], [u, v   1], [u - 1, v]);
            }
        }
        frontier = newFrontier;
    }
    
    return count;
}

let board = [
    "11111111111111",
    "10000000000001",
    "10000000000001",
    "10011100111001",
    "10010000001001",
    "10010000001001",
    "10000000000001",
    "10000000000001",
    "10000000000001",
    "10010000001001",
    "10010000001001",
    "10011100111001",
    "10000000000001",
    "10000000000001",
    "11111111111111"
].map(row => Array.from(row, Number));

let res = search(board, 6, 2, 2);

console.log("number of cells reached: ", res);

console.log(board.map(row => row.join(" ")).join("n"));

Ответ №2:

Вы должны использовать поиск по ширине, чтобы решить свою проблему. Вы можете прочитать о BFS здесь. Ниже приведен мой код unran на Java. Я рекомендую не использовать это, потому что я закодировал его в редакторе StackOverflow, но основная идея есть.

 public class BFS {
    static final int MAX_N = 100;
    public static void main(String[] args) {
         int[][] board = new int[MAX_N][MAX_N];
         Queue<Point> q = new LinkedList<>();
         List<int[]> reachable = new ArrayList<>();
         boolean[][] vist = new boolean[MAX_N][MAX_N];
         q.add(new Point(0,0,0));
         vist[0][0] = true;
         while(!q.isEmpty()) {
             Point curr = q.poll();

             if(vist[curr.x][curr.y]) continue;
             if(curr.move > N) continue;
 
             reachable.add(new int[]{curr.x, curr.y});

             // dx and dy array not shown
             for(int i = 0; i < 4; i  ) {
                 int nx = curr.x   dx[i];
                 int ny = curr.y   dy[i];

                 if(nx < 0 || nx >= MAX_N || ny < 0 || ny >= MAX_N) continue;
                 if(board[nx][ny] == 1) continue;

                 vist[nx][ny] = true;
                 q.add(new Point(nx, ny, curr.move 1));
                 
             }
         }

         // You now have your reachable points.
    }
}

class Point {
    public int x, y, move;
    public Point(int x, int y, int move) {
        this.x = x;
        this.y = y;
        this.move = move;
    }
}
Метки: