Skip to content

Instantly share code, notes, and snippets.

@quangnle
Created August 31, 2023 03:48
Show Gist options
  • Save quangnle/7770b70a9a83f2ec40ce809125b71046 to your computer and use it in GitHub Desktop.
Save quangnle/7770b70a9a83f2ec40ce809125b71046 to your computer and use it in GitHub Desktop.
A* Demo for Path Finding
var AStar = function(){
this.getBestState = function(states){
var bestState = states[0];
var bestIdx = 0;
for (var i = 0; i < states.length; i++){
if (states[i].distance + states[i].estimate < bestState.distance + bestState.estimate){
bestState = states[i];
bestIdx = i;
}
}
states.splice(bestIdx, 1);
return bestState;
}
this.solve = function(start, target){
var states = [];
var used = [];
states.push(start);
start.distance = 0;
start.estimate = start.heuristicDist(target);
while (states.length > 0){
// step 1:
var checkingState = this.getBestState(states);
// step 2:
if (checkingState.heuristicDist(target) == 0) return checkingState;
// step 3:
var newStates = checkingState.getNextStates(target);
for (var i=0; i< newStates.length; i++){
states.push(newStates[i]);
}
}
return undefined;
}
}
var Board = function(width, height, cellSize){
this.width = width;
this.height = height;
this.content = [];
this.init = function(){
var blockrate = 0.2;
for (var r = 0; r < height + 2; r++) {
for (var c = 0; c < width + 2; c++){
//create new state
var rnd = Math.floor(Math.random() * 100);
var val = -1;
if ((r == 0 || r == height + 1) || (c == 0 || c == width + 1)) val = -1;
else {
if (rnd < 100 * blockrate) val = -1;
else val = 0;
}
this.content.push(new State(r, c, val, this));
}
}
}
this.getState = function(r, c){
for (var i = 0; i < this.content.length; i++){
if (this.content[i].r == r && this.content[i].c == c) return this.content[i];
}
return undefined;
}
this.draw = function(){
for (var r = 1; r < height+1; r++){
for(var c = 1; c < width+1; c++){
var state = this.getState(r, c);
if (state.val == -1) fill(0);
else fill(255);
rect(c * cellSize, r * cellSize, cellSize, cellSize);
}
}
}
}
<html>
<head>
<title></title>
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.4.0/p5.js"></script>
<script src="board.js"></script>
<script src="state.js"></script>
<script src="astar.js"></script>
<script src="sketch.js"></script>
</head>
<body>
</body>
</html>
var cellSize = 20;
var board = new Board(20,20, cellSize);
var start = undefined;
var target = undefined;
var path = undefined;
function setup(){
board.init();
createCanvas(600, 600);
redraw(false);
}
function draw(){
board.draw();
if (path != undefined){
var drawingPath = path;
fill('#0f0');
while (drawingPath != undefined){
ellipse((drawingPath.c + 1) * cellSize - 0.5 * cellSize, (drawingPath.r + 1)* cellSize - 0.5 * cellSize, cellSize * 0.2, cellSize * 0.2);
drawingPath = drawingPath.prev;
}
}
}
function mousePressed(){
var row = Math.floor(mouseY / cellSize);
var col = Math.floor(mouseX / cellSize);
if (start == undefined){
start = board.getState(row, col);
console.log('start:' + row + ' ' + col + ' ' + start.val);
}
else
{
target = board.getState(row,col);
console.log('target:' + row + ' ' + col + ' ' + target.val);
if (start.val != -1 && target.val != -1){
var astar = new AStar();
path = astar.solve(start, target);
console.log(path);
}
}
}
var State = function(r, c, val, board){
this.board = board;
this.r = r;
this.c = c;
this.val = val;
this.distance = -1;
this.estimate = -1;
this.prev = undefined;
this.heuristicDist = function(target){
return (this.r - target.r) * (this.r - target.r) + (this.c - target.c) * (this.c - target.c);
}
this.getNextStates = function(target){
var dr = [0, -1, 0, 1];
var dc = [-1, 0, 1, 0];
var newStates = [];
for (var i = 0; i < 4; i++){
var state = board.getState(this.r + dr[i], this.c + dc[i]);
if (state.val != -1) {
if (state.distance == -1) {
state.distance = this.distance + 1;
state.estimate = state.heuristicDist(target);
state.prev = this;
newStates.push(state);
}
}
}
return newStates;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment