1
我最近采取了刺探A *搜索算法。我以前尝试过没有用，但是这次我已经取得了一定的成功。它总是找到一条路径，除非它不能（明显），它通常接近最短路径。其他时候，它会在加入太多次的时候真正起作用，形成锯齿形，随机向错误的方向移动。这很奇怪。下面的截图here.A *寻路问题。编译，但行为奇怪
代码：
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;
}
反正！感谢您提前提供帮助！如果你想给我一些有用的提示或任何其他的帮助，那就太棒了！非常感谢！ ：^）
_“它的行为真的很棘手”_不是对你正在观察的行为的很好的描述。也许你应该尝试更具描述性，并且告诉我们你正在看到什么样的行为，以及你正在期待什么样的行为。 –