- oCount = openList 中的元素数
- cCount = closedList 中的元素数
我正在基于图块的环境中实现没有对角线移动的 A-star。当我尝试访问其中的最后一个元素时（当 oCount = 0 时使用 [oCount - 1]），每隔一段时间，就会在我的 openList 上引发“索引超出范围错误”。oCount 只有在 cCount 为 159 时才变为 0，这表明 closedList 已经使用了 openList 中的每个元素。这是一个例子：
cCount 变为 159 -> oCount 为 0 -> 检查 closedList[158] 中瓷砖周围的瓷砖 -> 没有有效的瓷砖 -> 返回 while 循环的开头 -> 尝试将 openList 中的最后一个元素移动到 closedList（错误）
这是我的 FindPath() 方法：（ 图块的网格位置基于其在数组中的位置（即 tile[0,0] 是左上角的图块）
//xBound + yBound = the bounding area with which the character can walk
public List<int> FindPath(Tile[,] tile, Vector2 xBoundary, Vector2 yBoundary, Vector2 startTile, Vector2 endTile)
{
//Initialize variables
List<Tile> openList = new List<Tile>();
List<Tile> closedList = new List<Tile>();
List<int> path = new List<int>();
int cCount = 0;
int oCount = 0;
tile[(int)startTile.X, (int)startTile.Y].PDir = 0; //PDir = direction to its parent tile
//Add starting tile to openList
openList.Add(tile[(int)startTile.X, (int)startTile.Y]);
//Set scores for starting tile
openList[0].G = 0;
openList[0].H = (int)Math.Abs(endTile.X - startTile.X) + (int)Math.Abs(endTile.Y - startTile.Y);
openList[0].F = openList[0].G + openList[0].H;
while (path.Count == 0)
{
oCount = openList.Count;
//Sort openList by decreasing F score
openList = Sort(openList);
//Move tile with lowest F score from openList to closedList
closedList.Add(openList[oCount - 1]); //ERROR OCCURS HERE
openList.RemoveAt(oCount - 1);
cCount = closedList.Count;
//Add valid surrounding tiles OR Alter valid existing tiles
//----------------------------------------------------------------------------------------------
for (int a = -1; a < 2; a += 2) //[a = difference in grid x-position]
{
//If tile is walkable, not in closed list, and within set boundaries...
if (tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y].Collision == false
&& !closedList.Contains(tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y])
&& closedList[cCount - 1].X + a >= xBoundary.X && closedList[cCount - 1].X + a <= xBoundary.Y //Test if boundaries must be < or <=
&& closedList[cCount - 1].Y >= yBoundary.X && closedList[cCount - 1].Y <= yBoundary.Y)
{
//If tile not in open list...
if (!openList.Contains(tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y]))
{
//Add tile
openList.Add(tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y]);
oCount = openList.Count;
//Set parent direction
if (a == -1)
tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y].PDir = 1;
else if (a == 1)
tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y].PDir = 3;
//Calculate F, G and H
openList[oCount - 1].G = closedList[cCount - 1].G + 1;
openList[oCount - 1].H = (int)Math.Abs(endTile.X - openList[oCount - 1].X) + (int)Math.Abs(endTile.Y - openList[oCount - 1].Y);
openList[oCount - 1].F = openList[oCount - 1].G + openList[oCount - 1].H;
}
//otherwise, check if current path is better than the previous path that tile had...
else if (closedList[cCount - 1].G + 1 < tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y].G)
{
//Set new parent direction
if (a == -1)
tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y].PDir = 1;
else if (a == 1)
tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y].PDir = 3;
//Re-calculate G and H values
int g = closedList[cCount - 1].G + 1;
int h = (int)Math.Abs(endTile.X - tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y].X) + (int)Math.Abs(endTile.Y - tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y].Y);
//Set values to tile
tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y].G = g;
tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y].H = h;
tile[closedList[cCount - 1].X + a, closedList[cCount - 1].Y].F = g + h; //including f-value...
}
}
}
// Above for-loop repeated for [b = difference in y-position]
//----------------------------------------------------------------------------------------------
//If at endTile...
if (closedList[cCount - 1].Y == endTile.Y && closedList[cCount - 1].X == endTile.X)
{
path = PlotPath(tile, tile[(int)startTile.X, (int)startTile.Y], tile[(int)endTile.X, (int)endTile.Y]);
}
}
return path;
}
据我所知，这似乎是我的算法的问题
--
- 编辑 -
根据 user3444160 的要求，这是堆栈跟踪（我相信）：
Mini RPG (test1).exe!Mini_RPG__test1_.AI.FindPath(Mini_RPG__test1_.Tile[,] tile, Microsoft.Xna.Framework.Vector2 xBoundary, Microsoft.Xna.Framework.Vector2 yBoundary, Microsoft.Xna.Framework.Vector2 startTile, Microsoft.Xna.Framework.Vector2 endTile) Line 45 C#
Mini RPG (test1).exe!Mini_RPG__test1_.Character1.UpdateDecisions(Mini_RPG__test1_.Tile[,] tileArray) Line 106 + 0xa9 bytes C#
Mini RPG (test1).exe!Mini_RPG__test1_.Character1.Update(Microsoft.Xna.Framework.GameTime gameTime, Mini_RPG__test1_.Tile[,] tileArray) Line 69 + 0xb bytes C#
Mini RPG (test1).exe!Mini_RPG__test1_.Game1.Update(Microsoft.Xna.Framework.GameTime gameTime) Line 745 + 0x28 bytes C#
[External Code]
Mini RPG (test1).exe!Mini_RPG__test1_.Program.Main(string[] args) Line 15 + 0xb bytes C#