`
qinysong
  • 浏览: 192427 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

一种高效的寻路算法 - B*寻路算法

阅读更多

在此把这个算法称作B* 寻路算法(Branch Star 分支寻路算法,且与A*对应),本算法适用于游戏中怪物的自动寻路,其效率远远超过A*算法,经过测试,效率是普通A*算法的几十上百倍。

通过引入该算法,一定程度上解决了游戏服务器端无法进行常规寻路的效率问题,除非服务器端有独立的AI处理线程,否则在服务器端无法允许可能消耗大量时间的寻路搜索,即使是业界普遍公认的最佳的A*,所以普遍的折中做法是服务器端只做近距离的寻路,或通过导航站点缩短A*的范围。

算法原理
本算法启发于自然界中真实动物的寻路过程,并加以改善以解决各种阻挡问题。
前置定义:
1、探索节点:
为了叙述方便,我们定义在寻路过程中向前探索的节点(地图格子)称为探索节点,起始探索节点即为原点。(探索节点可以对应为A*中的开放节点)

2、自由的探索节点:
探索节点朝着目标前进,如果前方不是阻挡,探索节点可以继续向前进入下一个地图格子,这种探索节点我们称为自由探索节点;

3、绕爬的探索节点:
探索节点朝着目标前进,如果前方是阻挡,探索节点将试图绕过阻挡,绕行中的探索节点我们成为绕爬的探索节点;
算法过程
1、起始,探索节点为自由节点,从原点出发,向目标前进;
2、自由节点前进过程中判断前面是否为障碍,
     a、不是障碍,向目标前进一步,仍为自由节点;
     b、是障碍,以前方障碍为界,分出左右两个分支,分别试图绕过障碍,这两个分支节点即成为两个绕爬的探索节点;
3、绕爬的探索节点绕过障碍后,又成为自由节点,回到2);
4、探索节点前进后,判断当前地图格子是否为目标格子,如果是则寻路成功,根据寻路过程构造完整路径;
5、寻路过程中,如果探索节点没有了,则寻路结束,表明没有目标格子不可达;


演示如下: 
    
   



B*与A*算法的性能比较

寻路次数比较(5秒钟寻路次数) 


 
B*与A*性能比较实例
1、 无障碍情况
此种情况,根据以上测试数据,B*算法效率是普通A*的44倍(左为A*,右为B*)

     
 

2、线形障碍
此种情况,根据以上测试数据,B*算法效率是普通A*的28倍(左为A*,右为B*)

   

  
3、环形障碍
此种情况,根据以上测试数据,B*算法效率是普通A*的132倍(左为A*,右为B*)

      


4、封闭障碍(目标不可达)
此种情况,根据以上测试数据,B*算法效率是普通A*的581倍(左为A*,右为B*)
    

衍生算法
通过以上封闭障碍,可以看出,这个方法在判断地图上的两个点是否可达上,也是非常高效的,在不可达情况下,时间复杂度与封闭障碍的周长相当,而不是整个地图的面积。

 

分享到:
评论
39 楼 qinysong 2011-01-12  
附件是b×程序源代码(一个包含B×和A×比较的vc6.0工程)
为解决变态阻挡,b×中引入了两个概念:
1、弯曲度,解决此类阻挡


2、弯曲回归,解决此类阻挡


本代码有一处已经发现的bug,就是在寻路的两个点上会不停遍历,后面有时间再把他修复

38 楼 cicl 2010-12-31  
楼主的A星看起来使用的是四个格子的A星,不知有没有与8个格子的A星进行比较?希望楼主提供修正死循环后的源码
37 楼 bugsage 2010-09-11  
楼主能不能说下探索节点终止是在什么时候?
36 楼 middin 2010-06-17  
我好像见我同学玩过类似这种算法的游戏……
感谢LZ!
35 楼 morroky 2010-06-10  
测试首先就要确定边界
没有边界还谈什么测试
就好比你脱离需求做测试有意义么
34 楼 leemissen 2010-06-10  
这也不算是把问题复杂化的,这叫测试,一个算法出来了,就要去验证其强壮与否,
你说要简单看问题,但你又提到递归,这不是自相矛盾了吗,
我们之所以去测试,去提意见是对楼主的算法的关注还有兴趣,
至少我们有认真的去阅读楼主的代码才能发现其中的问题,
而不是为了避免质问而把要面对的情况尽量简化,这不符合一个程序员应有的品德。
33 楼 morroky 2010-06-10  
你们不要把问题搞复杂了啊
自动寻路不要考虑迷宫地图
迷宫地图都是不能寻路的,地图都不会显示
自动寻路只要考虑大地图就行了
最好的做法应该是求出两点的最短路径,遇到障碍物也就是有交叉线
出现交叉点取上下或者左右坐标再向目的地球最短路径再向交叉点扩展
也就是个递归直到没有交叉点为止,这样基本能够算出最短路径
只是个思路自己想的应该大致上没错具体细节还要完善
32 楼 qinysong 2010-06-09  
丶Lo丨痕灬 写道
尝试了一下! 发现Lz程序在有的时候会进入一个死循环而找不到正确的路!

多谢发现了一个Bug,修了,试试这个
(更新附件,上一个有死循环的现象)
31 楼 丶Lo丨痕灬 2010-06-09  
尝试了一下! 发现Lz程序在有的时候会进入一个死循环而找不到正确的路!



30 楼 leemissen 2010-06-08  

我用的是JavaScript而已
29 楼 大器晚成 2010-06-07  
qinysong 写道
主体代码段如下(一气呵成有点流水账,仅参考吧),附件为执行演示程序
bool CPathFinder::BStar()
{
	std::list<Cell> opened;
	std::list<Cell> backup;
	
	Cell& firstCell = Cells[Origin.y][Origin.x];
	
	opened.push_back(firstCell);
	opened.sort();
	
	std::list<Cell>::iterator iter = NULL;
	while (opened.size() > 0)
	{
		for (iter = opened.begin(); iter != opened.end(); iter++)
		{
			Cell nextCell;
			Cell currentCell = *iter;
			if (currentCell.s != cell_state_origin)
			{
				Cells[currentCell.y][currentCell.x].s = cell_state_check;
			}

			// 自由节点
			if (currentCell.stick == stick_dir_none)
			{
				int dir = 0;
				int nextX = 0;
				int nextY = 0;
				for (dir = 0; dir < MAX_DIRECTION; dir++)
				{
					nextX = currentCell.x + Around[dir].x;
					nextY = currentCell.y + Around[dir].y;
					if (nextY < 0 || nextY >= CELL_NUM || nextX < 0 || nextX >= CELL_NUM)
					{
						continue;
					}

					int dirDiff = g_GetDirDiff(currentCell.x, currentCell.y, Target.x, Target.y, nextX, nextY);
					if (dirDiff <= 8)
					{
						nextCell = Cells[nextY][nextX];
						break;
					}
				}

				if (nextCell.x == Target.x && nextCell.y == Target.y)
				{
					nextCell.px = currentCell.x;
					nextCell.py = currentCell.y;
					nextCell.g = currentCell.g + 1;
					
					Cells[nextY][nextX] = nextCell;

					BuildPath();
					UpdateView();
					return true;
				}
				else if (nextCell.s == cell_state_none)
				{
					Cells[nextY][nextX].s = cell_state_next;
					nextCell.s = cell_state_next;
					UpdateView();
					SleepMoment();

					nextCell.px = currentCell.x;
					nextCell.py = currentCell.y;				
					nextCell.g = currentCell.g + 1;				
					nextCell.s = cell_state_open;

					Cells[nextY][nextX] = nextCell;

					backup.push_back(nextCell);
				}
				else if (nextCell.s == cell_state_close)
				{
					if (nextCell.reel > currentCell.reel)
					{
						Cells[nextY][nextX].s = cell_state_next;
						nextCell.s = cell_state_next;
						UpdateView();
						SleepMoment();
						
						nextCell.reel = currentCell.reel;
						nextCell.s = cell_state_open;
						nextCell.stick = stick_dir_none;
						nextCell.dir = -1;
						
						Cells[nextY][nextX] = nextCell;
						
						backup.push_back(nextCell);
					}
				}
				else if (nextCell.s == cell_state_balk)
				{
					Cell left, right;
					bool cancel = false;
					int testdir = 0;
					for (testdir = 0; testdir < 4; testdir++)
					{
						if (StickAround[stick_dir_left][testdir] == dir)
						{
							break;
						}
					}
					int count = 0;
					for (testdir = testdir+1, count = 0; count < 3; testdir++, count++)
					{
						if (testdir == 4) testdir = 0;
						nextX = currentCell.x + Around[StickAround[stick_dir_left][testdir]].x;
						nextY = currentCell.y + Around[StickAround[stick_dir_left][testdir]].y;
						if (nextY < 0 || nextY >= CELL_NUM || nextX < 0 || nextX >= CELL_NUM)
						{
							cancel = true;
							break;
						}

						left = Cells[nextY][nextX];
						if (left.s != cell_state_balk)
						{
							break;
						}

					}
					if (cancel == false)
					{
						left.stick = stick_dir_right;
						left.dir = StickAround[stick_dir_left][testdir];
						
						if (Cells[nextY][nextX].s == cell_state_none)
						{
							left.px = currentCell.x;
							left.py = currentCell.y;
							left.g = currentCell.g + 1;				
						}
						else if (Cells[nextY][nextX].s == cell_state_close)
						{
							if (Cells[nextY][nextX].stick == stick_dir_left 
								&& (Cells[nextY][nextX].x == currentCell.px && Cells[nextY][nextX].y == currentCell.py))
							{
								cancel = true; 
							}
						}
						else if (Cells[nextY][nextX].s == cell_state_open)
						{
							if (left.g > currentCell.g + 1)
							{
								left.px = currentCell.x;
								left.py = currentCell.y;
								left.g = currentCell.g + 1;
							}
						}
						if (cancel == false)
						{
							left.reel = count + 1;
							left.s = cell_state_next;
							Cells[nextY][nextX].s = cell_state_next;
							
							UpdateView();
							SleepMoment();
							
							left.s = cell_state_open;
							
							Cells[nextY][nextX] = left;
							
							backup.push_back(left);
						}
					}

					cancel = false;
					for (testdir = 0; testdir < 4; testdir++)
					{
						if (StickAround[stick_dir_right][testdir] == dir)
						{
							break;
						}
					}
					for (testdir = testdir + 1, count = 0; count < 3; count++, testdir++)
					{
						if (testdir == 4) testdir = 0;
						nextX = currentCell.x + Around[StickAround[stick_dir_right][testdir]].x;
						nextY = currentCell.y + Around[StickAround[stick_dir_right][testdir]].y;
						if (nextY < 0 || nextY >= CELL_NUM || nextX < 0 || nextX >= CELL_NUM)
						{
							cancel = true;
							break;
						}
						
						right = Cells[nextY][nextX];
						if (right.s != cell_state_balk)
						{
							break;
						}
						
					}
					if (cancel == false)
					{
						right.stick = stick_dir_left;
						right.dir = StickAround[stick_dir_right][testdir];
						
						if (Cells[nextY][nextX].s == cell_state_none)
						{
							right.px = currentCell.x;
							right.py = currentCell.y;
							right.g = currentCell.g + 1;				
						}
						else if (Cells[nextY][nextX].s == cell_state_close)
						{
							if (Cells[nextY][nextX].stick == stick_dir_right 
								&& (Cells[nextY][nextX].x == currentCell.px && Cells[nextY][nextX].y == currentCell.py))
							{
								cancel = true; 
							}
						}
						else if (Cells[nextY][nextX].s == cell_state_open)
						{
							if (right.g > currentCell.g + 1)
							{
								right.px = currentCell.x;
								right.py = currentCell.y;
								right.g = currentCell.g + 1;				
							}
						}
						if (cancel == false)
						{
							right.reel = count + 1;
							right.s = cell_state_next;
							Cells[nextY][nextX].s = cell_state_next;
							
							UpdateView();
							SleepMoment();
							
							right.s = cell_state_open;
							
							Cells[nextY][nextX] = right;						
							backup.push_back(right);
						}
					}
				}
			}
			else
			{
				// 爬绕节点
				int nextX = 0;
				int nextY = 0;
				Cell nextCell;
				bool cancel = false;
				if (currentCell.stick == stick_dir_right)
				{
					int dir = 0;
					for (dir = 0; dir < 4; dir++)
					{
						if (StickAround[stick_dir_left][dir] == currentCell.dir)
						{
							break;
						}
					}
					dir += 2 + 1;
					if (dir >= 4) dir -= 4;
					for (int count = 0; count < 4; count++,dir++)
					{
						if (dir >= 4) dir -= 4;
						int nextdir = StickAround[stick_dir_left][dir];
						nextX = currentCell.x + Around[nextdir].x;
						nextY = currentCell.y + Around[nextdir].y;
						if (nextY < 0 || nextY >= CELL_NUM || nextX < 0 || nextX >= CELL_NUM)
						{
							break;
						}
						
						nextCell = Cells[nextY][nextX];
						if (nextCell.s != cell_state_balk)
						{
							if (Cells[nextY][nextX].s == cell_state_none)
							{
								nextCell.px = currentCell.x;
								nextCell.py = currentCell.y;
								nextCell.g = currentCell.g + 1;				
							}
							else if (Cells[nextY][nextX].s == cell_state_close)
							{
								if (Cells[nextY][nextX].stick == stick_dir_left 
									&& (Cells[nextY][nextX].x == currentCell.px && Cells[nextY][nextX].y == currentCell.py))
								{
									cancel = true; 
								}
								else if (nextCell.g > currentCell.g + 1)
								{
									nextCell.px = currentCell.x;
									nextCell.py = currentCell.y;
									nextCell.g = currentCell.g + 1;				
								}
							}
							if (cancel == false)
							{
								nextCell.s = cell_state_next;
								Cells[nextY][nextX].s = cell_state_next;
								
								UpdateView();
								SleepMoment();
								
								int reelAdd = count - 1;
								nextCell.reel = currentCell.reel + reelAdd;
								if (nextCell.reel < 0)
									nextCell.reel = 0;
								
								nextCell.s = cell_state_open;
								Cells[nextY][nextX] = nextCell;
								int dirDiff = g_GetDirDiff(currentCell.x, currentCell.y, Target.x, Target.y, nextX, nextY);
								
								if (nextCell.reel > 0)
								{
									nextCell.stick = stick_dir_right;
									nextCell.dir = nextdir;
								}
								else
								{
									nextCell.stick = stick_dir_none;
									nextCell.dir = -1;
								}
								
								Cells[nextY][nextX] = nextCell;
								backup.push_back(nextCell);
								break;
							}
						}
					}
				}
				else
				{
					int dir = 0;
					for (dir = 0; dir < 4; dir++)
					{
						if (StickAround[stick_dir_right][dir] == currentCell.dir)
						{
							break;
						}
					}
					dir += 2 + 1;
					if (dir >= 4) dir -= 4;
					for (int count = 0; count < 4; count++,dir++)
					{
						if (dir >= 4) dir -= 4;
						int nextdir = StickAround[stick_dir_right][dir];
						nextX = currentCell.x + Around[nextdir].x;
						nextY = currentCell.y + Around[nextdir].y;
						if (nextY < 0 || nextY >= CELL_NUM || nextX < 0 || nextX >= CELL_NUM)
						{
							break;
						}
						
						nextCell = Cells[nextY][nextX];
						if (nextCell.s != cell_state_balk)
						{
							if (Cells[nextY][nextX].s == cell_state_none)
							{
								nextCell.px = currentCell.x;
								nextCell.py = currentCell.y;
								nextCell.g = currentCell.g + 1;				
							}
							else if (Cells[nextY][nextX].s == cell_state_close)
							{
								if (Cells[nextY][nextX].stick == stick_dir_right 
									&& (Cells[nextY][nextX].x == currentCell.px && Cells[nextY][nextX].y == currentCell.py))
								{
									cancel = true; 
								}
								else if (nextCell.g > currentCell.g + 1)
								{
									nextCell.px = currentCell.x;
									nextCell.py = currentCell.y;
									nextCell.g = currentCell.g + 1;				
								}
							}
							if (cancel == false)
							{
								nextCell.s = cell_state_next;
								Cells[nextY][nextX].s = cell_state_next;
								
								UpdateView();
								SleepMoment();
								
								int reelAdd = count - 1;
								nextCell.reel = currentCell.reel + reelAdd;
								if (nextCell.reel < 0)
									nextCell.reel = 0;

								nextCell.s = cell_state_open;
								Cells[nextY][nextX] = nextCell;
								int dirDiff = g_GetDirDiff(currentCell.x, currentCell.y, Target.x, Target.y, nextX, nextY);
								if (nextCell.reel > 0)
								{
									nextCell.stick = stick_dir_left;
									nextCell.dir = nextdir;
								}
								else
								{
									nextCell.stick = stick_dir_none;
									nextCell.dir = -1;
								}
								
								Cells[nextY][nextX] = nextCell;
								backup.push_back(nextCell);
								break;
							} // if (cancel == false)
						} // if (nextCell.s != cell_state_balk)
					} // for (int n = 0; n < 3; n++,dir++)
				} // else currentCell.stickdir == en_stick_right
			} // else currentCell.prevdir != -1
			Cells[currentCell.y][currentCell.x].s = cell_state_close;
		}
		opened.clear();
		opened.splice(opened.end(), backup);
	}
	
	return false;	
}

感觉这种算法不错  我用 java实现看看  呵呵
C++代码就不看了  感谢楼主共享,  这个和我之前想的差不多
28 楼 qinysong 2010-06-05  
主体代码段如下(一气呵成有点流水账,仅参考吧),附件为执行演示程序
bool CPathFinder::BStar()
{
	std::list<Cell> opened;
	std::list<Cell> backup;
	
	Cell& firstCell = Cells[Origin.y][Origin.x];
	
	opened.push_back(firstCell);
	opened.sort();
	
	std::list<Cell>::iterator iter = NULL;
	while (opened.size() > 0)
	{
		for (iter = opened.begin(); iter != opened.end(); iter++)
		{
			Cell nextCell;
			Cell currentCell = *iter;
			if (currentCell.s != cell_state_origin)
			{
				Cells[currentCell.y][currentCell.x].s = cell_state_check;
			}

			// 自由节点
			if (currentCell.stick == stick_dir_none)
			{
				int dir = 0;
				int nextX = 0;
				int nextY = 0;
				for (dir = 0; dir < MAX_DIRECTION; dir++)
				{
					nextX = currentCell.x + Around[dir].x;
					nextY = currentCell.y + Around[dir].y;
					if (nextY < 0 || nextY >= CELL_NUM || nextX < 0 || nextX >= CELL_NUM)
					{
						continue;
					}

					int dirDiff = g_GetDirDiff(currentCell.x, currentCell.y, Target.x, Target.y, nextX, nextY);
					if (dirDiff <= 8)
					{
						nextCell = Cells[nextY][nextX];
						break;
					}
				}

				if (nextCell.x == Target.x && nextCell.y == Target.y)
				{
					nextCell.px = currentCell.x;
					nextCell.py = currentCell.y;
					nextCell.g = currentCell.g + 1;
					
					Cells[nextY][nextX] = nextCell;

					BuildPath();
					UpdateView();
					return true;
				}
				else if (nextCell.s == cell_state_none)
				{
					Cells[nextY][nextX].s = cell_state_next;
					nextCell.s = cell_state_next;
					UpdateView();
					SleepMoment();

					nextCell.px = currentCell.x;
					nextCell.py = currentCell.y;				
					nextCell.g = currentCell.g + 1;				
					nextCell.s = cell_state_open;

					Cells[nextY][nextX] = nextCell;

					backup.push_back(nextCell);
				}
				else if (nextCell.s == cell_state_close)
				{
					if (nextCell.reel > currentCell.reel)
					{
						Cells[nextY][nextX].s = cell_state_next;
						nextCell.s = cell_state_next;
						UpdateView();
						SleepMoment();
						
						nextCell.reel = currentCell.reel;
						nextCell.s = cell_state_open;
						nextCell.stick = stick_dir_none;
						nextCell.dir = -1;
						
						Cells[nextY][nextX] = nextCell;
						
						backup.push_back(nextCell);
					}
				}
				else if (nextCell.s == cell_state_balk)
				{
					Cell left, right;
					bool cancel = false;
					int testdir = 0;
					for (testdir = 0; testdir < 4; testdir++)
					{
						if (StickAround[stick_dir_left][testdir] == dir)
						{
							break;
						}
					}
					int count = 0;
					for (testdir = testdir+1, count = 0; count < 3; testdir++, count++)
					{
						if (testdir == 4) testdir = 0;
						nextX = currentCell.x + Around[StickAround[stick_dir_left][testdir]].x;
						nextY = currentCell.y + Around[StickAround[stick_dir_left][testdir]].y;
						if (nextY < 0 || nextY >= CELL_NUM || nextX < 0 || nextX >= CELL_NUM)
						{
							cancel = true;
							break;
						}

						left = Cells[nextY][nextX];
						if (left.s != cell_state_balk)
						{
							break;
						}

					}
					if (cancel == false)
					{
						left.stick = stick_dir_right;
						left.dir = StickAround[stick_dir_left][testdir];
						
						if (Cells[nextY][nextX].s == cell_state_none)
						{
							left.px = currentCell.x;
							left.py = currentCell.y;
							left.g = currentCell.g + 1;				
						}
						else if (Cells[nextY][nextX].s == cell_state_close)
						{
							if (Cells[nextY][nextX].stick == stick_dir_left 
								&& (Cells[nextY][nextX].x == currentCell.px && Cells[nextY][nextX].y == currentCell.py))
							{
								cancel = true; 
							}
						}
						else if (Cells[nextY][nextX].s == cell_state_open)
						{
							if (left.g > currentCell.g + 1)
							{
								left.px = currentCell.x;
								left.py = currentCell.y;
								left.g = currentCell.g + 1;
							}
						}
						if (cancel == false)
						{
							left.reel = count + 1;
							left.s = cell_state_next;
							Cells[nextY][nextX].s = cell_state_next;
							
							UpdateView();
							SleepMoment();
							
							left.s = cell_state_open;
							
							Cells[nextY][nextX] = left;
							
							backup.push_back(left);
						}
					}

					cancel = false;
					for (testdir = 0; testdir < 4; testdir++)
					{
						if (StickAround[stick_dir_right][testdir] == dir)
						{
							break;
						}
					}
					for (testdir = testdir + 1, count = 0; count < 3; count++, testdir++)
					{
						if (testdir == 4) testdir = 0;
						nextX = currentCell.x + Around[StickAround[stick_dir_right][testdir]].x;
						nextY = currentCell.y + Around[StickAround[stick_dir_right][testdir]].y;
						if (nextY < 0 || nextY >= CELL_NUM || nextX < 0 || nextX >= CELL_NUM)
						{
							cancel = true;
							break;
						}
						
						right = Cells[nextY][nextX];
						if (right.s != cell_state_balk)
						{
							break;
						}
						
					}
					if (cancel == false)
					{
						right.stick = stick_dir_left;
						right.dir = StickAround[stick_dir_right][testdir];
						
						if (Cells[nextY][nextX].s == cell_state_none)
						{
							right.px = currentCell.x;
							right.py = currentCell.y;
							right.g = currentCell.g + 1;				
						}
						else if (Cells[nextY][nextX].s == cell_state_close)
						{
							if (Cells[nextY][nextX].stick == stick_dir_right 
								&& (Cells[nextY][nextX].x == currentCell.px && Cells[nextY][nextX].y == currentCell.py))
							{
								cancel = true; 
							}
						}
						else if (Cells[nextY][nextX].s == cell_state_open)
						{
							if (right.g > currentCell.g + 1)
							{
								right.px = currentCell.x;
								right.py = currentCell.y;
								right.g = currentCell.g + 1;				
							}
						}
						if (cancel == false)
						{
							right.reel = count + 1;
							right.s = cell_state_next;
							Cells[nextY][nextX].s = cell_state_next;
							
							UpdateView();
							SleepMoment();
							
							right.s = cell_state_open;
							
							Cells[nextY][nextX] = right;						
							backup.push_back(right);
						}
					}
				}
			}
			else
			{
				// 爬绕节点
				int nextX = 0;
				int nextY = 0;
				Cell nextCell;
				bool cancel = false;
				if (currentCell.stick == stick_dir_right)
				{
					int dir = 0;
					for (dir = 0; dir < 4; dir++)
					{
						if (StickAround[stick_dir_left][dir] == currentCell.dir)
						{
							break;
						}
					}
					dir += 2 + 1;
					if (dir >= 4) dir -= 4;
					for (int count = 0; count < 4; count++,dir++)
					{
						if (dir >= 4) dir -= 4;
						int nextdir = StickAround[stick_dir_left][dir];
						nextX = currentCell.x + Around[nextdir].x;
						nextY = currentCell.y + Around[nextdir].y;
						if (nextY < 0 || nextY >= CELL_NUM || nextX < 0 || nextX >= CELL_NUM)
						{
							break;
						}
						
						nextCell = Cells[nextY][nextX];
						if (nextCell.s != cell_state_balk)
						{
							if (Cells[nextY][nextX].s == cell_state_none)
							{
								nextCell.px = currentCell.x;
								nextCell.py = currentCell.y;
								nextCell.g = currentCell.g + 1;				
							}
							else if (Cells[nextY][nextX].s == cell_state_close)
							{
								if (Cells[nextY][nextX].stick == stick_dir_left 
									&& (Cells[nextY][nextX].x == currentCell.px && Cells[nextY][nextX].y == currentCell.py))
								{
									cancel = true; 
								}
								else if (nextCell.g > currentCell.g + 1)
								{
									nextCell.px = currentCell.x;
									nextCell.py = currentCell.y;
									nextCell.g = currentCell.g + 1;				
								}
							}
							if (cancel == false)
							{
								nextCell.s = cell_state_next;
								Cells[nextY][nextX].s = cell_state_next;
								
								UpdateView();
								SleepMoment();
								
								int reelAdd = count - 1;
								nextCell.reel = currentCell.reel + reelAdd;
								if (nextCell.reel < 0)
									nextCell.reel = 0;
								
								nextCell.s = cell_state_open;
								Cells[nextY][nextX] = nextCell;
								int dirDiff = g_GetDirDiff(currentCell.x, currentCell.y, Target.x, Target.y, nextX, nextY);
								
								if (nextCell.reel > 0)
								{
									nextCell.stick = stick_dir_right;
									nextCell.dir = nextdir;
								}
								else
								{
									nextCell.stick = stick_dir_none;
									nextCell.dir = -1;
								}
								
								Cells[nextY][nextX] = nextCell;
								backup.push_back(nextCell);
								break;
							}
						}
					}
				}
				else
				{
					int dir = 0;
					for (dir = 0; dir < 4; dir++)
					{
						if (StickAround[stick_dir_right][dir] == currentCell.dir)
						{
							break;
						}
					}
					dir += 2 + 1;
					if (dir >= 4) dir -= 4;
					for (int count = 0; count < 4; count++,dir++)
					{
						if (dir >= 4) dir -= 4;
						int nextdir = StickAround[stick_dir_right][dir];
						nextX = currentCell.x + Around[nextdir].x;
						nextY = currentCell.y + Around[nextdir].y;
						if (nextY < 0 || nextY >= CELL_NUM || nextX < 0 || nextX >= CELL_NUM)
						{
							break;
						}
						
						nextCell = Cells[nextY][nextX];
						if (nextCell.s != cell_state_balk)
						{
							if (Cells[nextY][nextX].s == cell_state_none)
							{
								nextCell.px = currentCell.x;
								nextCell.py = currentCell.y;
								nextCell.g = currentCell.g + 1;				
							}
							else if (Cells[nextY][nextX].s == cell_state_close)
							{
								if (Cells[nextY][nextX].stick == stick_dir_right 
									&& (Cells[nextY][nextX].x == currentCell.px && Cells[nextY][nextX].y == currentCell.py))
								{
									cancel = true; 
								}
								else if (nextCell.g > currentCell.g + 1)
								{
									nextCell.px = currentCell.x;
									nextCell.py = currentCell.y;
									nextCell.g = currentCell.g + 1;				
								}
							}
							if (cancel == false)
							{
								nextCell.s = cell_state_next;
								Cells[nextY][nextX].s = cell_state_next;
								
								UpdateView();
								SleepMoment();
								
								int reelAdd = count - 1;
								nextCell.reel = currentCell.reel + reelAdd;
								if (nextCell.reel < 0)
									nextCell.reel = 0;

								nextCell.s = cell_state_open;
								Cells[nextY][nextX] = nextCell;
								int dirDiff = g_GetDirDiff(currentCell.x, currentCell.y, Target.x, Target.y, nextX, nextY);
								if (nextCell.reel > 0)
								{
									nextCell.stick = stick_dir_left;
									nextCell.dir = nextdir;
								}
								else
								{
									nextCell.stick = stick_dir_none;
									nextCell.dir = -1;
								}
								
								Cells[nextY][nextX] = nextCell;
								backup.push_back(nextCell);
								break;
							} // if (cancel == false)
						} // if (nextCell.s != cell_state_balk)
					} // for (int n = 0; n < 3; n++,dir++)
				} // else currentCell.stickdir == en_stick_right
			} // else currentCell.prevdir != -1
			Cells[currentCell.y][currentCell.x].s = cell_state_close;
		}
		opened.clear();
		opened.splice(opened.end(), backup);
	}
	
	return false;	
}
27 楼 gundumw100 2010-06-05  
想法不错,希望出个演示程序,谢谢
26 楼 flasheep 2010-06-04  
强烈支持这样有探索精神的原创贴 感谢LZ
25 楼 steafler 2010-06-03  
源码呢,拿出来分享一下撒
24 楼 fc6029585 2010-06-03  
源码呢?
23 楼 leemissen 2010-06-02  
是的 我那A*是很早之前的Demo ,自己探索时写的,所以没有考虑对角穿墙的问题,教材上面的A*应该把四个对角位的寻路给屏蔽掉的。
22 楼 procty 2010-06-01  
A*我写过,感觉楼主用来做例子的A*写错了。做例子的A*是个全向搜索的算法,和真正的A*似乎不服啊。
21 楼 qinysong 2010-06-01  
<div class="quote_title">leemissen 写道</div>
<div class="quote_div">
<p><br>谢谢你的解析,我也明白你的意思。</p>
<p>但你之前提过的拉直的这个问题不知道会不会在拉直的动作中产生新的中节点,然后又有新的拉直,会不会产生连锁的返寻呢?</p>
<p>而且,那些节点之间需要拉直,该谁和谁拉直,这又是一个新的课题了,如果要实现里面的思路,最后的性能,还有内存方面的损耗会很可观的:P</p>
<p>你说过你的寻路方法比较接近动物的思考方法,</p>
<p>但我的观点是A*的思路,更接近于自然界的法则--水满则溢:)</p>
</div>
<p><br>嗯。</p>
<p>这就回归到算法的使用范围和场景,B*不适合解决最优寻路,B*适合作为<span style="color: #ff0000;"><span style="color: #333300;">游戏系统中服务器端</span><span style="color: #333300;">的</span></span><span style="color: #333300;">长距离寻路</span>。且在无策划需求的话,我认为不大需要进行拉直优化。</p>
<p> </p>
<p>但是拉直优化可以支持策划出很多好的关卡设计。比如模拟出Boss智能路线学习,它会每一次走的路线都比上一次更优(拉直一个拐点),以迫使玩家每次重复都提高其过关难度。</p>
20 楼 leemissen 2010-06-01  
<div class="quote_title">qinysong 写道</div>
<div class="quote_div">
<div class="quote_title">leemissen 写道</div>
<div class="quote_div">
<div class="quote_title">qinysong 写道</div>
<div class="quote_div">
<p><br>非常高兴和你谈到这个问题,之前我也想过这种情况,我先把你这种阻挡下的B*寻路贴出来</p>
<p><img style="vertical-align: text-top;" src="http://dl.iteye.com/upload/picture/pic/64155/4ae25086-134d-32ba-b2ea-3a051ceec541.gif" alt="" width="731" height="403"></p>
<p> </p>
<p>你所担心的其实是上面第三种情况,看起来这种路线确实非常笨,呵呵。不过这个问题其实不难解决——在寻路过程中做个拉直,比如上面的73,92节点做个拉直,这样路线会趋近于最优,而优化所带来的性能损耗不会超过寻路本身,即优化后的时间复杂度&lt;O(B*) × 2 = O(B*), O(B*) 为B*基本算法的复杂度</p>
</div>
<p>很高兴能看到你这么认真的回复,这里首先肯定的是你的算法的效率感觉上是高,不过不知道你有没有留意到上面图里,第二个和第三个的例子的起始条件是相同的,</p>
<p>但在第二个节点的时候就开始出现不同的分线了,这个在特定的条件下可能会产生不稳定的情况,就好比导航的时候会让航线结果不一致,</p>
<p>还有的就是在第三个例子里面,你第108个节点往下走的出发条件是什么,为什么不在107~102之间发生,这些也就是个问题所在啦。<br>谢谢指教啦。</p>
</div>
<p><br>吃饭归来,继续这么有意思的讨论:)</p>
<p> </p>
<p>“这个在特定的条件下可能会产生不稳定的情况”</p>
<p>不是这样的,这个算法除非为了需要加上随机性,否则结果还是确定的。第二和第三分线之所以不同,是因为他们的重点不一样。为了让基本的B*走出梳子的轮廓,我特意把第二个图的重点往下放中间调了。</p>
<p> </p>
<p>“还有的就是在第三个例子里面,你第108个节点往下走的出发条件是什么,为什么不在107~102之间发生,这些也就是个问题所在啦”</p>
<p>在帖子正文算法过程中,第一条说明了这个原因:</p>
<p><span style="font-family: 'Times New Roman'; font-size: 10.5pt;">1、</span><span style="font-family: 'Times New Roman'; font-size: 10.5pt;">起始,探索节点为自由节点,<span style="color: #ff0000;">从原点出发,向目标前进。</span></span></p>
<p><span style="font-family: 'Times New Roman'; font-size: 10.5pt;"><span style="font-family: Verdana; font-size: x-small;">即这是目标方向的引导性,和第二与第三图的分线不同是一个原因。</span></span></p>
<p> </p>
</div>
<p><br>谢谢你的解析,我也明白你的意思。</p>
<p>但你之前提过的拉直的这个问题不知道会不会在拉直的动作中产生新的中节点,然后又有新的拉直,会不会产生连锁的返寻呢?</p>
<p>而且,那些节点之间需要拉直,该谁和谁拉直,这又是一个新的课题了,如果要实现里面的思路,最后的性能,还有内存方面的损耗会很可观的:P</p>
<p>你说过你的寻路方法比较接近动物的思考方法,</p>
<p>但我的观点是A*的思路,更接近于自然界的法则--水满则溢:)</p>

相关推荐

    寻路算法 - A*算法(简易函数接口)

    最新在研究寻路算法,在此要感谢大佬的技术支持 https://bbs.egret.com/thread-2524-1-1.html 我研究大佬的代码后,取出了A* 的计算函数。 我在大佬的帖子里,看到有高人提出:分帧计算的概念 下一篇博,会根据...

    b* 寻路算法

    总的来说,B*寻路算法是一种适应性强、准确度高的路径规划方法,尤其适用于动态或不确定的环境。通过理解和应用B*算法,我们可以设计出更智能的路径搜索系统,广泛应用于游戏开发、机器人导航、物流规划等领域。

    A*寻路算法 源码

    A*寻路算法(A* Pathfinding Algorithm)是游戏开发、地图导航、机器人路径规划等领域广泛应用的一种高效路径搜索算法。它结合了Dijkstra算法的全局最优性和BFS(广度优先搜索)的效率,通过引入启发式函数来指导搜索,...

    四方向走迷宫&寻路算法C语言

    - **寻路算法**:用于在复杂环境中寻找从起点到终点最短或最优路径的算法,如A*算法、Dijkstra算法、深度优先搜索(DFS)和广度优先搜索(BFS)等。 2. **四方向与八方向**: - **四方向**:上、下、左、右四个基本...

    a*寻路算法,c++类

    **A*寻路算法**是一种广泛应用的路径搜索算法,它结合了Dijkstra算法的最短路径特性以及优先级队列的效率,同时引入了启发式信息以提高搜索速度。在游戏开发、图形图像处理、地图导航等领域,A*算法被广泛用于计算两...

    cocos creator 实现A*寻路

    A*(A-Star)寻路算法是路径规划领域中一种广泛应用的算法,它结合了Dijkstra算法的最短路径特性与优先级队列的效率优势。在Cocos Creator中,利用JavaScript实现A*寻路算法可以为游戏或交互式应用提供高效、智能的...

    优秀程序员必须知道的32个算法

    - **定义**: 一种高效的多项式乘法算法,特别适用于大整数乘法。 - **特点**: - 通过递归将乘法问题转化为加法问题。 - 时间复杂度为O(n^log2(3))。 - **应用场景**: - 计算机代数系统。 - 大整数计算。 #### ...

    自动寻路算法(A*算法)分享

    自动寻路算法是计算机科学和游戏开发中的一个重要领域,它主要解决的是在复杂环境中找到从起点到终点的最优路径问题。A*(A-Star)算法是其中一种广泛应用且高效的算法,它结合了Dijkstra算法的最优化路径寻找和...

    A*自动寻路算法实现(java)

    下载本程序仅可演示A*自动寻路算法实现(java),该程序是基于我写的网络版贪吃蛇基础上编写的(网络版贪吃蛇...wasd键控制太阳的方向,鼠标左击目的地,会根据A*自动寻路算法计算出一条最优路线,太阳按最优路线移动。

    A星寻路算法(A*)Flex 实现

    A星(A*)寻路算法是一种在图形中寻找从起点到终点最短路径的搜索算法,广泛应用在游戏开发、路径规划、地图导航等领域。它结合了Dijkstra算法的全局最优性和 Greedy Best-First Search的效率,通过引入启发式函数来...

    A*寻路算法

    A*寻路算法是一种广泛应用于游戏开发、机器人路径规划等领域的重要算法。它结合了最佳优先搜索策略与启发式搜索技术,能够有效地找到从起点到终点的最短路径。尽管A*算法在初次接触时可能显得复杂,但一旦掌握了其...

    寻路系统之A*算法原理

    通过以上分析,我们可以看出A*算法是一种结合了贪心策略和启发式搜索策略的强大寻路算法。通过对节点成本的有效估计,A*算法能够在众多候选路径中快速找到最优路径。掌握A*算法不仅有助于解决实际的寻路问题,也能为...

    a*算法 寻路算法 寻路寻路寻路寻路寻路寻路寻路寻路寻路寻路寻路

    a*(A-star)算法是一种在图形搜索中用于寻找从起点到终点最短路径的启发式搜索算法。它结合了Dijkstra算法的最优性和BFS(广度优先搜索)的效率,通过引入启发式函数来指导搜索方向,从而更快地找到目标。a*算法...

    软件价值3-A*算法寻路

    A*(A-star)算法作为其中的一种高效寻路算法,因其智能性和准确性而备受青睐。本项目将深入探讨A*算法的原理、实现及其在实际应用中的价值。 A*算法是一种启发式搜索算法,由Peter Hart、Nils Nilsson和Brendan ...

    A*走路 自动寻路A*算法 易语言源码优化版

    A*(A-star)算法是一种广泛应用的路径搜索算法,它在自动寻路系统中起着核心作用。易语言是一种中国本土开发的、面向对象的编程语言,它以其简单易学的特点受到很多程序员的喜爱。这个“A*走路 自动寻路A*算法 ...

    实用算法基础教程--算法和数据结构

    - **概念**: 动态规划是一种优化技术,通过把原问题分解为互相重叠的子问题,再递归求解子问题,存储子问题的解而避免重复计算。 - **案例**: 最长公共子序列问题、编辑距离问题等。 - **第二节:动态规划与递推**...

    A* 寻路算法实例

    A*(发音为 "A-star")寻路算法是一种在图形中寻找最短路径的高效算法,广泛应用于游戏开发、地图导航、网络路由等领域。它结合了Dijkstra算法的全局最优性和最佳优先搜索的效率,通过引入启发式函数来估计从起点到...

Global site tag (gtag.js) - Google Analytics