Navmesh progress

Note: This article was written on 2025-01-04, as a summary of the events happening on Discord back during this development log

Navmeshes (a tool to allow NPCs to move around freely) have been a pain to implement for the longest time, due to a mix of not finding much information, and wanting to do everything myself. This is a short update on this topic.

Navmeshes (navigation meshes) are special "hidden" parts of the map that allow non-player characters to find how they should move. The idea is to break down the floor into "little parts" that we absolutely know the character can walk in, and what each little part is connected to. Then, using some clever code (something called the A* search algorithm), it's fairly easy to plot a "route" from anywhere to anywhere else, and then have a character follow that route.

The main issue I encountered while implementing navmeshes is simply the sheer lack of resources for how to actually create said navmeshes. Almost all resources on the web assume that you

I ended up finding this "Constructing a Navigation Mesh in Node.js" article by Talin as the closest candidate to what I wanted to do, which was good, but very... Surface-level. Unfortunately, this article relies on a few math libraries that contain the complex part of creating navmeshes, and unfortunately, the code of these libraries is very hard to understand and lacks a lot of explanations.

Still, I wanted a first draft of the system. So, sarting on June 17th, I decided to ignore the whole "remove things" part of the algorithm, and just focused on actually mapping out the walls of the existing dungeon maps. This was a simpler algorithm, and while it still took a while to get it right, it was a way to get faster results and have some progress done.

On June 21st, I ended up with a viable implementation for the grid layout at least, and it will do for now!