A* Pathfinding 2.9 Is Released (Unity 3 Compatible)

Hey guys,


Im testing this amazing work and so far everything is going good, im following the guide at the Arons website by surfing the website through the googles cache..

but theres one thing im missing.. the AIFollow script.

does any one has this script? can you guys please upload it or post it here please?

im stuck without this..


Thank you so much!

Best regards,
-Brian.

 

@Patyrn

Sorry, I forgot about it.
The script isn't creating a new grid every time, what it does is that it flood fills the nodes around the area (Bounds) you updated, but since it doesn't know if the update will split the area it was placed on into two (too slow to check) it cannot reuse that area's id, so it will create a new one. So some areas might be unused, that's why it always increments by 1.

@zyndro

Here it is (attached).

 

thank you so much!
i really appreciate it!

amazing work with this project.

 

Hi again Aron,


i think i have it complete, its not working as it should, i must be doing something wrong, im checking it..

but the thing i want to ask is..

im trying to create a flying object, that allows to follow waypoints in both axes ( X and Y ), at the moment ive manage to create the grid but at the ground level, the object reach the target in the ground, but its possible to make it reach the object in the Y axis aswell? like climbing in the air?


Sorry my english, thanks again!
-Brian.

 

So what exactly does that mean for what I'm trying to accomplish?

If I do this:
AstarPath.active.SetNodesWorld(true, new Rect(xyz.x-1, xyz.z-1, xyz.x+1, xyz.z+1), 0, true);

to mark nodes unpassable, do I increment gridId to mark them passable and call this the next time?

AstarPath.active.SetNodesWorld(true, new Rect(xyz.x-1, xyz.z-1, xyz.x+1, xyz.z+1), 1, true);

 

I've just started to use this for a project im working on and im getting a problem with the AIFollow.cs and im getting the following error

how can i fix this?

 

The website is up again!
At last the domain name transfer is done.

@Patyrn
No, grid id and area values are not the same thing. Grid id is the index in the grid list (0 is the first grid, 1 is the second etc. etc.). Area is used to mark nodes which can be reached from each other, There is (almost, there might not be one if you have a low "max angle" value) always a valid path from one node to another if they are in the same area.
And btw, "SetNodesWorld" is actually indented for internal use, just "SetNodes" is the function indented for being called by other scripts.

@fmaddict
Since the website is up again now, you can download the full example project with everything included.

 

@Zyndro

Do you say that you want to pathfind in 3D (i.e nodes would be cubes instead) or do you just want 2D pathfinding but the movement script just follows the ground even though your target was some distance up in the air?

 

One of your pages on your website doesn't appear to be working.
Under Unity -> A* Pathfinding -> Documentation -> How to change the grid at runtime
or
http://www.arongranberg.com/unity/a-pathfinding/docs/api/runtime-change/
I get a page not found

Thanks!
Luke

 

@Aron,
Any beta date for your navmesh system?

 

Oops, though I had fixed that. Anyway, it's working now.

@Tatoforever
Not yet, I still have a lot to do, but it is progressing steadily.

 

I am having a problem with this. When clicking on a piece of geometry, a wall for instance, the player continues to run at the wall, never making it to the point which seems to be "inside" the wall.

What's the best way to handle this?

 

Awesome, keep working hard.

 

@Jonbonazza

You could try to change the Seeker variable "endPoint" (I think) to "Snapped" instead of "Exact". Otherwise this is best handled within the local movement script (the script which moves the player) using for example raycasting.

If you are using the AIFollow script you can also try to raise the "Max Stop" value.

 

I’m trying to apply your code to my project and I’m having some difficulty. Right now, all I’ve done is import the allrequiredassets2_9 (version 2.94) into my scene on top of the controller folder and the scripts in it (the one with AIFollow and others. I had to pull those from the example).


I’ve created my grid using a quad tree (since my map falls under “massive”), created an object with character controller, seeker script, and AIfollow, a target, and attached clicker to my main camera (as well as associated object to seeker, target to target, and mask to everything).


Now when I run the game, my object does not move every time i click. It roughly works 25-40% of the time. It seems to be very dependent on where the object is located and where I am clicking because a spot that worked once won’t work again after the object moves.


I have a box collider on the ground plane, which I thought may be causing some drag and stopping the object, but that shouldn’t make a difference since it is the same in your example. Do you have any ideas?


