java - Finding the path though a list of vectors -
i have list of 325 nodes on map of earth. these nodes map out planet shipping routes.
i've tasked make method can find shortest route in distance 1 node using path of nodes. needs real time , quick there possibly hundreds of boats.
i've looked a* , dijkstras solutions don't deal corner well?
i thinking using angle , distances i'm not sure how implement it.
each node on map following object in objectmap. int being node number.
the nodes , calculations done within loading of app. have of that.
the below class contained in objectmap , works nicely.
public static class node { private int nodenumber; private vector2 pos; private int connectednodes[]; private objectmap<integer, node> masterlist; private objectmap<integer, float> connectednodedistances; private objectmap<integer, float> connectednodedegrees; public node(int nodenumber, float x, float y, int connectednodes[], objectmap<integer, node> masterlist) { this.nodenumber = nodenumber; float areax = x / mapcreator.world_scale; float areay = y / mapcreator.world_scale; this.pos = new vector2(areax / mapcreator.current_down_size_x, (polyutils.getinstance().getscreenpercentagey(1f) - (areay / mapcreator.current_down_size_x)) - mapcreator.top_extra); this.connectednodes = connectednodes; this.masterlist = masterlist; this.connectednodedistances = new objectmap<integer, float>(); this.connectednodedegrees = new objectmap<integer, float>(); } public void calculatedistances() { for(int eachconnectednode : connectednodes) { float angledegree = new vector2(this.pos).sub(masterlist.get(eachconnectednode).getpos()).angle(); connectednodedistances.put(eachconnectednode, this.pos.dst(masterlist.get(eachconnectednode).getpos())); connectednodedegrees.put(eachconnectednode, angledegree); } } public int getnodenumber() { return nodenumber; } public float getdistancefromnode(int number) { return connectednodedistances.get(number); } public vector2 getpos() { return pos; } public int[] getconnectednodes() { return connectednodes; } } where i'm stuck is:
public array<node> getfastestroute(vector2 startpos, vector2 endpos, int numberofattempts) { array<array<node>> potentialroutes = new array<array<node>>(); int sizeofshortestroutenodes = 999999; for(int index = 0; index < numberofattempts; index++) { array<node> newroute = getlistofnodes(startpos, endpos, mathutils.random(-0.75f, 0.75f)); if(newroute != null) { if(newroute.size < sizeofshortestroutenodes) { potentialroutes.clear(); potentialroutes.add(newroute); sizeofshortestroutenodes = potentialroutes.size; } else if(newroute.size == sizeofshortestroutenodes) { potentialroutes.add(newroute); } } } return getshortestroutedistance(potentialroutes); } private array<node> getlistofnodes(vector2 startpos, vector2 endpos, float randomizationseed) { //todo draw lines test. array<node> nodelist = new array<node>(); array<node> deadnodes = new array<node>(); int iterations = 0; final int maxiterations = 100; //needs low boat trip isn't long helps performance. nodelist.add(getnearestnode(startpos)); node lastnode = getnearestnode(endpos); node currentnode = nodelist.first(); while(true) { float currentnodetoendangle = new vector2(new vector2(currentnode.getpos())).sub(endpos).angle(); //find closest direction node closestnodeindirection = null; float closestdirection = 361; for(int eachconnectednode : currentnode.getconnectednodes()) { node potentialnode = boatnodes.get((eachconnectednode)); if(!deadnodes.contains(potentialnode, true)) { float angletoendnodefromcurrent = (new vector2(currentnode.getpos()).sub(potentialnode.getpos()).angle()); //randomize direction seed. angletoendnodefromcurrent = angletoendnodefromcurrent * randomizationseed; float differenceindegrees = math.abs(angletoendnodefromcurrent - currentnodetoendangle); if(differenceindegrees < closestdirection) { closestdirection = differenceindegrees; closestnodeindirection = potentialnode; } } } //no new nodes. if(closestnodeindirection == null) { //go , try route. if(nodelist.size > 1) { nodelist.pop(); currentnode = nodelist.peek(); } } //adding nodes. if(closestnodeindirection != null && lastnode != closestnodeindirection) { nodelist.add(closestnodeindirection); deadnodes.add(closestnodeindirection); currentnode = closestnodeindirection; } else if(closestnodeindirection != null) { //last node reached. nodelist.add(lastnode); return nodelist; } //iterations many. iterations++; if(iterations >= maxiterations){ return null; } } } public array<node> getshortestroutedistance(array<array<node>> allnoderoutes) { array<node> shortestroute = null; float shortestroutelength = 99999f; for(int arraysindex = 0; arraysindex < allnoderoutes.size; arraysindex++) { array<node> nodearray = allnoderoutes.get(arraysindex); float lengthofthisroute = 0f; for(int nodesindex = 0; nodesindex < nodearray.size; nodesindex++) { node nextnode = null; node thisnode = nodearray.get(nodesindex); if(nodesindex + 1 < nodearray.size) { nextnode = nodearray.get(nodesindex + 1); } if(nextnode != null) { lengthofthisroute += thisnode.getdistancefromnode(nextnode.getnodenumber()); } } if(lengthofthisroute < shortestroutelength) { shortestroutelength = lengthofthisroute; shortestroute = nodearray; } } return shortestroute; }
what describing known problem a* , dijkstras --- , solution not use either of them.
what need "any-angle" algorithm --- should use algorithm called theta* instead. approach cuts near corners while avoiding obstacles.
in fact, quite similar approach came with! recommend reading excellent article here, explanation of do: theta*: any-angle path planning smoother trajectories in continuous environments
Comments
Post a Comment