Search Unity

Navigation Mesh And Pathfinding Plugin (Fast, Robust, And Free)

Discussion in 'Works In Progress' started by janzdott, Mar 28, 2013.

  1. janzdott

    janzdott

    Joined:
    Aug 24, 2012
    Posts:
    16
    Hey everyone :) This is actually my third rewrite of a navigation plugin I've been working on. My first attempt worked decently. The performance was good, but the paths were not the best quality. I have been doing a lot of research online in the fields of AI and pathfinding, and I've learned a lot. My third (and final) rewrite is working perfectly. It's very fast, and it's very simple to use. I will be releasing it on the Asset Store soon (for free). And I will update it as I add new features and make changes. I'm open to ideas on features I should add. Or if anyone wants to learn about how pathfinding works, I'd be glad to share my knowledge :)

    Demo Video
    http://youtu.be/tmFTdLI9mP8

    Screenshots
    $NavMesh.png

    $path1.png

    $path2.png

    $path3.png

    Features
    • Fast And Easy NavMesh Import
      Model a mesh in your favorite modeling program, and with the click of a button, import it into Unity to use as a NavMesh.
    • Easy, Accurate Pathfinding
      Give your agent a destination, and it will find the path on its own. No hard work needed.
    • Move The Agent How YOU Want
      Your agent can be a RigidBody, a plain GameObject, a CharacterController, or whatever you want. The agent supplies a steering vector, and the agent's movement is completely controlled by YOU.
    • Multithreaded Pathfinding
      Pathfinding is very fast and can handle hundreds of agents at a time without putting a dent in your framerate.
    • Uniform Random Point Sampling
      You can easily sample a random point on the NavMesh. Useful for making characters wander around, or even for spawning characters and objects.

    Upcoming Features
    • Dynamic Obstacle Avoidance
      Add an obstacle component to an agent, or any GameObject, and the agents will move around them, and not run into obstacles.
    • NavMesh Baking
      Build your scene in Unity, and build a NavMesh within Unity with the click of a button.
    • NavMesh Editing
      Bake the NavMesh in Unity, and use a built-in editing tool to change the mesh to your liking.

    Possible Upcoming Features
    • Off Mesh Links
      Add an Off Mesh Link to a spot on the NavMesh to connect it to another spot on the NavMesh. Useful for jumping across gaps, ladders, elevators, etc.
    • NavMesh Streaming
      Dynamically stream in new parts of a NavMesh. Useful for large, or open world levels.
     
    Last edited: Apr 2, 2013
  2. tasadar

    tasadar

    Joined:
    Nov 23, 2010
    Posts:
    230
    goodwork. is it based on recast?
     
  3. janzdott

    janzdott

    Joined:
    Aug 24, 2012
    Posts:
    16
    Thanks you. And no, it's all my own work. I learned everything through online research. While I have looked at some of recast/detour's source code, I haven't based any of my work off of it. I was mainly looking at how his baking process works. When I include baking, it will be mostly be based off of recast because I like the way he does it. It's very fast.
     
  4. chufraise

    chufraise

    Joined:
    Dec 5, 2012
    Posts:
    6
    Dude. This is so cool.
     
  5. Schlumpfsack

    Schlumpfsack

    Joined:
    May 30, 2010
    Posts:
    607
    looks really good :)

    nice work
     
  6. landon912

    landon912

    Joined:
    Nov 8, 2011
    Posts:
    1,572
    This very nice, but I'll wait a while before using it, just to let it mature. :D Are you using the A* algorithm?
     
  7. Blacklight

    Blacklight

    Joined:
    Dec 6, 2009
    Posts:
    1,241
    You sir, are a brilliant person. I'm going to be all over this if it doesn't require pro.
     
    Last edited: Mar 29, 2013
  8. janzdott

    janzdott

    Joined:
    Aug 24, 2012
    Posts:
    16
    Thanks guys :) and no, it doesn't require pro. And yes, it uses A* to find a path between triangles, then uses the funnel algorithm to optimize and simplify the path
     
  9. GeneBox

    GeneBox

    Joined:
    Nov 15, 2012
    Posts:
    480
    Awesome stuff!
     
  10. Gnimmel

    Gnimmel

    Joined:
    Apr 21, 2010
    Posts:
    353
    I just wanted to say this looks great, and you can't beat the price :D

    My only real question is will it work on mobile?

    I really like the simplicity of it, just getting a move vector to me makes a lot more sense than some of the other path finding solutions I've tried. I will be keeping an eye on this and giving it a try once you've released it. I'm especially interested in the avoidance because I'm not happy with the way this is working in my game yet.

    One thing I didn't see in the video was a setting to change the turn radius, is it possible to change?

    ok, 1 more question, what happens when the target is outside the nav mesh? Will the path just fail, or will the agent walk to the edge of the navmesh and stop?

    This is looking great, and to release it for free is very generous of you.
     
  11. janzdott

    janzdott

    Joined:
    Aug 24, 2012
    Posts:
    16
    Its funny that you asked if it would work on mobile. Yes, I'm actually making this for a 3rd person shooter game for Android that I'm working on :) My first attempt worked great on mobile. I could have 50 rigged and scripted characters all running around the level with no framerate loss. And this rewrite is much faster, so I should be able to squeeze even more out of it. And I haven't even started optimizing yet ;)

    Right now, I don't have a turn radius. The steering vector that the agent supplies is just a normalized vector that points in the direction it should move. Turning speed can be added if you dampen the change in the steering vector. I've thought about adding acceleration and turning speed variables to the agent. I can add those if you guys think it would be useful.

    And when the target is outside the NavMesh, it finds a path to the edge. The algorithm finds which triangle the start and end points are in. If they are not in a triangle, it simply finds the closest one. So it would be easy for me to add a check to determine if the point is not on the NavMesh.
     
  12. janzdott

    janzdott

    Joined:
    Aug 24, 2012
    Posts:
    16
    I added two new functions to the NavMesh to help with checking if a point is on the NavMesh.

    bool NavMesh.isOnNavMesh(Vector3 point)
    returns true if the point is on the NavMesh, and false if it is not. Note: It will return true if the point is floating above or below the NavMesh within a threshold. This threshold varies based on the density of the triangles (because of the octree that is used to pick nearby triangles).

    Vector3 NavMesh.samplePoint(Vector3 point)
    returns the closest point on the NavMesh to the given point.
     
  13. Gnimmel

    Gnimmel

    Joined:
    Apr 21, 2010
    Posts:
    353
    That's great that it works on mobile, I'm presently working on a Iphone RPG which I would love to test your solution out on.

    Adding some sort of acceleration and turning radius might be useful to some, especially for vehicles, as long as it can be turned off. Personally I like your solution because of it's simplicity, and that sort of thing could be added into the movement code away from the plugin. I'm sure others would want it though.
     
  14. janzdott

    janzdott

    Joined:
    Aug 24, 2012
    Posts:
    16
    Yeah I'll add all that stuff, and have an option to select simple or advanced movement for the agent.

    I got rid of my maximum timestep system, which used coroutines, and I added multithreading support instead. Pathfinding is faster now, and still won't make the game lag. I tested with 500 agents constantly pathfinding around my test scene. FPS stays at a solid 130. By the way, this is on my laptop which has 64 bit AMD A6-3400M 1.4GHz quad core with 4 Gigs of RAM.
     
    Last edited: Apr 1, 2013
  15. LightSky

    LightSky

    Joined:
    Aug 12, 2012
    Posts:
    39
    I have a game which has a constantly changing maze (walls are being added/changing). Will the AI for this automatically adjust when the predetermined path becomes obstructed by such walls and obstacles? or will it just stop and break?

    Thanks :D
     
  16. janzdott

    janzdott

    Joined:
    Aug 24, 2012
    Posts:
    16
    If your maze is constantly changing, that means the NavMesh will have to change also. The vertices and triangles of the NavMesh are public, so you're able to change them. I also plan on adding a delegate for when the NavMesh changes, so the agents recalculate their paths. But manually setting the triangles and vertices for this sort of scenario would be difficult. When I add baking, I will try to make it as fast as possible, and threaded so it can run in the background. If it's fast enough, you'll be able to bake the NavMesh in-game whenever the world changes, making navigation in a dynamic world very simple.
     
  17. MD_Reptile

    MD_Reptile

    Joined:
    Jan 19, 2012
    Posts:
    2,583
    When will we see this in asset store? has it been tested at all? if not let me try :p I would love to see how many characters I can run on my droid razr without lag.
     
  18. janzdott

    janzdott

    Joined:
    Aug 24, 2012
    Posts:
    16
    I was planning on putting it on the Asset Store after I finished obstacle avoidance, but I can put it up tonight if you'd like. I've tested it with 500 agents on my laptop, which ran just fine. But I would like to know how well it runs on single core devices.
     
  19. mcunha98

    mcunha98

    Joined:
    Jun 13, 2010
    Posts:
    258
    Waiting for news !!!
    Greate job, keep work !
     
  20. NnelGdaBandit

    NnelGdaBandit

    Joined:
    Dec 21, 2012
    Posts:
    13
    This looks great man! How are you planning on doing the dynamic obstacle avoidance? Modifying the navmesh, by raycasts, some other way? I wanted to use the pro-version of Unity's pathfinding but their dynamic obstacle avoidance seems to just be steering behaviors and I need a path ahead of time for what I'm working on. Do you know if that will be possible? Anyway great work, I'm looking forward to this!
     
  21. janzdott

    janzdott

    Joined:
    Aug 24, 2012
    Posts:
    16
    Thank you! And I'm currently trying to figure out how I'm going to do obstacle avoidance. I've thought about modifying the navmesh (recast/detour does this for temporary obstacles) but I don't believe it will be fast enough. I'm probably going to use steering behaviors, but I'm not sure how I'm going to handle everything yet. Like grouped obstacles, and making sure the agent doesn't steer off the navmesh can be major problems. I also thought about looping through the vertices in the path, and re-running the funnel algorithm around the obstacles. I'm not sure if that would be possible, but it's something to think about. Why do you need to have the path go around obstacles ahead of time?
     
  22. NnelGdaBandit

    NnelGdaBandit

    Joined:
    Dec 21, 2012
    Posts:
    13
    The project I'm working on is a tactical game and movement is all based on distance. Once you click somewhere I would want the exact path of where they are going to go. Then I can trim the path to make it within the movement limits. (Assuming a path goes through an obstacle) If the character moves out of the way of the obstacle when he gets near it via steering behaviors I cannot show the player that path and the character would technically be traveling extra distance. I'll probably end up using a graph though I thought about doing something like this:

    http://digestingduck.blogspot.com/2011/02/very-temporary-obstacle-avoidance.html

    But I'm too concerned about performance and path error with all the iterations I might have to do. A graph will suit my needs but a dynamic nav mesh would be the holy grail for my special case.
     
  23. toon

    toon

    Joined:
    Apr 14, 2013
    Posts:
    1
    Looks really promising! I'm currently trying the older version that you've released on the forum, and I really like it because its a lightweight solution.
    Would be great if you could release your new version soon (even without obstacle avoidance) :)
    cheers, and thanks in advance!
     
  24. daboretto

    daboretto

    Joined:
    Mar 21, 2013
    Posts:
    3
    Does that will offer also some kind of framework so that it can work also for procedural generated levels and not only for prefabs and static scenes?
     
  25. janzdott

    janzdott

    Joined:
    Aug 24, 2012
    Posts:
    16
    You're able to modify the NavMesh at runtime. So technically you can use it for procedural or dynamic levels. The problem is, it's not easy to build a NavMesh from code on your own. That's why I will be including baking. Then you can bake the NavMesh during runtime as your level changes.
     
  26. MD_Reptile

    MD_Reptile

    Joined:
    Jan 19, 2012
    Posts:
    2,583
    hey sure thing, maybe just post a alpha demo project (rar) on dropbox or something. I would like the check it out, just to see how it ticks. Any updates of whats going on with this?
     
  27. janzdott

    janzdott

    Joined:
    Aug 24, 2012
    Posts:
    16
    Well, I haven't worked on it for a bit, because I haven't figured out how I'm going to do obstacle avoidance. I'll do some api cleanup, fix a little bug on the path replanning, and put an alpha version on the asset store soon.
     
  28. rob_vld

    rob_vld

    Joined:
    Jul 9, 2013
    Posts:
    158
    hello mr...

    been following this for some time now... this is really great stuff....
    was wondering(hoping actually :p) if you made any progress with your dynamic obstacle avoidance??

    keep up the good work!
     
  29. rockysam888

    rockysam888

    Joined:
    Jul 28, 2009
    Posts:
    650
    Hi all,

    Where could I download this plug-in?
     
  30. ChrisSch

    ChrisSch

    Joined:
    Feb 15, 2013
    Posts:
    763
    Nowhere yet rockysam. We're still waiting, but it looks like its worth the wait. *cough* hurry *cough* xD
     
  31. fernandovt

    fernandovt

    Joined:
    Oct 1, 2012
    Posts:
    67
    When is it going to be in the asset store?:O, I can't wait!, if this works on enemies, oh man.... Do you have any plans of making a video tutorial to teach us how the most recent version works when you put it on the asset store?, i've working forever to make my enemies find me in my horror game project...
     
  32. Nolaa

    Nolaa

    Joined:
    Nov 11, 2013
    Posts:
    1
    Hi,
    I'm interested in this plugin but I see that there has been no activity for 4 weeks and I can not find it in the store.

    If published, what's his name?
     
  33. janzdott

    janzdott

    Joined:
    Aug 24, 2012
    Posts:
    16
    Hi I'm really sorry everybody! I stopped working on the game that I originally needed this for, but I have need for it again and I know others do too. Now I'm working on a grid based RTS with procedurally generated terrain. Path finding on the grid was slow and the paths were ugly, so I'm dynamically generating and triangulating a navigation mesh from the grid data. It works pretty well but does have some issues, and only works in 2D. I'd like to add it to the plugin when it's a little more polished.

    I'm also planning on trying out path finding with dynamic memory allocation. A* is run on the navigation mesh nodes to find a path through the triangles. It currently initializes memory for every node before finding the path. This can take a lot of memory if you have a very large navigation mesh. It is also very wasteful if the path is short compared to the size of the entire mesh. What I plan on doing is initializing memory for only the nodes that are considered. This will save a lot of memory, but I am unsure how it will impact performance. I'm going to give it a try soon. If it doesn't impact performance very much, I will add it to the plugin. If it does affect the performance, I will have an option to choose whether to use it or not.

    I don't want to specify a release date yet, but it won't be too long. I will keep up to date on the progress.
     
  34. goat

    goat

    Joined:
    Aug 24, 2009
    Posts:
    5,179
    Actually I started to use this code and was porting it all to C# and than I got stuck on the javascript Array() class with seemed to be an array of a defined class but then in places in the code was passed an integer. So I'm like, darn, I will have to learn how this code works or write my own. Since I only get 3 points to navigate to I wrote my own. I'll be watching this though.
     
  35. squared55

    squared55

    Joined:
    Aug 28, 2012
    Posts:
    1,819
    Have you tried using ArrayLists? http://msdn.microsoft.com/en-us/library/system.collections.arraylist.aspx
     
  36. IssacTeoh

    IssacTeoh

    Joined:
    Apr 9, 2014
    Posts:
    3
    cant find this plugin any where :confused: is the plugin been release yet ? What is the name this plugin ?