Pathfinding

Hey! I'm planning on releasing a pathfinding package, and I wanted to get some input from you guys. What sort of features do you want out of a pathfinding system?

First, let me give a brief background on myself. My name is Alex Kring, and I've been working in the games industry for about 4 years, working mostly on AI. I've shipped 4 games under The Sims franchise, and one game for the Sony Move. More recently I've been working on Resistance for the NGP. This past year I gave a talk on pathfinding at the GDC, I presented a pathfinding research paper at the AIIDE at Stanford, and I have several publications on pathfinding with AiGameDev [1] [2].

The focus of this package will be to do one thing really well: pathfinding. It will not handle path-smoothing, steering, or terrain representation (though it will come with an example project that uses a grid representation and simple steering). I find that all of theses features heavily depend on the project you are working on. The package will be setup so that you can easily integrate your existing steering system and terrain representation.

Here are the features I plan on supporting:

• A* pathfinding
• User-defined terrain representation (ex: waypoint, nav mesh, grid)
• User-defined A* heuristic (ex: euclidean distance, manhattan distance)
• User-defined target (ex: position, game object)
• Load-balancing (the user defines the number of A* cycles to solve per frame, and per planner)
• Re-plan rate (set a float value that determines the number of seconds before a path will be re-planned, since some game worlds are very dynamic).
• Custom unity editor that displays debug visuals, performance, and maybe some sort of testing?
• Example project that uses a grid terrain representation, and a simple steering system. The project will navigate a bunch of cylinders around the world.

Here are some of the more technical details

• A* priority queue will use a binary heap
• There will be no run-time allocations. All allocations come from a memory pool.
• Variable number of planners (user defines the number of planners within the system)
• User defines the maximum number of nodes per planner, and thus the search depth and amount of memory used.

When I say "user-defined", I mean that the package will provide an existing solution, but it will allow you to define your own solution through an interface. For example, the package will come with a grid terrain representation. But, if you want to use a nav mesh, you will need to create your own NavMeshTerrain class, that inherits from the IPathTerrain C# interface.

Finally, the software will not be free, I will be selling it on the Unity Asset Store. I haven't yet decided on a price point, but you should expect it to be priced the same as other similar packages.

Let me know if this is something that sounds useful to you guys, and let me know what features you are looking for!

 

cool man,waitting for good news

 

Very interested. Have read some of your articles on AIGamedev. I've been working on navmesh generation and was about to start writing a* on it. If I could use your stuff it would save me a job.

Here's a link to my post:-

http://forum.unity3d.com/threads/85348-WIP-My-first-unity-project-navmesh-generation

 

Ah looks like a fun project :] I assume you've heard about Recast, and Mikko's blog? If not, check him out! I plan on publishing to the asset store in about 2-3 weeks, so hopefully I can help you out.

 

