A* pathfinding (stable 0v841)

[kiriri]

This project is currently deprecated. Please wait til mid march for an updated version.

What is this package?
This is an implementation of Aron Granberg's A* pathfinding package into PlayMaker. Unlike other actions and addons, it not only offers the functions of the original package as actions, but it also extends and greatly simplifies complex processes. This is why each action is usually rather complex and why progress is seemingly slow


What is pathfinding and Why should I use it?
Pathfinding solutions are systems that take your environment and interpret it in a simple way. Then they use this simple data, which is called a "graph" to find a valid path from point a to point b. Depending on your settings the path may avoid walls, holes or even try to avoid grounds that are walkable, but slow, like swamps, if the extra way around them is worth it in the end.
Unity itself has pathfinding too, but it is very weak compared to any of the available packages. If you want to place objects at runtime for example, and then want your actors (the gameObjects that move around, like your enemies) to avoid them, then that will not be possible with the default unity pathfinding.

More information can be found on Aron Granberg's website :
http://arongranberg.com/astar/front

Is it better than XXX?
If you're thinking whether you should use this solution over another then that is a fairly simple question atm. This package is for those who want maximum exposure of settings, and maximum performance. On the other hand there is a real learning curve involved. Aron's package is open source and it's vast. Additionally, I have and will continue to add all kind of stuff to make other things possible or more accessible.
Aron's package is also a wise choice for anyone working on a mobile platform.


Have a look at the following vid if you do not know how to use specified object variables. The variables involved with the actions are under FsmPathfinding:

Install instructions 0v83free
1) Download the package (see bottom of the thread)
2) extract the content of the 7z into your assets folder.
3) Install python 3 or make sure your python version is 3.0 or later
4) Run the setup.py in the AstarPlayMakerInstaller folder.

Install instructions 0v82 pro
0) Install Aron Granbergs astarPro package in your project (no need for js support anymore, though it doesn't hurt either )
1) Download the package (see bottom of the thread)
2) extract the content of the 7z into your assets folder.
3) Install python 3 or make sure your python version is 3.0 or later
4) Run the setup.py in the AstarPlayMakerInstaller folder.


Upgrade to (pro):
 -- Same as Install instructions for pro --

This is a stable release now. I've created a prototype tower defense without any problems and am currently building a full fledged rts, so no worries that this will get lost If you find any bugs, tell me. If you find something odd, tell me and if you have a better idea on how to do things, commit it here or just directly critisize my work. No worries there

What we've got so far:
You can create point graphs at runtime and use any type of graph that was setup before.
You can use a custom controller or choose from Transform, CharacterController, RVOController and Rigidbodies/Rigidbodies with fixed velocity.
You can either use a vector3 or a gameObject as a target, and you can run away from it, run towards it, follow it until you're close, follow it forever, copy the movement of the target (shadow it) until you reach it or forever, flee a certain distance from it, flee forever from it or you can just walk randomly around
You can smoothly follow a path or use modifiers to actually make the path smooth (currently only subdivisions)
You can access all the node information, graph information and astarPath information (main A* information).
There's also lots of other goodies, like calculating the time of arrival for an actor if he moves along a path, or getting and setting the walkability in an area, but I don't feel like listing them all up. If you feel like something is missing, then just leave a comment and I'll probably integrate it in like 19/20 cases.


Upcoming stuffs:
0v85/0v86 :
- back to c# Since the installer will force a js supporting structure, why bother?
- fix actor failing if the node he's currently standing  on is unwalkable
- fix smooth modifier on point graphs. Implement other modifiers. Merge all in one action.
- add "shadow offset" for group movement
- option to instantly create a path.
- fix auto option which to be honest is ridiculously outdated/broken
- compare nodeType action
- integrate tags into the actions
- add name option to pointgraph creation actions [done] and create a system to access graphs by name (I think this could be rather useful on larger projects)
- create GridGraphAction
- destroy Graph action

long term ideas:
- create a system for actors to smoothly follow a path [in progress]
- create a system for actors that makes them walk in a straight line if possible, ignoring exact node positions, and only using them where necessary (eg corners). This should both save performance and look better, so it should definitely not use recast.
- make system to move multiple actors at once (eg in formation like in rts, this will likely be part of my future "advanced" version)
- general performance boosts.
- claim and release paths for memory optimization (potentially important for mobile, but this needs some reading in)
- Complete grid graph support. (almost established)



