I was asked on twitter to give an overview of the navmesh generation process. Click on the above picture to see what happens when a temporary obstacle is added.What is missing from the picture is the logic that triggers tile updates when an obstacle is added or removed. I have not quite figured that all out. The plan is to have one class that allows you to add and remove temp obstacles, and then you update that class each frame, give it a time quota, and it will figure out which tile layers to update based on the obstacle shape and finally update the navmesh.
The tile layers will be always updated all the way from the compressed data, so adding or removing an obstacle will be the same process, but the temporary obstacle set used to build the layer will be different.
The obstacle shapes are expected to be expanded by the agent radius.
Each obstacle marks an area type into the grid. This means that you can punch holes or just mark certain areas depending on what you do. My plan is to support a couple of obstacle types, like extruded polygons and circles, but nothing prevents you from inventing you own shapes too! Maybe you can have some kind of cone to describe a line of fire of an agent, or a sphere which describes the radius of an explosion.
I'm quite excited about the performance I measured earlier today! The final step is to connect it all to Detour. It will be mostly boring bookkeeping coding on how to connect the tiles and such.
Thanks for the recap !
ReplyDeleteAs i understand it, the actual navmesh is allways computed when a tile is loaded. This is nice: you can generate navmesh for agents with different raddi at runtime from the same heightfield.
I don't how you'll be able to have a navmesh manager able to 'guess' how much data it can process from a time quota on any proc, though.
You can compute the initial pieces as preprocess or when you load the cache layers.
ReplyDeleteThe agent expansion is actually done in preprocess, but you could easily store multiple agent radii in the same heighfield layer, thought.
Since each layer has same dimensions, you can estimate an upper bound for processing per layer. My previous approach used column tiles, which could have multiple floors (layers), so the per tile cost would vary hugely based on how many floors there would be. It also meant that if an obstacle would move on the second floor, I would need to recreate the mesh for first and second.
It is not exact science, but it allows me to make more assumptions and simplify the code.
google 513
ReplyDeletegoogle 514
google 515
google 516
google 517
google 518
google 519
google 520