I've used recast a lot - but outside of Unity. I moved over to Unity so wanted something similar. My project is a poor man's "copy" of recast using quads instead of polygons (I'm not very clever and my maths is poor -quads make life easier). It's all my own code but uses some of the concepts of recast.

PS

All my code is free - feel free to use it if you want some poorly written spaghetti.

 

Sounds cool!

I would be interested in having a solution that can work with various types of locomotion systems. For example, a Character collider, or a rigid body/physics based motion and of course a vehicle. This would allow for different types of movement to get to the target, some smooth and fluid, allowing for errors and randomness, while others are more exact and direct.

 

The package will provide an example project with simple steering, so that you can see how steering can be integrated. But, the package will not focus on steering. It should work with any steering and locomotion system that you create. The output of the system, for any particular path, is just a Vector3[], and you can choose to use that however you want. To me, locomotion means playing animations based on the output of the steering and pathfinding systems, but I understand everyone has a slightly different definition of locomotion! One thing you will be able to do, is modify the A* heuristic as you please. So you could modify the heuristic differently for different types of characters.

Is this what you are asking for?

 

Here's a preview of some of the features.

http://dl.dropbox.com/u/28622161/WebPlayer.html

There are 20 AI with separate patrol points. The white cylinders are the AI, and the green dots are the patrol points. On my laptop, pathfinding never exceeds 0.17ms per frame in the above demo.

 

Look very promising ! I'm wondering how your implementation will differ from Aron Granberg's one? I've been building my own implementation because I wasn't able to find a suitable simple solution.

UnitySteer has the 3 locomotions your looking for and can be easily tied to a path follow behavior. A pathfinding system will return you a array of Vector3, once you have it, UnitySteer can handle the movement. Hope it help

 

representing the terrain as nav mesh could become interesting given its not a mesh at any time

But I'm looking forward to the outcome

 

You can turn it into a mesh though by getting the terrain height at to corner of each "virtual" triangle. That's what I've managed before (but not in Unity). I'll be doing this soon on my own NavMesh project.

 

One of the problems with Unity steer (a bit missing from OpenSteer) is the function to add planes as obstacles. Adding planes as obstacles allows you to fence in the steering, keeping it on the navmesh while following a path.

 

Agreed, that would be possible but if you overlay it with a mesh grid of equally sized quads I'm not sure there is much gain over just using the grid right from the start as it does not require a virtual mesh etc, just X*Y calls to ask the terrain for the height there

or are you generating some other form of virtual mesh to make some real use with custom triangulation basing on reachability etc (or nav mesh generated on potential fields potentials)

 

Looking good but...

Why do the agents seem to zigzag on the diagonal?

 

I've looked at Aron Granberg's software, and I just took a look at yours once I saw your post :] It's good to see so many people interested in AI! I appreciate your suggestions as well; I've looked at UnitySteer, but not yet in much depth. I am quite familiar with OpenSteer though (UnitySteer was originally a straight port of OpenSteer), and I'm using the most slimmed down version of OpenSteer possible, for the steering in my package. There's only one data structure and a handful of functions that you need in order to get the basics of OpenSteer running.

To answer your question, I think there are several key features that differentiate this pathfinding software from others

• The package provides pathfinding, steering, pathsmoothing, and terrain editing. I havent seen all of these features offered in the same package yet.
• The software is easily extensible. It is structured so that the steering and terrain representation are easily replaceable with your own solutions. If you want to use your own steering system, then you only need to create the hooks in the SteeringAgentComponent. If you want to define your own terrain, you just need to inherit from the IPathTerrain interface, and define three functions. Additionally, you can define your own A* heuristics, A* success conditions, and navigation targets (ex: the software allows you to choose a position or a gameobject to travel toward, but you can define your own type of target).
• Dynamic obstacles. Moving objects are considered by the planner, and not just the steering system. If an agent is happily traveling toward his goal, and a giant rock drops down in front of him, the planner will immediately replan around the rock. This behavior is tunable, through a "replan rate" variable, that allows you to specify how often paths are replanned. The package will ship with a scene that demonstrates this behavior. Additionally, the software supports a FootprintComponent. When you add this component to any of the objects in your scene, the collider of that object will be rasterized into the grid, and the AI will be sure to plan around the footprint of that object. If you dynamically modify the collision of the object, the footprint will update accordingly.
• Performance. I can only speculate, but I suspect that the package will be more performant than many of the other pathfinding packages out there. The only metrics I have right now are that the worst case frame update for the pathfinding is 0.17ms for a scene with 20 agents navigating simple paths. However, I think the bigger differentiating factor will be memory. Most of the memory in the pathfinding system is pooled, which is important for avoiding spikes from the Mono garbage collector. I still have a bit more work to do on this front, but the largest potential memory bottlenecks are pooled (ex: all path nodes come from a pool). It is common for all commercial pathfinding software to completely run from pooled, and make no runtime allocations (this is the case for the pathfinding in Playstation Move Heroes, DragonAge, Starcraft 2, and Havok AI).
• Experience. I've shipped 5 commercial games where I worked on the navigation system, and I've contributed to pathfinding in academia, which I feel has allowed me to create a very reliable pathfinding software.
• Documentation. The package will come with a PDF that explains how to use the software, including a step-by-step tutorial for creating a simple scene. The package will contain four sample scenes, and all of the C# files, so you can modify it as you please, and more easily identify bugs as they arise.

