我如何才能在不经过障碍物的情况下检测出从A点到B点的最短路径? [英] How can I can I detect the shortest path from point A to point B without going through the obstacles?

查看：127
本文介绍了我如何才能在不经过障碍物的情况下检测出从A点到B点的最短路径?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我一直在尝试创建一个jQuery代码，该代码将扫描ID为map和.map的div，并查找从#A到#B的最短路径，同时尝试避免交叉/触摸#blockings，但是我对如何执行后者一无所知.

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.

插图:

这是我的代码 :

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>

推荐答案

有一些方法可以在网格和图形上找到最短路径(

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.)

对这些方法的引用:

  1. 单源最短路径图算法
  2. 欧几里德最短路径
  3. 用于飞机中欧几里德最短路径的最优算法
  4. 一种有效的算法，用于在飞机
  5. 得出连续空间中避免障碍的最短路径
  6. 视觉引导转向的动力学模型，避障和路线选择
  7. 解决地形导航问题的算法方法
  8. 一种用于规划无冲突路径的算法多面障碍物
  9. 解决最短路径问题:Dijkstra的算法
  10. 最短路线:自动路由选择的不同方法和实施方法的比较车辆
  1. Single-source shortest-path graph algorithms
  2. Euclidean shortest path
  3. An optimal algorithm for Euclidean shortest paths in the Plane
  4. An efficient algorithm for euclidean shortest paths among polygonal objects in the plane
  5. Deriving an Obstacle-Avoiding Shortest Path in Continuous Space
  6. A Dynamical Model of Visually-Guided Steering, Obstacle Avoidance, and Route Selection
  7. An algorithmic approach to problems in terrain navigation
  8. An Algorithm for Planning Collision-Free Paths Among Polyhedral Obstacles
  9. Solving Shortest Path Problem: Dijkstra’s Algorithm
  10. THE SHORTEST PATH: COMPARISON OF DIFFERENT APPROACHES AND IMPLEMENTATIONS FOR THE AUTOMATIC ROUTING OF VEHICLES

这篇关于我如何才能在不经过障碍物的情况下检测出从A点到B点的最短路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
前端开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