I have a routing algorithm that works by iterating through chunks of a dataset.
First it finds the first chunk (an array containing multiple arrays of coordinates each making up lines) containing an inner array with the closest point to start, then it searches in that inner array for the closest point to destination, then using the indexes of both found points it extracts coords in that array from indexA to indexB and adds them to the route. Then it sets start to IndexB and repeats the whole thing again until IndexB equals the destination. It's painfully slow, it would take about 35 minutes to calculate a route from London to Glasgow which is not ideal. I iterate using OnUpdate to avoid triggering the watchdog.
I believe the amount of time it takes to generate the route is not necessarilly the size of the data itself as I use the same data to draw a background map and this runs well considering the amount of coordinates to process, it's not instant but for drawing over 10,000 points, a couple of seconds isn't bad. I believe the problem lies in that I iterate through the data over and over including those i've iterated through before, it's esssentially down to a lack of efficiency. I've provided the code here:
function GenerateRoute() {
if (MapArr != null) {
if (RoutePick != Map.size()){
//go through all arrays to find the closest point to start
var array = MapArr[add];
for (var j = 0; j < array.size(); j+=2) {
var CurrentX = array[j];
var CurrentY = array[j+1];
var package = [startLat,startLon,CurrentX,CurrentY];
var distance = distance(package);
hasit = route.indexOf(CurrentX);
hasit2 = route.indexOf(CurrentY);
if (distance < minDistanceToStart && CurrentX != startLon && CurrentY != startLat && hasit == -1 && hasit2 == -1) {
currentArr = array;
minDistanceToStart = distance;
c2SIndex = j;
}
}
if (add == (MapArr.size() - 1)){
if (RoutePick != (Map.size() - 1)){
add = 0;
RoutePick = RoutePick + 1;
//go through the current array to find the closest point to destination
WatchUi.requestUpdate();}
else if (RoutePick == (Map.size() - 1)){
for (var k=0; k<currentArr.size(); k+=2) {
var CurrentX = currentArr[k];
var CurrentY = currentArr[k+1];
var package = [destLat,destLon,CurrentX,CurrentY];
var distance = distance(package);
hasit = route.indexOf(CurrentX);
hasit2 = route.indexOf(CurrentY);
if (distance < minDistanceToDest && hasit == -1) {
closestToDestX = CurrentX;
closestToDestY = CurrentY;
minDistanceToDest = distance;
c2DIndex = k;
}
}
//reverse array if start index is greater than destination index
router = [];
if (c2SIndex > c2DIndex) {
for (var l = c2SIndex; l > c2DIndex; l-=2){
router.addAll([currentArr[l],currentArr[l+1]]);
}
//System.println(router);
//System.println(c2DIndex + "," + c2SIndex + "reverse");
}
// Add the points to the route array.
else if (c2SIndex < c2DIndex){
for (var l = c2SIndex; l < c2DIndex; l+=2) {
router.addAll([currentArr[l],currentArr[l+1]]);
}
//System.println(c2DIndex + "," + c2SIndex + "Don't reverse");
}
else if (c2SIndex == c2DIndex){
router.addAll([currentArr[c2SIndex],currentArr[c2SIndex + 1]]);
}
hasit = route.indexOf(router);
if (router.size() > 0 && hasit == -1){
route.addAll(router);}
router = null;
if (closestToDestX == destLon && closestToDestY == destLat || route[0] == destLat && route[1] == destLon){
RoutePick = Map.size();
System.println("route finished");
route.add(destLon);
route.add(destLat);
generateRoute = null;
NumPick = 0;
var m = Position.getInfo().position;
m = m.toDegrees();
startLat = m[0];
startLon = m[1];
MapviewerView.GenerateBitmap();
}
else {
add = 0;
RoutePick = 0;
startLat = closestToDestY;
startLon = closestToDestX;
minDistanceToDest = 2147483647;
minDistanceToStart = 2147483647;
WatchUi.requestUpdate();
}
}
}
else if (add < (MapArr.size() - 1)) {
add = add + 1;
WatchUi.requestUpdate();
}
}
}
}
I've tried looking at other algorithms but I am unsure how to implement them that doesn't use up too much memory as some of them require storing cost and what not.
I'd appreciate some guidance on how/where to modify my code to make it generate a route faster. Thanks