Posted By

nulldev on 02/18/15


Tagged

path example a find Star pathfinding Finding


Versions (?)

A* Pathfinding Example


 / Published in: Java
 

URL: http://software-talk.org/blog/2012/01/a-star-java/

An A* pathfinding algorithm in Java, taken from: http://software-talk.org/blog/2012/01/a-star-java/

  1. /**
  2.   * The main A Star Algorithm in Java.
  3.   *
  4.   * finds an allowed path from start to goal coordinates on this map.
  5.   * <p>
  6.   * This method uses the A Star algorithm. The hCosts value is calculated in
  7.   * the given Node implementation.
  8.   * <p>
  9.   * This method will return a LinkedList containing the start node at the
  10.   * beginning followed by the calculated shortest allowed path ending
  11.   * with the end node.
  12.   * <p>
  13.   * If no allowed path exists, an empty list will be returned.
  14.   * <p>
  15.   * <p>
  16.   * x/y must be bigger or equal to 0 and smaller or equal to width/hight.
  17.   *
  18.   * @param oldX x where the path starts
  19.   * @param oldY y where the path starts
  20.   * @param newX x where the path ends
  21.   * @param newY y where the path ends
  22.   * @return the path as calculated by the A Star algorithm
  23.   */
  24. public final List<T> findPath(int oldX, int oldY, int newX, int newY) {
  25. openList = new LinkedList<T>();
  26. closedList = new LinkedList<T>();
  27. openList.add(nodes[oldX][oldY]); // add starting node to open list
  28.  
  29. done = false;
  30. T current;
  31. while (!done) {
  32. current = lowestFInOpen(); // get node with lowest fCosts from openList
  33. closedList.add(current); // add current node to closed list
  34. openList.remove(current); // delete current node from open list
  35.  
  36. if ((current.getxPosition() == newX)
  37. && (current.getyPosition() == newY)) { // found goal
  38. return calcPath(nodes[oldX][oldY], current);
  39. }
  40.  
  41. // for all adjacent nodes:
  42. List<T> adjacentNodes = getAdjacent(current);
  43. for (int i = 0; i < adjacentNodes.size(); i++) {
  44. T currentAdj = adjacentNodes.get(i);
  45. if (!openList.contains(currentAdj)) { // node is not in openList
  46. currentAdj.setPrevious(current); // set current node as previous for this node
  47. currentAdj.sethCosts(nodes[newX][newY]); // set h costs of this node (estimated costs to goal)
  48. currentAdj.setgCosts(current); // set g costs of this node (costs from start to this node)
  49. openList.add(currentAdj); // add node to openList
  50. } else { // node is in openList
  51. if (currentAdj.getgCosts() > currentAdj.calculategCosts(current)) { // costs from current node are cheaper than previous costs
  52. currentAdj.setPrevious(current); // set current node as previous for this node
  53. currentAdj.setgCosts(current); // set g costs of this node (costs from start to this node)
  54. }
  55. }
  56. }
  57.  
  58. if (openList.isEmpty()) { // no path exists
  59. return new LinkedList<T>(); // return empty list
  60. }
  61. }
  62. return null; // unreachable
  63. }

Report this snippet  

You need to login to post a comment.