解决这个迷宫游戏的算法

Question

在学习 flutter 的同时，我制作了一个游戏 Rabbit and maze，您可以从 this link 访问它。 .

游戏说明:游戏中有5种牌型:加号(+)型有四路(或开口)，T型有三路，L型有两路，工字有两种方式，砖型没有任何方式。在我的游戏中，用户必须通过轻敲和旋转砖 block 让路从兔子到家。我附上了一张 3x3 的游戏截图(有 4x4、5x5 等关卡)。

.

每次游戏都是随机生成的，因此在此屏幕截图中您可以看到 T 形和 I 形瓷砖。每次点击瓷砖旋转 90 度。要完成这个游戏，必须开辟从兔子到家的白色路径(可以通过点击右上角的瓷砖 2 次来完成)。现在，游戏确实会告诉用户他们是否已成功完成路径。

问题:游戏是随机生成的。所以我们不知道是否每个游戏都可以解决。我只想展示可解决的游戏。如果用户最终未能以最少的步骤解决问题，我还必须向用户展示解决方案。

游戏单元模态:

 class GameCellModal {
  AngleDegree angle; //can have 0,90,180,270
  IconCode icon;
  int row; 
  int column;
  int rowLength; // max length for eg 3 for 3x3
  int columnLength; // max length for eg 3 for 3x3
}

Answer 1

您可以使用 Dijkstra 算法的变体。将网格转换为图形，其中一个节点是一个网格单元格，一个节点最多有四个邻居(与单元格的内容无关)。 可以到达的实际邻居取决于路径来自何处以及单元格的内容。生成所有可能性以找到可以遍历的下一条边，如果需要旋转到某个方向，则增加路径的成本。不允许路径重新访问它已有的节点。

您需要将路径存储在优先级队列中(基于总轮换成本)，但正如我们所知，总成本是有限的(< 3 x #cells)，您可以为此使用一个数组，其中索引是成本，值是具有该成本的路径列表。

然后您可以从索引 0 开始迭代该数组，并按该顺序处理路径。这将确保您找到最短路径。

时间复杂度不如标准 Dijkstra 算法，因为您无法禁止通过不同路径访问同一单元格。但是，您仍然必须检查相同 路径是否访问相同的单元格。

对于网格和图形的表示，有很多可能性。在这里，我选择使用方框绘图字符来表示网格内容，因为在调试期间您可以轻松地看到单元格内容代表什么。

我认为上面的描述应该足以理解这个想法，但如果您需要查看实现，我会在此处添加一个 JavaScript 实现。它是交互式的，因此您可以生成随机的 8x8 网格，并通过网格查看算法的运行情况。

// Characters that will be used as cell content:
let box = " SE╝ ═╚╩ ╗║╣╔╦╠╬";
// blank = brick, S = start, E = end.
// The position of the character is a 4 bit number. Each bit represents a direction
// (east, north, west, south), and is set to 1 when that direction is enabled.
// Exceptions are S and E which have all four directions enabled.

// Determine which rotations make sense for each character.
let rotations = { 
    " ": [] // A brick has no rotations
};
for (let i = 1; i < 16; i++) {
    let chr = box[i];
    if (chr == " ") continue;
    let rot = [];
    let j = i;
    if ("╬SE".includes(chr)) { // rotating does not change anything
        rot.push(0xF);
    } else { // can turn 90° to different shape
        rot.push(j, j = bitRotate(j));
        if (!"═║".includes(chr)) { // shape has more than two states
            rot.push(j = bitRotate(j), bitRotate(j)); 
        }
    }
    rotations[chr] = rot;
}

class Node {
    constructor(name, row, col, chr) {
        this.name = name;
        this.row = row;
        this.col = col;
        this.chr = chr;
        // One potential entry for each direction: East, North, West, South
        this.neighbors = [null, null, null, null];
    }
    addNeighbor(direction, neighbor) {
        if (!neighbor) return;
        this.neighbors[direction] = neighbor;
        neighbor.neighbors[direction ^ 2] = this; // reverse direction
    }
}

function createGraph(grid) {
    let height = grid.length;
    let width = grid[0].length;
    let startNode = null;
    let nodes = [];
    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if (grid[i][j] == " ") {
                nodes[j] = null;
            } else {
                let node = new Node(JSON.stringify([i, j]), i, j, grid[i][j]);
                // if there is a node left, log it as neighbor
                if (j > 0) node.addNeighbor(0, nodes[j-1]);
                // if there is a node above, log it as neighbor
                if (i > 0) node.addNeighbor(1, nodes[j]);
                if (node.chr == "S") startNode = node;
                nodes[j] = node;
            }
        }
    }
    return startNode;
}

