Sims-style walls part 2: Flood fill

Question

A follow up to this post. I've ported all of it to Unity, and generally cleaned it up a little, but looking over the code, the code for flood filling is messy and repetitive. Here's a visual of how it works:

Here's the code that achieves this, with some minor comments:

    protected WallSegment readSegment(PackedPoint p, bool isX) => (isX ? map.wallsX : map.wallsZ)[p];

    protected void writeSegment(PackedPoint p, bool isX, WallSegment value) => (isX ? map.wallsX : map.wallsZ)[p] = value;

    protected struct WallPosition
    {
        public WallPosition(PackedPoint pp, bool isX, bool isFront)
        {
            this.pp = pp;
            this.isX = isX;
            this.isFront = isFront;
        }

        public PackedPoint pp;
        public bool isX, isFront;
        public int x { get { return pp.x; } set { pp.x = value; } }
        public int y { get { return pp.y; } set { pp.y = value; } }
        public int z { get { return pp.z; } set { pp.z = value; } }
    }

    private void floodFill()
    {
        Assert.isTrue(curPos.HasValue);
        WallPosition p = curPos.Value;
        WallSegment old = readSegment(p.pp, p.isX);
        Debug.Assert(old.exists);
        ushort mOld = (p.isFront ? old.front : old.back);
        ushort mNew = map.selectedMaterial;
        Debug.Assert(mOld != 0 && mNew != 0);

        // if the clicked segment is already the destination material, don't do anything
        if(mOld == mNew) 
            return;

        Queue<WallPosition> q = new Queue<WallPosition>();
        q.Enqueue(p);
        while(q.Count > 0)
        {
            p = q.Dequeue();
            old = readSegment(p.pp, p.isX);

            // this covers both the case where we've already painted it and the case where it's a different
            // material that we don't want to flood fill
            if((p.isFront ? old.front : old.back) != mOld)
                continue;

            // write the new segment data
            WallSegment @new = p.isFront ? new WallSegment(mNew, old.back) : new WallSegment(old.front, mNew);
            writeSegment(p.pp, p.isX, @new);

            // check if any of the 4 directions from this wall exist and are not blocked by intervening tiles
            // if so, enqueue those new positions. Note this means we will visit painted segments up to 4 times,
            // but since they will already have been painted, we won't do this part again
            WallPosition next = p; 
            if(goLeft(ref next)) 
                q.Enqueue(next);
            next = p; 
            if(goRight(ref next)) 
                q.Enqueue(next);
            next = p; 
            if(goUp(ref next)) 
                q.Enqueue(next);
            next = p; 
            if(goDown(ref next))
                q.Enqueue(next);
        }

        afterUpdate("Flood Fill Walls");
    }

    private bool goLeft(ref WallPosition p)
    {
        MapWalls wallsX = map.wallsX;
        MapWalls wallsZ = map.wallsZ;
        if(p.isX)
        {
            if(p.isFront) // decreasing X
            {
                if(wallsZ.exists(p.x,     p.y, p.z    )) {               p.isX = false;                    return true; }
                if(wallsX.exists(p.x - 1, p.y, p.z    )) { p.x--;                                          return true; }
                if(wallsZ.exists(p.x,     p.y, p.z - 1)) {        p.z--; p.isX = false; p.isFront = false; return true; }
            }
            else       // increasing X
            {
                if(wallsZ.exists(p.x + 1, p.y, p.z - 1)) { p.x++; p.z--; p.isX = false;                    return true; }
                if(wallsX.exists(p.x + 1, p.y, p.z    )) { p.x++;                                          return true; }
                if(wallsZ.exists(p.x + 1, p.y, p.z    )) { p.x++;        p.isX = false; p.isFront = true;  return true; }
            }
        }
        else
        {
            if(p.isFront) // increasing Z
            {
                if(wallsX.exists(p.x    , p.y, p.z + 1)) {        p.z++; p.isX = true;  p.isFront = false; return true; }
                if(wallsZ.exists(p.x    , p.y, p.z + 1)) {        p.z++;                                   return true; }
                if(wallsX.exists(p.x - 1, p.y, p.z + 1)) { p.x--; p.z++; p.isX = true;                     return true; }
            }
            else        // decreasing Z
            {
                if(wallsX.exists(p.x - 1, p.y, p.z    )) { p.x--;        p.isX = true;  p.isFront = true;  return true; }
                if(wallsZ.exists(p.x    , p.y, p.z - 1)) {        p.z--;                                   return true; }
                if(wallsX.exists(p.x    , p.y, p.z    )) {               p.isX = true;                     return true; }
            }
        }
        return false;
    }

    private bool goRight(ref WallPosition p)
    {
        MapWalls wallsX = map.wallsX;
        MapWalls wallsZ = map.wallsZ;
        if(p.isX)
        {
            if(!p.isFront) // decreasing X
            {
                if(wallsZ.exists(p.x    , p.y, p.z - 1)) {        p.z--; p.isX = false; p.isFront = true;  return true; }
                if(wallsX.exists(p.x - 1, p.y, p.z    )) { p.x--;                                          return true; }
                if(wallsZ.exists(p.x    , p.y, p.z    )) {               p.isX = false;                    return true; }
            }
            else          // increasing X
            {
                if(wallsZ.exists(p.x + 1, p.y, p.z    )) { p.x++;        p.isX = false; p.isFront = false; return true; }
                if(wallsX.exists(p.x + 1, p.y, p.z    )) { p.x++;                                          return true; }
                if(wallsZ.exists(p.x + 1, p.y, p.z - 1)) { p.x++; p.z--; p.isX = false;                    return true; }
            }
        }
        else
        {
            if(!p.isFront) // increasing Z
            {
                if(wallsX.exists(p.x - 1, p.y, p.z + 1)) { p.x--; p.z++; p.isX = true;                     return true; }
                if(wallsZ.exists(p.x,     p.y, p.z + 1)) {        p.z++;                                   return true; }
                if(wallsX.exists(p.x,     p.y, p.z + 1)) {        p.z++; p.isX = true;  p.isFront = true;  return true; }
            }
            else          // decreasing Z
            {
                if(wallsX.exists(p.x    , p.y, p.z    )) {               p.isX = true;                     return true; }
                if(wallsZ.exists(p.x    , p.y, p.z - 1)) {        p.z--;                                   return true; }
                if(wallsX.exists(p.x - 1, p.y, p.z    )) { p.x--;        p.isX = true;  p.isFront = false; return true; }
            }
        }
        return false;
    }

    private bool goUp(ref WallPosition p)
    {
        int x = p.x, y = p.y, z = p.z;
        MapWalls wallsX = map.wallsX, wallsZ = map.wallsZ;
        MapTiles tiles = map.tiles;
        bool wallAbove, tileAbove;
        if(p.isX)
        {
            wallAbove = wallsX.exists(x, y + 1, z);
            tileAbove = p.isFront ? tiles.exists(x, y + 1, z) : tiles.exists(x, y + 1, z - 1);
        }
        else
        {
            wallAbove = wallsZ.exists(x, y + 1, z);
            tileAbove = p.isFront ? tiles.exists(x, y + 1, z) : tiles.exists(x - 1, y + 1, z);
        }
        if(wallAbove && !tileAbove)
        {
            p.y++; 
            return true;
        } 
        return false;
    }

    private bool goDown(ref WallPosition p)
    {
        int x = p.x, y = p.y, z = p.z;
        MapWalls wallsX = map.wallsX, wallsZ = map.wallsZ;
        MapTiles tiles = map.tiles;
        bool wallBelow, tileBelow;
        if(p.isX)
        {
            wallBelow = wallsX.exists(x, y - 1, z);
            tileBelow = p.isFront ? tiles.exists(x, y, z) : tiles.exists(x, y, z - 1);
        }
        else
        {
            wallBelow = wallsZ.exists(x, y - 1, z);
            tileBelow = p.isFront ? tiles.exists(x, y, z) : tiles.exists(x - 1, y, z);
        }
        if(wallBelow && !tileBelow)
        {
            p.y--; 
            return true;
        } 
        return false;
    }

