1.介绍
广度寻路算法是上,左,下,右一起试探,把试探过能走的点用以四叉树的方式保存起来,直到试探到终点。
广度相比于深度,可以找到从起点到终点的最佳路径
废话不多说,看图
2.图

图中1表示起点,2表示终点

3.步骤&&方法:
1.如上图,这里引入一个层的概念,例如起点(1,9)就是第一层,随之试探出第二层…
2.这里可以使用C++的vector,把第一层的节点存入vector中,在进行循环,在之后吧第一层的每一个节点试探出的节点存放到vect中,直到试探出终点循环结束。
4.代码
#include"stdfax.h"
#define ROW 10
#define COL 10
enum direct { p_Up, p_Left, p_Down, p_Right };
class testMap
{
public:
bool IsGo;
};
struct MyPoint
{
int x;
int y;
};
class treeNode
{
public:
MyPoint pos;
treeNode * Parent;
vector<treeNode *> pChild;
treeNode(int x,int y)
{
pos.x = x;
pos.y = y;
Parent = NULL;
}
treeNode(MyPoint pos1)
{
pos = pos1;
Parent = NULL;
}
};
bool CanWalk(int map[ROW][COL], testMap testmap[ROW][COL],MyPoint pos)
{
if (map[pos.x][pos.y] ) return false;
if (testmap[pos.x][pos.y].IsGo == true) return false;
if (pos.x >= ROW || pos.x < 0 || pos.y >= COL || pos.y < 0) return false;
return true;
}
int main()
{
int map[ROW][COL] = {
1,1,1,1,1,1,1,1,1,1,
1,0,1,0,0,0,0,1,1,1,
1,0,0,0,1,1,1,1,1,1,
1,0,0,0,0,0,0,0,1,1,
1,0,1,1,1,1,1,0,1,1,
1,0,0,0,0,1,1,0,1,1,
1,0,1,0,1,1,1,0,1,1,
1,0,0,0,1,1,0,0,1,1,
1,0,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1
};
testMap testmap[ROW][COL] = { 0 };
MyPoint BegPoint = { 1,1 };
MyPoint EndPoint = { 8,2 };
testmap[BegPoint.x][BegPoint.y].IsGo = true;
vector<treeNode *> Current;
vector<treeNode *> Next;
treeNode * pRoot = new treeNode(BegPoint);
Current.push_back(pRoot);
MyPoint tempPos;
MyPoint currentPos;
treeNode * pChild = NULL;
bool IsEnd = false;
while (1)
{
Next.clear();
for (int i = 0; i < Current.size(); i++)
{
currentPos = Current[i]->pos;
for (int j = 0; j < 4;j++)
{
switch (j)
{
case p_Up://向上
tempPos.x = currentPos.x;
tempPos.y = currentPos.y - 1;
break;
case p_Left://左
tempPos.x = currentPos.x-1;
tempPos.y = currentPos.y;
break;
case p_Down://向下
tempPos.x = currentPos.x;
tempPos.y = currentPos.y + 1;
break;
case p_Right://向右
tempPos.x = currentPos.x + 1;
tempPos.y = currentPos.y;
break;
default:
break;
}
if (CanWalk(map,testmap, tempPos))
{
pChild = new treeNode(tempPos);
Current[i]->pChild.push_back(pChild);
Next.push_back(pChild);
pChild->Parent = Current[i];
testmap[tempPos.x][tempPos.y].IsGo = true;
if (tempPos.x == EndPoint.x && tempPos.y == EndPoint.y)
{
IsEnd = true;
break;
}
}
if (IsEnd)
break;
}
if (IsEnd)
break;
}
if (IsEnd)
{
printf("找到终点啦");
while (NULL != pChild)
{
printf("路径是:");
printf("(%d,%d)\n ", pChild->pos.x, pChild->pos.y);
pChild = pChild->Parent;
}
break;
}
Current = Next;
}
printf("程序结束\n");
return 0;
}
5.总结
1.广度与深度的比较
1.1.没有回退
1.2.深度不一定能找到最佳路径,广度能
1.3.时间复杂度高
2.个人感觉广度寻路算法要比深度寻路算法要有趣的多。像RPG游戏里的自动寻路用的就是类似于广度的算法吧。比如A星寻路就是在广度的基础上更加智能优化了一点。
明天继续更新A星寻路算法,前几天因为开学原因没时间啦。