Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ArrayList<Coordinates> makePath(Coordinates startNode, Coordinates endNode, ArrayList<Coordinates> pathSoFar, ArrayList<Coordinates> closedNodes, ArrayList<Coordinates> openNodes)
- { //recursively finds the path from startNode to endNode:
- //start @ starting node, make list of ways out of it
- //for each of these potential paths, find all the potential paths out of them
- //and so on until these paths reach the end
- //as the recursion collapses, the best paths are passed back up, and the others discarded
- //this ensures that the path returned by the last call of the method is the best one
- //this method is very, very inefficient, but is very simple
- //mainly, however, since the map has a very tiny number of potential paths, relatively speaking, the inefficiency is acceptable
- //if first call (just starting)
- if (openNodes.size() == 0 && !closedNodes.contains(startNode)) { openNodes.add(startNode); }
- int a = startNode.z; //traced NullPointerException back to here
- Coordinates n = openNodes.get(0); //get a node to test
- openNodes.remove(0); //remove it from the open nodes, so don't repeat it later
- closedNodes.add(n); //record that have done this one
- ArrayList<Coordinates> adjacent = getAdjacentCoords(n);
- //get the nodes that are adjacent to this one
- for (int i = 0; i < adjacent.size(); i++)
- {
- //if this adjacent node has not yet been checked - this prevents infinite loops
- if (!openNodes.contains(adjacent.get(i)) && !closedNodes.contains(adjacent.get(i)))
- { //add it to the list of nodes to check
- openNodes.add(adjacent.get(i));
- }
- }
- //if reached destination
- if (n.equals(endNode))
- { //done
- pathSoFar.add(n);
- return pathSoFar;
- }
- else
- {
- ArrayList<ArrayList<Coordinates>> pathList = new ArrayList<ArrayList<Coordinates>>(); //list of potential paths that come from this node + path
- // openNodes = coordOrder(openNodes, endNode); //don't need this (right now, at least), as dealing with a tiny number of nodes
- for (int i = 0; i < openNodes.size(); i++)
- { //recursively add the paths - should be max. 3 - inward path + four other directions, but only ever put max 3 in the map
- pathList.add(makePath(startNode, endNode, pathSoFar, closedNodes, openNodes));
- }
- int lowVal = 1024; //length of beth path from here to end
- int iLow = -1; //index of the best path from here to end
- //check all paths found just before
- for (int i = 0; i < pathList.size(); i++)
- { //if this path is smaller than the previous smallest found one, this is the new smallest found one
- if (pathList.get(i).size() < lowVal) { iLow = i; lowVal = pathList.get(i).size(); i = 0; }
- }
- //return the best path to proceed from this node to the end
- return pathList.get(iLow);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement