I think I just answered my own question about filtering layers… There is a graphMask that I’m setting to -1 but -1 is really 0xffffffff which means ALL layers… so if I include all layers in my graph, I can individually pick them per path with graphMask?
I’m also still having trouble understanding the units that I pass into ABPath.Construct() for my start and end vectors, and, of course, the resulting path I get back is in those same units. That output you saw of it navigating was only possible because I kept guessing different start and end locations from your sample map with the bridge and the ramp. I kept doing some trial and error until it walked up the ramp. I actually do not know how to translate world units to the units the pathfinder is using, and vice-versa.
Hi
The pathfinder should use world units. However if you see Int3 coordinates somewhere (instead of Vector3) you can cast from a Vector3 to an Int3 using an explicit cast. Int3 essentially hold integer values of the coordinates multiplied by 1000 (Int3.Precision more precisely).
So sorry about stupid questions like that. As you were probably typing, I got one of my Unity scenes’ graphs to work properly (in world units). For some reason, the graph from that test scene is messed up bad.
And, it was floats though… last night I did figure out I was getting Int3’s when I was expecting floats. It’s funny cause I actually did something similar a dozen years ago, or so. I used floats multiplied by 1000 and stored in a uint for performance reasons… you could do integer math on it, like bit shifting to the left by 1 to multiply by two, etc.
So, I’m going to try using the Funnel Modifier and then work on multi-threaded graph-building. I’m excited!!
Okay, I implemented IFunnelModifier and looked the code over and figured out I needed to instantiate FunnelModifier can call Apply() on it with my path. I passed Pathfinding.ModifierData.StrictVectorPath even though it looks like this argument is unused in the Apply() function.
This is what I got…much SHORTER list…but…
result path count: 14
node: (514.5, 2.6, 269.2)
node: (504.0, 2.6, 274.5)
node: (486.5, 2.6, 283.5)
node: (486.0, 3.2, 285.0)
node: (487.5, 8.7, 296.5)
node: (485.0, 7.5, 313.5)
node: (482.5, 3.6, 325.0)
node: (473.0, 3.6, 358.5)
node: (471.5, 4.0, 359.5)
node: (465.5, 6.3, 353.0)
node: (460.5, 8.1, 356.0)
node: (453.0, 9.9, 356.0)
node: (452.0, 10.5, 354.0)
node: (478.7, 23.8, 261.5)
It didn’t land on the destination. Neither did pathfinding without funneling. The end node that I passed in was:
pathFind(new Vector3(513,4,266),new Vector3(480,26,266));
So this is off by quite a bit. I know I could always make a b-line for the destination from the last node and it wouldn’t be obstructed but then my seeker could actually run right past his destination and come back a little bit.
Hi
Yes, the path will still by default end up on the position of the last node in the path.
Usually the Seeker handles this, but the easiest for you is probably to run this right before you run the funnel modifier:
path.vectorPath[0] = path.originalStartPoint;
path.vectorPath[path.vectorPath.Count-1] = path.originalEndPoint;
You might want to snap it to the closest point on the last node in the path, but this should be a good start anyway.
Take a look at the StartEndModifier if you want to know more.
BAH!! Failing to make this multi-cored:
Voxelize[] vox=new Voxelize[8]; for(int i=0;i<8;i++) { vox[i] = new Voxelize (cellHeight, cellSize, walkableClimb, walkableHeight, maxSlope); vox[i].inputExtraMeshes = extraMeshes; vox[i].maxEdgeLength = maxEdgeLength; }
. . . //Generate all tiles for (int z=0;z<td;z++) { for (int x=0;x<tw;x++) { . . .// BuildTileMesh (vox, x,z);
int i; while(totalThreads>=8) Thread.Sleep(1); totalThreads++; for(i=0;i<8;i++) if(VOXs[i]==0) break; if(i==8) { System.Console.WriteLine("****SEVERE ERROR in scan: a VOXs slot should've been freed up but there are still 8 in use!.. quitting."); return; } VOXs[i]=1; new Thread(() => { Thread.CurrentThread.IsBackground = true; BuildTileMesh(vox[i],x,z,i); }).Start(); . . . }
It still uses a single core and then it hangs a little more than half-way thru the process. Still working on it. BuildTileMesh() decrements the thread count at the end and also frees up its VOXs array slot i.
If I can get this working, maybe something similar to this could become an option in your codebase if there are any other people who want speed when baking.
It has to be the line: while(totalThreads>=8) Thread.Sleep(1);
But that condition shouldn’t happen. All BuildTileMesh threads decrement totalThreads when they’re done. If you were interested in the final product, I wouldn’t leave it like that. Even though it should never get stuck in that loop, there should be a limit to how long it will wait before erroring out…
UPDATE: stupid me! You can only increment or decrement a shared variable from different threads if it isn’t true multitasking, like the old days when we had one core. Now I’m using Interlocked.Increment and Interlocked.Decrement… However, I’m still very confused, it’s going no faster (12.5% CPU usage).
Hi
It seems that you have encountered a race condition. I am not quite sure what it is, but I would suggest that you use a thread pool instead. I think .Net one built in.
Keep in mind that at every point during a threads execution it might stop and another thread can start running.
Also, if a, b = 0 initialize and then thread A does
a = 1;
b = 1;
then thread B may (for some small amount of time) see (a = 0, b = 1 or a = 1, b = 0, or a = 1, b = 1).
I found the problem… some of the stuff inside BuildTileMesh() doesn’t appear the be thread safe:
vox.Init ();
vox.CollectMeshes ();
vox.VoxelizeInput ();
I put checkpoints between these lines and it always gets to vox.Init() but the thread crashes often before getting to vox.CollectMeshes() and has passed vox.VoxelizeInput only one time that I saw. And I’m sure these were independent instances of Voxelizer.
UPDATE:
I found the problem to this mystery. You may have forgotten about cached variables in CreateTile (cachedInt3_int_dict) and CreateTile is called from BuildTileMesh(). It’s not thread safe. After many hours of work and then running into this, I’ve given up on speeding up the rasterization process. It’s too much work.
I ran into another issue with pathfinding. This may be very simple but I couldn’t figure it out. Take a look at this screenshot. The white wolf in the distance ran around the fence and he is almost on the fence. Sometimes, he gets so close that he does snap right on top of it and then back to the ground. The Y-location snapping of course is due to my own code but pathfinding gave it a line to walk that took it right into the same XZ as the fence at one point:
(Could only upload one image so please see next post for the rest…)
Hi
I replied to your other thread about this issue.
Thank you Aron! I actually meant to delete it from this thread because I created a new thread for the navmesh generation issue (rounding issue). I figured that is a totally separate issue that has nothing to do with running A* Pathfinding outside of Unity so it didn’t belong here. I have yet to try the bug fix and regenerate the recast… hopefully after work today. 
But, regarding the thread unsafeness of multithreaded navmesh generation, as described above, did you have any thoughts on that? As it stands now, its too complicated for me to attempt and I will have to run scans on the larger scenes just before bed.
I have one more question regarding my A* Pathfinding outside of Unity. As you know, I’m handling many worlds at once. So, I load multiple graph files into memory at once. What I’m doing is I’m creating an array of AStarPath singleton classes, one for every world I have. When a path is calculated, I set the static active variable to the relevant instance. If I enable pathfinding on more than one world, it still crashes though. Each array instance of AStarPath should think it has the only instance in its active variable and have its own AStarData, etc. To further explain, I force paths to calculate instantly so two paths cannot actually be calculated concurrently. This is not how I want to keep it but I was trying to get something that works. I was surprised the crashes were happening despite the use of WaitForPath() each time.
Any thoughts on this one? Am I missing something simple? Do you think there is an easier way for me to do this?
Hi
You cannot have multiple AstarPath instances since it uses a singleton pattern, however you can load multiple graphs into a single AstarPath instance.
See AstarData.DeserializeAdditive (http://arongranberg.com/astar/docs/class_pathfinding_1_1_astar_data.php#ab75c959813c5066a85a9f8981471e772).
You most likely want to set the path.nnConstraint.graphMask field to indicate which graph it should search. The graphMask is a bitmask so “1 << 0” indicates “use the first graph” and “1 << 1” indicates “use the second graph” and so on.
Regarding the multithreading. I could probably attempt to do that myself since it would be a big win for all users of the A* Pathfinding Project. Not sure when I will have time to though since I am working on some other projects at the moment. You can try enabling the “ASTAR_RECAST_BFS” compiler directive. It is faster however in rare circumstances it can fail to generate a navmesh tile completely.
Also there are likely a few optimizations I could do for worlds with a huge number of tiles (you have 20000 tiles or something, and it is probable that this will cause a bottleneck in some part of the code that can be handled much faster, I am actually not sure I have ever seen a user use that many tiles).
I would recommend that while you experiment, that you use a much smaller scan size to
Hi,
I just looked at DeserializeGraphsAdditive. I thought the reason for this mask was to turn certain layers on or off (like if I want a certain seeker to traverse water while another seeker sets his water layer off at (1<<waterlayer). If this can’t be done then I have additional problems.
So, aside from the scene layer issue, graphMask is 32-bit integer and that wouldn’t be nearly sufficient for my game. Not even a long integer (64 bits) would suffice. Every level of every dungeon will be another scene, no matter how large or small they are. I am working on creating a full-scale MMORPG.
Back to the idea of having multiple “singletons”, I did mention that I am changing that static reference to active on every path call, so it sort of “switches in” another scene. This however, can’t be multithreaded and it still doesn’t work for some reason.
So, my two questions really are, can nnConstraint.graphMask still be used to filter different scene layers? It appears that it should work because I can see graph triangle lines go across my bodies of water but also on the terrain below them… Secondly, is there another easy way to use multiple graphs besides graphMask due to the limitation of 32 graphs?
As for multi-threaded and/or optimized graph building, I am very thankful that you will put some thought into it. Yes, I think many people would like to see faster speeds even if they don’t have any levels as large as mine. I’ve designed the game so that 10000x10000 world unit scenes would be used for pieces of a larger world making up my outdoor map. Indoor maps (dungeons, for example), and other world maps would be much smaller. I could look into tilizing my outdoor world into even smaller scenes but I’ll take any speed increases I can get
Thank you!
Are you sure you are going to put all this on a single server? Simulating huge worlds for an MMORPG is not exactly going to be cheap.
Since you are only going to use a single graph per character, you can change it so that instead of a bitmask, it just indicates which graph should be used. You can modify the NNConstraint.IsGraphSuitable method (or a similar name anyway).
The graph mask is not used for that. You are probably thinking about tags.
A very easy way to get it working is to just fire up a new server instance for every dungeon 
not sure if that would suit your game.
I thought about the possible problems that can occur when this thing reaches the size that I have in mind. If a single very powerful computer won’t be able to handle all of my levels and instances at once, I was thinking that the game could be grouped into chunks of maps and distributed across multiple servers. When a character decides to (for example) travel to another continent or particular dungeon group, his character data will be saved to a central server and then the corresponding server that handles his new area will be contacted by the server he is leaving, so that the new server can load his data and take over.
I can see that your AStarPath does handle Layers and tags to filter on before I scan a scene. I was hoping that this is what graphMask was filtering on. I can see there is a constrainTags boolean and I’m trying to read the API reference to see what it means and it’s not loading for some reason. I hope there is a way I can have terrain and water be traversable separately in the same graph and I just set an ABPath value to let it know which layers/tags it can traverse.
Regarding using graphMask as an index instead of a bitmask, I’ll look into this (thank you for the advice!) I won’t be mixing graphs together so just using an index to a graph would totally work… I just hope the scope if this change won’t be huge 
Ah, sorry. Name confusion.
Unity has tags, and there are node tags. See http://arongranberg.com/astar/docs/tags.php
(Unity already picked the good names: tags and layers).
If you are familiar with the Unity pathfinding system, they are called “pathfinding layers” in their system.
Thanks!! I’ll take a look at this! Yeah, I used to use Unity’s pathfinding system… The server actually used Unity at one time and it only handled a SINGLE map …That contributed to the origin of the huge 10000x10000 size. I had to scrap this approach when I separated my server from Unity into a standalone C# project.
It’s too bad your .bytes format isn’t the same as Unity’s NavMash.asset format… or, I wonder how difficult it would be to write a converter? Then, the baking speed would be a non-issue!
Hi
Actually I don’t think it should be too difficult to convert a Unity navmesh for use by my system. Unity can already output a triangulation of it, and that should be able to feed into a navmesh graph at least. However if it is tiled you likely want to use a recast graph and figure out a way to separate the triangles from Unity’s into the tiles where they belong (shouldn’t be that hard).
See http://docs.unity3d.com/ScriptReference/NavMesh.CalculateTriangulation.html
Hi Christmas
I have read through your entire thread and notice you went quiet 14 days ago. This is something I am interested in doing to add to my own MMO framework and am wondering how far along you got?
I am likely going to re-work it all so that nothing is left out as well as make it multi-threaded; so, if you do not already have a solid solution that you are happy with, maybe we could work something out.
It is likely that I will end up porting it to C++ later on as well as there would be no reason to have it as a separate module written in C#.