Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

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

Discussion in 'Works In Progress - Archive' started by Kivak, Aug 7, 2014.

?

Should this be available for public use?

  1. Yes, but only for free

    35.5%
  2. Yes, but I wouldn't use it

    9.7%
  3. Yes, I would pay a small fee for it

    61.3%
  4. No, nothing useful here

    0 vote(s)
    0.0%
  5. Maybe... (Please comment)

    0 vote(s)
    0.0%
Multiple votes are allowed.
  1. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    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. :)

    My biggest question... is anyone interested in this asset for use in their project? :)

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

    Free Download from Github: https://github.com/mrabenhorst/AdHoc-Pathfinder

    "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! :)

    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! :)

    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:

     
    Last edited: Sep 12, 2014
    crag likes this.
  2. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    Reserved.
     
  3. John-G

    John-G

    Joined:
    Mar 21, 2013
    Posts:
    1,122
    Looking forward to its development :)
     
    Kivak likes this.
  4. MotuProprio

    MotuProprio

    Joined:
    Sep 24, 2013
    Posts:
    144
    Interested.
     
    Kivak likes this.
  5. calmcarrots

    calmcarrots

    Joined:
    Mar 7, 2014
    Posts:
    654
    What does that mean? Also project looks AWESOME
     
    Kivak likes this.
  6. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    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. :)
     
    calmcarrots likes this.
  7. Hard target

    Hard target

    Joined:
    Oct 31, 2013
    Posts:
    132
    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. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    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. :)
     
  9. Hard target

    Hard target

    Joined:
    Oct 31, 2013
    Posts:
    132
    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.
     
    Last edited: Aug 23, 2014
  10. KelsoMRK

    KelsoMRK

    Joined:
    Jul 18, 2010
    Posts:
    5,539
    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. Hard target

    Hard target

    Joined:
    Oct 31, 2013
    Posts:
    132
    If it is free i will get it.I was thinking about using a teleport script for obstacle avoidance.Until i saw this.
     
    Last edited: Aug 23, 2014
  12. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    @Hard target
    This will work in unity free. I intend to keep it that way. :) 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. :)

    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. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    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. Hard target

    Hard target

    Joined:
    Oct 31, 2013
    Posts:
    132
    That would be a great idea.I love those type of games.
     
  15. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    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.
     
    John-G likes this.
  16. Hard target

    Hard target

    Joined:
    Oct 31, 2013
    Posts:
    132
    I would love to see a video of this in action.
     
  17. John-G

    John-G

    Joined:
    Mar 21, 2013
    Posts:
    1,122
    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. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    @Hard target
    I am planning to post an interactive in the next couple days or so. So that might be even better! :)

    @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. John-G

    John-G

    Joined:
    Mar 21, 2013
    Posts:
    1,122
  20. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
  21. John-G

    John-G

    Joined:
    Mar 21, 2013
    Posts:
    1,122
    Excellent, that would work perfect then. :)

    To extend on the question can one assign a tag to prefered routes. ie tag a road so that agent will choose to navigate via road in preference to terrain where possible, that way would move from road to terrain if blocked and back to road when possible.
     
  22. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    Yes. Although there is a caveat. Preferring one route over another is somewhat subjective. In order to make it objective (I.e. computer understands) you need to produce a biasing value.

    Lets say one route would take you 10 minutes. The other would take 5 minutes. It is the same distance, but one is faster. The speed preference is to use the 5 minute route. But in the pathfinder distance is the only factor. So there needs to be a bias multiplier which makes one route appear "shorter". This multiplier would take the place of a pseudo "speed" (given that the speed of the agent actually doesnt change). So for the preferred route you would add a bias value of 2 to make it twice as fast.

    This is all well and good until you start using terrain (as my project does). I only have rocks, cliffs, and water that is offlimits. But you brought up a great point. It would be more efficient for someone to walk across grass than mud, or field rather than forest, etc. In this case, i would set certain terrain splat textures to have different bias values. I think that sounds very useful!
     
    John-G likes this.
  23. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    I forgot to answer your first question! I would like to have a couple testers before anything goes live. Ideally testing in a week or two. Followed by testing review, then release. I want this to be really easy to use and so it is going to take a little time to add a bit of polish so people feel really good with their purchase. :)
     
  24. John-G

    John-G

    Joined:
    Mar 21, 2013
    Posts:
    1,122
    Nice one, the bias multiplier should do the trick. That way a vehicle could have a higher bias then a character on foot.
    If the character is walking it will choose the more direct path across the terrain, while if it can use a vehicle it will use the road as it is faster then travelling across terrain. :) Testers... cough... cough... ;)
     
  25. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    I am happy to announce the first demo of AHP. Read about it below (and in the main post):

    Demo:
    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.
    • In this demo, searching uses the main thread and will lock your movement. Note that this is NOT the final usage. :)
    • 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.
    Finally, the terrain here was randomly generated using TerrainComposer's Island sample script and textured with RTPv3. Thanks to both of them! :)
     
    John-G likes this.
  26. Hard target

    Hard target

    Joined:
    Oct 31, 2013
    Posts:
    132
    Will people be able to make games that they can give away with this?
     
  27. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    I am not quite sure what you mean. As long as the source code isn't given out, you could use this for any game/app you want. :)
     
  28. Hard target

    Hard target

    Joined:
    Oct 31, 2013
    Posts:
    132
    I mean if you upload a game on a websight for anyone to play.
     
  29. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    If I understand the question right, this would be fine. If you buy the code you can use it for anything you want. This will be totally in C# so you can edit the code if you want too.
     
  30. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    Sorry for the lack of updates this week. I have been mainly focused on developing my game (in signature). This weekend, expect updates featuring an out of bounds texture detection system - optional, of course.

    No feedback on the demo so far, any thoughts?
     
  31. Hard target

    Hard target

    Joined:
    Oct 31, 2013
    Posts:
    132
    It works great so far.But of coarse some places need to be made unwalkable like steep inclines and buildings you place on the terrain.But it would be great if you could modify it to work with procedurally generated environments and randomly generated environments as well.Could be even better if you could make it work with minecraft type videogames and ones that use the marching cubes algorithm.
     
  32. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    All of those things are currently possible at this moment except for minecraft-type environment (which would probably work with a little tweeking) and marching cubes. The minecraft environment is more difficult to work with because the slope of one block to the next is 90-degrees. So the slope test would need to be modified.

    I'm unfamiliar with marching cubes (do you mean marching squares?). This was designed around A* specifically because of the ability to modify it for this usage. I don't know a lot about marching squares, but I don't know how easily that can be modified to fit these requirements.

    A note about randomly/procedurally generated environments... generated on the fly:
    Currently... as long as the terrain/environment exists at the time you ask the agent to find a path, it will find a path using the terrain/environment. This does not mean the terrain has to exist at the time of the agent's creation. So terrain/environment could be generated between the agent's creation and the request for a path and the agent will use that newly generated terrain.

    HOWEVER
    , You could actually go even further... with some slight modification to the "Walkable" test function, you COULD generate terrain as it tests. So, in theory, you could ask an agent to find a path to a location which doesn't exist yet as long as you generate the terrain on demand of the agent's script. :)

    This might be particularly useful for usage when the player decides to investigate unknown space. If the player indicates that they want to go from 2D coordinate 0,0 to 100,100 and only 50 units in each direction have been procedurally generated, the script would navigate to the ideally best location nearest to 50,50 and then request the generator to generate another chunk of land. It would then navigate across that chunk and continue to request new chunks as needed.

    As a side, this may not even be a feature limited to procedurally generated environments. If you're environment is MASSIVE you may only want to keep a few chunks active at one time to save memory. This would work perfect.

    Yet another thing that this can do that baked-mesh or runtime-mesh pathfinders couldn't dream of. :)
     
    Last edited: Aug 23, 2014
  33. Hard target

    Hard target

    Joined:
    Oct 31, 2013
    Posts:
    132
    Look up marching cubes algorithm on the internet.Then you will see what I mean.
     
  34. ludiares

    ludiares

    Joined:
    Jul 14, 2011
    Posts:
    242
    I must say that the performance in the pathfinding itself is awesome. 3 Seconds for a path that may be half a kilometer, or one kilometer is awesome. I've tried other pathfinding systems, and this one is much much better. I would buy it pretty sure.
    Keep working on it
     
  35. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    I will have to check into it further. :)
    I wont limit this to A* if I can find another that works better. But the system requires some fancy footwork to work.
     
  36. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    Very glad to hear it! I put quite a bit into this and will definitely continue.
     
  37. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    Update!!

    Because of the needs of my own project, I have had to shelve the terrain material test for a later date. In the meantime, I have been working on something I know everyone will like...

    Asynchronous....sorta.
    AHP is now pseudo-asynchronous! You'll have noticed in the last demo piece that the entire game froze while calculating the path. This is not acceptable for any game. However, this needs to operate at least partially on the main thread due to the way it functions. This presented a bit of a challenge since most Pathfinders actually use background and multi-threading.

    Since background and multi-threading were not viable options, I ended up using Corutines. A corutine is a Unity-specific sort of pseudo-asynchronous function/class that allows methods to be shelved mid-run until beginning the next frame. This actually allows for some awesome scripting without using the Update() method (which I actually found very helpful!). So check out Corutines if you don't already know what they are.

    Pros and Cons
    Unfortunately, Corutines have their limitations. Since the code is still executed on the main thread, it is still vying for a piece of the CPU pie - metaphorically speaking. Also, waiting for the next frame to come up could also be quite a long time. Since you can't have perfect resolution of these two opposing forces I built in a regulator variable called "cyclesPerFrame" (CPF from now on).

    The CPF regulator variable indicates how many cycles of pathfinding should be calculated between frames. You can think of this as "How many dots on the path get calculated every frame?". In reality, each cycle of the pathfinder determines the validity of the 8 grid-squares directly adjacent to the active search square and moves to the best one. Therefore, with a CPF of 1, you could expect 8 queries between each frame - that's pretty slow at 30 frames per second (lets be conservative). But, the overall processing time is VERY fast (we're talking like a fraction of a fraction of a fraction of a second). You could expect approximately: 1*8*30 = 240 queries per second. If you boosted the CPF up to 200, you'll be calculating at a whopping 200*8*30 = 48,000 queries per second! But you'll feel the lag...

    There are, however, reasons why you would use one strategy over another. For example: If units are spawned at the scene's load, why not use 100% CPU time to do it? Crank the CPF up to 1000+! But when the game is running, make the unit pre-calculate its next ideal move while still moving. This can be done (factoring in distance) around 20 CPF and not have a performance hit overall.

    Target Queuing:
    This is one feature I am excited about for my own game. Generally speaking, my NPC wildlife will not be affected greatly by immediate threats (unless players are actively hunting). They will be moving about the landscape in realistic behavioral fashion formed by abiotic (landscape) factors. I.E. "Go graze", "Go drink", etc. These can be queued up as the behavior mapping will pre-determine it's next movement. AHP will be able to add and remove targets from a queue that will be pre-calculated by the pathfinder. This is especially handy for environments that don't change often. But there will be a "proofing" technique which will check to make sure the pre-calculated path is still viable once dynamic obstructions are fully supported.

    New demo!
    Obviously this requires some showing off... I have created a second demo which illustrates the Corutine variant of AHP using a magic number of 20 CPF. Notice that the game is now still actively playable while the pathfinding is occurring. I also added a nice Elk model with animations to illustrate the use of the pathfinding. Do note that the movement script isn't completely smoothened at this point. So the Elk is a little wobbly. ;)

    Demo is here: Clicky the linky!
     
    ludiares likes this.
  38. FBTH

    FBTH

    Joined:
    Jul 25, 2012
    Posts:
    272
    INCREDIBLE! :D Looking forward to this!
     
    Kivak likes this.
  39. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    Update!!

    I have good news for everyone! AHP will be released in a beta version in the next couple days (aiming for tomorrow, but I don't know yet). I will explain more about "beta" when it is released and what my goals are before final release of 1.0.

    As for pricing, I think you all will appreciate the cost. Even though there was support of a paid product, I have decided that AHP will be released as an open-source script set available through Github and free on the Asset store (pending 1.0 release). I will explain more about how they will interact, but the basic concept is that the github version will contain versioned builds and the asset store will just include the stable editions at regular increments. Also, I have decided to use the GNU license, which is virtually unlimited. This license does allow you to use AHP in any type of project you want. I do ask that you include somewhere that your project uses AHP - details will follow.

    My reason for going open-source is twofold: I have hope that people will contribute to this project and make it even better than it already is. As the only product on the market that does this, I am confident it will be utilized and get even better over time. I also wanted to offer this as an affordable pathfinding solution for people using vast worlds and infinite terrain (as I would love to see more games like this). Please contribute if you can and make awesome games - seriously... make more open worlds... eventually AHP will support point-based gravity. I want to walk on planets, OK? :)

    More soon!
     
    FBTH likes this.
  40. Hard target

    Hard target

    Joined:
    Oct 31, 2013
    Posts:
    132
    Would you like a free infinite terrain script to test it out on?
     
  41. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    Hi everyone!

    Sorry to have gone dark the last few days. It's been a rough time family-wise at the moment so it's been hard to actually do anything about this project. I did finally get it up onto Github! However, I don't have any walkthrough videos at this moment like I had hoped. It should be fairly easy to understand and add in. But if you have questions, feel free to respond to the thread. :)

    Here it is! https://github.com/mrabenhorst/AdHoc-Pathfinder
     
    jason-fisher and ludiares like this.
  42. jason-fisher

    jason-fisher

    Joined:
    Mar 19, 2014
    Posts:
    133
    Kivak, thank you for releasing your wonderful work. I am working on a game that uses instanced voxel areas on a large cubed-sphere planet terrain and have not slept the last two nights trying to wrap my head around the right third-party pathfinding solution to embrace (and hack to death).

    Glancing over the source quickly, it looks like in order to support spherical navigation, we would need a new distance evaluator? Haversine?

    Code (csharp):
    1.  
    2. private static float haversineDist(Vector2 pos1, Vector2 pos2, float radius)
    3.   {
    4.     float dLat = Mathf.Deg2Rad * (pos2.x - pos1.x);
    5.     float dLon = Mathf.Deg2Rad * (pos2.y - pos1.y);
    6.  
    7.     float a = Mathf.Sin(dLat / 2) * Mathf.Sin(dLat / 2) +
    8.       Mathf.Cos(Mathf.Deg2Rad * (float)pos1.x) * Mathf.Cos(Mathf.Deg2Rad * (float)pos2.x) *
    9.       Mathf.Sin(dLon / 2) * Mathf.Sin(dLon / 2);
    10.     float c = 2 * Mathf.Asin(Mathf.Min(1, Mathf.Sqrt(a)));
    11.     float d = radius * c;
    12.  
    13.     return d;
    14.   }
    15.  
    And then to take the up vector from either the terrain or the agent to use in slope calculations?

    In this case, the planet is large enough that it appears mostly flat at the character level.

    I think we would also need to normalize the neighbor positions?

    Code (csharp):
    1.  
    2. // Predetermine the 8 surrounding node positions to prevent recalculation
    3. TLVector = new Vector3(-navResolution, 0, navResolution);
    4. TCVector = new Vector3( 0, 0, navResolution);
    5. TRVector = new Vector3( navResolution, 0, navResolution);
    6. MLVector = new Vector3(-navResolution, 0, 0);
    7. MRVector = new Vector3( navResolution, 0, 0);
    8. BLVector = new Vector3(-navResolution, 0, -navResolution);
    9. BCVector = new Vector3( 0, 0, -navResolution);
    10. BRVector = new Vector3( navResolution, 0, -navResolution);
    11.  
    Am I missing something?
     
    Last edited: Sep 29, 2014
    Kivak likes this.
  43. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    @jason.fisher

    You're very welcome! I am glad someone is thinking about using it!

    I am actually very interested in modifying it to work on planetoids and have put quite some thought into it. You are correct about needing to use the Haversine formula to determine distance. Although, it is quite computationally expensive. A better heuristic would be calculating the linear distance. It won't be exact, but it will still keep points at the appropriate order.

    The one thing I believe you are missing is adjusting the raycast. Using a point-gravity planetoid you will need to add the center coordinate and maximum radius of the planetoid into the pathfinding model. You'll then want to structure the grid based on latitude/longitude (which is the second code block adjustment you mentioned) and also direct the raycasts from the maximum radius toward the center of the planetoid. Right now, the raycast is vertical, which is fine for planer terrains but will only work for the 90N latitude coordinate on a spherical planetoid.

    Currently, the grid is based on a meter "navResolution" variable. I would advise changing that to a degree resolution variable (which, using the radius, you can determine meter resolution or visa versa). Then alter the predefined 8-node positions to be determined based on the current lat/lon with the proper degree resolution displacement.

    Hope that helps! I'll also see if I can dig into this some more code-wise... feel free to ask any questions! :)
     
    Last edited: Sep 30, 2014
  44. jason-fisher

    jason-fisher

    Joined:
    Mar 19, 2014
    Posts:
    133
    Do you think there would be a benefit to caching walkable areas into a bounding-box-based quad tree? You could then request a chunk of data for a grid-aligned bounding box in the 'upcoming' path prior to falling back to a ray cast?

    Thinking of a populated planet where 1,000 units may be in a visible radius, but another 5,000 may be moving out-of-sight. Eventually the populated areas should get cached, with a lazy timer that queues cache flush on certain triggers.

    Thinking about this some more .. extended into an octree, this 'cache' could potentially allow multi-layered/3D navigation while keeping a simple grid during the actual processing.

    Basically, when you are doing the ray casting, you identify the 'layers' that the ray hits, caching the results into different 'layers' (bounding areas) in the octree. You know the layer the player is on, so you can determine which they can reach using the cell next to the multi-layered cell. You then make the look-up into the octree more intelligent by giving it the ability to choose the appropriate 'layer' and having it return a flattened grid for the actual movement. There may be a need for some kind of transition trigger.. but that is for a different conversation.
     
    Last edited: Sep 30, 2014
  45. jason-fisher

    jason-fisher

    Joined:
    Mar 19, 2014
    Posts:
    133
    Getting closer ..
    • Still using XYZ coordinates
    • Scanning neighbors based on (currently) fixed rotation steps from the source, using the planet's center as the pivot
    • Snapping all vector comparisons to a 0.5 navResolution
    • Including Y in the hash (all snapped)
    • Lerp without clamp from the planet's center to 'above' the source position. I am hoping this can be used to allow multi-level/indoor pathfinding
    • Using line casts from lerped surface/room height toward planet's center
    Still need:
    • Rotate and snap feet to surface instead of the snapped grid location
    • Base slope tests on planet -> toPosition angle
    • Base neighbor rotation set step size off of ratio of distance from planet center to node for proper scaling
    • Lerp is to 1.2f in my test, this needs to be based off of the agent's height/minimum walkable ceiling in a room -- maybe even add an option for a test ray upward that could be used in tight/organic spaces?
    • Switch to Physics2D.Linecast because we want to stop at the first hit?
    • Add flat surface 'emulation' and transition? -- because we are using X/Y/Z still, I think we could also dynamically transition from a flat surface to a spherical one (stepping off of a spaceship with 'simulated gravity' onto a planet)
    • Test with larger planets
    Will share everything in a github fork once I get a bit further early next week.. I think some of these adjustments will help with voxel world compatibility also.

    Thanks again for sharing your work here. This is exactly the start I needed.


     
  46. jason-fisher

    jason-fisher

    Joined:
    Mar 19, 2014
    Posts:
    133
    Is your intention that both the Pathfinding and Agent script exist on every agent? Maybe the 'Pathfinding Query Engine' should stand-alone, so multiple agents can share a hash cache?
     
  47. Kivak

    Kivak

    Joined:
    Jul 13, 2013
    Posts:
    140
    @jason.fisher

    Wow this is incredible! I'm greatly appreciative to your contribution to this project. I wish I had been able to help a bit more (my dad is late term brain cancer in hospital/hospice so I'm limited on time right now). Please let me know when you have code ready to merge into the master branch and I'll make it a priority to get this together. I can't wait to try it out!

    A couple answers:

    "Do you think there would be a benefit to caching walkable areas into a bounding-box-based quad tree? You could then request a chunk of data for a grid-aligned bounding box in the 'upcoming' path prior to falling back to a ray cast?"

    Absolutely! Unfortunately, I have never ventured into the area of developing a Quad-tree. I had approached this as a memory light solution, so a maximum tree cache amount (and fully disabling) might be a good idea.

    "Is your intention that both the Pathfinding and Agent script exist on every agent? Maybe the 'Pathfinding Query Engine' should stand-alone, so multiple agents can share a hash cache?"

    I had originally decided that all objects have their own agent because I don't cache any results. If you do decide to make a quad-tree, having a master agent may be a good idea. However, I do want to allow multiple master agents. For example: you can determine offlimits zones differently for each agent as of current. I want that to continue to exist. So perhaps there should be a dynamically created cache object which simply holds the cached locations for the agents. That way you can have a shared cache, but each agent still uses its own pathfinding. But I don't know if the saved performance would be taken away by having to talk to the cache object...

    Thanks again for your hard work! Can't wait to see it in action. :)
    -Kivak
     
  48. jason-fisher

    jason-fisher

    Joined:
    Mar 19, 2014
    Posts:
    133


    That's terrible news. I recently lost a friend in a similar way .. it was all very sudden. My condolences and prayers to you and your family..

    Getting closer. This is testing with the "Tiny" scene that comes with Planetary Terrain. It should work with any spherical body. I have conversion to longitude/latitude and back, with snapping back to a grid size (0.2 in this example) to reduce potential unique sites/improve cache hits, and then storing the linecast hitpoint to use in actual movement.

    I think I have the slope calculations at least half-working -- it was able to avoid the mountainous area here, but needs more testing.

    You can see some additional debug lines drawn, where cyan is the area being processed currently and magenta is the walkable result result of that test. I will need to tighten up the start of the linecast later when we get to testing with platforms/voxels..

    I am having one more problem with the latitude/longitude distance offset algorithm that is causing it to fail either in one direction, or at the equator -- it ends up pathfinding the wrong way around. :)

    The functions I am using:
    Code (csharp):
    1.  
    2.     public Vector2 CartesianToPolar(Vector3 point)
    3.     {
    4.         Vector2 polar;
    5.         //calc longitude
    6.         polar.y = Mathf.Atan2(point.x,point.z);
    7.    
    8.         //this is easier to write and read than sqrt(pow(x,2), pow(y,2))!
    9.         float xzLen = new Vector2(point.x,point.z).magnitude;
    10.         //do the atan thing to get our latitude
    11.         polar.x = Mathf.Atan2(-point.y,xzLen);
    12.    
    13.         //convert to degrees
    14.         polar *= Mathf.Rad2Deg;
    15.    
    16.         return polar;
    17.     }
    18.  
    19.     public Vector3 PolarToCartesian(Vector2 polar, float radius)
    20.     {
    21.         //an origin vector, representing lat,lon of 0,0.
    22.         Vector3 origin=new Vector3(0,0,radius);
    23.         //generate a rotation quat based on polar's angle values
    24.         Quaternion rotation = Quaternion.Euler(polar.x,polar.y,0);
    25.         //rotate origin by rotation
    26.         Vector3 point=rotation*origin;
    27.  
    28.         return point;
    29.     }
    30.  
    31.         // TODO: this should be higher performance?  has an issue with one direction?  are negative values not supported?
    32.     public Vector3 PolarOffset(Vector2 LatLon, float radius, float offsetNorth, float offsetEast) {
    33.         float dLat = offsetNorth/radius;
    34.         float dLon = offsetEast/(radius*Mathf.Cos(Mathf.PI*LatLon.y/180));
    35.        
    36.         //OffsetPosition, decimal degrees
    37.         return new Vector2(LatLon.x + dLon * 180 / Mathf.PI, LatLon.y + dLat * 180 / Mathf.PI);
    38.     }
    39.  
    40.        // TODO: was using this method to calculate offset by distance, but it had the same problem:
    41.     public Vector2 LatLonDistanceStep(Vector2 LatLon, float R, float distance, float bearing) {
    42.         // double R = 6371000; // meters , earth Radius approx
    43.         float PIf = 3.1415926535f;
    44.         float RADIANS = PIf/180;
    45.         float DEGREES = 180/PIf;
    46.    
    47.         float lat2;
    48.         float lon2;
    49.    
    50.         float lat1 = LatLon.y * RADIANS;
    51.         float lon1 = LatLon.x * RADIANS;
    52.         float radbear = bearing * RADIANS;
    53.  
    54.         lat2 = Mathf.Asin( Mathf.Sin(lat1)*Mathf.Cos(distance / R) +
    55.                          Mathf.Cos(lat1)*Mathf.Sin(distance/R)*Mathf.Cos(radbear) );
    56.         lon2 = lon1 + Mathf.Atan2(Mathf.Sin(radbear)*Mathf.Sin(distance / R)*Mathf.Cos(lat1),
    57.                                  Mathf.Cos(distance/R)-Mathf.Sin(lat1)*Mathf.Sin(lat2));
    58.         LatLon.x = lon2*DEGREES;
    59.         LatLon.y = lat2*DEGREES;
    60.         return LatLon;
    61.     }
    62.  
    Maybe someone can provide some insight .. or maybe I just need to add a sign test. I haven't taken it apart completely yet.

    Usage/context is:

    Code (csharp):
    1.  
    2. ajacentNodeVectorList[0] = SnapVector3(PolarToCartesian(PolarOffset(polarPosition, radius, stepDistance, 0), radius), navResolution);
    3. ajacentNodeVectorList[1] = SnapVector3(PolarToCartesian(PolarOffset(polarPosition, radius, stepDistance, stepDistance), radius), navResolution);
    4. ajacentNodeVectorList[2] = SnapVector3(PolarToCartesian(PolarOffset(polarPosition, radius, 0, stepDistance), radius), navResolution);
    5. ajacentNodeVectorList[3] = SnapVector3(PolarToCartesian(PolarOffset(polarPosition, radius, -stepDistance, stepDistance), radius), navResolution);
    6. ajacentNodeVectorList[4] = SnapVector3(PolarToCartesian(PolarOffset(polarPosition, radius, -stepDistance, 0), radius), navResolution);
    7. ajacentNodeVectorList[5] = SnapVector3(PolarToCartesian(PolarOffset(polarPosition, radius, -stepDistance, -stepDistance), radius), navResolution);
    8. ajacentNodeVectorList[6] = SnapVector3(PolarToCartesian(PolarOffset(polarPosition, radius, 0, -stepDistance), radius), navResolution);
    9. ajacentNodeVectorList[7] = SnapVector3(PolarToCartesian(PolarOffset(polarPosition, radius, stepDistance, -stepDistance), radius), navResolution);
    10.  
     
  49. jason-fisher

    jason-fisher

    Joined:
    Mar 19, 2014
    Posts:
    133
    Just thinking about optimization, and maybe some sort of progressive scan is the way to go. Start by scanning a quarter circle at about the halfway point between the start and target, with that spline split into N points. Then, from each of those points, do the same at the halfway point forward and backward between that point and the start/finish. Rinse/repeat and I think you can greatly reduce the number of raycasts by scanning a fewer points across a greater distance in the main algorithm, then using the smoothing algorithm to complete the path.
     
  50. Myhijim

    Myhijim

    Joined:
    Jun 15, 2012
    Posts:
    1,148
    This. Is. Beautiful.

    Working on a procedural generated terrain system, this will just complete me.

    I can see myself using this extensively in the future.

    Brilliant work guys.