[Navigation Script] FREE AdHoc Pathfinder (AHP) for vast, infinite, and Multi-Terrain sets (w/Demo)

Community Showcases
1

Greetings all,

The game I am currently developing was in need of a pathfinding script which had a small memory footprint and could work on vast (10,000^2 unit) terrains. This made baking a mesh completely out of the question and since nearly all pathfinding assets require a pre-baked mesh or mesh generated on run-time, I decided to code my own. Now I’d like to share my progress! But do note, this is still a WIP and under heavy development. :slight_smile:

My biggest question… is anyone interested in this asset for use in their project? :slight_smile:

DEMO NOW AVAILABLE!! (Scroll down to screenshots/demo section)

Free Download from Github: GitHub - mrabenhorst/AdHoc-Pathfinder: An open-source, open world pathfinder for Unity

“Free”? Is it really?
Yes, actually it is truly 100% free. You should still take a look at the license file. There are some requirements like acknowledging that you use it. But it is totally free for personal and commercial use! However, this is powered by donuts and coffee. So donations would be great. Find the donate link on Github if you would like to give back! :slight_smile:

What is AHP?
AHP (AdHoc Pathfinder) is a pathfinder based on the A* algorithm and finds a path from source to target during runtime without the need of a pre-baked mesh.

Features:

  • Pathfinding without the memory overhead of a baked mesh
  • Can be used on terrain of any size without loss of performance
  • Multi-terrain compatible (I use and recommend TerrainComposer)
  • Automatically detects terrain edges
  • Completely accessible via code (C# now, may translate to JS later)
  • Stupid simple to operate out of the box
  • Outputs raw Vector3 coordinate list rather than forcing you to use it’s own movement system

Planned features: (Which may or may not make it to release)

  • Planetary point-gravity pathfinding compatibility (I can’t afford the asset to test yet. ;.; )

  • Multi-level support for voxel terrains (I can’t afford a voxel asset to test yet. ;.; )

  • Behavior list (Patrolling, fleeing, etc)

  • Better movement behaviors

  • Better heuristics options

Current Goals before 1.0 release:

  • Speed improvements (Corutines Added 8/29/14)
  • Tag-based In-bounds/Out-of-bounds (Added 8/14/14!!)
  • Path refinement (much fewer kinks)
  • Refinement of simple movement script

What does AHP have that other pathfinders don’t?
AHP is a niche pathfinder. It is designed for people who:

  • Use massive terrains
  • Don’t want the memory overhead of a baked mesh

Because AHP generates a grid on the fly, performance is not based on the size of the terrain, rather, it is based on the complexity and length of the desired path. So if your path is 50 units long and it’s on a terrain 100x100, it will perform as fast as if it was on a terrain of 100,000x100,000 but it won’t use any more memory.

How does it work?
It accepts a maximum slope (and soon, “Out Of Bounds” and “In Bounds” tags) to create a path on command that fits the requirements.

Is it the shortest path?
Yes and No. It CAN be. For performance reasons, AHP is not designed to always return the shortest path - rather, a path that fits the requirements. However, different Heuristics will be available so the user can balance performance->accuracy as needed.

A short tour of the components:

AStar Ad Hoc Pathfinder Component:
Description: This is the backbone script of the pathfinder. It’s the only one you need to use if you plan to take the raw Vector3 coordinate list and move your gameobject via your own script.

Start Object: Optional use of assigning a starting point via game object’s transform
Target Object: Optional use of assigning a target point via game object’s transform
Start: Optional use of a Vector3 to assign a starting point (overridden by Start Object)
Target: Optional use of a Vector3 to assign a target point (overridden by Target Object)
Nav Resolution: This is the precision of the navigation grid. Smaller = more precise pathway, longer time to generate a path. This must be smaller than the smallest gap in terrain.
Max Angle: Maximum angle over which a valid path can traverse
Search Timeout: Automatic timeout of a search. This is extremely useful for random location pathfinding where you do not know a path exists at all. If you add a timeout, it will prevent the entire valid area of the terrain (potentially enormous) from being scanned for a point that can never be reached.
Use Optimal Heuristics: A temporary variable which will be changed. Right now only two Heuristics are used: Manhattan Cube (3D version of Manhattan Block) and Distance literal (Vector3.Distance). Checking “true” uses distance literal. More variations will be added.
Raycast Height: 2x maximum terrain height differential
Debug Mode: True = shows debug objects during runtime
Debug Open List Object: Object to show open list locations
Debug Closed List Object: Object to show closed list locations
Debug Path Object: Object to show final path locations


AStar Ad Hoc Simple Movement
Description: This is a VERY simple movement script that uses “MoveTo” to move from one coordinate to the next. It automatically generates a path to the target on command, can be paused, resumed, and stopped on the fly via code.
Speed: Movement speed in units/sec
Is Moving: Publicly exposed variable for whether the object is moving
Debug mode: If true, on start the script will cause the object to move to the Target GO
Target GO: Game object which the script with navigate to. IMPORTANT: The gameobject itself must be disabled.

Screenshots/Demo:

Demo 0.2:
To view the demo, please follow this link (full-screen view is suggested)

Notes about the demo:

  • The demo terrain is a 3x3 terrain of 1000 units each (9000sq units total)
  • The navigation did not require ANY pre-baked mesh or pre-loading
  • The navigation “timeout” is 10 seconds. That means, if the target location is valid but 10 seconds have elapsed since attempting to find a path, it will self-terminate. Otherwise if you have a massive (or infinite) terrain, it may never stop looking.
  • The red terrain splat is designed to give visual indication of where the slope >50 degrees. However, it is not 100% accurate because of the spat resolution on the terrain. So if you find you’re navigating over red splat at times, it may very well be just barely valid but the splat doesn’t indicate it.
  • AHP currently runs by way of using Corutines. You can control the CPU-usage vs. framerate impact of AHP running on the main thread by altering the cyclesPerFrame (CPF) variable. Larger numbers compute faster but hit framerate performance more. I’ve found that an ideal CPF value is around 20 (which the demo uses). But this can be set at any time - even during runtime.

Finally, the terrain here was randomly generated using TerrainComposer’s Island sample script and textured with RTPv3. The Elk model was made by Jenna Jones by request (she did awesome!) Thanks to all of them! :slight_smile:

Screenshots:
Note: These are taken in debug mode.
Red = Closed list
Blue = Open list
Green = Path found

Pathfinding on a 100x100 terrain with obstructions. This took less than a second

Pathfinding on a 4000x4000 terrain set (2x2 of 2000x2000). This took a little more than a second:

1 Like
2

Reserved.

3

Looking forward to its development :slight_smile:

1 Like
4

Interested.

1 Like
5

What does that mean? Also project looks AWESOME

1 Like
6

John G., MotuProprio, calmcarrots: Thanks for your interest and encouragement!

That just means I am holding on to the second post in case I need it for other information later on. :slight_smile:

1 Like
7

Could this be used with a infinite terrain script?And can this path find around buildings and other objects you place on the terrain?This would be great along with a infinite terrain script.Along with the features I asked a question about.

8

Yes and yes. This does not need to know anything about the terrain at all so infinite terrains are no problem. Buildings would need to be tagged as non-walkable at very most. :slight_smile:

9

But could it work with the free version of unity?What i like about this idea is you could go anywhere and the enemy will follow you.I like this idea of that it could be used along with a infinte terrain script.I did found one on youtube and still have it.

10

Interesting.

How are you building your graph? How have you decoupled graph size from the performance of the algorithm? I’d also say that 3 seconds is a long time to get a path - do you have mechanisms to get an agent moving along the path before it’s complete in order to mitigate this? I’m also assuming it’s threaded?

11

If it is free i will get it.I was thinking about using a teleport script for obstacle avoidance.Until i saw this.

12

@Hard_target
This will work in unity free. I intend to keep it that way. :slight_smile: I don’t know about the cost of the pathfinder asset, but it may be a nominal fee (which will help support my game development).

@KelsoMRK
The performace hit is a necessary tradeoff for the capability. You wont be able to use this for all games, but it will allow, otherwise impossible, pathfinding to occur in special cases. I definitely agree that 3 seconds is a long time to create a path and is not intended to be the actual time. Currently, this uses arrays and is single-threaded. The final product will use a much more efficient data structure (similar to a Binary heap) for node storage and will be multi-threaded.

Edit: Forgot to add that, yes, I am working on allowing the agent to start moving before the path is completed (as a toggle). There are also other ways to speed up pathfinding that I will be implementing such as scheduled paths (i.e. predetermining a new path while not finished the current path) which will make successive paths seamless in timing.

You might say that I haven’t yet trimmed the fat off the code because it isn’t working 100% how I would like at this point. :slight_smile:

I thought I might also state that this is not specifically being developed for biped characters either. My goal is to make the movement work for both biped and quadruped characters (as my game specifically needs both).

13

The first of two speed optimizations have been implemented. Because this optimization was aimed at large scale pathfinding, it’s impacts are nearly exponential with increasing size. The time it took for the 4000x4000 sample path was a bit over a second. (Ironically, housekeeping is now more costly than searching)

There will be at least one more performance enhancement implemented: multithreading. I expect this to take a day or two. After that, path smoothening and then working on refining the movement scripts.

As a side, I have been putting a lot of thought into using this for point-gravity planetoids. I may not fit that into release, but I am curious how many people would be interested in that type of pathfinding. Are there any existing pathfinders that work on planetoids?

Time for sleep.

14

That would be a great idea.I love those type of games.

15

Update!

I have introduced some more optimization and tagged obstructions! These are obstructions which would otherwise be an acceptable pathway but are manually set by the developer to be out of bounds. You can set an object as an obstruction by setting the “Out of Bounds Tags” variable in the pathfinder script to the tag of the objects that are obstructions. Below are some screenshots showing this in action:

This is an example of a normal pathway without tagged obstructions. You can see that it is possible (using the slope criteria of the pathfinder) to navigate to the left of the blue bridge.

What if we decided to fill the lower area with water? (Big thanks to RTPv3 for beautiful water!) The water plane is, otherwise, a walkable plane. In order to prevent the pathfinder from using it, we tag the water. Lets say, the tag is cleverly named “Water”. Since all water is “out of bounds” from navigation, you add “Water” to the “Out of Bounds Tags” variable in the pathfinder. The result is below:

Now the pathfinder is forced to use the bridge instead of the water or the surface below the water level.

This also applies to objects. What if the pathfinder is deciding the path of a very heavy truck. We don’t want the truck to go over bridges that can’t support its weight. So we would tag any weak bridges a tag, “Weak Bridge” for example. Then add “Weak Bridge” to the “Out of Bounds Tags” variable in the pathfinder script to prevent it’s use as in the case of the red bridge below:

Note that tags are checked before every run of the pathfinder. So it is possible (and likely) that you will change tags programmatically. As long as they are tagged before the pathfinder script attempts to find a path, you can change anything you want as much as you like.

1 Like
16

I would love to see a video of this in action.

17

Getting much better, any approx release date? With regard to bridges would it be possible to get the agent to stick to left/right sides, to simulate traffic lanes?

18

@Hard_target
I am planning to post an interactive in the next couple days or so. So that might be even better! :slight_smile:

@John-G
Right now that isnt an option. However, it might not be difficult to do. Unlike most pathfinders, I have coded this in such a way that passage from one grid cell to another can be blocked not only based on parameters of the target block but based on parameters of the source and target. This means that you could restrict access based on direction. This might be useful for two bridges side by side. If the bridges are North-South, you could restrict passage on one bridge to only northbound and the other only southbound.

19

That would work, one could basically split a bridge down the middle to have 2 objects pushed together to make one bridge. One half tagged south the other tagged north.

20

Exactly. It would be like having the blue bridge one way and the red bridge the other way rather than completely out of bounds like in my example. :slight_smile: