Created
March 1, 2012 10:58
-
-
Save anonymous/1949089 to your computer and use it in GitHub Desktop.
A* path finding algorithm for impactjs game engine with debug
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* AStar Debug | |
* | |
* Created by Andreas Giemza on 2012-03-01. | |
* Copyright (c) 2011 Andreas Giemza. All rights reserved. | |
* | |
*/ | |
ig.module( | |
'plugins.a-star-debug' | |
) | |
.requires( | |
'impact.debug.menu', | |
'impact.game' | |
) | |
.defines(function(){ | |
ig.Game.inject({ | |
draw: function() { | |
// Draw all entities and backgroundMaps | |
this.parent(); | |
if (ig.Game.AStarDebug) { | |
this.astar.draw(); | |
} | |
} | |
}); | |
ig.Game.AStarDebug = false; | |
ig.debug.addPanel({ | |
type: ig.DebugPanel, | |
name: 'AStarTrap', | |
label: 'A*', | |
// Toggle switches for this panel | |
options: [ | |
{ | |
name: 'Show path', | |
// When the toggle switch is clicked, it will flip the property | |
// value for the given object. | |
// In this case 'ig.CollisionMap._enabled' | |
object: ig.Game, | |
property: 'AStarDebug' | |
} | |
] | |
}); | |
}); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* AStar | |
* | |
* Extended by Andreas Giemza on 2012-03-01. | |
* | |
* Created by Paul Armstrong on 2011-05-26. | |
* Copyright (c) 2011 Paul Armstrong Designs. All rights reserved. | |
* | |
* Based on: https://gist.github.com/827899 | |
*/ | |
ig.module('plugins.a-star') | |
.requires( | |
'impact.game' | |
) | |
.defines(function () { | |
PathFinderNode = function(pos, parent) { | |
var tileSize = ig.game.collisionMap.tilesize; | |
this.x = Math.floor(pos.x); | |
this.y = Math.floor(pos.y); | |
this.parent = parent; | |
this.g = -1; | |
this.h = -1; | |
this.f = -1; | |
this.hash = this.x + ',' + this.y; | |
this.closed = false; | |
}; | |
PathMapNode = function(x, y, v) { | |
this.x = x; | |
this.y = y; | |
this.v = v; | |
}; | |
PathFinder = ig.Class.extend({ | |
start: null, | |
end: null, | |
board: null, | |
columns: null, | |
rows: null, | |
bestway: null, | |
init: function(settings) { | |
this.columns = ig.game.collisionMap.width; | |
this.rows = ig.game.collisionMap.height; | |
this.tilesize = ig.game.collisionMap.tilesize; | |
this.updateBoard(); | |
// for (var i = 0; i < this.board.length; i++) { | |
// console.log(this.board[i]); | |
// } | |
ig.merge(this, settings); | |
}, | |
updateBoard: function() { | |
this.board = ig.game.collisionMap.data; | |
}, | |
getPath: function(startEnt, endEnt) { | |
this.start = new PathFinderNode({ | |
x: (startEnt.pos.x / this.tilesize), | |
y: (startEnt.pos.y / this.tilesize) | |
}, -1); | |
this.end = new PathFinderNode({ | |
x: ((endEnt.pos.x + endEnt.size.x / 2) / this.tilesize), | |
y: ((endEnt.pos.y + endEnt.size.y / 2) / this.tilesize) | |
}, -1); | |
var nodes = {}, | |
//Map of nodes hashed by node.hash | |
open = [], | |
//List of open nodes (nodes to be inspected) | |
closed = [], | |
//List of closed nodes (nodes we've already inspected) | |
g = 0, | |
//Cost from start to current node | |
h = this.getHeuristic(this.start, this.end), | |
//Cost from current node to destination | |
f = g + h, | |
//Cost from start to destination going through the current node | |
bestCost, bestNode, currentNode, nNodes, nNode, exNode, isEnd, fOpen, path, fPath = [], | |
q; | |
//Push the start node onto the list of open nodes | |
open.push(this.start); | |
nodes[this.start.hash] = this.start; | |
nodes[this.end.hash] = this.end; | |
//Keep going while there's nodes in our open list | |
while (open.length > 0) { | |
//Find the best open node (lowest f value) | |
//Alternately, you could simply keep the open list sorted by f value lowest to highest, | |
//in which case you always use the first node | |
bestCost = open[0].f; | |
bestNode = 0; | |
q = 1; | |
for (q; q < open.length; q++) { | |
if (open[q].f < bestCost) { | |
bestCost = open[q].f; | |
bestNode = q; | |
} | |
} | |
currentNode = open[bestNode]; | |
//Check if we've reached our destination | |
if (currentNode.x === this.end.x && currentNode.y === this.end.y) { | |
path = [this.end]; //Initialize the path with the destination node | |
//Go up the chain to recreate the path | |
while (currentNode.parent !== -1) { | |
currentNode = closed[currentNode.parent]; | |
path.unshift(currentNode); | |
} | |
q = path.length; | |
while (q--) { | |
fPath.unshift({ | |
x: path[q].x * this.tilesize, | |
y: path[q].y * this.tilesize | |
}); | |
} | |
this.bestway = fPath; | |
return; | |
} | |
//Remove the current node from our open list | |
open.splice(bestNode, 1); | |
//Push it onto the closed list | |
closed.push(currentNode); | |
currentNode.closed = true; | |
//Expand our current node (look in all 8 directions) | |
nNodes = this.getNodeNeighbors(currentNode); | |
q = 0; | |
for (q; q < nNodes.length; q++) { | |
nNode = nNodes[q]; | |
isEnd = (this.end.x === nNode.x && this.end.y === nNode.y); | |
if (this.board[nNode.y][nNode.x] === 0 || isEnd) //or the new node is our destination | |
{ | |
// Do we already know about this node? | |
fClose = false; | |
exNode = nodes[nNode.hash]; | |
if (exNode) { | |
if (exNode.closed) { | |
continue; | |
} else { | |
// normally we would say this: fClose = true; | |
// but the destination is never in either list | |
fClose = !isEnd; | |
} | |
} | |
//If the node is in our open list, use it. Also use it if it is the destination (which is never in either list) | |
if (!fClose || isEnd) { | |
ig.merge(nNode, { | |
parent: closed.length - 1, | |
g: currentNode.g + this.getHeuristic(currentNode, nNode), | |
h: this.getHeuristic(nNode, this.end) | |
}); | |
nNode.f = nNode.g + nNode.h; | |
open.push(nNode); | |
nodes[nNode.hash] = nNode; | |
} | |
} | |
} | |
} | |
this.bestway = []; | |
}, | |
getNodeNeighbors: function(node) { | |
var nodes = [], | |
x = Math.max(0, node.x - 1), | |
xMax = Math.min(this.columns - 1, node.x + 1), | |
y, yMax = Math.min(this.rows - 1, node.y + 1); | |
for (x; x <= xMax; x++) { | |
y = Math.max(0, node.y - 1); | |
for (y; y <= yMax; y++) { | |
nodes.push(new PathFinderNode({ | |
x: x, | |
y: y | |
}, -1)); | |
} | |
} | |
return nodes; | |
}, | |
getHeuristic: function(start, end) { | |
var x = start.x - end.x, | |
y = start.y - end.y; | |
// stepped route | |
return Math.sqrt(x * x + y * y); | |
// most direct route | |
// return (x * x) + (y * y); | |
}, | |
draw: function() { | |
if (this.bestway) { | |
ig.system.context.strokeStyle = 'rgba(255,0,0,0.5)'; | |
ig.system.context.lineWidth = 4.0; | |
ig.system.context.beginPath(); | |
ig.system.context.moveTo( | |
ig.system.getDrawPos(this.bestway[0].x + ig.game.collisionMap.tilesize / 2 - ig.game.screen.x), ig.system.getDrawPos(this.bestway[0].y + ig.game.collisionMap.tilesize / 2 - ig.game.screen.y)); | |
for (var i = 1; i < this.bestway.length; i++) { | |
ig.system.context.lineTo( | |
ig.system.getDrawPos(this.bestway[i].x + ig.game.collisionMap.tilesize / 2 - ig.game.screen.x), ig.system.getDrawPos(this.bestway[i].y + ig.game.collisionMap.tilesize / 2 - ig.game.screen.y)); | |
} | |
ig.system.context.stroke(); | |
ig.system.context.closePath(); | |
} | |
} | |
}); | |
ig.Game.inject({ | |
loadLevel: function(level) { | |
this.parent(level); | |
this.astar = new PathFinder(); | |
} | |
}); | |
}); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment