1. Help us improve the editor usability and artist workflows. Join our discussion to provide your feedback.
    Dismiss Notice
  2. We're looking for feedback on Unity Starter Kits! Let us know what you’d like.
    Dismiss Notice
  3. We’re giving 2017.1 beta testers a chance to win t-shirts and a Nintendo Switch. Read more on the blog.
    Dismiss Notice
  4. We want to know how you learned Unity! Help us by taking this quick survey and have a chance at a $25 gift card
    Dismiss Notice
  5. Unity 5.6 is now released.
    Dismiss Notice
  6. Check out all the fixes for 5.6 on the patch releases page.
    Dismiss Notice

SimplePath - Advanced Pathfinding for any Game Genre - RELEASED

Discussion in 'Assets and Asset Store' started by alexkring, May 18, 2011.

  1. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    SimplePath 1.11 is now available in the asset store!

    SimplePath in the Unity Asset Store
    SimplePath User's Manual
    SimplePath API

    SimplePath provides advanced pathfinding for any game genre. The software includes code for pathfinding, steering, pathsmoothing, dynamic obstacle avoidance, and terrain editing. The package includes everything you need to navigate your agents around the game world.

    Demo Video


    500 Agents Pathfinding + Dynamic Obstacle Avoidance


    1.1 new features


    And here is a bit about myself. My name is Alex Kring, and I've been working in the games industry for about 4 years, working mostly on AI. I've shipped 4 games under The Sims franchise, and one game for the Sony Move. More recently I've been working on Resistance for the NGP. This past year I gave a talk on pathfinding at the GDC, I presented a pathfinding research paper at the AIIDE at Stanford, and I have several publications on pathfinding with AiGameDev [1] [2].

    I look forward to hearing more about how I can improve this software, to better support this community of game developers. Please, give me your feedback!
     
    Last edited: Jun 21, 2011
    TakuanDaikon likes this.
  2. seon

    seon

    Joined:
    Jan 10, 2007
    Posts:
    1,440
    This looks great! Well done :)
     
  3. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,832
    Thing I'd like is a better description of its capabilities, and while your at it, possibilities :)
     
  4. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    @npsf: can you be more specific about what you are looking for? I appreciate the feedback! And I just realized the video post doesn't show up on iPhone :x
     
  5. Codster

    Codster

    Joined:
    Apr 27, 2010
    Posts:
    440
    First impression; impressed.

    But not quite amazed. Don't get me wrong it is one of the best pathfinders I have seen! But the demonstration was messing (in my not vary important opinion lol) a stress test. I mean your features are great, but what about performance? I mean sure you showed 20 guys running around. But what about RTS games (a large use of path finding) where you have 100 or so guys? Or maybe 200, who knows maybe 1000? Unlikely to have that many, and path finding would be the least of your problems. But people (well me anyway lol) want to see a over the top demonstration where the know it's everything and more then the need.

    Anyway I don't mean to rain on your parade. I just want to hear the motor purr if you know what I mean ;).
     
  6. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    You have a good point! I'll post a stress test video tomorrow :)
     
  7. angel_m

    angel_m

    Joined:
    Nov 4, 2005
    Posts:
    1,008
    Very good work, I can see you are a real expert in pathfinding.
    I would like to use your system but I don´t know if I would be able to integrate it in my project because:

    - My enemy characters (on land) use a character controller component but it seems a rigidbody is necessary.

    - All my enemy gameobjects, land characters and flying ships, already have a moving function in their AI scripts, how can I combine this with the moving function provided by your path system?

    EDIT: - Does your system work with a path with different heights?

    Thanks.
     
    Last edited: May 18, 2011
  8. iio

    iio

    Joined:
    Nov 21, 2009
    Posts:
    22
    How fortuitous! I just started to think about navigation in my game and this pops up :). Question: how extendable is this to 3D paths? I want to use it for space ships.
     
  9. brn

    brn

    Joined:
    Feb 8, 2011
    Posts:
    297
    looks great
     
  10. sybixsus2

    sybixsus2

    Joined:
    Feb 16, 2009
    Posts:
    943
    Does it allow each unit to have a different radius, which restricts where it can travel? (IE: big units need a big space between objects, small units need a smaller space)
     
  11. Cirion

    Cirion

    Joined:
    May 18, 2011
    Posts:
    2
    Hey,

    Just wanted to ask you a question if this will support jumping between 2+ navmesh.

    EG you have a 2d platformer that allow enemies to jump from platform to platform as part of their patrol path.

    Cheers

    Cirion
     
  12. Toad

    Toad

    Joined:
    Aug 14, 2010
    Posts:
    280
    Purchased! :)
     
  13. BloodWraith86

    BloodWraith86

    Joined:
    May 16, 2011
    Posts:
    136
    I have a question, as I'm a bit of a AI newb.

    Im making a 2D game that works only on X Y axis, with Z being layers (irrelevant to movement) and orthographic camera.
    Movement is done in 8 isometric directions using North, east, south, west, northeast, northwest, southeast, southwest directions, but is NOT tile based. Collision is done in tiles, and every character's attacks and collidors are square tiles, but movement is free. However, one can ONLY move in 1 of 8 directions.

    How difficult, if at all, will it be to use this with my 8 directional, free, (NOT-tile-based), movement?
     
  14. kenlem

    kenlem

    Joined:
    Oct 16, 2008
    Posts:
    1,593
    This looks useful and the price is extremely reasonable. I'm buying this when I get home tonight.
     
  15. mgrenier

    mgrenier

    Joined:
    Apr 26, 2011
    Posts:
    57
    Really nice work alexkring !

    As King also mention, I'm very interested in seeing a stress test as I'm building a game with high density of AI (crowd).

    I read the user manual, and I must say it's a bit lacking explanation in "Terrain Representation" since we don't have the code structure in front of us. I'm saying this because I've already built my own system with a navmesh (polygons to reduce the nodes count) and I was wondering how it could be merged/connected with your package.

    When building my own "Terrain Representation", I supose I'll need to code every bits of debug / inspector helper?
     
  16. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    @angel_m:

    If you are using a character controller instead of a rigidbody, you only need to change the code in the SteeringAgentController files. This component only requires a rigidbody because it needs to set a velocity. I just counted and there are 5 lines of code in that file that reference the rigidbody. Change all those refences to a character controller, and everything should work.

    I'd have to see your moving function. Does this function just set velocities, or does it do pathfinding? The PathAgentComponent outputs a list of points, and you can interpret that however you like. The SteeringAgentComponent takes that list of points as input, and moves the character forward along those points. If you are doing your own custom steering, then you can just replace the code in the SteeringAgentComponent with your own code (there is a SteerAlongPath(Vector3[] path) fuction that takes in a list of points, and kicks off the agent steering along those points),

    The system doesn't support this, but it is trivial to add. At the top of the SteerAlongPath(Vector3[] path) function, you'd need to loop over all the points in 'path', and set the Y value to be the height of the terrain at that XZ location. You can get this information from a heightmap.
     
  17. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    @iio:

    Depends on the movement of the space ships. If they don't need to search in 3D, it will work fine. So it depends on how sophisticated you want your movement to be. You could just navigate the spaceships in 2D, and have them play animations that move them up and down. Or maybe there are certain assumptions you can make about your game, that will allow you to vary their height in code. I hope that helps, I'd need more information to give you more specific advice.
     
  18. PrimeDerektive

    PrimeDerektive

    Joined:
    Dec 13, 2009
    Posts:
    3,002
    Could you use multiple grid objects? And could you combine grid objects with standard waypoints (just empty transforms around the level)?
     
  19. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    The system does not support any sort of clearance pathfinding. Typically, this problem is solved by just having different maps for different sized units (ex: one grid for small units and one grid for large units), and you make the size of the cell match the radius of the unit. This is how it was handled in Dawn of War 2, and Company of Heroes. The latest SplinterCell also used different maps for differently sized units (but was on a nav mesh). There are a lot of problems with having the pathfinding respect the agent's radius (ex: how do you know that your destination position is always at least X meters from any piece of collision, where X is the radius of the agent?)

    That being said, SimplePath does support the industry-standard solution to this problem. You can create any number of grids, and any number of PathManagers, and decide which agents are linked to which PathManagers.
     
    Last edited: May 19, 2011
  20. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Yes you can use multiple grids, and you can theoretically mix terrain representations, though I've never tried it. Each PathManager is linked to a PathTerrain, and each agent is linked to a PathManager. You could have a waypoint graph for the flyers, and a grid for the ground enemies. This would require two PathManager objects.
     
  21. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    You can have two different nav meshes, but it does not support switching between the two. I'm not sure I understand the second question. I don't think I'd use a nav mesh for a 2D platformer. I've never made a 2D platformer before, but I imagine I would use a waypoint graph, and just set waypoints at the end of each platform where the agent can travel.
     
  22. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    This system assumes Y is up, since Y is the up vector in Unity, so you'd have to make a few changes if you would want a different up vector. I think the system will be fine for the rest of your concerns.
     
  23. Cirion

    Cirion

    Joined:
    May 18, 2011
    Posts:
    2
    Thanks for your reply. Sorry for the badly worded question I will have another go :)

    Basically regardless of method navmesh / waypoint / xyz I want to be able to achieve the AI creep the ability to jump / climb up a set of platforms like the attached image below.

    $ai example.png

    If simple path can not support what i am after is it possible to add or extend it to achieve what i want.

    Thanks in advance

    Cirion
     
  24. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    The package comes with all the source code; there are no dlls, just c# code. When you buy it, you will have all the code in front of you :] But I will make note of your comment and improve the User's Manual, I agree with you. If you want a bit more information about the code before buying it, take a look at the Doxygen doc which documents every function and data structure in the package.

    When building your own terrain representation, you need to inherit from the IPathTerrain class. If you click that link, you can see the 9 functions that you need to define in order to use your own terrain representation. The pathsmoothing will still work on a nav mesh (I use the funnel algorithm for pathsmoothing), so long as you fill out those 9 functions. I've created a pathfinding system for a nav mesh for Playstation Move Heroes, and I am confident that this interface will work for a nav mesh as well :] Also read the "Create your own Terrain Representation" section of this doc.
     
  25. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    For this type of game, I would use a waypoint graph, and yes SimplePath will support searching across a waypoint graph so long as you define your own terrain representation (there's a section in the doc that explains how to do this). However, I wouldn't use any steering for what you are doing. In otherwords, I think you'd want to define your own Agent prefab, and only give him the PathAgentComponent, but not the NavigationAgentComponent and SteeringAgentComponent like the existing Agent prefabs have. For your case, SimplePath will give you a list of points telling you which path that you need to take, and then you can interpret those points as you desire. For example, looking at your image, SimplePath would give you a list of 4 points, so you can take those points and tell the AI to play a jumping animation between each point.
     
  26. hippocoder

    hippocoder

    Digital Ape Moderator

    Joined:
    Apr 11, 2010
    Posts:
    18,985
    Hi alex, couple of questions:

    1. can I just build my own list of points (gameobjects) in the scene and have it generate a pathfinding solution from just a point cloud?

    2. does it support a max time for pathfinding value and spread the calculation (if need be) across several frames? such a setup is pretty much required for mobile devices. And just give me a list of points back via say a callback or something in an array.
     
  27. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    For those of you interested in the stress test, here you go!


    [video=youtube;8ZNaNdOFXRw]="500 Agents Pathfinding + Dynamic Obstacle Avoidance"]http://www.youtube.com/watch?v=8ZNaNdOFXRw[/URL]
     
    Last edited: May 19, 2011
  28. PrimeDerektive

    PrimeDerektive

    Joined:
    Dec 13, 2009
    Posts:
    3,002
    So you couldn't use multiple grids for a single agent?
     
  29. Codster

    Codster

    Joined:
    Apr 27, 2010
    Posts:
    440
    Nice! But what fps are you getting? And what are the stats of the rig your running it on?
     
  30. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Actually, I think it will support this. You would just need to call RemovePathRequest on the agent who is switching grids, and then set his PathManager member variable to the new grid that he is supposed to use.
     
  31. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    This is running on my laptop. I have a low-end alienware m17x. I don't know what the framerate is, somewhere between 15 and 30.
     
    Last edited: May 19, 2011
  32. Codster

    Codster

    Joined:
    Apr 27, 2010
    Posts:
    440
    Well then 500 is quite (drum roll) amazing ;)
     
  33. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Thanks! I updated the video so you can see what it looks like without debug visuals as well (just look at the previous video post). The bottleneck is rendering and physics. I also ran a test with 1000 agents, and I was getting maybe 5-10 fps.
     
  34. Dreamora

    Dreamora

    Joined:
    Apr 5, 2008
    Posts:
    26,596
    Looks very interesting. Definitely looking forward to see where it goes and if it can become a reasonable alternative to Aron Granbergs A*.

    At the time, at least from the docs and videos, it shows a lot of potential, but with a planar grid representation only its at least for me useless and if I have to implement the representation and editor tools to generate it myself I'm a bit in doubt why again I invested at start. I don't mind paying a fair price for good software but at the time its definitely too limited and not where it was indicated to go on the Pathfinding thread :)
     
  35. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Can you tell me a bit more about the game you are making? DragonAge was made with a grid terrain representation, so it might be the case that you can still use a grid. If you want to define your own terrain structure, there is documentation for how to do this. If you really do need tools for generating a navigation mesh, that is not something I plan on offering. I would suggest Mikko Monnen's Recast, which has become an industry standard for nav mesh generation at this point, and it's free and under the MIT license. You could still use SimplePath for the runtime portion of navigation. I'd love to support something like nav mesh generation, but that's simply beyond the scope of the product, and I know I couldn't do a better job than Mikko :] I apologize if you have been misled!
     
  36. rockysam888

    rockysam888

    Joined:
    Jul 28, 2009
    Posts:
    649
    (bookmarked)
     
  37. hippocoder

    hippocoder

    Digital Ape Moderator

    Joined:
    Apr 11, 2010
    Posts:
    18,985
    Did not get a reply :)
     
  38. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    1. You can build your own list of patrol points (game objects), and the agent will move through to each of those patrol points in order. But, there is no support for building a waypoint graph. Hmm maybe I should just add a waypoint graph, it wouldnt take long.

    2. Yes it supports load-balancing, and yes it gives you a callback for important events. You can see what control you have over performance on pages 14 and 15 here (read the PathManager section). It's actually better to control performance via the number of "A* cycles" than setting millisecond values, since a single A* cycle is the most atomic operation of a planner (I can go into further detail about this if you like, but I don't think you need that level of detail). The system sends a message to the gameobject when navigation request fails or succeeds. When the path request succeeds, a message is also sent along with a Vector3[] containing the path solution.
     
  39. Toad

    Toad

    Joined:
    Aug 14, 2010
    Posts:
    280
    Yes, please. That would be great!
     
  40. psyclone

    psyclone

    Joined:
    Nov 17, 2009
    Posts:
    245
    Yeah, that would be great.

    Im currently integrating into into my rts, which requires hex based circular grids.. so gonna have some fine bulding those, but i have a lot of other plans that this is also gonna find it way into.

    Thanks for a solution....
     
  41. psyclone

    psyclone

    Joined:
    Nov 17, 2009
    Posts:
    245
    Quick question, whats the best way to force the agents to stay on the defined grid?
     
  42. ChrisPaulson

    ChrisPaulson

    Joined:
    Nov 16, 2010
    Posts:
    41
    I'm considering trying to integrate my navmesh generation with simplepath. My navmesh stuff is a dumbed down version of recast. Just need to find the time in the evenings. See: -

    http://forum.unity3d.com/threads/85348-WIP-My-first-unity-project-navmesh-generation

    for more info. I'm hoping it would be easy as all my "merged regions" are quads which would fit nicely with terrain grids.
     
    Last edited: May 19, 2011
  43. sybixsus2

    sybixsus2

    Joined:
    Feb 16, 2009
    Posts:
    943
    Thanks for the answer with regard to unit radiuses. I'm aware of the issues, and that some games don't use them, but I'm also aware of how much more work it is for the artists to create multiple navmeshes, particularly when unit size might change. If you change your mind and implement unit radiuses, I would definitely be interested in buying a copy, but my own pathfinding solution already does everything else yours does, so this was the must-have feature for me.
     
  44. Frido

    Frido

    Joined:
    Mar 27, 2009
    Posts:
    107
    In the video I can see that the agents are colliding with each other, therefor i presume that there is no Agent Avoidance. Is this correct?
     
  45. calveit

    calveit

    Joined:
    Jul 4, 2009
    Posts:
    42
    First of all - great job! The package looks impressive.
    I am thinking of switching to Simple Path because of the steering integration is already there.

    Short question though, is it possible to assign/modify diffrent weights within the grid? Assuming I prefer my agents use the road instead of grass/desert/dirt?
     
  46. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Collision. But note that the agents will never try to move to a position outside the grid. All destination positions are guaranteed to be clamped inside the grid, plus there is some work done to prevent the agent from moving to a position covered by an obstacle. If the agent goes outside the grid, it's because he was pushed there by something else, or because his steering force pushed him there
     
  47. kenlem

    kenlem

    Joined:
    Oct 16, 2008
    Posts:
    1,593
    Can agents steer away from other agents? UnitySteer supports:

    Steer to align yourself with your neighbors,
    Steer to keep a distance from your neighbors, and
    Steer for cohesion with your neighbors.

    Is that possible?
     
  48. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Fantastic! Please let me know more as this progresses!
     
  49. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    That is correct, the agents do not try to avoid one another. The agents avoid anything with a FootprintComponent. For example, the obstacles have this component, and so the obstacles get rasterized into the grid. You can add a FootprintComponent to the agents, to make them avoid one another, or you can add your own steering code inside SteeringAgentComponent. If there is enough interest, I can add an optional force based solution like the one that is used in OpenSteer. Or, you can handle this by just adding some code to make the agents slide off one another and push one another when they collide. To reiterate, there are three classes of solutions:

    1. Planning (via the footprint component)
    2. Steering forces
    3. Collision response.
     
  50. Dreamora

    Dreamora

    Joined:
    Apr 5, 2008
    Posts:
    26,596
    I see :)

    Where it would be used would be a multi storey environment with lifts / stairs connecting them and as far as I see this would cause problems / require custom expansion at the time.


    I know :)
    I've been AI GameDev Premium subscriber since the service started and was a regular visitor of the previous form it existed in and had the chance to toy with it before it hit public space :)

    But I prefer something thats integrated in Unity and thats troublesome if possible at all with Recast due to the fundamental limitations of Unity at the time. Getting to something like that from Recast is beyond the time effort I could justify at least for the time being. I'm too much of a perfectionist and in addition there is Aron Granbergs A* which together kills most of the motivation.

    Perhaps I should have asked an additional question and thats how it compares to Arons library for example, what SimplePath offers that Arons solution doesn't.

    No problem :)
    Perhaps I just missconcluded what you were targeting to reach from the Pathfinding thread, where it sounded as if you agreed that NavMeshs are the standard from which one would assume that your solution offers it.

    EDIT: Just to be sure: I don't consider it bad or anything like that, just not "enough" out of the box for this project, but I will definitely recheck it with a project where less / no extra work would be needed etc for example.
     
    Last edited: May 19, 2011