quangnle/astar.js

## astar.js
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;
	}
}

## board.js
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);
			}
		}
	}
}

## index.html
<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>

## sketch.js
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);
		}
	}
}

## state.js
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;
	}
}
	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;
	}
	}