PS: Can you please fix your pictures in your tutorials. None of them work.

Edit: I think I might be retarded? Double clicking seemed to fix it. I click once to move the target and click again, on the target, to route the object to it. Is it intended to work that way? In the examples it's always a single click that gets it to work...

EDIT EDIT: Figured it out... My sphere was below the grid during the first click, then when i clicked it again, it went up enough to go over the grid and thus allowed pathing. I edited the clicker script to account for some extra height on click and now it works perfect.

 

Hi Darknuke

Great that you solved it! Sorry for taking a long time to answer (errm... not answering at all).

Ah, yeah, I have those images too, they must've got lost in the server migration, I will try to find them.

 

Hi @sturestone is there documentation about image navigation done? Also I'm encountered some problems with navmesh navigation.. Trying to figure out details how to do propper setup.

 

Image navigation, you mean texture mode?

 

yep. thank you

 

Also can I use directly navmesh from critter navmesh generation as mesh for a*? It looks like when i create navmesh in 3ds max at import it get rotated 90. and also I'm unable to scale and position it match properly.. Are you planing to add support for critter navmesh? I tested it and it produces quite nice results.

 

No there is no documentation done on that.
The nearest is the description text in the Texture scene in the example project.

I can give you a brief explanation here:
The script will create one node for each pixel, like a grid. If the greyscale value of the pixel is lower than Walkable Threshold it will become unwalkable (basically, black nodes are unwalkable). If it isn't unwalkable it will get the penalty value from the red component of the pixel and scale that with the Penalty Multiplier. Remember white does contain red since it is r,g,b (255,255,255) so don't use that for no-penalty nodes, use green instead. Then it is just to use it like a regular grid.

You can rotate the mesh in the editor with the rotation settings, also make sure you use the correct handedness for the mesh. Most meshes are rotated 90 deg by default on import, when you place them in the Unity it applies -90 deg rotation to that GameObject by default to account for that.

In 3.0 I'm adding support for generating navmeshes from any level geometry, this will be similar to critter's since it is based on the same source (Recast), though I haven't actually tested critter's AI.

 

Btw I just wanted to say that I'll be buying two licenses for this once I have funds. Basically I spoke to the author about a bug and it was fixed the next day. He is polite, hard-working and deserves every penny he gets for what is an AAA class of pathfinding.

Do you guys know that you can generate a navmesh just from gameobjects for ultra precise pathfinding? I didn't know till I experimented as it is not documented. It is fantastic and called List in the options if anyone wants to check it out.

With List, just make a root game object, then inside that the child gameobjects are the points of the navmesh. Pass root to List in unity (not one line of code needed for this btw) and it builds the pathfinding for you. Unbelievable simplicity.

The author relies on a trust model to pay him if you use this. $100 is cheap, and if any of you guys are using it on appstore or anywhere else, please consider paying him as you will get 3.0 as well. Fantastic system for the price.

 

Yep critter uses corridor based approach instead of middle edge..
I suppose that texture for navigation should have red/write enabled so It is possible to manipulate navigation texture in realtime? Is there some additional room in texture to store my custom data, like cover locations, hazard zones etc? Does not have it open right now but I'll ask master would be hard to rewrite code for navigation to use alpha channel instead rgb? Or this modification damage somehow pathfinding?

I'd like to propose some solution to enhance this already great package [if they are already implemented I'm open to discussion how to add more features]:
1. use RGBA texture, if opinions below damage resolution of pathfinding use higher channel bit depth
2. alpha px color 255 = unwalkable. Penalty decreases to alpha px 0 which means 100% walkable
3. red channel = use to store agent specific informations [resolution of 256 should be enough to store things like use of specific animation, weapon, general alert level, cover location, ledge position etc]
3. green channel = use for averaged slope at pixel position this means resolution about 26' (minutes) with 256 values in range 0-90 degrees
4. blue channel = may be used for cover, "interesting" places, surface type description [road, mud, rock, sand], baked shadow for stealth units etc.. Or simply mask pathfinding area to "fog of war"

This way returned nav data could be more rich: path array, red array, green array, blue array

And also I'd like to ask if it is possible make search over multiple nav textures..?

 

