我最近对A *搜索算法感到不满。我曾经尝试过,但没有成功,但是这次我取得了一定的成功。它总是找到一条路径,除非它不能(显然),并且通常接近最短的路径。其他时候,它的作用确实很棘手,因为它加了太多次,呈锯齿状,随机向错误的方向移动。真奇怪截图here.
代码如下:
int manhattan( Coord a, Coord b )
{
int x = abs(b.x-a.x);
int y = abs(b.y-a.y);
return x+y;
}
std::vector<Coord> AStar( std::vector< std::vector< int > > grid, Point start, Point end )
{
//The current 'focal' point.
Point *cur;
//The open and closed lists.
std::vector< Point* > closed;
std::vector< Point* > open;
//Start by adding the starting position to the list.
open.push_back( &start );
//Just so it knows whether or not to try and reconstruct a path.
bool error = true;
while( open.size() > 0 )
{
//The current point is the first entry in the open list.
cur = open.at(0);
if( cur->getPos() == end.getPos() )
{
error = false;
break;
}
//Add in all the neighbors of the current point.
for( int y = -1; y <= 1; y++ )
{
for( int x = -1; x <= 1; x++ )
{
int curX = cur->getPos().x+x;
int curY = cur->getPos().y+y;
int movCost = 10;
//If it is a diagonal, make it cost 14 instead of 10.
if( (y == -1 && x == -1)||
(y == 1 && x == -1)||
(y == -1 && x == 1)||
(y == 1 && x == 1))
{
movCost = 14;
//continue;
}
Coord temp( curX, curY );
bool make = true;
//If it is outside the range of the map, continue.
if( curY >= grid.size() ||
curX >= grid.size() )
{
continue;
}
/*
These two loops are to check whether or not the point's neighbors already exist.
This feels really sloppy to me. Please tell me if there is a better way.
*/
for( int i = 0; i < open.size(); i++ )
{
if( temp == open.at(i)->getPos() )
{
make = false;
break;
}
}
for( int i = 0; i < closed.size(); i++ )
{
if( temp == closed.at(i)->getPos() )
{
make = false;
break;
}
}
//If the point in the map is a zero, then it is a wall. Continue.
if( (grid.at(temp.x).at(temp.y) == 0 ) ||
( temp.x<0 || temp.y < 0 ) )
{
continue;
}
//If it is allowed to make a new point, it adds it to the open list.
if( make )
{
int gScore = manhattan( start.getPos(), Coord( curX, curY ) );
int hScore = manhattan( end.getPos(), Coord( curX, curY ) );
int tileCost = grid[curX][curY];
int fScore = gScore+hScore+tileCost;
open.push_back( new Point( curX, curY, fScore, cur ) );
}
}
}
//It then pushes back the current into the closed set as well as erasing it from the open set.
closed.push_back( cur );
open.erase( open.begin() );
//Heapsort works, guranteed. Not sure if it's a stable sort, though. From what I can tell that shouldn't matter, though.
open = heapsort( open );
}
std::vector<Coord> path;
if( error )
{
return path;
}
//Reconstruct a path by tracing through the parents.
while( cur->getParent() != nullptr )
{
path.push_back( cur->getPos() );
cur = cur->getParent();
}
path.push_back( cur->getPos() );
return path;
}
无论如何!感谢您提前提供的帮助!如果您想给我一些有用的提示或任何其他很棒的帮助!非常感谢! :^)
最佳答案
我可以看到您正在尝试使对角线的价格更高:
int movCost = 10;
//If it is a diagonal, make it cost 14 instead of 10.
if( (y == -1 && x == -1)||
(y == 1 && x == -1)||
(y == -1 && x == 1)||
(y == 1 && x == 1))
{
movCost = 14;
//continue;
}
但是您实际上并没有在代码的其他地方使用
movCost
。相反,您的成本函数仅使用曼哈顿距离:
int gScore = manhattan( start.getPos(), Coord( curX, curY ) );
int hScore = manhattan( end.getPos(), Coord( curX, curY ) );
int tileCost = grid[curX][curY];
int fScore = gScore+hScore+tileCost;
解释了对角曲折路径:
顺便说一句,您的代码中还有另一个逻辑错误:在A *中,g成本应计算为从起点到当前节点的实际成本,而不是像使用
manhattan()
函数那样估算。您应该在打开和关闭集中节省成本以及积分。将来,您应该打开所有编译器警告,并且不要忽略它们。这将捕获容易遗漏的错误,例如未使用的变量。
关于c++ - A *寻路问题。编译但行为异常,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/33248410/