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

吃饭归来，继续这么有意思的讨论：）

“这个在特定的条件下可能会产生不稳定的情况”

不是这样的，这个算法除非为了需要加上随机性，否则结果还是确定的。第二和第三分线之所以不同，是因为他们的重点不一样。为了让基本的B*走出梳子的轮廓，我特意把第二个图的重点往下放中间调了。

“还有的就是在第三个例子里面，你第108个节点往下走的出发条件是什么，为什么不在107~102之间发生，这些也就是个问题所在啦”

在帖子正文算法过程中，第一条说明了这个原因：

1、起始，探索节点为自由节点，从原点出发，向目标前进。

即这是目标方向的引导性，和第二与第三图的分线不同是一个原因。

谢谢你的解析，我也明白你的意思。

但你之前提过的拉直的这个问题不知道会不会在拉直的动作中产生新的中节点，然后又有新的拉直，会不会产生连锁的返寻呢？

而且，那些节点之间需要拉直，该谁和谁拉直，这又是一个新的课题了，如果要实现里面的思路，最后的性能，还有内存方面的损耗会很可观的：P

你说过你的寻路方法比较接近动物的思考方法，

但我的观点是A*的思路，更接近于自然界的法则--水满则溢：）

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;	
}