Search Unity

Pathfinding Engine

Discussion in 'Assets and Asset Store' started by limdorn, Apr 8, 2014.

  1. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    $logo2.jpg

    Hi everybody,
    I want to present a new Unity3D tool : Pathfinding Engine.

    Pathfinding Engine is an easy to use and fast A* path-finding solution. It auto-generates navigational grids and support dynamic obstacles.
    The package comes with example scripts, ready to be adapted to any game implementation.

    ASSET STORE

    Here you can try different live demos:

    Simple example.
    Dynamic Obstacle example.
    Patrol example
    Stress example
    Terrain example
    Local avoidance ( version 1.2 )


    $01.jpg $terrain.jpg
    $dynamic.jpg
    $stress.jpg

    This asset will be soon to store.
    I wait your comments.
     
    Last edited: May 2, 2014
  2. sootie8

    sootie8

    Joined:
    Mar 25, 2014
    Posts:
    233
    It good but I don't like the way it keeps twitching between up and left/right one at a time when traveling diagonally. I'd prefer a Lerp if there is a clear path to the destination.
     
  3. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    Hi sootie8.
    First, thanks for your interest.

    My idea is to create an economic pathfinding system with a correct initial version.
    When this asset will be available in asset store I will update with other features in future:
    -support to 2d ( ready in 2 weeks )
    -dynamic avoidance between agents ( ready in 4 weeks)
    -generate a better smooth path (ready in 2 weeks )

    Other ideas can be added if community take into consideration.
     
    Last edited: Apr 17, 2014
  4. The smooth gamemaker

    The smooth gamemaker

    Joined:
    Mar 10, 2014
    Posts:
    53
    is this a game or something which we can use in our games?
    looks like a game except for that robot never comes back.
     
  5. TowerOfBricks

    TowerOfBricks

    Joined:
    Oct 20, 2007
    Posts:
    963
    Hi

    I would suggest that you change the layout of your example scenes. Currently they are pretty much identical to the ones I include in my A* Pathfinding Project, you even seem to be using the exact same materials that I created.
    I haven't checked if you are also using code from my project, I hope not.

    Comparison (this is from the A* Pathfinding Project):
    $Screen Shot 2014-04-11 at 15.36.15.png
     
  6. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    The Pathfinding Engine is not a game.
    It's a tool to help with pathfinding units in your game.
    You can use in RTS, TD...
     
  7. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56

    Hi Aron.
    First : sorry if any example is similar but if itt's a problem I will change it soon as posible.
    Second: all code i write myself and my asset haven't same level than yours.
    My asset is more simple.
    If you have any question more send me a email and i will respond you all without problems.
     
  8. TowerOfBricks

    TowerOfBricks

    Joined:
    Oct 20, 2007
    Posts:
    963
    Ok.
    Yes it would be good if you would change it to avoid confusion for users.
     
  9. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    It´s changed. :)
     
  10. hippocoder

    hippocoder

    Digital Ape Moderator

    Joined:
    Apr 11, 2010
    Posts:
    25,935
    What makes this stand out from one of the many existing A* pathfinding solutions available?
     
  11. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    The purpose of Pathfinding Engine is to provide game developers with a robust ,well documented and easy-to-use toolkit for pathfinding with a CHEAP PRICE.
    My idea is to create a correct and low-cost solution : 10 or 15$.
     
    Last edited: Apr 17, 2014
  12. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
  13. Mauri

    Mauri

    Joined:
    Dec 9, 2010
    Posts:
    1,597
    I saw two issues:
    - Clicking multiple times on a point causes the robots to go back and forth where they currently stay. After the last one, they'll go to the planned point.
    - If they starting to go to the specific point, the framerate drops for a split second but goes then back to normal again.
     
  14. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    Hi Mauri.
    I´m working about your first issue and I will find a solution in several days: I need to implement a function to check the generated path with the actual position agent because exists a time between the moment you click a destination and the moment the path to go to destination is generated.
    About the frame rate , in Pathfinding Engine code , you can find a variable , that if you change, will be solved.
     
    Last edited: Apr 17, 2014
  15. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    First of all I want to thank you for the contributions of Sootie8 and Mauri.
    Thanks to them I have focused my attention on solving various problems.
    I have improved the smoothness of the path, I have improved the generation of routes that have not backwards (although needs a bit more work) and optimized the framerate in some examples.
    Now the main post examples are updated. Thanks a lot.:D
     
    Last edited: Apr 17, 2014
  16. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    I've finally been able to solve the step back that appeared if a destination quickly and repeatedly was defined.
    The examples have been updated.

    I hope new comments.:)
     
  17. zenGarden

    zenGarden

    Joined:
    Mar 30, 2013
    Posts:
    4,538
    Compared to A* pathfinding , stress test seems not so powerfull.
    How easy to generate navmesh ? some parameters ? will it be editable ?
    How to tweak navmesh navigtaion calculation , like one call only for some project or several for dynamic advoidance ?
     
  18. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    The navigation agent works with a single instruction: agent.GoTo (point)
    Right now I'm working on the user manual and hope to get soon: maybe tonight or tomorrow.

    The collision avoidance will be something to add in the future after the Pathfinding Engine be published in the asset store.

    On the stress test will try to create a harder test.
     
    Last edited: Apr 18, 2014
  19. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    Hi zenGarden,
    I upload several examples where agents are patrolling with dynamic obstacles.

    300 agents
    600 agents

    And a quick start manual.

    If anyone has any suggestions let me know, please.
     
    Last edited: May 2, 2014
  20. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    Hi,
    I uploaded tonight Pathfinding Engine v1.1b. Right now I'm waiting for confirmation. I hope there are no problems.

    While I'm working on a multilayer system. Here you have a new demo.
    IMPORTANT: The demo is still at an early stage.

    Multilayerd Demo
     
    Last edited: Apr 20, 2014
  21. Drowning-Monkeys

    Drowning-Monkeys

    Joined:
    Mar 6, 2013
    Posts:
    302
    Hey there,

    Will this engine pass the Windows 8 Authentication? (WACK)
     
  22. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    I think so.
    The code should work on other platforms but I've only had a chance to use it on Android.
    I'm working on some improvements for version 1.2 and I just created a demo for Android: 50 units patrolling on a map with dynamic objects. I quite like the result but I hope to optimize it more.

    DEMO Android by PEv1.2.beta.
     
    Last edited: Apr 29, 2014
  23. Drowning-Monkeys

    Drowning-Monkeys

    Joined:
    Mar 6, 2013
    Posts:
    302
    Are you using Hashtables? or Dictionaries? To get it to pass WACK you can't use Hashtables for any Win8 products.
     
  24. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    Hi ,
    I updated Pathfinding Engine to 1.2.
    I create a local avoidance system , new smoothing path and new inspector editor extension.

    Stress example
    Local avoidance

    I just optimized a demo for Android: 50 units patrolling on a map with dynamic objects with local avoidance. ;)
    Android Stress example
     
  25. ZJP

    ZJP

    Joined:
    Jan 22, 2010
    Posts:
    2,646
    It's funny, you forgot the link to the Asset Store...
     
    Last edited: May 2, 2014
  26. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    Thanks. :D
    I insert it to main post.
     
    Last edited: May 2, 2014
  27. ZJP

    ZJP

    Joined:
    Jan 22, 2010
    Posts:
    2,646
    You're welcome. As a customer i take care of my...'good' providers.
     
  28. castor76

    castor76

    Joined:
    Dec 5, 2011
    Posts:
    1,497
    Hi, I am interested with this, but can it work with unity 2D stuff.? 2D colliders and XY plane axis.

    Also I would suggest to use very simple object for your stress example as I couldn't tell if it is the drawing number of models are causing very low fps or your path finding system.

    My i7 930 is running it at 8fps...
     
  29. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    Hi Castor. Thanks to your suggestions : it help to become better my work. Really I apreciate it.
    The 2D stuff will ready in some days.
     
  30. Zelek

    Zelek

    Joined:
    Jun 12, 2010
    Posts:
    87
    I just purchased and tried out your pathfinding engine, and was really impressed with how simple it was to use and how quick it was to set up. I'm also interested in using it for a 2D project. Any update on how that's coming along?
     
  31. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    Hi Zelek, thanks for your reply.
    Right now I'm moving into a new house and I'm busy, but I am preparing for the version Pathfinding Engine 2.0.
    This new version will have support to 2D stuff and it will be more fast and robust.
    I want to tell you that I´m rewriting a lot of code ( I´m changing raycast system to a bound/mathematic system) but all functions that v1.2 have to work will be the same.

    Here It´s a new stress demo with Pathfinding Engine v2.0 beta.

    I wait your comments.
     
  32. Zelek

    Zelek

    Joined:
    Jun 12, 2010
    Posts:
    87
    I notice that the framerate is much improved over the Stress Test demo that's linked in the asset store, though the agents don't seem to come that close to each other and the obstacles aren't yet moving. I actually only need a dozen or so agents in my particular case, so I was already happy with the performance in the current version. Being able to have Local Avoidance in 2D is the main feature I'm looking for. Hopefully it's ready soon!
     
  33. Moonblade-Studios

    Moonblade-Studios

    Joined:
    Oct 14, 2013
    Posts:
    34
    really nice system. I hope you will improve it after the 2.0 will game out (which from the webplayer demo looks really improved in terms of speed). Good luck
     
  34. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
  35. Zelek

    Zelek

    Joined:
    Jun 12, 2010
    Posts:
    87
    Looks really good, can't wait to try it out in 2D. I'm curious how the local avoidance behaves when multiple objects are following a moving target (like enemies chasing a player).
     
  36. ScriptGeek

    ScriptGeek

    Joined:
    Mar 4, 2011
    Posts:
    45
    First off, I'd like to say this project is awesome, this is the solution that I've been looking for. :)

    If I bought the current 1.2 version does that mean I automatically can update to 2.0 when it becomes available?

    Also, I checked out your demo: https://dl.dropboxusercontent.com/u/54848710/PE20BETA/avoidance2.0beta.html It appears to work great for a while, but then something happens... They stop moving and get stuck together, but they still animate. Here is a screen shot of what I see: $pathfinding_bug.png
     
  37. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    Hi ScriptGeek.
    If you bought PathfindingEngine , it will update to 2.0. in moment it will be ready.
    I named PathfindingEngine v2.0 because I´m changing a lot of code/systems.
    Thanks for the screen shot. This will help me to publish a better version.
     
  38. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
  39. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    Hi Zelek.
    I´m working a lot to create the 2D stuff. Sorry to wait you so much.
     
  40. mkgame

    mkgame

    Joined:
    Feb 24, 2014
    Posts:
    583
    Hi,

    since Arons pathfinding don't have anymore a local avoidance implementation, your asset looks very interesting. I need a pathfinding solution for a strategy game and i don't want to reinvent the wheel again, because an RTS game has so much components, that i don't have the time for implementing a part of it, except the moving behavior of the units. I would have just some questions.

    1. Do you support multiple level terrain pathfinding? (eg. move on the bridge and under the bridge)
    2. Can i use it for a big terrain with A* 1000*1000 grid? And moving about 100 units at the same time from one corner to another corner?
    3. Can i configure the local avoidance system behavior? Eg. Can a unit push away another units, needed if i build lot of units in a building? (if there is no path to a grid, because it is blocked by another units, then the shortest path should be calculated to the grid and all units on the grid should move away.)
    4. Because of the units size, the units can stuck on pathes which are to near to obstacles. Do you have a solution for that?

    Thanks in advance for your time.
     
  41. ScriptGeek

    ScriptGeek

    Joined:
    Mar 4, 2011
    Posts:
    45
    Hi limdorn,

    I checked out your latest demo: https://dl.dropboxusercontent.com/u/54848710/PE20BETA/avoidance2.0beta.v2.html

    The bots appear to work just fine during light traffic conditions, but they often walk or pass through each other during heavy congestion. Here's a screen shot of two bots walking through each other:

    $pathfinding_bug.png

    It looks like the same problem as before, but instead of getting stuck they just continue moving through each other.
     
    Last edited: May 19, 2014
  42. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    WOW. Good questions !
    1 - Right now I'm focusing on creating a fast and robust system. Support for multiple layers will be included in the future but not now.
    2 - I tried to create a scene with your specifications and works well with version 2.0 but takes too long to calculate the paths for all agents at once.
    3 - The avoidance Local is currently implemented to be a simple and non-configurable system.
    4 - I would not had been considered so far.

    At this time, and by request of many users, I have decided to redo the code to take into account all these points you have show me.
    I've been researching and I think the best option is to create a system search paths from Voronoi.
    Here I have found a very didactic video:
    https://www.youtube.com/watch?v=tH9dNESH4ic

    Once implemented this venue is the avoidance may be implemented with a steering Behaviour.
    These changes will require a little time to be ready the version 2.0.
    Forgive me for any inconvenience this may cause. :(
     
    Last edited: May 20, 2014
  43. mkgame

    mkgame

    Joined:
    Feb 24, 2014
    Posts:
    583

    1. Is nice to have this feature, but if it comes in the future it is okay. A saw your beta multi layer demo.
    2. I got in expensive pathfinding solutions 1 sec. calculation time for each path. I don't know why this happens, because the terrain was quite empty. In this case A* should calculate a line form the target to AI, and this should be done very fast. Generally A* should be a fast solution for non complicatad terrains.
    3. Thats okay, but what kind of algorithm do you use for? Probably Clear-Path?
    4. Another pathfinding solutions have trouble with this problem. For an RTS game i would need this feature, and i see other people have the same problems. I don't know how Unity Pro pathfinding handle this.

    And, these are questions for a 100$ pathfinding solution, so nothing is embarassing on it to have this results yet!
     
  44. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    Hi mkgame.
    First thanks for your understanding but my idea is to do something great.
    I have been researching other pathfinding systems and now I'm trying to create new one: I like flow field pathfinding used in games like supreme commander 2 to planetary annhilation.
     
  45. EasyPlay

    EasyPlay

    Joined:
    Mar 23, 2014
    Posts:
    8
    I look for a solution for dynamic generated grids in real time run,my grids is dynamic generated,but I found many path finding solution,it is difficulty to realize,if your solution can solve this ,it is great.I hope your 2d solution come out quickly.
     
  46. EasyPlay

    EasyPlay

    Joined:
    Mar 23, 2014
    Posts:
    8
    I test your solution,it is very great.But I want to use it in my 2D project,In your PathfindingEngine,only set In X Z,
    unfortunately 2D is X Y,If I can set In X Y,I think I will use it for solve my problem.
    1 p1.png
    My objects move in local space,I want to avoid to nails,and the red ,blue,green object patrol;
    2, p2.png
    for a moment,I slice the plane to two area,the object move in two area,not connected.
    which all in local space.in the same,avoid to nails.

    if I use 3D collison replace 2D collison,rotate the X,Z to X,Y,I think solve my problem.

    can your give me some suggestion?
     
  47. limdorn

    limdorn

    Joined:
    Jan 5, 2012
    Posts:
    56
    Hello everyone.
    First sorry to everyone to not contact with the forum: I have a new home and internet service has taken a few days to work.
    Now I´m here again and I will update pathfinding engine with 2d support.
    This update will not be a v2.0 but to all people who need it will be enough.
    In several days will be ready. I promise.
     
    Last edited: Jun 13, 2014
  48. c-Row

    c-Row

    Joined:
    Nov 10, 2009
    Posts:
    799
    Hi lindorn

    1. Can the system be set up so an agent only travels along the grid lines rather than a smooth path? I know people usually ask for the other way around, but I am explicitely looking for a grid-based movement.
    2. If so, can I tell agents to pause between nodes for a short amount of time?
    3. Can an agent somehow find a neighbour point in a certain/random direction and move there? I would like to place an agent on a node and have him move to the next neighbour point in the direction I click (or a random neighbour when not clicking anywhere).
     
    fishZombie likes this.
  49. fishZombie

    fishZombie

    Joined:
    Apr 28, 2014
    Posts:
    8
    Hey c-Row, I'm looking for the same thing. :p
    Limdorn Thank you very much for creating this awesome Asset. My Agents will be moving (I hope) on a boardgame-like tile system. I'm hoping not to have to patch in someone else's grid asset on top of yours.
    I'm looking to do Mobile games (so fast comp speed is important).
    Having a setting for how smooth the path traveled is, would be very nice.
    something like a ... 10 would have it running smoothly, and a 1 would have it popping from Grid-Point to Grid-Point, with a timed pause at each move.
    I could do this in GS, but Unity is new to me, so I'm hitting the big learning curve.
     
  50. Zelek

    Zelek

    Joined:
    Jun 12, 2010
    Posts:
    87
    Hi limdorn,

    Any update on how things are coming along? Are you still planning to add support for 2D with local avoidance, or have you decided to take a break from the project?