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 Project : 2.8 beta is live!

Discussion in 'Made With Unity' started by half_voxel, Jun 23, 2010.

  1. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Since I have made so many improvements which I haven't released yet, I decided to release a beta version, which basically is the full project, but it isn't tested and I guarantee that there are bugs in there.

    :arrow: Here's a list of the major improvements:
    :arrow: Quadtrees : This enables you to search for paths in wide open areas really fast.
    :arrow: Path smoothing : I have three path smoothers, Bezier Curve smoother, Catmull Rom and Simple Smooth (subdivides the path and smoothes it).
    :arrow: The editor gui has many improvements, e.g a quick button bar at the top which enables you to quickly switch on and off debug info.
    :arrow: Up to 9+ times faster : I have found ways of caching data to make the script about 9 times faster, my average pathfinding calls are now calculated in milliseconds.
    :arrow: Multithreading : If you enable this, the pathfinding will have almost no impact on framerate (if you run it on a 2+ core computer), which is great (Warning: This might cause crashes on windows of some reason).
    :arrow: Correct paths, actually, in previous version paths have not been optimal in all cases, but they are now!

    Download it here: http://arongranberg.com/unity/a-pathfinding/

    Here's a video showing the speed of the beta : http://www.arongranberg.com/wp-content/uploads/astarpathfinding/videos/speedTest.mov


    I'm on vacation from tomorrow, so I will not have a lot of time to answer questions and such (most of the time I will not even have internet connection).

    A lot of questions have been asked and answered before, so if you have a question you can look in the previous release thread.
    http://forum.unity3d.com/viewtopic.php?t=43822

    Cheers
    Aron
     
  2. Dreamora

    Dreamora

    Joined:
    Apr 5, 2008
    Posts:
    26,601
    very cool thing, congrats on the new version.

    I hope I will find some time soon to experiment with it :)
     
  3. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530
    Wow this project has really evolved even since the short time I've been around.

    Great job!
     
  4. Creative

    Creative

    Joined:
    May 8, 2010
    Posts:
    184
    Great Job! Thanks Aron!
     
  5. Caliber-Mengsk

    Caliber-Mengsk

    Joined:
    Mar 24, 2010
    Posts:
    689
    Amazing! I've never been able to grasp how to program a*... XD Kind of problemsome with the fact I'm trying to program an RTS. May have to look at your code to get some ideas.

    Very cool though.

    (I'm one of those people that doesn't like just using someone else's code. I prefer to use my own, even if it's not as efficient. Personal preference.)
     
  6. KevS

    KevS

    Joined:
    Apr 21, 2010
    Posts:
    51
    A really good work ! Thank you ! :)
     
  7. gamesurgeon

    gamesurgeon

    Joined:
    Oct 11, 2009
    Posts:
    427
    Awesome!
     
  8. gamenut30111

    gamenut30111

    Joined:
    Nov 7, 2009
    Posts:
    399
    You never fail to amaze, great work!! :)
     
  9. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    I'm one of those people too! :wink:
     
  10. gamenut30111

    gamenut30111

    Joined:
    Nov 7, 2009
    Posts:
    399
    Yeah, your the person who gives the people code at a good price :D
     
  11. ColossalDuck

    ColossalDuck

    Joined:
    Jun 6, 2009
    Posts:
    3,246
    Neatomaleato. That is pretty sweet.
     
  12. liverolA

    liverolA

    Joined:
    Feb 10, 2009
    Posts:
    347
    wow,the most useful package for unity on the planet
     
  13. allen

    allen

    Joined:
    Mar 21, 2010
    Posts:
    81
    Really is. Saved me a ton of time and headaches.

    I've also gotten a big performance boost since switching to 2.8 beta.
     
  14. windexglow

    windexglow

    Joined:
    Jun 18, 2010
    Posts:
    378
    Before I get deeper into unit (very new to it) I'd like to know this is possible.

    Grid 0
    http://img707.imageshack.us/img707/7578/93098241.jpg
    Grid 0 and 1. They overlap on the ramp.
    http://img227.imageshack.us/img227/746/56119327.jpg
    Grid 1.
    http://img695.imageshack.us/img695/5288/15151667.jpg


    Basically I want those to connect ingame - I plan to procedurally generate my structures when the game begins, and to have multiple floors.
    Is it possible to connect those 2 ingame? It should be easy enough - look for nodes at a specific height, than match the X Y together.


    Likewise a small bug, when using quad-trees it doesn't work very well with ramps (trying to optimize it like it's part of the flat terrain)
    Workaround would be to place colliders on both sides of the ramp.


    Besides that, I'm loving it. I need to give some love to the procedural scenes and make sure my question isn't answered in it. Huge performance boost as well!
     
  15. Nic-Cusworth

    Nic-Cusworth

    Joined:
    Oct 12, 2008
    Posts:
    218
    Will try dropping the beta into my project today. Looks great. Will let you know if there are any problems.
     
  16. Nic-Cusworth

    Nic-Cusworth

    Joined:
    Oct 12, 2008
    Posts:
    218
    HUGE HUGE HUGE speed improvement on calculating the grid is the first thing I've noticed. Everything else is working just fine with no code changes. Took me a little while to find all the bits I needed to drop it in the project. Couldn't find a 2.8 'just source' download.

    Excellent work as always and if my project ever sees the light of day - money dropping at ya.
     
  17. mrbdrm

    mrbdrm

    Joined:
    Mar 22, 2009
    Posts:
    510
    if this comes with like anemy ai and follow ai scripts
    i will be happy to pay you 100$
    im not kidding realy good job man
    keep it up :)
     
  18. KevS

    KevS

    Joined:
    Apr 21, 2010
    Posts:
    51
    Hi !

    Is there someone who don't "scan map on startup" ?

    I try to save my grid to not have to scan it ("big" grid) but when i run my project, Unity crash xD
    I saw that some code is commented, i know that is a beta but maybe i'm bad :D
    (Create new AstarData, uncheck "Scan map on Startup", drag'n drop my AstarData object in the AstarData field, scan, save, run ... crash :D)
     
  19. KevS

    KevS

    Joined:
    Apr 21, 2010
    Posts:
    51
    Ok, i reimported all my scripts, it doesn't crash anymore but i have this error at loading

    Code (csharp):
    1.  
    2. NullReferenceException: Object reference not set to an instance of an object
    3. AstarPath.FloodFillAll ()   (at Assets\Pathfinding\AstarPath.cs:2026)
    4. AstarPath.LoadAstarData ()   (at Assets\Pathfinding\AstarPath.cs:3519)
    5. AstarPath.Awake ()   (at Assets\Pathfinding\AstarPath.cs:587)
    6.  
    I know sturestone is in holiday, but if someone have an idea :)
     
  20. mikesgames

    mikesgames

    Joined:
    Apr 16, 2010
    Posts:
    1,071
    looks really good!

    Will download at home!
     
  21. reset

    reset

    Joined:
    May 22, 2009
    Posts:
    393
    Hey this is truly amazing pathfinding!! Thank you.

    Quick question:

    How do I get the AI to STOP pathfinding - I code in JS.

    Do I send STAY to COMMAND?

    Thanks
     
  22. WarpedAxiom

    WarpedAxiom

    Joined:
    Oct 27, 2006
    Posts:
    245
    Väldigt snyggt jobbat, Granberg!
     
  23. fallingbrickwork

    fallingbrickwork

    Joined:
    Mar 16, 2009
    Posts:
    1,072
    It has been a real joy watching this project develop, congrats!

    I will try and implement this into my project as it is a far better solution than I could ever devise.

    Best Regards,
    Matt.
     
  24. cyangamer

    cyangamer

    Joined:
    Feb 17, 2010
    Posts:
    234
    We really appreciate the work you put into this project. I have a question:

    Because my "Seeker" is disc-shaped, using a capsule-shaped CharacterController won't work - I need a rigidbody. Is this plug-in set up to handle Rigidbodies well, and how would you suggest I replace my CC with a Rigidbody?
     
  25. SPIKY

    SPIKY

    Joined:
    Dec 19, 2008
    Posts:
    57
    Are you planning on implementing polygonal navmeshes in future releases, or is it out of the question?

    Current navmeshes seem to act like some sort of waypoint implementation (using the centre of edges of each polygon). Because of this, navmeshes have to be denser meshes than those in polygonal navmeshes (like described in http://www.ai-blog.net/archives/000152.html) which can describe an area instead of points.
    Or am I seeing this wrong?
     
  26. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Hi Everyone

    Back again.

    @SPIKY, yes I am working on implementing "real" navmeshes, but it is quite hard.

    @Cyangamer, The AIFollow script is the only script which needs a character controller, and that script is just an example script, so you can just plug in any movement script you want.
    Make sure to read the doc page for that though:
    http://www.arongranberg.com/unity/a-pathfinding/docs/othercode/

    @Reset, If you are using Continuous Target Search (as you wrote in the PM) you will have to first set the continuousTargetSearch variable to false (to make it stop computing paths) and then call myAIFollowComponent.Stop ();
    Just remembered that it is possible that it will fail, if it was computing a path while you sent the Stop command then it will start to walk later, so it is best to set the speed variable to 0 too.

    If you are using JS then you need to place all C# scripts you want to access in the Standard Assets folder (if you haven't got one, create one).

    @Blizhard, well, beta you know :wink:

    @Mrbdrm, no sorry, it doesn't come with enemy AI and such stuff, pathfinding is mainly about finding a path from A to B, everything else isn't really pathfinding.

    Thanks for all the positive comments! :D
     
  27. AlexZ

    AlexZ

    Joined:
    Sep 17, 2009
    Posts:
    263
    Hey Guys,

    We have been working with the Aron Grandberg A* system for a few months now. Great system.

    Recently though, we ran into a bug that has halted our production of our indie game for the past week.

    Something is causing the enemy AI to stop working, we cant figure out what it is.

    Things we noticed:

    in AIFollow, Stop is constantly being set.
    seeker.StartPath() is being called every second on our enemies (we have 20 max), since they are targeting the player that moves (using our own targeting code).

    When the bug occurs, PathComplete() does not get called anymore, and we are still calling seeker.StartPath(), it seems like something is breaking internally, maybe on of the threads breaks.

    We first thought it was due to our enemy being killed/destroyed while the StartPath() was calculating in another thread, so what we did was, when we killed an enemy, instead of destroying it, we added it to a queue, that would destroy it only when PathComplete() was called.

    This seemed to have fixed things, but after celebrating, we now realized the bug is still there, just more rare.

    Any ideas? we have spent so much time on solving this already with no luck. I tried the 2.8 beta to see if this is solved but same issue.

    Any help is appreciated,

    Alex
     
  28. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Hi Alex

    Very interesting problem.
    I wonder if this might have to do with a bug which I have heard about before but I couldn't really put the finger on when (and where) it occurred, the result is similar though, all seekers stop moving.

    I will have a look at this and contact you, hopefully tomorrow by PM.

    Btw, you said it was possible that one of the threads break, can you get the bug when you are not using multithreading?

    Aron Granberg
     
  29. Vectrex

    Vectrex

    Joined:
    Oct 31, 2009
    Posts:
    267
    check this out, it's really quite good and the licence is MIT (free to use how ever you want)
    http://code.google.com/p/recastnavigation/
     
  30. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Yeah I have seen it, very nice!
    I haven't begun trying to understand the code yet though.
    Of some reason it doesn't seem to run on intel macs/snow leopard though, and that's quite annoying.
     
  31. reset

    reset

    Joined:
    May 22, 2009
    Posts:
    393
    Isn't ReCast simply creating a navmesh from an imported mesh - which is available in the new version your pathfinding Surestone?
     
  32. XRA

    XRA

    Joined:
    Aug 26, 2010
    Posts:
    265
    this is a great resource, I haven't had a chance to try it yet but look forward to.

    It would be amazing if navigation meshes were supported. I'd suggest not being worried about having to create the navmesh manually, I'm not sure if you are looking for an automatic solution for the first implementation. In my experience I've always had to create navmesh poly by poly manually..

    Some other interesting things to think about with navmesh is having a way to group certain polygons under various types of objects which modify how the navigation across that polygon is handled... the simplest example is a polygon that stretches under a door and the object it is grouped under says it is a door and points to the door object.. and when the AI is about to navigate across that door poly it first must open the door.
     
  33. Vectrex

    Vectrex

    Joined:
    Oct 31, 2009
    Posts:
    267
    btw, can the package be made to be usable without 'installing' it. I had real hassles getting 2.8 to work from 2.5 with all the 'help' it was giving me ;)
     
  34. Tom163

    Tom163

    Joined:
    Nov 30, 2007
    Posts:
    1,290
    Excellent stuff here, I like it a lot.

    [update: found my problem]

    Documentation could be a bit more obvious in the "walkable check / mask" part, or maybe set up so that "default" is not by default included. :)
     
  35. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Thanks for you suggestions!

    @Vectrex, Ah, yes, I haven't really though about that, the update from 2.5 to 2.8 just using the UnityPackage might be a bit tricky.
    And I realise that those large help dialogue boxes were a bit overkill.
     
  36. Tilluss

    Tilluss

    Joined:
    Mar 5, 2010
    Posts:
    34
    Just a tiny little picky bug from me (v2.8); in the inspector it says the version i have is out of date and that the latest version is 2.52 which is actually a lower version than the one i have. Nothing operationally wrong, but i thought i would point it out none the less ;)

    Just testing it out and it's producing great results so far, very impressed!
     
  37. Adam-Buckner

    Adam-Buckner

    Joined:
    Jun 27, 2007
    Posts:
    5,664
    I'm missing something somewhere...

    I've looked at the A* script, looked here on the forums (2.5 2.8), and on Aron's site (http://www.arongranberg.com), and I can't find any instructions on how to upgrade from 2.5 to 2.8...

    I'm sure I'm being a bonehead, but what am I missing?
     
  38. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    No are not missing anything, it didn't exist an upgrade guide before.
    I have added it to the download page now though.

    @Tilluss, Ah, thanks!
     
  39. Arkdurath

    Arkdurath

    Joined:
    Jan 10, 2010
    Posts:
    64
    Hi all.

    Can anybody confirm if this is a problem:

    I have an A* component configured as a List of nodes, then, when a seeker is trying to go to a near node, it return a stright path between start(exact) point and end(exact) point ignoring obstacles. This is causing me problems in turns or sides where you can hide. It's like seeker doesnt understand about obstacles.

    I must say that i have 2.5 version yet, so i dont know if this is corrected in version 2.8

    I think that a fast solution is let seeker (configure with List of nodes) make a first straight line test, and if it collides, then return a normal path, but i dont know if this is working now.

    Thanks for your help

    LLORENS
     
  40. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Congratulations! You have found a bug! [Added to ToDo list]

    Check your email, the mail you sent has been answered.
     
  41. Arkdurath

    Arkdurath

    Joined:
    Jan 10, 2010
    Posts:
    64
    Hi

    No, thanks to you for this great library :) and hope my reports help improving it :)

    LLORENS
     
  42. Arkdurath

    Arkdurath

    Joined:
    Jan 10, 2010
    Posts:
    64
    Hi Sturestone

    I have a question about version 2.8:

    When you request a path, the resulting path will be optimized ??

    For example, if we want to go from node A to node D and our logical path is A-B-C-D, if all nodes remains on the same plane and there are no obstacles, will the result of this be a A-D path ??

    Thanks for your work

    LLORENS
     
  43. aubergine

    aubergine

    Joined:
    Sep 12, 2009
    Posts:
    2,878
    From version 2.8 i tried 3 samples;
    Bounds: worked okay.
    House: character falls from edges and doesnt stick to the path.
    Large: Crashes at start.

    Will try the others too and let you know.
     
  44. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    @LLorens

    Depends on which settings you use.
    If you use 'None' for the Simplification setting in the Runtime Settings, the path wil be A,B,C,D

    But if you use 'Full' the path will be A,D

    @Aubergine

    Hmm, doesn't sound good, I know the character in the House scene might fall of the edges sometimes, I haven't created a good enough movement script.

    With the Large scene, are you using Windows and have mutithreading enabled?
    Multithreading can sometimes make cause crashes on Windows.
    If not: Does Unity really crash or does it just hang and won't respond (like it is working on something really processor intensive)?
     
  45. aubergine

    aubergine

    Joined:
    Sep 12, 2009
    Posts:
    2,878
    im on windows and multithread is enabled, unity just crashes.
     
  46. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Then that's the problem (it is a beta after all).

    I have never been able to figure out why multithreading crashes so often on windows.
     
  47. MTracerStudios

    MTracerStudios

    Joined:
    Aug 24, 2010
    Posts:
    118
    Correct me if I'm stupid, but does this support dynamic obstacles? For instance, if in my RTS another unit were to stop in front of the pathfinding unit in question, would the pathfinding unit in question go around? This would be most important for building avoidance, as that would be completely dynamic.

    Thanks,

    MTracer.

    PS: If this is not already a feature, could you make it one? Thanks in advance.
     
  48. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    I understand that you are confused.

    Dynamic obstacles are supported, but you need to use undocumented functions in order to use it.

    The function needed is SetNodes (...) which enables you to manipulate the grid (only works with Grid and Texture modes) at runtime. But there is no built-in support for managing dynamic obstacles.
    Tell me if you want to know more (e.g SetNodes syntax).

    In your case building avoidance can be accomplished quite easy, but avoiding every unit is a bit hard because to get it to work you would need to use very small nodes.
     
  49. Arkdurath

    Arkdurath

    Joined:
    Jan 10, 2010
    Posts:
    64
    Hi Sturestone

    When you answered me about optimitzations of paths, did this optimitzation works with 'List of nodes' ? I mean, if you select 'Full' optimization, it works ?

    Today i downloaded and ported a copy of project to Unity3. I switched the target system to iPhone, and then, when i tryed to compile, some errors arraised:

    - In file AstarPath.cs (line 1574), the 'Terrain' does not exist in the current context
    - Same in the line 1576

    Hopes it help you

    LLORENS
     
  50. half_voxel

    half_voxel

    Joined:
    Oct 20, 2007
    Posts:
    978
    Hi LLORENS

    No, simplification does only work with the Texture and Grid modes.

    Could be that the Terrain system isn't supported on iPhone, Unity hasn't reported this compiler error before, the Terrain class did still exist, it just didn't work.

    I will look into it.