Using pathfinding outside of Unity

#1

Hey Voxel, and all!

Continuing our conversation about how to get A* Pathfinding to run outside of Unity, I’ve taken the steps you’ve suggested so far.

To fill everyone else in who might be interested, the following symbols need to be set to true when compiling: ASTAR_NO_GRID_GRAPH, ASTAR_NO_POINT_GRAPH and ASTAR_NO_GUI.

You said to ignore:
Editor, ExampleScenes, Modifiers, Navmesh except the RelevantGraphSurface script (you might want the navmesh cut script, but let’s skip that for simplicity), RVO, Utilities/UnityReferenceHelper, Utilities/AstarProfiler, Generators/GridGenerator, Generators/LayerGridGraphGenerator, Generators/PointGenerator, Generators/NodeClasses/GridNode, Generators/NodeClasses/PointNode, Generators/Utilities/NavMeshRenderer, Generators/Utilities/ObjImporter, Generators/Utilities/TileHandler, Generators/Utilities/Voxels/DebugUtility, Core/AI, Core/RVO. The Seeker script could be useful, but probably it is easier to just copy and paste bits of code from it if you need to rather than getting it to work outside Unity.

Additionally, all methods called OnDrawGizmos can be deleted.

By doing this, there are lots of errors now in AStarPath not being able to find GraphModifier and the referencing code looks important.
Secondly, I went to add in my own StartCoroutine from the link you suggested (http://forum.arongranberg.com/) and then realized it’s already in the code, conditionally excluded from compilation because it looks for a symbol called “PhotonImplementation”. What is this for? I followed the #if’s for this symbol and it almost looks like it was an attempt to have the code build outside of Unity. Unfortunately, enabling this symbol created even more errors.

Also, in case anyone else is interested in this topic, if you build all of the classes from the A* Pathfinding Project in a standalone XamarinStudio project targeting a Library, and you add references to all the included DLLs, you will get NO ERRORS and NO WARNINGS but, there will be many references to the Unity Engine that will cause failure at runtime. And, that is what I’m working through right now.

1 Like
Questions for using A* Pathfinding Project for MMO
#2

Hi

Huh, is that in the released version!? I really thought that was stripped out of the final build.
Yeah, the PhotonImplementation define is the only thing left from my old version where I had it working outside Unity (primarily for people wanting it to work on Photon servers). Don’t rely on it though, it hasn’t been tested in years.

The GraphModifier stuff is not important for what you want to do, but it is probably easier to keep it but not just use it.

Ok, if you are going that route, I would suggest that you create an empty dummy class for MonoBehaviour to avoid using t he UnityEngine one (which will definitely cause things to fail).

#3

You know, I had a a unity asset for your Pathfinding project from quite a while ago. I downloaded it but never used it until this week. I’m not sure how that Proton stuff ended up in any of your releases but I think the first thing I need to do is pull down the latest free version and work with that. I apologize if some of these issues wouldn’t have been prevalent if I had just used the latest version. I’ll let you know how it goes.

#4

Aron,

I’m not sure if you got my email from a few days ago or not but I’m looking to pay someone to develop a stand-alone version of A* Pathfinding. Is this something I can ask in your forum? If it’s the pro version, I could pay the programmer plus purchase a license from you. I realize that I couldn’t expect updates on this branched version but I would be okay with that if it does what I need. I need to be able to traverse NavMeshes saved with a recast of a whole scene, but I need to be able to do this pathfinding without Unity. If it’s permitted, I would like the source code, otherwise, a compiled DLL would suffice.

I desperately need quick pathfinding on my MMORPG server. It needs to be able to handle multiple XZ regions stacked on top of each other as well as the terrain. Two-sided edges would be preferred so you can jump down further than you can climb up, but I would settle for one-sided edges in which, say, 45-degree angles are the steepest any path can traverse.
Please let me know! :smile:

Thanks

#5

Hi

I did not get that email.

Sure, you can ask in my forum, though I think you would probably have better success elsewhere where other programmers are actually looking for work. Maybe the Unity forums. The source code is included in the pro version as well as the free version.

I would be interested in hearing your progress and I would be happy to help you with any questions.

If you put your modified branch under version control you should be able to apply diffs from upgraded versions relatively easily. (also, you should probably start with the current beta version to be as up to date as possible).

1 Like
#6

I’ll definitely keep you updated on my progress! Thanks for your interest. Maybe you’d like to see some screenshots too? It’s a fantasy MMORPG game inspired by WoW and Perfect World.

I decided to give A* Pathfinding Project one more go alone before I try to hire someone to modify the code. A lot of the complexity I run into stems back to BBTree. How much of that class is actually needed if I’m just trying to navigate a NavMesh or Recast graph? I know the class itself is essential for pathfinding. And I already know I can comment out OnDrawGizmos.
Also, isn’t a recast graph still a navmesh? From the way you described it, it is how I can bombard my levels with rays to figure out height. So, the way I understand it is a recast graph is still just a navmesh but it picks up all the colliders in the scene and it shoots rays out in both directions and continues to look for colliders, not stopping at the first one. Does this sound right?

EDIT: Do I need JSON Serialization for anything on the server side?

#7

Hi

I’m not sure why the BBTree class is problematic. That should be pretty separate from any Unity API (except the Vector3 and Rect classes). It is not strictly required, but you are going to want to avoid huge performance penalties.

It doesn’t exactly bombard it with rays, it takes in a polygon soup (i.e lots of polygons) and rasterizes each polygon into voxels (think minecraft with smaller blocks), those voxels are then used to build the navmesh. The easiest for you is probably to generate the navmesh in Unity and then serialize it, but it is also possible to send it custom meshes on your server if that would be necessary (you will need a simple clone of the Mesh class however).

Json serialization can be disabled using the ASTAR_NO_JSON compiler directive, however I don’t think that json should cause many complications since it does not rely on Unity at all.

#8

The BBTree class itself isn’t problematic. I was trying to bring the absolute minimum number of files into my project and I was down to a single error (That it couldn’t find BBTree). And adding BBTree then requires many other files which I’ve been working hard to try to isolate what is needed, while commenting out areas of code that don’t seem to be needed.

So, the functionality is already present to generate the navmesh and another function to serialize it? Regarding JSON, the reason I asked is I can see a binary reader and writer and was trying to figure out how to use them properly. My thinking is that it is more efficient to store everything as binary (ZIPped).

#9

Hi

Ok.

Only settings are actually stored as json. The graph data itself is stored in binary.
There is some documentation on the format, but unfortunately it is a bit out of date now.
If you disable json, it will store settings in binary as well, however that will sacrifice some forwards and backwards compatibility (not a huge problem I guess). The performance and memory overhead is negligible.

#10

I am so sorry about all the questions. I just have one more for today and, hopefully, this is the last one.

I get this error many times but you said I don’t need Modifiers:

…/Projects/pathfind/pathfind/AstarPath.cs(3,3): Error CS0103: The name `GraphModifier’ does not exist in the current context (CS0103) (pathfind)

Some of the things that call on modifiers seem important. Can they all be commented out?

The other major error is this:

…/Projects/pathfind/pathfind/RecastGenerator.cs(44,44): Error CS0103: The name `ConnectTiles’ does not exist in the current context (CS0103) (pathfind)

Recast’s UpdateArea() uses this… do I need it? If I do need it, where is it implemented?

Thanks!

EDIT: It looks like BuildTileMesh and CollectMeshes are also related to the absence of ConnectTiles. So if I need it, I want to implement the minimum possible.

#11

Hi

Correct, you do not need the modifiers. Mainly they are there to provide hooks into the graph generation process.

The ConnectTiles method is implemented in the RecastGenerator.cs file. It generates connections between two tiles. If you are only going to load serialized graphs from file and never update them, you can remove it, otherwise you will need it to make sure that agents can move between different recast graph tiles.

[EDIT] BuildTileMesh and CollectMeshes can be removed if you are only going to load serialized graphs from file and never update them.

#12

In AStarPath, Awake() calls Scan() which calls ScanLoop() which has all that modifier stuff in it. Can this whole call to Scan() be removed from Awake() or do I have to pick it apart?
And since this is not a MonoBeaviour anymore, I was planning on making Awake() public and just manually calling it once in the beginning.

I think I am almost there!!! :smile:

#13

I guess if you are only going to load graphs from file, then it is not needed.

#14

I GOT IT!!! :smile:

This is proof that I found a path that climbed up the ramp you have in your Recast Example! Lots of hard work to get to this point!

astar data awake() called!
loaded graph with 1 graphs!
graph 0 nodes: 369
path ID=1
startnode walkable? True
result path count: 35
node: (1.0, 0.2, 2.4)
node: (2.3, 0.2, 2.4)
node: (2.9, 0.2, 1.6)
node: (2.1, 0.2, 0.9)
node: (2.7, 0.2, 0.5)
node: (2.7, 0.2, -0.2)
node: (2.1, 0.2, -0.4)
node: (2.1, 0.2, -1.1)
node: (2.7, 0.2, -1.7)
node: (2.1, 0.2, -2.8)
node: (2.8, 0.2, -3.4)
node: (3.6, 0.2, -3.0)
node: (4.4, 0.2, -3.6)
node: (5.0, 0.2, -3.2)
node: (6.2, 0.2, -3.2)
node: (6.8, 0.2, -3.6)
node: (7.6, 0.2, -3.8)
node: (8.4, 0.2, -3.8)
node: (9.0, 0.2, -4.4)
node: (8.4, 0.2, -5.8)
node: (8.8, 0.2, -7.0)
node: (9.1, 0.2, -8.5)
node: (9.9, 0.2, -8.7)
node: (10.5, 0.2, -9.1)
node: (11.5, 0.2, -9.1)
node: (11.8, 0.2, -10.1)
node: (13.6, 0.2, -10.9)
node: (15.4, 0.2, -9.9)
node: (17.4, 0.2, -9.9)
node: (17.7, 0.3, -11.3)
node: (18.9, 0.3, -10.1)
node: (18.3, 0.5, -12.3)
node: (17.2, 0.6, -14.2)
node: (17.0, 0.6, -14.8)
node: (16.3, 0.9, -14.2)

Now for performance testing…

But, the only thing I can’t figure out is, why is the end node (16.3, 0.9, -14.2)? The Unity scene that this graph came from has this part of the ramp as being near (17.8.29.5,-35.9)… I couldn’t figure out how graph coordinates map to world coordinates…

Update on 14-Jan: I still have not figured out the coordinate system mismatch and I even reviewed the seeker code to see what it did with the path[] array once the path completed.
Now, I just used A* to scan one of my large scenes (10000x10000) units and it is only on 800/24900 tiles right now and more than 10 minutes have gone by. I know Unity’s NavMash baker takes considerably less than this on the same scene. Any ideas for speeding this up? If I so much as add one piece of fence, I’m going to have to scan the terrain again. That is unless I don’t mind creatures running right through it while I’m testing.
I believe my character radius is 0.3f, 45 degree slope limit, used tiles, and everything else is pretty much default (like rasterizing meshes instead of colliders).
Thanks Aron :smile:

Calculate outside unity
#16

Hi

Awesome! Nice work!

The nodes that you get back are the centers of the triangles. You very likely want to use the FunnelModifier to get a smoother path on the navmesh. It simplifies the path and returns the shortest path inside the corridor formed by the nodes that the path visits.

Wow 10000*10000 units, that’s a lot. Yeah… unfortunately since it is written in C# it is slower than the Unity counterpart. Reducing the resolution obviously helps. How many different terrain objects and colliders do you have? Screenshot?
You can enable ASTAR_RECAST_BFS if you are feeling experimental (see Optimizations tab). However it might not be that part that is slowing it down. Since you (I assume) have a lot of objects, just finding all objects inside a tile might be taking up a lot of the scan time. It doesn’t do that many optimizations for fast finding of objects that are inside a tile because most users do not generate maps for worlds that contain that many tiles and it is usually done offline anyway, so the scan time has not mattered that much. For testing you can probably scan a smaller part of the world and export just that part.

#17

Thanks Aron!! :slight_smile: I am quite happy that I made it this far.
Ahhh that makes sense as to why there are SO many waypoints, it’s going from the center of each node to the center of the next, and so on… Does the FunnelModifier impact performance a lot? I would definitely want it, though, because I do want NPCs to walk in straight lines unless they’re going around obstacles.
As for the speed of scanning the scene, I think it’s single-threaded and just maxing out one core of the CPU. Is that what it’s doing? Is there any way this can be a parallel process or would that be too complicated? Having all cores work on the graph would theoretically take 1/8th the time on my machine (maybe 1/4… not sure how hyper-threading works). But I guess it’s going to end up being an off-line process, as you said, that I wouldn’t just change on the fly when I want to modify something.
I’ll get a couple screenshots together after I get some of my real work done (my job lol) but I do have over a thousand fence pieces on the map that were generated by a Unity editor function that I wrote (posts, upper and lower rails). Besides that, only three large three-level buildings exist so far, and only a couple dozen small buildings that you cannot go inside. Other than that, trees don’t even cover the whole terrain (only a fraction) and there is a HUGE 2500x2500 city wall but it’s all flat and empty inside. I have not built up the city yet. I dread what the speed will be like when that’s done (just playing the game; not even considering pathfinding).
You specifically mentioned “colliders” when you asked this question though. If the “collider” option is off but “rasterize meshes” in on, what exactly does that do? I assumed any mesh can be walkable (with or without a collider) ? That actually brings me to another question I forgot to ask. I have water surfaces that I included in the scan. Typically they should be marked as “WATER” and that layer mask ignored but, I want to do it both ways. I have certain creatures that can walk on water (pixies hover over it but follow the terrain, and water elementals can run right over it). When I begin pathfinding, is it possible to set the mask flags there?

#18

Hi

Currently you cannot specify the tag of a mesh directly, however you can do a graph update after the navmesh has finished generating. See “Example Scene 2 - Terrain”. Also http://arongranberg.com/astar/docs/tags.php

I think you should be able to parallelize it pretty easily.
In the RecastGraph.ScanAllTiles method, there is one loop which loops over all tiles and calls BuildTileMesh. Each tile gets passed a Voxelize instance. This is the part that you want to parallelize. However each thread needs to get its own Voxelize instance, otherwise they will start overwriting each others’ data. A Voxelize instance is pretty heavy memory wise, so only create 8 threads or so. Do not create one thread for each tile, that will create a huge amount of overhead. It is possible that the vox.CollectMeshes (in the BuildTileMesh method) call needs to run on the Unity thread (Unity doesn’t like when you call the Unity API from another thread), but the rest should be able to run in a separate thread.

#19

The funnel modifier is pretty fast, so that shouldn’t be a problem.

#20

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?

#21

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.