Moving platforms and elevator support is something that has been lacking a bit in the A* Pathfinding Project up until now. So I started thinking about it during the weekend, and figured that it shouldn’t be too hard to implement, so I did that 😀
What I ended up with was an implementation using one-way links. That is, if you have an elevator which only goes up, I would create one node at the bottom of it, and one at the top, and then add a link between them which only goes in one direction: from bottom to top.
I created a new graph type named LinkGraph, the idea is that it should always be present as the first graph in the scene. And a few scripts which enables you to create new nodes and connections using gameObjects which you place in the scene. It works similar to a list graph, but the nodes are not connected automatically, you have scripts which specify a connection from one point to another point, nodes will be created at both endpoints and automatically (currently not so sophisticated, might add more features there) connects them to nearby nodes in other graphs.
Further, I have an elevator/moving platform script which checks a trigger, if the AI stands on the platform for a specified length of time, it will lock the AI so it will not be able to move during transport to the target location, it will then move, and release the ai to move freely when it has reached it’s target location.
This simple technique works unexpectedly well in my tests.

Ways to improve it would probably be to tag the elevator nodes with certain tags which tell the AI to stop at the first one and then wait for it to move to the next instead of trying to walk towards it. That would free the elevator script from having to lock the AI from moving. It would be better in that the current system can fail if the AI walks too fast.

Here’s a video of what it looks like at the moment. Oh, and also, I have written a new AI script which has much better movement behavior than the previous AIFollow script, the one in the video is the new script, a bit modified to be able to animate the legs of the robot properly and to create a particle effect when it reaches the end of the path.

Hello World!

I’ve been working on some stuff recently for the upcoming A* Pathfinding Project 3.1 release. Many of you have probably been a bit annoyed by the amount of work needed to change tiny details in the graph, for example making some nodes unwalkable. Well, that problem is soon over.
I have created a new script which is called GraphUpdateScene. It collects a number of useful changes you might want to do to a graph such as, as mentioned before, making some nodes unwalkable, or perhaps adding a high penalty to an area (making the area harder to traverse, so units will avoid it).
You can even set the tags of the nodes, which is another new feature I have developed. It is used to define which units can walk on what ground.
Imagine for example that you have some critters, a player and some AIs in your world. Both the AIs and the critters pathfind randomly around in the world but you wouldn’t want the critters to enter houses (they make such a mess). Then tagging is a great way to solve it. If you tag all indoor areas with a tag named for example “Indoors” and make sure no critters can walk on those nodes, that would be it!
Oh, and did I mention that you are no longer restricted to axis-aligned rectangular areas, you can use any polygon shape you want!

Anyway, it’s tedious to describe stuff using text, so here’s a video for you showing both of these features:

You may have noticed that there are much fewer comments on the pages now. That’s because the very high number of comments on some pages caused them to slow down the site, sometimes it was really a pain opening some pages because of the time it took. Now that I have cleared most of the over 800 comments (those that were questions mostly), the site will hopefully be a bit faster. Sorry about removing everything people had written, but the site simply became too slow.
For questions, I now have the forums for the A* Pathfinding Project (currently 60 topics and counting).

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

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/

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.

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.

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 of the A* Pathfinding Project has now been sent to the Unity Asset Store for validation.
Hopefully they will accept it.

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.