New environment WIP: Floating polar ice

I’ve always planned that some levels would take place on polar ice, floating at sea. The latest Unity Asset Store Madness Sale includes the Ceto Water system that I’d long thought I might use for the sea. However I already have another called “Realistic Water” so thought it was time to evaluate that to decide whether to buy Ceto (or another, possibly PlayWay).

Here’s the very first integration of water into Snowman Scuffle with floating polar ice.

Obviously there are plenty of things that need fixing, e.g:

  • Functional:
    • The “replace-on-floor-if-you-slip-beneath-it” function needs disabling.
    • The character controller doesn’t handle moving platforms yet!
  • Aesthetic:
    • the bloom’s blown out.
    • the sky-box needs rotating.
    • The water surface could do with more details (e.g. specular highlights).

But ignoring these, it’s actually not a bad first step. That moving platform one is probably most tricky but, compared to how bad I feared this would be, it’s barely noticeable! Once fixed, it should be good!

How good will fighting, CTF’ing, racing, etc on blocks of floating ice feel!  (I’m kind’a hoping the answer will be “great!” 😉 ) Let me know your thoughts!

Voxel LOD generation

LOD (Level of detail) now working for voxel *generation* as well as building.

Here’s a YouTube at full res for the LOD-lovers like me out there 😉

As discussed in the last post, the generation phase is deciding on the matrix (8x8x8 for LOD0) of numbers that comprises a voxel ‘ChunkData’ whereas the building phase is turning those numbers into a ‘Chunk’ with a ‘Mesh’ — a thing you can actually see and interact with.

This new work means:

  • LOD0 (white boxes) contain 512 floats and 128 triangles = unchanged.
  • LOD0i (yellow boxes) contain 512 floats but only 2 triangles = unchanged.
  • LOD1 (cyan boxes) contain 1 float and 2 triangles = the NEW bit!

You can see how that’s much less memory and much better performance — especially for covering *much* larger arenas!

Yep, open(er) world campaign mode, here we come!

p.s. As with most gamedev or even programming, this took a great deal of frustrating tweaking including upgrading Unity and several assets then creating a whole new way to investigate details about voxel spaces that are generated on threads.  I know, implementation details.  I’m happy to discuss and the answer will involve phrases like “Marching Cubes”, “Isovalues” and lots about “neighbours”.  Ask if you’re curious / suffering from insomnia 😛

Oh and there’s still plenty of work to do before someone asks “is it done yet”.  There’s a reason I don’t show the Snowmen moving around in it yet 😉

Looking further, TerraVol performance work, part 2

Hi!

This blog post is gonna be lots of deep code stuff to optimize the performance of TerraVol.  Why?  Well I’d like larger arenas for SnwScf!  Huh?  How do those relate?  Well the voxel snow system I use proecdurally generates snow.  A larger arena requires more snow coverage.  More snow coverage requires more system resources (CPU, memory, GPU).  However if we increase the efficiency of the system, we can reduce that increase and make the game run better!  The uber-goal here being a campaign mode that takes place on a wide open terrain with long view distances.  To do that, I’m introducing LOD (Level of Detail) generation — building fewer snow pieces that cover larger areas with fewer details (vertices) — they’ll be atop far mountains you never reach, etc so they just don’t need a gazillion vertices up there!  …well, until you visit them — then they’ll be all beautifully detailed!  This is a common optimization in games but isn’t part of the voxel engine I used — TerraVol — so I’m adding it piece at a time.

So, a quick introduction to voxels in TerraVol.

Chunks, Blocks and GameObjects — oh my!

A cubic section of the voxel space is called a Chunk which consists of a 8x8x8 grid of Blocks.  Each Chunk has a GameObject and, at the start of all of this, 4096 were created at level start and sat in the scene.  (Yes, they were originally all Active GameObjects!  I can’t imagine Unity thinks much of 4096 active GameObjects sitting in its scene when not actually needed!  I switched them to all be inactive to start with.)  When some snow is needed in an area, all the Chunks from the highest Chunk that’s ever been to the lowest that’s allowed are queued for ‘generation’ in a thread.  This does some mathematics to determine height, values are assigned to each Chunk’s Blocks (8x8x8 = 512) and left.  Another thread notices the values are ready but no mesh has been made so it goes through each column and builds a mesh for each Chunk therein.  These two phases “Generation” and “Building” conclude and you can see the Chunks — snow in my case — in the game.

First we’ll do some work on Building then we’ll do some work on Generating.  First however, as noted at the bottom of the last post, since we can’t apply the Unity Profiler here, we need to measure manually!

Measuring time

Chunks are built on threads (I use 4).  Before my introduction of LOD, the average time to build (not generate) was 0.6ms per Chunk (where 19 out of 20 Chunks really need no actual meshing since all Blocks within have the same value = all above or all below a surface!).  For LOD1 columns the average to build becomes 0.01ms per column — a 60 times improvement in load!  (since 1 Chunk at LOD0 needs 8×8 = 64 runs through Marching Cubes, etc whereas 1 Chunk at LOD1 needs 1 run through!)

