LogInReddit user f4t4lity5 shared a WIP of their project.
A Reddit user known as f4t4lity5 showcased an update on Navigation Mesh generation in their project, which has impressively improved to deliver results 20 times faster than the previous version. The developer is in the process of optimizing and converting the entire thing into a C++ plug-in. Once completed, they plan to release it for free on the Unreal Marketplace.
This implementation may not be suitable for larger projects. As f4t4lity5 pointed out, most of the NavMesh areas in their project contain only 5,000 to 10,000 nodes, so even the unoptimized pathfinding doesn't show any noticeable performance issues. However, a paid version of this plug-in is set to support octrees for increased performance on very large and dynamic meshes.
Here's the actual pathfinding system created by f4t4lity5:
As for the mesh generation show off, the developer clarified that the red mesh displayed doesn't align with the actual mesh generation. It appears only after the mesh is completed. This is because rendering the debug meshes incurs some overhead, and they aimed to compare the generation algorithms as accurately as possible.
A bit of background on BFS, It starts with an origin node or a root. Then all surrounding nodes are added to a "To Be Checked" stack. The program then continues to loop so long as the stack is not empty. On every loop, it pops the top node of the stack and makes that the "Current Node", then every adjacent node to the Current Node is added to the stack.
List of optimizations:
- Most importantly, I ported it to C++;
- When adding new nodes to the To Be Checked stack, instead of checking if the node is already in the stack, I add it no matter what, then check if it is already in the grid on the next iteration of the loop. This is much faster because the grid is stored in a hash map while the stack is array-based. Meaning it is O(1) to check if it is already in the grid, while it is O(N) to check if it is already in the array;
- Lastly, I changed the stack into a classic array. On startup, I initialize the array to the size of the entire grid to avoid costly resizing operations. Then, rather than popping off nodes after I check them, I simply increase an index value that tells which array index to use to get the next node. This avoids the very slow remove operation, which essentially has to rebuild the array every iteration.
See the original Reddit post for more details here and join our 80 Level Talent platform and our Telegram channel, follow us on Instagram, Twitter, LinkedIn, TikTok, and Reddit, where we share breakdowns, the latest news, awesome artworks, and more.