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:
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:
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?