Hi again folks…

[WARNING: This is a crazy technical article. Pursue only if you’re mad]

As promised in my last post, here is a pretty technical article to show you the kind of problem I run into and to give you a hint on how I spend my days losing my hair. This one is a pretty complicated one and kept me occupied for the last 2 weeks, because it forced me to change a lot of things in the code of the game even if I though “no problem, I planned it well, everything’s gonna be okay”. How naïve…

The final goal is to have a continuous world without any loading time between zones.
Why an open world you may ask? Because, at the beginning, I set myself 3 major guidelines about my game:
– freedom
– humour
– oneiric world

And every choice I make at any step of the development follows these 3 “rules”. This ensures me that the game, even if not perfect, will have some coherent content and some kind of art/feel direction. Thus… having an open world helps a lot for the freedom feel. Plus it’s a crazy challenge, and I’m a crazy guy :).

As you may have seen in the demos and videos, the world of my game is a big ocean with various islands on it (yes, just like Zelda Windwaker). At some point the player will have the ability to travel on the ocean (on a turtle’s back 😉 ) and can go pretty much everywhere he wants. This means islands/levels must be loaded dynamically according to the player’s position/direction in the world.

I – Unity Limits (Yes I finally reached some)

I use Unity to create my game and (luckily?), Unity provides 2 functions to load a new level “in the background” so that you don’t notice any lag:

• LoadLevelAsync: loads a new level in background. Once loaded, the new level replaces the current one.
• LoadLevelAdditiveAsync: Same thing, but adds the content of the new level to the current one. This is obviously what I’m going for here.

But this is theoretical only. Unity is a great software, but some points are still under heavy development. These ones are. And it impacts the game in a way I didn’t think about: after using LoadLevelAdditiveAsync, all the IA agents of the new level crash.

This occurs because the IA uses a “NavMesh” (= Navigation Mesh) to represent the walkable areas in the level. The IA can only walk/move/search a path on the NavMesh. Problem is, Unity only authorizes 1 NavMesh to be loaded in memory at a time, and you can’t load a NavMesh using LoadLevelAdditiveAsync. Technical limitation. I can’t argue.

 

II – Time for Hacks

I found a hack on a forum post : using LoadLevelAsync (which actually loads the new NavMesh in memory) and tagging all objects of the current level not to be destroyed (a cool feature I discovered while reading the forums. Great community by the way).
This is supposed to do the trick but it rises 2 more problems:

• LoadLevelAsync is not actually a background task. It really freezes the game for a few ms, and it IS visible.
• Cool, the NavMesh of the new level is OK, and the IA too, but what happens if I go back towards the 1st level (which is still visible but with no corresponding NavMesh and no IA)? If I wan’t to reload only the NavMesh of the 1st level… I can’t without reloading the whole level, which may result in objects flickering during the reload.

At this point, I’m faced with Unity bugs I can’t fix and I’m left with a few options:

• Wait for a bug fix from Unity about the NavMesh+LoadLevelAdditiveAsync problem. I don’t think it will come before I release my game, the Unity guys have loads to do and this is not a priority.
• Use a 3rd-party library. I must find one that does NavMesh generation and path-finding, is real-time, and dynamically loads levels.
• Recode everything that is not working. Not impossible (I already coded a real-time A* path-finding algorithm for World of Ninjas, but it works only on a 2D grid)… but hardly realistic. Good guys spent months developping systems much more reliable than anything I could do in a few weeks.
• Find another workaround. I didn’t find any when I spent a few hours on forums and faqs.
• Give up. This is a serious option. I can perform the navigation part on a 2D map where you click where you wan’t to go. All islands would be accessible too, and it won’t change the gameplay on each island. Maybe I’ll even consider that if I achieve to create  a “real” open world but it’s not fun to explore.

But before giving up I heard a lot of good things about a 3rd-party library implementing the classical A* path-finding algorithm: Aron Granberg A* path-finding library.

 

III – A new lib: A*

Cool! A new library full of promises. But before commiting to this, I have to test that every basic IA feature already provided by Unity is implemented in this library.

I start with the free version of the library, which means… there is no NavMesh generation available (only on the full 100$ version). Of course, I can buy the full version, but I’m not sure this library solves my “dynamic loading” problem. I must first test it on this specific point.

I know that Unity can generate NavMeshes (I used them before). So I write a script to convert Unity NavMeshes to the library NavMesh format, which enables me to use the library path-finding on NavMeshes from my real levels.

But there is already a problem: the path-finding behaves weirdly and sometimes IA makes huge detours to get to some point. It seems to be a known issue… This is because of the NavMesh topology: a “good” NavMesh for the A* library is supposed to have some kind of grid pattern on it to avoid big triangles next to small triangles. Unluckily, NavMesh generation in Unity doesn’t expose some “grid size” or “max edge length” parameters, which means I can’t test that the path-finding behaves correctly with a “good” NavMesh.

IV – Another new lib : RAIN

I heard about another path-finding library: RAIN. Totally Free, but sparse documentation. I tested it mainly to assess its NavMesh generation algorithm and hurrah! It can generated “grid”-NavMeshes. So I write another script to convert RAIN NavMeshes to A* NavMeshes, with very few documentation… Tough time! And… I get a few errors during the convertion but the NavMesh seems to be generated anyway. I test it with the A* path-finding, and it seems OK! The IA behaves well.

