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. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Hmm I'm curious, what is your strategy? SimplePath does support defining your own heuristic, if that is what you are after. Or, if you are really looking for an 8 connected grid rather than a 4 connected grid (ability to have 8 neighbors instead of 4), here is what you need to modify:

    1. The eNeighborDirection. Just add enum values for the diagonals
    2. The GetNeighbor function. Add support for the neighbor directions you added in step1.
     
  2. seon

    seon

    Joined:
    Jan 10, 2007
    Posts:
    1,441
    Ok, I will give that a try. Just wasn't 100% confident in implementing my own alternate smoothing algorithm, especially when I had a working solution already developed that almost did what I needed.

    Also, I am fairly new to c#, having coded in UnityScript since Unity 1.5, reading other peoples c# and implementing additional code can be daunting task for a c# newbie :)

    I'll let you know how I go!
     
  3. seon

    seon

    Joined:
    Jan 10, 2007
    Posts:
    1,441
    Sorry Alex.. this is the hardest $60 you have ever earned, but I feel its worth it as many others here will benefit from this... well I hope anyway.

    Ok, so I have diagonals working now... it was as easy as you suggested... nice when you know your own code so well :)

    So, my next problem is how to adjust the AStar cost calculator to check direct neighbors of diagonals differently to allow for situations as per my next image.



    I have indicated the direction of the path with the green arrows and my cells of importance are the ones with the red dots.

    In this case, because the red cells are walls/blocked I would like the cost to include that both of the white X cells (direct neighbors) are not unblocked, making the diagonal neighbor still valid, but more expensive so it would go square (right and then down) instead of choosing a diagonal in this case. I want it to still be valid in case its the ONLY option for it (both direct neighbors are blocked) though that should never happen with my level designs.

    I have looked through your cost calcs in your AstarPlanner script but cant see how I can add this in. Any ideas?

    Thanks again for your great support :)
     
  4. psionic81

    psionic81

    Joined:
    Mar 3, 2011
    Posts:
    22
    Hi Alex,

    I'm working on the first integrations with my game, and I'm a bit confused.. I have a path ~11 tiles (cell size 10 as before) long with a pathnode at each end. I have an actor_patrol moving between the points.

    Then I have a dynamic obstacle, which is one of my characters with a footprint_component attached to it.

    Now, it seems that it should be working properly, as there is a red block denoting an obstacle at that point, but the actor_patrol doesn't seem to care about this. When it collides with the red square it does stop, but shouldn't it be pathing around the character?

    What do I need to add to get this to work?

    I've also tried the case where I have a character with a footprint_component just in the way of the patrol points (but not overlapping the patrol points), but the path still seems to be built at game start without taking this into consideration.
     
  5. psionic81

    psionic81

    Joined:
    Mar 3, 2011
    Posts:
    22
    ah i got it.

    by default your prefab for the actor_patrol has "replan interval" at something like 3.1etcetc e-18. This is something like .00000000000001 or whatnot (effectively zero), but it looks at casual glance like it has a valid value. I took a look at your example file and it had an actual replan value, and going back to my scene and setting it worked fine.
     
    Last edited: May 22, 2011
  6. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    No worries :] Take a look at the GetTraversalCost function.

    Code (csharp):
    1.  
    2.         public float GetTraversalCost(int startIndex, int goalIndex)
    3.  
    4.         {
    5.  
    6.             Vector3 startPos = GetPathNodePos(startIndex);
    7.  
    8.             Vector3 goalPos = GetPathNodePos(goalIndex);
    9.  
    10.             float cost = Vector3.Distance(startPos, goalPos);
    11.  
    12.             return cost;
    13.  
    14.         }
    15.  
    This function is used for both the G and H costs. It returns the cost of traveling from one node to another. You'll want to customize this a bit. The first thing to try, is to just weight diagonals more heavily. You can use the GetNeighborDirection function to check to see if you are at a diagonal. Another option is to try out other known heuristics, like the manhattan distance heuristic (I'm going to make this the default heuristic in the next release). Right now this function uses a euclidean distance heuristic. Here is a good page on heuristics.
     
  7. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Yea, that default value is set to float.MaxValue, so that the patrol agents don't replan, by default. Glad you figured it out yourself though!
     
  8. fas

    fas

    Joined:
    Apr 20, 2011
    Posts:
    18
    This looks nice, would definitely spice up my basic chase algorithm. Will it integrate well with a project that is otherwise JavaScript?
     
  9. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    @psionic: I wanted to adress your concern about memory from your previous post. If you us a manhattan distance herustic, the test case you described will only require the Max Number of Nodes Per Planner value to be 1000, as opposed to 28000. Also, this makes the search much faster! But, it will give you slightly different path results. Anyway, in a future release, I plan on including a better heuristic than just a simple euclidean distance. Weighting the heuristic more results in paths being solved much faster, thought results in a very slight loss in path optimality.
     
  10. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Hmm thats a good question, I am not sure how C# and Javascript mix in Unity. Anyone know the answer to this? I'll look around for you.
     
  11. Dreamora

    Dreamora

    Joined:
    Apr 5, 2008
    Posts:
    26,601
    You can just move the whole code into Plugins directory if its not there yet, which makes it "just another assembly that came with the unity engine" and call all public functions etc inside it as if it were written in JS.

    This is due to the compilation order, plugins is always compiled first, so for anything outside its just another .NET Assembly (the plugins folder among a few others are the scripts that are used to build the csharp-firstpass.dll in your builds afterwards)
     
  12. seon

    seon

    Joined:
    Jan 10, 2007
    Posts:
    1,441
    Ok, I have implemented a a brute force checking system inside the GetTraversalCost function that checks if the current goal is a diagonal and if so, check if either the left or right neighbors is blocked and if so upping the cost of that direction. Works a treat though have no real idea of additional overhead caused.

    With this new modification, I am now able to plot the exact paths I am after in my levels with simplePath. Yay.

    So, is there a way of retrieving or accessing the list of waypoints/path locations from the solution? I want to us my own AI driving code, but cant seem to get an array of vector3's etc to drive along. Am sure it must be there somewhere.
     
  13. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    There are two GetSolutionPath functions. One returns the solution as a list of points, and the other returns the solution as a list of path nodes.
     
  14. seon

    seon

    Joined:
    Jan 10, 2007
    Posts:
    1,441
    Awesome thanks :)
     
  15. sabrexx

    sabrexx

    Joined:
    Feb 2, 2011
    Posts:
    25
    Hi there,
    I've been doing some testing on my iphone 3GS with a scene that involves 33 always immobile and always present obstacles and no moving obstacles. I've placed footprint components onto them so that they are rasterized to the grid. When I profiled this on my iphone, it showed that ObstacleGridComponent.Update() was talking 49ms. Any suggestions on what to do here? Is this the right way to create a static obstacle? It appears to be rasterizing to the grid even when there are no changes to it.
     
  16. seon

    seon

    Joined:
    Jan 10, 2007
    Posts:
    1,441
    This is one of the optimisations I asked for previously. Right now Rasterize() collects a bunch of components at runtime every frame which is super expensive. For now I have altered the code to only call it the first time and then I call it manually whenever I know for sure the obstacles have changed in some way.

    Ideally, simeplePath should have a way of marking the obstacle list as dirty so it gets Rasterized only then, and not every update. That way either simplePath or we can set it dirty to cause a re-calc.
     
  17. sabrexx

    sabrexx

    Joined:
    Feb 2, 2011
    Posts:
    25
    I just made that modification myself as well. Seon, I second your request for this feature :)
     
  18. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    I agree. This feature will definitely be added in the upcoming release, which should be out in less than 2 weeks. I have a pretty good idea of what features I'd like to add. Here they are:

    • Optimized grid rasterization
    • Optimized runtime performance, and reduced memory. I am going to weight the heuristic, which will produce slightly suboptimal paths, but will drastically improve performance and reduce memory.
    • Uneven terrain. Currently there is a bit of work you need to support this. The upcoming release will support this automatically, and include examples for uneven terrain.
     
  19. sabrexx

    sabrexx

    Joined:
    Feb 2, 2011
    Posts:
    25
    I would definitely be a fan of trading off optimality for performance. I've been playing around some more on my iphone and when I have PathManager's settings throttled down to a point where it isn't eating up too much of my 33ms/frame budget (my target is 30fps), there can be several seconds of lag time before the paths for all characters are generated when there are many(~20) characters needing paths. I need my enemies to respond and flee quickly from explosions so even very suboptimal paths that generate quickly would be much more preferable to me.
     
  20. m.a.n.t.i.s

    m.a.n.t.i.s

    Joined:
    May 23, 2011
    Posts:
    1
  21. joel

    joel

    Joined:
    Jun 12, 2010
    Posts:
    117
    Havent read the whole tread, but could this work for a 2D game? like a 2D platform game?
     
  22. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    It can, but I think for most platformers you will want to use a waypoint graph instead of a grid. SimplePath supports plugging in your own terrain, so long as you inherit from IPathTerrain. There is a section in the documentation about defining your own terrain representation.
     
  23. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    I think the optimizations will be quite significant; I'll post about the performance gains as soon as everything is complete.
     
  24. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Great! You'll gave to let me know when the game releases :)
     
  25. psionic81

    psionic81

    Joined:
    Mar 3, 2011
    Posts:
    22
    That's an order of magnitude improvement.. nice :)

    I've done a test of my basic scene on IOS platform.. it's not doing anything worthwhile at the moment (~0.25 fps at the moment). I used a 425 grid with cell size of 4.. same setup as before, 2000 max nodes, max cycles: 250.


    I've got another question too:

    With my project, there's the issue to scale of the moving objects.

    If you can picture a stereotypical "voltron" type encounter, with something like the matrix 3's armored personel mechs.. you've got 3 different scales. ~4x typical human size, house size, and small city block size.

    I've noticed (in the unity editor, since the pathfinding isn't at a testable fps on IOS at the scale I need it at the moment), that when I have the large objects moving around on the 4 meter spacing grid, they will somewhat pathfind around a red footprint cell, but they will go onto the nearest edge of the cell. This is an issue because the character is actually wider than the cell size, and so it gets stuck when it collides with the smaller character. I can imagine the same thing happening for buildings as well that were the characters size.

    What would the proper solution that I could do for this?


    Attached is the example scene, you can see that the pathing is at the edge of the red blocked square, but the center of the actor (basic actor_patrol, but scaled 10, 1, 10 with its collider center at 0, 4, 0) hits the actual entity within the red square, and thus halts the patrolling actor as it bumps into it a lot and (Eventually) passes. I'd like it to just path around the obstacle, by having the footprint another cell wide to account for the patrol_actors collision width.
     

    Attached Files:

  26. psyclone

    psyclone

    Joined:
    Nov 17, 2009
    Posts:
    245
    A question for you.. I have come across a case where I need to mark two adjacent square as not being connected. e.g. no path from one to the next e.g. a wall.

    What would be the best way of achieving this in SimplePath, or is this something the uneven terrain expansion your planning will handle?
     
  27. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    You can place one of the obstacle prefabs into the cell you want blocked, and you can stretch that object to block the appropriate amount of space. Alternatively, you can attach a FootprintComponent to any object with a collider. If you want more control, you can inherit from FootprintComponent and define your own footprint shape. Finally, you can look at the ObstacleGrid prefab, see how grid cells are blocked, and modify this file to suit your needs. Does this make sense?

    @psionic: I'll get to your question tonight, as soon as I get home :) but the quick answer is that if you have different sized units, you should create a separate grid for each unit size. If you just want to add footprint padding to an obstacle, you can define your own FootprintComponent through inheritance, you can modify the existing FootprintComponent code, or you can place obstacles that don't have collision enabled, but have a collider, in the cells you want blocked
     
  28. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Did my previous post answer your question?
     
  29. psionic81

    psionic81

    Joined:
    Mar 3, 2011
    Posts:
    22
    Pretty much yes, thanks :)

    Since the IOS stuff is so critical to my project and its prototyping phase, I'd really appreciate a timeline with the updates you mentioned specifically re: optimizations. Right now it's just impossibly slow even with only one 170x170grid (~1fps), one actor_patrol, and 2 node points.
     
  30. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    They will be released before June 2nd. The main optimizations are nearly complete, I just need to test them a bit more. But I can send you the optimization code over email if you like, its not much code.
     
  31. sabrexx

    sabrexx

    Joined:
    Feb 2, 2011
    Posts:
    25
    Do you have any estimates for the amount of speed-up that generating sub-optimal paths will bring? Also, thanks alot for your support on this forum.
     
  32. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    No problem, I'm glad you guys are so appreciative! The pathfinding optimizations will be most noticeable for longer paths. I just ran a test, and a long path that took 10 seconds to solve in SimplePath 1.0, was solved almost instantly in SimplePath 1.1. As I mentioned to psionic before, this same path required 28000 nodes memory in 1.0, and will require only 750 nodes in 1.1.

    Keep in mind that you have control over performance by tuning the PathManager variables in the inspector window. So the performance improvements in 1.1 will allow you to decrease the tuning numbers on the PathManager, which will in turn improve performance.
     
  33. psionic81

    psionic81

    Joined:
    Mar 3, 2011
    Posts:
    22
    Just a note to whomever asked about it before:

    To make this package work w Unitysteer (which i'm using for crowd avoidance etc), you'll need to inherit from SteeringAgentComponent into a similar file (make sure the private variables are marked public to avoid namespace collisions), and instead of setting the rigidbody velocity manually, you'll need to have that set up to go into a "force velocity" or whatnot variable.

    Then you'll make another .cs file that inherits from UnitySteer's Steering class, which is set up like so:

    -------------

    using UnityEngine;
    using System.Collections;

    [RequireComponent(typeof(FASteeringAgentComponent))]
    public class FASteerForSimplePath : Steering
    {
    private FASteeringAgentComponent mSteeringAgent;

    void Awake()
    {
    mSteeringAgent = gameObject.GetComponent<FASteeringAgentComponent>();
    }

    protected override Vector3 CalculateForce()
    {
    return mSteeringAgent.forceVel;
    }
    }


    -----------


    Then your vehicles will like it, and move towards the SimplePath's path.



    Chris.
     
  34. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Nice! I really appreciate this. How's it working with unity steer? If you can post a video, that would be awesome. Also, did you get my email about improving performance?
     
  35. psionic81

    psionic81

    Joined:
    Mar 3, 2011
    Posts:
    22
    I did thanks,

    I definitely need to do more profiling to see what is going on, but I am getting around 4 fps now :)


    I'm using a relatively elaborate setup of UnitySteer, Angry Ant's Behave, and, of course SimplePath.

    What I'm hoping to do is use SimplePath's vectors as the baseline, then additively set up UnitySteer behaviour. Right now I just have the connector I posted to allow UnitySteer to use forces set by SimplePath.
     
  36. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Yep, the steering system was made to allow for augmentations like the one you've created, it's good to see that part is working. I'm curious about the performance, so please do let me know when you find out what is slowing things down. With the optimizations I gave you, you could try lowering the max cycles even further, which should earn you back some more performance. There are a few spikes I need to handle, related to the few things that are being newed rather than being pooled.
     
  37. psionic81

    psionic81

    Joined:
    Mar 3, 2011
    Posts:
    22
    I think it might have something to do with the rasterization of the footprints per frame. I haven't put in the optimization/tweak of not updating every frame as was mentioned earlier in this thread.

    I'll try that next, and what I'll actually do is create a function to add/remove from the footprint list instead of doing a scene wide scan. Additionally it will need a method to mark footprints as being 'dirty', so only certain areas will be rebuilt. I can appreciate the "just works" method as it currently stands for a pc level standpoint, but at the iOS level where things need to be extremely tight, I think it'll work much better.

    Beyond that, a quadtree optimization would probably be the next step, so you could have a pretty fast way to add, remove, and update the various footprints.


    Chris
     
  38. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Yea, the grid rasterization ought to be optimized. In 1.1 I will only rasterize whenever an object moves, or when an object with a footprint component is added. After 1.1, I will likely add some sort of spatial decomposition structure, like a quad tree, as you suggested. Here are a few alternatives to using a quad tree:

    1. lower resolution grid, on top of the existing grid.
    2. reference counting system. For example, when an obstacle gets placed, increment a counter in each of the cells that it touches. When it gets removed, decrement that counter. I think having a max of 4 bits per cell would be practical, since it would allow for 16 objects to be in the same cell. This would require 122KB for a grid of size 500x500 cells. But, if you could make the assumption that only 1 object will ever be in the same cell, this would drop to 30KB.

    I think I'd prefer having a lower resolution grid on top of the existing grid. This would allow for a lower memory footprint, and should provide nearly the same CPU gains as solution #2. Plus, this same structure can be used for hierarchical planning.

    Either way, I hope that you have been satisfied with the product so far!
     
  39. psionic81

    psionic81

    Joined:
    Mar 3, 2011
    Posts:
    22
    Hi Alex,

    I've gotten your SimplePath plugin working with UnitySteer and Behave, to the point where I can replicate my old purely-UnitySteer behaviours.

    I'm running into some issues with footprint components ON the actors themselves. What I'd like to do is have other actors path around them, but putting a footprint component on themselves makes their path finding freak out, since it starts on a blocked position.

    What would be the best way to handle this?
     
  40. Kondor0

    Kondor0

    Joined:
    Feb 20, 2010
    Posts:
    601
    I want to know if this plugin can work with a navmesh or includes a way to generate a terrain representation for a scene with complex geometry (a city for example).
     
  41. Fierce Waffle

    Fierce Waffle

    Joined:
    Dec 23, 2010
    Posts:
    93
    I would also like the answer to this question.
     
  42. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Hmm the actors would have to ignore their own footprint. There's a bunch of places where IsBlocked is called to determine if there is an obstacle blocking a particular location. You would have to return false in the cases when the agent's own footprint is blocking something. So I don't think there's an easy way to do this at the moment.
     
  43. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    SimplePath can work with a navmesh, but you need to create the data structures for the navmesh. You'd create some class called NavMesh, and have it inherit from IPathTerrain, and then the rest of the SimplePath features will work for the navmesh.

    If you are using a grid, the terrain representation is created by adding footprint components to obstacles. But there is no support for automatically generating a navmesh. I'd suggest using Recast for that, it's free and you can use it for commercial projects.
     
  44. psionic81

    psionic81

    Joined:
    Mar 3, 2011
    Posts:
    22
    Regarding Recast, have you any experience with it? How difficult is it to set up?
     
  45. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    We used it for a project I was working on at my previous company, but I wasn't the engineer that integrated it, so I don't have any direct experience. It has kind of become the industry standard for projects that use autogenerated nav meshes. I havent heard of anyone using it with Unity before, but there's no reason it wouldnt work with Unity.
     
  46. mrbdrm

    mrbdrm

    Joined:
    Mar 22, 2009
    Posts:
    510
    does it work with stairs and multiple level height ?
     
  47. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Support for this will be released in 1.1 this week.
     
  48. c-Row

    c-Row

    Joined:
    Nov 10, 2009
    Posts:
    847
    Noooooooo! Don't make it even harder to resist pushing that purchase button!

    ;)
     
  49. PolyMad

    PolyMad

    Joined:
    Mar 19, 2009
    Posts:
    2,350
    Well I was going to post to ask exactly this... nowadays a pathfinding solution without support for more floors looks quite limited ;)
     
  50. NomadMellock

    NomadMellock

    Joined:
    Sep 28, 2010
    Posts:
    5
    Another purchase here

    I've got general movement from node to node on a grid which is great (tutorial)

    My project has a H shaped level and i'm wanting a character to wander around the level
    with the grid having alot of un-wanted cells, I've looked at using the footprint component and creating boxes after boxes to try and stop the characters from walking in dead space.

    I've not got my head into creating the NavMesh or Nodes inheriting from IPathTerrain.

    I've read earlier about disabling certain cells in a grid but this is all a little confusing having just got this package
    I was hoping that the node and navmesh was already built into the package without me having to code it myself.
    I don't mind coding it, but a small video tutorial on these areas would help everyone.

    Video Tutorial
    Implementing your own hierarchy of nodes
    Implementing you own Navmesh
    Removing cells from a grid without objects containing Footprints components
     
    Last edited: Jun 1, 2011