How can I can I detect the shortest path from point A to point B without going through the obstacles?

Question

I've been trying to create a jQuery code that would scan a div with the id map and .map everything within it, and find the shortest path from #A to #B while trying to avoid crossing/touching the #blockings, but I'm clueless on how to do the latter.

Any help is profusely appreciated.

Illustration:

Here's my code:

computeTrack('#a','#b', '#map');

function computeTrack(A, B, MAP){
  
  var bag = [];
  var obstacle = [];
  
  bag = getDistance(A, B);
  obstacle = scanning(A, B, MAP);
  moveAtoB(A, B, MAP, obstacle, bag);
}

function moveAtoB(A, B, MAP, obstacle, bag){
  var clone;
  $(A).append('<div id="clone" style="position:fixed;width:5px; height:5px; background-color:#F00; top:'+$(A).position().top+'; left:'+$(A).position().left+';"></div>');
  
  clone = '#clone';
  generatePath(clone, A, B, MAP, obstacle, bag);
}

function generatePath(clone, A, B, MAP, obstacle, bag){ //Here lies the challenge
  if(bag[1] == 'top left'){    
    /*$(clone).stop().animate({
      top:$(B).offset().top,
      left:$(B).offset().left
    },Math.round(bag[0]*50),'linear');*/
  }else if(bag[1] == 'top right'){
    console.log(bag[1]);
  }else if(bag[1] == 'bottom left'){
    console.log(bag[1]);
  }else if(bag[1] == 'bottom right'){
    console.log(bag[1]);
  }
}

function collided(obj1, obj2) {
  var x1 = $(obj1).offset().left;
  var y1 = $(obj1).offset().top;
  var h1 = $(obj1).outerHeight(true);
  var w1 = $(obj1).outerWidth(true);
  var b1 = y1 + h1;
  var r1 = x1 + w1;
  var x2 = $(obj2).offset().left;
  var y2 = $(obj2).offset().top;
  var h2 = $(obj2).outerHeight(true);
  var w2 = $(obj2).outerWidth(true);
  var b2 = y2 + h2;
  var r2 = x2 + w2;
  
  if (b1 < y2 || y1 > b2 || r1 < x2 || x1 > r2) return false;
  return true;
}

function scanning(A, B, MAP){
  var allObjects = [];
  
  $(MAP+' > *').map(function(){
    if(('#'+$(this).attr('id')) !== A && ('#'+$(this).attr('id')) !== B){
      allObjects.push(('#'+$(this).attr('id')));
    }
  });
  
  return allObjects;
}

function getDistance(object, target){
  var bag = [];
  var message = '';
  var distance = 0;
  var objectPos = $(object).offset();
  var targetPos = $(target).offset();
  
  if(objectPos.top > targetPos.top){
    message += 'bottom';
  }else if(objectPos.top <= targetPos.top){
    message += 'top';
  }
  if(objectPos.left > targetPos.left){
    message += ' right';
  }else if(objectPos.left <= targetPos.left){
    message += ' left';
  }
  
  if(message == 'top left'){
    distance = Math.sqrt(((targetPos.top - objectPos.top)*(targetPos.top - objectPos.top)) + ((targetPos.left - objectPos.left)*(targetPos.left - objectPos.left)));
  }
  if(message == 'top right'){
    distance = Math.sqrt(((targetPos.top - objectPos.top)*(targetPos.top - objectPos.top)) + ((objectPos.left - targetPos.left)*(objectPos.left - targetPos.left)));
  }
  if(message == 'bottom left'){
    distance = Math.sqrt(((objectPos.top - targetPos.top)*(objectPos.top - targetPos.top)) + ((targetPos.left - objectPos.left)*(targetPos.left - objectPos.left)));
  }
  if(message == 'bottom right'){
    distance = Math.sqrt(((objectPos.top - targetPos.top)*(objectPos.top - targetPos.top)) + ((objectPos.left - targetPos.left)*(objectPos.left - targetPos.left)));
  }
  bag.push(distance, message);
  return bag;
}

<!DOCTYPE html>
<html>
  <head>
    <script type="text/javascript" src="http://code.jquery.com/jquery-latest.min.js"></script>
    <title>AtoB</title>
    <style>
      #map{
        width: 600px;
        height: 300px;
        border: 1px solid #000;
      }
      #a, #b, #blocking1, #blocking2{
        position: fixed;
      }
      #a{
        width: 1px;
        height: 1px;
        top: 50px;  
        left: 100px;
        background-color: #F00;
      }
      #b{
        width: 1px;
        height: 1px;
        top: 200px;
        left: 400px;
        background-color: #F00;
      }
      #blocking1{
        width: 100px;
        height: 100px;
        top: 150px;
        left: 250px;
        background-color: #000;
        color: #fff;
      }
      #blocking2{
        width: 50px;
        height: 50px;
        top: 50px;
        left: 275px;
        background-color: #000;
        color: #fff;
      }
    </style>
  </head>
  <body>
    <div id="map">
      <div id="a">A</div>
      <div id="b">B</div>
      <div id="blocking1">Blocking1</div>
      <div id="blocking2">Blocking2</div>
    </div>
  </body>
</html>

https://en.wikipedia.org/wiki/Shortest_path_problem#Single-source_shortest_paths — Nikos M., Dec 16 '15 at 14:16

score 5 · Accepted Answer · edited Apr 13 '17 at 12:57

There are approaches to shortest-path finding on grids and graphs (https://en.wikipedia.org/wiki/Shortest_path_problem#Single-source_shortest_paths, https://en.wikipedia.org/wiki/Euclidean_shortest_path)

To use these, for your question, you would have to discretise the space into a grid and take account of obstacle position/shape and dimensions and object shape/dimensions, as constraints. Then you have a graph and any of the shortest-path graph algorithms can be used.

Another approach (especialy for continous-space shortest-path route) is to use physics to solve a computational problem (see for example Physical systems for the solution of hard computational problems, Examples of using physical intuition to solve math problems).

In this approach, one models (or assumes) the object and obstacles are magnetised (or have a kind of potential interaction) in the sense that the target point attracts the object while the obstacles repel the object. Then, the stationary equilibrium solution provides the optimal path the object would travel (which in this case would be the shortest path as well).

For example, without any obstacles the object would travel in a straight line towards the target (attracting it). Having obstacles, diverts the object from that straight line into an optimal path to reach target while avoiding obstacles (which act like repeling targets).

(This approach tends to generate more smooth (i.e analytical) routes, which do not necessarily match the example in question, although this is not necessary and one can indeed simulate more dis-continous routes.)

References to these approaches:

Pretty concise so far, plus a lot of references, thank you so much for being helpful — Kyle, Dec 17 '15 at 16:38
welcome, hope it is useful, you can find algorithms in the references — Nikos M., Dec 17 '15 at 17:46

How can I can I detect the shortest path from point A to point B without going through the obstacles?

1 Answers1

Linked