Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

A* Pathfinding 2.9 Is Released (Unity 3 Compatible)

Discussion in 'Assets and Asset Store' started by half_voxel, Nov 16, 2010.

  1. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Hi Chris

    Ah, so you are working with CheckCapsule, how is that working, in terms of quality?
    I have been sketching on how I would go about implementing it with CheckCapsule, but I have always ran in to cases where it wouldn't work.
     
  2. ChrisPaulson

    ChrisPaulson

    Joined:
    Nov 16, 2010
    Posts:
    43
    Check capsule seems to work for me - I get voxels/nodes where I expect them, the only problem is speed. However I haven't tested it on a lot of scenes and have not done it on any large scenes.

    When I get home tonight I could post an example of my code if you like.
     
  3. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Nice!

    That would be great!
     
  4. ChrisPaulson

    ChrisPaulson

    Joined:
    Nov 16, 2010
    Posts:
    43
    Here is my Navmesh code - the main bit is navgrid.cs

    Warning - It's WIP and I'm new to Unity and new to c# so it might not be the best.

    Make a game object and add the navmesh component.
     

    Attached Files:

  5. jaguillard

    jaguillard

    Joined:
    Mar 1, 2011
    Posts:
    4
    I'm having some issues with using a Mesh. I had my artist created a simple plane that defines the walkable area of the environment. But when I run the program, I get the error:
    My target is standing over the grid.

    If I hack the Polygon.Contain() function to return true if the if check passes, I get a path but it is completely wrong, so I just changed that back. I noticed a post earlier about polygons having a limit to their neighbors, but as far as I can see, all polygons have, at most, three shared edges. Any idea what could be causing the issue?

    I've attached the mesh file below.
     

    Attached Files:

  6. ROCFriesePoort

    ROCFriesePoort

    Joined:
    Mar 27, 2009
    Posts:
    107
    Hi,

    I'm trying to use UnitySteer with the Pathfinding framework but I've no qlue how to do this. I've tried some setups but to no succes. Does anyone succesfully managed to get this to work and is able to explain how to set this up?

    Thanks!
     
  7. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Hi

    I have finally managed to get my Recast translation working!
    I can throw in any level geometry I want, and get a solid navmesh out!:D

    There is still a lot to be done, such as eroding the voxels and making the contour simplifier better, and I haven't actually tested it with multiple levels now that I come to think of it.

    I have also done a simple test on how the speed compares between the two versions (2.9x and 3.0).
    It isn't really that reliable, because the tests weren't done on the same map, but it is mapped to the number of searched nodes, which should give a quite good view on how fast it is. 3.0 seems to be faster! But surprisingly though, using multithreading is a tiny bit slower, but probably within the error margin, and of course, with multithreading the level still runs at 400-500 fps.
    See attached images.

    The navmesh you can see on the screenshots took about 160-220 ms to calculate for the recast code, but then my completely unoptimized code from translating that to a usable navmesh took another 300 ms.

    PS: Haven't forgot about you others, I will answer you later ;)
     

    Attached Files:

  8. ChrisPaulson

    ChrisPaulson

    Joined:
    Nov 16, 2010
    Posts:
    43
    This is great news!

    Only trouble is it might mean all my recent hard work might just be thrown away!

    300ms for generating that mesh seem pretty fast - seems you've done a good job on the recast code translation.

    I assume you've done it as a translation and not as a c++ plugin?
     
  9. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Hi Chris

    Thanks!
    Yeah, 300 ms is quite good, but it's still about half the speed of the original Recast code since it was written in C++ and not C# which is quite slow compared to C++, and yes I have translated it, not made a plugin.
     
  10. ChrisPaulson

    ChrisPaulson

    Joined:
    Nov 16, 2010
    Posts:
    43
    Not a plugin - again this is really good news as people will be able to use it with Unity free.

    I thought c# was 95% the speed of c++?
    One of the clever things recast does for speed is the way it organises it's memory/arrays which I guess might take work to replicate with c#

    If you manage to all convert the crowd manager stuff I should think a lot of people will be very pleased as its far better than using opensteer.

    Have you managed to convert the tiled mesh implementation (which enables the dynamic updating of the navmesh for dynamic/moving objects)?
     
  11. ChrisPaulson

    ChrisPaulson

    Joined:
    Nov 16, 2010
    Posts:
    43
    PS I should say, if you do a good job of the recast conversion I'd be happy buy it from asset store (as long as the price is not too steep).
     
  12. ChrisPaulson

    ChrisPaulson

    Joined:
    Nov 16, 2010
    Posts:
    43
    Have you had a look at:-
    http://www.critterai.org/nav_u3d

    you might find it useful, it uses nav meshes created by recast and is in Unity. Also it does very good documentation of recast theories.
     
  13. PrimeDerektive

    PrimeDerektive

    Joined:
    Dec 13, 2009
    Posts:
    3,090
    Wow thats really neat Chris, unfortunately I don't have Pro, but it definitely looks cool. I wonder how that slipped under the radar, I've never seen anyone post about it on the forums here.
     
  14. ChrisPaulson

    ChrisPaulson

    Joined:
    Nov 16, 2010
    Posts:
    43
    I can't take the credit for it I just found it by Googling (recast,unity etc...)
    The chap who did it (Steve) is really clever but doesn't seem to want to advertise the fact.
     
  15. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Yeah, I have seen that one, I have also wondered why no one has posted something about it.

    @Frido

    I would give you some advice on how to use it with Unity Steer, but unfortunately, I haven't tried to make it work myself, so I can't give you any right now.

    @Jaguillard

    I tried your mesh, and I could get it working directly.
    Things to check: Are your start and end objects pivot points completely inside the white bounding box, if not you can increase the Bounds Margin variable.
    Are your start and end objects pivot points above the mesh (although only the start point should have to be above the mesh).
     
  16. Patyrn

    Patyrn

    Joined:
    Feb 17, 2011
    Posts:
    57
    I'm attempting to weight nodes which have been travelled before, so that units tend to spread out and take varying paths. My approach is to take the path returned to each unit, and loop through the Vector3s calling GetNode with them, and incrementing the penalty variable. My problem is that this often results in an IndexOutOfRangeException.

    Any idea why that would happen, or if there's a better approach to what I'm doing?

    EDIT: Nevermind. I found your GetNearestNode AstarUser script.
     
    Last edited: Mar 6, 2011
  17. Patyrn

    Patyrn

    Joined:
    Feb 17, 2011
    Posts:
    57
    Is there a way to stop it spamming this type of thing:

    A* Pathfinding Completed Succesfully : End code 4
    Time: 0.00206852 Seconds
    Frames 1
    Average Seconds/Frame 0.00206852
    Points:48
    Searched Nodes848
    Path Length (G score) Was 626
    UnityEngine.Debug:Log(Object)
    Path:Calc(Boolean) (at Assets/Pathfinding/AstarPath.cs:1269)
    <CalculatePaths>c__Iterator5:MoveNext() (at Assets/Pathfinding/AstarPath.cs:548)

    I tried all the various checkboxes I could find and it kept doing it.
     
  18. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    @Patyrn

    In 2.94, there is no way of stopping that, except commenting out that line of code which should be quite easy.
    3.0 will have four debug modes - None, Normal, Heavy (a lot more info) and InGame (shows the debug info using OnGUI).
     
  19. Patyrn

    Patyrn

    Joined:
    Feb 17, 2011
    Posts:
    57
    Cool. I look forward to it.
     
  20. reset

    reset

    Joined:
    May 22, 2009
    Posts:
    393
    "I have finally managed to get my Recast translation working!"

    Surestone,
    this is the most exciting thing I have ever heard about since using Unity!!!!!! I can't wait to try it/buy it.
     
  21. Gaspedal

    Gaspedal

    Joined:
    Mar 29, 2009
    Posts:
    376
    @sturestone: First of all thank you for your great support and pathfinding. But I have modified your script, because I'm using a lot of Nod disablers/enablers and all enablers are visible as sphere objects. This causes an "Verticles>600.000" Error if scene window is open.
    I have replaced some lines in "AstarPath.cs" from "Gizmos.DrawSphere" to "Gizmos.DrawCube" and now it works. Cubes are better and needing only 8 verticles. I think this is important for all users and you can change this too.
     
    Last edited: Mar 9, 2011
  22. jaguillard

    jaguillard

    Joined:
    Mar 1, 2011
    Posts:
    4
    Okay, I doubled checked the exact points of the character vs the debug lines being drawn. Seems like even at 0.0 coordinate, the grid is forming higher than the floor. I pushed it down with a negative Y offset and up the bounds and it end up working.
     
  23. Anthony85

    Anthony85

    Joined:
    Mar 9, 2011
    Posts:
    30
    This looks real interesting. I downloaded it yesturday, i'll hopefully get the oportunity to try it in a game project (I'm just getting my feet wet with unity at the moment :p Very novice user, I have a bad tendancy to run before i can walk with things like this :p)

    I just have one question.

    How does this work on non-static game objects like ships? Like for instance, having the crew/soldiers walking around ondeck? (like in Rise and Fall: Civilizations At War, or Empire/Nepoleon: Total War)
     
    Last edited: Mar 11, 2011
  24. magomigo

    magomigo

    Joined:
    Mar 9, 2011
    Posts:
    11
    Hi everyone... and hi Aron,
    I'm using A* Pathfinding 2.94 in my project.
    Setup is made of a Grid, quite large (600x600 node size 1), calculated scanning level world in which there are lot of buildings.

    Everything works, memory usage is maybe high, but major problem comes when I try an load a new scene.
    All game objects are destroyed correctly...but seems that memory addressed by grids and nodes is not released propely making the game hang after a few scene changes.

    Does anyone has the same problem? or is there a better way to setup pathfinding for big worlds at runtime? or (this is the last question) is this problem known and maybe solved in the upcoming version 3?

    Thanks
    Bye
     
  25. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Hmmm... Where could that be saved between levels...
    I could run some tests to see what's causing it.
    And btw, how do you monitor memory usage? GC.GetTotalMemory, or?

    I'm thinking that it might be saved in the Open list, which is static and is never cleared, this might save a reference to a node in the previous scene, and that will thus link to all other nodes connected to it (usually the entire grid)...
    And yeah, 600*600 is more than the system (2.94) is designed to handle.

    @Anthony
    Well, it doesn't work at all for those cases (if you don't want to rescan the grid ever second or so, which would drop the framerate to like 0.5 fps ;). Firstly, it is not able to rotate, which a ship would, but you can fix translation by looping through all nodes and translating their positions (vectorPos)... and you would also have to do a lot more half complicated stuff to get it working. I would say, don't try, since you are new to Unity, and it will probably just give you a headache ;)
     
  26. GarethF

    GarethF

    Joined:
    Oct 6, 2010
    Posts:
    16
    Aron, just wanted to say thanks for such a great resource. Been testing it this last week and I'm loving it.
     
  27. magomigo

    magomigo

    Joined:
    Mar 9, 2011
    Posts:
    11
    Hi Aron and thanks...
    I'll check what you suggested and to aswer your question...I've made several test looking at the profiler (I'm using unity pro).
    In this tests, I isolated all subsystem present in the game...mainly testing different amount of content in one scene keeping low and costant the resources on the second scene switching between the two every 60 seconds.

    This made me find that the problem was in pathfind system, of course if the grid used is small the problem is less noticeable but on a grid of 600x600 with several hundreds of object...memory allocation for pathfinding can reach 200Mb easily.

    So you can understand that if no release occur...evething crash very soon...
    I cross the finger to solve the problem...You have done a great job!
    I'll look forward to next release for future projects!
     
  28. JositoPJ

    JositoPJ

    Joined:
    Mar 19, 2011
    Posts:
    10
    Hello,
    I installed unity 3.3, but the version of A * Pathfinding I have installed (2.93) does not work and I can not download version 2.94 of Aron's website.
    Someone could send me the package for version 2.94?
    Or tell me a website where you can will download the package (other than the web of Aron)?

    P. S.: Sorry if my English is not very good

    Thanks,
    Pedro.
     
  29. MrMetwurst2

    MrMetwurst2

    Joined:
    Jul 16, 2009
    Posts:
    253
    Hey Aron, I've finally got to the stage in my game where I wanted to implement AStar and your website is down !! Noooo :)
    Do you have an ETA to get up and running again?

    Is there somehwhere else I can get AStar 2.94?

    Cheers for your awesome contribution.
     
  30. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Hi Everyone,

    Sorry for my website being down, I'm moving to new servers (hopefully faster), I'm trying to get it working as fast as possible.
    Here's the UnityPackage with the latest version (I think it's the latest one), the complete example project is too big.
     

    Attached Files:

  31. jomeier

    jomeier

    Joined:
    Jun 5, 2010
    Posts:
    45
    Hi Aron,

    thanks for your effort. Could you also post the documentation for your package, please? I'm absolutely eager to try it.

    Thx and best regards,

    Josef
     
  32. MrMetwurst2

    MrMetwurst2

    Joined:
    Jul 16, 2009
    Posts:
    253
    Hey Aron,
    Thanks for the link, but I'm getting a lot of errors in Unity 3.2 as soon as I imported the package so I'm thinking this may not be the correct version.

    Do you want me to host the full package for you until you get up and running, I can give you some webspace if you like.

    Just let me know.

    Cheers, Phil.

    [Edit] I've re-imported and it seems to work fine now. Not sure why the errors were there. Thanks Aron :)
     
    Last edited: Mar 22, 2011
  33. JositoPJ

    JositoPJ

    Joined:
    Mar 19, 2011
    Posts:
    10
    Hi Aron,
    Thanks for the link, Now I can continue¡¡¡
    Thanks for everything.

    Pedro, Spain.
     
  34. JositoPJ

    JositoPJ

    Joined:
    Mar 19, 2011
    Posts:
    10
    Hello, to see if anyone would know how to help me out.
    I created a city, with 919 roads and each road has 2 lanes (some are 1 or 3, but a few). I created a mesh by "Astar Path" and using the "Procedural"(that I've done well, so that the mesh is of the form: 1 lane = 1 area, for a vehicle traveling on the lane without leaving).
    In total, 1809 areas have left me, but I the following problem arises: How I can move from one screen to another? Should I connect the mesh to generate a single mesh?
    This problem I get when a car traveling on an area (which would be a rail), if I want to change area (ie rail) will not allow me to be a different area.

    Thank you very much,
    Pedro.
     
  35. Disaster

    Disaster

    Joined:
    Oct 31, 2009
    Posts:
    43
    Any ETA on when you'll be back online? Looking forward to trying this out.
     
  36. Patyrn

    Patyrn

    Joined:
    Feb 17, 2011
    Posts:
    57
    I am having a problem with SetNodesWorld. I'm trying to use it to mark parts of the navmesh as unwalkable when I build, and clear them if the building is destroyed. The issue is that every time I call it I get a message "Flood Filled 4865 Nodes, The Grid now contains X Areas", where X is +1 for every time I call it. It appears to be creating a new grid every time.

    Any ideas?
     
  37. Disaster

    Disaster

    Joined:
    Oct 31, 2009
    Posts:
    43
    If anyone happens to have the latest full package and wouldn't mind hosting it, I'd really appreciate being able to give this a go :)
     
  38. SarperS

    SarperS

    Joined:
    Mar 10, 2009
    Posts:
    824
    I would also appreciate the latest full package and wouldn't mind hosting it.
     
  39. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
  40. Disaster

    Disaster

    Joined:
    Oct 31, 2009
    Posts:
    43
    Thanks! You made my evening.
     
  41. MrMetwurst2

    MrMetwurst2

    Joined:
    Jul 16, 2009
    Posts:
    253
    No problem Aron. Thanks for sharing your work.
     
  42. Avo

    Avo

    Joined:
    Dec 4, 2010
    Posts:
    236
    Aron, ive been having a bit of trouble with the "Scan()" command.

    Whenever i reference it it comes up with the error
    "Dungeon Generation.js(84,9): BCE0005: Unknown identifier: 'Scan'."

    Any idea why?
     
  43. jomeier

    jomeier

    Joined:
    Jun 5, 2010
    Posts:
    45
    Hi Aron,

    could you also provide a link to the documentation for your package? That would be very helpful.

    Thanks
     
  44. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Sorry, I can't. The documentation is wordpress based so I can't upload it :(

    @Avo
    Since you are using javascript you should place the 'Pathfinding' folder inside the Standard Assets folder. Also, since the Scan () function doesn't exists in your script, it will throw that error, you need to call something like myAstarScript.Scan () where myAstarScript is an AstarPath component. In most cases you could just call AstarPath.active.Scan () though.
     
  45. tODDk

    tODDk

    Joined:
    Aug 14, 2009
    Posts:
    50
    Thanks for the extra file host for the amazing scripts. :D
     
  46. LucasDaltro

    LucasDaltro

    Joined:
    Oct 31, 2010
    Posts:
    236
    I'll really use this on my game thank you!
     
  47. LucasDaltro

    LucasDaltro

    Joined:
    Oct 31, 2010
    Posts:
    236
    The site seems down:(
     
  48. Avo

    Avo

    Joined:
    Dec 4, 2010
    Posts:
    236
    Thanks Aron! That fixed the problem, now my map is scanning the world after its been generated! Your AI is an amazing time saver by the way.
     
  49. Patyrn

    Patyrn

    Joined:
    Feb 17, 2011
    Posts:
    57
    Just reposting this in case it got lost in the shuffle. It's really holding me back.

     
  50. Disaster

    Disaster

    Joined:
    Oct 31, 2009
    Posts:
    43
    Would be good to get the documentation back online. I love this script but it's kinda hard figuring it out without a starting point. If I can help at all (hosting or whatever) send me a message.