Pathfinding

Community Showcases
1

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!

2

cool man,waitting for good news

3

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

4

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.

5

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.

6

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.

7

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?

8

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.

9

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 :slight_smile:

10

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

But I’m looking forward to the outcome :slight_smile:

11

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.

12

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.

13

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)

14

Looking good but…

Why do the agents seem to zigzag on the diagonal?

15

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!

16

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://www.cs.wustl.edu/~suri/cs506/projects/sp.html

17

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

18

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!

19

Thank you for your detailed response :slight_smile: 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 !

20

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