Skip navigation
Help

Pathfinding

warning: Creating default object from empty value in /var/www/vhosts/sayforward.com/subdomains/recorder/httpdocs/modules/taxonomy/taxonomy.pages.inc on line 33.

This is a cross post from my personal development blog , about a day or two spent jamming on path finding.

I enjoy messing with path finding algorithms and finding interesting ways to obtain the results, this is about a few more recent attempts.

0
Your rating: None

I've been experimenting with this special AI pathfinding thing for a while now, and finally decided to merge it into a game. It's a very simple type of AI with a lot of emergent behaviors built in to it

0
Your rating: None

Features

Easy to set up
Requires no external data or code libraries
Very fast (see performance)
Can use multiple grids
Runtime changing of a grid, for example, placing a building on the ground
Custom node linking
Free for non-commercial projects (see license for info about commercial use)
Can execute over several frames (meaning no lag)
Path caching
Path simplification and smoothing
Support for navmeshes
Support for creating your own procedural grid generators
Works with Unity iPhone (U3 iPhone is not tested, but it shouldn’t be any problem)

Performance

For example, a path request which resulted in a 148 node path and searched 3030 nodes took about 3 milliseconds to complete.

A longer path, probably longer than you are going to use in a game, resulted in 294 nodes and searched about 22 thousand nodes. Because it was so long, the computation was spread over 3 frames. The path took 24.6 ms to compute, or 8 ms per frame.

If you download the project and open up the RTS scene, you can get a quite good picture on how fast it is, press the Send All At Once button, this will calculate paths for all 240 units to random positions on the map, on my computer this takes about 0.6 seconds while running at 40-50 fps, usually with 0.1-1 ms per path.

Results can vary very much depending on computer specs and things like that, so it is hard to give a good example. These tests were done in the Unity editor.

Licence

Creative Commons License

A* Pathfinding by Aron Granberg is licensed under a Creative Commons Attribution-Noncommercial 3.0 Unported License.
If you want to use the code for commercial projects please contact me at aron.g@me.com.
A license to use the project/code in commercial applications/games costs US $100, although other options such as profit sharing can be discussed if that suits the person/company in question better.

Download

Download A* Pathfinding Project version 2.95

Documentation

All Docs
Get Started Guide?
FAQ
How do I use my code with the A* script?
API and components
Using Unity iPhone

How does A* pathfinding work?

0
Your rating: None