[LIB] A* Pathfinding Algorithm

Discussion in 'Resources' started by Adamki11s, Feb 16, 2013.

Thread Status:
Not open for further replies.
  1. Path finding is something I looked into a while ago, but was too complicated for me to code myself at the time, and there were no open source libraries out there for Minecraft that I could find. Recently, for my plugin, QuestX, I wanted a better path finding implementation than the one that came with the NPC library and thought I may as well share it, so here it is for all of you to use!

    The library can be downloaded here : Download A* Pathfinding Library

    All you have to do is download and unzip the files and add them to your project. If you publish the plugin I would appreciate if you credited me.

    How to use the Library

    The only file you need to be working with is AStar.java. The constructor takes three parameters, the start and end location, and the range in blocks. Here is an example of creating our AStar pathfinder and using it. The implementation will be explained below. The range search parameter is there as a safeguard to stop exhaustive pathfinding. Any blocks outside of the specified range will not be considered, if the distance between the start and end location is greater than the range then the pathing result will be NO_PATH and the pathfinding operation will not be ran, so you can use this as a safe way to check the distance if you wish.

    Code:java
    1.  
    2. Location start, end;
    3. int range = 10;//any blocks further than 10 away from the start will not be considered, if a destination of further than 10 blocks is specified NO_PATH
    4.  
    5. try {
    6. //create our pathfinder
    7. AStar pathFinder = new AStar(start, end, range);
    8. //get the list of nodes to walk to as a Tile object
    9. ArrayList<Tile> route = path.iterate();
    10. //get the result of the path trace
    11. PathingResult res = path.getPathingResult();
    12. } catch (InvalidPathException e) {
    13. //InvalidPathException will be thrown if start or end block is air
    14. if(e.isStartNotSolid()){
    15. System.out.println("End block is not walkable");
    16. }
    17. if(e.isStartNotSolid()){
    18. System.out.println("Start block is not walkable");
    19. }
    20. }
    21.  
    22.  


    Every time you construct an AStar path object it must be wrapped in a Try-Catch block to handle an InvalidPathException which will be thrown if either the start or end Block at the Location specified is not walkable. Walkable blocks are any blocks which are not lava, fire, wheat, ladder, air or any block which can be walked through such as long grass and torches.

    Once your AStar object is constructed you want to run the algorithm and get the blocks to your destination. The iterate() method runs the algorithm and returns an ArrayList of Tiles. Each Tile object denotes a block as an offset from the starting Location. To get the Location of a Tile you do the following.

    Code:java
    1.  
    2. Tile t;
    3. Location startLocation;
    4.  
    5. Location endLocation = t.getLocation(startLocation);
    6.  


    So, simply pass in your starting Location and the Location specified by the Tile offset will be returned.

    Now, in the case of failures a PathingResult enum is set inside the AStar class. After calling iterate() you should check the pathing result before performing any operations on the Tile list. In the case of failure the ArrayList<Tile> will return null so it is important to do this, moreover it is easy to do so. The PathingResult can take one of two values : SUCCESS and NO_PATH. Success is returned if the pathfinding operation is complete, NO_PATH is returned if no path could be found or the distance was greater than the range to search.

    Code:java
    1.  
    2. //assume pre constructed pathing object
    3. AStar pathing = preconstructedAStarPathingObject;
    4. ArrayList<Tile> = pathing.iterate();
    5. PathingResult result = pathing.getPathingResult();
    6.  
    7. switch(result){
    8. case SUCCESS :
    9. //Path was successfull. Do something here.
    10. break;
    11. case NO_PATH :
    12. //No path found, throw error.
    13. break;
    14. }
    15.  


    That is all there is to it :). Once you have your nodes you can do whatever you want with them, make your entity walk to them, change the block type etc. Here is a final example where the nodes returned are all changed to diamond.

    Code:java
    1.  
    2. public void runPathing(final Location start, final Location end, final int range){
    3. try {
    4. //create our pathfinder
    5. AStar path = new AStar(start, end, range);
    6. //get the list of nodes to walk to as a Tile object
    7. ArrayList<Tile> route = path.iterate();
    8. //get the result of the path trace
    9. PathingResult result = path.getPathingResult();
    10.  
    11. switch(result){
    12. case SUCCESS :
    13. //Path was successfull. Do something here.
    14. changePathBlocksToDiamond(start, route);
    15. break;
    16. case NO_PATH :
    17. //No path found, throw error.
    18. System.out.println("No path found!");
    19. break;
    20. }
    21. } catch (InvalidPathException e) {
    22. //InvalidPathException will be thrown if start or end block is air
    23. if(e.isStartNotSolid()){
    24. System.out.println("End block is not walkable");
    25. }
    26. if(e.isStartNotSolid()){
    27. System.out.println("Start block is not walkable");
    28. }
    29. }
    30. }
    31.  
    32. private void changePathBlocksToDiamond(Location start, ArrayList<Tile> tiles){
    33. for(Tile t : tiles){
    34. t.getLocation(start).getBlock().setType(Material.DIAMOND_BLOCK);
    35. }
    36. }
    37.  
     
  2. Offline

    WarmakerT

    Awesome, thanks!
     
  3. Offline

    fullwall

    Just some thoughts after looking at the code.
    Why the usage of LinkedList? ArrayList is faster and uses less memory.
    EDIT: also, the code makes the open and closed set a list - this is very slow. Euclidean distance is a better heuristic than 3D Manhattan distance (which only works well in 2D)?
     
  4. fullwall
    I chose to use linked list because there is less overhead when adding elements which exceed the size of the array list as for a linked list the array doesn't not have to be expanded and copied. However it would probably be better to return an ArrayList, this is an oversight on my part thanks for pointing that out. However I haven't tested performance using ArrayList but I anticipate it would be worse, by how much I'm not sure.

    I will run some tests now and let you know what I find.

    As for the heuristic you are correct, the difference between the two are negligible and Euclidean should be favoured for 3D as it would return a shorter path and probably provide a faster overall execution time. I must have got some anomalous results during my testing which led me to believe that Manhattan was significantly faster in 3D.

    As for the open and closed set I thought an ArrayList be be the fastest implementation, what would you suggest?
     
  5. Offline

    chasechocolate

  6. Offline

    fullwall

    Adamki11s - I would use a Set or Map for the open/closed set, because you're mainly doing membership tests and iterating the open/closed as a list every time you want to expand is slow, especially if you're pathfinding over a large area.
     
  7. fullwall
    Big thanks to you, Fulwall for pointing that out to me, can't believe I didn't think of that before.

    The pathfinding now runs approximately 10 times faster :D. I'll be updating the link shortly.

    EDIT : Library has been updated.
     
  8. This is awesome and I would really like to add this ty my plugin but I have some problems ;)
    1. some blocks are only sometimes solid (doors, fencegates).
    2. Blocks that are higher than 1 Block (fences, cobblestone walls).
    3. View attachment 12788 View attachment 12787
    Keyle
     
  9. Keyle
    Thanks for pointing that out, I'll get to work on fixing that.

    Could you try and clarify points one and two? The AStar class can be modified if you wish to make some Blocks such as fences walkable.
     
  10. point one and two are not problems for me, it's just something that could be added to the default script
    1. View attachment 12789
    2. View attachment 12790 the problem is that most entities can't jump over fences so it's not a valid path
     
  11. Keyle
    I see your point, thank you. I will update this tomorrow.

    As for your first picture I understand how the current class doesn't provide support for that. I think what I will also do tomorrow is modify the pathfinder so that you can set a boolean flag on whether doors will be counted as a solid object and then when you are iterating over the tiles you can check if the object above is a door so then you can open it or do whatever else you wish.
     
  12. This is awesome, thanks!
     
  13. iKeirNez chasechocolate WarmakerT
    Glad you like it :).

    Keyle

    Library, has been updated.

    Walking diagonally through blocks has been fixed.
    [​IMG]


    Fences have been fixed, fence gates will now be walked through if the gate is open.
    [​IMG]
     
  14. Adamki11s
    Thanks for updating the Library. I also added some improvements to it (GitHub PullRequest).

    The is one think left that would be nice to have:
    View attachment 12797
    An option to let Entities jump down cliffs that are not higher than 3(or more) blocks.

    Edit: Ok nevermind, got it figured out myself.

    Keyle
     
  15. Keyle
    Some nice changes there, thanks, a few blocks I had forgotten about.

    That suggest of the entities jumping down is a nice idea, but I think it's better to leave it as is, until I make this option configurable as some people will not want the pathfinder to behave in this way.
     
  16. Offline

    AnniKa

    You can get alot of more speed when you put your open nodes into a Binary tree, just sort it so that the ones with low Gcost / Dist to target onto top on the binary tree and always take the nodes from the top of the tree.

    And if you just flush the closed nodes as metadata into the map you can also save alot time, instead of search the list if the node is in just check if the metadata at xyz cord exists, also you can put the direction to go into the metadata aswell so other plugins can then easy acces the path information.

    just how i did id a while ago^^
     
  17. Offline

    Haribo98

    This really should be part of the BukkitAPI. It's great!
     
    Chlorek, BRampersad and Adamki11s like this.
  18. Haribo98
    Thanks ;).
    AnniKa
    I replied to your reply on the old thread by mistake. I tried the binary node implementation but I had trouble, I find the HashMap works well at the moment and think its performance should be close to that of a binary tree because of the constant seek times. Although it's hard to tell because our algorithms work differently.

    The library has been updated. The maxIterations feature is now obsolete and has been replaced by a range search function. Any blocks outside of the specified range from the start location will not be considered, if you pass in two locations who have a greater distance between them than the range parameter then you will immediately receive a NO_PATH error.
     
  19. Offline

    Miro

    so.. how would i add this to the pathfinding of a custom mob..?
     
  20. Miro
    You'd have to create a class to override the mob and then override its pathfinding method with this library. In the resources section there is a tutorial on editing mob behaviour.
     
    Miro likes this.
  21. Offline

    Miro

    I already have a custom mob class.. but i have no clue where to put the a*... do it like this? this.goalSelector.a(0, new PathfinderGoalFloat(this));
     
  22. Miro
    I don't know how mobs perform path finding. I'm afraid you'll have to figure this out yourself. Although you should be able to use the tiles returned by the pathfinder to make the mob walk to the next block in its path.
     
  23. Offline

    fullwall

  24. Offline

    amadornes

  25. Offline

    unforgiven5232

    How can i add the 2 locations of where the entity can go!?
     
  26. Start and end location are defined as parameters in the constructor.
     
  27. Offline

    unforgiven5232

    yeah but how do i define them to s block?
     
  28. Offline

    BRampersad

    2 questions:
    1. How does this handle dynamic end paths such as a moving entity or a player.
    2. Does it calculate jumps and holes in the ground. Instead of trying to go around the gap, it calculates weather a mob can safely jump over the gap.
     
  29. BRampersad
    If you look how I do it in QuestX I just recalculate the route each second. https://github.com/Adamki11s/QuestX/blob/master/src/com/topcat/npclib/entity/NPC.java

    However an alternative to this is taking the end location and then pathfinding from there to the new location, unless you are pathfinding over large ranges (70+ blocks) you shouldn't notice much of a hit in performance. You can run performance tests if you wish but from memory it took about 0.02 seconds to find a path around 40 blocks away over a small hill.

    As for calculating holes and jumps no, if you need this functionality you will need to build it into the search algorithm. Although you are the second person who has suggested this so I am considering adding support for it :).
     
Thread Status:
Not open for further replies.

Share This Page