格子游戏的自动寻路 —— 从"点哪走哪"到处理门、NPC、障碍
精华04/3039 浏览开发日记
在做魔塔的时候，我需要实现一个功能：玩家点击地图上的任意格子，角色就自动走过去。听起来简单，做起来发现要处理的细节比想象中多得多。这篇日记记录我是怎么一步步把寻路系统做出来的。（塔拉拉说自动寻路没有技术性可写东西，所以发到开发日记了。）
一、需求分析：我需要什么样的寻路？
我的游戏是经典的格子地图魔塔，地图大小约 13×13 到 50×50 不等。玩家在格子上移动，遇到墙壁、门、怪物等障碍不能通过。操作方式有两种：
- 键盘/虚拟方向键：一格一格走，按住连续移动
- 触摸/鼠标点击：点一个格子，角色自动规划路径走过去
二、算法选择：为什么用 BFS 而不是 A*？
寻路算法常见的有三种：算法特点适用场景BFS（广度优先搜索）保证最短路径，逻辑最简单格子地图、移动代价统一A（A-star）*用启发函数加速，大地图更快大型地图、移动代价不同Dijkstra支持不同权重的最短路径有地形代价（沼泽慢、道路快等）我选了 BFS，原因很直接：
- 地图小（最大 50×50 = 2500 格），BFS 最坏情况遍历全部格子也就 2500 次，完全不需要优化
- 移动代价统一，每走一格的代价都是 1，不存在"走草地慢、走道路快"的区别
- 代码最简单，一个队列 + 一个 visited 表就搞定，不需要维护优先队列
三、地图数据结构在写寻路之前，先要搞清楚地图是怎么存的。
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 根本找不到路。而且游戏的交互逻辑是：
- 点击门 → 角色走到门旁边 → 面朝门 → 触发开门检测
- 点击 NPC → 角色走到 NPC 旁边 → 面朝 NPC → 触发对话
复制-- 玩家点击了一个门
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 几十行就能写完。真正花时间的是处理各种交互场景——点击门怎么办、点击不可达的地方怎么办、走到一半切换输入怎么办。这些边界情况才是寻路系统里最多的工作量。
以上内容基于魔塔：逃离乐园的实际开发记录。