I'm looking less for code style/spacing/braces suggestions (I happen to like the way I've lined stuff up since it helps with debugging and spotting patterns), and more for algorithmic suggestions.

I'm mostly worried because I'm considering adding diagonal walls. That will suddenly bloom the left/right logic from 24 cases (2 wall arrays * 3 directions the paint can go * 2 for front and back * 2 for left and right) to 112 cases (4 wall arrays * 7 directions the paint can go * 2 for front and back * 2 for left and right), at which point it might be simpler to generate the code with a text template or something.

---

EDIT: To help focus the discussion on the algorithm instead of the formatting, I've run auto-format on it. I'm not going to change the formatting in my version, but if you find it easier to read this way, here you go. I'm looking for feedback on how to simplify or improve the actual code, not opinions on what style/spacing different people prefer.

    protected WallSegment readSegment(PackedPoint p, bool isX) => (isX ? map.wallsX : map.wallsZ)[p];

    protected void writeSegment(PackedPoint p, bool isX, WallSegment value) =>
        (isX ? map.wallsX : map.wallsZ)[p] = value;

    protected struct WallPosition
    {
        public WallPosition(PackedPoint pp, bool isX, bool isFront)
        {
            this.pp = pp;
            this.isX = isX;
            this.isFront = isFront;
        }

        public PackedPoint pp;
        public bool isX, isFront;

        public int x
        {
            get { return pp.x; }
            set { pp.x = value; }
        }

        public int y
        {
            get { return pp.y; }
            set { pp.y = value; }
        }

        public int z
        {
            get { return pp.z; }
            set { pp.z = value; }
        }
    }

    private void floodFill()
    {
        Assert.isTrue(curPos.HasValue);
        WallPosition startPosition = curPos.Value;
        WallSegment oldSegment = readSegment(startPosition.pp, startPosition.isX);
        Debug.Assert(oldSegment.exists);
        ushort oldMaterial = startPosition.isFront ? oldSegment.front : oldSegment.back;
        ushort newMaterial = map.selectedMaterial;
        Debug.Assert(oldMaterial != 0 && newMaterial != 0);

        // if the clicked segment is already the destination material, don't do anything
        if(oldMaterial == newMaterial)
        {
            return;
        }

        Queue<WallPosition> q = new Queue<WallPosition>();
        q.Enqueue(startPosition);
        while(q.Count > 0)
        {
            WallPosition p = q.Dequeue();
            oldSegment = readSegment(startPosition.pp, startPosition.isX);

            // this covers both the case where we've already painted it and the case where it's a different
            // material that we don't want to flood fill
            if((startPosition.isFront ? oldSegment.front : oldSegment.back) != oldMaterial)
            {
                continue;
            }

            // write the new segment data
            WallSegment @new = startPosition.isFront
                ? new WallSegment(newMaterial, oldSegment.back)
                : new WallSegment(oldSegment.front, newMaterial);
            writeSegment(startPosition.pp, startPosition.isX, @new);

            // check if any of the 4 directions from this wall exist and are not blocked by intervening tiles
            // if so, enqueue those new positions. Note this means we will visit painted segments up to 4 times,
            // but since they will already have been painted, we won't do this part again
            WallPosition next = startPosition;
            if(goLeft(ref next))
            {
                q.Enqueue(next);
            }

            next = startPosition;
            if(goRight(ref next))
            {
                q.Enqueue(next);
            }

            next = startPosition;
            if(goUp(ref next))
            {
                q.Enqueue(next);
            }

            next = startPosition;
            if(goDown(ref next))
            {
                q.Enqueue(next);
            }
        }

        afterUpdate("Flood Fill Walls");
    }

    protected bool goLeft(ref WallPosition p)
    {
        MapWalls wallsX = map.wallsX;
        MapWalls wallsZ = map.wallsZ;
        if(p.isX)
        {
            if(p.isFront) // decreasing X
            {
                if(wallsZ.exists(p.x, p.y, p.z))
                {
                    p.isX = false;
                    return true;
                }

                if(wallsX.exists(p.x - 1, p.y, p.z))
                {
                    p.x--;
                    return true;
                }

                if(wallsZ.exists(p.x, p.y, p.z - 1))
                {
                    p.z--;
                    p.isX = false;
                    p.isFront = false;
                    return true;
                }
            }
            else // increasing X
            {
                if(wallsZ.exists(p.x + 1, p.y, p.z - 1))
                {
                    p.x++;
                    p.z--;
                    p.isX = false;
                    return true;
                }

                if(wallsX.exists(p.x + 1, p.y, p.z))
                {
                    p.x++;
                    return true;
                }

                if(wallsZ.exists(p.x + 1, p.y, p.z))
                {
                    p.x++;
                    p.isX = false;
                    p.isFront = true;
                    return true;
                }
            }
        }
        else
        {
            if(p.isFront) // increasing Z
            {
                if(wallsX.exists(p.x, p.y, p.z + 1))
                {
                    p.z++;
                    p.isX = true;
                    p.isFront = false;
                    return true;
                }

                if(wallsZ.exists(p.x, p.y, p.z + 1))
                {
                    p.z++;
                    return true;
                }

                if(wallsX.exists(p.x - 1, p.y, p.z + 1))
                {
                    p.x--;
                    p.z++;
                    p.isX = true;
                    return true;
                }
            }
            else // decreasing Z
            {
                if(wallsX.exists(p.x - 1, p.y, p.z))
                {
                    p.x--;
                    p.isX = true;
                    p.isFront = true;
                    return true;
                }

                if(wallsZ.exists(p.x, p.y, p.z - 1))
                {
                    p.z--;
                    return true;
                }

                if(wallsX.exists(p.x, p.y, p.z))
                {
                    p.isX = true;
                    return true;
                }
            }
        }

        return false;
    }

    protected bool goRight(ref WallPosition p)
    {
        MapWalls wallsX = map.wallsX;
        MapWalls wallsZ = map.wallsZ;
        if(p.isX)
        {
            if(!p.isFront) // decreasing X
            {
                if(wallsZ.exists(p.x, p.y, p.z - 1))
                {
                    p.z--;
                    p.isX = false;
                    p.isFront = true;
                    return true;
                }

                if(wallsX.exists(p.x - 1, p.y, p.z))
                {
                    p.x--;
                    return true;
                }

                if(wallsZ.exists(p.x, p.y, p.z))
                {
                    p.isX = false;
                    return true;
                }
            }
            else // increasing X
            {
                if(wallsZ.exists(p.x + 1, p.y, p.z))
                {
                    p.x++;
                    p.isX = false;
                    p.isFront = false;
                    return true;
                }

                if(wallsX.exists(p.x + 1, p.y, p.z))
                {
                    p.x++;
                    return true;
                }

                if(wallsZ.exists(p.x + 1, p.y, p.z - 1))
                {
                    p.x++;
                    p.z--;
                    p.isX = false;
                    return true;
                }
            }
        }
        else
        {
            if(!p.isFront) // increasing Z
            {
                if(wallsX.exists(p.x - 1, p.y, p.z + 1))
                {
                    p.x--;
                    p.z++;
                    p.isX = true;
                    return true;
                }

                if(wallsZ.exists(p.x, p.y, p.z + 1))
                {
                    p.z++;
                    return true;
                }

                if(wallsX.exists(p.x, p.y, p.z + 1))
                {
                    p.z++;
                    p.isX = true;
                    p.isFront = true;
                    return true;
                }
            }
            else // decreasing Z
            {
                if(wallsX.exists(p.x, p.y, p.z))
                {
                    p.isX = true;
                    return true;
                }

                if(wallsZ.exists(p.x, p.y, p.z - 1))
                {
                    p.z--;
                    return true;
                }

                if(wallsX.exists(p.x - 1, p.y, p.z))
                {
                    p.x--;
                    p.isX = true;
                    p.isFront = false;
                    return true;
                }
            }
        }

        return false;
    }

    protected bool goUp(ref WallPosition p)
    {
        int x = p.x, y = p.y, z = p.z;
        MapWalls wallsX = map.wallsX, wallsZ = map.wallsZ;
        MapTiles tiles = map.tiles;
        bool wallAbove, tileAbove;
        if(p.isX)
        {
            wallAbove = wallsX.exists(x, y + 1, z);
            tileAbove = p.isFront ? tiles.exists(x, y + 1, z) : tiles.exists(x, y + 1, z - 1);
        }
        else
        {
            wallAbove = wallsZ.exists(x, y + 1, z);
            tileAbove = p.isFront ? tiles.exists(x, y + 1, z) : tiles.exists(x - 1, y + 1, z);
        }

        if(wallAbove && !tileAbove)
        {
            p.y++;
            return true;
        }

        return false;
    }

    protected bool goDown(ref WallPosition p)
    {
        int x = p.x, y = p.y, z = p.z;
        MapWalls wallsX = map.wallsX, wallsZ = map.wallsZ;
        MapTiles tiles = map.tiles;
        bool wallBelow, tileBelow;
        if(p.isX)
        {
            wallBelow = wallsX.exists(x, y - 1, z);
            tileBelow = p.isFront ? tiles.exists(x, y, z) : tiles.exists(x, y, z - 1);
        }
        else
        {
            wallBelow = wallsZ.exists(x, y - 1, z);
            tileBelow = p.isFront ? tiles.exists(x, y, z) : tiles.exists(x - 1, y, z);
        }

        if(wallBelow && !tileBelow)
        {
            p.y--;
            return true;
        }

        return false;
    }

