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

    flim

    Joined:
    Mar 22, 2008
    Posts:
    326
    Purchased, but I forgot to ask a question, what is the license terms for this package? Is it valid for commercial use?
     
  2. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Yes
     
  3. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    1.1 is now live!
     
  4. Jacob-Aldridge

    Jacob-Aldridge

    Joined:
    Feb 26, 2009
    Posts:
    120
    Those should be some nice improvements Alex! Thanks! Be glad to download it tonight and test it out.
     
  5. atholm

    atholm

    Joined:
    Oct 10, 2008
    Posts:
    28
    Hi Alex and thanks for a solid product.
    Given the release notes and video, I can't seem to find any information regarding multiple levels support (stairs, floors) in 1.1?
    Did this feature not make the cut or is it hidden somewhere?

    Thanks
     
  6. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Unfortunately, SimplePath 1.1 will not support stairs.
     
  7. atholm

    atholm

    Joined:
    Oct 10, 2008
    Posts:
    28
    Thanks for the answer.
    Is this a planned feature? if not do you think it is possible to achieve with your current release?, any pointers?

    Thanks
     
  8. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    It is not a planned feature. If you want multiple levels, I'd suggest using a different terrain representation like a waypoint graph or a navmesh. You can plug either of these terrain structures into simplepath, but you would have to define those terrain structures yourself, and have them inherit from IPathTerrain (there is documentation for defining your own terrain structure).
     
  9. atholm

    atholm

    Joined:
    Oct 10, 2008
    Posts:
    28
    Ok thanks. I will look into the documentation and try a navmesh solution.
     
  10. HJP

    HJP

    Joined:
    Jul 8, 2009
    Posts:
    152
    It would be perfect, if there is an example of how to setup a custom mesh.
     
  11. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    How do you intend to use a custom mesh? Do you mean, a custom collision mesh? If that is the case, you will need to somehow extract the height information from your collision mesh. The only function we need for the heighmap, is the "SampleHeight" function, which takes in a 2d point, and returns a height. If you can add a function that does this, that will be all you need. Though, SimplePath is setup to work with Unity Terrain and not custom meshes, so you would have to either inherit from the Unity Terrain object, or just replace all references to this object with your mesh object (theres not many references). I would suggest prebaking a heightmap based on your custom mesh. So at the time you export the level, it also exports a heightmap from your custom mesh, and this heightmap gets used by SimplePath.
     
  12. HJP

    HJP

    Joined:
    Jul 8, 2009
    Posts:
    152
    Alex, I mean a custom navigation structure, like waypoints or navmeshes ...
     
  13. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Ahh I see. There is a section in the documentation that describes how to setup a custom navigation structure, and have it interface with SimplePath. You need to inherit from IPathTerrain, and define all the functions for this interface, and everything should work. Hopefully that helps!
     
  14. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    Can we clarify what is meant by stairs, floors, multiple levels, and height support? What exactly is supported now? How does SimplePath 1.1 handle ramps and cliff-like edges?
     
  15. seon

    seon

    Joined:
    Jan 10, 2007
    Posts:
    1,441
    Just downloaded SimplePath again from AssetStore and readme is still v1.0. Is there another procedure for getting the v1.1 update?
     
  16. psyclone

    psyclone

    Joined:
    Nov 17, 2009
    Posts:
    245
    Yeah he hasnt updated the readme, but the documentation and the code is version 1.1.

    If you have the stress test scene(s) and the uneven terrain scene you have 1.1.

    Cheers
     
  17. seon

    seon

    Joined:
    Jan 10, 2007
    Posts:
    1,441
    Ok, cool. Thanks. Now to re-integrate all of my many changes back into 1.1 :)
     
  18. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    If you are using the grid that comes with SimplePath 1.1, it will not support pathfinding across terrain where there is more than one piece of valid walkable collision for any single grid cell, and those pieces of collision have different height values.

    For example, if there is a bridge, and you need for the agents to be able to walk on top of and below the bridge at the same time, the grid in 1.1 will not support this. A navmesh or waypoint graph is more suitable for this sort of behavior.

    However, there are tricks you can use to get grids to work with multiple heights; but these tricks may be too cumbersome for certain games, like first person shooters. To give an example, let's say you are creating a turn-based RPG like final fantasy tactics, and there are two floors. You can represent this as two grids, where the agents on the top floor belong to the grid corresponding to the top floor, and the agents on the bottom floor belong to the grid on the bottom floor. Then if they need to switch floors, they can navigate to a viable spot where switching floors is allowed, and play an animation to switch between the two floors (SimplePath supports having the agents switch between two distinct grids)

    The "uneven terrain" support for 1.1 allows for both the steering system and the planning system to pay attention to the height of the terrain when navigating. The steering system will smoothly navigate the agent along bumpy surfaces of different heights, and the planning system will prefer planning paths in areas that don't require the agent to climb up a mountain or down into a valley.

    The most recent commercial game that was made with a grid, is DragonAge. So you can use grids to create AAA quality games, but sometimes it will make more sense to use a different terrain representation.
     
  19. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Thanks for finding this! I will update it shortly :]
     
  20. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    I'm really curious to see the games that people are making. Does anyone have a game in progress, or has anyone completed a game, that uses SimplePath? I'd love to see screenshots or videos!
     
  21. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    Can SimplePath 1.1 handle the case shown in the image below? If so, do I need to set up a Custom Mesh terrain? If not, what modifications need to be made to handle it?

     
    Last edited: Jun 15, 2011
  22. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Yes, it can handle these cases. But, are you planning on using a Unity Terrain object to represent the geometry above? Or is that going to be a static mesh, or some sort of object? If the geometry is not going to be part of the unity terrain object, then you will have to somehow determine the height at a particular point. Right now, there is one function that determines the height at any particular XZ position.

    Code (csharp):
    1.  
    2.         public float GetTerrainHeight(Vector3 position)
    3.         {
    4.             if ( m_heightmap == null )
    5.             {
    6.                 return Origin.y;   
    7.             }
    8.             else
    9.             {
    10.                 return m_heightmap.SampleHeight(position); 
    11.             }
    12.         }
    13.  
    In your case, you will probably have to add some code into this function to account for more complex geometry (or you can just inherit from PathGrid and override the GetTerrainHeight function, which is a member of the IPathTerrain interface). If the geometry is static, you can simply export a heightmap at the time you export the level, and calling GetTerrainHeight will just be a lookup into an array. If this geometry is dynamic, then you'll have to do something more expensive, such as performing a very short raycast from the agent's feet, downward a couple of meters (I've seen this in Havok, and in several games). This raycast can be an expensive operation since it will be performed often, so you will want to use it sparingly, or cache the raycasts.
     
  23. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    Ideally I'd like to use my own geometry, because Unity Terrain is more suitable for fluid terrain types, whereas mine is straight-edged and blocky. The geometry will be static, making things easier.

    The question is, CAN I use the Unity Terrain object to represent the above geometry? If so, then that seems like the easiest way. Otherwise, I have to create my own terrain representation along with a terrain data structure, etc as described in the manual? But then I'm not clear how the height map fits into this case. How would I generate the height map? In a 3D application?
     
  24. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    I'm not sure if you can use unity terrain to represent that object. I imagine you have some sort of level export process? If not, you would want to have the option to press some export button, that does processing on the level, and saves out some data to be loaded at runtime. In your case, when you click export, a heightmap should be generated. One way to do this would be to take the min and max XZ points in your level, and iterate over your level doing a bunch of raycasts. The result of each of those raycasts would be stored in a heightmap, which you then lookup at runtime. In otherwords, you are just storing a big array of height values. I'm guessing there might be some support in unity for generating heightmaps automatically from a scene, but Im not sure.

    You don't need to create your own terrain representation, you can still use a grid, you would just have to inject some code into the GetTerrainHeight function to get the terrain height from whatever data structure is storing all of the height values in your scene.
     
    Last edited: Jun 15, 2011
  25. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    Ah, I see. How dense will the array have to be to produce decent pathfinding? How many points per grid unit?
     
  26. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    One point per grid unit would probably be good. You should have a SampleHeight function that returns the height, given an XZ point, and that function can sample several of the nearby points to determine the height. There's a lot of documentation on heightmaps out there, I'm sure you could find an existing heightmap data structure on google that you could use, you mainly need to worry about filling that heightmap with the right data.
     
  27. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    1. Alex, can you post the latest ReadMe.txt here? I'd like to see a list of changes made in v1.1, cause it's hard to tell otherwise.
    2. Do Agents support the FootprintComponent for avoiding each other? When I attach a FootprintComponent, my agent behaves strangely. Am I missing a setting or toggle?
    3. Has code been added to align the Agent's rotation with direction of motion? If so, how is that activated?
     
  28. Jacob-Aldridge

    Jacob-Aldridge

    Joined:
    Feb 26, 2009
    Posts:
    120
    Liquid- What I did to align the agent to the next way point was two parts. First I added the following code to SteeringAgentComponent as a Property:

    Code (csharp):
    1.     public Vector3 SeekPos
    2.     {
    3.         get
    4.         {
    5.             if (m_path == null)
    6.                 return transform.forward;
    7.  
    8.             float currentDistAlongPath = m_path.MapPointToPathDistance(transform.position);
    9.             float futureDist = currentDistAlongPath + m_lookAheadDistance;
    10.             return m_path.MapPathDistanceToPoint(futureDist);
    11.         }
    12.     }
    Then I use the following code in my update for the unit while it's moving:

    Code (csharp):
    1. Vector3 lookPosition = steeringAgentComponent.SeekPos - transform.position;
    2.             if (lookPosition != Vector3.zero)
    3.             {
    4.                 Quaternion fromQuat = transform.rotation;
    5.                 Quaternion toQuat = Quaternion.LookRotation(lookPosition, Vector3.up);
    6.                 transform.rotation = Quaternion.Lerp(fromQuat, toQuat, Mathf.Clamp(5.0f * Time.deltaTime, 0.0f, 1.0f));
    7.             }
    Let me know if that helps!
     
  29. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    @LordAelfric: Yeah, I've used that code before in 1.0, but I though 1.1 was supposed to support this by default.

    Well, I've decided that I need to use a NavMesh to get the results I want. I understand how to inherit from IPathTerrain and such, but I'm not sure how to actually implement the 6 core methods and set up the custom data structure:

    1. GetPathNodeIndex
    2. GetPathNodePos
    3. ComputePortalsForPathSmoothing
    4. IsInBounds
    5. GetValidPathFloorPos
    6. GetTerrainHeight

    I don't have a problem creating the actually geometry. That will be done by hand. What I'm unclear about is how to translate that mesh into a data structure that works with SimplePath. What is this data structure holding? Triangles? Vertices? Edges?

    A tutorial or example file would really help. Has anyone implemented a NavMesh with SimplePath? Do you mind showing code or giving advice?
     
    Last edited: Jun 15, 2011
  30. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    If you look at the comments decorating each of those functions in IPathTerrain.cs, you should get a better idea about how to implement those functions. For example, here are the comments for the ComputerPortalsForPathSmoothing function.

    ComputePortalsForPathSmoothing(
    Vector3[] roughPath,
    out Vector3[] aPortalLeftEndPts,
    out Vector3[] aPortalRightEndPts)

    Code (csharp):
    1.  
    2. /// <summary>
    3. ///Compute the portals along a path. "Portal" is a term used in pathsmoothing, and was first defined by the
    4. ///funnel algorithm. For example, let's assume the terrain is a grid. Then the first portal will be the edge
    5. ///of the grid cell that intersects the vector (roughPath[1] - roughPath[0]). This function can be defined
    6. ///for a nav mesh as well, and any terrain type in general. We only need the portals for pathsmoothing. If you
    7. ///are not using pathsmoothing, then this function can be ignored.
    8. /// </summary>
    9. /// <param name="roughPath">
    10. ///Find all portals that belong to this path
    11. /// </param>
    12. /// <param name="aPortalLeftEndPts">
    13. ///Returns the left end points of all the portals, going from the start of the roughPath to the end of the roughPath
    14. /// </param>
    15. /// <param name="aPortalRightEndPts">
    16. ///Returns the right end points of all the portals, going from the start of the roughPath to the end of the roughPath
    17. /// </param>
    18.  
    Additionally, you can see how the PathGrid implements this function in PathGrid.cs. Do you think this will be sufficient?
     
    Last edited: Jun 15, 2011
  31. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Thanks LordAelfric! Originally I was going to include rotation code with 1.1, but I decided against it, since it would have further delayed the release of 1.1. The code is relatively simple, but if I am to add this feature, I would need to test it the same way I test all of my other features, it would need to be documented, and I'd want the code to be a bit more robust than what you see above. In other words, it would've taken more time than I expected :] I apologize for not implementing this in the end =/
     
  32. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    There's a list of changes when you click the "1.1" link on the SimplePath product in the unity asset store; this shows the release notes. Do you want something more detailed?

    I'd advise against this. I think the best option is to either 1.) add a simple avoidance force, or 2.) add a collision response force. Im considering adding this in a future release, it wouldn't take long at all to implement.
     
  33. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    I suppose the larger question for me is how the NavMesh gets represented at all, on a conceptional level, and how SimplePath works with it. Does SimplePath handle true NavMeshes? Looking at the terrain interface, it seems like even if I have a NavMesh, I will ultimately have to break it down into a set of nodes (centers of triangles?), which gives me a waypoint system, not a NavMesh system. I can generate a highly-triangulated mesh, but a NavMesh is supposed to be low-rez. From my understanding, a true NavMesh allows agents to travel anywhere inside the triangles defined by the mesh, not just their center points. I don't see how that will work give those 6 interfaces.

    Re: Agent Footprints: I was really hoping for a solution that didn't involve forces. Rigidbodies are inherently chaotic. In fact, I'm considering writing my own steering system that doesn't use forces or rigidbodies at all, just simple position Lerp. In this case, how could I ensure agents don't collide with each other?
     
  34. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Yes, you can store the nodes at the centers of the triangles. The "roughpath" will go through the center of each triangle, and the "smoothpath" will be the smoother looking path that doesn't necessarily go through the triangle centers. SimplePath comes with a pathsmoothing algorithm that works on both grids and navmeshes (I've tested this algorithm on both types of terrain), all you need to do is supply the "portals". By definining the ComputePortalsForPathSmoothing function in the IPathTerrain interface, you will be giving SimplePath the information it needs to smooth your path.

    In regards to the footprint question, I agree that steering forces can be chaotic, and it is because of this that I usually use collision response in commerical games I've worked on. In other words, if two agents collide, they should slide off of each other. Once they collide, you can generate some force that pushes one of the agents out of the way.
     
  35. HJP

    HJP

    Joined:
    Jul 8, 2009
    Posts:
    152
    I have the same problem. A navmesh could be a overlapping 3D structure. In the moment I see only a manager instance, that handle that and switch from this solution (terrain) to the next 3D level (terrain).
     
    Last edited: Jun 15, 2011
  36. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    It's fine that navmeshes overlap in 3D, simplepath will support that. SimplePath just doesnt support overlapping grids without adding code.
     
  37. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    So by your definition a NavMesh is simply a set of nodes, 100% equivalent a waypoint graph? And that is fundamentally no different than a grid, other than that it's shape can be 3D?

    Using this article as reference, I understood a NavMesh to be something quite different. The key benefit of a NevMesh is that it can define large regions with few polygons (see image below) and that agents aren't simply navigating using triangle center points, giving their paths more granularity.

     
    Last edited: Jun 15, 2011
  38. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    I think I am sending mixed messages. I'm not saying a nav mesh is a set of nodes, but the pathplanner sees all terrain representations as a graph (a network of nodes).

    On the other hand, pathsmoothing only cares about the "portals", regardless of the terrain structure. In the above image, the 3 portals are the 3 lines that you see intersecting the yellow line between A and B.

    I wrote the navmesh system for my previous company (Nihilistic Software Inc), and each polygon was represented by a single node placed at the center of the polygon. I also presented at this past year's GDC about navmeshes, so I'm quite familiar with the concept, I think I am just being confusing with my explanations :x Is there anything that doesnt seem to make sense that I can better explain?
     
  39. HJP

    HJP

    Joined:
    Jul 8, 2009
    Posts:
    152
    I see that, but which is your recommendation…
     
  40. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    It depends a lot upon the game you are making. If the game has a very dynamic terrain, I'd usually suggest a grid. If your game has multiple floors and the agents need to spend a fair amount of time navigating on stairs, (like an FPS), then I'd suggest a navmesh.

    The downside of using a navmesh, is that it's not very good at representing dynamic terrain. There are two common solutions for representing dynamic terrain with a navmesh: 1.) retesselate (havok and ubisoft do this), or 2.) rasterize a grid on top of the navmesh (deus ex, prototype, and uncharted did this). Both of these solutions take a long time to implement, and are a bit hairy.
     
    Last edited: Jun 15, 2011
  41. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    So if I hooked up the NavMesh from the image above to SimplePath, the agent would navigate straight from A to B? Or, the agent would navigate like the red path in the image below? And if there was a second agent starting at point C, trying to get to B, would he take the exact same path as the first agent? To me, this is the critical distinction between a NavMesh and a Waypoint graph. What I have drawn below is a NavMesh masquerading as a Waypoint graph (I can easily replace all the polygons with nodes corresponding to the polygon's center points). Can you clarify which one of these SimplePath supports? I'd rather not spend dozens of hours tinkering around just to find out that SimplePath doesn't handle the true NavMesh case.



    Edit: Browsing through various game development forums, I found the following explanation, which might be what you were talking about earlier:

    Is that how you're doing it?
     
    Last edited: Jun 16, 2011
  42. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    If you are going from A to B, the agent will follow a straight line from A to B. If you are going from C to B, the agent will follow a straight line from C to B.

    The red path the you have drawn from A to B, is the "roughpath". In SimplePath, the planner will first solve this rough path, and then it will go through a "pathsmoothing" process, to create a "smoothpath", which will be a line from A to B. The result is the agent traveling in a straight line from A to B. SimplePath uses the funnel algorithm for pathsmoothing. You can get more information on this algorithm here:

    http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html

    Also SimplePath supports the ability to use the smooth path, or the rough path. If you actually wanted to follow that red line illustrated, there is a checkbox you can tick that will make the agent follow that path instead of the smoothpath.
     
  43. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    Thanks, that's what I needed to know.

    I don't suppose you, being the expert, can create a component that would take a Mesh object and create a terrain out of it like PathGrid.cs? Seems like this is the vital feature SimplePath is lacking. I'd love to be able to just drag a mesh object onto a field in a component and have it work.

    If not, I'll start hacking away at the code myself. But it ain't gonna be pretty.
     
  44. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    I agree, that would be a nice feature :] Unfortunately, it would be very time consuming to create a software that comes with all the different types of terrain representation, along with tools for editing each of them. I'd love to do this, but I don't have the time to.I knew I wouldn't be able to create all types of terrain from the beginning, so I wrote the code to make it extensible enough to support other terrain types, for users like yourself who want to use SimplePath for fast pathfinding, and its structure.
     
  45. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    There are really only two types: Unity Terrain and Mesh. That would cover 95% of all use-cases. I think being able to easily hook up a Mesh is core to the commercial usability of this plugin. As for tools to edit the meshes, yes, I agree, that can be considered outside the scope of the plugin, hence I don't ask for it.
     
  46. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    True. You would just need to tesselate the mesh, and transform it into the appropriate data. Hmm maybe I will do that..
     
  47. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    That's the beauty of it, Unity automatically tesselates meshes. A mesh is simply an array of Vector3 triples in a particular order. It's basically a triangular grid. Seems like hooking that up should be pretty easy for you, knowing the guts of the system as you do.

    If only my coding skills were as advanced as my powers of persuasion :)
     
  48. alexkring

    alexkring

    Joined:
    May 5, 2011
    Posts:
    368
    Interesting, that would be very easy. I'll look into it. Do you know if Unity allows you to modify that mesh, within Unity? Then I wouldn't have to worry about making tools to modify that mesh :]
     
  49. seon

    seon

    Joined:
    Jan 10, 2007
    Posts:
    1,441
    Unity has a full Mesh class, and you can do anything you want to the mesh :) Can be runtime or via Editor scripts.
     
  50. liquidgraph

    liquidgraph

    Joined:
    Feb 26, 2009
    Posts:
    324
    You can certainly create meshes within Unity and modify them at run-time and the like. I've done that before and it's pretty easy. But that's done through code. So if you want the mesh's vertices to literally be editable in the editor with transform tools, that would require some work.

    It would be possible to create a very basic import process that would create an empty game object with a bunch of child objects representing each vertex in the mesh. Then those objects could be dragged around with transform tools and when the game started, you'd loop through those objects and re-create the mesh/graph. The only issue I see with this method is rendering it inside the editor in a sane way (i.e., so a level designer could actually use it). I'm not a big fan of Unity's Gizmo rendering because it makes judging distances impossible. They really need to fix that.

    Also, I'm not sure how you'd add or subtract vertices to the mesh. You'd need to create a 3ds modeling interface for that.
     
    Last edited: Jun 16, 2011