Search Unity

[Released] BFGames: Simply A* Pathfinding! NOW FREE

Discussion in 'Assets and Asset Store' started by BFGames, Dec 28, 2012.

  1. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    Update: Null reference bug on empty list fixed and submitted
     
  2. rosevelt

    rosevelt

    Joined:
    Oct 23, 2012
    Posts:
    47
    Thanks,
    It's a top-down ARPG all movements and path are in 2D.

    Can you point me to a page or write a few words what could be of major difference between your product and A* Pathfinding (Aron Granberg)

    Thanks
     
  3. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    I have never used Aron's system so i cannot comment on it really, because i have no idea how he creates hes maps or if it even works for procedural generated levels.

    My systems uses raycasting from the Y-axis down to create my node grid. It then checks the Y height and tag's on objects to determine if it is a collider you can walk on, you cannot walk on or it should ignore. It is generated in my pathfinders start method() which means it can easily be used for auto generated levels. My system can update the map based on new objects bounding boxes (It is however limited how many updates it can handle at once)
     
  4. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
  5. cristims

    cristims

    Joined:
    Dec 21, 2012
    Posts:
    24
    I do not know if you have any spare time, but if you do please consider this:

    in some turn based games the floor tiles around the selected unit are colored indicating the walking area, using a given walk range, and a pathfinding that avoids obstacles and other units on a given plane map.

    now i will gladly pay for a simple turn based pathfinding system, with javascript support and some of options like:
    - square grid
    - hex grid
    - corner movement (on/off- for square grid)

    of course a walk range will be provided by the game
    a plane or an object that defines the floor
    and a grid size

    and the pathfinding returns an array with the surrounding walkable tiles

    (I will really pay even for a simple square grid... no need for hexes or corner options...)
    just that I need that nice colored walkable tile effect.

    A "simply A* for turn based games" will be just great!
     
  6. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    It is a really cool idea, and it is possible. But i probably not gonna happen, at least not the next 6 months. You probably need to write one yourself ;)

    1. It works quite differently then A* - (though A* would be a part of it).
    2. Hexagon tiles a more suitable for this, so would need to re-write my system.
    3. So all in all, if i was to do this right i would create a whole new asset...
     
    Last edited: May 3, 2013
  7. GBCFraser

    GBCFraser

    Joined:
    Apr 11, 2013
    Posts:
    94
    I picked up the basics of your script in about two hours. Its suits my needs, now I just need to plug it in.
     
  8. GBCFraser

    GBCFraser

    Joined:
    Apr 11, 2013
    Posts:
    94
    I noticed that the grid only works on maps that have one layer (if there is a platform underneath the top one, it will not work unless you use the path finding grid nodes!). So its basically 2.5D or Isometric, it just so happens to work perfectly with my project, its quite good for my needs, and I might of done it myself if the idea had been described to me, but you probably saved me 1-3 weeks of figuring it out, learning, and debugging so its worth $20 very much so! I do not plan to have anything like cutaway floors so this is great. But as its future utility as an asset, I would like to know if you have any plans to implement tools to make it full 3D?
     
  9. cristims

    cristims

    Joined:
    Dec 21, 2012
    Posts:
    24
    new asset sounds great
    you can start whenever you have the time, create a bare bone system for this (only for squares, something simple), and then add more features as you go...

    (just make sure to post here when you have something in the store)
     
  10. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    It is great that i works for you!

    But what do you mean by full 3D? Like for space games and stuff like that? If yes, then i would never use A* for that. Having your map in a 3D world (array) would be too heavy for performance and memory, sure it can be done, but i would never use this Technic for that, as each node would have 26 neighbors and the world wouldn't be very big before it got out of proportion.
     
  11. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    Actually i thought about it some more, and i do really like the idea (and challenge hehe :D). So when i get some time off, after my exams i will look into creating a full asset for turn based games (would like to create a game like that myself)! :cool:
     
  12. cristims

    cristims

    Joined:
    Dec 21, 2012
    Posts:
    24
    great news!

    good luck with your exams!
     
  13. marcaurelio74

    marcaurelio74

    Joined:
    Sep 2, 2012
    Posts:
    58
    Hi BFGames,
    some question's :

    A) I have a terrain approximately 5kmX5km do you think that your grid can cover this map size?
    B) Alternatively do you know the max size of terrain that your grid can cover with 1.000.0000 of nodes?
    C) Is possible to use in the same terrain several grid?

    Thanks
     
  14. GBCFraser

    GBCFraser

    Joined:
    Apr 11, 2013
    Posts:
    94
    Not at all BF, I meant like floors, with a cutaway design, I would never use this for a 4X space game like Homeworld! Do you remember X-Com (Old Version)? Each spaceship(the interior level), farmhouse, warehouse, suburban house or office, had 2-4 floors. The system could handle up to 8 levels. Do you remember Ultima7? The game could handle 3 floors with a cutaway mode. But the path-finding stank and the enemies would wait for the player on the first floor, Origin software developed very bad real-time path-finding for a long time.

    This grid pathfinding is great 2.5D, in my opinion, because it can't handle floors, so if I make a ramp to another level, there is nothing underneath.
    There are work around which companies like Blizzard Entertainment use, like a level loading screen for stairs or moving from exterior to interior.

    Let me show you an example of what I would like to do in a game sequel, if my current one sells.
    $Example_Sm.png
    Because there is a raycast that stops at the first floor it hits, when generating the map, it doesn't register multiple floors.
    Obviously I can use the waypoint pack, which I might use for enemy patrols and realistic AI. But a hybrid system seems like alot of work to get to work properly, and debug. This is great for small levels or game scenariors, but not large game worlds which are made rapidly, way-points would have to be hand done every level. It would cost me time and would result in less levels for the gamer to play. For a large level it would be more time effective if we could just hit generate, and input the number of depths the raycaster should generate a grid for up to a value of, lets say 8. I guess I'm asking for 2.75D? I would gladly pay for an upgrade in lets say, a year.

    Currently I'm working on finding a way to register an event into your path generation system, at the moment an RTS unit doesn't respond because the path isn't generated instantly, you're using a queue, the unit automatically reverts to idle state because no path is generated instantly, obviously there is a bottleneck consideration which is a great to have your code do that, I have to work around. I think a co-routine which waits for, lets say... .25 seconds wait, or until a path is generated is all that needed.

    Make no mistake, I'm very happy with it and it will work very well for this iteration of my game. I'm doing levels like the one beneath and it works well.
    $Showcase_Sm.png
     

    Attached Files:

  15. GBCFraser

    GBCFraser

    Joined:
    Apr 11, 2013
    Posts:
    94
    1,0000,000 nodes = a grid of 1000 X 1000. And you don't need to make a square game map. If you have a large terrain, you can make the static colliders bigger and increase the tile size.
     
  16. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    A. You set the size of each node, so yes it can but if it is very big the precision might not be so good. However i am changing how it works in the next update such that it can handle more than 1 mill.

    B. see A

    C. Nope
     
  17. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    GBCFraser i see what you mean. No it is not something im looking to update it with at the moment, as it does not really work with how my system is build.

    The waypoint based solution is created to handle such situations - but ofcause manually setting up waypoints can be a lot of work.

    Unity's own system can however handle this if im not mistaking (needs pro for that though).
     
  18. GBCFraser

    GBCFraser

    Joined:
    Apr 11, 2013
    Posts:
    94
    BFGames, thank you for the support.

    Unity's mesh system adds movement too, and I wasn't liking that, as well as the basic unity restrictions which cause problems when I'm out of the studio on weekends. Plus, they like static levels, I have dynamic objects like doors, elevators, so on...

    I've integrated your path-finding with the Unity character controllers. Things can get a bit bumpy with disallowed tags around corners with my integration, as my colliders, won't always be snapping to the grid perfectly, it seems things are rounding down on disallowed items sometimes. Is there a way to make the disallowed exclusions round up on the grid?
     
  19. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    Could add something that would help on your problem, but you could also decrease the tile size ;)
     
  20. THRILLHOUSE

    THRILLHOUSE

    Joined:
    May 22, 2013
    Posts:
    6
    I too had this problem when I first used opened the demo scene, but what I figured out was that because the waypoints were imbedded halfway through the geometry the player controller would get hung up. moving all the waypoint up didn't help either I had to shift the entire level down so that all the path nodes were completley above the geo and not intersecting with it. I had to make sure of this whenever I made my own levels as well.

    Also the readme intructions told me to use the "pathfinding" script on the player, but that did nothing. In the demo scene the player had the "waypoint player" script attached for it to work. Was this just a typo or am I really supposed to use the pathfinding script and I just did did it wrong?
     
  21. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    1. Yes there was a mistake in the demo scene with the position of geometry. Dont know how the hell this happened as i have not touched it since i created if for the web-player used to showcase on the asset store, which still works. Maybe a unity update that screwed it over.

    2. You should use the pathfinding script! The waypoint player script is just for the showcase extending the pathfinding script, and will only work in a few cases. The pathfinding script is the basic script! you need to code how to move (like with the mouse in waypoint player script) yourself. The reason behind this is that everyone needs a different setup more of less.
     
  22. RiverL

    RiverL

    Joined:
    May 23, 2013
    Posts:
    1
    Hi,
    Could simply a* can export the navmesh data. Becuase I develop a mmogame, I need it can check the collison and path in c++ server.
     
  23. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    Its not using a mesh data so nope ;)
     
  24. THRILLHOUSE

    THRILLHOUSE

    Joined:
    May 22, 2013
    Posts:
    6
    question-
    before I spend a month on trial and error coding I was wondering if it sounds possible to click on waypoints using multiple cameras? Like right now I have my main camera just a black screen, and several other cameras rendering different angles of a scene on top the black, they are all tagged with "main camera" but it seems like its only responding to the very first camera which is all black if that makes sense. I want to be able to click inside different camera windows and have it respond correctly
     
  25. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    Did you try the test scene (grid test scene) it actually got 2 cameras setup, and you can click in both. So it is very possible to do so with as many cameras as you like.

    What you do with this system is to simply feed it with an end position. So when you ray-cast into the world to find your position, simply remember to create an ray from the correct camera. As the grid scene does so, you can see an example of how it is coded ;)
     
  26. DanarKayfi

    DanarKayfi

    Joined:
    Aug 27, 2012
    Posts:
    69
    HI, i don't know if someone asked this before...but i followed the the steps to do way point one by one, but seems like the Right Click is not working! for some reason i cant place any node?
    PS im using it to do a 2D Tower defence and i have a Tile Map
     
  27. DanarKayfi

    DanarKayfi

    Joined:
    Aug 27, 2012
    Posts:
    69
    Never mind i solved the problem :D i must put a collider to the tile map then press right click LoL
    Thanks alot its an amazing solution :)
     
  28. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    Hehe was just going to ask about it.
     
  29. THRILLHOUSE

    THRILLHOUSE

    Joined:
    May 22, 2013
    Posts:
    6
    thanks for the quick replay! I'll get on that

    also I'm not using the grid based one
     
    Last edited: Jun 8, 2013
  30. DanarKayfi

    DanarKayfi

    Joined:
    Aug 27, 2012
    Posts:
    69
    ok, just a a quick question, in Tower Defence Games the enemies always knows where to go (the end point) where to change in the code to make it always going to a fixed location?
     
  31. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    You just send the vector3 location.
     
  32. Julian-S

    Julian-S

    Joined:
    May 31, 2013
    Posts:
    72
    Hey BFGames I've got a quick question.

    I'm designing a game where I have a boat that I want the crew to navigate. It has a few layers so I'm guessing if I bought your system, I would use waypoints to set up the boat.

    The thing is that the boat will probably be constantly moving and rotating. Is there a way for the nodes to keep up with that so that the crew can navigate the ship while the ship is moving around and rotating?

    Thanks,
    Julian
     
  33. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    Nope sorry. When waypoints a placed the position won't change.

    Guess you have to create your own system for this, connecting waypoints which are a part of the ship as child objects that will follow the ship - this way you always have the right position. Another thing you need to consider is that everytime the ship moves you needs to have every crew member move just as much ;)

    GL
     
  34. Julian-S

    Julian-S

    Joined:
    May 31, 2013
    Posts:
    72
    Thanks for the quick response!

    I'm not exactly sure how the pathfinding is set up, but this is what I'm thinking. Have the waypoints set up on the ship, and the ai script on the crew member. I would cache the original transforms of the ship and the crew member. Then when the ship moves, the crew member moves with it. Then, when the crew member is looking for a path, I could somehow displace the path/where he is on the path by where the ship is relative to the initial starting position? Do you think something like that would work? I'm really trying to avoid writing my own system here, haha.
     
  35. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    Well what you suggest would be writing your own system more or less.

    Anyways the easiest way to make sure that crew members follows the ship, is to have them become a child object of the ship when they board it.
    In this manner they will move along with the ship. Now you just need to move them in the ships local space, which would also be where the coordinates from the waypoints would fit in as they should be a child object too.
     
  36. Julian-S

    Julian-S

    Joined:
    May 31, 2013
    Posts:
    72
    Right right. I guess my question is, will it work to use Simply A*, or should I just use empty game objects as my own nodes and code my own pathing system between those nodes?
     
  37. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    Use your own. Simply A* is not created for this type of matter ;)

    You could rewrite parts of it, but im sure it would be faster to create your own system in your case.
     
  38. Julian-S

    Julian-S

    Joined:
    May 31, 2013
    Posts:
    72
    Alright, thanks for your help and suggestions! I think this way will be a good challenge and learning experience anyway ;)
     
  39. CMoss

    CMoss

    Joined:
    Apr 21, 2009
    Posts:
    75
    I'm trying to use the grid based pathfinder on a flat surface, but when the max falldown height and climb limit is set to 0, it doesn't work. When they are given a value, it works, but the agent will move up or down at the beginning and end of the path even if the surface is flat there. Any idea why this would be happening?

    The example scene doesn't work either when the max falldown height and climb limit is set to 0, so why do the docs say to do that if the map is flat?

    Why can't I use the 2d version with Y as up? Or is that an option?
     
    Last edited: Jun 14, 2013
  40. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    Should work with zero, might be a bug though i will check for that as soon as i am home. The 2D version cannot be used with Y as the up axis, because the other thing should work.

    Now the problem you got with path movement has nothing to do with max falldown height and climb limit. When you search for a path it will return the paths which holds Vector3 positions, which for all grid squares will be at the level of the terrain. It will however also add the player/ai's position as the first position and the position you are going to as the last (which should be the same i guess, but don't know how you obtain it) these might not have the same Y value of the terrain.

    Therefore if you just move towards the position of the vectors (most simply way of moving) then it will go up and down if the Y coordinates are not the same.

    With a CharacterController or Rigidbody this is easily solved. But if you are not using any of these it is pretty easy to solve too, but it depends on your characters pivot point.

    What are you using for movement at the moment? Remember all scripts are just examples for different ways to use the system. The package is simply just returning the path, because i want it to work for as many different games a possible, and doing so does not limit it it any ways.
     
    Last edited: Jun 14, 2013
  41. CMoss

    CMoss

    Joined:
    Apr 21, 2009
    Posts:
    75
    Thanks, the movement in Y isn't really a problem, I'm just zeroing it out now at the end of the movement function. It's probably an issue with my script anyway. I think this system will work out well for what I'm doing.
     
  42. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    Glad to hear! Zeroing out is a good idea for a flat game. If you run into some problems just ask. I can easily provide some example methods for doing different stuff and so on ;)
     
  43. Mister-D

    Mister-D

    Joined:
    Dec 6, 2011
    Posts:
    1,562
    hi, will your system work with playmaker?
     
  44. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    I have never used PlayerMaker, so i cannot say. But it is not build with it in mind.
     
  45. Copywright

    Copywright

    Joined:
    Apr 17, 2012
    Posts:
    21
    Hey! Would it be possible to work out a waypoint solution for 2D XY plane? Or is it already supported?
     
  46. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    The waypoint system work for all planes. It just needs a collider that you can "click on" in the editor window.
     
  47. kevdotbadger

    kevdotbadger

    Joined:
    Sep 13, 2011
    Posts:
    82
    Has anyone used this with Toolkit2D's tilemap system?
     
  48. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    If tiles got a collider attached (which i think they do) then it will work for top down like games (XY axis). If you want to use it in the XZ plane for something like a platformer, then no - but then you would not use A* to begin with ;)
     
  49. DanarKayfi

    DanarKayfi

    Joined:
    Aug 27, 2012
    Posts:
    69
    Hey again :)
    another quick question, I'm using your plug in in my Tower Defence game, and i'm using the waypoint, my question is: how to make the catapult rotate to face the way its moving towards ?
     
  50. BFGames

    BFGames

    Joined:
    Oct 2, 2012
    Posts:
    1,543
    Use something like Vector3.RotateTowards, and then what you rotate towards is index 0 of the returned list (or array if you use JS). The list is called Path in your script, so:

    Vector3.RotateTowards(transform.position, Path[0], Time.deltaTime * some speed variable);
    You can then use the returned vector in something like transform.Rotate;

    But that is more a unity question, doesn't really have much to do with me asset hehe ;)
     
    Last edited: Jun 20, 2013