I must just say that I'm freshle instaled ms express and diggin into scripts of both a* and critter.. I noticed that critter supporting [they're documented only in source code] some features like setting custom flag for navmesh polygons which lead me to write above post.. I'll have some more questions when I'' be more comfortable with code cause c# is new world for me right now..

 

This seems like a simple question, but how do I stop a seeker from pathing while mid path? There's seeker.StartPath, but is there a StopPath equivalent?

Also, when I run this code:

Code (csharp):

1. InvokeRepeating("WanderSeeker", 0, 6);

- That is run in the Start method

Code (csharp):

1. void WanderSeeker()
2.     {
3.         Vector2 rnd = Random.insideUnitCircle;
4.         Vector3 target = new Vector3(rnd.x, 0, rnd.y) * 10;
5.         target += objPlayer.transform.position;
6.         seeker.StartPath(seeker.transform.position, target);
7.         targetGO.position = target;
8.     }

I can get it to run once, but after that the unit won't repath. The target changes, so the endpath must be changing, but the object won't path to the new endpoint. Why is that?

If it helps. After the seeker gets to the end of its path, the blue debug line for the path looks like it's tweaking underneath it in the -Y direction.

EDIT: Well deleting and re-attaching AIFollow and Seeker fixed the problem, but I still would like to know how to manually stop a path.

 

It is interesting you point this out, because if you have Error enabled as the default response, it will not clear the array, and this will cause issues. Does anyone know how to clear the path manually?

 

TIP: for critter output navmesh to use in a* navmesh and roughly match scale set in import settings of produced and saved critter generated navmesh scale to 0.0515.. trying to figure out how to remove nonconected little islands..

 

You can make holes in navmesh by using gameobjects with colliders that are on the obstacle layer mask.

 

I'm aware of that.. Just some adjustments on my previous tip, scale on import problem to me happened when i imported models with diferent source units. Other than that resulting critter produced navmesh exported and saved to project should be fine without additional rotation or scaling.. This are great packages and you both guys should cooperate in this.. It will be great!

 

Please, where can obtain feed for changelog? anyone knows? Just realized that I'm using old version so I upgraded for next tests.

 

Hullo,

First off, great work on this, never done pathfinding before but was able to get some stuff running really quickly. This is really superb work. Having a bit of an issue here though...

I'm trying to emulate the House scene that comes with the demo for my little level. It has two different floors and should allow units to path underneath the "roof" of the second floor. The entire level is one mesh collider, just like the house demo. But with my level, it doesn't seem to be calculating it right...here's what I have now.



I highlighted the problem edges in red. Ideally, I'd want these to be unwalkable nodes. In the House demo, it seems to be working the way I want it to, where the edges are blocked by the ramp without using any other colliders.

I have basically the same settings as the House demo: Node Size 5, my Mesh collider is not unwalkable, but it's layer is in the Raycast mask (using raycast with angle of 60, no normal for max angle calc, 7 height), collider check with radius of 0.5 height of 2...

Now I'm guessing this is because it's just check the angle between the two points and is thinking that they're okay (because the angle is under 60), but I just can't understand why it's working fine in the House demo and not here...

Also, I plan on having two grids (one per floor) but am just testing with one right now. Anyone have any input?

 

You can use the linker to add and remove nodes (node links tab), just use that.

 

sturestone,

Getting some pretty bad performance and wondering if you have any tips on what I can do to improve it. In these screenshots I have 6 entities pathing around and they are killing the framerate!




Any other info you need?

 

try to experiment with cache limit for paths and also at bottom is >Advanced try to experiment with this sliders also. It controls depth of search tree I think and thus speed of search.. Also check if agents are not asking for path all 6 at once (that can be that peak).. If yes vary them with small random value.
Good practice is also let them do some waiting behavior from time when they request path to time when they got one. Like "look around" that way they end up looking more natural instead rapid change in pathing

 

Some good tips, I will try them. I am putting in a variation to their seek times, each of those peeks is a search for one entity. I think the issue is I have two types of pathfinding use-cases, one for entities seeking the player when they have spotted him and one for waypoint walking, and I think I am using the same logic for both, which is bad because then the ones walking the waypoints are still re-calculating paths every second instead of once only.

 

Tried several things but still getting 4-6ms per entity per search which is terrible in a scene with many wanderers. I have a pretty heavy rig (8 cores, 8Gb Ram, ATI 5870, etc..) so it won't get any faster.

