Flowing Water in Byte Array based Terrain

Question

I am using a byte array to describe the terrain in my game, each byte value represents a different block type

I created a grid to simulate the water spread, I'm giving a byte value to the amount of water on a block and then I am spreading it by increasing the value of one block which causes it to spread to blocks that have less water, I made a little video of it to show: ( value 55 is a wall, 0 air, 1 to 4 water, its a top down perspective )

https://www.youtube.com/watch?v=SOmnejfmPe0

However I am having trouble finishing it, I dont want the water level to rise above 4, when a block that is already at value 4 goes to 5 I want it to flow through all the other blocks until all the contained water is at value 4. However with my current code if I set the condition so that the water flows no matter what if it has value of 4 or more it ends in infinite loop.

here is the current relevant code:

 public Vector3Int PosToCheck;
    public IEnumerator FlowRoutine(int x, int y, int z)
    {
        PosToCheck = KeepPosInBounds(new Vector3Int(x - 1, y, z));
        if ( GridArray[x,y,z] > GridArray[PosToCheck.x,PosToCheck.y,PosToCheck.z] + 1  && GridArray[PosToCheck.x, PosToCheck.y, PosToCheck.z] != 55)
        {
            GridArray[x, y, z] -= 1;
            GridArray[PosToCheck.x, PosToCheck.y, PosToCheck.z] += 1;

            yield return StartCoroutine(FlowRoutine(PosToCheck.x, PosToCheck.y, PosToCheck.z));
        }
        else
        {
            PosToCheck = KeepPosInBounds(new Vector3Int(x, y + 1, z));
            if (GridArray[x,y,z] > GridArray[PosToCheck.x,PosToCheck.y,PosToCheck.z] + 1  && GridArray[PosToCheck.x, PosToCheck.y, PosToCheck.z] != 55)
            {
                GridArray[x, y, z] -= 1;
                GridArray[PosToCheck.x, PosToCheck.y, PosToCheck.z] += 1;

                yield return StartCoroutine(FlowRoutine(PosToCheck.x, PosToCheck.y, PosToCheck.z));
            }
            else
            {
                PosToCheck = KeepPosInBounds(new Vector3Int(x + 1, y, z));
                if (GridArray[x,y,z] > GridArray[PosToCheck.x,PosToCheck.y,PosToCheck.z] + 1  && GridArray[PosToCheck.x, PosToCheck.y, PosToCheck.z] != 55)
                {
                    GridArray[x, y, z] -= 1;
                    GridArray[PosToCheck.x, PosToCheck.y, PosToCheck.z] += 1;

                    yield return StartCoroutine(FlowRoutine(PosToCheck.x, PosToCheck.y, PosToCheck.z));
                }
                else
                {
                    PosToCheck = KeepPosInBounds(new Vector3Int(x , y-1, z));
                    if (GridArray[x,y,z] > GridArray[PosToCheck.x,PosToCheck.y,PosToCheck.z] + 1  && GridArray[PosToCheck.x, PosToCheck.y, PosToCheck.z] != 55)
                    {
                        GridArray[x, y, z] -= 1;
                        GridArray[PosToCheck.x, PosToCheck.y, PosToCheck.z] += 1;

                        yield return StartCoroutine(FlowRoutine(PosToCheck.x, PosToCheck.y, PosToCheck.z));
                    }
                }
            }
        }

        UpdateAllButtons();

        yield return null;
    }

    public Vector3Int KeepPosInBounds(Vector3Int newPos)
    {
        if (newPos.x < 0) { newPos.x = XGridSize - 1; }
        if (newPos.y < 0) { newPos.y = YGridSize - 1; }
        if (newPos.z < 0) { newPos.z = ZGridSize - 1; }
        if (newPos.x >= XGridSize) { newPos.x = 0; }
        if (newPos.y >= YGridSize) { newPos.y = 0; }
        if (newPos.z >= ZGridSize) { newPos.z = 0; }

        return newPos;
    }

and this is the condition I was trying to add but it breaks before all available blocks are at 4, ( water gets caught in an infinite loop between 2 blocks that pass water to each other infinitely)

    if ((GridArray[x,y,z] > GridArray[PosToCheck.x,PosToCheck.y,PosToCheck.z] + 1 || GridArray[x, y, z]>=WaterCap) && GridArray[PosToCheck.x, PosToCheck.y, PosToCheck.z] != 55)

Would appreciate advice on how to tackle this problem, Thanks!

user_12636223 · Answer

Is this the behavior you are looking for?

Assuming you have a 2D grid of byte type, you can use DFS or BFS to achieve this. In my case, I made a Cell class having the Value property which when set, updates the cell's text and color automatically.