If I introduce a LOD2 or LOD3 covering 2×2 and 3×3 Chunks respectively, the ‘1 Chunk’ call cost should drop to 0.0025 and 0.001!  At this point the overhead of queuing and locking will probably exceed my measurement ability!

Aside: Unfair?

An odd thing to note: BuilderThread-02 is taking about twices as long as the other 3 threads?!  I recall the dispatching is round-robin not single-pool.

To explain: when a Chunk needs building (turning from numbers into a mesh) the work is placed onto a queue-per-thread rather than all placed in a single queue that all threads take from.

I imagine the original author did this since it avoids lock contention at work-retrieval time and can reduce lock contention for the dispatching thread (since the lock it needs to take only has 1 thread vying for it vs. 4 in a single-pool approach).

It would seem ’02 is just getting more of the harder work!?  Odd.  Will this cause a problem?  Well, it will mean that 3 threads will be sitting idle when they could be doing work ’02 has been given.  This might mean things take slightly longer than they should.  What’s odd is that I’d expect it would average-out in the long run — but it’s always ’02!?  I ought to try a single-pool approach (where all work is taken from a single queue).

After introducing ChunkSimpleState the average for both LOD levels is 0.55ms per Chunk.  Now that looks bad since it’s an increase from 0.01ms however we’ve lost all extraenous queueings and meshings of Chunks that didn’t actually need them so this is pure building that needed to be done.  Although the per-Chunk time has gone up, the system as a whole ought to be faster!  It also paves the way for reducing the number of GameObjects the system uses.

Model vs. View

Now the original developer had obviously once thought to do this but hadn’t finished it.  The system does separate ‘data’ (a.k.a. Model) from ‘visualization’ (a.k.a. View) so a ‘ChunkData‘ represents that large block of space but has no visualization until meshed as a ‘Chunk’ — a MonoBehaviour with a static builder method that creates the GameObject and other associated Components (MeshFilter, MeshRenderer, MeshCollider).  As it stands, a pool of ChunkData are created and each associated with a Chunk at creation time — hence 4096.  I removed that immediate association and made it lazy, based on whether ChunkSimpleState indicates a given ChunkData actually needs a mesh!  Now a 20x20x20 grid of Chunks still needs 8000 ChunkData instances but likely only 400 Chunks!  (assuming no caves or overhangs.)

Of course when the pool is exhausted, each are created on-demand.  Given I wish to move all of this off to a separate thread shortly, I can’t be trying to create the Chunk (and its GameObject, etc) at use point (Unity doesn’t allow things affecting its internal systems to be done off its main thread).  Instead let’s add another pool and pull from that.  Now Chunks are returned to their pool and disassociated from the ChunkData.

Data efficiency and Model-View separation

Now recall that each Chunk consists of 8x8x8 Blocks?  To be more precise each ChunkData consists of 8x8x8 BlockData.  ChunkData and BlockData are classes — instances are associated when needed.

Aside: Packed?

It strikes me the BlockData might be better as a packed format, maybe a struct that would result in a cache-friendly array for ChunkData?  Obviously that ‘associating’ approach would need addressing.  I’ll probably come back to that.

For now, what concerns me — why we’re doing all of this in the first place — is increasing the draw distance for the voxel snow, largely by making the system more efficient, especially by introducing efficient LOD usage.  So at the moment, although we’ve now got LOD1 generating a greatly simplified mesh (e.g. 2×2 vertices for LOD1 rather than 8×8 for LOD0), that’s all in the Chunk (built mesh).  The ChunkData still has 8x8x8 BlockData.  For LOD1+, that’s not needed — we only need 1 BlockData at each ChunkData’s local coordinate (0,0,0).  So let’s see whether we can get generation time to only do Blocks that are needed!  Let’s measure first!

Actually when I went to measure and fix this, I found the generation code is neither optimal nor conducive to this new need.  It’s getting the ChunkData from the TerraMap (via a ThreadLocal cache I previously added) each inner step of a 3-layer deep for loop (loop y, loop x, loop z).  I previously fixed so we looped down y first in preparation for this (and in preparation for storing MaxY per Chunk2D — column).  Now we can clearly see each ChunkData only needs retrieving every 8 Blocks — the X & Z coords never affect which ChunkData we need since they’re only operating in a single column!  So I re-structured to only get a new ChunkData every 8 Blocks and then make the ChunkData’s direct methods to change Block values (rather than going through the TerraMap’s lookups each time).

After that change, times to generate in seconds/column with minHeight 20 becomes:

0.002568627 +
0.003196078 +
0.003450980 +
0.003176471 +
0.003803922 +
0.003578431 +
0.008921568 + <-- odd spike
0.003617647 +
0.003803922 +
0.003696078
====
Average: 0.0039813724

