0
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You are supposed to use BFS from each power source instead \$\endgroup\$
    – AturSams
    Commented Feb 21, 2014 at 11:26

1 Answer 1

1
\$\begingroup\$

Use BFS,here. You want to spread power from node A to all the tiles connected to it. Take the node that's spreading power as your initial then do your search to find out all the connected nodes to it.

If that sounds not so familiar, I found this tutorial for you. I quickly read through it and seems like a good fitting example for you.

Good luck :).

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for your help - I found out what BFS was from Arthur's post (was most familiar with A*) and had a go with it. The tutorial you've suggested seems more friendly though! \$\endgroup\$
    – Sando
    Commented Feb 25, 2014 at 13:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .