Question regarding capabilities of A*

i’ve recently been looking around for different pathfinding solutions online to help me with an issue in my project, and I have a question that I couldn’t find a clear answer for. In the game im working on, I want to be able to place buildings on the map at run time, and have NPC’s traverse them when they have been placed during runtime. Now, from my understanding, i can’t do this with unity’s built in navmesh system, so i ended up discovering A*. My question is, is this possible with A* pathfinding? The ability to place/Instantiate a complex structure like a house, and have a navmesh be generated for it in real time and have NPC’s be able to traverse on top of it?


so from what i’ve been reading on the documentation so far, i’ve come up with the following idea. The map we have in our game is really big (1000’s by 1000’s big), so it seems the best way to generate a graph for it would be a navmesh graph not the grid graph. Now if I have a navmesh generated for the terrain, im thinking that i could have a second Grid Graph generated on top during runtime, for only the buildings of which i would place/update at runtime and would want to have AI walk on. The issue is though, it seems the grid graph can only be so large, and the houses, although small, are spread vastly apart, therefore not allowing me to generate just one grid graph for them, thus limiting me with the graph limit. Before i purchase the pro version so I don’t have to make the navmesh by hand, is there a solution or a way to do what im trying to do and would i be able to generate a navmesh link between the two graph’s? or does anyone know of a better way to solve my issue.


This is in theory possible with the pro version. You would use a tiled recast graph and the recalculate the tiles which the house touches. However the problem is that unless your houses are really tiny, you would run in to lag. The system can offload the calculation to a separate thread, so if you can tolerate a second (or more) delay until the graph has been updated (and during that time, no pathfinding can be done, requests will be queued), it might work.

I just did a test with a small cube which I moved around while the graph was recalculated and it worked. However I realised that the default thread priority for the graph update thread was too high, so it affected the FPS quite a lot, when I changed it to Lowest, it ran smoothly. The scanning process does still allocate quite a lot of memory, so you might run into GC issues.

For this you will need to change
in AstarPath.Awake
if ( numThreads != 0 ) { graphUpdateThread = new Thread (new ParameterizedThreadStart(ProcessGraphUpdatesAsync)); graphUpdateThread.IsBackground = true; graphUpdateThread.Priority = System.Threading.ThreadPriority.Lowest; // Add this line graphUpdateThread.Start (this); }

I will likely expose that for the next update.

I cannot guarantee that this will work for you since I only did a small test, but it might.

I strongly discourage combining multiple graphs, from experience I have found that it usually just ends up with lots of edge cases near the border between the two graphs.

thanks for the response, I’ll give this a shot for sure and see how it works.

I’ve done what you’ve said, along with some things i’ve read from a few other discussions that relate to this, and its going really well so far. everything works great except for one error that im getting. sometimes when i place a building, and i update the graph, i get an error stating "Not allowed to access triangles on mesh ‘g17’ " (the g17 part is not the same each time). any ideas what’s causing this and what i can do to fix it?
(also sorry for asking so many questions :))
Edit: made new post as this discussion got a little buried