You may recall from the previous post that we’d got it down from 0.015 s/column to 0.005 s/column so this 0.001 s/column improvement (on my fast machine) is within measurement error bounds.  Still it’s not going the wrong direction; still might be something and, as highlighted above, it paves the way for the next big steps!

Generating LOD data

Next is generating at the LOD.  This means that:

LOD 0 columns: (minheight - minY) * blocks per Chunk * Y block per chunk * Y blocks per
 chunk
LOD 1 columns: (minheight - minY) * 1 * 1

For minHeight:20 and minY:-3, that’s:

LOD 0 columns: 23 * 8 * 8 * 8 = 11776
LOD 1 columns: 23 * 1 * 1 * 1 = 23

That’s 11753 fewer loops, psuedo-random number calls for perlin values, etc and 11753 fewer BlockData assigned!

0.002441176 + LOD0
0.003137255 + LOD0
0.002166667 + LOD0
0.000784313 + mixed
0.000970588 + LOD1
0.000862745 + LOD1
0.000745098 + LOD1
0.000941176 + LOD1
0.001000000 + LOD1
0.000941176   LOD1
====
Average: 0.0013990194 s/column for both

BUT just the LOD1 values:
Average: 0.0009101305 s/column at LOD1

 

That’s a 30x improvement!  Super!

Now admittedly there’s still some work to do since the boundary between LOD0 and LOD1 now looks a little odd — the LOD0 building code is probably looking for values along the LOD1 boundaries.  Unless I can contrive a cheat, I might need to generate the edge values for LOD1.  Hmm… perhaps a new LOD0i for columns on the interface between LOD0 and LOD1 which does this (or probably build at LOD1 but generate at LOD0 since it’ll make the code much cleaner).

Well, off to a BBQ this afternoon so I’ll schedule this to post later in case I forget.  Maybe inspiration will strike while I’m wolfing down hog roast and chit-chatting with people IRL!

p.s. Nope, decided to go with LOD0i 🙂

3 times increase in voxel generation speed

TerraVol’s procedural terrain generation is thrashing its internal ChunkData cache!

The loops are ordered:

  1. outside: work across X & Z
  2. inside: down Y!

But this means every 8 Blocks done (SIZE_Z), another ChunkData must be found (flushing the cache) and that repeats 8×8 = 64 times for a single Chunk2D column!  Better would be going down Y as outer loop and across X & Y as inner loops.  This should give 512 hits before a new ChunkData must be found.

Let’s measure performance before and after.

This is all done in threads so we’ll need thread-local stopwatches that, in a lock, add their value to a global and increases a numDone count.  Periodically lock, average, dump and clear.

Timing results before:

With minHeight 1.4 (default in PlayerSetupArena):

0.0001 seconds/column  = not terrible but just about the *best* case possible — barely 3 chunks high!

With minHeight 20:

 0.004490196+
 0.006598039+
 0.009725491+
 0.01311765 +
 0.02141177 +
 0.01319608 +
 0.02912745 +
 0.02162745 +
 0.01719608 + (note worryingly increasing!)
 ===
 Average: 0.01516

After (still minHeight 20):

 0.003186275 +
 0.004343137 +
 0.006480392 +
 0.004676471 +
 0.007215686 +
 0.004666667 +
 0.00472549  +
 0.008745098 +
 0.00472549  +
 0.004921569 +
 ===
 Average: 0.00537

I make that roughly a 3 times improvement!  Real-time use shows FPS now much closer to being pegged at 60!

This also paves the way to my next optimization which should drastically reduce the load on both the Builder threads *and* (most importantly) the Unity Main Thread!  (all this will improve the local-multiplayer game but, more importantly, make the campaign able to use much wider areas of voxel snow!)

Before that, a quick aside: a further improvement might be retrieving the ChunkData outside the X,Z loops since they’re the same for all X & Z for a given Y!  It’s cached (threadlocal) but it’s 4 deep in method calls and involves some struct allocations, etc that just aren’t needed.  Think I’ll leave for now but…

The difficulty here is that, since this is all threaded code, I cannot profile it!

I’ll repeat: No profilability!  Unprofilable!  Profligate!  (check it)  Gah!

Unity’s profiler doesn’t record data for anything but the Unity Main Thread!  (which it can do excellently btw and also does awesome things for GPU, memory (better coming), etc.)  Furthermore since Unity isn’t Microsoft’s .Net runtime, one cannot apply Visual Studio (or others aimed at MS’).  As such, one’s reduced to personal timing tests like my Stopwatch use here.  That requires knowing where potential problems might be!  Recalling that “Premature optimization is the root of all evil“, this is a hard pill to unswallow!

By that I mean that, for gamedevs like me, we find it hard not to write things optimally as we go — but Knuth’s Adage means we must try to focus on code clarity (for maintainability).  That’s the hard pill.  Trying to unswallow it… yuck!  Even worse!

Just added all my remaining feedback points to the Unity Enhancement Request for Profiling MultiThreaded code.  Who’s with me!