# A Brushfire algorithm to generate a distance map in a grid

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++)
{
}
}

var currentDistance = 0;
heatMap[grid.IndexOf(goal)] = currentDistance;
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;
unexploredPoints.Remove(point);
}
}
}
openPoints.Clear();
}
return heatMap;
}


For clarity here the definition of GridPoint

public struct GridPoint
{
public GridPoint(int x, int y)
{
this.x = x;
this.y = y;
}
}



What can I do to improve this?

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++)
{
}
}

return points;

}

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

}


you can also do something like this :

public class HeatMapGridPoints
{

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.

• I think you didn't understand my code. I'll edit my initial post to explain the brusfire algorithm. How it works is: set the goal as my start point in my grid, and give it a distance of 0 in my distance map (it's called heatmap but I think distance map is better) then I set that point as an "open" point. Then for each point in my open points I get all its neighbours, check if they're walkable and unexplored, set their distance in the heat map, and add them to the list of open points. Then I remove the open points I just treated, and repeat until there are no new open points. – user1747281 Feb 11 '20 at 8:09
• @user1747281 I understood your code, but don't know the brushfire algorithm except what you have in your code. What I was suggesting is expanding your code (as I suggested) would give you a better management. The idea is an easier way to access both functionalities, and a way to store the points instead of regenerating them every time you call GenerateHeatMap. – iSR5 Feb 11 '20 at 11:01