TRA* Pathfinding

[MathiasDG]

Hello there!

I think its about time to show you guys what i’ve been working on.

It is a very powerfull and easy to use pathfinding, based off TRA*, wich stands for Triangulation Reduction A*.
For those of you who dont know, TRA* is a quite fast pathfinding techique as it uses only a few of the mesh triangles to search with the A* algorithm. These triangles can be seen in pink on the next picture.

So this is basically a very fast pathfinding code. A test was run on that terrain wich had a resolution of 512x512 and a error tolerance of 1, wich means the actual generated mesh is never more than 1 pixel away from the actual mesh. Note that the mesh does not depend on the map size, but on the map resolution. So a small sized map with 512x512 resolution would have the same mesh resolution as a big sized map with 512x512 resolution. The above mesh was generated in 5 seconds.
The test results of the test are shown in the next picture.

The y-axis on the graph shows the time in ms it took for the code to find the path, and the x-axis show the length of the path. Starting and Goal points were randomly chosen. Map size is 64x64 world units, so if the x-axis shows 30 on the path length, it means the path has 30 world units of length.

The average time it took to find a path is somewhere about 0.4ms, and the average path length requested about 55 world units.

So yeah, thats fast, considering it can run on background threads, it can find a lot of paths in a single frame without overloading the main thread at all.

Now about the asset.

The asset is very, very easy to use, it comes with a window that has three options : error tolerance, max slope and minimum area.
Other than setting that up, the user has only to click “Generate Mesh” and it is all done. No coding needed, not dragging stuff around no nothing.
Of course you will have to write a line down on your code to tell where you want your agent to go, something like : Agent.SetDestination(Vector2 position).

Right now the mesh generation is not considering user placed obstacles (GameObjects), but i’l be working on that pretty soon, the code is already structured to support that, i just need to really write it down. I plan on allowing objects to be marked as either obstacle, or traversable obstacle, to allow bridges, ramps and such. Like i said, the code structure already supports that, i just need to put some geometry codes down.

This is mainly a 2.5D mesh, so it works on unity 3D projects, i havent tested it out on 2D, the only difference though would be the mesh generation process, wich would not take a map, but sprites and whatnot. I’m not sure if i am going that way though.

I mention Vector2 because the y coordinate of the vector 3 doesnt matter for the mesh itself, it ignores the y coordinate during its calculations and returns a Vector2(x,y) and a height value, wich would be the y value for unity’s vector3.

Some mesh features :
QueryPoint(Vector2 point, float radius) → Returns the closest point on the mesh that is valid for that radius.
QueryCollision(Vector2 point, float radius) → Tells whether or not that point collides with something.
QueryVisibility(Vector2 pointA, Vector2 pointB, float radius) → Tells wheter or not the pointB can be seen from the point A keeping radius distance from obstacles.
QueryRandomPoint() → Returns a random point of the mesh. (excludes points over obstacles)
QueryPath(Vector2 A, Vector2 B, float radius) → Returns a path from A to B keeping distance radius from obstacles.

Pathfinding features :
-Path contains rounded corners around obstacles (you actualy dont have to worry about dealing with this on your code, the Path has a method that returns the next velocity the agent must take, just ask for it)
-If the starting point of the path is not on a valid point for the agent, a path will be found from the closest valid point to the start to the goal.
-If the goal cannot be reached, a path will be found to the closest reachable point to the goal.

The image above shows a path whose goal could not be reached.

Other than that, there are two or three advanced settings that can be changed :
-Max Iterations → Maximum number of paths to look for before exiting the A* search loop.
-Length Ratio → Allows the A* to quit the loop if it knows there is no more possible paths shorter than the best one found so far multiplied by this value
-Heuristic → Two options here, a greedy heuristic, that finds the first path faster, or a normal heuristic wich finds the optimal path faster.

These advanced settings dont really have to be changed, i ran tests to find out some average optimal values, but they’re there just in case someone wants to mess around with them.

There is not really a whole lot of things to show other than these, i just wanted to show you guys what i’ve been working on and ask for possible suggestions.

I already plan on adding the Agent script and easy to use methods with this, where the user would just ask for the agent to go somethere and the code would take care of it.
I might also add some Agents behaviour, such as follow other agents, chase agents and stop at distance with visibility, patrolling, maybe some mix up some AI for cahse and move behaviours.

Oh, and one last thing, i am probably adding some type of RVO for collision avoidance, i already have it pretty much coded, but its not integrated with the pathfinding and the mest just yet, i’ll have to work on that.

I’d love to receive some suggestions if you guys have any!

Post got longer than i expected, i guess i’ll just make a video next time!

Thank you for your attention!

TL : DR

-Very very fast and easy to use pathfinding code.
-Asking for suggestions!

[im1]

sounds interesting, i wonder how the engines i already have do this. perhaps they already doing it this way. who knows, i should read the manuals sometime

so what about support for native threading. nice if did its magic on some other thread so basically you make call to get path and it then async calls you back when its got the path without you having to wait for it.

what about pooling now that i think about it keeping like n most popular paths so you dont have to recalculate them again?

also be nice to have api to cancel a path search like when for example mob dies they no longer need the path they may have been searching for.

so about how much and when you think will have some working webplayer demos and it in the asset store, hopefully including full source code.

anyways those are sort of the thing i run into when using a*

make sure it has good way to save and load meshes.

what about realtime mesh calculation/recalculation preferably on other native thread(s). so it could be used to calulate mesh for pathing realtime like when map changes ingame. sort of important when you have like modern voxel based games where lots can change.

