# Optimising a bool spread on a 2D Grid/List

I'm trying to work out a more efficient way of spreading a bool flag across a 2D tilemap, as the way I currently have it setup works, but has to run far too many times to work properly. This isn't a massive performance problem as the code doesn't run every tick, but it's still annoying as there must be a better way! Hopefully somebody on here can help...

At present, the game code grabs a map XML file and deserialises it into a List of "mapsquares" (simple little class that holds all the info about that square in memory, so it can be modified). This works great for most of what I want to do, but is causing an issue with "power spreading".

Each square that contains a building uses a powered/notpowered bool, with the idea that power spreads from the station along power lines to other buildings. If it's connected to the grid, it's powered.

However, trying to get this working properly is proving messy, I've already followed the advice on here and generated neighbouring tile co-ordinates for every square when first loading the map file, this is used for exploration, but I thought it would also do power spreading.

It kinda works:

public void RegeneratePower()
{
MapSquare msnsq = new MapSquare(0, Vector2.Zero);
MapSquare msssq = new MapSquare(0, Vector2.Zero);
MapSquare msesq = new MapSquare(0, Vector2.Zero);
MapSquare mswsq = new MapSquare(0, Vector2.Zero);

foreach (MapSquare ms in mapSquares)
{
if (ms.HasBuilding)
{
Vector2 msn = ms.North;
Vector2 mss = ms.South;
Vector2 mse = ms.East;
Vector2 msw = ms.West;

foreach (MapSquare msa in mapSquares)
{
if (msa.Location == ms.North) msnsq = msa;
if (msa.Location == ms.South) msssq = msa;
if (msa.Location == ms.East) msesq = msa;
if (msa.Location == ms.West) mswsq = msa;
}

if (msnsq.HasPower || msssq.HasPower || msesq.HasPower || mswsq.HasPower) ms.HasPower = true;

}
}
}


However, it has to be run multiple times to actually spread the power more than 1 square at a time - theoretically I might have to run it as many times as the length or height of the map to ensure it covers everything :(. I thought about using the .Reverse() command to change the List order, or using a different kind of construct instead of a list. What would be the best way of doing this?

Thanks.

• You are supposed to use BFS from each power source instead Commented Feb 21, 2014 at 11:26