function extendPath(path) {
    let node = path[path.length-1];
    // Get direction (bit) at which we entered last node in path
    let entry = 1;
    if (path.length > 1) entry = 1 << node.neighbors.indexOf(path[path.length-2]);
    let rot = rotations[node.chr];
    let exits = 0;
    let remainingExits = 0xF;
    let paths = [];
    for (let i = 0; i < rot.length && remainingExits > 0; i++) {
        if ((rot[i] & entry) == 0) continue; // Cannot enter at this rotation
        let exits = (rot[i] ^ entry) & remainingExits;
        remainingExits ^= exits;
        let j = 0;
        while (exits) {
            let neighbor = node.neighbors[j];
            // Can exit in direction j? Only when:
            // - rotation allows it
            // - there is an edge (not off-grid; not visited before)
            // - not going to a node that is already on this path
            if ((exits & 1) && neighbor && !path.includes(neighbor)) {
                paths.push([i, path.concat(neighbor)]);
            }
            exits >>= 1;
            j++;
        }
    }
    return paths;
}

// Use delays so the algorithm's progress can be visualised
const delay = () => new Promise(resolve => setTimeout(resolve, 10));

async function shortestPath(grid, listener) {
    // Convert to an easier to use data structure:
    let startNode = createGraph(grid);
    // As a BFS priority queue, use an array indexed by total made rotations,
    // and for each index, store a list of paths that use that many rotations.
    // The maximum number of rotations per node is 3, so the total made rotations
    // cannot be more than 3 times the number of cells in the grid.
    let paths = []; // This is a dynamicly growing array
    paths[0] = [[startNode]]; // Initial path has 0 rotations and has just the start node.
    for (let cost = 0; cost < paths.length; cost++) {
        let cheapPaths = paths[cost] || [];
        for (let j = 0; j < cheapPaths.length; j++) {
            let path = cheapPaths[j];
            if (path.length > 1) {
                // Check that the edge was not yet visited
                let [prev, curr] = path.slice(path.length-2); // get last two nodes
                let dir = prev.neighbors.indexOf(curr);
                if (dir < 0) continue; // edge was already visited
                // Visit the directed edge by removing it from the graph
                prev.neighbors[dir] = null;
            }
            if (listener) {
                listener(path.map(node => [node.row, node.col]));
                await delay();
            }
            // Did we reach the target?
            if (path[path.length-1].chr == "E") return cost;
            for (let [rotation, nextPath] of extendPath(path)) {
                let newCost = cost + rotation;
                if (!paths[newCost]) paths[newCost] = []; // extend array
                paths[newCost].push(nextPath);
            }
        }
    }
    return Infinity; // no solution found
}

function generateGrid(width, height) {
    let grid = Array.from({length: height}, () => 
        Array.from({length: width}, () => " ╝═╚╩╗║╣╔╦╠╬"[Math.floor(Math.random() * 12)])
    );
    // For this demo, we always put the start/end nodes in the opposite corners
    grid[0][0] = "S"; // starting node
    grid[7][7] = "E"; // ending node
    return grid;
}

function bitRotate(bits) { // Rotate 4 bits:
    return ((bits << 1) | +(bits >= 8)) & 0xF;
}

// All below is for I/O handling with DOM

