- Home /
more efficient recursive spread
I'm currently making light simulation for my 2D Terraria-like game, when you place a light source it recursively spreads out to light up the area, however, this is horribly inefficient taking 341 method calls to spread a light source with a radius of 5. I'd like to only have to call the method the same number of times as there are blocks being lit. the reference code if here:
private void SpreadLight(LColor color, Vector2Int position, float intensity, byte radius, float distance)
{
LColor c = GetColor(position, color, distance, intensity, radius);
if (world.Map.CheckForBlock(position))
{
distance--;
}
else
{
distance -= 0.5f;
}
if(world.Map.GetTile(position).GetLight().color.a < c.a)
{
world.Map.SetLight(c, position);
}
if (distance > 0)
{
Tile tempTile0 = world.Map.GetTile(position + Vector2Int.down);
Tile tempTile1 = world.Map.GetTile(position + Vector2Int.left);
Tile tempTile2 = world.Map.GetTile(position + Vector2Int.right);
Tile tempTile3 = world.Map.GetTile(position + Vector2Int.up);
if (tempTile0 != null)
{
SpreadLight(c, tempTile0.Position, intensity, radius, distance);
}
if (tempTile1 != null)
{
SpreadLight(c, tempTile1.Position, intensity, radius, distance);
}
if (tempTile2 != null)
{
SpreadLight(c, tempTile2.Position, intensity, radius, distance);
}
if (tempTile3 != null)
{
SpreadLight(c, tempTile3.Position, intensity, radius, distance);
}
world.Map.GetChunk(world.Map.GetChunkCoord(position)).LightUpdated = false;
}
}
Perhaps instead of recursion, you can do a 2D loop over a square of size radius * 2 by radius * 2
centered at the light's position
, only updating tiles where the distance is <= radius
. Hope this helps!
The problem with that is that it won't always be a perfect square, it spreads farther where there aren't blocks blocking it.
Idea: Keep a Set of visited tiles. Before each recursion, check if the tile has been visited (i.e. - it is in the set). If not, add it to the set and call SpreadLight, else do nothing. This will make sure every tile only gets processed once.