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

Opensource Navigation Framework

Discussion in 'General Discussion' started by DavidB, Nov 13, 2010.

  1. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530
    Edit 2: Please see my signature for a link to the package
    Edit: Updated the video link.

    This thread is likely a bit premature...so I've put this in Gossip for now, but I've been working away at this for some time now in various incarnations.... and I finally almost have it in a state where it's ready to release.

    Certain Logic Studios has been working on what will soon be an Open-Sourced Navigation framework. The package allows users to:

    • Generate and edit navigation grids on arbitrary geometry
    • Save generated navigation grids to a file
    • Load these saved grids to a PathMaster and allow Path Finding Game Agents to pathfind across the generated grids

    We were going to roll our own locomotion engine for this... but I took a second look at UnitySteer 2.0 and to be honest this system is far more robust than anything that we could have come up with in the short term. Arges has outdone himself and darn near perfected the system for Unity users (a huge thanks to him for that of course!... if you haven't seen this project before please do check it out -- http://forum.unity3d.com/threads/64292-UnitySteer-2.0-released)

    I have only just scratched the surface of what UnitySteer can do, but I've managed to pull together an extremely crude demo of the framework in it's current state. Figured I'd post a video to let people see.

    http://www.youtube.com/watch?v=dxuZI3LqpvA

    Check it out, this framework should be available as soon as I can get a few issues ironed out and the code cleaned up a bit. Documentation will follow (the fun part....).

    We'll be offering updates as they arrive through our twitter if you wish to keep an eye on the progress of the package. The link is in my signature.

    Cheers!
     
    Last edited: Feb 20, 2011
  2. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530
    Just wanted to post an update. Things are coming along well..... most of the code is functioning at an acceptable level right now. It's definitely in the alpha stages, but it's almost ready to let you guys/gals have at it.

    I've put together a video going over the workflow of using our framework... integrated with UnitySteer 2.0. This framework does not require UnitySteer 2.0, you are free to roll your own locomotion system if you prefer, but it certainly does make the world a better place when such an awesome system is freely available to use! (Thanks Arges!)

    Anyways check out the video. All comments are welcome.

    Video can be found: http://www.youtube.com/watch?v=dxuZI3LqpvA
     
  3. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530
    Hello again, just wanted to poll the community... what sort of license would you prefer be attached to this framework? Currently I'm thinking the MIT license... it's very open and will allow you all to do what you want. Would you guys/gals suggest anything else?

    Cheers!
     
  4. Mingo

    Mingo

    Joined:
    Nov 14, 2010
    Posts:
    39
    Hi, this is looking very promising! Can't wait to try it out, as we're currently trialling Unity and the lack of a working (stable) navigation system for 3.0 stands out for us at the moment. Every other engine we're trialling supports them internally and will save us months of work, and something like your very impressive implementation may tip us towards Unity again!

    What I'd love to see in a navigation system is support for multiple levels (ie, a spiral staircase) instead of the traditional raycasting/masking system to generate the mesh. Will this project support that for, eg, houses with several floors or will that require setting up multiple meshes/grids like the other third-party navigation systems for Unity? I find that this quickly gets out of hand and starts crashing Unity if you require a complex multi-layered navigation mesh along with terrain navigation. They all seem to work perfectly for a simple "2d" game level, but struggle to handle more complicated levels.

    The best I've seen in a game engine is the one in Shiva, where you can just click an object and choose "add to navmesh", and it will append that objects "walkable" surfaces to the existing (single) navmesh without requiring any manual setup or positioning raycast boxes, etc.

    Anyway, thanks for developing this. I feel that it is something that Unity (as a commercial engine) should support internally instead of relying on the generosity of people such as yourselves and the authors of UnitySteer/Path/A* Pathfinding etc!
     
  5. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530
    Thanks for your comments Mingo! Much appreciated. This thread was quiet as the grave... was freaking me out :p. As for complex level support.... It's already in. Our SimpleGrid system defines a 3d matrix of points.... and thus supports multiple levels. I guess I could have made that video more complex to show that off..... I'll try to roll some video demo of that for the documentation wiki I'm putting up regarding the project. Our framework is still somewhat in its infancy... so while multiple levels are supported, it does take a bit of hand editing to bring it up to "snuff"... but it definitely works!

    As for ease of use... we hope to improve this over time.. and expand the types of navigation graphs/meshes that can be generated as well as what pathfinding heuristics game agents use. A* is great, but not always the best choice.

    Anyways thanks for the comments! :D
     
  6. Mingo

    Mingo

    Joined:
    Nov 14, 2010
    Posts:
    39
    Hey, thanks for the quick reply. I agree it was eerily quiet in here considering the effort you've put into this!

    Great to hear that it'll support more complicated meshes. What would be the workflow for something like a building with two floors? Is it possible to simply tag/layer all walkable surfaces with the same name and have the raycasts "penetrate" through the upper floor (creating a mesh for both upstairs and downstairs in one pass) or would it require creating and saving multiple files and somehow combining them?

    Sorry for so many questions before you've even released this, I'm just excited to see another pathfinding system for Unity!
     
  7. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530
    Questions make me feel warm and tingly inside. So please continue with them :p

    As for the workflow, currently when you create the SimpleGrid casting box.... (watch the video if you have no clue what I'm talking about...you'll see it as the white wireframe box), and cast your grid... it will penetrate all surfaces that are on the correct layer. So if you have a two floored house... you would create the Casting Box to encompass the two floors (so long as they have their own collider..... there will likely be bug issues we have to solve here... but all good things in time :D).

    Basically this system casts a ray from the top of the box downwards... and places a node at every point that it intersects a collider. The nodes are then checked and non-suitable nodes are discarded.... leaving a pretty good estimation of the walkable surfaces. So for a two story house... you would cast from the top floor, down to the bottom floor... and nodes would be placed on both floors and automatically link with nearby nodes.

    The only problem I foresee is any odd issues with custom mesh colliders.... if that is the case though, a user could very simply circumvent this by using primitive colliders in their scene to approximate floors and such. (If the bug does exist... still needs to be tested! I've been working in very simple geometry...although this geometry has had several levels :D).

    Anyways so to answer your question....you simply make the Casting box big enough to cover your area and all floors. There is tentative support for multiple meshes as well... for instance if you want a ground mesh.... and then perhaps an air navigation grid.... you could presumably have both and agents can be registered to pathfind on either or....

    Hope that makes some sense!
    Cheers
     
    Last edited: Nov 14, 2010
  8. Mingo

    Mingo

    Joined:
    Nov 14, 2010
    Posts:
    39
    This sounds great to me - I was confused by Aron Granberg's system as it seemed to stop at the first valid walkable area that the ray hits, so for something like a house with two floors and stairs you'd need to configure a minimum of 3 raycast boxes per house (or similar geometry) and probably an extra tag/layer name for the stairs, combined with complicated masks and ordering of the grids, then try to join the navmeshes together. I'm not sure how Path dealt with this as it doesn't seem to work in Unity 3, but the ability to combine a navmesh (for terrain) with waypoints (for indoor areas) makes it sound interesting.

    I won't dare to ask what happens if you try to use your system with a full terrain just yet, as I'm quite happy to just lay down simple collision geometry for this project instead of casting against the actual world geometry. Looking forward to experimenting with this when you get it finished!
     
  9. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530

    To be honest I haven't tested yet. I know the system gets a bit bogged down if you have too many points spaced too closely together. Optimizations definitely need to be done... but I'm toying with a few ideas to allow optimization without requiring loss of detail. Once the project is cleaned up, these options can and will be explored. It's also a goal of ours to try to get this thing as cross platform compatible as possible.

    More in depth documentation/examples will be prepared as I get the code into a releasable state. It's quite messy right now (mark of genius right?... or maybe it's insanity hard to say).

    Again thanks for the interest! All comments and suggestions are welcome!
     
  10. Arges

    Arges

    Joined:
    Oct 5, 2008
    Posts:
    359
    Hi David,

    Glad to see you're finding UnitySteer useful - it's a great feel to see what people building with your code. Regarding your license question: if you don't plan to impose any restrictions on people, I'm partial to MIT - it's clean, simple and straightforward. If you do plan to impose some restrictions, I'd favor LGPL instead of GPL, as it's less likely to scare people away from using it on their own projects.

    A couple of notes:

    First, I noticed that on your SteerForPointPath you return a normalized vector which you then multiply by the vehicle's maximum force. There's no need to do that, as AutonomousVehicle.ApplySteeringForce already clamps the force vector to that value.

    Second, you're using GetSeekVector to calculate the force. Bear in mind two things:
    • GetSeekVector takes into account the vehicle's radius, which means that it's likely to stop before the object is centered at the specific point you're trying to move to. That's why on this video it seems to skip a few points (particularly near the end).
    • GetSeekVector has an easing in as it's arriving at the point, as you can see here . This is what causes the vehicle to decelerate as it approaches every point in the path.

    You may want to substitute the call to that function with simply

    Code (csharp):
    1. force = Point - Vehicle.Position;
    Cheers,
     
  11. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530
    The great steer man himself. Currently the code is a hack to see if it'd work. I still have to look deeper into your new framework to see how it works . Thanks for the heads up though its going to save me a lot of time. I am strongly leaning towards MIT atm as it is simple and clean. couldn't agree with you more!

    Cheers!
     
  12. Arges

    Arges

    Joined:
    Oct 5, 2008
    Posts:
    359
    That would be Craig Reynolds. :) A lot of the UnitySteer code comes from his OpenSteer - you can still even see some of his comments in there.

    Please keep me posted on how the project goes. Cheers,
     
  13. reset

    reset

    Joined:
    May 22, 2009
    Posts:
    393
    This pathfinding solution sounds so promising!!

    When do you think that it might be available? It is the one thing that I believe Unity really needs!! I understand that Angry Ant is working on a Unity version of Recast - but for Pro only - which is not very good for us Indie developers. :(

    I love Aaron's pathfinding but it is a little complex over multiple levels/complex meshes. Your solutions seems quite simple.

    Never understood why Unity have never pushed for in-built pathfinding solution - esp since Shiva and UDK - as well as other engine - offer this. So essential for great AI and game play!
     
  14. niosop2

    niosop2

    Joined:
    Jul 23, 2009
    Posts:
    1,059
    This looks awesome, really interested in giving it a whirl. This might get more attention in Showcase rather than Gossip, might be why it's so dead in here.

    As far as licensing, I'd love to see it either MIT or or 2 clause BSD.
     
  15. KITT

    KITT

    Joined:
    Jul 17, 2009
    Posts:
    221
    This is great for the community. I am looking forward to this!

    EDIT - 1 vote for MIT License.
     
    Last edited: Nov 18, 2010
  16. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530
    Thanks for the feedback all. I'm heavily leaning towards the MIT... just have to firm it up with the rest of the team now. As for when it's available... soon I hope! Got caught with a bit of that ugly "real life" thing.... The code just needs a good clean up but it's essentially ready to go.

    When I actually officially release it, I'll make a thread in showcase for sure. Just felt it was too soon to do so, but wanted to hear people's opinions :p

    Cheers!
     
  17. phocker

    phocker

    Joined:
    Sep 12, 2010
    Posts:
    57
    Any update on this great looking new stuff?

    Thanks.
     
  18. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530
  19. tatoforever

    tatoforever

    Joined:
    Apr 16, 2009
    Posts:
    4,364
    This is a good example of why unity should provide build-in support to this essential feature, pathfinding.
    Most of the time, community based addons/tools never see the day light. Most of those being, unfinished, unusable or totally broken.
    I'm not blaming you David in anyway, as we are in the same kind of situation, i was working in my spare time on free community tools but, most of them are unfinished due to the massive amount of work we have. But the point is that, must-have essential/important features like pathfinding and steer behaviors should be supported by Unity and not by the community.

    Hopefully we already knows that Unity will provide build-in support to pathfinding.
    Btw, good luck to all of you guys.
    Cheers,
     
  20. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530
    Rome wasn't built in a night, nor is this pathfinding engine. We're still actively working on it and it's undergone a few revisions already. We aren't updating it publicly yet because there was essentially zero interest in it. We'll come out with a more user-friendly version (though if you follow the steps provided, it is quite simple), so that this tool can be chosen as a completely free solution to the already available solutions.

    It would be great if Unity provided a pathfinding solution, but I don't believe they can provide a "one solution fits all" pathfinding subsystem. Often with these things you have to tweak and rebuild parts of it so that it runs specifically for your game/software.

    We will certainly be continuing the development of this platform regardless if Unity brings out an in-house solution or not. This system benefits from being totally open source (and as it matures... fully documented with many examples). We put an early version out hoping that there were others in the community who would like a completely free (MIT) and open sourced pathfinding solution so that there could be some joint development between us and the community, but this didn't really happen. So again, we'll be re-releasing, but there are other projects on our plate at the moment that have a higher priority.

    If anyone is interested in helping develop this system, please don't be afraid to fork it and keep us posted. If you develop interesting features or aspects, we'd love to incorporate them into the platform as a whole.

    Cheers!
     
  21. tatoforever

    tatoforever

    Joined:
    Apr 16, 2009
    Posts:
    4,364
    Maybe unity wont provide a "one solution fits all" but at least will cover the most user demanded/popular pathfinding system and maybe why not steer behaviors? A general purpose game engine like Unity cant simply cover all user needs, but at least a whole range of them and all that with the rapid productive dev in mind.
    Though, you are doing a great work anyway, keep it up.
    Cheers,
     
  22. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530
    I agree, and to be honest, "the more the merrier" applies here. Options always help give rise to refined solutions. We're just trying to do our part :D

    Thanks for the wellwishing!
     
  23. psyclone

    psyclone

    Joined:
    Nov 17, 2009
    Posts:
    245
    Looks good so far... And I think I have a use for it.. Keep up the good work
     
  24. DavidB

    DavidB

    Joined:
    Dec 13, 2009
    Posts:
    530