Dealing with occlusion in an isometric sandbox game

Imagine a 3D sandbox game like Minecraft with third-person isometric graphics. If the camera only moves in two dimensions, and doesn't rotate, then a large portion of the world will always be occluded e.g. caves, areas behind mountains and buildings, etc. Obviously this isn't acceptable.

I'm trying to figure out how such a game could deal with this issue while preserving certain properties: the world must be entirely buildable/destructible and must extend in some manner along all three axes. Other than that, nothing is off the table.

I can't think of any simple culling algorithm that wouldn't either leave too much occluded or needlessly cull things. Which features are visible where seems to be a very high level design issue. If you are underground, you don't want to see the ground above you at all. But some small objects you probably never want culled, even when standing behind them.

And it's not at all clear what you would want to do with medium-sized objects, like buildings... perhaps make them translucent when the player walks behind them. But how would such objects be classified? And how would you distinguish the outside of the building from the inside? You probably don't want the inside of buildings to become visible when you walk behind them.

If the player can place objects anywhere, what happens if they place an object behind an occluder? Is it now impossible to interact with this object without destroying the thing in front of it, even when the player is standing right next to it? What about important features on back-facing surfaces? Are they never rendered at all?

It seems to me that isometry is just not capable of practically representing arbitrary three dimensional architecture, which suggests that the game needs to be designed in such a way that arbitrary architecture can't be built. Rather, it needs to be constrained to some kind of 2.5D model, where occluded things simply cannot exist. But how could a world like that feel consistent and logical to the player while they dig and build in it?

-
I'm going to edit the question to try and make it clearer – jedediah Jan 21 '12 at 23:07