Anyone have any other ideas?

 

Activate them based on line of site? Can you drill down a bit deeper in the profiler to see what they're doing at that spike? Share as much as you can - 2 guards with similar LOS can use the same single check, etc.

 

Yeah I am still playing with it. I just finished putting into place my AI LOD system so that has helped a bit. But I am still concerned with the overall "hit" of finding a path.

 

Can you switch for "List" or "Mesh" for pathing to test performance?

 

Here is more from the profiler...

 

How many nodes are you searching? Post the whole Path Complete log message.

Search for @Performance in the AstarPath.cs script and AstarClasses.cs, I have some comments tagged with that in places where it is possible to hard-code stuff to get better performance, not very much, but I see in one case you have the Node.f property taking 9.5% of the total frame time, and I know that's one of the places where you can get better performance by hard-coding stuff.

 

I just digged this out! It's a MUST share here..

 

10492 nodes, of which 3378 are walkable

Here is log:



Oh and commenting out that line had negligible effect on the time taken to path.

 

Does that 2500 hits to the binary heap occur when a guard sees you? I'm just trying to work out why the pathfinding would be taxed so much for entities that effectively have pre calculated paths until they engage something. Is there something can do so that npc B only has to find a path to npc A and then follow the exact same (cached) path? I'm on vacation at the moment so it's only me, an iPad and a 4 mile beach with emerald water and fruity drinks, otherwise I'd be testing this out myself!

 

Oh man don't think about this on vacation!! Basiclly I have modified the AIFollow script so that I can use it for two purposes, Wandering (where the target is static and is a waypoint so I only search for a path once) and secondly for AI to chase/move to an enemy, of course this is dynamic so I need to calc the path over and over. However right the path is calculated every 0.5 seconds (roughly it has a small randomizer on it). However the spike happens on every search and you can the spikes at 0.5sec apart. I cannot really cache the paths as enemies are always moving around.

 

@Cupsster

I'm think I will add that to version 3.0 (custom flags for each node). Though I am a bit worried about memory when using grids though since one flag would mean 1-4 bytes extra per node. This could easily mean 20-100 kb extra data which isn't small for a feature which might not be used at all, especially for mobile applications. So perhaps I will only add this to navmesh nodes (polygon nodes) which are not used in such a high quantity as grid nodes.

@KrankyBoyGames

I mean how many nodes are you searching for each path call. It should say in the log message (if you have commented it out, then uncomment it) from a path being completed, the one in the Unity log, it doesn't say in the astar log.

Though since you can at most be searching 3378 nodes your 4-6 ms sounds a bit high. In 3.0 at least, I'm can search 1000 nodes per millisecond approximately (it is remarkably exact actually, at least on my computer). So it wouldn't take more than 3.4 ms. And I don't think the performance has changed that much.

What you can do is to spread out the spike. Adjust the Max Frame Time in the A* settings to something like 0.001 or 0.002, this would spread your calls over 2 or 3 frames and the framerate would get more constant.

@Cupsster

Wow, that's awesome! They have actually made a dedicated AI card!

One part was worth pointing out though:

As I said before, I can search about 1000 nodes per millisecond, which means 1 node per µs or 10 nodes per 10µs. This means my pathfinding implementation is only 10 times slower than theirs (and they've got a dedicated card to do it!). So my system would be 10-20 times faster than their comparable software solutions! Perhaps theirs is a bit more advanced, and returns more info, but it seems like mine is really fast anyway!

 

@Cupsster

Where you can find the changelog... Um... no idea, I have forgotten to write one. Anyway, for those who want to know, the last update 2.95 solved a NullReferenceException bug which could occur with Link graphs having multiple non-connected areas.

 

sturestone - I have attached my log with my wandering agents and their search data. I have not tried those changes yet (to MaxFrameTime), but will try that now.

View attachment $log.zip

 

Another issue, if you use raycasting for your grid and have areas that overlap at different heights you will get holes in the lower grid area (expected). I then used links to fill in the holes in the lower area (see image), however an agent in the lower section will TRY and use the path above it's head (at a higher level).



Is the only solution to use two grids one for each level and use links to connect them?

 

Just as a side-note, Here's a good overview of current game ai challenges, as well as their proposed solutions, as of April 2011.

http://aigamedev.com/open/editorial/open-challenges-fps/