Local Avoidance pt 3

So it’s time for local avoidance again.
The A* Pathfinding Project (pro version) has included a beta version of local avoidance for some time. I decided it was time to do something about that “beta” label.
There is a great library out there called the RVO2 library. It has been used in both UDK and in Unity. Unfortunately it has a rather limited license. Not for commercial use unless explicit permission is granted, which is a problem since they do not seem to answer any emails I send them.
So I decided to take inspiration from the rvo2 library and rewrite it in C#. Which I have now done. I have also added new features, for example agents and obstacles can now have different Y coordinates as well as XZ coordinates, so agents at different floors of a building can navigate properly without “colliding” with agents at other floors.
I have written a script to convert navmeshes to RVO obstacles, so agents will properly avoid navmesh edges. I will later write a similar one for Grid Graphs and I hope to get graph updates to work fine with it as well.
Time to stop talking and link to a demo:
http://www.arongranberg.com/unity/a-pathfinding/local-avoidance-demo/

It has really good performance. On my laptop I can run 500 agents when I just make sure they don’t all try to go through the same point, and on my stationary computer I can run more than 500 agents with a good framerate. Currently the rvo simulation is set to a desired fps of 20 and everything in between is interpolated.

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.