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;
}
反正！感謝您提前提供幫助！如果你想給我一些有用的提示或任何其他的幫助，那就太棒了！非常感謝！ ：^）
_「它的行爲真的很棘手」_不是對你正在觀察的行爲的很好的描述。也許你應該嘗試更具描述性，並且告訴我們你正在看到什麼樣的行爲，以及你正在期待什麼樣的行爲。 –