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#.
Hey Tim!
Itās good to see someone else interested in standalone pathfinding. Iāve been playing around with a few different ideas over the past couple months. I have gotten pathfinding to work (including Aronās A*Pathfinding system in C#) without Unity. I have not yet, however, gotten a solution to work that does everything I want though.
After working on a solution using A*, I started playing with Recast/Detour which (I think) is what inspired the this C# project. Recast/Detour are written in 100% unmanged (C++) code. Unfortunately, I have not yet been able to get it to read in my vertices/indices/layers and give me a good path. Plus, Iāve gotten some segmentation faults with it. Aronās C# solution seems to be very accurate when it comes to pathfinding but the baking (scanning) time was long and it didnāt do well around my bodies of water where the tag IDs change. I couldnāt get a fine line of vertices around my lake, with triangles converging on the outside of it, while triangles are built on the inside too that just come to the edge and not protrude. Aron has updated his algorithm and it is supposed to bake a lot faster now but I have not tried this yet.
For me, the holy grail would be a very fast pathfinding algorithm that can directly use Unityās navmesh data. If not then, at least be able to take my list of verts, indices, and areas and give me paths on it.
What have you been able to do so far? I would love to share ideas and help each other.
By the way, there are other threads that Iāve posted to. Please check them out by clicking on my name. Thatās why you havenāt seen activity in 14 days.
