У меня есть NPC, и у меня есть целевое местоположение для него. Я поместил свой алгоритм поиска пути A * в код. Это создало путь, но это ни в коем случае не идеальный путь и не сплоченный. Я написал эту статью несколько раз и столкнулся с той же проблемой.
Эта картинка должна показать результат моей проблемы: окончательный путь повсюду.
Мне кажется, что алгоритм находит связь между каждой плиткой на моей карте, а не находит лучший путь. Хотя я действительно не могу понять, где это происходит.
Для ясности я определяю плитки (квадраты) и их соседей, когда загружаю свою игровую сцену. Когда программа достигает GetAdjacentSquares использует эти результаты, чтобы найти допустимые плитки. Вы заметите, что путь их NPC не сосредоточен непосредственно на какой-либо из зеленых плиток.
List<Path> GetAdjacentSquares(Path p)
{
List<Path> ret = new List<Path>();
TileData tile = tManager.GetTileByCoords(new Vector2(p.x, p.y));
foreach (Vector2 t in tile.neighborLocs)
{
TileData n = tManager.GetTileByCoords(t);
if (n && n.tType == TileTypes.Houses || n.tType == TileTypes.Road)
{
ret.Add(new Path(p, n.tTileLoc.x, n.tTileLoc.y));
}
}
return ret;
}
int BlocksToTarget(Vector2 tileLoc, Vector2 targetLoc)
{
int final = (int)Mathf.Abs((tileLoc.x - targetLoc.x) * (tileLoc.x - targetLoc.x) + (tileLoc.y - targetLoc.y) * (tileLoc.y - targetLoc.y));
return final;`
}
bool DoesPathContain(List<Path> paths, Vector2 target)
{
foreach(Path p in paths)
{
if (p.x == target.x && p.y == target.y)
return true;
}
return false;
}
int LowestFScore(List<Path> path)
{
int lowest = int.MaxValue;
foreach(Path p in path)
{
if (p.f <= lowest)
lowest = p.f;
}
return lowest;
}
void GoHome()
{
Path current = null;
//target
Path destination = new Path(null, cData.houseLoc.x, cData.houseLoc.y);
//start
Path start = new Path(destination, transform.localPosition.x, transform.localPosition.y);
//start by adding the original position to the open list
List<Path> open = new List<Path>() { start };
List<Path> close = new List<Path>();
int g = 0;
while(open.Count > 0)
{
//get the square with the lowest F score
current = open.Last(p => p.f == LowestFScore(open));
//add the current square to the closed list
close.Add(current);
//remove it from the open list
open.Remove(current);
//if we added the destination to the closed list, we've found a path
if(DoesPathContain(close, cData.houseLoc))
break;
//The rest of the algorithm evaluates adjacent tiles
List<Path> adjacentTiles = GetAdjacentSquares(current);
g++;
foreach(Path tile in adjacentTiles)
{
Vector2 tileLoc = new Vector2(tile.x, tile.y);
//if this adjacent square is already in the closed list, ignore it
if (DoesPathContain(close, tileLoc))
continue;
if(!DoesPathContain(open, tileLoc))
{
//if this adjacent square is already in the closed list, ignore it
tile.g = g;
tile.h = BlocksToTarget(tileLoc, cData.houseLoc);
tile.parent = current;
//add it to the open list
open.Add(tile);
}
else
{
//test if using the current G score makes the adjacent square's F score
//lower, if yes update the parent because it means it's a better path
if (g+tile.h < tile.f)
{
tile.g = g;
tile.parent = current;
}
}
}
}
//foreach (Path p in close)
// Debug.Log(p.f + " ("+p.x+", "+p.y+")");
walkTo = close;
cData.isWalking = true;
}
`