However, if you're trying to follow what's actually going on with goLeft and goRight, though, I highly recommend the column view in the original code, since modifications to each variable are shown in a column. Each column of code in the test is aligned so each of the 24 cases is on a single line and laid out sort of like it would be on a spreadsheet or table. This helps in spotting patterns and understanding the differences between each of the 24 cases (each of the 24 cases is extremely similar).

Answer 1

I happen to like the way I've lined stuff up since it helps with debugging and spotting patterns

I do not necessarily reflect this opinion.

You use a lot of very short variable names for parameters that make your code difficult to understand. Remember that their names are picked by IntelliSense and shown to the user. If all he sees is p or pp it isn't of much assistance.

You also use the same names for different things and these are not consistent:

PackedPoint p
PackedPoint pp
WallPosition p

This is not very professional. You do however consistently use confusing names in all parts of the code:

WallSegment old = readSegment(p.pp, p.isX);    
ushort mOld = (p.isFront ? old.front : old.back);
ushort mNew = map.selectedMaterial;

You are asking about the algorithm but how should anyone understand it when he first needs to answer such questions as:

• old what?
• mOld & mNew - what-the-heck is m?

Queue<WallPosition> q = new Queue<WallPosition>();

• q of what?

and so on...

You cannot really expect anyone to improve your algorithm without them understanding it first and your code isn't helping with that. On the contrary. It looks like it was obfuscated.

