迷宫寻路系列常用算法逻辑探究

02月

504 0 0

　　关于该问题，大家肯定不假思索的提到: 宽度优先遍历(BFS)。

// 1).初始化工作
// 1.1). 把源节点坐标放入队列中
queue.push((x, y，step=0));
// 1.2). 标示该节点访问过
visited[(x, y)] = true
// 2).BFS procedure
while ( !queue.empty() ) {
// 2.1).取出当前节点
(x, y, step) <= queue.pop()
// 2.2).判断是否为目标节点, 并返回
if ( (x, y) == (dest.x, dest.y) ) {
return (step);
}
// 2.3).遍历(x, y)的邻近节点
foreach ((x, y) in neighbor(x, y)) {
// 2.3.1).可到达且没有访问过
if (is_available(x, y) and visited[(x, y)] == false) {
queue.push((x, y, step + 1));
// 标示访问过
visited[(x, y)] = true
}
}
}
// 3). 不存在路径
return unavailable

　　在有不确定的因素的干扰下，使用常规的最短路径算法就不再可行的。有没有其他的解法呢？

　　在迷宫地图较小时，我们可以借助动态规划的思想来解决。

设opt[n][y][x]为状态矩阵:
- n表示步数, (x, y)表示迷宫地图的位置信息, 而其值表示鼠精灵在该步数后能否到达该节点.
  - 初始状态:
    - opt[0][y][x] = true
      - 状态迁移方程:
        opt[n+1][y][x] = (opt[n][y][x]==true monster[n+1] != (x, y) )==false, {ε(x,y)，adjacency to (x,y)}) ? true : false;

复制代码
　　具体的伪码如下:

// 初始化
- opt[0][y][x] = true;
  - // 步数遍历
    - for ( step = 0; ; step++ ) {
      - // 迷宫矩阵遍历
        for ( i = 0; i < height; i++ ) {
        for ( j = 0; j < width; j++ ) {
        // 当前节点可达
        if ( opt[step][i][j] == true ) {
        // 枚举各个邻近的可达节点
        foreach (x, y) adjacency (j, i) {
        // 小怪兽在步数step + 1，没有走到该点
        if ( monster[step + 1] != (x, y) ) {
        opt[step + 1][y][x] = true;
        }
        }
        }
        }
        }
        // 检查目标节点是否到达
        if ( opt[step][dest_y][dest_x] == true ) {
        return step;
        }
        }
        
        return Oops;

复制代码
　　注: 若该迷宫没解，必然存在循环节，最外层循环借助滚动数组来优化。

　　总结:

　　从迷宫寻路的场景出发，逐步进行基础知识的深挖掘，还是具备一定的区分度的。

　　面试这东西，能遇到一个nice的面试官是种幸福。但很多时候，往往是一场闹剧了。

　　相关阅读：对弈类游戏的人工智能设计（1）：评估函数+博弈树算法

标签：魔兽开发经验爬坑游戏开发者开发技术游戏开发论坛

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！