I'd say the reason you're asking the question in the way you have (i.e. not a single question but many smaller ones), is because you have various explicit requirements that you have not reconciled: culling what should be culled, not culling what shouldn't be culled, and using alpha where you need foreground objects to not obscure key gameplay objects in the midfield. I guess you're less-than-willing to start down a path that might not fit your exact requirements. But sometimes, experimentation is the only way to get rolling. Choose to implement ONE of these. To start with, draw EVERYTHING, just allow overdraw for now -- given a limited world height, even heavy overdraw should not grind your FPS too badly (unless you're writing in ActionScript or JavaScript, and the overdraw is major), because you're looking toward the ground, not toward some far horizon. Even so, I provide a solution for isometric occlusion culling below. Anyway, from drawing everything, you will find that it's much easier to simply move toward achieving your other two criterion. You need a base to experiment with.

Foreground alpha

I assume you don't want the player to be hidden behind walls. How about enemies? Items? Controls (including ones situated on back-facing walls)? I'll have to assume all, for the purposes of responding.

Whatever is directly between your ortho camera and any gameplay-critical entities, must be made transparent OR culled completely from the view.

For walls near to your player, simply make surface voxels transparent (never consider non-surface voxels for rendering). You need to determine the silhouette of the entire clump that would occlude, and render it only as a silhouette at a single alpha (say 10%). If you were to simply treat each voxel as being at a given alpha, their transparencies might combine to be so opaque so that you would hardly see the critical entities beyond them.

You furthermore mentioned the insides of buildings, which could equally be seen as other rooms (if eg. your game was in a dungeon environment). The best way to deal with this is to keep a list of bounding boxes describing other rooms, and use these for additional zone-based culling. This could be the same as, or separate from, your level chunks. I would recommend it be separate as chunks should ideally be based on a uniform grid in order to keep processing times uniform regardless of where in the world you are. Using non-uniform bounding boxes can mess with this.

Culling what is definitely occluded by opaque objects

Consider a standard isometric engine. Occlusion is often not explicitly handled, because the degree of occlusion is minimal enough in most cases that we can afford to ignore it. In your case, however, it is necessary to know what not to draw. This is a perfect application of the reverse painter's algorithm. Determine the lines of voxel "bases" closest to the lower edge of your screen. In each such "tile" along this line, there exists a column of voxels. Draw each voxel in this column, from the base point near the bottom of the screen, upwards. Proceed to the next row above it, and repeat, till you've drawn all rows in the scene. As for knowing what NOT to draw, this image represents the tile base positions on your screen (the bottoms of all voxels at sea level):

``````* * * * * * *
* * * * * *
* * * * * * *
* * * * * *  <- Second last row
* * * * * * * <- Baseline row
``````

Do you see how the second last row's voxel bases are offset from the baseline's? Every second row's tile centre lies exactly between the next and previous line's x-centres? Same thing, with graphics:

Because of this, the first (leftmost) tile column in the second-from-last line is only occluded if the first AND second tile columns in the baseline BOTH exceed the height of the column that lies behind/between them. If they are equal, then you won't see the sides of the voxel behind, but you will see it's top -- so it will still need to be drawn. If less than both, it is completely occluded.

This solution will not entirely eliminate overdraw (since you still need to draw a whole column even if only one of the two in front of it is occluding it), but it certainly will make a major difference. For complete elimination of overdraw at a per-pixel level, see below.

Dealing with overhangs / floating voxels shouldn't be too hard to figure out given the above.

-
Not sure if his question was about hiding stuff as much as revealing the stuff that is behind it (eg. the player, mobs, etc) and still be able to affect the "blocks" that are transparent. – Tor Valamo Jan 21 '12 at 19:27
Good point @TorValamo. I've updated. – Arcane Engineer Jan 21 '12 at 20:04
This is a sandbox game, so I don't know what's a wall, or a room, unless I come up with a heuristic for that. It's just a bunch of voxels. That's the problem. – jedediah Jan 21 '12 at 21:29
It's not a whole other question, it's exactly what I'm trying to ask here. – jedediah Jan 21 '12 at 22:04
@jedediah Creating anything procedurally or allowing players to create geometry is never straightforward. There has to be a sort of world manager in place to deal with matters like this. Specifying boundary zones is part of your world AI's job. But that is a whole other question. I think Tor and I have both tried to answer the one you asked. Furthermore it seems you're unwilling to experiment as I suggested. You will quickly enough see solutions if you do. – Arcane Engineer Jan 21 '12 at 22:05

I have considered this problem myself and the only solution I have been able to come up with is to allow rotating the camera (or more technically correct, the map).

This will let you see the player/items that are in range (by removing anything that is blocking your observer line of sight), and it also lets you interact with any item even if you are deep underground, because the things that are between you as the observer and the player is removed, so if you want to interact with any of the blank stuff, you just rotate the camera, and make the other side transparent instead.

I've thought of how to make this as unnoticeable (hassle-free) as possible, and one or two hotkeys near the wasd keys may be appropriate (C or V rotates the map 90 degrees, and as a result the wasd keys change orientation, but this is not noticeable, because "up" is still "up", even though internally the direction is a different one.)

-
+1 This occurred to me some years back. I've often wondered what the usability would be like in practice. – Arcane Engineer Jan 21 '12 at 21:00
A rotating camera gets you part way there, but you still have to cull some front-facing geometry, so that e.g. when you're underground, you don't see the surface. Along the line of site to the player, you can decide this fairly easily. But toward the edges of the screen, how do you decide what is "in front" of the player? In a game with pre-designed levels, you would want to constrain this to natural boundaries like the edges of walls. But for an arbitrary grid of voxels, how do you slice up the scene? – jedediah Jan 21 '12 at 21:42
@jedediah, As I stated, you could use bounding boxes to create zones. You have to start somewhere. An AI will have to be used, later, to decide where those zones begin and end. And no, that's not easy. Tor's just trying to answer the question you asked, which is about occlusion. We cannot answer every problem in your game design. As it is, this question pushes the boundaries of remaining focused. – Arcane Engineer Jan 21 '12 at 21:57
@jedediah Going with a 45 degree angle (that is, from each bottom corner to the middle of screen) is a decent solution of what could be unhidden. Of course this is totally project dependent. As to what shouldn't be transparent, you could have special objects which the rendering refuses to make transparent. There's always a way. – Tor Valamo Jan 21 '12 at 22:47
@TorValamo "There's always a way." So true. And prototyping goes a long way toward proof-of-concept. – Arcane Engineer Jan 21 '12 at 22:54