prismtank

快乐分享,一起学习进步~

bfs 寻路演示程序

这个程序是 bfs 寻路 demo。

该程序可以让用户自由设置起点、终点、障碍物,并得出寻路结果。寻路算法用的是广度优先搜索算法(bfs),界面和图形显示用的是 easyx。

程序运行界面如下:

完整的源代码如下:

// 程序名称:bfs 寻路 demo
// 作者:光棱坦克
// QQ:3152239285
// 完成日期:2016-7-16
// easyx 版本:2015-10-15
//
#include <graphics.h>
#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;

const int WIDTH = 24, HEIGHT = 24;

struct Block
{
	BYTE x,y,depth,data[200];
	bool searched,isblock;

	void getdata(Block father,int dx,int dy)
	{
		depth=father.depth+1;
		memcpy(data,father.data,(depth-1)*sizeof(BYTE)*2);
		data[2*depth-2]=father.x+dx;
		data[2*depth-1]=father.y+dy;
	}
	void clean()
	{
		memset(data,0,sizeof(char)*200);
		searched=false;
		depth=0;
	}

}map[WIDTH][HEIGHT];

MOUSEMSG msg;
bool success=false;
int startx=0,starty=0,endx=WIDTH-1,endy=HEIGHT-1,mousemode=1;
queue<Block> q;

void map_search(int targx,int targy)
{
	if(targx>=0&&targy>=0&&targx<WIDTH&&targy<HEIGHT&&!map[targx][targy].searched)
	{
		map[targx][targy].searched=true;
		if(map[targx][targy].isblock)
			return;
		if(targx==endx&&targy==endy)
		{
			success=true;
			int i;
			char jieguo[5000]="",text[100];
			for(i=0;i<map[endx][endy].depth;i++)
			{
				char temp[20];
				if(i!=map[endx][endy].depth-1)
					sprintf(temp,"(%d,%d)->",map[endx][endy].data[i*2],map[endx][endy].data[i*2+1]);
				else
					sprintf(temp,"(%d,%d)",map[endx][endy].data[i*2],map[endx][endy].data[i*2+1]);

				strcat(jieguo,temp);

				if(i!=map[endx][endy].depth-1)
				{
					setfillcolor(RED);
					fillrectangle(map[endx][endy].data[i*2]*20,map[endx][endy].data[i*2+1]*20,map[endx][endy].data[i*2]*20+20,
					map[endx][endy].data[i*2+1]*20+20);
				}
			}
			sprintf(text,"成功,共%d步",map[endx][endy].depth);
			MessageBox(GetHWnd(),jieguo,text,0);
		}
		if(targx+1<WIDTH)
		{
			map[targx+1][targy].getdata(map[targx][targy],1,0);
			q.push(map[targx+1][targy]);
		}
		if(targy+1<HEIGHT)
		{
			map[targx][targy+1].getdata(map[targx][targy],0,1);
			q.push(map[targx][targy+1]);
		}
		if(targx>0)
		{
			map[targx-1][targy].getdata(map[targx][targy],-1,0);
			q.push(map[targx-1][targy]);
		}
		if(targy>0)
		{
			map[targx][targy-1].getdata(map[targx][targy],0,-1);
			q.push(map[targx][targy-1]);
		}
	}
}

void mapclean()
{
	int i,j;
	for(i=0;i<WIDTH;i++)
		for(j=0;j<HEIGHT;j++)
		{
			map[i][j].clean();
			map[i][j].isblock=false;
			map[i][j].x=i;
			map[i][j].y=j;
		}
	startx=0;
	starty=0;
	endx=WIDTH-1;
	endy=HEIGHT-1;
	success=false;
}

void runxunlu()
{
	int i,j;
	for(i=0;i<WIDTH;i++)
		for(j=0;j<HEIGHT;j++)
		{
			map[i][j].clean();
			map[i][j].x=i;
			map[i][j].y=j;
		}
	success=false;

	q.push(map[startx][starty]);

	while(!q.empty()&&!success)
	{
		map_search(q.front().x,q.front().y);
		q.pop();
	}

	if(!success)
		MessageBox(GetHWnd(),"很遗憾,寻路失败","提示",0);

	while(!q.empty())
		q.pop();
}

IMAGE buffer(WIDTH*20+160,HEIGHT*20);
void render()
{
	SetWorkingImage(&buffer);

	cleardevice();

	setbkmode(TRANSPARENT);

	setfillcolor(GREEN);
	fillrectangle(WIDTH*20,0,WIDTH*20+160,HEIGHT*20);

	setfillcolor(RED);

	fillrectangle(WIDTH*20,0,WIDTH*20+160,30);
	outtextxy(WIDTH*20+10,10,"设起点");

	fillrectangle(WIDTH*20,60,WIDTH*20+160,90);
	outtextxy(WIDTH*20+10,70,"设终点");

	fillrectangle(WIDTH*20,120,WIDTH*20+160,150);
	outtextxy(WIDTH*20+10,130,"设障碍");

	fillrectangle(WIDTH*20,180,WIDTH*20+160,210);
	outtextxy(WIDTH*20+10,190,"开始寻路");

	fillrectangle(WIDTH*20,240,WIDTH*20+160,270);
	outtextxy(WIDTH*20+10,250,"地图重置");

	setfillcolor(BLUE);
	fillrectangle(startx*20,starty*20,startx*20+20,starty*20+20);

	setfillcolor(BROWN);
	fillrectangle(endx*20,endy*20,endx*20+20,endy*20+20);

	setfillcolor(YELLOW);
	int i,j;
	for(i=0;i<WIDTH;i++)
		for(j=0;j<HEIGHT;j++)
		{
			if(map[i][j].isblock)
				fillrectangle(i*20,j*20,i*20+20,j*20+20);
		}
	SetWorkingImage();
	putimage(0,0,&buffer);

}
int WINAPI WinMain(HINSTANCE,HINSTANCE,LPSTR,int)
{
	initgraph(WIDTH*20+160,HEIGHT*20);

	while(true)
	{
		while(MouseHit())
		{
			msg=GetMouseMsg();
			if(msg.uMsg==WM_LBUTTONDOWN)
			{
				if(msg.x>=WIDTH*20)
				{
					if(msg.y>=0&&msg.y<=30)
						mousemode=1;
					
					else if(msg.y>=60&&msg.y<=90)
						mousemode=2;
					
					else if(msg.y>=120&&msg.y<=150)
						mousemode=3;
					
					else if(msg.y>=180&&msg.y<=210)
						runxunlu();
					
					else if(msg.y>=240&&msg.y<=270)
						mapclean();
				}
				else
				{
					switch(mousemode)
					{
						case 1:
							startx=msg.x/20;
							starty=msg.y/20;
							break;
						case 2:
							endx=msg.x/20;
							endy=msg.y/20;
							break;
						case 3:
							map[msg.x/20][msg.y/20].isblock=!map[msg.x/20][msg.y/20].isblock;
							break;
					}
				}
			}
		}
		render();
	}
	return 0;
}

作者:光棱坦克
QQ:3152239285

评论 (2) -

  • wxd

    2016/8/3 17:48:32 | 回复

    debug的情况下,各种设置障碍、寻路之后,点击右上角的叉叉关闭界面,偶尔会崩掉,崩点在SetWorkingImage();这个位置

    • 光棱坦克

      2016/8/29 16:38:23 | 回复

      我用的缓冲区技术,防闪烁,估计是在debug模式下,缓冲区image不释放造成的问题,应该是无解的。

添加评论

Loading