A* 寻路几乎不起作用
A* Path-finding is just barely not working
我有我的 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;
}
`
我了解到我正在从封闭列表中获取最终结果。一旦我访问了正确的列表,路径就被绘制出来了!
我有我的 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;
}
`
我了解到我正在从封闭列表中获取最终结果。一旦我访问了正确的列表,路径就被绘制出来了!