I plan on submitting the software to Unity this coming Monday. All of the code is complete, and has been thoroughly tested, I'm just finishing up work on documentation, and an introduction video. If you have any more questions, please let me know!

 

Ahh thats a good point Chris! In the scene I posted, the agents are not using pathsmoothing. Pathsmoothing has been sucessfully integrated into that package at this point. Additionally, the package allows you to turn on or off pathsmoothing by ticking a checkbox in the Unity inspector. I wanted to keep this behavior as optional, as certain games do not want pathsmoothing (ex: turn-based games). The pathsmoothing is based on the funnel algorithm, which is O(n), always provides the geometrically shortest path, and works with any terrain type (I've used it for both grids and nav meshes). If you want more information on the funnel algorithm, you can check out these links:

http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html
http://webdocs.cs.ualberta.ca/~mburo/ps/thesis_demyen_2006.pdf
http://www.cs.wustl.edu/~suri/cs506/projects/sp.html

 

Thanks for these 2 posts - very good descriptions. I look forward to seeing more.

 

I love the idea of a lightweight but robust pathfinding/obstacle avoidance system with good documentation and that is easy to set up. Looking forward to this!

 

Thank you for your detailed response I'm very curious on how easy it is to setup your scene just to be able to retrieve a path (no steering/locomotion) ?

I'm looking forward for your submission / demo / video !

 

Looking forward to this. So much great stuff in the Asset Store right now!!

 

In order to just retrieve a path (and have no steering occur), you need two GameObjects in your scene:

PathManager
PathTerrain

The package comes with a prefab for both of those objects. Once these objects are placed, you can get the PathManagerComponent, and request a path as follows (pseudo-code).

PathManagerComponent pathManager = (PathManagerComponent)GameObject.FindObjectOfType(typeof(PathManagerComponent));
pathManager.RequestPath(Vector3 start, Vector3 goal, IPathAgent agent)

When the path is successfully completed, a message will be sent to the IPathAgent.

OnPathRequestSucessfullyCompleted(IPathRequest pathRequest)

At this point, you can call pathRequest.GetSolution(), which will return the solution as a Vector3[], or you can have it return the solution as an array of path nodes. If the path search fails, then OnPathRequestFailed() will be called.

You can inherit from IPathAgent to define your own agent (just need to define 3 functions), or you can use one of the prefab agents that the package comes with. This will return the rough path. If you want to smooth the path, you can take your output from the path request, and call

PathSmoother.Smooth(Vector3[] roughPath, IPathTerrain terrain)

And it will return the smoothed path as a Vector3[].

 

How does the obstacle avoidance/steering work? Could you use it in a simple situation without path data? eg: chase this target and avoid stuff on the way?

 

Obstacle avoidance is handled by the planner, not the steering system, which is a departure from some of the other implementations that I've seen in the Asset Store, but is not an uncommon solution (they used this solution for Uncharted 2, The Sims, Deus Ex, and Prototype).

To answer your question, you need the path data. The path will plan around the obstacles, so long as that obstacle has a FootprintComponent attached to it. The package comes with a prefab for an obstacle, so you can see how to use the FootprintComponent. This might not make much sense right now, but I'll post a video when I get home tonight, which should make the concept crystal clear :]

Additionally, the package comes with a "Chase" scene, and a chase script, which demonstrates how to achieve the chase behavior that you described. One agent randomly wanders around the environment, and the second agent chases after him. This showcases one of my favorite features of the package, which is that you have the ability to request a plan to a moving target. I don't have the code in front of me, but the function call looks something like this:

pathManager.RequestPath(Vector3 start, GameObject targetObject, IPathAgent agent, float replanInterval)

That is, if you just want the path to the target. The path will be replanned after every "replanInterval" number of seconds have passed. If you want the navigation system to handle everything, including steering, then you can call the following function

navigationComponent.MoveToTargetObject(GameObject targetObject, float replanInterval)

And the agent will continually chase after the targetObject, until he gets within the "Arrival Distance", specified by the SteeringAgentComponent. Once the agent reaches his target, OnNavigationRequestSucessfullyCompleted() will be sent as a message to the attached GameObject.

 

legend, here is a video to demonstrate how dynamic obstacle avoidance is handled, hopefully my explanation makes more sense after watching this!

http://www.youtube.com/watch?v=h3jxh26hlyQ

 

Thanks !

 

I submitted the package for review today, hopefully Unity approves, and SimplePath will be out soon!

 

coolio, you know about the pricing yet?

 

I'd like to sell it for $50.

 

Wow, that looks pretty awesome. The second example seemed neat; it looks like with only two points (the starting position and the destination) it seems to find its way through a multitude of obstacles.

With that in mind, what if you used your solution, for example, in a scene with one moving player (the destination point), and one enemy (whose initial position is the starting point), and have him chase the player through a scene of obstacles, with no other waypoints in the scene?

What is it thats making the agent intelligent enough to "move around" those obstacles in that second example with only 2 waypoints in the scene?

 

I have another video demonstrating that exact behavior, but I haven't posted it yet. The package comes with a scene demonstrating this "chase" behavior. The system supports a MoveToGameObject(GameObject targetObject) request. Calling this function will result in the agent chasing the target object, until he gets within a specified distance. A message is sent once the agent reaches his target.

To answer your second question, those green circles are not waypoints, they are what I call patrol points. The patrol points are just there to provide you with an easy way to test an agent moving to a specific location. The grid is the actual terrain representation (as opposed to a waypoint graph or nav mesh). In you use a waypoint graph as your terrain representation, you typically manually place all of the waypoints in the scene. If you use a grid terrain representation, you define the number of rows, columns, and the cellsize, and the system will place a pathnode at the center of every grid cell. Let me know if this doesn't make sense!

 

awesome price, i will definetely give it a try. Any ideas how the performance is with webclients? Say in a rts with ~30 agents?

 

Ahh I see. How would you set up a grid on custom level geometry? Could you?

 

Alex, any chance of you posting a link to the documentation for your pathfinding system? Your system seems very complete, and giving people access to the documentation would probably create a lot of momentum.

The state of pathfinding in Unity3D is a bit puzzling at the moment. AngryAnt's Path, while free, has bugs, very little in the way of documentation and is developed rather slowly; also the integration with UnitySteer (a package not well understood due to its lack of documentation and examples) is broken at this time. There's also talk of Unity working on an integrated pathfinding system for a future version, though nothing has been said of when and for what Unity release. In a situation like this, I'm sure many would be more than willing to pay $50 for a supported, complete and documented pathfinding system, especially one that integrates aspects of OpenSteer.

 

@zemog86: This largely depends on the size of your terrain, and other factors specific to your game. But, I suspect you will be able to hit your performance goals. You can control performance by changing some of the values in the Inspector window, for the PathManager.

@legend411: Yes, you can, but you may have to customize a few things. This depends on the type of game you are making. For example, are there bridges in your game where one character can walk on top of the bridge and another character can walk beneath the bridge at the same time? Do you need a spiral staircase where the enemies can navigate? I think you would only have to make changes in the SteeringAgentComponent. One solution would be to treat the path data as 2d, and then use a heightfield or some other mechanism to determine the height of the terrain at a particular point. The SteeringAgentComponent has one function where it starts to follow a path ( SteerAlongPath(Vector3[] path) ). You would need to add some code at the top of that function that iterated over all of the path points, and gave them the correct Y value. Does this make sense? This is a very reasonable approach, it's what they did for DragonAge :].

@PeterB: Here you go!

SimplePath User's Manual
SimplePath Doxygen

Please let me know if you feel the documentation needs to be more robust, if there are features that you think the system ought to have that it does not, or if any of these answers are unsatisfactory.

 

Cool, I see... so I could just resize grid objects to fit my floor space?

Can you use multiple grid objects? And could you combine simple waypoints with grid objects?

 

ah thx for the docs and the reply Terrain is currently from 3000x3000 to 6000x6000 so it should run fine I'd say, I will test it once I've picked it up from the store - thank you!

 

Yes, you can change the size of the grid cells, the number of rows, and number of columns.

BTW, SimplePath was just released into the asset store, and is currently featured!

http://u3d.as/content/alex-kring/simple-path/1QM

I'll make the official announcement thread on the forums later today.

 

Great, really looking forward to this. It will be nice to have one package that has all of the parts implemented and working together. I will be interested in looking at how your steering and vehicle scripts are written to see if I am able to write my own. It would be great to see an example of how to plug this into UnitySteer and use some of those scripts with this.

I really appreciate your docs explaining to use a single Path Manager and pooling. There are lots of scripts/libraries that can do X, but the performance costs can make using them in a commercial game unrealistic. I'd really like to use the most efficient system possible and use best practices whenever I can.

One question, if I have multiple enemies chasing after the player, how do I prevent the enemies from colliding efficiently using your system? I would imagine colliders would work, is that the best way or is a radar/neighbor avoidance system using something like UnitySteer a good way to do this?

 

How does this handle large scenes - like a couple of RPG villages in the middle of a forest (etc)?

 

Alex, thanks for a well-designed, modular and clean pathfinding package! I particularly appreciate how the terrain interface allows environments/terrains of different kinds to work with the system in an identical fashion, and also the fact that terrains can be given their own PathManagers, for instance to cover the different needs of flying/walking/swimming NPCs.

However, even though these possibilities are provided for, SimplePath as delivered implements support only for flat, rectangular navigation grids. Two extensions which I'm sure people will be asking for, and which I think really should be part of the package (if only to save yourself from having to answer a huge amount of questions on how to implement them), are support for navmeshes autogenerated from Unity Terrain components, and waypoints (à la AngryAnt's Path). Thanks to the design of SImplePath, they seem relatively trivial to write (perhaps apart from the path smoothing portal calculations).