Other People involved : ZeroSigma, hannibalov, LampRabbit

Current Status of the tutorial series:

1) Project Setup

2) Graph Basics

3) Movement basics

Astar-PlayMaker Download : https://docs.google.com/file/d/0BwrgibYeepavZ0o0ZmNpWE9lRTg/edit?usp=sharing

[kiriri]

|FAQ|

1# My MoveTo action never finishes, even when the actor already reached the end of the path. What can I do?

Good question! There may be a number of reasons for this. The least obvious is the usage of the "absolute" FinishDistanceMode, combined with a low FinishDistance. In this case your actor walks to the last node on the path, but even then the absolute distance between him and the target can still be higher than the FinishDistance (eg if you have a Gridgraph and your target is right in the centre of one of those "gridsquares".) In this case you can either :

1) Up your FinishDistance
2) Enable the ExactFinish option which adds your target's center as a last node to the path
3) Change the FinishDistanceMode to something like Last or AbsoluteLast, which  checks the distance between the actor and the last node on the path instead of the distance between the actor and the target.

You should always note that sometimes your target might be underground. In this case you should make sure to check the IgnoreY option, which will also ignore any y coordinates in the FinishDistance modes.


2# I'm confused by the different movement modes. What do they do. When should I use which?

So far there are 9 Different Movement Modes.

   moveTo,
   followTo,
   follow,
   shadowTo,
   shadow,
   followPath,
   fleeTo,
   flee,
   randomPath,

Some come in pairs, like Follow and FollowTo, or Shadow and Shadow To. These pairs are very similar, but the To suffix means that this mode sends a FinishEvent once it arrives at the target location. So the mode FollowTo will finish once it is in FinishDistance of the target, while the mode Follow will continue following the target indefinitely (well, as long as that particular Action/State is active).

Now that we understand the naming, let's have a look at the individual actions to see what they do and when they should be used :
1) MoveTo : This mode is the most simple mode. Use it to get from point A to point B. It is a To Mode, so it will fire an event on Finish. I use this mode in strategy games to send a selected unit to a certain position. The path is never updated.

2) FollowTo : This mode is like MoveTo, but it updates the path every number of frames. You can define the update interval, which stands for the number of frames the action should wait before updating. I rarely use any update interval that is lower than 60 (1second in my game), because this can cost you a lot of performance, especially on long paths. I use this mode to send a unit to attack some other unit. The FinishEvent is directly wired up with my attack stuff.

3) Follow : Exactly like the FollowTo mode, but it never finishes. Useful if your unit is far away from the target but you want to send it to guard the moving target. I do not use it because there are cheaper alternatives (like using a FollowTo until your actor is very close to the target, and to then shadow it, or if the target is slower than your actor, you could also use something like the default SimpleMove action [without any pathfinding whatsoever] ).

4) ShadowTo : Shadow to exactly copies the path of the target. First it calculates a path to the target, and then it checks every frame whether the center of the target is more than a certain distance away from the last node on the path. If it is, it will add the current target position as a last node to the path. Since apart from the first path calculation no Pathfinding is being used, this is much cheaper than say Follow. This is why I use it to follow fleeing units and other targets that are close by.
It can also allow you to "draw" a path. Just create a setup where you do a mouse pick every frame and set the target to that hit position. Then let an actor follow your target. You will now be able to draw a path the actor is going to follow along.

5) Shadow : Just like Shadow To, just without the finish

6) FollowPath : Sometimes you've got loads of units following exactly the same path. An example for this is a tower defense game. Instead of recalculating the same path over and over, you can just save the path in a global variable and use this MoveMode to follow that path. Since there are some options that edit the path, like the option to connect the current actor's position to the closest node on the path, you might want to use the "DuplicatePath" actions before using a path.
All in all this action can be very useful on mobile devices.

7) fleeTo : This is a pro feature from Aron Granberg's package, I really did nothing more than implement it in the action. It allows for a very cheap way to flee from something. You can also use it in the free version, but it is just a cheap mockup of a MoveTo mode with a target that lies somewhere away from the target. So unfortunately it's just as expensive as the normal MoveTo.

flee : -"-

9) RandomPath : Like Flee, this is a pro only feature, it can calculate a very cheap random path of a certain length, the free users again use a mockup MoveTo instead.

