如何在不穿过障碍物的情况下检测从 A 点到 B 点的最短路径？

Question

如何在不穿过障碍物的情况下检测从 A 点到 B 点的最短路径？

Kyl*_*yle 4 javascript jquery path-finding

我一直在尝试创建一个 jQuery 代码，该代码将扫描带有 id 的 divmap及其中的.map所有内容，并在尝试避免交叉/触摸的同时找到从#Ato的最短路径，但我对如何做后者一无所知.#B#blockings

非常感谢任何帮助。

插图：

这是我的代码：

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;
}

Run Code Online (Sandbox Code Playgroud)

<!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>

Run Code Online (Sandbox Code Playgroud)

Answer 1

Nik*_* M. 5

有在网格和图形上找到最短路径的方法（https://en.wikipedia.org/wiki/Shortest_path_problem#Single-source_shortest_paths，https://en.wikipedia.org/wiki/Euclidean_shortest_path）

要使用这些，对于您的问题，您必须将空间离散为网格，并考虑障碍物位置/形状和尺寸以及物体形状/尺寸作为约束。然后你有一个图，可以使用任何最短路径图算法。

另一种方法（特别是具有用于连续空间的最短路径路由）是利用物理学来解决计算问题（见例如物理系统的硬计算问题的解决方案，使用物理直觉的例子来解决数学问题）。

在这种方法中，一个模型（或假设）物体和障碍物被磁化（或具有一种潜在的相互作用），因为目标点吸引物体而障碍物排斥物体。然后，平稳平衡解提供了物体将行进的最佳路径（在这种情况下也是最短路径）。

例如，在没有任何障碍物的情况下，物体将沿直线向目标移动（吸引它）。有障碍物，将物体从该直线转移到最佳路径以到达目标，同时避开障碍物（就像击退目标一样）。

（这种方法倾向于生成更平滑（即分析）的路线，这些路线不一定与所讨论的示例相匹配，尽管这不是必需的，并且确实可以模拟更多不连续的路线。）

这些方法的参考：

归档时间：	9 年，11 月前
查看次数：	1093 次
最近记录：	9 年，11 月前