3.1.2 Update

Version 3.1.2 of the A* Pathfinding Project has just been released.
This is a bugfix update which fixes some problems, mainly with iPhone compatibility.
Check out the changelog at the usual place: http://arongranberg.com/astar/docs/changelog.php

Small bugfix release

Okay, people immediately found bugs with the 3.1 release (and obvious bugs as well I really should have tested it more).
So now 3.1.1 has been uploaded, the two bugs should be fixed now. With a bit of luck, I haven’t made any other serious mistakes.
For those wondering, the Asset Store submission is pending.

Changelog (updated version will be uploaded in a minute): http://arongranberg.com/astar/docs/changelog.php

[EDIT] Version 3.1.1 is now available in the Asset Store as well.

A* Pathfinding Project 3.1 Released!

Yay! Now it is finally here! Version 3.1 of my pathfinding system.
The upgrade should be hassle free (hopefully). However ListGraphs will not have their settings preserved. This is because I have renamed the ListGraph to PointGraph (better name) so it will not find the graph type ListGraph anymore.
The whole serialization system has been rewritten as well. It is now a lot more stable (no custom written hackish stuff) and is aimed to be both forwards and backwards compatible (well, not with the old system, but when updates to the new serialization system are made). It is based on Json and now you can actually save graph data, unzip it (yes it is stored as a zip) and edit the graph settings by hand!
Anyway, too many new features to list here (seriously!). Check out the changelog: http://arongranberg.com/astar/docs/changelog.php

Version 3.1 has been submitted to the Asset Store, but it might take a few days for it to be approved.

A* Pathfinding Project 3.1 beta released!

I just released the beta version of the A* Pathfinding Project 3.1.

The release has almost everything working, just a few details which need to be reworked, so it is stable enough to be used in a game. But please back up your projects before upgrading.

Pro users which have bought it at this website can use the download link in the confirmation email they got when first buying it, the zip file linked will now contain both the current version and the 3.1 beta.

Sorry, but I didn’t have time to upload the beta version to the Asset Store (and I won’t have time for about two weeks). Those who have bought it there will have to wait for the final 3.1 release.

I hope you will find it a great upgrade!

More Threads! Multithreaded Pathfinding

As some of you may know, I’m have multithreaded pathfinding in the A* Pathfinding Project. This is a great way to keep the game at a steady FPS while other threads can carry out heavy pathfinding. Until now I have only had a single separate thread for pathfinding. That works good, but there is room for so much more now that computers with more than 2 cores start becoming common. So I decided that I should try to implement that.
It didn’t work out the way I wanted to in the beginning, the reason is that I have made no separation of connectivity data (which is usually static) and path data (temporary data needed for path calculation) everything was stored in the same Node object. So I started working on separating them. What I ended up with was a huge matrix where a large array of NodeRun object (in lack of a better name) is stored for each thread. The NodeRun object stores the temporary data (e.g G and H score) and every NodeRun object is linked to a specific Node, however there are for each thread a NodeRun object which links to the same Node. This works quite good, memory hasn’t increased that much, should be about 12 bytes per node for 1 thread and then 8 extra bytes per node per thread added. And I think the performance has barely been affected per thread.
The awesome stuff reveals itself when you test the performance with more threads then 1.

Multithreaded Pathfinding Graph









My computer has 4 physical cores, but uses hyperthreading for a total of 8. As you can see in the graph, I can manage to get it to run as much as 3.75 times faster than with a single thread! The speedup is linear at the start, but gets smaller when the number of threads increase above the number of physical cores. Memory usage increases linearly at about 2mb per added thread (for the 200*200 grid graph I’m testing on).

The only major drawback that I can see is that it will be slower to update the graphs. When a graph is updated, pathfinding must not be searching the graph at the same time, that could lead to weird errors. When not using multithreading, the function can simply update the graph (if needed) between calculating paths. Almost as easy when using a single thread, but then it must stop for a bit to let the Unity thread update the graphs since many things such as raycasting must be called from the main Unity thread. When using more than one thread, every thread must finish calculating the current path they are calculating, stop and then notify the unity thread that it can proceed with updating the graphs. This can lead to a decrease in performance because the threads spend much time idling. One way to solve this is to group graph updates together in chunks for example every 0.2 or 0.5 seconds to avoid stopping the threads too often when updating the graph a lot.

Anyway, I’m happy with the transition. I could also simplify many functions to use more advanced atomic operations instead of custom written lockless queues and stuff. When I get around to rewriting the GraphUpdateObject system for this I can also make sure it does not block the unity thread waiting for the pathfinding threads to stop, but it simply notifies the pathfinding threads that they should pause. And when they have, the unity thread, some frames later, can update the graphs. The previous approach could lead to lag when updating graphs if the pathfinding thread was calculating a really long path.

I’m a bit concerned for the mobile development though with the increased memory usage. It is not really much though. I built two tests, one with the original code (similar to latest release) and one with the new code. Both using a 200*200 grid graph. The new code used 6mb according to GC, and the old code used about 5 mb (I only had 1mb precision). But what’s interesting is that the old code had about 1.5 mb allocation per second, but the new code allocated practically nothing (0.0 to 0.1). I don’t know if that is something relevant, or if it just is GC acting odd. But it was repeatable at least. With 4 threads it peaked at 13mb, though it started at 8 or something. I don’t know much about C# internal memory management, so I usually just measure the peak allocated memory after 20 seconds or so when it has stabilized.

Multi Level Grid Graphs

One of the most common questions I get is how to get grid graphs working for a world with multiple levels (as in floors in a building, not game levels).

I have tried to implement that at least 3 times, every time I have got results which I haven’t been totally happy with. So today I decided to brush up some old scripts and see if I could make them better. Turns out it was quite easy to get them working and generate good looking graphs.

Here’s a demo video:

Hopefully this feature will make it to the 3.1 release of the A* Pathfinding Project.

I got some stuff to implement before it is finished though:

  • Funnel algorithm support
  • Graph update support
  • Linecasting (maybe I will skip that though)
  • Erosion

iPhone crashes

For those of you experiencing crashes on startup when running the A* Pathfinding Project on iPhone here’s a workaround.

The background is that, even though it in the Unity docs appears to be supported, the System.Guid class isn’t supported on IOS. The A* Pathfinding Project uses that class for saving an ID for each graph.

In all graphs there is a variable initialized to new Guid () (in the base.cs script). This will, since it is not supported, crash the application.

For 3.1 I will write a replacement class for the Guid class, until then, here are two different workarounds.

Option one: In the player settings (Project Settings -> Player Settings) there is an option to catch all exceptions or crash on exceptions (the crash option yields faster applications).  If you set it to catch all exceptions, I think it will run ok.

Option 2: One variable almost at the top of the base.cs script is initialized to new Guid (). You can comment out that variable (it’s obsolete anyway). And it will hopefully not crash again.

Note that you will not be able to create new graphs during runtime even with these changes applied, that will create a new Guid and crash the application.

Hope it will work for all of you 😀

Moving Platforms

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.

Graph Updates and Tagging

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: