格子游戏的自动寻路 —— 从"点哪走哪"到处理门、NPC、障碍

在做魔塔的时候，我需要实现一个功能：玩家点击地图上的任意格子，角色就自动走过去。听起来简单，做起来发现要处理的细节比想象中多得多。这篇日记记录我是怎么一步步把寻路系统做出来的。（塔拉拉说自动寻路没有技术性可写东西，所以发到开发日记了。）

我的游戏是经典的格子地图魔塔，地图大小约 13×13 到 50×50 不等。玩家在格子上移动，遇到墙壁、门、怪物等障碍不能通过。操作方式有两种：

寻路算法常见的有三种：算法特点适用场景BFS（广度优先搜索）保证最短路径，逻辑最简单格子地图、移动代价统一A（A-star）*用启发函数加速，大地图更快大型地图、移动代价不同Dijkstra支持不同权重的最短路径有地形代价（沼泽慢、道路快等）我选了 BFS，原因很直接：

三、地图数据结构在写寻路之前，先要搞清楚地图是怎么存的。

3.1 二维数组存储我的地图是一个二维数组，行优先存储：lua

复制-- 地图数据示例（简化版）

local mapData = {

    { 8, 8, 8, 8, 8 },    -- 第1行：全是墙

    { 8, 2, 2, 2, 8 },    -- 第2行：墙-路-路-路-墙

    { 8, 2, 8, 2, 8 },    -- 第3行：中间有堵墙

    { 8, 2, 2, 2, 8 },    -- 第4行

    { 8, 8, 8, 8, 8 },    -- 第5行：全是墙

}

-- 访问方式：mapData[y][x]

-- 注意：Lua 数组从 1 开始！

3.2 瓦片类型与通行性每个数字代表一种瓦片类型，我用一张查找表来判断"这个格子能不能走"：lua

复制-- 瓦片类型

local TILE = {

    GRASS = 1,     -- 草地（可通行）

    PATH  = 2,     -- 小路（可通行）

    WALL  = 8,     -- 墙壁（不可通行）

    DOOR  = 11,    -- 黄门（不可通行，但可以开门后变成可通行）

    HOUSE = 6,     -- 蘑菇屋（不可通行）

    -- ... 更多类型

}

-- 不可通行的瓦片集合

local SOLID_TILES = {

    [TILE.WALL]  = true,

    [TILE.DOOR]  = true,

    [TILE.HOUSE] = true,

    -- ...

}

-- 判断通行性：不在 SOLID_TILES 里就能走

function IsTilePassable(tx, ty)

    if tx < 1 or tx > mapWidth or ty < 1 or ty > mapHeight then

        return false  -- 越界不可通行

    end

    local tile = mapData[ty][tx]

    return not SOLID_TILES[tile]

end

这个设计的好处：新增瓦片类型时，只要往 SOLID_TILES 里加一行就行，寻路代码完全不用改。3.3 坐标系统格子游戏有两套坐标要来回转换，一开始搞混了好几次：坐标类型范围说明瓦片索引整数，从 1 开始第几行第几列，用于查地图数据玩家坐标浮点数，0.5 为格子中心用于渲染和平滑移动lua

复制-- 玩家坐标 → 瓦片索引

function PosToTileX(x)

    return math.floor(x) + 1   -- 0.5 → 第1格，1.5 → 第2格

end

-- 瓦片索引 → 格子中心坐标

function TileCenterX(tileIdx)

    return tileIdx - 0.5        -- 第1格 → 0.5，第2格 → 1.5

end

踩坑记录：最早我忘了 Lua 数组从 1 开始，PosToTileX 写成了 math.floor(x) 没有加 1，导致玩家站在第一列时索引为 0，查表返回 nil，然后程序就崩了。

四、BFS 核心实现4.1 算法思路BFS 的思路很直白：

