我最近试了一下 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-cost 应该计算为从开始到当前节点的实际成本，而不是像你使用 那样估计曼哈顿 () 函数。您应该在打开和关闭集中节省成本以及您的积分。
将来，您应该打开所有编译器警告，不要忽略它们。这将捕获容易遗漏的错误，例如未使用的变量。
关于c++ - A* 寻路问题。编译，但行为异常，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33248410/