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:
			used.push(checkingState);
			var newStates = checkingState.getNextStates(target);

			//check if newstate is existed
			for (var i=0; i < newStates.length; i++){
				var isNew = true;
				for (var j=0; j < states.length; j++){
					if (newStates[i].val == states[j].val){
						isNew = false;
						continue;
					}
				}

				if (isNew) {
					for (var j=0; j < used.length; j++){
						if (newStates[i].val == used[j].val){
							isNew = false;
							continue;
						}
					}
				}

				if (isNew) states.push(newStates[i]);
			}

		}

		return undefined;
	}
}

## index.html
<html>
<head>
<title>8 Puzzle demo A*</title>
	<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.7.0/p5.min.js" integrity="sha512-bcfltY+lNLlNxz38yBBm/HLaUB1gTV6I0e+fahbF9pS6roIdzUytozWdnFV8ZnM6cSAG5EbmO0ag0a/fLZSG4Q==" crossorigin="anonymous" referrerpolicy="no-referrer"></script>
	<script src="state.js"></script>
	<script src="astar.js"></script>
	<script src="sketch.js"></script>
</head>
<body>
</body>
</html>

## sketch.js
var start = new State('123456780');
var target = new State('203416578');

function setup(){
	createCanvas(800, 600);
	noLoop();
}

function draw(){
	start.draw(5, 5);
	target.draw(55, 5);
}

function mousePressed(){
	var astar = new AStar();
	var path = astar.solve(start, target);

	var cx = 5;
	var cy = 80;
	while (path != undefined) {
		if (cx > 700) {
			cx = 5;
			cy = cy + 60;
		}

		path.draw(cx, cy);
		cx = cx + 50;

		path = path.prev;
	}
}

## state.js
function swapStr(st, i, j){
	var newStr = '';
	for (var c = 0; c < st.length; c++){
		if (c == i) newStr = newStr + st[j];
		else if (c ==j) newStr = newStr + st[i];
		else newStr = newStr + st[c];
	}
	return newStr;
}

var State = function(val){
	this.val = val;
	this.distance = -1;
	this.estimate = -1;
	this.prev = undefined;

	this.heuristicDist = function(target){
		var d = 0;
		for(var i = 0; i< val.length; i++){
			if (this.val[i] != target.val[i]) d++;
		}
		return d;
	}

	this.getNextStates = function(target){
		var dr = [0, -1, 0, 1];
		var dc = [-1, 0, 1, 0];

		var idx = this.val.indexOf('0');
		var r = Math.floor(idx / 3);
		var c = idx % 3;

		var newStates = [];
		for (var i = 0; i < 4; i++){
			var cr = r + dr[i];
			var cc = c + dc[i];
			if (cr >= 0 && cr < 3 && cc >= 0 && cc < 3){
				var swapIdx = cc + cr * 3;
				var newState = new State(swapStr(this.val, idx, swapIdx));
				newState.distance = this.distance + 1;
				newState.estimate = newState.heuristicDist(target);
				newState.prev = this;
				newStates.push(newState);
			}
		}

		return newStates;
	}

	this.draw = function(x, y){
		push();
		translate(x, y);
		for (var i = 0; i < 9; i++){
			var r = Math.floor(i / 3);
			var c = i % 3;
			rect(15 * c, 15 * r, 15, 15);
			if (this.val[i] != '0'){
				textSize(12)
				text(this.val[i], 15 * c + 5, 15 * r + 12);
			}
		}
		pop();
	}
}
	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:
	used.push(checkingState);
	var newStates = checkingState.getNextStates(target);

	//check if newstate is existed
	for (var i=0; i < newStates.length; i++){
	var isNew = true;
	for (var j=0; j < states.length; j++){
	if (newStates[i].val == states[j].val){
	isNew = false;
	continue;
	}
	}

	if (isNew) {
	for (var j=0; j < used.length; j++){
	if (newStates[i].val == used[j].val){
	isNew = false;
	continue;
	}
	}
	}

	if (isNew) states.push(newStates[i]);
	}

	}

	return undefined;
	}
	}
	<html>
	<head>
	<title>8 Puzzle demo A*</title>
	<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.7.0/p5.min.js" integrity="sha512-bcfltY+lNLlNxz38yBBm/HLaUB1gTV6I0e+fahbF9pS6roIdzUytozWdnFV8ZnM6cSAG5EbmO0ag0a/fLZSG4Q==" crossorigin="anonymous" referrerpolicy="no-referrer"></script>
	<script src="state.js"></script>
	<script src="astar.js"></script>
	<script src="sketch.js"></script>
	</head>
	<body>
	</body>
	</html>
	var start = new State('123456780');
	var target = new State('203416578');

	function setup(){
	createCanvas(800, 600);
	noLoop();
	}

	function draw(){
	start.draw(5, 5);
	target.draw(55, 5);
	}

	function mousePressed(){
	var astar = new AStar();
	var path = astar.solve(start, target);

	var cx = 5;
	var cy = 80;
	while (path != undefined) {
	if (cx > 700) {
	cx = 5;
	cy = cy + 60;
	}

	path.draw(cx, cy);
	cx = cx + 50;

	path = path.prev;
	}
	}
	function swapStr(st, i, j){
	var newStr = '';
	for (var c = 0; c < st.length; c++){
	if (c == i) newStr = newStr + st[j];
	else if (c ==j) newStr = newStr + st[i];
	else newStr = newStr + st[c];
	}
	return newStr;
	}

	var State = function(val){
	this.val = val;
	this.distance = -1;
	this.estimate = -1;
	this.prev = undefined;

	this.heuristicDist = function(target){
	var d = 0;
	for(var i = 0; i< val.length; i++){
	if (this.val[i] != target.val[i]) d++;
	}
	return d;
	}

	this.getNextStates = function(target){
	var dr = [0, -1, 0, 1];
	var dc = [-1, 0, 1, 0];

	var idx = this.val.indexOf('0');
	var r = Math.floor(idx / 3);
	var c = idx % 3;

	var newStates = [];
	for (var i = 0; i < 4; i++){
	var cr = r + dr[i];
	var cc = c + dc[i];
	if (cr >= 0 && cr < 3 && cc >= 0 && cc < 3){
	var swapIdx = cc + cr * 3;
	var newState = new State(swapStr(this.val, idx, swapIdx));
	newState.distance = this.distance + 1;
	newState.estimate = newState.heuristicDist(target);
	newState.prev = this;
	newStates.push(newState);
	}
	}

	return newStates;
	}

	this.draw = function(x, y){
	push();
	translate(x, y);
	for (var i = 0; i < 9; i++){
	var r = Math.floor(i / 3);
	var c = i % 3;
	rect(15 * c, 15 * r, 15, 15);
	if (this.val[i] != '0'){
	textSize(12)
	text(this.val[i], 15 * c + 5, 15 * r + 12);
	}
	}
	pop();
	}
	}