A Brushfire algorithm to generate a distance map in a grid

Question

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?

Answer 1

I would suggest to implement a HeatMapGridPoints class and inside this class, create two separate methods for GetUnexploredPoints and GetOpenPoints which will return list of GridPoint. This way, you can expand and also reuse the HeatMap. Also, it would be more readable than just gathering them into one method.

Example :

public class HeatMapGridPoints
{

    public IList<GridPoint> GetUnexploredPoints(IGrid grid)
    {
        var points = new List<GridPoint>();

        for (int i = 0; i < grid.Width; i++)
        {
            for (int j = 0; j < grid.Height; j++)
            {
                points.Add(new GridPoint(i, j));
            }
        }

        return points;

    }


    public IList<GridPoint> GetOpenPoints(IGrid grid, GridPoint goal)
    {
        // rest of the code 
    }


}

you can also do something like this :

public class HeatMapGridPoints
{
    private readonly IGrid _grid;

    private readonly GridPoint _gridPoint;

    public IList<GridPoint> OpenPoints { get; private set; }

    public IList<GridPoint> UnexploredPoints { get; private set; }



    public HeatMap(IGrid grid, GridPoint goal)
    {
        _grid = grid;

        _gridPoint = goal;

        OpenPoints = GetOpenPoints(); 

        UnexploredPoints = GetUnexploredPoints();
    }


    private IList<GridPoint> GetUnexploredPoints()
    {
        ...
    }


    private IList<GridPoint> GetOpenPoints()
    {
        ...
    }


}

usage :

var heatMap = new HeatMapGridPoints(grid, goal);

foreach(var point in heatMap.OpenPoints)
{
    ....
}

this would make it much easier to maintain and also more readable.