and speaking about voxel what about support for voxel where you have complex geometries, paths like not just above ground, but below, like in caves.

anyways those are sort of the stuff ive run across.

[MathiasDG]

@im

sounds interesting, i wonder how the engines i already have do this. perhaps they already doing it this way. who knows, i should read the manuals sometime

I cant really tell specifics, but open scource pathfinding codes for games out there are usually polygon oriented. It’s just a lot easier to write the code, and it should not be slower than triangle based pathfinding.
The difference is in the abstraction, generally speaking, abstraction speeds up the A*. So if one were to write a code with abstract polygons, it would be just as fast as a code with abstract triangles.
Just in case you’re interested in other abstractions, you can search for PRA pathfinding.

@im

so what about support for native threading. nice if did its magic on some other thread so basically you make call to get path and it then async calls you back when its got the path without you having to wait for it.

Yes, i plan on making it work on the background threads. I’m currently using a singleton that runs on the background and assigns the path to the agent when complete. This singleton is easily expandable to multiple workers, but i’m not really into that right now. Will do it as i get closer to finishing this project.

@im

what about pooling now that i think about it keeping like n most popular paths so you dont have to recalculate them again?

Thats an interesting idea, i’m adding that to the lists of possible improvements.

@im

also be nice to have api to cancel a path search like when for example mob dies they no longer need the path they may have been searching for.

Well thought, will definatly do this.

@im

so about how much and when you think will have some working webplayer demos and it in the asset store, hopefully including full source code.

I dont really plan on releasing it before it is as good as i’d like it to be, so it might still take some time to get into the asset store. A web player demo however, is alot eassier since it is already working pretty well, so i’d just have to put things toguether and build the demo. Can’t really tell exactly when i expect to do that though.

@im

make sure it has good way to save and load meshes.

As it is, once the Generate Mesh button is clicked on the window, a Monobehaviour is automatically attached to the terrain, and a ScriptableObject called MeshData is automatically created and attached to that Monobehaviour. Serialization is done automatically within the MeshData code everytime a scene is saved / loaded, so saving the mesh is automatic.

@im

what about realtime mesh calculation/recalculation preferably on other native thread(s). so it could be used to calulate mesh for pathing realtime like when map changes ingame. sort of important when you have like modern voxel based games where lots can change.

I am not sure i am going into that, its definatly on the improvements list, let me explain real quick how real time TRA mesh updates are usually done.

1. We desire to insert / remove a polygon from the mesh.
2. Foreach vertex in the polygon → insert vertex in the triangulation.
3. Foreach edge in the polygon → insert constraint in triangulation.

These steps are common to every triangulated mesh. TRA needs an additional step :

4 : Foreach affected triangle → update abstract graph element connected to that triangle.

This additional step isnt really very costly performance wise since repairing the abstract graph can be done locally, but i havent thought about how to code that just yet, and that’s why i’m can’t tell whether or not we’re gonna have this feature.
There are also some other complications with inserting polygons, because the code i wrote works with specific polygons set, where polygons are not allowed to intercept each other. So i’d have to work around this if the user could insert any polygon he wanted to into the mesh.
The first three steps are already part of the initial mesh generation, so they’re no big deal.

@im

and speaking about voxel what about support for voxel where you have complex geometries, paths like not just above ground, but below, like in caves.

Thats definatly possible, and allowing that would require a change mostly on the mesh generation process, the pathfinding itself would not change at all. I think i’ll look into that when i’m done with the other basic features.

Thank you very much for your suggestions!

[im1]

hi thanks for responding to my post so quickly and with such detail.

wanted to ask couple more quick ones…

what about dynamic obstacles, do you deal with them

and what about bridging/navigation between two nav meshes which is something required if yo have like generated scene made up of parts each with their own sub nav mesh

finally what i mean by recalculate nav mesh realtime is not as much about the terrain changing but being able to generate the nav mesh realtime since the scene is entirely procedurally generated like in one of those dungeon generators or procedurally generated worlds where the it does not really change other than dynamic obstacles, but scene is not known until it is generated.

[MathiasDG]

@im

what about dynamic obstacles, do you deal with them

If by dynamic obstacles you mean other agents (or obstacles that are moving, that can be tagged as agents), i think i mentioned on the original topic i have the RVO code working, just need to integrate it with the TRA.

If you mean obstacles that are not constantly moving or cannon be represented by circles, then they are treated as mesh changes that need to be made. For example, if a door is open, the door obstacle needs to be removed from the mesh and the mesh needs to be updated.

@im

and what about bridging/navigation between two nav meshes which is something required if yo have like generated scene made up of parts each with their own sub nav mesh

Connecting two meshes can be done with off-mesh links. I think i can do that. I will definatly add it to the things to improve list.

@im

finally what i mean by recalculate nav mesh realtime is not as much about the terrain changing but being able to generate the nav mesh realtime since the scene is entirely procedurally generated like in one of those dungeon generators or procedurally generated worlds where the it does not really change other than dynamic obstacles, but scene is not known until it is generated.

I think that would be achievable by either calculating a new mesh for each room, each time a room is generated, and then connect these two meshes using off-mesh links as mentioned before.
Another option would be to allow not only to insert obstacles online, but to also allow mesh boundary extension (walkable area). This option would provide continuous online mesh extension if your level is continuously being generated. A better option if your infinite level is not generated by “rooms”.

This second option though, would require the user to call some more methods, such as ExtendBoundary() and AddObstacle() for each obstacle you are adding, so you would need to know what you’re adding.

Once i get the real time mesh updates working, implementing the second option would not be difficult, so this could be a future feature.

Thanks for the suggestions again!.