BFS 宽度优先搜索
概念¶
BFS（Breadth First Search），宽度优先算法（又名广度优先算法），宽度优先就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层
下面是一个例子，*代表起始点，不同位置的数字代表第几层（同时等于最短路径长度），在此示例中，只能水平和竖直方向上搜索
使用BFS算法，可以快速地找到路径最短路程
实现¶
一般的BFS算法使用队列Queue处理，C++中可以使用STL中的queue，Python可以使用Queue库，Javascript没有专门的队列，但可以使用数组实现
本文档中仅提供二维BFS的代码
警告
请不要将n、m的值设置的太大，在C++中，若n、m的值大于10000，会导致数组下标越界导致程序出错
并且过大的值也会造成大量的内存占用，若n、m的值都为10000，即使使用C++，光是储存vis都会占用约\(381.4697MiB\)（\(400MB\)）内存；Python和Javascript只会占用比其更大的内存
若是设置为32768（实际上会数组下标越界），理论上会占用\(4GiB\)（约\(4.2950GB\)）内存
二维BFS¶
#include <stdio.h>
#include <queue>
using namespace std;
struct Vector2
{
int x = 0, y = 0;
Vector2 operator+(Vector2 v)
{
return {x + v.x, y + v.y};
}
};
// vis: 储存所有搜索过的格子 n、m: 地图尺寸
int vis[10000][10000], n, m;
const Vector2 SIDES[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 搜索点坐标
Vector2 now, u, v;
void BFS()
{
queue<Vector2> que;
que.push(now);
vis[now.x][now.y] = 1;
while (!que.empty())
{
u = que.front();
que.pop();
for (int i = 0; i < 4; i++)
{
Vector2 v = u + SIDES[i];
if (v.x < 0 || v.x >= n || v.y < 0 || v.y >= m)
continue;
if (vis[v.x][v.y] != 0)
continue;
// 在这里添加if(...) continue; 实现避开障碍物的效果
vis[v.x][v.y] = vis[u.x][u.y] + 1;
que.push(v);
}
}
}
int main()
{
scanf("%d%d%d%d", &n, &m, &now.x, &now.y);
BFS();
for (int x = 0; x < n; x++)
{
for (int y = 0; y < m; y++)
{
printf("%d ", vis[x][y] - 1);
}
putchar('\n');
}
return 0;
}
from queue import Queue
class Vector2:
x = 0
y = 0
def __init__(self, x, y):
self.x = x
self.y = y
def add(self, v):
return Vector2(self.x + v.x, self.y + v.y)
SIDES = (Vector2(-1, 0), Vector2(1, 0), Vector2(0, -1), Vector2(0, 1))
vis = []
n = 10
m = 10
def BFS(s: Vector2):
que = Queue()
vis[s.x][s.y] = 0
que.put(s)
while not que.empty():
u: Vector2 = que.get()
for d in SIDES:
v = u.add(d)
if v.x < 0 or v.x >= n or v.y < 0 or v.y >= m:
continue
if vis[v.x][v.y] != -1:
continue
# 在这里添加
# if ...:
# continue
# 实现避开障碍物的效果
vis[v.x][v.y] = vis[u.x][u.y] + 1
que.put(v)
n = int(input())
m = int(input())
for i in range(0, n):
l = []
for j in range(0, m):
l.append(-1)
vis.append(l)
sx = int(input())
sy = int(input())
BFS(Vector2(sx, sy))
for i in range(0, n):
for j in range(0, m):
print(vis[i][j], end=' ')
print('')
class Vector2 {
constructor(x, y) {
this.x = x;
this.y = y;
}
/**
* @param {Vector2} v
* @returns {Vector2}
*/
add(v) {
return new Vector2(this.x + v.x, this.y + v.y);
}
clone() {
return new Vector2(this.x, this.y);
}
}
const SIDES = [new Vector2(-1, 0), new Vector2(1, 0), new Vector2(0, -1), new Vector2(0, 1)];
let n = 10, m = 10;
let vis = [];
for(let i = 0; i < n; i++)
vis.push(new Array(m).fill(-1));
/**
* BFS算法示例
* @param {Vector2} s 起始点坐标
*/
function BFS(s) {
let que = [];
que.push(s.clone());
vis[s.x][s.y] = 0;
while (que.length > 0) {
let u = que[0];
que.splice(0, 1);
for (const d of SIDES) {
let v = u.add(d);
if(v.x < 0 || v.x >= n || v.y < 0 || v.y >= m)
continue;
if(vis[v.x][v.y] !== -1)
continue;
// 在这里添加if(...) continue; 实现避开障碍物的效果
vis[v.x][v.y] = vis[u.x][u.y] + 1;
que.push(v);
}
}
}
BFS(new Vector2(5, 5));
for(let line in vis)
console.log(vis[line].join(' '));
你也许注意到了，这里初始化vis是使用了for+fill组合的方式，为什么不直接let vis = Array(n).fill(Array(m).fill(-1))呢？
因为fill方法的大致实现是这样的：
// this为该数组本身
fill: (value, start = 0, end = this.length) => {
for(let i = start; i < end; i++) {
this[i] = value;
}
}
在所有数据类型中，只有、、、、、为 值类型 ，值类型在赋值的时候会直接把 数据本身 赋值给变量/属性
举个例子：
而引用类型包含（包含、、、等）类型，引用类型在赋值的时候会将该类型的引用赋值给变量/属性
简单来说，要是有一个类型的变量a，将a的值赋值给b，则b就是a的引用，b变成了a的别名，除非将b赋予了其他值 用代码表示即：
let a = [1];
let b = a;
a[0] = 2;
console.log(b[0]); // 2
b = [-1];
a[0] = 3;
console.log(b[0]); // -1
vis的值属于引用类型，若使用fill方法，那么vis的所有成员都是填入的那个数组的引用，修改其中任意一个成员的成员的值，其他成员的成员的值也会发生变化
图上BFS¶
在图上使用BFS
警告
此处的“图”指的不是“地图”
class BFSNode {
/**
* 节点对应的值
*/
value: any;
/**
* 和该节点相连的其他节点
*/
edges: BFSNode[] = [];
/**
* 该节点是否被访问过
* 若为`-1`，代表节点没被访问；否则为节点被访问时的路程
*/
visited: number = -1;
constructor(value: any, edges: BFSNode[] = []){
this.value = value;
this.edges = edges;
}
}
function BFS(s: BFSNode) {
let queue: BFSNode[] = [];
queue.push(s);
s.visited = 0;
while(queue.length > 0){
let u: BFSNode = queue[0];
queue.splice(1, 0);
for(let v of u.edges){
if(v.visited)
continue;
v.visited = u.visited + 1;
queue.push(v);
}
}
}
具体使用¶
下面为在Box3环境中，实体使用BFS算法实现自动寻路的代码
不考虑其他实体体积和碰撞，位置皆按照整格来计算
测试视频
const SIDES = [
new Vector3(-1, 0, 0),
new Vector3(1, 0, 0),
new Vector3(0, 0, -1),
new Vector3(0, 0, 1),
new Vector3(-1, -1, 0),
new Vector3(1, -1, 0),
new Vector3(0, -1, -1),
new Vector3(0, -1, 1),
new Vector3(-1, 1, 0),
new Vector3(1, 1, 0),
new Vector3(0, 1, -1),
new Vector3(0, 1, 1),
];
const entityPositionFix = new Vector3(0.5, 0.5, 0.5); // 修复实体位置
const startPosition = new Vector3(128, 9, 128);
const endPosition = new Vector3(243, 19, 11);
const e = world.createEntity({
mesh: 'mesh/test.vb', // 假设文件里有一个叫test.vb的实体
position: startPosition.add(entityPositionFix),
meshScale: new Vector3(0.0625, 0.0625, 0.0625),
collides: false,
fixed: true,
gravity: false
});
function BFS(s, e) {
/**@type {number[][][]}*/
let vis = [],
/**@type {Vector3[]}*/
que = [], found = false, cnt = 1;
// 手动修正Box3的bug
// 测试地图为256地图 不同地图需要手动修改数值
voxels.shape.set(255, 63, 255);
console.log('地图尺寸', voxels.shape.x, voxels.shape.y, voxels.shape.z);
for (let i = 0; i < voxels.shape.x; i++) {
vis.push([]);
for (let j = 0; j < voxels.shape.y; j++)
vis[vis.length - 1].push(new Array(voxels.shape.z));
}
que.push(s.clone());
vis[s.x][s.y][s.z] = 0;
while (que.length > 0 && !found) {
let u = que[0];
que.splice(0, 1);
for (const d of SIDES) {
let v = u.add(d);
if (v.x < 0 || v.x >= voxels.shape.x || v.y < 0 || v.y >= voxels.shape.y || v.z < 0 || v.z >= voxels.shape.z)
continue;
if (vis[v.x][v.y][v.z] !== undefined)
continue;
if (voxels.getVoxel(v.x, v.y, v.z) !== 0 || voxels.getVoxel(v.x, v.y - 1, v.z) === 0) // 禁止穿墙和空中寻路
continue;
vis[v.x][v.y][v.z] = vis[u.x][u.y][u.z] + 1;
que.push(v);
if (v.equals(e)) {
found = true;
console.log('找到终点', v.x, v.y, v.z, vis[v.x][v.y][v.z]);
break;
}
cnt++;
}
}
console.log('搜索完成，共搜索', cnt, '个位置');
return vis;
}
function findPath(map, s, e) {
if (map[endPosition.x][endPosition.y][endPosition.z] === undefined)
throw "无效数据";
let result = [], now = new Vector3(Math.round(e.x), Math.round(e.y), Math.round(e.z));
result.push(now.clone());
do {
let v;
for (const d of SIDES) {
v = now.add(d);
if (v.x < 0 || v.x >= map.length || v.y < 0 || v.y >= map[now.x].length || v.z < 0 || v.z >= map[now.x][now.y].length)
continue;
if (map[now.x][now.y][now.z] - 1 === map[v.x][v.y][v.z]) {
result.push(v);
now.copy(v);
break;
}
}
if (v === undefined)
throw "找不到路径";
} while (!result[result.length - 1].equals(s));
return result.reverse();
}
world.onPlayerJoin(async ({ entity }) => {
entity.player.spectator = true;
entity.player.invisible = true;
entity.player.cameraEntity = e;
console.log('开始搜索');
let startTime = Date.now()
const MAP = BFS(startPosition, endPosition);
console.log('寻路完成 长度', MAP[endPosition.x][endPosition.y][endPosition.z], '用时', Date.now() - startTime, 'ms');
console.log('开始寻路');
const PATH = findPath(MAP, startPosition, endPosition);
console.log('路径长度', PATH.length);
for (let p of PATH) {
await sleep(100);//entity.player.nextPress();
e.position.copy(p.add(entityPositionFix));
console.log(p.toString());
}
console.log('完成');
});