I'm working on implementing a goal-based pathfinding. first step is to set a goal and calculate the shortest walkable distance between the goal and all points in the grid, using a brushfire algorithm.
I'm worried about two things here, readability and efficiency, since this is for an RTS game.
int[] GenerateHeatMap(IGrid grid, GridPoint goal)
{
var heatMap = new int[grid.Cells.Length];
var unexploredPoints = new List<GridPoint>();
var openPoints = new List<GridPoint>();
for (int i = 0; i < grid.Width; i++)
{
for (int j = 0; j < grid.Height; j++)
{
unexploredPoints.Add(new GridPoint(i, j));
}
}
var currentDistance = 0;
heatMap[grid.IndexOf(goal)] = currentDistance;
openPoints.Add(goal);
unexploredPoints.Remove(goal);
while (openPoints.Count > 0)
{
currentDistance++;
var newOpenPoints = new List<GridPoint>();
foreach (var currentPoint in openPoints)
{
for (int i = -1; i < 2; i++)
{
for (int j = -1; j < 2; j++)
{
var point = new GridPoint(currentPoint.x + i, currentPoint.y + j);
if ((i == 0 && j == 0) || !unexploredPoints.Contains(point) || newOpenPoints.Contains(point) || !grid.PointToCell(point).CanCross) continue;
heatMap[grid.IndexOf(point)] = currentDistance;
newOpenPoints.Add(point);
unexploredPoints.Remove(point);
}
}
}
openPoints.Clear();
openPoints.AddRange(newOpenPoints);
}
return heatMap;
}
For clarity here the definition of GridPoint
public struct GridPoint
{
public GridPoint(int x, int y)
{
this.x = x;
this.y = y;
}
public readonly int x;
public readonly int y;
}
What can I do to improve this?