I know it's easy to create a working solution because at the time of writing you understand every bit of it... other people don't.

All we see are some letters. If you don't use strong variable names they are meaningless to anyone but you... though in a couple of weeks you'll be where we are now, wondering, what's going on there and you'll understand what we are talking about ;-)

Answer 2

I'm not too familiar with graphic algorithms, so I'll leave that review to others. This is mostly a style review because you make many mistakes that IME will make it more difficult to maintain this code.

public PackedPoint pp;
public bool isX, isFront;

Don't make your fields public. General convention is that a field is a private implementation detail; anything that needs to be exposed to anything else is a property that can control write access.

---

if(goLeft(ref next)) 
    q.Enqueue(next);

You have good indentation, but please use braces. Braces are never optional in my book; I've seen enough bugs/confusion (i.e. a new programmer doesn't understand that you can only have one statement without braces) around them.

---

if(!p.isFront) // decreasing X
{
    if(wallsZ.exists(p.x    , p.y, p.z - 1)) {        p.z--; p.isX = false; p.isFront = true;  return true; }
    if(wallsX.exists(p.x - 1, p.y, p.z    )) { p.x--;                                          return true; }
    if(wallsZ.exists(p.x    , p.y, p.z    )) {               p.isX = false;                    return true; }
}

Now that is just plain messy. And it hides code on the screen; it took me a second to figure out what was going on here, and it will you too, when you come back to it next year. Write each statement on new lines like so:

