Skip to content

Instantly share code, notes, and snippets.

@riuzzang

riuzzang/.block

Last active January 29, 2023 02:05
Show Gist options
  • Save riuzzang/5660d67de605372ddbf3424eb9f1da52 to your computer and use it in GitHub Desktop.
Save riuzzang/5660d67de605372ddbf3424eb9f1da52 to your computer and use it in GitHub Desktop.
Download ZIP
Path finding by 'A Star'(A* algorithm)
Raw
.block
license: gpl-3.0
Raw
index.html
<!DOCTYPE html>
<head>
<meta charset="utf-8">
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://code.jquery.com/jquery-3.2.1.min.js"></script>
<script src="pathfinding_browser.min.js"></script>
<script src="network.js"></script>
<style>
body { margin:0;position:fixed;top:0;right:0;bottom:0;left:0; }
.ticks {
font: 10px sans-serif;
}
.track,
.track-inset,
.track-overlay {
stroke-linecap: round;
}
.track {
stroke: #000;
stroke-opacity: 0.3;
stroke-width: 10px;
}
.track-inset {
stroke: #ddd;
stroke-width: 8px;
}
.track-overlay {
pointer-events: stroke;
stroke-width: 50px;
stroke: transparent;
cursor: ew-resize;
}
.handle {
fill: #fff;
stroke: #000;
stroke-opacity: 0.5;
stroke-width: 1.25px;
}
.mesh {
fill: none;
stroke: #333;
stroke-width: .5px;
stroke-linejoin: round;
}
.play circle {
fill: white;
stroke: black;
stroke-width: 1px;
}
.play:hover path {
fill: blue;
}
.play.mousedown circle {
fill: red;
}
.play.mousedown path {
fill: white;
}
.play rect {
fill: none;
pointer-events: all;
cursor: pointer;
}
.ring {
fill: none;
stroke: red;
stroke-width: 3px;
stroke-linejoin: round;
}
</style>
</head>
<body>
<input type="hidden" class="objectPolygon" objectNo="6" polygonNo="7" x="-50" y="-50" objectType="02" points="493,32.25782012939453_493,57.257816314697266_547,57.257816314697266_547,31.75782012939453"/>
<input type="hidden" class="objectPolygon" objectno="3" polygonno="4" x="-50" y="-50" objecttype="01" points="1367.2499389648438,668.7578125_1502.375,667.7578125_1501.2499389648438,4.2578125">
<input type="hidden" class="objectPolygon" objectno="11" polygonno="12" x="-50" y="-50" objecttype="01" points="333.00000762939453,421.00781375_320.00000762939453,421.00781375_320.00000762939453,479.00781375_436,363.00781375_433,330.00781375_333.00000762939453,330.00781375">
<input type="hidden" class="objectPolygon" objectno="11" polygonno="12" x="-50" y="-50" objecttype="01" points="522.9999847412109,290.00781756469723_524.9999847412109,344.00781374999997_552.9999847412109,366.00781374999997_651.9999847412109,391.00781374999997_650.9999847412109,236.00781661102295_640.9999847412109,224.00781756469726">
<input type="hidden" class="objectPolygon" objectno="11" polygonno="12" x="-50" y="-50" objecttype="01" points="566,398.7578061206055_509.99999237060547,399.7578061206055_555,478.75779849121096_582,478.75779849121096_637,439.75779849121096_631,418.7578061206055">
<input type="hidden" class="objectPolygon" objectno="12" polygonno="13" x="-50" y="-50" objecttype="01" points="473.5,149.50000585144045_473.5,239.50000012939455_484.5,249.50000012939455_535.5,249.50000012939455_623.5,198.50000775878908_624.5,188.50000775878908_528.5,148.50000585144045">
<input type="hidden" class="objectPolygon" objectno="12" polygonno="13" x="-50" y="-50" objecttype="01" points="682.0000114440918,209.00780375_682.0000114440918,329.00780375_840.0000152587891,329.00780375_868.0000152587891,265.00780375_866.0000152587891,220.00780375_801.0000152587891,199.00780375_705.0000076293945,200.00780375">
<input type="hidden" class="objectPolygon" objectno="12" polygonno="13" x="-55.0" y="-50" objecttype="01" points="347,187.99999892060546_407,248.00000655_440,248.00000655_445,240.00000655_423,161.00000273530273_414,149.00000273530273_348,148.00000273530273">
<div id="grid"></div>
<div>
<svg id="controller" width="1000" height="50"></svg>
</div>
<script>
var networkWidth = 1000;
var networkHeight = 300;
var cellWidth = 10;
var cellHeight = 10;
var nt = new Network("grid", networkWidth+2, networkHeight+2, cellWidth, cellHeight);
//nt.loadImage(networkWidth, networkHeight, "b1.png");
nt.drawNetwork(networkWidth, networkHeight, cellWidth, cellHeight);
// 장애물
$(".objectPolygon[objectType=01]").each(function(){
var objectNo = $(this).attr("objectNo");
var polygonNo = $(this).attr("polygonNo");
var points = $(this).attr("points").replace(/_/g, ' ');
var x = $(this).attr("x");
var y = $(this).attr("y");
nt.drawObject(objectNo, polygonNo, points, x, y);
});
// 이동통로
$(".objectPolygon[objectType=02]").each(function(){
var objectNo = $(this).attr("objectNo");
var polygonNo = $(this).attr("polygonNo");
var points = $(this).attr("points").replace(/_/g, ' ');
var x = $(this).attr("x");
var y = $(this).attr("y");
nt.drawExit(objectNo, polygonNo, points, x, y);
});
var exits = nt.intersectObject();
var normalWalkers = nt.createWalkers(20, 'normal');
nt.ready(normalWalkers, exits);
</script>
</body>
Raw
network.js
var Network = function(networkDivId, networkWidth, networkHeight, cellWidth, cellHeight){
this.networkWidth = networkWidth - 2;
this.networkHeight = networkHeight - 2;
this.cellWidth = cellWidth;
this.cellHeight = cellHeight;
this.walkPathList = [];
d3.select("#" + networkDivId)
.append("svg")
.attr("id", "network")
.attr("width",networkWidth)
.attr("height",networkHeight);
};
Network.prototype.loadImage = function(width, height, imagePath){
d3.select("#network").append("image")
.attr("xlink:href", imagePath);
};
Network.prototype.getNetwork = function(networkWidth, networkHeight, cellWidth, cellHeight){
var data = new Array();
var xpos = 1;
var ypos = 1;
// iterate for rows
for (var row = 0; row < networkHeight / cellHeight; row++) {
data.push( new Array() );
// iterate for cells/columns inside rows
for (var column = 0; column < networkWidth / cellWidth; column++) {
data[row].push({
x: xpos,
y: ypos,
width: cellWidth,
height: cellHeight,
row : row,
column : column
})
// increment the x position. I.e. move it over by 50 (width variable)
xpos += cellWidth;
}
// reset the x position after a row is complete
xpos = 1;
// increment the y position for the next row. Move it down 50 (height variable)
ypos += cellHeight;
}
return data;
};
Network.prototype.drawNetwork = function(networkWidth, networkHeight, cellWidth, cellHeight){
var gridData = this.getNetwork(networkWidth, networkHeight, cellWidth, cellHeight);
var row = d3.select("#network").selectAll(".row")
.data(gridData)
.enter().append("g")
.attr("class", "row");
var column = row.selectAll(".square")
.data(function(d) { return d; })
.enter().append("rect")
.attr("class","square")
.attr("x", function(d) { return d.x; })
.attr("y", function(d) { return d.y; })
.attr("width", function(d) { return d.width; })
.attr("height", function(d) { return d.height; })
.attr("row", function(d) { return d.row; })
.attr("column", function(d) { return d.column; })
.attr("centerX", function(d) { // 셀의 중심점 X
var x = ((d.width * d.column) + (d.width * (d.column + 1))) / 2;
return x;
})
.attr("centerY", function(d) { // 셀의 중심점 Y
var y = ((d.height * d.row) + (d.height * (d.row + 1))) / 2;
return y;
})
.style("fill", "white")
.style("opacity", 1)
.style("stroke", "#222");
};
Network.prototype.drawObject = function(objectNo, polygonNo, points, x, y) {
var polygon = d3.select("#network").append('polygon')
.attr('class', 'objects')
.attr('points', points)
.attr('objectNo', objectNo)
.attr('polygonNo', polygonNo)
.attr('objectType', '01')
.attr('x', x)
.attr('y', y)
.attr("transform", function(){
return "translate(" + x + "," + y + ")";
})
.attr("walkerable", "false")
.style("fill", "black")
.style("opacity", "0.3");
};
Network.prototype.intersectObject = function(){
var exits = [];
d3.select("#network").selectAll(".objects").each(function(){
var object = d3.select(this);
var objectType = object.attr("objectType");
var points = object.attr("points").split(" ");
var x = object.attr("x");
var y = object.attr("y");
var polygon = [];
for(var i=0; i<points.length; i++){
var p = points[i].split(",");
polygon.push([Number(p[0]), Number(p[1])]);
}
d3.select("#network").selectAll(".square").each(function(){
var square = d3.select(this).node();
var self = d3.select(this);
var column = d3.select(this).attr("column");
var row = d3.select(this).attr("row");
var left = square.getBoundingClientRect().left + 50;
var right = square.getBoundingClientRect().right + 50;
var top = square.getBoundingClientRect().top + 50;
var bottom = square.getBoundingClientRect().bottom + 50;
var vertexList = [];
vertexList.push([left, top]);
vertexList.push([right, top]);
vertexList.push([right, bottom]);
vertexList.push([left, bottom]);
for(var i=0; i<vertexList.length; i++){
var vertex = vertexList[i];
var contain = d3.polygonContains(polygon, [vertex[0], vertex[1]]);
if(contain){
if(objectType == '01'){
self.style("fill","green")
.style("opacity", 0)
.attr("walkerable", "false");
}else{
self.style("fill","blue")
.style("opacity", 0)
.attr("walkerable", "true")
.attr("exit", "true")
.attr("row", row)
.attr("column", column);
exits.push([Number(row), Number(column)]);
}
break;
}
}
});
});
return exits;
};
//출구 Drawing
Network.prototype.drawExit = function(objectNo, polygonNo, points, x, y) {
var polygon = d3.select("#network").append('polygon')
.attr('class', 'objects')
.attr('points', points)
.attr('objectNo', objectNo)
.attr('polygonNo', polygonNo)
.attr('objectType', '02')
.attr('x', x)
.attr('y', y)
.attr("transform", function(){
return "translate(" + x + "," + y + ")";
})
.attr("walkerable", "true")
.attr("exit", "true")
.style("fill","red")
.style("opacity", .5);
};
// 보행자 생성
Network.prototype.createWalkers = function(walkerCnt, walkerType) {
// 중복된 위치 여부
function hasWalker(walkers, x, y){
var has = false;
for(var z=0; z<walkers.length; z++){
if(walkers[z][0] == x && walkers[z][1] == y){
has = true;
break;
}
}
return has;
};
// 장애물(객체) 위치 여부
function isBlock(x, y){
var block = false;
d3.select("#network").selectAll(".square[walkerable='false']").each(function(){
var row = d3.select(this).attr("row");
var column = d3.select(this).attr("column");
if(column == x && row == y){
block = true;
return false;
}
});
d3.select("#network").selectAll(".square[exit='true']").each(function(){
var row = d3.select(this).attr("row");
var column = d3.select(this).attr("column");
if(column == x && row == y){
block = true;
return false;
}
});
return block;
};
var walkers = [];
for(var i=0; i<walkerCnt; i++){
var x = Math.floor(Math.random() * networkWidth/cellWidth);
var y = Math.floor(Math.random() * networkHeight/cellHeight);
var has = hasWalker(walkers, x, y);
var block = isBlock(x, y);
while(has || block){
x = Math.floor(Math.random() * networkWidth/cellWidth);
y = Math.floor(Math.random() * networkHeight/cellHeight);
has = hasWalker(walkers, x, y);
block = isBlock(x, y);
}
var walker = [x,y,walkerType];
walkers.push(walker);
}
return walkers;
};
// 시뮬레이션 시작
Network.prototype.ready = function(walkers, exits) {
var network = this.getCurrentNetworkData();
var column = Math.ceil(this.networkWidth / this.cellWidth);
var row = Math.ceil(this.networkHeight / this.cellHeight);
var finder = new PF.AStarFinder({
allowDiagonal: true
, dontCrossCorners: true
});
var maxLength = 0;
for(var i=0; i<walkers.length; i++){
var startColumn = walkers[i][0];
var startRow = walkers[i][1];
var walkerType = walkers[i][2];
var pathList = [];
for(var j=0; j<exits.length; j++){
var endColumn = exits[j][1];
var endRow = exits[j][0];
var grid = new PF.Grid(column, row, network);
var path = finder.findPath(startColumn, startRow, endColumn, endRow, grid);
pathList.push(path);
}
var shortest = pathList[0];
for(var k=1; k<pathList.length; k++){
if(pathList[k].length < shortest.length){
shortest = pathList[k];
}
}
if(shortest == null){
continue;
}
if(maxLength < shortest.length){
maxLength = shortest.length;
}
var walkPath = this.getWalkerablePath(shortest);
var walker = this.drawWalker(walkPath, i, walkerType);
var linePath = this.drawWalkPathLine(walkPath, i);
var p = linePath.node().getPointAtLength(0);
walker.attr("transform", "translate(" + p.x + "," + p.y + ")");
walker.attr("walkPath", walkPath);
walker.attr("sourcePath", shortest);
walker.attr("linePath", linePath);
this.walkPathList.push({
"walker" : walker
, "shortest" : shortest
, "linePath" : linePath
});
}
this.drawController(maxLength, this.walkPathList);
/*
for(var i=0; i<this.walkPathList.length; i++){
this.playWalker(this.walkPathList[i].walker, this.walkPathList[i].shortest, this.walkPathList[i].linePath);
}
*/
};
//현재 네트워크 데이터 조회
Network.prototype.getCurrentNetworkData = function(){
var data = [];
var selector = ".row";
d3.select("#network").selectAll(selector)
.each(function(d,i){
var rowData = [];
var column = d3.select(this).selectAll(".square")
.each(function(d,j){
rowData.push(d3.select(this).attr("walkerable") == "false" ? 1 : 0);
});
data.push(rowData);
});
return data;
};
// 보행자 Drawing
Network.prototype.drawWalker = function(sourcePath, index, walkerType){
var walkerGroup = d3.select("#network").append("g")
.attr("class", "walker")
.attr("currentT", 0)
.attr("lastT", 0)
.attr("id", "walker"+index)
.attr("idx", index)
.attr("speed", function(d){
return walkerType == 'normal' ? 500 : 2000;
});
var walker = walkerGroup.append("circle")
.attr("r", 5)
.attr("stroke", "steelblue")
.attr("stroke-width", 1)
.attr("fill", "none");
var arc = d3.symbol().type(d3.symbolTriangle);
walkerGroup.append("path")
.attr("d", arc)
.attr("fill", "steelblue")
.attr("transform", "scale(0.75)");
return walkerGroup;
};
//네트워크 데이터 조회
Network.prototype.getWalkerablePath = function(path){
var data = [];
var walkPath = [];
var selector = ".row";
for(var z=0; z<path.length; z++){
d3.select("#network").selectAll(selector)
.each(function(d,i){
var rowData = [];
var column = d3.select(this).selectAll(".square")
.each(function(dd,j){
// 알고리즘에서 계산된 경로에 해당하는 셀 추가
if(path[z][0] == d3.select(this).attr("column") && path[z][1] == d3.select(this).attr("row")){
walkPath.push(d3.select(this));
}
});
data.push(rowData);
});
}
return walkPath;
};
// 보행 경로 Drawing
Network.prototype.drawWalkPathLine = function(walkPath, idx){
var lineData = [];
for(var i=0; i<walkPath.length; i++){
var x = walkPath[i].attr("centerX");
var y = walkPath[i].attr("centerY");
lineData.push({ "x": x, "y": y});
}
var lineFunction = d3.line()
.x(function(d) { return d.x; })
.y(function(d) { return d.y; })
//.curve(d3.curveNatural);
//.curve(d3.curveCardinal);
.curve(d3.curveBasis);
var linePath = d3.select("#network").append("path")
.attr("id", "path" + idx)
.attr("d", lineFunction(lineData))
.attr("stroke", "purple")
.attr("stroke-width", .5)
//.attr("display", "none")
.attr("fill", "none");
return linePath;
};
// 보행 경로 Drawing
Network.prototype.drawWalkPathLine2 = function(walkPath, idx){
d3.select("#network").select("path[id='path" + idx + "']").remove();
var lineData = [];
for(var i=0; i<walkPath.length-1; i++){
var x = ((this.cellWidth * walkPath[i][0]) + (this.cellWidth * (walkPath[i][0] + 1))) / 2;
var y = ((this.cellHeight * walkPath[i][1]) + (this.cellHeight * (walkPath[i][1] + 1))) / 2;
lineData.push({ "x": x, "y": y});
}
var lineFunction = d3.line()
.x(function(d) { return d.x; })
.y(function(d) { return d.y; })
//.curve(d3.curveNatural);
//.curve(d3.curveCardinal);
//.curve(d3.curveLinear);
.curve(d3.curveBasis);
var linePath = d3.select("#network").append("path")
.attr("id", "path" + idx)
.attr("d", lineFunction(lineData))
.attr("stroke", "purple")
.attr("stroke-width", .5)
//.attr("display", "none")
.attr("fill", "none");
return linePath;
};
// 보행
Network.prototype.playWalker = function(walker, sourcePath, linePath){
var self = this;
d3.select("#network").selectAll(".walker")
.style("visibility", "visible");
function transition(){
var duration = sourcePath.length * walker.attr("speed");
var lastT = walker.attr("lastT");
var t = d3.transition()
.ease(d3.easeLinear)
.duration(duration - (duration * lastT))
.on("start", function(d){
d3.selectAll("path").style("display", "block");
});
walker.transition(t)
.attrTween("transform", translateAlong(linePath.node()))
.attr("node", linePath.node())
.on("end", function(d){
d3.select(this).remove();
});
var totalLength = linePath.node().getTotalLength();
linePath
.transition(t)
.attrTween("stroke-dasharray",function(){
return d3.interpolateString("0," + totalLength, totalLength + "," + totalLength);
});
}
transition();
function translateAlong(path) {
var l = path.getTotalLength();
return function(d, i, a) {
return function(t) {
t += walker.attr("lastT");
var p = path.getPointAtLength(t * l);
walker.attr("currentT", t);
if(collide(walker)){
walker.select('path').style("fill", "red");
}else{
walker.select('path').style("fill", "steelblue");
}
var pos = t * l;
function pointAtLength(l) {
var xy = path.getPointAtLength(l);
return [xy.x, xy.y];
}
// Approximate tangent
function angleAtLength(l) {
var a = pointAtLength(Math.max(l - 0.01,0)), // this could be slightly negative
b = pointAtLength(l + 0.01); // browsers cap at total length
return Math.atan2(b[1] - a[1], b[0] - a[0]) * 180 / Math.PI;
}
return "translate(" + p.x + "," + p.y + ") rotate( " + (angleAtLength(pos) - 25) + ")";
};
};
}
// 충돌 여부
function collide(node){
var nodeId = node.attr("id");
var t = node.attr("transform");
var trans = t.substring(t.indexOf("(")+1, t.indexOf(")")).split(",");
var x1 = Number(trans[0]),
x2 = Number(trans[0]) + Number(node.select('circle').attr("r")),
y1 = Number(trans[1]),
y2 = Number(trans[1]) + Number(node.select('circle').attr("r"));
var colliding = false;
d3.select("#network").selectAll(".walker:not(#" + nodeId + ")").each(function(d,i){
var t = d3.select(this).attr("transform");
var ntrans = t.substring(t.indexOf("(")+1, t.indexOf(")")).split(",");
var nx1 = Number(ntrans[0]),
nx2 = Number(ntrans[0]) + Number(d3.select(this).attr("r")),
ny1 = Number(ntrans[1]),
ny2 = Number(ntrans[1]) + Number(d3.select(this).attr("r"));
if(!(x1 >= nx2 || x2 <= nx1 || y1 >= ny2 || y2 <= ny1)){
colliding = true;
return;
}
});
return colliding;
}
};
Network.prototype.drawController = function(maxLength){
var self = this;
d3.select("#controller").selectAll("*").remove();
var svg = d3.select("#controller"),
margin = {right: 30, left: 30},
width =+ svg.attr("width") - margin.left - margin.right - 40,
height =+ svg.attr("height");
var play = svg.append("g")
.attr("class", "play")
.attr("id", "player")
.attr("maxLength", maxLength);
play.append("circle")
.attr("r", 15)
.attr("transform", "translate(" + margin.left + "," + height / 2 + ")");
play.append("path")
.attr("d", "M-22,-30l60,30l-60,30z")
.attr("transform", "translate(" + margin.left + "," + height / 2 + ") scale(.2)");
play.append("rect")
.attr("width", 60)
.attr("height", height)
.on("click", function() {
self.play();
});
var x = d3.scaleLinear()
.domain([0, maxLength])
.range([0, width])
.clamp(true);
var slider = svg.append("g")
.attr("class", "slider")
.attr("transform", "translate(" + (margin.left + 40) + "," + height / 2 + ")");
slider.append("line")
.attr("class", "track")
.attr("x1", x.range()[0])
.attr("x2", x.range()[1])
.select(function() {
return this.parentNode.appendChild(this.cloneNode(true));
})
.attr("class", "track-inset")
.select(function() {
return this.parentNode.appendChild(this.cloneNode(true));
})
.attr("class", "track-overlay")
.call(
d3.drag().on("start.interrupt", function() {
slider.interrupt();
})
.on("start drag", function() {
self.seeking(x.invert(d3.event.x), x, maxLength);
})
);
// 눈금 단위 표시
slider.insert("g", ".track-overlay")
.attr("class", "ticks")
.attr("transform", "translate(0, 18)")
.selectAll("text")
.data(x.ticks(maxLength))
.enter()
.append("text")
.attr("x", x)
.attr("text-anchor", "middle")
.text(function(d) {
if(d == 0){
return "Start"
}else if(d == maxLength){
return "Finish"
}else{
return d % 2 == 1 ? d + "'" : "";
}
});
// 눈금바 표시
slider.insert("g", ".track-overlay")
.attr("class", "ticks-bar")
.attr("transform", "translate(0, -8)")
.selectAll("line")
.data(x.ticks(maxLength))
.enter()
.append("line")
.attr("x1", x)
.attr("y1", 0)
.attr("x2", x)
.attr("y2", 15)
.attr("stroke-width", function(d){
if(d == 0){
return 0
}else if(d == maxLength){
return 0
}else{
return 0.5;
}
})
.attr("stroke", "gray");
var handle = slider.insert("circle", ".track-overlay")
.attr("class", "handle")
.attr("r", 9);
};
// 시뮬레이션 seeking
Network.prototype.seeking = function(sliderCurrentT, x, sliderMaxLength) {
var handle = d3.select("#controller").select(".handle");
handle.attr("cx", x(sliderCurrentT));
for(var i=0; i<this.walkPathList.length; i++){
var walker = this.walkPathList[i].walker;
var sourcePath = this.walkPathList[i].shortest;
var linePath = this.walkPathList[i].linePath;
var speed = walker.attr("speed");
if(sourcePath.length == 0){ // 왜 생길까
continue;
}
var walkerCurrentT = sliderCurrentT / sourcePath.length;
walker.transition()
.ease(d3.easeLinear)
.duration(function(d){
return sourcePath.length * walker.attr("speed");
})
.attrTween("transform", translateAlong(linePath.node(), walkerCurrentT))
.attr("node", linePath.node());
//.on("end", function(d){
// d3.select(this).style("visibility", "hidden");
//});
function translateAlong(path, time) {
var l = path.getTotalLength();
return function(d, i, a) {
return function(t) {
var p = path.getPointAtLength(time * l);
/*
if(collide(walker)){
walker.style("fill", "red");
}else{
walker.style("fill", "steelblue");
}
*/
var pos = time * l;
function pointAtLength(l) {
var xy = path.getPointAtLength(l);
return [xy.x, xy.y];
}
// Approximate tangent
function angleAtLength(l) {
var a = pointAtLength(Math.max(l - 0.01,0)), // this could be slightly negative
b = pointAtLength(l + 0.01); // browsers cap at total length
return Math.atan2(b[1] - a[1], b[0] - a[0]) * 180 / Math.PI;
}
return "translate(" + p.x + "," + p.y + ") rotate( " + (angleAtLength(pos) - 25) + ")";
};
};
}
}
};
Network.prototype.play = function(){
var self = this;
var maxLength = d3.select("#controller").select("#player").attr("maxLength");
var x = d3.scaleLinear()
.domain([0, maxLength])
.range([0, 900]) // <svg id="controller" width="1000" height="50"></svg>
.clamp(true);
d3.select("#controller").select(".slider").transition()
.ease(d3.easeLinear)
.duration(maxLength * 1000)
.tween("seeking", function() {
var i = d3.interpolate(0, maxLength);
return function(t) {
self.seeking(i(t), x, maxLength);
};
});
/*
for(var i=0; i<this.walkPathList.length; i++){
this.playWalker(this.walkPathList[i].walker, this.walkPathList[i].shortest, this.walkPathList[i].linePath);
}
*/
};
Raw
pathfinding_browser.min.js
!function(t){if("object"==typeof exports&&"undefined"!=typeof module)module.exports=t();else if("function"==typeof define&&define.amd)define([],t);else{var e;"undefined"!=typeof window?e=window:"undefined"!=typeof global?e=global:"undefined"!=typeof self&&(e=self),e.PF=t()}}(function(){return function t(e,r,i){function n(s,a){if(!r[s]){if(!e[s]){var u="function"==typeof require&&require;if(!a&&u)return u(s,!0);if(o)return o(s,!0);var h=new Error("Cannot find module '"+s+"'");throw h.code="MODULE_NOT_FOUND",h}var l=r[s]={exports:{}};e[s][0].call(l.exports,function(t){var r=e[s][1][t];return n(r?r:t)},l,l.exports,t,e,r,i)}return r[s].exports}for(var o="function"==typeof require&&require,s=0;s<i.length;s++)n(i[s]);return n}({1:[function(t,e){e.exports=t("./lib/heap")},{"./lib/heap":2}],2:[function(t,e){!function(){var t,r,i,n,o,s,a,u,h,l,p,c,f,d,g;i=Math.floor,l=Math.min,r=function(t,e){return e>t?-1:t>e?1:0},h=function(t,e,n,o,s){var a;if(null==n&&(n=0),null==s&&(s=r),0>n)throw new Error("lo must be non-negative");for(null==o&&(o=t.length);o>n;)a=i((n+o)/2),s(e,t[a])<0?o=a:n=a+1;return[].splice.apply(t,[n,n-n].concat(e)),e},s=function(t,e,i){return null==i&&(i=r),t.push(e),d(t,0,t.length-1,i)},o=function(t,e){var i,n;return null==e&&(e=r),i=t.pop(),t.length?(n=t[0],t[0]=i,g(t,0,e)):n=i,n},u=function(t,e,i){var n;return null==i&&(i=r),n=t[0],t[0]=e,g(t,0,i),n},a=function(t,e,i){var n;return null==i&&(i=r),t.length&&i(t[0],e)<0&&(n=[t[0],e],e=n[0],t[0]=n[1],g(t,0,i)),e},n=function(t,e){var n,o,s,a,u,h;for(null==e&&(e=r),a=function(){h=[];for(var e=0,r=i(t.length/2);r>=0?r>e:e>r;r>=0?e++:e--)h.push(e);return h}.apply(this).reverse(),u=[],o=0,s=a.length;s>o;o++)n=a[o],u.push(g(t,n,e));return u},f=function(t,e,i){var n;return null==i&&(i=r),n=t.indexOf(e),-1!==n?(d(t,0,n,i),g(t,n,i)):void 0},p=function(t,e,i){var o,s,u,h,l;if(null==i&&(i=r),s=t.slice(0,e),!s.length)return s;for(n(s,i),l=t.slice(e),u=0,h=l.length;h>u;u++)o=l[u],a(s,o,i);return s.sort(i).reverse()},c=function(t,e,i){var s,a,u,p,c,f,d,g,y,b;if(null==i&&(i=r),10*e<=t.length){if(p=t.slice(0,e).sort(i),!p.length)return p;for(u=p[p.length-1],g=t.slice(e),c=0,d=g.length;d>c;c++)s=g[c],i(s,u)<0&&(h(p,s,0,null,i),p.pop(),u=p[p.length-1]);return p}for(n(t,i),b=[],a=f=0,y=l(e,t.length);y>=0?y>f:f>y;a=y>=0?++f:--f)b.push(o(t,i));return b},d=function(t,e,i,n){var o,s,a;for(null==n&&(n=r),o=t[i];i>e&&(a=i-1>>1,s=t[a],n(o,s)<0);)t[i]=s,i=a;return t[i]=o},g=function(t,e,i){var n,o,s,a,u;for(null==i&&(i=r),o=t.length,u=e,s=t[e],n=2*e+1;o>n;)a=n+1,o>a&&!(i(t[n],t[a])<0)&&(n=a),t[e]=t[n],e=n,n=2*e+1;return t[e]=s,d(t,u,e,i)},t=function(){function t(t){this.cmp=null!=t?t:r,this.nodes=[]}return t.push=s,t.pop=o,t.replace=u,t.pushpop=a,t.heapify=n,t.nlargest=p,t.nsmallest=c,t.prototype.push=function(t){return s(this.nodes,t,this.cmp)},t.prototype.pop=function(){return o(this.nodes,this.cmp)},t.prototype.peek=function(){return this.nodes[0]},t.prototype.contains=function(t){return-1!==this.nodes.indexOf(t)},t.prototype.replace=function(t){return u(this.nodes,t,this.cmp)},t.prototype.pushpop=function(t){return a(this.nodes,t,this.cmp)},t.prototype.heapify=function(){return n(this.nodes,this.cmp)},t.prototype.updateItem=function(t){return f(this.nodes,t,this.cmp)},t.prototype.clear=function(){return this.nodes=[]},t.prototype.empty=function(){return 0===this.nodes.length},t.prototype.size=function(){return this.nodes.length},t.prototype.clone=function(){var e;return e=new t,e.nodes=this.nodes.slice(0),e},t.prototype.toArray=function(){return this.nodes.slice(0)},t.prototype.insert=t.prototype.push,t.prototype.remove=t.prototype.pop,t.prototype.top=t.prototype.peek,t.prototype.front=t.prototype.peek,t.prototype.has=t.prototype.contains,t.prototype.copy=t.prototype.clone,t}(),("undefined"!=typeof e&&null!==e?e.exports:void 0)?e.exports=t:window.Heap=t}.call(this)},{}],3:[function(t,e){function r(t,e,r){this.width=t,this.height=e,this.nodes=this._buildNodes(t,e,r)}var i=t("./Node");r.prototype._buildNodes=function(t,e,r){var n,o,s=new Array(e);for(n=0;e>n;++n)for(s[n]=new Array(t),o=0;t>o;++o)s[n][o]=new i(o,n);if(void 0===r)return s;if(r.length!==e||r[0].length!==t)throw new Error("Matrix size does not fit");for(n=0;e>n;++n)for(o=0;t>o;++o)r[n][o]&&(s[n][o].walkable=!1);return s},r.prototype.getNodeAt=function(t,e){return this.nodes[e][t]},r.prototype.isWalkableAt=function(t,e){return this.isInside(t,e)&&this.nodes[e][t].walkable},r.prototype.isInside=function(t,e){return t>=0&&t<this.width&&e>=0&&e<this.height},r.prototype.setWalkableAt=function(t,e,r){this.nodes[e][t].walkable=r},r.prototype.getNeighbors=function(t,e,r){var i=t.x,n=t.y,o=[],s=!1,a=!1,u=!1,h=!1,l=!1,p=!1,c=!1,f=!1,d=this.nodes;return this.isWalkableAt(i,n-1)&&(o.push(d[n-1][i]),s=!0),this.isWalkableAt(i+1,n)&&(o.push(d[n][i+1]),u=!0),this.isWalkableAt(i,n+1)&&(o.push(d[n+1][i]),l=!0),this.isWalkableAt(i-1,n)&&(o.push(d[n][i-1]),c=!0),e?(r?(a=c&&s,h=s&&u,p=u&&l,f=l&&c):(a=c||s,h=s||u,p=u||l,f=l||c),a&&this.isWalkableAt(i-1,n-1)&&o.push(d[n-1][i-1]),h&&this.isWalkableAt(i+1,n-1)&&o.push(d[n-1][i+1]),p&&this.isWalkableAt(i+1,n+1)&&o.push(d[n+1][i+1]),f&&this.isWalkableAt(i-1,n+1)&&o.push(d[n+1][i-1]),o):o},r.prototype.clone=function(){var t,e,n=this.width,o=this.height,s=this.nodes,a=new r(n,o),u=new Array(o);for(t=0;o>t;++t)for(u[t]=new Array(n),e=0;n>e;++e)u[t][e]=new i(e,t,s[t][e].walkable);return a.nodes=u,a},e.exports=r},{"./Node":5}],4:[function(t,e){e.exports={manhattan:function(t,e){return t+e},euclidean:function(t,e){return Math.sqrt(t*t+e*e)},octile:function(t,e){var r=Math.SQRT2-1;return e>t?r*t+e:r*e+t},chebyshev:function(t,e){return Math.max(t,e)}}},{}],5:[function(t,e){function r(t,e,r){this.x=t,this.y=e,this.walkable=void 0===r?!0:r}e.exports=r},{}],6:[function(t,e,r){function i(t){for(var e=[[t.x,t.y]];t.parent;)t=t.parent,e.push([t.x,t.y]);return e.reverse()}function n(t,e){var r=i(t),n=i(e);return r.concat(n.reverse())}function o(t){var e,r,i,n,o,s=0;for(e=1;e<t.length;++e)r=t[e-1],i=t[e],n=r[0]-i[0],o=r[1]-i[1],s+=Math.sqrt(n*n+o*o);return s}function s(t,e,r,i){var n,o,s,a,u,h,l=Math.abs,p=[];for(s=l(r-t),a=l(i-e),n=r>t?1:-1,o=i>e?1:-1,u=s-a;;){if(p.push([t,e]),t===r&&e===i)break;h=2*u,h>-a&&(u-=a,t+=n),s>h&&(u+=s,e+=o)}return p}function a(t){var e,r,i,n,o,a,u=[],h=t.length;if(2>h)return u;for(o=0;h-1>o;++o)for(e=t[o],r=t[o+1],i=s(e[0],e[1],r[0],r[1]),n=i.length,a=0;n-1>a;++a)u.push(i[a]);return u.push(t[h-1]),u}function u(t,e){var r,i,n,o,a,u,h,l,p,c,f,d,g,y=e.length,b=e[0][0],A=e[0][1],k=e[y-1][0],m=e[y-1][1];for(r=b,i=A,a=e[1][0],u=e[1][1],h=[[r,i]],l=2;y>l;++l){for(c=e[l],n=c[0],o=c[1],f=s(r,i,n,o),g=!1,p=1;p<f.length;++p)if(d=f[p],!t.isWalkableAt(d[0],d[1])){g=!0,h.push([a,u]),r=a,i=u;break}g||(a=n,u=o)}return h.push([k,m]),h}function h(t){if(t.length<3)return t;var e,r,i,n,o,s,a=[],u=t[0][0],h=t[0][1],l=t[1][0],p=t[1][1],c=l-u,f=p-h;for(o=Math.sqrt(c*c+f*f),c/=o,f/=o,a.push([u,h]),s=2;s<t.length;s++)e=l,r=p,i=c,n=f,l=t[s][0],p=t[s][1],c=l-e,f=p-r,o=Math.sqrt(c*c+f*f),c/=o,f/=o,(c!==i||f!==n)&&a.push([e,r]);return a.push([l,p]),a}r.backtrace=i,r.biBacktrace=n,r.pathLength=o,r.interpolate=s,r.expandPath=a,r.smoothenPath=u,r.compressPath=h},{}],7:[function(t,e){function r(t){t=t||{},this.allowDiagonal=t.allowDiagonal,this.dontCrossCorners=t.dontCrossCorners,this.heuristic=t.heuristic||o.manhattan,this.weight=t.weight||1}var i=t("heap"),n=t("../core/Util"),o=t("../core/Heuristic");r.prototype.findPath=function(t,e,r,o,s){var a,u,h,l,p,c,f,d,g=new i(function(t,e){return t.f-e.f}),y=s.getNodeAt(t,e),b=s.getNodeAt(r,o),A=this.heuristic,k=this.allowDiagonal,m=this.dontCrossCorners,v=this.weight,w=Math.abs,x=Math.SQRT2;for(y.g=0,y.f=0,g.push(y),y.opened=!0;!g.empty();){if(a=g.pop(),a.closed=!0,a===b)return n.backtrace(b);for(u=s.getNeighbors(a,k,m),l=0,p=u.length;p>l;++l)h=u[l],h.closed||(c=h.x,f=h.y,d=a.g+(0===c-a.x||0===f-a.y?1:x),(!h.opened||d<h.g)&&(h.g=d,h.h=h.h||v*A(w(c-r),w(f-o)),h.f=h.g+h.h,h.parent=a,h.opened?g.updateItem(h):(g.push(h),h.opened=!0)))}return[]},e.exports=r},{"../core/Heuristic":4,"../core/Util":6,heap:1}],8:[function(t,e){function r(t){i.call(this,t);var e=this.heuristic;this.heuristic=function(t,r){return 1e6*e(t,r)}}var i=t("./AStarFinder");r.prototype=new i,r.prototype.constructor=r,e.exports=r},{"./AStarFinder":7}],9:[function(t,e){function r(t){t=t||{},this.allowDiagonal=t.allowDiagonal,this.dontCrossCorners=t.dontCrossCorners,this.heuristic=t.heuristic||o.manhattan,this.weight=t.weight||1}var i=t("heap"),n=t("../core/Util"),o=t("../core/Heuristic");r.prototype.findPath=function(t,e,r,o,s){var a,u,h,l,p,c,f,d,g=function(t,e){return t.f-e.f},y=new i(g),b=new i(g),A=s.getNodeAt(t,e),k=s.getNodeAt(r,o),m=this.heuristic,v=this.allowDiagonal,w=this.dontCrossCorners,x=this.weight,F=Math.abs,W=Math.SQRT2,N=1,C=2;for(A.g=0,A.f=0,y.push(A),A.opened=N,k.g=0,k.f=0,b.push(k),k.opened=C;!y.empty()&&!b.empty();){for(a=y.pop(),a.closed=!0,u=s.getNeighbors(a,v,w),l=0,p=u.length;p>l;++l)if(h=u[l],!h.closed){if(h.opened===C)return n.biBacktrace(a,h);c=h.x,f=h.y,d=a.g+(0===c-a.x||0===f-a.y?1:W),(!h.opened||d<h.g)&&(h.g=d,h.h=h.h||x*m(F(c-r),F(f-o)),h.f=h.g+h.h,h.parent=a,h.opened?y.updateItem(h):(y.push(h),h.opened=N))}for(a=b.pop(),a.closed=!0,u=s.getNeighbors(a,v,w),l=0,p=u.length;p>l;++l)if(h=u[l],!h.closed){if(h.opened===N)return n.biBacktrace(h,a);c=h.x,f=h.y,d=a.g+(0===c-a.x||0===f-a.y?1:W),(!h.opened||d<h.g)&&(h.g=d,h.h=h.h||x*m(F(c-t),F(f-e)),h.f=h.g+h.h,h.parent=a,h.opened?b.updateItem(h):(b.push(h),h.opened=C))}}return[]},e.exports=r},{"../core/Heuristic":4,"../core/Util":6,heap:1}],10:[function(t,e){function r(t){i.call(this,t);var e=this.heuristic;this.heuristic=function(t,r){return 1e6*e(t,r)}}var i=t("./BiAStarFinder");r.prototype=new i,r.prototype.constructor=r,e.exports=r},{"./BiAStarFinder":9}],11:[function(t,e){function r(t){t=t||{},this.allowDiagonal=t.allowDiagonal,this.dontCrossCorners=t.dontCrossCorners}var i=t("../core/Util");r.prototype.findPath=function(t,e,r,n,o){var s,a,u,h,l,p=o.getNodeAt(t,e),c=o.getNodeAt(r,n),f=[],d=[],g=this.allowDiagonal,y=this.dontCrossCorners,b=0,A=1;for(f.push(p),p.opened=!0,p.by=b,d.push(c),c.opened=!0,c.by=A;f.length&&d.length;){for(u=f.shift(),u.closed=!0,s=o.getNeighbors(u,g,y),h=0,l=s.length;l>h;++h)if(a=s[h],!a.closed)if(a.opened){if(a.by===A)return i.biBacktrace(u,a)}else f.push(a),a.parent=u,a.opened=!0,a.by=b;for(u=d.shift(),u.closed=!0,s=o.getNeighbors(u,g,y),h=0,l=s.length;l>h;++h)if(a=s[h],!a.closed)if(a.opened){if(a.by===b)return i.biBacktrace(a,u)}else d.push(a),a.parent=u,a.opened=!0,a.by=A}return[]},e.exports=r},{"../core/Util":6}],12:[function(t,e){function r(t){i.call(this,t),this.heuristic=function(){return 0}}var i=t("./BiAStarFinder");r.prototype=new i,r.prototype.constructor=r,e.exports=r},{"./BiAStarFinder":9}],13:[function(t,e){function r(t){t=t||{},this.allowDiagonal=t.allowDiagonal,this.dontCrossCorners=t.dontCrossCorners}var i=t("../core/Util");r.prototype.findPath=function(t,e,r,n,o){var s,a,u,h,l,p=[],c=this.allowDiagonal,f=this.dontCrossCorners,d=o.getNodeAt(t,e),g=o.getNodeAt(r,n);for(p.push(d),d.opened=!0;p.length;){if(u=p.shift(),u.closed=!0,u===g)return i.backtrace(g);for(s=o.getNeighbors(u,c,f),h=0,l=s.length;l>h;++h)a=s[h],a.closed||a.opened||(p.push(a),a.opened=!0,a.parent=u)}return[]},e.exports=r},{"../core/Util":6}],14:[function(t,e){function r(t){i.call(this,t),this.heuristic=function(){return 0}}var i=t("./AStarFinder");r.prototype=new i,r.prototype.constructor=r,e.exports=r},{"./AStarFinder":7}],15:[function(t,e){function r(t){t=t||{},this.allowDiagonal=t.allowDiagonal,this.dontCrossCorners=t.dontCrossCorners,this.heuristic=t.heuristic||i.manhattan,this.weight=t.weight||1,this.trackRecursion=t.trackRecursion||!1,this.timeLimit=t.timeLimit||1/0}t("../core/Util");var i=t("../core/Heuristic"),n=t("../core/Node");r.prototype.findPath=function(t,e,r,i,o){var s,a,u,h=0,l=(new Date).getTime(),p=function(t,e){return this.heuristic(Math.abs(e.x-t.x),Math.abs(e.y-t.y))}.bind(this),c=function(t,e){return t.x===e.x||t.y===e.y?1:Math.SQRT2},f=function(t,e,r,i,s){if(h++,this.timeLimit>0&&(new Date).getTime()-l>1e3*this.timeLimit)return 1/0;var a=e+p(t,g)*this.weight;if(a>r)return a;if(t==g)return i[s]=[t.x,t.y],t;var u,d,y,b,A=o.getNeighbors(t,this.allowDiagonal,this.dontCrossCorners);for(y=0,u=1/0;b=A[y];++y){if(this.trackRecursion&&(b.retainCount=b.retainCount+1||1,b.tested!==!0&&(b.tested=!0)),d=f(b,e+c(t,b),r,i,s+1),d instanceof n)return i[s]=[t.x,t.y],d;this.trackRecursion&&0===--b.retainCount&&(b.tested=!1),u>d&&(u=d)}return u}.bind(this),d=o.getNodeAt(t,e),g=o.getNodeAt(r,i),y=p(d,g);for(s=0;!0;++s){if(a=[],u=f(d,0,y,a,0),1/0===u)return[];if(u instanceof n)return a;y=u}return[]},e.exports=r},{"../core/Heuristic":4,"../core/Node":5,"../core/Util":6}],16:[function(t,e){function r(t){t=t||{},this.heuristic=t.heuristic||o.manhattan,this.trackJumpRecursion=t.trackJumpRecursion||!1}var i=t("heap"),n=t("../core/Util"),o=t("../core/Heuristic");r.prototype.findPath=function(t,e,r,o,s){var a,u=this.openList=new i(function(t,e){return t.f-e.f}),h=this.startNode=s.getNodeAt(t,e),l=this.endNode=s.getNodeAt(r,o);for(this.grid=s,h.g=0,h.f=0,u.push(h),h.opened=!0;!u.empty();){if(a=u.pop(),a.closed=!0,a===l)return n.expandPath(n.backtrace(l));this._identifySuccessors(a)}return[]},r.prototype._identifySuccessors=function(t){var e,r,i,n,s,a,u,h,l,p,c=this.grid,f=this.heuristic,d=this.openList,g=this.endNode.x,y=this.endNode.y,b=t.x,A=t.y,k=Math.abs;for(Math.max,e=this._findNeighbors(t),n=0,s=e.length;s>n;++n)if(r=e[n],i=this._jump(r[0],r[1],b,A)){if(a=i[0],u=i[1],p=c.getNodeAt(a,u),p.closed)continue;h=o.octile(k(a-b),k(u-A)),l=t.g+h,(!p.opened||l<p.g)&&(p.g=l,p.h=p.h||f(k(a-g),k(u-y)),p.f=p.g+p.h,p.parent=t,p.opened?d.updateItem(p):(d.push(p),p.opened=!0))}},r.prototype._jump=function(t,e,r,i){var n=this.grid,o=t-r,s=e-i;if(!n.isWalkableAt(t,e))return null;if(this.trackJumpRecursion===!0&&(n.getNodeAt(t,e).tested=!0),n.getNodeAt(t,e)===this.endNode)return[t,e];if(0!==o&&0!==s){if(n.isWalkableAt(t-o,e+s)&&!n.isWalkableAt(t-o,e)||n.isWalkableAt(t+o,e-s)&&!n.isWalkableAt(t,e-s))return[t,e]}else if(0!==o){if(n.isWalkableAt(t+o,e+1)&&!n.isWalkableAt(t,e+1)||n.isWalkableAt(t+o,e-1)&&!n.isWalkableAt(t,e-1))return[t,e]}else if(n.isWalkableAt(t+1,e+s)&&!n.isWalkableAt(t+1,e)||n.isWalkableAt(t-1,e+s)&&!n.isWalkableAt(t-1,e))return[t,e];return 0!==o&&0!==s&&(this._jump(t+o,e,t,e)||this._jump(t,e+s,t,e))?[t,e]:n.isWalkableAt(t+o,e)||n.isWalkableAt(t,e+s)?this._jump(t+o,e+s,t,e):null},r.prototype._findNeighbors=function(t){var e,r,i,n,o,s,a,u,h=t.parent,l=t.x,p=t.y,c=this.grid,f=[];if(h)e=h.x,r=h.y,i=(l-e)/Math.max(Math.abs(l-e),1),n=(p-r)/Math.max(Math.abs(p-r),1),0!==i&&0!==n?(c.isWalkableAt(l,p+n)&&f.push([l,p+n]),c.isWalkableAt(l+i,p)&&f.push([l+i,p]),(c.isWalkableAt(l,p+n)||c.isWalkableAt(l+i,p))&&f.push([l+i,p+n]),!c.isWalkableAt(l-i,p)&&c.isWalkableAt(l,p+n)&&f.push([l-i,p+n]),!c.isWalkableAt(l,p-n)&&c.isWalkableAt(l+i,p)&&f.push([l+i,p-n])):0===i?c.isWalkableAt(l,p+n)&&(f.push([l,p+n]),c.isWalkableAt(l+1,p)||f.push([l+1,p+n]),c.isWalkableAt(l-1,p)||f.push([l-1,p+n])):c.isWalkableAt(l+i,p)&&(f.push([l+i,p]),c.isWalkableAt(l,p+1)||f.push([l+i,p+1]),c.isWalkableAt(l,p-1)||f.push([l+i,p-1]));else for(o=c.getNeighbors(t,!0),a=0,u=o.length;u>a;++a)s=o[a],f.push([s.x,s.y]);return f},e.exports=r},{"../core/Heuristic":4,"../core/Util":6,heap:1}],17:[function(t,e){function r(t){n.call(this,t),t=t||{},this.heuristic=t.heuristic||i.manhattan}var i=t("../core/Heuristic"),n=t("./JumpPointFinder");r.prototype=new n,r.prototype.constructor=r,r.prototype._jump=function(t,e,r,i){var n=this.grid,o=t-r,s=e-i;if(!n.isWalkableAt(t,e))return null;if(this.trackJumpRecursion===!0&&(n.getNodeAt(t,e).tested=!0),n.getNodeAt(t,e)===this.endNode)return[t,e];if(0!==o){if(n.isWalkableAt(t,e-1)&&!n.isWalkableAt(t-o,e-1)||n.isWalkableAt(t,e+1)&&!n.isWalkableAt(t-o,e+1))return[t,e]}else{if(0===s)throw new Error("Only horizontal and vertical movements are allowed");if(n.isWalkableAt(t-1,e)&&!n.isWalkableAt(t-1,e-s)||n.isWalkableAt(t+1,e)&&!n.isWalkableAt(t+1,e-s))return[t,e];if(this._jump(t+1,e,t,e)||this._jump(t-1,e,t,e))return[t,e]}return this._jump(t+o,e+s,t,e)},r.prototype._findNeighbors=function(t){var e,r,i,n,o,s,a,u,h=t.parent,l=t.x,p=t.y,c=this.grid,f=[];if(h)e=h.x,r=h.y,i=(l-e)/Math.max(Math.abs(l-e),1),n=(p-r)/Math.max(Math.abs(p-r),1),0!==i?(c.isWalkableAt(l,p-1)&&f.push([l,p-1]),c.isWalkableAt(l,p+1)&&f.push([l,p+1]),c.isWalkableAt(l+i,p)&&f.push([l+i,p])):0!==n&&(c.isWalkableAt(l-1,p)&&f.push([l-1,p]),c.isWalkableAt(l+1,p)&&f.push([l+1,p]),c.isWalkableAt(l,p+n)&&f.push([l,p+n]));else for(o=c.getNeighbors(t,!1),a=0,u=o.length;u>a;++a)s=o[a],f.push([s.x,s.y]);return f},e.exports=r},{"../core/Heuristic":4,"./JumpPointFinder":16}],18:[function(t,e){function r(t){t=t||{},this.allowDiagonal=t.allowDiagonal,this.dontCrossCorners=t.dontCrossCorners,this.heuristic=t.heuristic||o.manhattan}var i=t("heap"),n=t("../core/Util"),o=t("../core/Heuristic");r.prototype.findPath=function(t,e,r,o,s){var a,u,h,l,p,c,f,d,g=new i(function(t,e){return t.f-e.f}),y=s.getNodeAt(t,e),b=s.getNodeAt(r,o),A=this.heuristic,k=this.allowDiagonal,m=this.dontCrossCorners,v=Math.abs,w=Math.SQRT2;for(y.g=0,y.f=0,g.push(y),y.opened=!0;!g.empty();){if(a=g.pop(),a.closed=!0,a===b)return n.backtrace(b);u=s.getNeighbors(a,k,m);var x=u.length;for(l=0,p=u.length;p>l;++l)h=u[l],h.closed||(c=h.x,f=h.y,d=a.g+(0===c-a.x||0===f-a.y?1:w),(!h.opened||d<h.g)&&(h.g=d*x/9,h.h=h.h||A(v(c-r),v(f-o)),h.f=h.g+h.h,h.parent=a,h.opened?g.updateItem(h):(g.push(h),h.opened=!0)))}return[]},e.exports=r},{"../core/Heuristic":4,"../core/Util":6,heap:1}],19:[function(t,e){e.exports={Heap:t("heap"),Node:t("./core/Node"),Grid:t("./core/Grid"),Util:t("./core/Util"),Heuristic:t("./core/Heuristic"),AStarFinder:t("./finders/AStarFinder"),BestFirstFinder:t("./finders/BestFirstFinder"),BreadthFirstFinder:t("./finders/BreadthFirstFinder"),DijkstraFinder:t("./finders/DijkstraFinder"),BiAStarFinder:t("./finders/BiAStarFinder"),BiBestFirstFinder:t("./finders/BiBestFirstFinder"),BiBreadthFirstFinder:t("./finders/BiBreadthFirstFinder"),BiDijkstraFinder:t("./finders/BiDijkstraFinder"),IDAStarFinder:t("./finders/IDAStarFinder"),JumpPointFinder:t("./finders/JumpPointFinder"),OrthogonalJumpPointFinder:t("./finders/OrthogonalJumpPointFinder"),TraceFinder:t("./finders/TraceFinder")}},{"./core/Grid":3,"./core/Heuristic":4,"./core/Node":5,"./core/Util":6,"./finders/AStarFinder":7,"./finders/BestFirstFinder":8,"./finders/BiAStarFinder":9,"./finders/BiBestFirstFinder":10,"./finders/BiBreadthFirstFinder":11,"./finders/BiDijkstraFinder":12,"./finders/BreadthFirstFinder":13,"./finders/DijkstraFinder":14,"./finders/IDAStarFinder":15,"./finders/JumpPointFinder":16,"./finders/OrthogonalJumpPointFinder":17,"./finders/TraceFinder":18,heap:1}]},{},[19])(19)});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment