Advertisement
Guest User

Untitled

a guest
Apr 30th, 2014
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.75 KB | None | 0 0
  1. ArrayList<Coordinates> makePath(Coordinates startNode, Coordinates endNode, ArrayList<Coordinates> pathSoFar, ArrayList<Coordinates> closedNodes, ArrayList<Coordinates> openNodes)
  2. { //recursively finds the path from startNode to endNode:
  3. //start @ starting node, make list of ways out of it
  4. //for each of these potential paths, find all the potential paths out of them
  5. //and so on until these paths reach the end
  6. //as the recursion collapses, the best paths are passed back up, and the others discarded
  7. //this ensures that the path returned by the last call of the method is the best one
  8. //this method is very, very inefficient, but is very simple
  9. //mainly, however, since the map has a very tiny number of potential paths, relatively speaking, the inefficiency is acceptable
  10.  
  11. //if first call (just starting)
  12. if (openNodes.size() == 0 && !closedNodes.contains(startNode)) { openNodes.add(startNode); }
  13. int a = startNode.z; //traced NullPointerException back to here
  14. Coordinates n = openNodes.get(0); //get a node to test
  15. openNodes.remove(0); //remove it from the open nodes, so don't repeat it later
  16. closedNodes.add(n); //record that have done this one
  17. ArrayList<Coordinates> adjacent = getAdjacentCoords(n);
  18. //get the nodes that are adjacent to this one
  19. for (int i = 0; i < adjacent.size(); i++)
  20. {
  21. //if this adjacent node has not yet been checked - this prevents infinite loops
  22. if (!openNodes.contains(adjacent.get(i)) && !closedNodes.contains(adjacent.get(i)))
  23. { //add it to the list of nodes to check
  24. openNodes.add(adjacent.get(i));
  25. }
  26. }
  27. //if reached destination
  28. if (n.equals(endNode))
  29. { //done
  30. pathSoFar.add(n);
  31. return pathSoFar;
  32. }
  33. else
  34. {
  35. ArrayList<ArrayList<Coordinates>> pathList = new ArrayList<ArrayList<Coordinates>>(); //list of potential paths that come from this node + path
  36. // openNodes = coordOrder(openNodes, endNode); //don't need this (right now, at least), as dealing with a tiny number of nodes
  37. for (int i = 0; i < openNodes.size(); i++)
  38. { //recursively add the paths - should be max. 3 - inward path + four other directions, but only ever put max 3 in the map
  39. pathList.add(makePath(startNode, endNode, pathSoFar, closedNodes, openNodes));
  40. }
  41. int lowVal = 1024; //length of beth path from here to end
  42. int iLow = -1; //index of the best path from here to end
  43. //check all paths found just before
  44. for (int i = 0; i < pathList.size(); i++)
  45. { //if this path is smaller than the previous smallest found one, this is the new smallest found one
  46. if (pathList.get(i).size() < lowVal) { iLow = i; lowVal = pathList.get(i).size(); i = 0; }
  47. }
  48. //return the best path to proceed from this node to the end
  49. return pathList.get(iLow);
  50. }
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement