A* Pathfinding Project 3.0.8

Merry Christmas everyone!
And as a christmas present, you can now download an updated version of the A* Pathfinding Project. Version 3.0.8!

The major feature for this version is the beta of the Local Avoidance which I have been working on, it is included in the Pro version of the system. If you haven’t seen it, check out this video on youtube!
Great news for those of you who have the free version is that you can now save graphs to files, including nodes!

As many of you probably have seen, the developer preview of Unity 3.5 (with built-in pathfinding), was released a few days ago.
What this means for the continuing development of this project is not certain yet, but I will not likely stop all development.
The Unity pathfinder has a number of advantages, and a number of drawbacks compared to my system, I haven’t been able to explore it very much though since it only seems to be available for Unity Pro users (which is the first drawback), I cannot edit any pathfinding settings anyway.
First of all, the Unity pathfinder has only support for navmeshes, not grid graphs or list (point) graphs. This is probably the feature most people will miss with the Unity pathfinder, especially makers of TD and RTS games as grid graphs are the primary choice among them. It doesn’t seem very expandable from what I can see in the docs, I haven’t even found a class for nodes. On the advantage side though, can be mentioned that it does have more advanced local avoidance (from recast, mine is still under development, but it’s getting there), and better support for off-mesh links, and also it seems to have support for partial paths (something I have chosen not to implement since paths are returned within a few milliseconds anyway). It does not seem to use time splicing (i.e calculating over multiple frames) as there is a function in the docs which returns paths instantly, this does in turn mean that it is not multithreaded (except for the generating of the navmesh, which can be run async), but I can be wrong about that.
The path layers they are using for the bridge and door scenes in the examples is another difference, however I have an early implementation of it in 3.0.8 (check out the “Door” scene which is included, only for pro users though as it is based on a recast graph, but the functionality is present in the free version as well, check out the DoorController.cs script in the example scripts folder).

Please comment if I have got something wrong about the unity pathfinder.

Now go ahead and download the latest version: http://arongranberg.com/unity/a-pathfinding/download/
Changelog can be found here

As an extra christmas present, I will give you a 10% discount until the 1st of January on the Pro version!
Just use the promo-code: Christmas2011

Merry Christmas!

-Aron Granberg

Forums for the A* Pathfinding Project!

After getting through the simple installation of the bbPress plugin for wordpress, and the tedious process of finding out how to install plugins (as this seems to be different for different versions of bbPress). I have now got forums working for the A* Pathfinding Project. This should hopefully help to organize the questions all users have as they are now in a very very very long unstructured list of comments to the pages.

Check it out here: http://www.arongranberg.com/forums/forum/pathfinding-project/

Local Avoidance pt.2

I have been able to improve the local avoidance by some. I have changed how the limit (the part which is cut off from the VO cone) is calculated, and changed a bit in where the samples are put. I also tried the solution of using half-planes instead of cones as some papers suggest, but it didn’t work out that well, the sampling method with cones worked better.

Worth to note is that the agents don’t use any physics for collision, collision avoidance is purely done by the local avoidance.

Local Avoidance

I have been trying to get some local avoidance working. It’s such a crucial part of AI movement and very close to pathfinding.
So after reading quite a lot of papers about it I started coding my own attempt at it.
Here’s the result so far.
It uses a variant of Velocity Obstacles (VO) and I currently sample a number of point around the desired velocity to try to find a good velocity. It has got a number of problems still, but it’s pretty good for a first attempt i.m.o.

I plan to integrate this into the A* Pathfinding Project later on.

A* Pathfinding Project 3.0 is Released!

So finally I have released version 3.0 of the A* Pathfinding Project.
This version is a rewrite of everything. The user interface is completely new and it seems to be a tiny bit faster too, especially when counting with that 3.0 has multithreading, i.e it can run the pathfinding in a separate thread so it will barely affect the frame rate on 2+ core computers.
Well, I can’t explain all features here, go check them out yourself – A* Pathfinding Project

The Pro version of the system is not released yet though, I’m waiting for a response from the Unity Asset Store guys.

I have also been working on better documentation for the system. I decided to go for Doxygen, a tool which enables me to add small documentation snippets directly in the source code and it will search through the files and put everything together to a nice documentation page.
I haven’t been able to document every single function and variable, but it’s lots of progress compared to 2.9x.
Check it out here – Documentation

Version 3.0 Update

Hi everyone.

Version 3.0 release date is nearing. So I thought I should share some news:

New features I have implemented since the last video.

Path pooling (reduces memory allocations)
Max slope and max climb settings for grid graph
More stable graph updates
Smaller file sizes for saved graphs.
Generally more stable
Optimized search modes for multiple start points to one end point
Better documentation! Using Doxygen, I’m building docs for every single function and variable.

I will release the system as a Free version and one Pro version. The Free version will have most of the features, but the Pro one will have some additional advanced features such as Recast graph generation and optimized pathfinding modes, I have not decided exactly what it will contain or the price. Both version will be distributed on the Unity Asset Store!
And the free version will also be available on my website.

Here’s a new video for you:
A stress test of the system with 600 agents pathfinding back and forth across a plane while obstacles spawn randomly. The AI’s are quite crappy, but they are using raycasting simplification (even with thick raycasts!).

The YouTube ID of htoen7x3LuQ&version=3 is invalid.