bfs.cpp

《游戏编程指南》配套代码 [涉及平台] VC++ [作者] void [文件大小] 1761KB [更新日期] 2005-10-26

//标准广度优先搜索程序：

#include <iostream>
#include <memory>
using namespace std;

#define SX	10 //宽
#define SY	10 //长

int dx[4]={0,0,-1,1}; //四种移动方向对x和y坐标的影响
int dy[4]={-1,1,0,0};

char Block[SY][SX]= //障碍表
{{	0,1,0,0,0,0,0,0,0,0	},
{   0,1,1,0,1,1,1,0,0,0	},
{   0,0,0,0,0,0,0,0,0,0	},
{	1,1,1,0,1,0,0,0,1,0	},
{	0,1,0,0,1,0,1,1,1,0	},
{	0,1,0,0,1,1,1,1,1,0	},
{	0,0,0,1,1,0,0,0,1,0	},
{	0,1,0,0,0,0,1,0,1,0	},
{	0,1,1,1,0,1,1,0,1,1	},
{	0,0,0,0,0,0,1,0,0,0	}};
int	AllComplete=0; //全部完成标志
int	LevelNow=1, //搜索到第几层
	Act, //现在的移动方向
	ActBefore, //现在的节点的父节点
	MaxAct=4, //移动方向总数
	ActNow, //现在的节点
    tx,ty; //当前坐标
int	LevelFoot[200] = {0}, //每一层最后的节点
	ActHead[3000] = {0}; //每一个节点的父节点
char AllAct[3000] = {0}; //每一个节点的移动方向
char ActX[3000] = {0}, ActY[3000] = {0}; //按节点移动后的坐标
char Table[SY][SX] = {0}; //已到过标记
char TargetX=9,TargetY=9; //目标点

int ActOK( );
int Test( );

int ActOK( )
{
	tx=ActX[ActBefore]+dx[Act-1]; //将到点的x坐标
	ty=ActY[ActBefore]+dy[Act-1]; //将到点的y坐标
	if ((tx>=SX)||(tx<0)) //x坐标出界？
		return 0;
	if ((ty>=SY)||(ty<0)) //y坐标出界？
		return 0;
	if (Table[ty][tx]==1) //已到过？
		return 0;
	if (Block[ty][tx]==1) //有障碍？
		return 0;
	return 1;
}
int Test( )
{
	if ((tx==TargetX)&&(ty==TargetY)) //已到目标
	{
		int act=ActNow;
		while (act!=0)
		{
			cout<<(int)AllAct[act]; //一步步向前推出所有移动方向
			act=ActHead[act]; //所以输出倒了过来
		}
		return 1;
	}
	return 0;
}

void main()
{
	LevelNow=1;
	LevelFoot[1]=0;
	LevelFoot[0]=-1;
	ActX[0]=0;
	ActY[0]=0;
	while (!AllComplete)
	{
		LevelNow++; //开始搜索下一层
			LevelFoot[LevelNow]=LevelFoot[LevelNow-1];
//新一层的尾节点先设为与上一层相同
			for (ActBefore=LevelFoot[LevelNow-2]+1;
ActBefore<=LevelFoot[LevelNow-1];
ActBefore++) //对上一层所有节点扩展
		{
			for (Act=1;Act<=MaxAct;Act++) //尝试所有方向
			{
				if ((ActOK( )) && (!AllComplete)) //操作可行?
				{
					LevelFoot[LevelNow]++; //移动尾指针准备加入新节点
					ActNow=LevelFoot[LevelNow]; //找到加入新节点位置
					ActHead[ActNow]=ActBefore; //置头指针
					AllAct[ActNow]=Act; //加入新节点
					ActX[ActNow]=tx;
					ActY[ActNow]=ty; //存储移动后位置
					Table[ty][tx]=1; //做已到过标记
					if (Test( )) AllComplete=1; //完成?
				}
			}
		}
	}
}