You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
321 lines
8.4 KiB
321 lines
8.4 KiB
class Algorithm{
|
|
|
|
constructor(){
|
|
this.startNode = game.startNode;
|
|
this.targetNode = game.targetNode;
|
|
|
|
this.grid = game.grid;
|
|
|
|
this.startDate = new Date();
|
|
this.timeDiff = 0;
|
|
}
|
|
|
|
get running(){
|
|
return !this.hasSucceeded && !this.hasFailed;
|
|
}
|
|
|
|
display(){
|
|
push();
|
|
scale(1 / this.grid.nodeSize.x, 1 / this.grid.nodeSize.y);
|
|
fill(0);
|
|
textSize(20);
|
|
textAlign(CENTER, TOP);
|
|
text('Time: ' + this.timeDiff / 1000 + 's', this.grid.size / 2, -this.grid.nodeSize.y / 2 - 50);
|
|
pop();
|
|
}
|
|
|
|
update(){
|
|
this.timeDiff = new Date().getTime() - this.startDate.getTime();
|
|
}
|
|
|
|
success(){
|
|
console.log('Success!');
|
|
this.hasSucceeded = true;
|
|
}
|
|
|
|
failed(){
|
|
console.log('Failed!');
|
|
this.hasFailed = true;
|
|
}
|
|
|
|
}
|
|
|
|
function startAlgorithm(){
|
|
switch ($('#algorithm_type').val()){
|
|
case 'astar':
|
|
game.start(new AStar());
|
|
break;
|
|
case 'dijkstra':
|
|
game.start(new Dijkstra());
|
|
break;
|
|
case 'dstar':
|
|
game.start(new DStar());
|
|
break;
|
|
}
|
|
}
|
|
|
|
|
|
class DStar extends Algorithm{
|
|
|
|
constructor() {
|
|
super();
|
|
|
|
this.openList = []
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
class AStar extends Algorithm{
|
|
|
|
constructor(){
|
|
super();
|
|
|
|
this.startNode.f = 0;
|
|
this.startNode.g = 0;
|
|
|
|
this.openList = [this.startNode];
|
|
this.closedList = [];
|
|
}
|
|
|
|
get minFNodeIndex(){
|
|
let f = this.openList[0].f, index = 0;
|
|
this.openList.forEach((n, i) => {
|
|
if (n.f < f){
|
|
f = n.f;
|
|
index = i;
|
|
}
|
|
});
|
|
return index;
|
|
}
|
|
|
|
update(){
|
|
if (!this.running){
|
|
return;
|
|
}
|
|
|
|
super.update();
|
|
|
|
if (!this.openList.length){
|
|
this.failed();
|
|
} else {
|
|
let index = this.minFNodeIndex;
|
|
let currentNode = this.openList[index];
|
|
this.openList.splice(index, 1);
|
|
|
|
if (currentNode === this.targetNode){
|
|
this.success();
|
|
} else {
|
|
this.closedList.push(currentNode);
|
|
|
|
currentNode.successors.forEach(successor => {
|
|
|
|
if (this.closedList.find(n => n === successor)){
|
|
return;
|
|
}
|
|
|
|
let provisionalG = currentNode.g + currentNode.pos.dist(successor.pos);
|
|
if (this.openList.find(n => n === successor) && provisionalG >= successor.g){
|
|
return;
|
|
}
|
|
|
|
successor.predecessor = currentNode
|
|
successor.g = provisionalG;
|
|
|
|
successor.f = provisionalG + successor.distanceToTarget;
|
|
if (!this.openList.find(n => n === successor)){
|
|
this.openList.push(successor);
|
|
}
|
|
});
|
|
}
|
|
}
|
|
}
|
|
|
|
display(appearance, isInformationVisible, pathSmoothness){
|
|
super.display();
|
|
|
|
if (isInformationVisible){
|
|
|
|
if (appearance === 'Circles'){
|
|
let r = 0.5;
|
|
|
|
fill(200);
|
|
this.openList.forEach(n => {
|
|
ellipse(n.pos.x, n.pos.y, r * 2);
|
|
});
|
|
|
|
fill(100);
|
|
this.closedList.forEach(n => {
|
|
if (n === this.startNode)
|
|
return;
|
|
ellipse(n.pos.x, n.pos.y, r * 2);
|
|
});
|
|
}
|
|
|
|
if (appearance === 'Rectangles'){
|
|
fill(200);
|
|
this.openList.forEach(n => {
|
|
rect(n.pos.x - 0.5, n.pos.y - 0.5, 1, 1);
|
|
});
|
|
|
|
fill(100);
|
|
this.closedList.forEach(n => {
|
|
if (n === this.startNode)
|
|
return;
|
|
rect(n.pos.x - 0.5, n.pos.y - 0.5, 1, 1);
|
|
});
|
|
}
|
|
}
|
|
|
|
|
|
noFill();
|
|
stroke(50, 255, 50);
|
|
strokeWeight(0.2);
|
|
|
|
let node;
|
|
if (!this.openList.length){
|
|
node = this.closedList[this.closedList.length - 1];
|
|
} else {
|
|
node = this.openList[this.minFNodeIndex];
|
|
}
|
|
if (this.hasSucceeded){
|
|
node = this.targetNode;
|
|
}
|
|
if (node){
|
|
|
|
if (pathSmoothness){
|
|
beginShape();
|
|
vertex(node.pos.x, node.pos.y);
|
|
while (node.predecessor){
|
|
node = node.predecessor;
|
|
|
|
if (!node.predecessor){
|
|
quadraticVertex(node.pos.x, node.pos.y, node.pos.x, node.pos.y);
|
|
endShape();
|
|
} else {
|
|
let cx = (node.pos.x + node.predecessor.pos.x) / 2;
|
|
let cy = (node.pos.y + node.predecessor.pos.y) / 2;
|
|
quadraticVertex(node.pos.x, node.pos.y, cx, cy);
|
|
}
|
|
}
|
|
|
|
} else {
|
|
while (node.predecessor){
|
|
line(node.pos.x, node.pos.y, node.predecessor.pos.x, node.predecessor.pos.y);
|
|
node = node.predecessor;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
}
|
|
|
|
class Dijkstra extends Algorithm{
|
|
|
|
constructor(){
|
|
super();
|
|
|
|
this.nodes = this.grid.allowedNodes.slice();
|
|
this.nodes.forEach(n => n.distance = Infinity);
|
|
this.startNode.distance = 0;
|
|
}
|
|
|
|
get minDistanceNodeIndex(){
|
|
let index = 0, distance = this.nodes[0].distance;
|
|
this.nodes.forEach((n, i) => {
|
|
if (n.distance < distance){
|
|
index = i;
|
|
distance = n.distance;
|
|
}
|
|
});
|
|
return index;
|
|
}
|
|
|
|
update(){
|
|
if (!this.running){
|
|
return;
|
|
}
|
|
super.update();
|
|
|
|
let index = this.minDistanceNodeIndex;
|
|
let currentNode = this.nodes[index];
|
|
|
|
this.nodes.splice(index, 1);
|
|
|
|
if (currentNode === this.targetNode){
|
|
this.success();
|
|
}
|
|
|
|
currentNode.successors.forEach(s => {
|
|
if (this.nodes.find(n => n === s)){
|
|
let alternativeDistance = currentNode.distance + currentNode.pos.dist(s.pos);
|
|
if (alternativeDistance < s.distance){
|
|
s.distance = alternativeDistance;
|
|
s.predecessor = currentNode;
|
|
}
|
|
}
|
|
})
|
|
}
|
|
|
|
display(appearance, isInformationVisible, pathSmoothness){
|
|
super.display();
|
|
|
|
if (isInformationVisible){
|
|
if (appearance === 'Circles'){
|
|
let r = 0.5;
|
|
fill(100);
|
|
this.nodes.forEach(n => {
|
|
if (n === this.startNode || n === this.targetNode)
|
|
return;
|
|
ellipse(n.pos.x, n.pos.y, r * 2);
|
|
});
|
|
}
|
|
|
|
if (appearance === 'Rectangles'){
|
|
fill(100);
|
|
this.nodes.forEach(n => {
|
|
if (n === this.startNode || n === this.targetNode)
|
|
return;
|
|
rect(n.pos.x - 0.5, n.pos.y - 0.5, 1, 1);
|
|
});
|
|
}
|
|
}
|
|
|
|
|
|
noFill();
|
|
stroke(50, 255, 50);
|
|
strokeWeight(0.2);
|
|
|
|
let node = this.nodes[this.minDistanceNodeIndex];
|
|
if (this.hasSucceeded){
|
|
node = this.targetNode;
|
|
}
|
|
if (node){
|
|
|
|
if (pathSmoothness){
|
|
beginShape();
|
|
vertex(node.pos.x, node.pos.y);
|
|
while (node.predecessor){
|
|
node = node.predecessor;
|
|
|
|
if (!node.predecessor){
|
|
quadraticVertex(node.pos.x, node.pos.y, node.pos.x, node.pos.y);
|
|
endShape();
|
|
} else {
|
|
let cx = (node.pos.x + node.predecessor.pos.x) / 2;
|
|
let cy = (node.pos.y + node.predecessor.pos.y) / 2;
|
|
quadraticVertex(node.pos.x, node.pos.y, cx, cy);
|
|
}
|
|
}
|
|
|
|
} else {
|
|
while (node.predecessor){
|
|
line(node.pos.x, node.pos.y, node.predecessor.pos.x, node.predecessor.pos.y);
|
|
node = node.predecessor;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
} |