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

SimplePath - Advanced Pathfinding for any Game Genre - RELEASED

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

  1. bryanleister

    bryanleister

    Joined:
    Apr 28, 2009
    Posts:
    130
    +1

    A couple of additional example scenes would be nice, or a video tutorial. My interest is seeing:

    Example of integration with UnitySteer
    Example of using rigid body forces in concert with pathfinding, I.e. moving off course based on collision or random movement and then getting back on course.
     
  2. HJP

    HJP

    Joined:
    Jul 8, 2009
    Posts:
    152
    +1

    good work, go on ....
     
  3. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    I don't plan on adding a hierarchical representation on top of this in the future. It is certainly doable, but unfortunately it's not a feature that I plan on implementing. Implementing your own nav mesh is also something that you will have to code. The primary purpose of SimplePath is robust pathfinding. I created structures like IPathTerrain to allow people to plugin their own terrain representation, but I don't plan on including code for for every terrain representation. I would love to, but that's just too much work. So long as you implement all the functions defined in IPathTerrain, and inherit from that structure, it should all work fine, because everything in the pathplanning, path smoothing, and steering systems only look at IPathTerrain objects, and those systems dont care if the terrain is a grid or a waypoint graph or nav mesh.

    I know another person on this thread created their own way of removing cells from a grid without using objects containing footprint components. This is a feature I could see myself adding after 1.1, if there is enough interest :]

    Part of the problem with implementing all these features is that pathfinding is a really large problem, and theres a ton of different ways to solve this problem. There are big companies that have implemented largescale middleware solutions (ex: NavPower, Havok, PathEngine), but because I am only one person, and I work on this product part time, I have to define the product to be of a smaller scale than these much larger solutions. My plan is to support the most requested features, while making sure the product remains simple to understand, the code is easily readable and there are no bugs, and the code is extensible to the point where it is a useful tool to anyone that wants any kind of planning in their game. I hope this is helpful, and I really appreciate all the feedback you've given me! It's really great to see how interested people have been.
     
  4. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Hmm there was someone in a previous post who hooked up SimplePath to UnitySteer, you might be able to talk to him. SimplePath does include support for rigidbody forces, this is what the SteeringAgentComponent does, and it does contain a wander behavior, but it doesnt have any examples of randomly wandering off of the path based on steering forces. I can't think of a use case for that in a game, but if you can describe one, I might be able to tell you how to solve the same problem with planning instead of steering forces :] Also, just want to make sure that you found the documentation PDF in the package, as this contains a tutorial for getting up and running.
     
  5. ZJP

    ZJP

    Joined:
    Jan 22, 2010
    Posts:
    2,649
  6. Jacob-Aldridge

    Jacob-Aldridge

    Joined:
    Feb 26, 2009
    Posts:
    120
    Alex- How do you go about rotating the agent so that it faces the path it's taking? I should better clarify, how do I get the next waypoint along the path so I can face the agent accordingly?
     
    Last edited: Jun 2, 2011
  7. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    The path solution contains all of the points. However, I think you might want to use the "SeekPos", which is the position that the agent is seeking towards, along his path. For example, if the path is of total length 1, and the agent is at length 0.5, his seek pos might be at length 0.6. So the seekpos is always a position along the path, that is ahead of the agent, and you can make the agent look toward this position. If you search the code for "seekPos", you will see how this is used inside the SteeringAgentComponent. You could cache this value as a member variable, and then access it from the SteeringAgentComponent to determine the proper facing direction for the agent. I did this exact thing for a previous project I worked on.
     
  8. Jacob-Aldridge

    Jacob-Aldridge

    Joined:
    Feb 26, 2009
    Posts:
    120
    Thanks for the tip, I'll look into that. Also if I have an agent that needs to be destroyed, because it has died or something of similar effect, how do I remove any path requests to it if it's the target of a chase request? The reason I ask this is because when I Destroy(target) I get the following errors (simply because the reference has been destroyed):

    Code (csharp):
    1.  
    2. MissingReferenceException: The object of type 'PathAgentComponent' has been destroyed but you are still trying to access it.
    3. Your script should either check if it is null or you should not destroy the object.
    4. PathAgentComponent.GetPathAgentFootPos () (at Assets/SimplePath/Main/Code/AI/Components/PathAgentComponent.cs:121)
    5. PathManagerComponent.UpdateCompletedRequests (Single deltaTimeInSeconds) (at Assets/SimplePath/Main/Code/AI/Components/PathManagerComponent.cs:298)
    6. PathManagerComponent.Update () (at Assets/SimplePath/Main/Code/AI/Components/PathManagerComponent.cs:112)
    7.  
     
  9. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    The function call you want is RemoveRequest. There are two ways you could do this: polling, or through an event. I'd suggest using an event. For example, when the chasee gets destroyed, it can send out an event that the chaser is listening to. When the chaser receives that event, it can call RemoveRequest, and determine what to do next.
     
  10. rumblemonkey

    rumblemonkey

    Joined:
    Mar 25, 2011
    Posts:
    280
    Hi. You've said, "any game design". What about 3D pathfinding and path following? And how does it handle steering / collision decisions?
     
  11. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    1.1, which will be released soon, will support 3D movement. Really this is just modifying the steering to look at a heightmap, so it's not a terribly difficult addition. The package comes with a very simple steering model that is completely self-contained in the SteeringAgentComponent. There is no code for collision response, because this sort of behavior varies drastically in different games. Adding your own collision response code would require you to just listen for collision events, and modify the agent's velocity as you please :]
     
    Last edited: Jun 2, 2011
  12. psionic81

    psionic81

    Joined:
    Mar 3, 2011
    Posts:
    22
    You can hook it up to UnitySteer relatively easily. Look in this thread for a post of mine for the requisite informations.

    Keep in mind i'm using the UnitySteer (2.0 i believe) that can actually be used on IOS devices, so the syntax might be a bit different if you use an updated version


    Chris.
     
  13. Jacob-Aldridge

    Jacob-Aldridge

    Joined:
    Feb 26, 2009
    Posts:
    120
    Just as a note for any who are looking to add the same and/or Alex to add to the code base. The following addition allows you to clear out a path request for an object you plan on destroying. I've found that if you still have plans requesting for an object that has been destroyed in Unity that it'll throw lots of errors.

    This was added to the PathAgentComponent.cs class.

    Code (csharp):
    1. public void AbortRequest()
    2. {
    3.     m_pathManager.RemoveRequest(m_query);
    4.     m_query = null;
    5. }
     
  14. sabrexx

    sabrexx

    Joined:
    Feb 2, 2011
    Posts:
    25
    Any status on the new version? I'm looking forward to it.
     
  15. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Yea, it got delayed a bit because I moved and I currently don't have Internet access. It should be out within a week. Sorry for the delay!
     
  16. zyndro

    zyndro

    Joined:
    Oct 19, 2010
    Posts:
    78
    i'm also interested on this.. i'm wondering if this new version comes with the posibility to move an object in 3D space, evade obstacles and reach targets? if so i'll defenitely will buy it!
    =P
     
    Last edited: Jun 7, 2011
  17. NomadMellock

    NomadMellock

    Joined:
    Sep 28, 2010
    Posts:
    5
    alexkring thanks for the response a few posts ago.

    I will attempt to create a node based setup shortly inheriting from IPathTerrain as you suggest.

    I appreciate your work load I also have a few very interesting project/tools soon to apear on Unity
    and i know how hard it is to work on these project on your own or with a small group.

    Keep up the good work alexkring, looking forward to the new release.

    I'll let you know how i get on.
     
  18. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    Alex, you've got a great plugin here, but as folks have mentioned, it needs a few more features to make it killer. Here are my suggestions:

    1. Definitely need robust support of various heights, including ramps and cliffs/edges that agents will not pathfind across. Placing thin obstacles walls isn't a good solutions here. Too much work for level designers. I'd like to see it work like this: if the angle of terrain is too step (say >80 degrees), the pathfinder counts that cell as an obstacle automatically.

    Edit: I wanted to include an image of the type of terrain that should be navigable, for posterity.


    2. Agents need to be able to avoid each other. Attaching a footprint component leads to odd behavior. I think the agent tries to avoid itself -- an unacceptable existential position if there ever was one :)

    3. There should be a toggle (on by default) that has agents align their rotation with direction of motion AND this should also align to the surface normal of the terrain (since height support is on its way). For example, if an agent is going up a slope, he should tilt back, etc. I have basic alignment right now by adding the following lines to the SteeringAgentComponent in the update function:

    Code (csharp):
    1.  
    2. Quaternion fromQuat = transform.rotation;
    3. Quaternion toQuat = Quaternion.LookRotation(seekPos - transform.position, Vector3.up);
    4. transform.rotation = Quaternion.Lerp (fromQuat,toQuat, Mathf.Clamp(5.0f * Time.deltaTime, 0.0f, 1.0f));
    5.  
    But I'd like to see something like this as default behavior. It's what most people would expect.

    4. Cranking up the maxVelocity in the SteeringAgentComponent leads to agents banking corners and looking silly. Try cranking it up to 10 or 20 with a 1 unit grid. Doesn't work well. How can we adjust the speed of the traversal while sticking to the path more strictly?

    5. Right now my agents get stuck on obstacle edges all the time. Pretty much broken. Need default support for buffer around every obstacle. I don't want to have to set this manually. Too much hassle.

    I've read this entire thread and it seems that most of these points have already been brought up, but they're core to making this plugin a success, so I want make sure they're getting implemented.

    Now, on to things I need help with:

    a) How do we abort an agent's path midway and have it stop in place (or doing something else)?
    b) How do we change the active patrol point to another one and how do we remove patrol points from the list?
    c) What's the best way to make custom interaction scripts? Right now I just duplicated the Interaction_Patrol script, renamed it, and started modifying all the code by adding various timers and triggers. Is this the recommended way to do it? I want to make sure that my code isn't over-written or nullified when you release updates. Please advise.
     
    Last edited: Jun 9, 2011
  19. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Thanks for the feedback.

    1. Support for various heights is coming in 1.1
    2. I agree this ought to be improved.
    3. I can add this by default, thanks!
    4. You can solve this problem by increasing the acceleration as well, and decreasing the lookahead distance.
    5. You need to tune the distance between the collision and the edge of the footprint. Support for tuning this is coming in 1.1, the work for this is complete.

    a.) Call RemoveRequest to cancel an existing request.
    b.) You can call RemoveRequest on the current request, and then request to move to some other patrol point.
    c.)Yes, you are doing it correctly. However, if you have more complex AI that need several different states, then I'd suggest using some sort of state machine to manage their current state. You can use a state machine, or a behavior tree.
     
  20. Jaimi

    Jaimi

    Joined:
    Jan 10, 2009
    Posts:
    6,203
    While that might be good for cars, it would look terrible for people. Humans don't tilt when they go up slopes, they'd fall over backwards. There are plenty of people out here making non-driving games - don't forget us.
     
  21. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Certainly. The rotation will only be in the XY axis, so this sort of behavior is also desirable for human characters.
     
  22. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Certainly. The rotation will only be in the XY axis, so this sort of behavior is also desirable for human characters.
     
  23. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    I'm actually making a game with human agents, and for some reason thought they'd look more realistic if they tilted back. Your point has made me re-consider. This feature is better suited to vehicles like tanks and cars. The best bet would be to make it a toggle like, "Align to Terrain Normals". Seems like half the people here will want it "on" and half won't.
     
  24. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    How do I grab the current request inside my Interaction component to use with RemoveRequest? Is there a "CurrentRequest" -like variable?

    How do I start new requests? Is it correct to use MoveToPosition and MoveToGameObject? It seems these are the main two ways of setting new destination/patrol points via script, correct?
     
  25. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Yes, you are correct. The PathAgentComponent stores the IPathRequestQuery variable, which represents the current active path request.
     
  26. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    I'm not having much luck. Here's what I'm trying to do: I want to stop an Agent while he's moving between patrol points. In my interaction component I'm calling this:

    Code (csharp):
    1.  
    2. m_pathManager.RemoveRequest(m_pathAgent.PathRequestQuery);
    3. rigidbody.velocity = Vector3.zero;
    4.  
    The code fires, but the Agent just keeps moving along the path as usual, and when he reaches the patrol point, Unity crashes, issuing this error:

    "InvalidOperationException: Attempt to return and inactive node." Log in file: Assets/SimplePath/Main/Code/AI/Pool.cs at line 203.
     
  27. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Ah, you need to call StopSteering on the steering agent first, and then call the RemoveRequest function.
     
  28. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    Very good. That worked! But... (there's always a but)... if I invoke:

    Code (csharp):
    1.  
    2. m_navigationAgent.MoveToPosition(new Vector3(16.0f, 0.0f, 13.0f), m_replanInterval);
    3.  
    to get the agent moving to some random position I get the same error: "InvalidOperationException: Attempt to return and inactive node." Log in file: Assets/SimplePath/Main/Code/AI/Pool.cs at line 203.
     
  29. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368


    Hmm this code seems to have worked for LordAelfric, but I can check into your issue. Maybe you can try what he is doing?
     
  30. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    I'm able to Remove Requests just fine now. The problem is, afterward, moving the agent again using MoveToPosition. I don't think LordAelfric's code addresses that issue. Or does it?
     
  31. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    See what happens if you wait until the next frame to make the request, that might work, thought you should be able to immediately just make the next request.
     
  32. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    I used a timer. I waited for 3 seconds to make new request and it still broke.

    Also, it seems the agent is traversing the patrol node list randomly. Is this intentional? Shouldn't node 0 be the first node the agent moves towards, followed by node 1, 2, 3... etc? If this is intentional, how can I change the order around to go 0, 1, 2, 3...
     
    Last edited: Jun 10, 2011
  33. Tudor_n

    Tudor_n

    Joined:
    Dec 10, 2009
    Posts:
    359
    Count another customer in once 1.1 hits. :D
     
  34. Jacob-Aldridge

    Jacob-Aldridge

    Joined:
    Feb 26, 2009
    Posts:
    120
    Liquid,

    I was having the same issues that you are. If I remember correctly, because the m_query was not being cleared the pathing requests were still trying to access it. It's why after my RemoveRequest I set it to null. Try adding that bit of code and trying it, it works for me.

    -Aelfric
     
  35. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    That worked! Cheers mate!

    Have you been able to figure out the order in which agents navigate nodes? My agent always starts with Node #2 in a 3-node array. Strange.

    Edit: Never mind! I figured out why that was happening. In the interaction code there's a line that simply increments the goalNode with +1, but since the starting node is 0, and a request complete event is triggered on scene start, if the agent isn't already at node 0, he will start navigating to node 0+1, which is node 2. A few simple if statements can easily be set up to force the initial node to stay 0 until it has been successfully navigated to.
     
    Last edited: Jun 10, 2011
  36. Hans

    Hans

    Joined:
    Feb 20, 2007
    Posts:
    422
    AH Thanks for that weee tip, i was wondering y the AI was spinning around on a way point , and not moving to the right way points in the right order
     
  37. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    Actually, I just found a cleaner solution. By default, in the Interaction component's Awake function you'll find:

    Code (csharp):
    1. m_bNavRequestCompleted = true;
    This line means that a RequestComplete event will fire at the start of the scene. That later leads to having to write more code to get the agent to navigate to node 0 instead of node 1. So what I do is set that bool to false. Then I just manually engauge node traversal with a MoveToPosition function.

    I don't really want a RequestComplete event to fire until the agent has actually gotten to a node. And since at the start of the scene the agent isn't at a node, it makes sense to set that flag to false. I don't know if this will break anything else. So far it seems to work pretty well.
     
    Last edited: Jun 10, 2011
  38. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    Seems like the pathfinding isn't as short/straight as can be. See picture. The yellow line is the path SimplePath drew. Is it possible to have it be like the red line I've drawn in by hand?

    http://screencast.com/t/RrcGALPQ

     
    Last edited: Jun 11, 2011
  39. hippocoder

    hippocoder

    Digital Ape

    Joined:
    Apr 11, 2010
    Posts:
    29,723
    Because its still shorter to take the path it just did. Trace it manually: start going directly diagonal and you see it still needs to take an inverse path similar to what it chose.

    I count 10 squares going directly diagonal, then up (left diagonal then up) and it also came to 10 squares for it's own solution.

    Following your line as though it used a bresenham, yields around 13 squares of movement. What you ask for, isn't an A* job.

    To fix this you may want to do a yield based function which raycasts for a clear line of sight so you can just move direct, it wouldn't be that slow, doing x number of raycasts per frame for all objects and yielding out when 2ms has elapsed etc... :)
     
    Last edited: Jun 12, 2011
  40. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    But look, the path I outline below in blue is also only 10 squares and seems more direct. I understand if A* doesn't work like that, but I thought it was going to give the most direct path. Is this a side-effect of the path smoothing algorithm?

     
    Last edited: Jun 12, 2011
  41. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    The grid is 4-connected, meaning it doesn't consider diagonal neighbors. If you were to have an 8 connected grid (diagonals are neighbors), you might get the results you're after. If you want to try this, theres two changes you will need to make. You will have to add the diagonals to the eNeighborDirection enum, and you will have to modify the GetNeighbor function to consider the diagonals.

    If you want to try doing raycasts on the grid, as hippocoder mentioned, you can use the function Raycast2D in the SolidityGrid.cs.
     
  42. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Here's a preview of the new features in version 1.1. I plan on submitting it tomorrow, once I finish updating the documentation.


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

    The price will be $80 for any new customers purchasing SimplePath after the 1.1 release.
     
    Last edited: Jun 13, 2011
  43. psyclone

    psyclone

    Joined:
    Nov 17, 2009
    Posts:
    245
    Looks good... so glad I took the plunge early.
     
  44. RichBosworth

    RichBosworth

    Joined:
    May 26, 2009
    Posts:
    325
    Hi,

    What is the difference between this and UnitySteer? I'm considering purchasing this, but to me there seems to be no difference between SimplePath and UnitySteer apart from the price. I'm obviously not very well versed in these pathfinding/steering tools!
     
  45. leonardoaraujo

    leonardoaraujo

    Joined:
    Jun 3, 2010
    Posts:
    87
    Hi alexkring you know if I can use your SimplePath solution with Android?
     
  46. PrimeDerektive

    PrimeDerektive

    Joined:
    Dec 13, 2009
    Posts:
    3,090
    Simplepath is a pathfinding solution (with some built in obstacle avoidance), steer is just an obstacle avoidance solution.
     
  47. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    I havent tested it with android, but yes it should work with android. I've tested simplepath on iphone, web, and PC builds.
     
  48. I am da bawss

    I am da bawss

    Joined:
    Jun 2, 2011
    Posts:
    2,574
    Very nice! Definitely on my shopping list.

    Question - can you set the radius for the collision boundary? In some video it looks like the AI is half walking through the wall because the path is aligning to the center while polygon is clipping the wall. Maybe parameters such as "offset", "radius" - etc.
     
    Last edited: Jun 13, 2011
  49. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    The agents will clip through the footprint, but not the collision boundary. It's hard to tell the difference because they are both red in the video. This is why I'm adding the ability to increase the scale of the footprint in 1.1, so you can determine the amount of padding between the collision and the agent's path.
     
    Last edited: Jun 13, 2011
  50. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    Very nice. Can't wait to get my hands on it.