At last I have got a new forum software up and running!
It is powered by Vanilla Forums, an open source forum platform which seems to be very good. However I did not manage to migrate the old forum to the new forum, so I will leave the old forum open for viewing, but closed so that no new topics or posts can be created.
Check out the new forums here: http://arongranberg.com/vanillaforums
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.
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
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.
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.
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!
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.
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.
Check out this blag! —> One Tiny Leap
He is experimenting with developing steering behaviors for the A* Pathfinding Project among others. It might turn out to be really awesome! 😀
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:
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 😀