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

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








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.

 

goodwork. is it based on recast?

 

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.

 

Dude. This is so cool.

 

looks really good

nice work

 

This very nice, but I'll wait a while before using it, just to let it mature. Are you using the A* algorithm?

 

You sir, are a brilliant person. I'm going to be all over this if it doesn't require pro.

 

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

 

Awesome stuff!

 

I just wanted to say this looks great, and you can't beat the price

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.

 

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.

 

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.

 

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.

 

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.

 

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

 

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.

 

When will we see this in asset store? has it been tested at all? if not let me try I would love to see how many characters I can run on my droid razr without lag.

 

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.

 

Waiting for news !!!
Greate job, keep work !

 

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!

 

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?

 

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.

 

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!

 

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?

 

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.

 

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?

 

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.

 

hello mr...

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

keep up the good work!

 

Hi all,

Where could I download this plug-in?

 

Nowhere yet rockysam. We're still waiting, but it looks like its worth the wait. *cough* hurry *cough* xD

 

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

 

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?

 

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.

 

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.

 

Have you tried using ArrayLists? http://msdn.microsoft.com/en-us/library/system.collections.arraylist.aspx

 

cant find this plugin any where is the plugin been release yet ? What is the name this plugin ?