Cell iterator - Part 2 (Brain Dump)

Frustum culling

From what I gathered, the concept of hiding cells that are behind the closest ones is called Frustum Culling.

There's a few techniques used for this, but those involve pre-processing.

For the purpose of the NAPL engine, I'm trying to figure out how this can be applied to the grid system.

Basically, in a grid system, knowing that some cells are opaque, how can we determine cells that we don't need to calculate (given that items will be hidden).

Cell hiding procedure

To figure out what gets hidden by a single cell, we draw two lines, indicating the left edge and right edge of our vision.

Normally, we would draw those lines from a single point, but since we're calculating from a cell, and we can be anywhere within the cells, we look at the two spots that give the biggest range of vision.

As shown in the image below:

• Case A: One opaque block on the side 3 units away (green) seems to just hide just once cell every 3 units that we go further.
• Case B: An opaque block right in front of the player hides every cells behind it.
• Case A+B: As we can see, when we combine both cases, if we simply take the union of the hidden cells, that's not enough to cover all the cells actually hidden.

In frustum culling, it is sort of fine to not include every cells that can be hidden (as it doesn't cause any error visually), but they do take extra computing. So it's worth trying to figuring out a way to more accurately determine what cells are really hidden, when two blocks are collated next to each other.

Expanding block technique

One idea comes to mind.

• We start at the origin, and move further out (forward).
• As we encounter opaque blocks, we keep those in mind (as imaginary blocks).
• If an opaque block intersects with an imaginary block, we can expand that imaginary block. This could also cause two imaginary blocks to merge into one larger one.
• Every time we move further, we expand the size of the imaginary block. The rate of expansion depends on the position of that imaginary block's edges. In the example above, the imaginary block expands by 1/3 unit every time we move further.

When an imaginary block fully covers a cell, it means that cell is not visible, thus it is skipped from rendering.

Applying this in a ring pattern

Rather than go in one direction, we perform the operation outwards in all 4 directions, expanding a ring of imaginary blocks.

This should help determine the sprites that are hidden by closer cells... in theory. Some basic implementation might reveal whether or not this works...