[Voke]

Hi, I checked your first script today, but the object only moves to the first waypoint and stops then. Playing around with the variables didn't help. Just to let you know

[kiriri]

ah about that, sorry, the default values should definitely be different.
Try something like 3 for both failure and next waypoint.
I'll update the action right now...

EDIT:
Updated it!

[ZeroSigma]

Thanks for this script, I've taken the liberty of cleaning it up a bit and adding a few extra comments.

Edit: Corrected some minor bugs in the stuff I modified. Hehe

[kiriri]

thank you, that is very appreciated. Can I add it to the top post (with credits of course) ?
I will write a simple wrapper now and implement it in the move to target action. I hate wrapper modules just as much as the second guy, but I see no way around it unless you want to recalculate the entire path each time you want to change it. Furthermore that way we can also implement a follow path action to save performance and make mass movements possible. I picked this up as my current project now so there should be some progress over Christmas etc.

Anyways, the number of downloads do say that there's a bunch of people interested in these actions. That's nice to see

[hannibalov]

Hi, I'm interested in this action, but I can't find it   I tried here https://hutonggames.fogbugz.com/default.asp?W714 , but no cigar. Where is it?

(EDIT) idiot of me, it's included in the post. Sorry for that

[then00b]

I'm definitely interested to see more of your work in the way of A* actions. It's been challenging trying to work around A* with the default actions.

[ZeroSigma]

Hey kiriti, its not problem you can add the action to the top post, it is mostly your work I just cleaned it up a bit.

Anyway guys remember to get this working you need to install the A* Pathfinding Project unity package  created by Aron Granberg. There is a free version here: http://www.arongranberg.com/unity/a-pathfinding/. The Pro version is also worth looking at if you are going to do heavy pathfinding.

[hannibalov]

Hi, I added angular speed so that agents look towards their next path point. Something cool would be to add a "begin stopping distance" so that you can trigger stop walking animations or so.

PS. I don't care much about credit for just a few lines of code, so if you think this is interesting go ahead and post it without asking

[hannibalov]

woops, I found an error. Sending the correction with a little addition to play nice with mecanim. Now you can set the variable that sets the moving animation in mecanim.

I would like to have acceleration also, but I'm not sure how to code that

[kiriri]

@Everyone
I added some more functionality to the base scripts, created a Follow Path and CreatePathToTarget action, and added the actions to check the calculating state of a path as well as its length.
You can now either use a gameObject with a Seeker component on it to save/load a path, or an object variable of the type Seeker. It was important for me to be able to use object variables, though seriously, I forgot why. Anyways, I'm sure it'll come back to me
This package (top post) is alpha for a reason. It'll throw a lot of error messages into yo9ur face, though non of them seem to really cause any problems whatsoever. I'll see if I can find the things causing them tomorrow. Or maybe you guys will spot them. Whatever  

@hannibalov
Thanks, I'll look at it tomorrow and make it merge with the new version I made.

@ZeroSigma
Ok, for now I continued on the basis of those modified scripts, though I may have somewhat destroyed the order while I was trying out new things. I'm definitely not an orderly guy

[hannibalov]

Great

Another action could be the FollowObject. It should be quite similar to moveTo, just resending the target whenever it moves. I tried to do that today, but I'm concerned with performance (I'm creating a crowd simulation with lots of agents). Is there a better way to just call the StartPath on and on? Maybe GetNewPath would be more efficient

In addition to all this, local avoidance would be great. I'm new to A* pathfinding, so I don't know how they implement that, but watching this video

it looks like they solved the problem. It says 3.2, maybe we'll have to wait...

[then00b]

Excited to check out the updated action. Thanks for all your work, kiriri!

Edit: just noticed ZeroSigma and hannibalov have also been helping. Thanks, guys!

[hannibalov]

Hi, I couldn't wait and I decided to implement the FollowTarget action. It works decently with a catch... it's executed as long as you are in a following target state, meaning that you can't set it to follow a target and move on to another state. Anyway, for my project the job gets done, so I just left it like that.

Maybe someone here can improve it. By the way, I was concerned with too many path recalculations, but performance seems ok (100+ agents moving around at 60FPS). If someone knows more about all this, no need to ask for my permission. As this is basically a mashup of kiriri's script, I suppose he would be the one to ask