Next, I made a grid manager storing the 2D grid of Cells. The trigger function resides in the manager. Whenever I trigger a certain cell, It runs a DFS to update starting from this cell. The DFS logic has conditions to check for bounds and walls and also restricts the overflow of water.

void Trigger(int x, int y)
{
    bool[,] visited = new bool[yCount, xCount];

    for(int i=0; i= yCount) return;
    if (j < 0 || j >= xCount) return;

    if (visited[i, j]) return;

    // Mark as visited
    visited[i, j] = true;

    if (cells[i, j].Value == 55) // Its a wall
        return;

    if (cells[i, j].Value == 0)
    {
        // Needs 1 update and return
        cells[i, j].Value++;
        return;
    }

    // Restrict upto 4 if its water
    cells[i, j].Value = (byte) Mathf.Min(cells[i, j].Value + 1, 4);

    // Recursively call neighbouting cells
    DfsUpdate(i + 1, j, visited);
    DfsUpdate(i - 1, j, visited);
    DfsUpdate(i, j + 1, visited);
    DfsUpdate(i, j - 1, visited);
}

You can use BFS too but DFS works fine here and implementation is easier in case of DFS.

Edit:

It takes 72 clicks to fill the grid now. Check the bottom left to see the mouse click count.

I changed the code. Now when I click on a cell, if it is already 4 (filled), it finds for the nearest grid that's not completely filled and adds 1 to it else it fills itself. In the Update method, I iterate over the grid at a certain rate and check if there are any cells having a neighbor such that their water levels have a difference of two. I fill that cell and mark it as updated so that they don't get updated again in the current frame.

The grid update method is a simple BFS which adds 1 to the nearest non-filled neighbor if any exists.

In the update method, using a timer, whenever a certain delay is crossed, I iterate over the grid to even out the water level differences.

Here is the code.

void GridUpdate(int i, int j)
{
    bool[,] visited = new bool[yCount, xCount];
    Queue iQ = new Queue();
    Queue jQ = new Queue();
    iQ.Enqueue(i);
    jQ.Enqueue(j);

    while(iQ.Count > 0)
    {
        int si = iQ.Dequeue();
        int sj = jQ.Dequeue();

        if (!CheckBounds(si, sj)) continue;

        if (cells[si, sj].Value == 55) continue;

        if (cells[si, sj].Value < 4)
        {
            cells[si, sj].Value++;
            return;
        }

        // Up
        iQ.Enqueue(si - 1);
        jQ.Enqueue(sj);

        // Down
        iQ.Enqueue(si + 1);
        jQ.Enqueue(sj);

        // Left
        iQ.Enqueue(si);
        jQ.Enqueue(sj - 1);

        // Right
        iQ.Enqueue(si);
        jQ.Enqueue(sj + 1);
    }
}

void Update()
{
    timer += Time.deltaTime * 1000f;
    if (timer >= updateDelay)
    {
        timer -= updateDelay;
        bool[,] updated = new bool[yCount, xCount];

        for (int i = 0; i < yCount; i++)
        {
            for (int j = 0; j < xCount; j++)
            {
                if (updated[i, j] || cells[i,j].Value == 55) continue;

                if (CheckBounds(i-1, j) && !updated[i-1, j] && cells[i, j].Value - cells[i - 1, j].Value >= 2)
                {
                    updated[i - 1, j] = true;
                    cells[i - 1, j].Value++;
                    cells[i, j].Value--;
                }
                else if (CheckBounds(i+1, j) && !updated[i + 1, j] && cells[i, j].Value - cells[i + 1, j].Value >= 2)
                {
                    updated[i + 1, j] = true;
                    cells[i + 1, j].Value++;
                    cells[i, j].Value--;
                }
                else if (CheckBounds(i, j-1) && !updated[i, j-1] && cells[i, j].Value - cells[i, j-1].Value >= 2)
                {
                    updated[i, j-1] = true;
                    cells[i, j-1].Value++;
                    cells[i, j].Value--;
                }
                else if (CheckBounds(i, j+1) && !updated[i, j + 1] && cells[i, j].Value - cells[i, j + 1].Value >= 2)
                {
                    updated[i, j + 1] = true;
                    cells[i, j + 1].Value++;
                    cells[i, j].Value--;
                }
            }
        }
    }
}

// Checks if a given i and j are not out of bounds of the grid
bool CheckBounds(int i, int j)
{
    if (j < 0 || j >= xCount) return false;
    if (i < 0 || i >= yCount) return false;
    return true;
}

Hope this helps!

Flowing Water in Byte Array based Terrain

1 Answers