if(!p.isFront) // decreasing X
{
    if(wallsZ.exists(p.x, p.y, p.z - 1))
    {
        p.z--;
        p.isX = false;
        p.isFront = true;
        return true;
    }
    if(wallsX.exists(p.x - 1, p.y, p.z))
    {
        p.x--;
        return true;
    }
    if(wallsZ.exists(p.x, p.y, p.z))
    {
       p.isX = false;
       return true;
    }
}

This is actually a good case for C# 7's pattern matching feature. I'm not as familiar with this feature as I would like, but it should look something like this:

switch (p)
{
    // syntax might be `case p when wallsZ.exists(p.x, p.y, p.z - 1)`:
    case wallsZ.exists(p.x, p.y, p.z - 1):
        p.z--;
        p.isX = false;
        p.isFront = true;
        return true;
    case wallsX.exists(p.x - 1, p.y, p.z):
        p.x--;
        return true;
    case wallsZ.exists(p.x, p.y, p.z):
       p.isX = false;
       return true;
}

---

int x = p.x, y = p.y, z = p.z;

Write those each on their own line. At first I thought that was a complicated initializer.

---

The reason there are style guidelines is because it allows you to skim your code and find what exactly happens at each point without reading it character by character and line by line. If, for example, I had never worked on this, but had to fix a bug on a certain special case involving one of the dimensions, I would have to read the code carefully to figure out where variables are declared and used. By the time I was done, I'd know the process, but I'd be so involved in the process, I would have a hard time seeing the algorithm.

If, on the other hand, you followed more standard guidelines, I'd be able to skim it and figure out the general algorithm and then look through the process to see where it deviated from the algorithm. I'd also be able to easily skip over sections of the process that were functioning correctly based on the expectations of the algorithm. This could speed up a bug fix from taking 5 hours to 5 minutes.