Deleting an item in the game world: detecting if an item supports other items

Question

I'm writing a 3D construction module similar to the how you build houses in the Sims. Users are able to build walls and floors (which also act as ceilings) on multiple floors (layers). This question needs a little background info:

I'm not using an physics, there is no gravity. I use the term floor/ceiling tile here interchangeably. Essentially all are floor tiles, ceiling tiles are just floor tiles on a higher layer.

I store the build data in a multi dimensional array like:

grid[layer][row][column][position]

The layer represents the layer (ground floor, 1st floor etc..). The row and columns make up the grid. The position can hold any number of 3 positional values, namely:

• 0 : wall on west side of cell
• 1 : wall on south side of cell
• 2 : ceiling

So for example, a south wall on the row/column 2/4 on layer 3 would looks like:

grid[3][2][4][0=>null,1=>item,2=>null]

This works great, and it's easy to write functionality to check if a item can be placed at any position (by looking at neighbouring cells, layers below etc...)

Here is the actual problem and question:

I'm writing functionality to delete items within the game world. The rules by which I decide if something can be deleted are what you would expect in real life:

• Any item that's not on the ground floor needs something else supporting it

So for the following examples:

Only 1 of the 2 blue tiles adjacent to the red tile could be deleted

The red tile cannot be deleted because the wall connected to it would no longer have a support.

Walls are simple enough, I just check nothing is in the same row/col above them (since it would only be another wall or ceiling). It's the floor/ceiling tiles that are difficult.

It's easy enough to check if an item has neighbouring items, or if is supported by a wall below, but I can't seem to find an efficient way to do the checks if, for example, a ceiling tile has many neighbouring tiles that it supports:

VS those same neighbouring tiles, but they are supported by another item:

I thought maybe I should be storing the information about which other items support the current item during placement, but that just feels like moving the same complexity to another part of the code.

Is there and algorithm or concept that I could use/adapt to do the checks?

Answer 1

You can run a breadth-first search from the ground, and each time you encounter a new piece, you mark it with an integer distanceToGround equal to the current generation of the search. (So objects directly touching the ground get marked with a 1, those touching an object directly touching the ground get marked with a 2, etc...)

Then when you want to delete an object, you check the distanceToGround value of the object to remove and all of its neighbours. If all the neighours have an equal or lower distanceToGround, you can remove the object safely - none of the neighbouring objects' paths to the ground could go through this piece or they'd have a higher number.

If you do find an object with a higher distanceToGround, then you'll need to verify it has an alternate path available. Do a search from that object (excluding the object you want to remove), looking for another one with a lower distanceToGround than the neighbour you started from.

If you find one, then this object has an alternate path to the ground through this alternate root (we'll come back to it later). If you can't find anything lower without going through the object to remove, then it can't be removed without stranding some parts.

When you do remove the object, you'll need to update the distanceToGround numbers for any objects downstream from the alternate roots we identified in our searches, so that the invariant holds for the next time we want to test an object removal.

Answer 2

First you'd need to check if the object has any neighbors. If not, it can be deleted.

If the object does have neighbors, you'll need to check each of its neighbors and see if they ALL touch the ground. If they do, the object can be deleted.

If one of the neighboring objects does not touch the ground, you'll need to check if it can be deleted using the same rules as above.

It should come out to something like this. I added the alreadyChecked to avoid causing an infinite loop resulting in a StackOverFlowException You'd call this by passing the object you want to delete for objToDelete and null for alreadyChecked. I'll continue editing as I keep thinking it over.

public bool CanDelete(GameObject g, ref List<GameObject> alreadyChecked)
{
    if (objToDelete.Neighbors.Count == 0) 
        return true;

    if (alreadyChecked == null)
        alreadyChecked = new List<GameObject>();

    bool allCanBeDeleted = true;
    foreach (GameObject n in objToDelete.Neighbors)
    {
        if (alreadyChecked.Contains(n)
            continue;

        alreadyChecked.Add(n);

        if (!n.touchesGround)
            if (!CanDelete(n, alreadyChecked))
            {
                allCanBeDeleted = false;
                break;
            }
    }  
    return allCanBeDeleted;      
}