Now, by combining 2 external libs, I have some basic IA behavior. I am at the same point that with Unity path-finding before.
I must now tackle the REAL problem: dynamic NavMesh/IA loading.

V – NavMesh dynamic loading

It seems the A* library provides a way to export a NavMesh in a text file to load it dynamically at run time. Exactly what I need (theorically 😉 ). After a few tests, it seems to work at least for “little” files. But of course loading a new NavMesh gets rid of the previous one. I have to be cautious while activating/deactivating IA agents. But this means I need to write another script to convert the A* NavMesh in a text file during level generation.

 

VI – Integrating everything

OK. Every test I’ve made until now was of course on temporary/separate IA agents. I must know rewrite the code of the real enemy IA in my game to make them use the new A* library. And of course, I have a few problems because the library doesn’t provide exactly the same callbacks/hooks for various states (path is computing, agent has arrived at destination, etc…). But finally, the IA works just like before, and I can dynamically load a new level with correct IA behaviour.

VII – Final surprise: progressive activation

But… for larger levels, the loading seems to lag. How it this possible? I made all this to finally realize that the Unity fonction LoadLevelAdditiveAsync lags? Did I do something wrong?

And indeed, after a few tests, it seems that the loading itself doesn’t lag. It’s the activation and start scripts of all the loaded objects (IA/vegetation/animals…) that occur on the same frame that makes the game lag!

So I have to disable all the loaded objects, and activate them one by one on each frame. But this leads to 30 seconds to load a 1800 element level. So I optimized this to load many objects on one frame if they are light (a simple crate), and only one if it’s a complex one (enemies). I dropped down to 3 seconds to load the same 1800 elements.

VIII – Making it automatic

Cool! It works on a few levels that I placed “by hand” on the global world! But, in the end, I’ll have many levels, some of which may change in location. I have to set up a pipeline to ensure that every step I manually made is correctly and systematically handled for every new level.

I set up a special “world” mesh file made in Blender to precisely locate every level in the world. Each individual level is stored in a separate Blender file and centered on a (0,0,0) position.

When loading a level from Blender in Unity here’s the (almost automatic) process:

• Find the final level position in the “world” mesh
• Move the whole level to the final world position (while converting coordinates conventions)
• Convert every Blender object in a “smart”/”scripted” Unity object
• Create the NavMesh using either the Unity or RAIN NavMesh generation
• Convert the Unity/RAIN NavMesh to A* NavMesh
• Plug the generated A* NavMesh into the A* path-finding Object
• Convert the A* NavMesh to a text file
• Deactive all objects in the scene so that they won’t be activated simultaneously after a dynamic load

… And that’s pretty much it… For the offline level edition part.

At run-time here’s what happens:

• If you enter a level zone, the level is dynamically loaded, but nothing is activated yet. Only basic (and huge) island meshes are visible
• If you get closer, the text file NavMesh is loaded, object activation starts and within a few seconds the whole level comes to life.
• When you leave the activation zone, all objects are deactived, but the NavMesh is still in memory (in case you want to come back 😉 )
• When you leave the level zone, the whole level is destroyed.

I had to carefully study the distance at which each loading/activation occurs. Because I don’t want to start activating very far away levels, but I still want them to be visible at a fair distance. I must also care about the distance between the islands: if 2 or more activation zones overlap,  many levels are loaded at the same time, and this may seriously slow down the game.
In brief… all this things are to be tuned and balanced.

Sooooo…. This was a huge journey through incredibly complex features, but I now have an open world running at 50 fps in average and at least at 20 fps during loading. Now, you know why the game hardly changes between 2 releases 😉

For the brave guys who read until here, here’s a video of the dynamic loading of the levels. I use a super-graple enabling me to move from one island to the other, even if the aiming is sometimes a bit difficult… And you may notice the distance between islands is perhaps a bit long.

 

 

IX – Even more problems

For the sake of clarity I didn’t talk about every problem I had, but for the guys who would like to set up a similar structure, you have to know:

• The A* lib has some cache information about the NavMesh, and it’s sometimes necessary to “rebake”/”rescan” the NavMesh after loading it. But this is absolutely not real-time friendly.  I have to make additionnal tests, but it seems to be necessary only when playing in the editor when you modify a preexisting NavMesh. In the release, this may not be necessary.
• LoadLevelAdditiveAsync is absolutely not async in the editor. It freezes the game. You have to make a release exe to truly test real-time loading.
• Loading lots of level simultaneously totally messed up with all the automatic triggers I used to launch dialogs/cinematics or whatever. I had to fix all those things happening at the same time while I was still far away from the actual islands.
• Because I now dynamically load levels, I also must dynamically save all the local modifications of the player: if he takes a pickable item, unlocks a door or a chest, I must keep track of it even if the level is unloaded before he gets to a save point.
• A few objects don’t support activation/deactivation at all: clothes. This breaks the physics simulation in the best case, crashes in the worst. I had to find a workaround consisting in only disabling the cloth component instead of the full object… which makes my code look like crap.

 

 

That’s all for the crazy stuff. See you next time! Peace!