Building Recast Navigation for the Web
I remember the first time I heard of Emscripten. I had mixed feelings. JavaScript was notably slower at the time and I had a lot questions.
Is C++ 100% compatible with it? How do I debug it? Can I use OpenGL with it? What will it used for other than porting old games to the web?
Years later, it is now in good shape. The performance is awesome. The toolchain is mature. More uses are found everyday. It opens doors for a number of industry-proven libraries previously only available to native applications. Thousands of libraries ranging from computer vision, to 3D engines, to games… decades of C/C++ are now accessible to JS developers.
Take some time to read Justin’s excellent post on Bringing Native Marker Tracking to the Web with WebAssembly:
Hello world!
Let’s make an “Hello world!” program starting from scratch. You only need to have Git installed to start. Type these commands in a terminal:
Congratulations! You are ready to compile C++ to JS!
Copy and paste the following to helloworld.c:
In the same terminal as before enter this command:
You should get a helloworld.html, helloworld.js and helloworld.wasm
Still in the terminal type:
This will start a web server accessible with your browser at the URL: http://localhost:8000/helloworld.html
Your first C program running in your browser! Isn’t it awesome and magic?
The glue
The glue is where Emscripten really shines and make the porting easier. Any C++ program can make a call to the system to read files, print some text on screen, open a window, you name it. Emscripten can convert those calls to the JavaScript equivalent. It doesn’t work for every library you may use but for the most common it works perfectly.
For example, the filesystem calls are emulated so you can read files in a virtual file system. If you use LibSDL to create your window and your OpenGL context, Emscripten replaces the calls with a WebGL canvas automatically.
Depending on what you want to achieve, you can build your application or game using C++ then transpile to WASM. Or you can build your application with JS and use libraries and code from C++.
That’s the approach we take on the Babylon team. As the name implies, Babylon.js is a web 3D engine and we use third party libraries. For example, we use Ammo.js which is a port of BulletPhysics for physics simulation and Recast.js for navigation. And it’s the latter that I’ll talk about in more detail.
Recast navigation
Recast navigation is a production-ready navigation library used in countless 3D engines and applications. The repository is composed of 3 parts:
- Navigation mesh creation
- Agents navigation
- A visual sample that shows how to use it
Parts 1 and 2 don’t have any dependencies and that’s what we want to use in Babylon. We need to turn it into a library that’ll be accessible in JS.
The repository is available here: https://github.com/BabylonJS/Extensions/tree/master/recastjs
The interesting parts are the CPP files in the src folder, the recast.idl file, and the Python build script. In the src/ folder there is nothing fancy, just simple classes to wrap everything inside simple C++ classes. I didn’t want to expose all the recast API to JS, so I decided to do a wrapper for the most common uses of Recast and expose it to JS using web interface description language (IDL).
The syntax is quite simple:
So, we have the C++ and the IDL. It’s time to bake everything into a .js/.wasm pair. That process is more complex, however, and won’t fit in this blog post. I invite you to read the Python build script. It’s 140 lines long and can be easily adapted to compile any C++ source. It’s even easier if there is already a CMake build system used.
- You’ll find the call to build the glue from the IDL https://github.com/BabylonJS/Extensions/blob/master/recastjs/make.py#L88
- emcmake call to build the C++ https://github.com/BabylonJS/Extensions/blob/master/recastjs/make.py#L103
- and bundling altogether https://github.com/BabylonJS/Extensions/blob/master/recastjs/make.py#L122
Use that script as a starting point. Rapid iterations are key to great programs, and this script may help you build for the web quickly.
A word on memory allocations
One of the most annoying issues that I faced was the memory allocation life-time. To simplify things, any C++ memory allocation ends up being a span in an array allocated on the JS side. In C++ if you allocate memory, use it, and then free it, you’ll get an error the next time you try to access it. With WASM, you can free memory and use it after, with no error reported. It will be reused by another part of the program at some point resulting in your freed-and-reused memory being trashed. These types of issues that don’t report an error but may cause non-reproductible issues can be hard to track sometimes.
Cedric Guillemet — Babylon.js team
