Hi,
My setup is as follows:
- 2048*2048 map
- Using Recast
- About 20k trees some of which are added or deleted (chopped down) during run time - using Navmesh cut to add/remove them as obstacles
- Houses added / removed during runtime - using UpdateGraphs
So far it all works fine and fast.
The last piece of the puzzle are roads which I have marked in my splat map - and which are also dynamic - ie. places that are more trafficked will become “roads”, places that are less will slowly go away.
The way I have this solved using Unity’s navmesh was to create “road marker” gameobjects with a different navmesh layer that Unity would then catch and I could assign a different cost for pathfinding.
My first attempt at this with A* was to assign penalties through GraphUpdateObject - which leads to 2 problems:
-
This results in a very approximative shape of the road - ie. it catches the navmesh triangles that intersect the road - which is to be expected I assume. So this raises question 1 - is there any way I can influence the navmesh shape so that it generates finer triangles along the path? Maybe adding small navmeshcut objects along the way?
-
The navmesh is often updated - either by adding/removing navmeshcut components (cut a tree) or by adding/removing houses. The problem is that the update operations result in new nodes that of course, do not inherit the penalty/tags previously set. These realculations happen relatively often so I’m not sure reapplying the updates every time is a great idea.
I’ve also tried replicating my Unity navmesh approach for a bit - ie. generating the road markers (several hundred gameobjects) but A* seemed to hang on the update (ie. had several hundred objects to rasterize). I could try merging all those objects into one, or generate a shape but that would be a time consuming undertaking that I’m not looking forward to unless I think it’s the way to go.
Is there a way to supply A* a texture or a volume that it would check against and assign penalties to new nodes as they’re generated?
I very shortly looked into grid graphs but that looks like an inferior approach to recast for my needs.
Help? 
An idea related to initial penalty - if I could give it a callback instead of a value I could probably accomplish this. The callback would have to get the position or node etc as a param - it could also set other attributes besides penalty - sort of like the Graph Update Object.
(if you point me in the right direction I’m happy to try/make the code change myself - at least as a proof of concept)
So I managed something - see the attachment. It ain’t pretty but it does it’s job nicely and at a first sight seems to be fast enough (more profiling to do). The path also follows the road and works with modifiers nicely. Had to apply a 1,000,000 penalty to non road to make it work though (but penalty points come cheap )
-
I influenced the navmesh to be “finer” along my road by placing plenty of navmesh cut objects on either side of the road. Not pretty, but good enough.
-
For “stabilizing” the penalties on new node generations I added a “InitialPenaltyDelegate(x,z)” property to NavGraph. Then on NavmeshBase::CreateNodes I moved the default penalty assigment after the position calc and made it use the delegate if assigned, default penalty otherwise.
Of course I had to change the A* core code so that means I’ll have to deal with patches and whatnot whenever I want to update the library so it would be great if you would integrate something along these lines officially? I think it would offer great value for a variety of cases - penalty based on incline, roads, make terrain under/above altitude expensive etc - would add an initialTagDelegate as well.
Any ideas on improving it? Any caveats that will bite me down the road?
Hi
When it comes to penalties I usually recommend a grid graph or layered grid graph. The reason is that they are much more uniform so penalties behave better. It also has built-in support for adding penalties using a texture that you supply.
However your world does look pretty large. So it is possible your world is too big for a grid graph.
Well, what I managed to get so far isn’t too bad. - and path wise works better than it looks on the penalty map.
Do you have any better suggestion to get a finer/more regular mesh around the road than placing small navmesh cut objects along?
Hi Aron,
The biggest problem I’m hitting is (obviously) controlling the navmesh generation along the path. Right now I’m using the pattern in “cut.jpg” as a tile and it gives decent results - however less than ideal - for example it doesn’t interact nicely with the radius modifier + it has 3 cuts per tile which is less than ideal.
I also tried the “dual.jpg” pattern - with the cut marked isDual - and it gives a much better result however apparently even if it preserves the mesh inside the cut that part seems to not be connected to the surrounding mesh? Ie. I can’t get them to walk to the middle of the tile. Is there an option (even if it takes a code change) to make the inside of a dual cut be connected with the surrounding mesh - ie. not to generate an actual cut - just to add those vertex to the navmesh.
Alternatively - is there an API that allows me to add some vertices/nodes to the navmesh at certain positions?
PS - first pic = “cut.jps”, 2nd = “dual.jpg”
PS2 - Getting random “Too many perturbations aborting” after some time - so probably an alternative way to tighten the mesh around the road is required…
Thank you!
Yeah… that’s usually why people go with grid type graphs for this use case :).
Reducing the tile size of the graph can help with getting more triangles where you need them.
So what do you do if you need a grid graph but also a large map?
Right now I am getting decent results by cutting a 0.1 circle in the middle of each tile. And by not creating tiles near buildings as that was leading to the too many perturbations error. So far so good in my testing but I still get an uneasy feeling…