(function () {
    let table = document.querySelector("#game");
    let msg = document.querySelector("#msg");
    let btnScramble = document.querySelector("#scramble");
    let btnSolve = document.querySelector("#solve");
    let grid;

    function newGame() {
        grid = generateGrid(8, 8);
        display();
    }

    function display(path=[]) {
        // Create HTML table contents from scratch
        table.innerHTML = grid.map(row =>
            `<tr>${row.map(chr => `<td>${htmlBox(chr)}<\/td>`).join("")}<\/tr>`
        ).join("");
        // If a path argument was given, then color that path
        let cost = 0;
        for (let i = 0; i < path.length; i++) {
            let p = path[i];
            let numRotations = 0;
            if (i > 0 && i < path.length-1) {
                numRotations = rotationCount(grid, path[i-1], p, path[i+1], path[path.length-1].join() === "7,7");
            }
            table.rows[p[0]].cells[p[1]].style.backgroundColor = 
                ["yellow", "orange", "red", "purple"][numRotations];
            cost += numRotations;
        }
        if (path.length) {
            msg.textContent = "Used " + cost + " rotations...";
        } else {
            msg.textContent = "";
        }
    }
    
    async function solve() {     
        btnScramble.disabled = true;
        btnSolve.disabled = true;
        // As the algorithm progresses, call display
        let cost = await shortestPath(grid, display);
        msg.textContent = cost === Infinity ? "No path found" : "Minimal number of rotations = " + cost;
        btnScramble.disabled = false;
        btnSolve.disabled = false;
    }

    newGame(); // immediately create a game on page load

    btnScramble.addEventListener("click", newGame);
    btnSolve.addEventListener("click", solve);

    table.addEventListener("click", function (e) {
        if (btnSolve.disabled) return; // do not allow changing the grid while solving
        let td = e.target.closest("#game>tbody>tr>td");
        if (!td) return;
        rotate(grid, td.cellIndex, td.parentNode.rowIndex);
        display();
    });
})();

function rotate(grid, x, y) {
    let chr = grid[y][x];
    if ("SE╬ ".includes(chr)) return false; // nothing to turn
    let bits = box.indexOf(chr);
    grid[y][x] = box[bitRotate(bits)];
    return true;
}

function rotationCount(grid, a, b, c) {
    let entry = a[1] < b[1] ? 1 
              : a[1] > b[1] ? 4
              : a[0] < b[0] ? 2 : 8;
    let exit  = c[1] < b[1] ? 1
              : c[1] > b[1] ? 4
              : c[0] < b[0] ? 2 : 8;
    let needed = entry + exit;
    let actual = box.indexOf(grid[b[0]][b[1]]);
    for (let count = 0; count < 4; count++) {
        if ((actual & needed) == needed) return count;
        actual = bitRotate(actual);
    }
    throw "rotation not found";
}

function htmlBox(chr) {
    if (chr == "S") return "🐇";
    if (chr == "E") return "🏠";
    let bits = box.indexOf(chr);
    return "<table>"
        + `<tr><td class="black"><\/td><td class="${color(bits, 2)}"><\/td><td class="black"><\/td><\/tr>`
        + `<tr><td class="${color(bits, 1)}"><\/td><td class="white"><\/td><td class="${color(bits, 4)}"><\/td><\/tr>` 
        + `<tr><td class="black"><\/td><td class="${color(bits, 8)}"><\/td><td class="black"><\/td><\/tr>`
    + "</table>";
}

function color(bits, bit) {
    return bits & bit ? "white" : "black";
}

table { border-collapse: collapse }
td { padding: 0; border: 1px solid grey; text-align: center }

#game { margin-right: 10px; float: left }
#game table td { border-width: 0px; }
#game table tr:first-child, #game table tr:last-child { height: 6px }
#game table tr:nth-child(2) { height: 12px }
#game table td:first-child, #game table td:last-child { width: 6px }
#game table td:nth-child(2) { width: 12px }

#game .black { background: black }

button { margin-right: 10px }

body { margin: 0 }

<table id="game"></table>
<button id="scramble">Scramble</button><button id="solve">Solve</button><br>
Yellow = no rotation, Orange=1, Red=2, Purple=3

<div id="msg"></div>