基于PHP多数组的游戏地图路径寻路算法实现问询

看起来你需要在一个无权重的地点图中找到两点之间的路径，最适合这种场景的是**广度优先搜索（BFS）**算法——它不仅容易实现，还能保证找到起点到终点的最短路径（因为每个地点间的移动代价相同）。

先给你理清楚思路，再结合你的$location数组给出具体实现：

核心思路：BFS寻路 #

BFS的工作方式就像从起点“扩散”出去，逐层访问所有相邻的地点，同时记录每个地点是从哪个节点过来的（前置节点）。当我们找到终点时，就可以通过回溯前置节点，从终点倒推回起点，再反转得到正序的路径。

PHP实现代码 #

// 你的地点关联数组
$location = [
    1 => [1,2,3,4,5,6,7],
    2 => [1,3,7],
    3 => [1,2,4,11],
    4 => [1,3,5],
    5 => [1,4,6,16],
    6 => [1,5,17],
    7 => [1,2,23],
    8 => [9,10,11],
    9 => [8,10,11],
    10 => [8,9,11],
    11 => [8,9,10,3],
    12 => [13,14,16],
    13 => [12,14],
    14 => [12,13,16],
    15 => [16],
    16 => [12,14,5],
    17 => [18,20,6],
    18 => [17,19],
    19 => [18],
    20 => [17],
    21 => [22,23],
    22 => [21,23],
    23 => [21,22,7],
];

function findShortestPath($location, $start, $end) {
    // 处理起点就是终点的情况
    if ($start === $end) {
        return [$start];
    }

    // 队列：用于存储待访问的节点
    $queue = new SplQueue();
    $queue->enqueue($start);

    // 已访问节点：避免重复遍历
    $visited = [$start => true];

    // 前置节点记录：key是当前节点，value是到达它的上一个节点
    $prev = [];

    while (!$queue->isEmpty()) {
        $current = $queue->dequeue();

        // 遍历当前节点的所有关联地点
        foreach ($location[$current] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $prev[$neighbor] = $current;
                $queue->enqueue($neighbor);

                // 找到终点，提前退出循环
                if ($neighbor === $end) {
                    $queue = new SplQueue(); // 清空队列结束循环
                    break;
                }
            }
        }
    }

    // 如果终点没有被访问到，说明没有路径
    if (!isset($prev[$end])) {
        return null;
    }

    // 回溯路径：从终点倒推回起点
    $path = [];
    $current = $end;
    while (isset($prev[$current])) {
        array_unshift($path, $current);
        $current = $prev[$current];
    }
    array_unshift($path, $start);

    return $path;
}

// 测试：从地点1到地点8
$path = findShortestPath($location, 1, 8);
if ($path) {
    echo "找到路径：" . implode(' -> ', $path);
    // 输出：找到路径：1 -> 3 -> 11 -> 8
} else {
    echo "没有可用路径";
}

其他可选方案 #

• 深度优先搜索（DFS）：如果你需要探索所有可能的路径（而不是最短路径），可以用DFS，但它不能保证找到最短路径，适合需要遍历所有路线的场景。
• Dijkstra算法：如果以后你的游戏给不同路径添加了权重（比如某些路线消耗更多体力/时间），Dijkstra算法可以找到权重最小的路径，是BFS的加权版本。

注意事项 #

• 你的$location数组中，部分节点包含自身（比如$location[1]里有1），在遍历的时候其实可以跳过自身，避免无效的循环访问，上面的代码已经通过visited数组自动处理了这种情况，但你也可以在遍历前先过滤掉自身节点优化性能。
• 如果你的地图很大，可以考虑优化队列和访问数组的存储方式，不过对于当前的规模来说，上面的实现完全够用。

内容的提问来源于stack exchange，提问作者Eddas