SimplePath - Advanced Pathfinding for any Game Genre - RELEASED

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

  1. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    Yes, you'd want to create your own implementation for GetTraversalCost, defined in the IPlanningWorld interface, and implemented in the PathGrid class. Right now it just uses the euclidean distance heuristic, but you can change it to consider the type of terrain. Here is the current implementation in the PathGrid class:

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

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    There is currently no support for this at the moment. If you'd like to add it yourself, you can hook it into the SteeringAgentComponent, and all youd need to do is just add those forces to the one force that is already being applied to the agent (the seek force). I will likely add this as an option in a future release if there is enough interest, this wouldnt take long. You can also consider adding a footprint component to the agent, or using making the agents slide off one another when they collide, as I suggested in a previous post.
     
  3. kenlem

    kenlem

    Member

    Joined:
    Oct 16, 2008
    Messages:
    1,457
    Thanks. I'll explore your suggestions.
     
  4. Kondor0

    Kondor0

    Member

    Joined:
    Feb 20, 2010
    Messages:
    280
    This looks great but i wonder what limitations has the grid: does it works with big levels with complex geometry? (stairs, slopes, etc) That's my first issue in the project i'm working right now, i have a big city level, too big for an automatic navmesh generator so i wonder if this could be the tool i need or it's more focused for small and simple levels.

    Anyway, for those that mentioned Recast, here's a Unity implementation made by Stephen Pratt: http://www.critterai.org/nmgen

    Regards.
     
  5. mgrenier

    mgrenier

    New Member

    Joined:
    Apr 26, 2011
    Messages:
    57
    Thank you. As of now, I'll stick with my own implementation :) I wish you success with your package!
     
  6. BloodWraith86

    BloodWraith86

    New Member

    Joined:
    May 16, 2011
    Messages:
    136
    What advantages does this have over AngryAnt's PATH?

    Curious, bc before I bought this, I just realized AngryAnt's is free, I believe, so I was like "Oh crap! I almost spent $$$ before asking this question!" lol
     
  7. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    I'm not going to say anything bad about his implementation, I'm glad he has created it and released it to the community for free. I posted this a while ago, explaining what I felt were the key distinguishing features of SimplePath. Here ythey are again.

    • The package provides pathfinding, steering, pathsmoothing, and terrain editing. I havent seen all of these features offered in the same package yet.
    • The software is easily extensible. It is structured so that the steering and terrain representation are easily replaceable with your own solutions. If you want to use your own steering system, then you only need to create the hooks in the SteeringAgentComponent. If you want to define your own terrain, you just need to inherit from the IPathTerrain interface, and define nine functions. Additionally, you can define your own A* heuristics, A* success conditions, and navigation targets (ex: the software allows you to choose a position or a gameobject to travel toward, but you can define your own type of target).
    • Dynamic obstacles. Moving objects are considered by the planner, and not just the steering system. If an agent is happily traveling toward his goal, and a giant rock drops down in front of him, the planner will immediately replan around the rock. This behavior is tunable, through a "replan rate" variable, that allows you to specify how often paths are replanned. The package will ship with a scene that demonstrates this behavior. Additionally, the software supports a FootprintComponent. When you add this component to any of the objects in your scene, the collider of that object will be rasterized into the grid, and the AI will be sure to plan around the footprint of that object. If you dynamically modify the collision of the object, the footprint will update accordingly.
    • Performance. I can only speculate, but I suspect that the package will be more performant than many of the other pathfinding packages out there. I have a demo video of 500 agents pathfinding and peroforming dynamic obstacle avoidance at an interactive frame rate. Another important performance factor is memory. Most of the memory in the pathfinding system is pooled, which is important for avoiding spikes from the Mono garbage collector. I still have a bit more work to do on this front, but the largest potential memory bottlenecks are pooled (ex: all path nodes come from a pool). It is common for all commercial pathfinding software to completely run from pooled, and make no runtime allocations (this is the case for the pathfinding in Playstation Move Heroes, DragonAge, Starcraft 2, and Havok AI).
    • Experience. I've shipped 5 commercial games where I worked on the navigation system, and I've contributed to pathfinding in academia, which I feel has allowed me to create a very reliable pathfinding software.
    • Documentation. The package comes with a PDF that explains how to use the software, including a step-by-step tutorial for creating a simple scene. The package contains four sample scenes, and all of the C# files, so you can modify it as you please, and more easily identify bugs as they arise.
     
  8. Jaimi

    Jaimi

    Member

    Joined:
    Jan 10, 2009
    Messages:
    2,302
    Will it work on Unity Terrain, and if so, will it take into account mountains that the player cannot walk up?
    Will it work on a large terrain for example - 1 square mile of terrain?
    Will it work on maps that are mostly empty, but with small concentrations of busy spots? Think: two small villages a half mile apart in the desert.

    Thank you.
     
  9. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    Yes, however there is one thing that you will have to do. At the top of the SteerAlongPath(Vector3[] path) function, you will need to do something like this:

    Code (csharp):
    1.  
    2. for ( int i = 0; i < path.Length; i++ )
    3. {
    4.     path[i].y = Terrain.SampleHeight(path[i]);
    5. }
    6.  
    I plan on adding support for this in the future, but its also quite easy to do yourself :]

    I need more information about the game you are making to better understand how to answer this question.

    Yes.
     
  10. psyclone

    psyclone

    Member

    Joined:
    Nov 17, 2009
    Messages:
    245
    Does this support building a single grid from multiple grids... e.g two squares connected by a rectangle.
     
  11. Jaimi

    Jaimi

    Member

    Joined:
    Jan 10, 2009
    Messages:
    2,302
    It's standard RPG fare. Could in fact be Dragon Age or any other similar game - A large terrain with various spots under water and on top of mountains. Various bands of creatures either patrolling or "standing guard" or spawning at particular events - never more than 30 or 40 at any one time doing anything. Mostly waiting until you get close, then go into "seek mode". May chase you halfway across the map, and if they lose you, will make their way back to their home spots. May be trees, boulders, broken down wagons, large fences with gates, etc they need to plot around. Nothing that you haven't seen before in any other modern RPG.
     
  12. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    You can use any number of grids, but there is no code for connecting the grids.
     
  13. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    Any of the pathfinding packages on the Unity Asset store can help to solve your problem, but whatever solution you choose, you are going to have to do some coding to tailor the game to your needs. All of the pathfinding packages are like toolkits to help you solve your problem faster. You always have the option of trying out the other free pathfinding packages, and then buying mine if those do not work out. I will say that I'm very proud of the software that I have released, and I've been doing this for a long time. There's a fair share of SimplePath users right now, and I still haven't had any bugs reported, and I haven't encountered bug in all of the testing I've done since release. Pathfinding isn't an easy problem, and there really are a lot of ways to solve the same problem; everyone has a different opinion. If you'd like more advice, we can discuss this outside the forums, and I can give you my unbiased opinion. I hope this helps!
     
  14. angel_m

    angel_m

    Member

    Joined:
    Nov 4, 2005
    Messages:
    871
    Please could you include also a javascript version of the files?
     
  15. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    I don't plan on supporting javascript, I apologize. There are programs that can help convert C# to javascript, you could checkout one of those.
     
  16. sabrexx

    sabrexx

    New Member

    Joined:
    Feb 2, 2011
    Messages:
    25
    Hi there,
    This looks very interesting to me, but before spending the money I would like to know how well this performs on ios. Would it be possible for you to run a stress test on an iphone?
     
  17. psionic81

    psionic81

    New Member

    Joined:
    Mar 3, 2011
    Messages:
    22
    I'm just echoing sabreXX's post.. I'm working on a DOTA-style game that's going to be heavily featured on the IOS platform, I have absolutely no issue buying a $60 product, but am needing some sort of confirmation about its memory usage, and how it would perform with ~156 creatures moving about.

    you can send me an email at psionic[numbers: eighty one][at]gmail.com


    Thanks,
    Chris.
     
  18. Dreamora

    Dreamora

    Member

    Joined:
    Apr 5, 2008
    Messages:
    26,589
    I think its important that you clarify what hardware these informations are relevant for psionic, as the difference from 3GS up to iPad2 is in the range beyond 250% performance wise (I doubt anything earlier than 3GS is of interest as the cpu on those is filled already enough rendering the environment, no time left for much AI, even less for 100 path finding searches)
     
  19. psionic81

    psionic81

    New Member

    Joined:
    Mar 3, 2011
    Messages:
    22
    Good point..

    3GS+ effectively, the release time is still around another year, so I'd like to support OpenGLES2.0 devices only.
     
  20. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    The scene with 20 agents is capable of running on iOS without any hitches in framerate, are you looking for something more thorough?
     
  21. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    I'll run some more detailed performance tests today
     
  22. psionic81

    psionic81

    New Member

    Joined:
    Mar 3, 2011
    Messages:
    22
    well since it's a dota style game, the # of pathfinding is pretty constant, my figure was based on:

    6 * 4 waves of "creeps" (minion characters that generally follow a fixed path, but could potentially get sidetracked chasing a player), with 2 sides, with 3 lanes of each of those 6 * 4 * 2 waves, plus 10 characters and maybe 2 "pets" in total.

    I was wondering if the system was able to handle that many with dynamic obstacles, on an IOS platform, and what the memory footprint would be for a scene of that size.



    Thanks,
    Chris.
     
  23. psionic81

    psionic81

    New Member

    Joined:
    Mar 3, 2011
    Messages:
    22
    Also the other pertinent figure is the map size.. pretty huge.. 1700x1700 unity "units" (effectively, meters).

    Can i actually have a map this large with your grid on it and have it functional in the editor?
     
  24. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    Honestly I'm not sure how well it will perform in that situation without running a test more specific to your setup. In the test I ran with 500 agents, the total grid size is 352 x 76 cells, where each cell is 1 meter.

    I also just tested a 500x500 grid, with 3 agents moving from one side of the map to the other. Pathplanning stayed around 0.4ms on my laptop. However, updating the obstacle grid was up near 14ms. If you are going to use maps this large, I think you'll need to size down the dynamic obstacle grid to be only local to where the action is. But this should be fine, I dont think you need things blowing up way off screen :] And theres still one infrequent spike of about 1 to 4 ms as a result of garbage collection in circumstances like this, that i plan on fixing (theres few things that I havent pooled). In terms of memory, this scene takes up 3KB.
     
  25. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    I just ran another test on a map of size 1700x1700. Still the same amount of memory (3KB), and the performance is the same (0.4ms). Keep in mind that you can control the performance through the inspector (both memory and CPU). The system load-balances the performance across many frames. So if the performance is too slow, you can just change a few of these variables, and take a few extra frames for the paths to be solved. For example, if I drop the "Max Number of Cycles Per Frame" variable to 50 instead of 100, then pathfinding takes an average of 0.2ms per frame in this scenario. The tools are there, you just need to play with them to find what works best for you :]
     
  26. psionic81

    psionic81

    New Member

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

    Thanks for the timely responses. I'll give it a go.



    Chris.
     
  27. sabrexx

    sabrexx

    New Member

    Joined:
    Feb 2, 2011
    Messages:
    25
    Thanks for the info :). Would you perhaps be able to provide something like the number of ms per update spent on the processing of steering/pathfinding for those 20 agents on whatever iphone you have, just like you did for your laptop? I'm just curious about this would impact my cpu budget.
     
  28. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    Unfortunately I don't have a license for the iphone, though I will be buying one in the future. Right now I have to run all of my iphone tests on my friend's computer, which takes a bit of time. I'll try to do that for you. But, as I mentioned to psionic, performance is something you can tune. I have a high confidence that it will be fast enough to suit most peoples needs on the iphone. If someone else releases a pathfinding package that is more performant than mine, I will be quite surprised. And if you find that its not fast enough, then I'll fix it, so long as you are not trying to do something impossible ;p
     
  29. sabrexx

    sabrexx

    New Member

    Joined:
    Feb 2, 2011
    Messages:
    25
    Good deal :) I'll probably end up buying it this weekend. Do you have any estimate, even anecdotally, as to how much faster this is than unitysteer?
     
  30. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    I haven't used UnitySteer. But UnitySteer handles just steering, not pathfinding. You can plugin UnitySteer to SimplePath, you'd just need to feed the resultant path to UnitySteer. However, I don't really like steering solutions for dynamic obstacle avoidance to be honest. The reason being that they are unpredictable, and they result in dealing with a lot more edge cases (ex: oscillating forces, ad getting stuck in concavities). I've used OpenSteer for two games before. It's nice for simple behavior, but I don't quite like it for larger scale games. SimplePath handles dynamic obstacle avoidance at the planner level, which means the agent will always know where he needs to go, and won't be subject to getting stuck at local minima. It is for this reason that many commercial games use some sort of grid for dynamic obstacle avoidance (ex: uncharted 2, Prototype).

    One distinct advantage that SimplePath provides over other solutions, is dynamic obstacles avoidance. To give you an example of where a grid is useful, imagine what will happen if you add concave structure to the scene, at runtime. If you are only using steering, your agents will get stuck inside the concavity. If you are using a nav mesh, you will need to retesselate the mesh to consider that new obstacle, and currently there are no unity pathfinding packages out there that handle navmesh retesselation. If you are using a grid, then you can rasterize the collision shape of the object into the grid (this is what the footprint component does), and the agents will avoid the cells that the collision touches. SimplePath handles this rasterization for you. This behavior is demonstrated in the SimplePath demo video.

    Another thing to note is that SimplePath doesnt come setup to avoid agents, it only avoids objects with FootpringComponents. So if you want the agents to not get stuck on one another, you can either add a FootprintComponent to the agents, or make them slide off one another when they collide, or use something like UnitySteer. For most cases I would advise using the collision sliding or the footprintcomponent solution. This question has been asked a lot, so I'm going to add an option for agent avoidance in the next release.
     
    Last edited: May 20, 2011
  31. sabrexx

    sabrexx

    New Member

    Joined:
    Feb 2, 2011
    Messages:
    25
    Ok I'm sold. I'll purchase it tonight.
     
  32. Dreamora

    Dreamora

    Member

    Joined:
    Apr 5, 2008
    Messages:
    26,589
    Makes me really want to buy it and try it on my own "experiment prototype" where the grid will definitely work, consider another license sold :)
     
  33. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    Of the people who have bought this package, how is it working out for you so far? I'd love to get some feedback!
     
  34. psyclone

    psyclone

    Member

    Joined:
    Nov 17, 2009
    Messages:
    245
    Hi Alex,

    Seems to be good... I have three project currently underway which I intend to use it.. One of which will required custom grids, so I will have to write a custom generator (already have most of a hex based one done).


    But yeah, easy to understand. Nice clean code.. Liking the package and easier to get the head around than Path (at least for me).
     
  35. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    Great to hear. If you come up with any bugs, or ideas about features you'd like, please let me know. I already have a few ideas for what I'd like to add, but I want to be sure that the product stays simple.
     
  36. seon

    seon

    Member

    Joined:
    Jan 10, 2007
    Messages:
    1,404
    Just got another purchase here. Keep up the good work!
     
  37. seon

    seon

    Member

    Joined:
    Jan 10, 2007
    Messages:
    1,404
    Ok, first question... I see there is a SolidityGrid.cs file that I assume is called when generating the grid on start as I can see it works out if there cells are inside the bounds etc and store a list of blocked cells (that I assume cant be traversed).

    Can you explain how one would go about adding one's own list of blocked cells into this array as that is we have a non-square area for our grid (lets say a hole missing inside the grid) we could add these cells into the blocked list so your pathfinding wont use them?

    I am not wanting to place footprint components on colliders everywhere to block paths for this as some of my levels are, though all made in essence of a grid, have intricate paths and lots of non-traverable areas.

    So... in a cleaner Q... if I already have a list of cells that I want to be blocked from an XxY grid (starting at the same start location as SimplePath grid) how would I easily get these cell locations into the SolidityGrid array and how does it get used at runtime.

    Example image... Orange area can be traversed, grey or other colours cannot.

    [​IMG]

    Cheers :)
     
    Last edited: May 21, 2011
  38. seon

    seon

    Member

    Joined:
    Jan 10, 2007
    Messages:
    1,404
    Ok, after lots of wrangling, I have managed to add my own array of additional blocked cells that also get included on the check to see if a path can be found... working great.

    I have noticed some optimisation opportunities, but my main concern is making changes to your core code will end up being a noose around my neck when you produce updates. So I am unsure how I should tread at the moment.

    For instance, I have added some code to ObsticleGridComponent that allows the Rasterize() function to only be called once, for situations where no dynamic obstacles are going to be placed and we don't care if 2+ elements try to occupy the same space. This gained me an additional 120fps in the editor (310fps up to 430+fps). - Doing a "GameObject.FindObjectsOfType" every frame is SUPER expensive.

    The problem is this my effect other stuff under the hood, so I would prefer if this type of functionality was built in by you into the core of the logic.

    Another feature that would be REALLY handy is diagonal lookups (not just left, top, right, down), or at least the ability when smoothing the path to still require the path to conform to the centre of each cell, so we don't have to worry about bigger objects clipping corners of colliders and getting stuck.

    All in all, a great product. Very happy with my purchase and how easy it was to (A) get some pathfinding into my existing project and (B) how well written the code is.

    So in summary, the new feature I would like (so far) are:-

    1. The ability to only call the "ObsticleGridComponent - Rasterize()" function once, or only when I want, rather than always every frame.
    2. The ability to conform smooth paths to still use cell centers.
    3. The ability to look up diagonals (so I can turn off smoothing when needed)

    Cheers :)
     
  39. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    Cool, glad to see its working, and thats really neat to see how you are using the software :] I will definitely make note of your optimization, and include it in the next release. Regarding your comment about using the cell centers, if you just use the rough path, that path only goes through the cell centers. There is a "Use Smooth Paths" checkbox in the inspector window, for each Agent prefab. If you set this to false, the agents will use their rough paths. I demonstrate this at the end of the SimplePath demo video. Is this what you are looking for, or do you want something different?

    Any changes I make to the existing code, I will make sure to document, to make the process of upgrading easier.

    For your grid rasterization, I could add an interface that allows you to specify another grid that also gets rasterized, so then the final set of blocked cells would be the union of the blocked cells in the ObstacleGrid and whatever grid you specify (your grid would inherit from the SolidityGrid class, just like the ObstacleGrid does).

    BTW let me know more as your product progresses! I'm really interested to see the games people are making with SimplePath.
     
    Last edited: May 21, 2011
  40. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    If you find your objects getting stuck on colliders, I think the best thing to do is to increase the padding around the colliders. In other words, making the footprint larger than the collider. Right now the footprint just takes the projection of the collider, to determine which cells it should block. I'd like to support users creating their own footprints. If this is something you want, you can jut inherit from FootprintComponent and define your own footprint shapes, and that shouldn't conflict with an future releases of SimplePath. But, it would be nicer if I provided this functionality for you!

    But I want it to be clear that I don't plan on smoothing the path to conform to the cell centers, or some defined distance away from blocked cells. There are a lot of problems related to doing this, and the common industry solution is to just adding padding to the footprint, as I suggested. In other words, each agent is simulated as a point in the navigation space, and the knowledge of his radius is baked into the grid itself, meaning any valid point in the grid should be a minimum of X distance from any piece of collision, where X is the radius of the agent. This also means that you would define different grids for agents of different sizes. For example, for small agents, lets say with radius X, should use a grid with a cell size of X. Larger agents with a radius Y should use a separate grid with cell size Y. SimplePath supports the ability to create multiple grids.
     
  41. psionic81

    psionic81

    New Member

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

    Bought your package today, it looks good, a few concerns:

    (stats):
    Grid of 170x170, cell size 10
    cube of scale 1700x10x1700
    path agent
    2 path nodes:
    (a) at -780, 5, 780
    (b) at 780, 5, -780

    It just won't create a path without a max number of nodes: 28000, and even this takes around 2 minutes to compute with the default max number of cycles etc.

    PathManager employs a "max number of nodes per planner", which is statically created in a pool, of nodes.

    Nodes have:
    3 x float, 3 x int: 48 bytes per object

    48 * 28000 = 1.34 MB per object that I have in the pool.


    Obviously, this isn't going to be functional with my project in mind. I can have the smaller creeps etc path plan with a maximum range of ~20 tiles, but the players (10) will regularly have to path plan across the map (to switch between lanes, or even if they die and need to rejoin their teammates on the frontlines). 10mb is just way too much, even if it didn't take 5 minutes to plan on an IOS class device.

    What do you think would be a good solution to this?



    Chris.
     
  42. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    Hmm what do youran when you say a cube of 1700x10x1700?
     
  43. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    Okay I see what you mean, I'm looking at this right now.
     
  44. seon

    seon

    Member

    Joined:
    Jan 10, 2007
    Messages:
    1,404
    Ok, I have tried the footprint component and have even modified the bounds (bounds.Expand) to expand the calculation area but it doesn't solve my problem and in my specific case introduces more problems as it blocks cells that other AI are trying to calculate through.

    For my specific use, diagonals would be ideal if you cant/wont do the smoothing using centre of grid. See images below...

    [​IMG]

    This is what I have right now. Current smoothing isn't an option for me for the behaviour I am after.

    [​IMG]

    Diagonals is a clear improvement as I get whats looks to be smarter movement paths.

    [​IMG]

    Smooth centres would yield the best looking results for my AI.

    In my specific use case I am not using open space real world navigation, but instead everything conforms to a grid and often a path will only be 1 grid space (cellsize) wide.

    I had already written my own A-Star grid based system that does diags etc... but it was far less flexible for multiple agents etc that your solution, as wasn't as fast for calculation hence me jumping on simplePath.
     
  45. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    First, the memory concerns:

    Nodes have (3 float + 3 int) = 24 bytes per nodes. 24 * 28000 = 0.656MB. And I agree, thats a lot of memory. I can pack the bytes and get it down to 16 bytes per node, which would result in 0.438 MB. Hmm I'll need to think about this more, but I agree there ought to be a way to reduce the memory for such large scenes like the one that you have created. I'm considering adding a hierarchical structure to reduce memory.

    Now, the CPU concerns.

    If you increase the cycles per frame and cycles per planner, it shouldn't take as long as you are describing. I just recreated your scene, and increased both of these to 250, and the path was solved almost instantly, while taking less than 1ms per frame. Though, I am curious as to why you would need to solve such faraway paths so quickly? I highly doubt the player will be able to see all 170x170 cells at the same time, so it shouldn't really matter if the longest paths take long to solve; it won't impact framerate so long as you have reasonable values set for the PathManager.

    I hope this helps, let me know if you have any more questions!
     
  46. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    Hmm it sounds like you want something very specific for the game you are making. In this case, I think you should create your own pathsmoothing algorithm. Take a look at PathSmoother.cs. Look at the function ApplyFunnelPathSmoothing. I am using the funnel algorithm for pathsmoothing, You should create your own function, and call it instead of calling ApplyFunnelPathSmoothing.
     
  47. seon

    seon

    Member

    Joined:
    Jan 10, 2007
    Messages:
    1,404
    Yes you are right (as I have already stated) I have a spacial use case for pathfinding. I think I might just go back to my own A-Star for now and watch how this project progresses over time. I think its going to take as much work to finish my own solution as it will be to modify yours.
     
  48. Dreamora

    Dreamora

    Member

    Joined:
    Apr 5, 2008
    Messages:
    26,589
    HPA* or more like cached sub paths? :)
     
  49. alexkring

    alexkring

    New Member

    Joined:
    May 5, 2011
    Messages:
    366
    My current thoughts are to use some sort of hierarchy, like HPA* does. Here is s a good paper on the topic.
     
  50. Dreamora

    Dreamora

    Member

    Joined:
    Apr 5, 2008
    Messages:
    26,589
    Indeed thats a good one, I think I've read it in the past along a whole host of HPA* related stuff in general after I first struggled over it and its detail concept