Navcast

Optikk · July 18, 2026, 2:50am

Navcast is a project porting Recast, the navmesh generation module of the popular open-source Recast Navigation library, to Luau.

About

This release aims to provide advanced users a starting point to have full control over navigable geometry and agent capabilities. Navcast is not a “batteries included” navmesh generation tool, nor does it provide a pathfinding runtime. You’ll need to write code that interacts with the Navcast module to use it in your own projects, and you’ll need to handle the pathfinding yourself. I’d like to provide a more complete, easy-to-use module in the future, but that will not be any time soon.

In its current state, this module is likely far too slow to use in live games except for in specific circumstances. I would not consider this a game-ready resource. However, if you are able to generate useful static navmesh geometry with it or if you want to use it as a starting point for your own navmesh generation, you may find it useful.

Additional Notes

For the core library code, I only use types that are available in plain Luau (in particular, vector is used instead of Vector3). Maybe this was a mistake, but I thought it’d be nice for the code to be available in any Luau environment.

As of now, there’s no documentation. This is something I’d like to fix eventually. You will have to look around for yourself to figure things out. Plenty of Recast concepts apply to Navcast, so you might be able to get something out of familiarizing yourself with Recast. The demo source code (more info below) may also help get you started.

Demo

A Recast-inspired demo model available that you can drag and drop into existing places. You may have to drag it into StarterPlayerScripts. In the demo UI, try checking the Live Build Tiles option for larger maps. This will generate navmesh tiles around you as you walk around. This option is especially recommended for large maps.

The demo is not perfect. I had to resort to some unpleasant methods to extract walkable geometry from any BasePart that isn’t one of the Part primitives. There’s plenty to refine, but it was good enough for a demo.

Disclaimer

This is a little pet project I’ve been working on for quite a while on my own. Certain things are incomplete, and there’s probably plenty of bugs that I have not yet discovered. I would not recommend using this code in live games unless using static, manually reviewed navmeshes that you have confirmed are correct.

Code

You can get the models and source code here:

Ionypex23 · July 18, 2026, 4:14am

The performance bottleneck is likely the heavy math involved in voxelization. Have you benchmarked how much the complexity scales with polygon count, or are we just assuming it’s too slow for runtime?

Optikk · July 18, 2026, 4:38pm

Yep, the voxelization is the greatest cost by a mile. I’ve kind of hit a wall with optimizing rasterizeTris (which is what this port and Recast provide by default) myself, started getting real diminishing returns, so I’ve left it alone and figured it might take someone else to figure out.

Last I benchmarked, the polygon dividing functions seemed to take the most time, followed by the adding of new spans (voxel columns). The data representation for spans is an easy optimization that I’ll probably take care of first, which should help a little bit.

The demo uses its own standalone voxelization, which I have hardly bothered to optimize. It was made strictly for demonstration purposes, mostly because rasterizeTris doesn’t give great results if you just plug in the tris from your average made-in-Roblox map. Ultimately, I think the best gains can be made if one knows exactly what their input geometry is and can optimize for that. For example, it’d be very cheap and easy to rasterize a bunch of AABBs.

After voxelization, everything else is pretty fast in comparison (faster than I anticipated without making a great effort to optimize/tune things for Luau).

I do think that no amount of optimizing will make the standard rasterizeTris step fast enough for real-time changes. I think one of the Recast demos (temp obstacles) uses a technique where voxelization is performed once, and then dynamic obstacles may remark the already-computed heightfield. I think heightfield layers also play a role in that demo, though I haven’t tinkered with heightfield layers myself so I don’t have much to say about the role they play.

Also, just for clarification, I say “too slow” to mean that generating from scratch can degrade performance to a degree that it may be impractical/unstable if intended for production environments. You will most likely have to use a form of “tile” generation with yields between work to avoid script timeouts.

WhatAboutCap · July 22, 2026, 6:07pm

Hey, looks pretty good! I’ve been working on my own version of Recast and implemented baking navmesh data into a string, bake once, then reuse it for pathfinding later. Never got around to finishing the pathfinding part itself though.

While testing I added RasterizeAabb to your version. It’s just a faster path for boxes that aren’t rotated, instead of doing the full polygon clipping, it stamps the box straight into the grid using its min/max bounds.

Optimized the span pool a bit, instead of using #heightfield.spanPool and table.remove every time, I added a manual spanPoolCount field that gets tracked directly. Since this runs constantly during rasterization, avoiding the length operator.

And tweaked the merge logic a bit too, when two spans end at almost the same height, it now picks the bigger area id between them instead of just going with whichever one happened to come first.

lunariitsu · August 12, 2026, 4:20am

This is so impressive cool, gg’s to you!

paswa · August 12, 2026, 3:18pm

Usage of vector was a good choice. Though the fully have its capabilities you need to enable native code generation. The vector library in Roblox has the ability to use a CPU computation optimization, which essentially turns any of the vector operands in the vector library into a singular computation on the cpu. What do I mean by that? When you do

vector.create(1,2,3) + vector.create(2,3,4)

you are computing 1 + 2, 2 + 3, 3 + 4, in one instruction. If you used Vector3, that would result in 3 operations. This is called SIMD and the native vector library introduces SIMD. Combined with --!native you can get some outlandish results.

Do not be mistaken though. An operation like

vector.create(1,2,3) * 4

is magnitudes slower than

vector.create(1,2,3) * vector.create(4,4,4)

So ensure, if you are multiplying by scalars, to fill the vector with the scalar, then multiply. I would look more into how you can optimize this system using SIMD. Which can be found in a lot of other languages like C++. Anyways nice project!