I haven't tried using Javascript/Unityscript with SimplePath, which is written in C# throughout, but if there are any special considerations you might want to mention them in the manual, as I'm sure many will want to interface to SimplePath from the Unityscript world.

Anyway, thanks again for a pathfinding package worth every cent! Now let me see if I can use this thing to implement HPA* for my 4000x4000 unit mixed terrain...

 

I'll get to everyone's questions, I'm on the train at the moment, on my iPhone, but I'll be home shortly.

@Bryan: First, can you explain more about the collider solution you mentioned? I'm interested to hear what you had in mind. There are three viable solutions for steering. 1. You can do a local neighborhood steering like opensteer does (quite simple to implement, I'll likely incorporate this soon), 2. You can modify the collision response, and make the agents slide off of and push one another (I've done this for 1 commercial game before), 3. You can simply add a FootprintComponent to the agents, so that they get rasterized into the grid as obstacles. SimplePath supports #3 currently, but I'd like to add the option of using the other two solutions, as they are easy to implement, and each of these solutions is novel.

 

Purchased the package and so far it looks great! I already notice better performance than previous solutions I've worked on with lots of enemies.

What I am working on is a game with a number of enemies, they typically randomly wander and after a while they lock onto a target. Either the player or a random target. What I find with the various steering systems and pathfinding is that if several enemies lock on to the player, they form a line and head straight to the player. I would like some randomness, like jostling or have the enemies avoid each other while trying to get to the target.

The solution #2 works somewhat, but the enemies kind of feel like ice cubes sliding off each other and don't feel intelligent. The Footprint component works pretty well. There are two problems I've found initially:

1. The Footprint is fairly large and the enemies will get locked up and not move when they are cornered by other enemies or an obstacle.
2. At times, the avoidance has a 'three stooges' quality, where the enemies run around each other in the general direction of the target, but in a slapstick kind of way.

I'm thinking that the ability to modify the size of footprint for enemies would make them less likely to get trapped and maybe plan more directly towards the target while more or less avoiding each other.