CODEWITHSUNDEEP
c#algorithmoptimization
manabreak
manabreak

Reputation: 5597

Finding the minimum amount of walls

I'm making a game where the walls are made of square blocks. The walls are placed on a two-dimensional grid, like this:

[X][X][X][X]
[ ][X][ ][ ]
[ ][X][ ][ ]
[ ][X][ ][ ]

Now, as I'm optimizing my collision detection, it helps to reduce the wall count to the bare minimum. In the above case, there is seven wall blocks, but only two walls if the blocks are combined. I'm having difficult time coming up with an optimal solution for finding these combined walls and get varying results depending on which block the search starts (the blocks are stored in an unordered list, the order comes from the order in which they were laid in an editor). Any thoughts on how to solve this? It should be pretty rudimentary stuff, but, y'know, it's friday and I can't function correctly. :)

Here's my sub-optimal code at the moment, it basically does two checks, both for horizontal and vertical "continuity" and then checks which one is better. It also stores the "already handled" blocks of walls so they won't be recognized twice, but this of course makes it go funky in crossing points.

public void CreateCollidersForExport()
{
    List<Wall> handledWalls = new List<Wall>();

    foreach (Wall w in walls)
    {
        if (handledWalls.Contains(w)) continue;
        handledWalls.Add(w);

        // Search how many walls there is horizontally
        Vector3 horizontalCenter = new Vector3(w.X, w.Y, w.Z);
        List<Wall> tmpWallsHorizontal = new List<Wall>();
        tmpWallsHorizontal.Add(w);
        foreach (Wall other in walls)
        {
            if (handledWalls.Contains(other) || tmpWallsHorizontal.Contains(other)) continue;
            bool canAdd = false;
            foreach (Wall _w in tmpWallsHorizontal)
            {
                if (other.X == _w.X + Wall.size && other.Y == _w.Y && other.Z == _w.Z)
                {
                    canAdd = true;
                    horizontalCenter.X += Wall.size / 2;
                    break;
                }
                else if (other.X == _w.X - Wall.size && other.Y == _w.Y && other.Z == _w.Z)
                {
                    canAdd = true;
                    horizontalCenter.X -= Wall.size / 2;
                    break;
                }
            }

            if (canAdd)
            {
                tmpWallsHorizontal.Add(other);
            }
        }

        // Search how many walls there is vertically
        Vector3 verticalCenter = new Vector3(w.X, w.Y, w.Z);
        List<Wall> tmpWallsVertical = new List<Wall>();
        tmpWallsVertical.Add(w);
        foreach (Wall other in walls)
        {
            if (handledWalls.Contains(other) || tmpWallsVertical.Contains(other)) continue;
            bool canAdd = false;
            foreach (Wall _w in tmpWallsVertical)
            {
                if (other.X == _w.X && other.Y == _w.Y && other.Z == _w.Z + Wall.size)
                {
                    canAdd = true;
                    verticalCenter.Z += Wall.size / 2;
                    break;
                }
                else if (other.X == _w.X && other.Y == _w.Y && other.Z == _w.Z - Wall.size)
                {
                    canAdd = true;
                    verticalCenter.Z -= Wall.size / 2;
                    break;
                }
            }

            if (canAdd)
            {
                tmpWallsVertical.Add(other);
            }
        }

        if (tmpWallsHorizontal.Count > tmpWallsVertical.Count)
        {
            // tmpWallsHorizontal has the longest "wall" now
        }
        else if (tmpWallsVertical.Count > tmpWallsHorizontal.Count)
        {
            // tmpWallsVertical has the longest "wall" now
        }
        else
        {
            // Both ways are the same length
        }
    }
}

Upvotes: 2

Views: 133

Answers (1)

Frerich Raabe
Frerich Raabe

Reputation: 94319

I'd try to treat this as a form of flood fill. The idea is that you walk over ever cell of the grid: every time you hit a 'wall' you start a flood fill, except that the flood fill only works on a single axis (so instead of flooding int o all four directions you either only go up/down or left/right).

Assuming you have your initial grid, and start iterating the cells left to right, top to bottom:

[X][X][X][X]
[ ][X][ ][ ]
[ ][X][ ][ ]
[ ][X][ ][ ]

You start with the top-left cell, notice it's a wall, start flooding. Since you can only flood to the right, you do a horizontal flood. You end up covering the area marked with '1' and memorize the area in a list:

[1][1][1][1]                  0/0 -> 3/0
[ ][X][ ][ ]
[ ][X][ ][ ]
[ ][X][ ][ ]

You move on, eventually hit the wall in the second row. You cannot flood left (no wall), you cannot flood up (already covered), you cannot flood right (no wall), but you can go down - so you do a vertical flood:

[1][1][1][1]                  1: 0/0 -> 3/0
[ ][2][ ][ ]                  2: 1/1 -> 1/3
[ ][2][ ][ ]
[ ][2][ ][ ]

And now you're done. In this version, ever 'X' is always only part of one wall. So if you had

[ ][X][ ][ ]
[X][X][X][X]
[ ][X][ ][ ]
[ ][X][ ][ ]

you would have three walls:

[ ][1][ ][ ]                  1: 1/0 -> 1/3
[2][1][3][3]                  2: 0/1 -> 0/1
[ ][1][ ][ ]                  3: 2/1 -> 3/1
[ ][1][ ][ ]

If you allow flooding 'X' cells covered by other walls, you could have just two:

[ ][1][ ][ ]                  1: 1/0 -> 1/3
[2][*][2][2]                  2: 0/1 -> 3/1
[ ][1][ ][ ]
[ ][1][ ][ ]

The '*' denotes a cell covered by two walls.

Upvotes: 1

Related Questions