复制function bfsPath(sx, sy, gx, gy)

    local mapW = GetMapWidth()

    local mapH = GetMapHeight()

    -- 用一维 key 做访问标记，避免二维表的开销

    local function key(x, y) return (y - 1) * mapW + x end

    local visited = {}

    local parent = {}     -- parent[key] = {x, y, parentKey}

    local startK = key(sx, sy)

    visited[startK] = true

    local queue = { { sx, sy } }

    local head = 1        -- 队列头指针（用数组模拟队列）

    local goalK = key(gx, gy)

    local dirs = { {0,-1}, {0,1}, {-1,0}, {1,0} }  -- 上下左右

    while head <= #queue do

        local cur = queue[head]

        head = head + 1

        local cx, cy = cur[1], cur[2]

        local ck = key(cx, cy)

        if ck == goalK then

            -- 找到了！回溯路径

            local path = {}

            local k = goalK

            while k ~= startK do

                local info = parent[k]

                path[#path + 1] = { tx = info[1], ty = info[2] }

                k = info[3]

            end

            -- 反转：回溯是终点→起点，需要反过来

            local n = #path

            for i = 1, math.floor(n / 2) do

                path[i], path[n - i + 1] = path[n - i + 1], path[i]

            end

            return path

        end

        for _, d in ipairs(dirs) do

            local nx, ny = cx + d[1], cy + d[2]

            if nx >= 1 and nx <= mapW and ny >= 1 and ny <= mapH then

                local nk = key(nx, ny)

                if not visited[nk] and IsTilePassable(nx, ny) then

                    visited[nk] = true

                    parent[nk] = { nx, ny, ck }

                    queue[#queue + 1] = { nx, ny }

                end

            end

        end

    end

    return nil  -- 无路可达

end

4.3 几个实现细节为什么用一维 key？local function key(x, y) return (y - 1) * mapW + x end

Lua 的 table 用二维索引（visited[x][y]）需要先创建内层 table，而一维 key 只需要一个 table，查找更快。对于 50×50 的地图，key 范围是 1~2500，完全够用。为什么用数组模拟队列？BFS 需要先进先出的队列。Lua 没有内置队列，用 table.remove(queue, 1) 每次删除头部元素的话，所有后面的元素都要前移，复杂度是 O(n)。我的做法是维护一个 head 指针，取元素只是 head = head + 1，O(1) 搞定。虽然"已取出"的元素还留在数组里浪费内存，但对 2500 格的地图来说完全无所谓。路径不含起点：返回的路径是"从起点出发要经过的格子列表"，起点本身不包含在内。这样调用方直接遍历路径就是要走的每一步。

五、难点：点击门和 NPC 的特殊处理5.1 问题普通格子的寻路很简单：点哪走哪。但门和 NPC 是不可通行的，BFS 根本找不到路。而且游戏的交互逻辑是：

复制-- 玩家点击了一个门

if IsTileDoor(tileX, tileY) then

    -- 先检查是不是已经站在门旁边了

    local dist = math.abs(tileX - curTX) + math.abs(tileY - curTY)

    if dist == 1 then

        -- 已经在旁边 → 直接面朝门，触发开门

        player.direction = calcFaceDir(curTX, curTY, tileX, tileY)

        doorDetected = true

        return

    end

    -- 找门旁边最近的可通行格

    local adjDirs = { {0,-1}, {0,1}, {-1,0}, {1,0} }

    local bestAdj, bestDist = nil, math.huge

    for _, d in ipairs(adjDirs) do

        local ax, ay = tileX + d[1], tileY + d[2]

        if IsTilePassable(ax, ay) then

            local d2 = math.abs(ax - curTX) + math.abs(ay - curTY)

            if d2 < bestDist then

                bestDist = d2

                bestAdj = { x = ax, y = ay }

            end

        end

    end

    if not bestAdj then return end  -- 门四周都走不了

    -- BFS 寻路到这个邻居格

    local path = bfsPath(curTX, curTY, bestAdj.x, bestAdj.y)

    if not path then return end

    -- 记住：到达后要面朝门

    movePath = path

    pendingFaceDir = calcFaceDir(bestAdj.x, bestAdj.y, tileX, tileY)

end

5.3 "到达后面朝目标"的实现走完路径的最后一步时，检查有没有 pendingFaceDir：lua

复制-- 路径走完

if pathIndex > #movePath then

    movePath = nil

    -- 有待转向 → 面朝门/NPC，触发检测

    if pendingFaceDir then

        player.direction = pendingFaceDir

        pendingFaceDir = nil

        doorDetected = true   -- 通知主循环：前方有可交互对象

    end

end

这样主循环在下一帧就会检测到 doorDetected，然后执行开门逻辑（检查钥匙够不够、播放开门动画等）。

六、路径执行：从路径数组到平滑移动BFS 算出来的是一串格子坐标，但玩家不能瞬移到终点，得一格一格走过去。6.1 逐格追踪lua

复制local movePath = nil         -- 完整路径 {{tx,ty}, ...}

local movePathIdx = 0        -- 当前走向第几步

local moveWaypoint = nil     -- 当前目标点（格子中心坐标）

function UpdateMove(dt)

    if not movePath then return end

    -- 需要设下一个 waypoint

    if not moveWaypoint then

        if movePathIdx <= #movePath then

            local wp = movePath[movePathIdx]

            moveWaypoint = {

                x = TileCenterX(wp.tx),

                y = TileCenterY(wp.ty),

            }

            -- 更新朝向

            player.direction = calcDirection(player, moveWaypoint)

        else

            -- 路径走完

            movePath = nil

            return

        end

    end

    -- 向 waypoint 移动

    local dx = moveWaypoint.x - player.x

    local dy = moveWaypoint.y - player.y

    local dist = math.sqrt(dx * dx + dy * dy)

    if dist < 0.05 then

        -- 到达当前 waypoint，对齐到格子中心

        player.x = moveWaypoint.x

        player.y = moveWaypoint.y

        moveWaypoint = nil

        movePathIdx = movePathIdx + 1

    else

        -- 匀速移动

        local step = math.min(speed * dt, dist)

        player.x = player.x + (dx / dist) * step

        player.y = player.y + (dy / dist) * step

    end

end

6.2 为什么要"对齐到格子中心"？到达 waypoint 时我强制把坐标设成格子中心（player.x = moveWaypoint.x），而不是让浮点数自然累积。原因：浮点运算有精度误差，走 10 格后可能偏移了 0.001，看起来没什么，但做碰撞检测时 PosToTileX 可能算出错误的格子索引。每步对齐一次就不会有这个问题。

七、两套输入共存游戏同时支持键盘和触摸，两套输入必须互相配合：lua

复制-- 键盘按下 → 立即清除触摸寻路

if keyboardDir ~= NONE then

    movePath = nil

    moveWaypoint = nil

end

-- 触摸点击 → 重新计算路径（覆盖之前的路径）

if touchClicked then

    movePath = bfsPath(...)

    movePathIdx = 1

end

规则：键盘优先级高于触摸。玩家正在自动寻路，中途按了方向键，就切换成手动控制，寻路路径立刻丢弃。还有一个容易忽略的细节：切层后冻结输入。玩家上楼梯切换到新楼层时，如果方向键还按着，角色会立刻往之前的方向走一格。我的做法是切层后设一个 inputFrozen 标记，等玩家松开所有方向键再解冻。

八、总结：格子寻路的清单如果你也在做格子游戏的自动寻路，这是我踩完坑之后总结的清单：步骤要点1. 地图数据二维数组存储，用查找表判断通行性2. 坐标转换瓦片索引（整数，从 1 开始）和玩家坐标（浮点数）要分清3. 寻路算法小地图用 BFS 就够了（保证最短路径，代码简单）4. 不可通行目标门/NPC → 寻路到旁边最近的可通行格 + 记录到达后的朝向5. 路径执行逐格追踪，每步对齐到格子中心，避免浮点漂移6. 输入优先级键盘覆盖触摸，切层后冻结输入格子寻路本身不难，BFS 几十行就能写完。真正花时间的是处理各种交互场景——点击门怎么办、点击不可达的地方怎么办、走到一半切换输入怎么办。这些边界情况才是寻路系统里最多的工作量。