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

Pathfinding in unity: Beta of Path now online

Discussion in 'Made With Unity' started by AngryAnt, Mar 31, 2008.

  1. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    :!: Updates:
    ---
    February 3rd, 2009:

    As I'm very far in my progress on Path 0.4b I'm no longer debugging 0.3b. I promise that not only will many of the mentioned bugs be addressed in the next release, but also "full" (whatever that means?) editor integration will be included and I'll have good documentation available.

    I'm aiming for a release around unity the 2.5 release as last I heard otee were aiming for a release at GDC09 in march.
    ---

    Path is now in beta. Please try it out and toss some feedback / bug reports / requests at me in this thread or in a pm.

    Documentation is available from the Path project site.

    Made a simple screencast of the system in action with some pretty debug info. Have a look: http://screencast.com/t/rL61tsU4

    :idea: Original thread:
    Hey guys

    I just finished an overhaul of the source of my Path project yesterday and though I might as well toss up a pre-release of the thing.

    It can be downloaded from my webside along with a demo project: http://angryant.com

    Note:
    This is a pre-release which means there is absolutely no documentation apart from the demo project. Also it is obviously not done and so all features have not yet been implemented or fully tested. However it is functional and if nothing else, fun to play with.

    From the website:

    This is a part time project. I plan on keeping it free to use (in accordance with the given license) and updating it as often as I can.

    Edit:
    A picture speaks a thousand words. Here's a screen-shot of the demo project in action with loads of pretty debugging lines and strings.

     
  2. Obscurity

    Obscurity

    Joined:
    Nov 13, 2007
    Posts:
    203
    Wow, very nice. I was just looking into how I could try to implement a path finding system. I look forward to playing around with it.

    Thanks for sharing.
     
  3. bigkahuna

    bigkahuna

    Joined:
    Apr 30, 2006
    Posts:
    5,434
    Looks interesting, how do I use it? Looks like the numbered buttons are waypoints?
     
  4. thylaxene

    thylaxene

    Joined:
    Oct 10, 2005
    Posts:
    716
    the project seems corrupted. I'm getting missing meta data file errors on opening, its asking me to re-import the png images.

    Cheers.
     
  5. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    The script ControlNavMeshTest is the control script of the demo. In the update you can see that the demo responds to right-clicks or shift-clicks. These requests a path be calculated for the seeker (in the demo a sphere) to go from its current location to where it is you've clicked within the NavMesh.

    The seeker in the demo is quite slow, but I'm sure you can figure out a more interesting setup of max speed vs. angular drag etc.

    I've got some demo code for an earlier version of the system where I used a character controller and the robot from the FPS demo. I'll have it updated and uploaded hopefully sometime at the end of the week.
     
  6. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    That sounds rather funky. Haven't heard of anyone else having this problem. It is a 2.0 project - perhaps that is a problem if you are on an earlier version of unity?

    Side-note: The project is developed for indie using indie.
     
  7. thylaxene

    thylaxene

    Joined:
    Oct 10, 2005
    Posts:
    716
    i'm using the latest unity pro 2 release. it shouldn't mater that it is developed in indie.

    Cheers.
     
  8. forestjohnson

    forestjohnson

    Joined:
    Oct 1, 2005
    Posts:
    1,370
    That doesn't matter. Just reimport the assets, its probably some quirk of the move to 2.0.
     
  9. thylaxene

    thylaxene

    Joined:
    Oct 10, 2005
    Posts:
    716
    :oops: yes that works
     
  10. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Just had a look at the code whilst evaluating the eta of the character controller pathfinding demo and realised that for some funky reason I've included an old version of the PathFinder class.

    I'll be updating this whilst working on the character controller pathfinder. Other than this, the interfaces presented shouldn't change much in the immediate future.
     
  11. Quietus2

    Quietus2

    Joined:
    Mar 28, 2008
    Posts:
    2,058
    Really good work there, Ant.

    Curious about the performance though, as it's implemented in script. Have you tested it with a larger number of bots running about?
     
  12. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    No I have not done large scale testing yet. However I have from the design phase thought of performance.

    :arrow: Multi-threading: Pathes are requested by the PathFinder to be calculated by the PathSystem. The PathSystem then creates a separate thread to do the calculations and notifies the PathFinder once a result has been found. This means your code is not held up by path calculations. Furthermore the PathSystem has parameters of max calculation. These are in place to terminate path calculation if it goes on for too long.

    :arrow: Multi-mesh environment: Calculation time increases with the triangle count of the NavMesh. To allow for detailed pathfinding whilst keeping performance high, the Path system supports having multiple inter-connected NavMeshes for navigation. For instance you could have one NavMesh for your landscape and then additional, more detailed meshes, for the interior of buildings.

    :arrow: Path re-use: Currently not fully implemented, the PathSystem stores calculated pathes for a set amount of time (dependant on how frequently it is used). These can then be re-used if a PathFinder requests a path including the same from and to mesh triangle - thus slicing calculation time altogether.

    :!: Since stored and active pathes are removed (and their PAthFinders notified) if a path becomes invalid, path re-use will not result in an invalid path being stored and given to a new PathFinder.
     
  13. Unclet

    Unclet

    Joined:
    Apr 12, 2007
    Posts:
    92
    Thanks for sharing this!
     
  14. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
  15. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Updated the library and demo to a new PathFinder interface.

    I've got an alternative design on the drawing board to make the system easier to access and usable by javascript programmers.
     
  16. bigkahuna

    bigkahuna

    Joined:
    Apr 30, 2006
    Posts:
    5,434
    That would be very nice. Thank you...
     
  17. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Finished implementing the new design.

    :arrow: Just uploaded a much simpler to use interface to the system.
    :arrow: Got a few quirks with path re-use, but it should be up and running next time I have an hour or two dedicated to the project.
    :arrow: This design should also be quite simple to make use of in JavaScript. I'll be uploading a demo using JavaScript in my next session.
    :arrow: Also I've tweaked the parameters on the demo so it should be more tolerable to watch :)
     
  18. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    A javascript demo is still on the list, but I just wanted to upload a demo implementing pathfinding and CharacterController as promised. I'm using the robot from the Unity demo projects to demo this, including how animation could be incorporated.

    :!: The core PathFinder still needs some tweaking as is quite apparent from this demo. Hoping to get this fixed this evening.
     
  19. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    :arrow: Uploaded a bugfix. Not planning on changing the current interface design in any near future. Path is now in a functional state without all features implemented, but none the less functional.

    :!: Moved the project to beta. Please try it out and toss some feedback / bug reports / requests at me in this thread or in a pm.
     
  20. drJones

    drJones

    Joined:
    Oct 19, 2005
    Posts:
    1,351
    haven't had the time to play with it yet but just wanted to say this looks so cool - thanks for sharing : )
     
  21. bigkahuna

    bigkahuna

    Joined:
    Apr 30, 2006
    Posts:
    5,434
    I still haven't really figured out how to use this. I gather that you right click on a toggle-button and the seeker goes to it. The path it follows is the centers of each poly in the mesh, so I take it that is because you eventually want it to follow a terrain mesh?

    At any rate, I managed to get it to crash Unity. I launched the player (in the game window) right clicked the bottom left toggle-button. Then when I right clicked it again -BAM- Unity crashed. :eek: Fastest Unity crash I've ever witnessed, must have done something really serious, and no, I don't plan on doing that again to see if it will happen twice... :wink:
     
  22. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    :oops: Interesting. Is this with the latest release? I'm not at a place where I can try and reproduce the crash, but if this is with the latest release I'll try your instructions right away.

    :arrow: I'll also be working on some preliminary documentation.
     
  23. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    I haven't been able to reproduce the bug you describe. I am however continuously debugging as I go along and I've just now uploaded a new build with

    :arrow: A few bugfixes.
    :arrow: Path re-use now fully implemented.

    Please feel free to submit any bugs, request or other issues in this thread.

    :!: I am currently in the process of writing documentation. A new section has been added to the Path site which I'll be updating as I go along.
     
  24. bigkahuna

    bigkahuna

    Joined:
    Apr 30, 2006
    Posts:
    5,434
    I think I finally understand how to use this: Left click on toggle button(s) to set up a "barrier" then right click somewhere on the surface to set a destination. Simple enough, but until a couple minutes ago I just couldn't seem to figure it out. FWIW, I played with it for a couple minutes and everything seems to work fine.

    A couple questions:

    A. Why did you choose to use a mesh and its polygon centers as your waypoints?

    B. What's the library .dll for? It appears your scripts in the demo work fine without an external library, so why the addtional .dll?

    C. I'm toying with a simpler (ie. less functional) path following script where the user clicks a spot on the screen and that places a waypoint. This wouldn't be adaptable to that sort of thing, would it?
     
  25. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    :arrow: Great. I see I'll need to add an introduction to the demo to the documentation page.

    :!: The advantage of using a navmeshe as opposed to a network generated by designer-placed nodes is that you can gather more information from a mesh and reduce your design time.

    :arrow: A node only gives you a position whereas a mesh triangle gives you an area. This means pathfinding can be more smooth by using the entire area of a triangle for navigation in stead of going straight for one central point.

    :arrow: Also you can decide to tie information to triangles / areas. For instance you might want to change the behaviour of a character as he moves into a certain area of the level.

    :?: That sounds funky. I'm guessing what you're seeing is pre-compiled scripting running because the dll holds all the classes and functionality.

    :!: Yes it would. As I state in the preliminary documentation, the system is designed with an abstract approach to networks and as such I can easily implement support for designed networks along with the current navmesh implementation.
     
  26. Joachim_Ante

    Joachim_Ante

    Unity Technologies

    Joined:
    Mar 16, 2005
    Posts:
    5,203
    Nice work. It's great to see a real navigation mesh library in Unity. The code seems good.

    For the demo I think it would be very useful to make a simple scene with a navigation mesh that has a more complex shape than a plane.
    So that you can hit play and immediately walk the character by left-clicking. I know the system can do a lot more but this is the main point of it, so it makes sense to show that first in a simple way.
     
  27. Unclet

    Unclet

    Joined:
    Apr 12, 2007
    Posts:
    92
    I was utterly baffled as to what to do as well. I have to admit I gave up :oops:
     
  28. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Thanks joe :D Indeed a more expressed demo would probably serve to document the system a lot more than a library reference. I've just sort of wanted to get the whole reference thing over-with :wink:

    :arrow: I'll be upgrading the demo and also start work on a small game project for displaying what can be possible using the system. Probably this will also reveal some more bugs or needed enhancements.

    :!: Again: Anyone wanting to try this out, look through the demo source and feel free to ask any questions and / or request features / report bugs in this thread.
     
  29. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    :?: Did you have trouble understanding the system in general or were the purpose of the demo unclear? Or both?

    :idea: Would a guide to using the demo as well as how it functions be desirable? Or do you have a better idea?
     
  30. podperson

    podperson

    Joined:
    Jun 6, 2006
    Posts:
    1,371
    It crashed Unity for me. I could get the dude to move around if I didn't have any red nodes. As soon as I had one ... bang.
     
  31. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Could you please provide a little more data on what happened before the crash?

    :arrow: Were you using the latest version of the library?
    :arrow: Was a path being calculated at the time?
    :arrow: Was the seeker in the process of following a path?
    :arrow: Was the red polygon in an already calculated path?
    :arrow: Were you using an un-altered version of the demo or did you make some changes?
    :arrow: If so, which?
     
  32. dacloo

    dacloo

    Joined:
    Jun 30, 2005
    Posts:
    469
    Great system. However I noticed crashes as well with the latest Unity. (The character hasn't started walking and it was in a white spot). I'm not sure how I can help you, do you need a bug report?

    Sometimes I right-click a node and nothing happens, but I know the area is free. I quickly see some text lighting up in the left bottom corner which dissapears almost instantly.

    And, when I click in the same area (same polygon), but just a bit further away, the pathfinding system is probably thinking: "don't move, we're in the same area", but I want the character to move to the exact spot in the same area.
     
  33. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    In the last case the spot you clicked is probably within the "Arrive at goal distance".

    I'm in the progress of doing some debugging myself - meanwhile I'm implementing a separate debug system so as to not flood syslogd (for those who are on leopard).

    My next upload will include this debugging system and hopefully will be rid of most of the crash bugs.
     
  34. podperson

    podperson

    Joined:
    Jun 6, 2006
    Posts:
    1,371
    AFAIK yes (I downloaded it just before testing and posting).
    How would I know?
    How would I know?
    I don't think so, but how would I know?
    Yes.
    N/A.
     
  35. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Sorry about that :) In the GUI on the left side of the screen there is a post titled PathWorkers - one worker is created per path being calculated. So if the count was more than zero, one more more pathes were being calculated.

    Was the robot in the middle of going somewhere?

    Sorry I can see that I need to make it clear in the documentation which lines and strings means what in the debug interface. Calculated pathes are drawn in black on top of the navigational mesh grid. All the polygons these lines go through are part of the pathes.

    As stated earlier I'm in the process of implementing a more detailed debugging system. This will prevent crashes and in stead shut down the Path system and generate descriptive error log files.
     
  36. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    New version now available for download:

    As far as I can see I have now prevented unity crashes resulting from use of the Path system. In stead I have implemented a logging and debugging system which will assist heavily in solving bugs which would before cause a crash. I believe I have also resolved the crash bugs mentioned up until this point.
     
  37. Hans

    Hans

    Joined:
    Feb 20, 2007
    Posts:
    422
    Hello AngryAnt

    love the pathfinder, trying to d/l the beta 0.2b but comes up with an error


    Not Found
    The requested URL /angryant/Path/Path.dll was not found on this server.


    thks

    Hans
     
  38. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    :oops: Woops. Fixing the link. In the meantime the link to the demo should work just fine. :wink:
     
  39. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Update:

    The newest demo project now uses a little more interesting navmesh to illustrate how well the canges to the seeker algorithm works.

    Please if you find anything not working as you'd expect don't hesitate to contact me.
     
  40. Joe ByDesign

    Joe ByDesign

    Joined:
    Oct 13, 2005
    Posts:
    841
    This is "freaking" cool! :p
     
  41. Dreamora

    Dreamora

    Joined:
    Apr 5, 2008
    Posts:
    26,601
    Definitely very interesting work :)
    I'm sure I will find use for. So far I avoided thinking about this in a real 3D environment and planned to do it with diablo style mouse movement :)
     
  42. Alec

    Alec

    Joined:
    Mar 11, 2008
    Posts:
    1,330
    outstanding! :eek:

    This is great! :D
     
  43. littlelingo

    littlelingo

    Joined:
    Jul 18, 2006
    Posts:
    372
    Hiya,

    This looks real cool. Is there a way to use this with the Terrain data that is generated when creating terrain in Unity 2.x?

    ( fingers crossed this is possible )

    Thanks,

    -- Clint
     
  44. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Clint:
    I suppose you could. Try exporting the heightmap of the terrain, take it to your 3D app, apply the heightmap to a plane and then simplify the resulting mesh. Then use this mesh as navmesh.
     
  45. angel_m

    angel_m

    Joined:
    Nov 4, 2005
    Posts:
    1,160
    The link-website doesn´t work.
     
  46. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    Sorry my host seems to be down atm. I'll find out whats going on asap.
     
  47. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
  48. Predster

    Predster

    Joined:
    Sep 11, 2007
    Posts:
    145
    I just did a quick test of the demo scene and this seems amazing!! I'm wondering if this could be applied to the following:

    I'm making an FPS style game and it would be great if I could use this to make a path that the would constraint the user's movement (so they could only go forward and backward on the path). It would need to have branch points of course.


    Would this be possible for someone with limited knowledge of scripting?
     
  49. AngryAnt

    AngryAnt

    Keyboard Operator

    Joined:
    Oct 25, 2005
    Posts:
    3,045
    I don't really know - I guess it could be adapted. The system is designed with computer controlled characters in mind - not anything directly related to the player character.

    Would take quite some adaption though so for someone with limited scripting knowledge I'd say its a very big task.
     
  50. Predster

    Predster

    Joined:
    Sep 11, 2007
    Posts:
    145
    I'm going to play around with it--I wonder if it will work!