我一直在尝试创建一个 jQuery 代码，它会扫描一个带有 id map 和 .map 的 div，并找到从 #A 到 #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;
}<!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 ， https://en.wikipedia.org/wiki/Euclidean_shortest_path )
要使用这些，对于您的问题，您必须将空间离散为网格，并考虑障碍物位置/形状和尺寸以及物体形状/尺寸作为约束。然后你有一个图，可以使用任何最短路径图算法。
另一种方法(特别是对于连续空间最短路径路线)是使用物理学来解决计算问题(参见例如 Physical systems for the solution of hard computational problems 、 Examples of using physical intuition to solve math problems )。
在这种方法中，在 目标点吸引 对象而 障碍物排斥 对象的意义上，一个模型(或假设)对象和障碍物被磁化(或具有一种潜在的相互作用)。然后，平稳平衡解提供了物体将行进的最佳路径(在这种情况下也是最短路径)。
例如，在没有任何障碍物的情况下，物体将沿直线向目标移动(吸引它)。有障碍物，将物体从该直线转移到最佳路径以到达目标，同时避开障碍物(就像击退目标一样)。
(这种方法往往会生成更平滑(即分析)的路线，这些路线不一定与所讨论的示例相匹配，尽管这不是必需的，并且确实可以模拟更多不连续的路线。)
这些方法的引用:
关于javascript - 如何在不穿过障碍物的情况下检测从 A 点到 B 点的最短路径？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34313843/