astar.html

<script>

	// Source: https://www.redblobgames.com/pathfinding/a-star/implementation.html
	function search (map, start, goal, straight) {
		var frontier = [[start, 0]]
		var cameFrom = {}
		var costSoFar = {}
		cameFrom[start] = null
		costSoFar[start] = 0
		while (frontier.length > 0) {
			var bestIndex = 0
			for (var i = 0; i < frontier.length; i++) {
				if (frontier[i][1] < frontier[bestIndex][1]) {
					bestIndex = i
				}
			}
			var current = frontier[bestIndex][0]
			frontier.splice(bestIndex, 1)
			if (current[0] === goal[0] && current[1] === goal[1]) {
				break
			}
			var x = current[0]
			var y = current[1]
			var neighbors = []
			if (y - 1 > -1 && map[y - 1][x]) {
				neighbors.push([x, y - 1])
			}
			if (x - 1 > -1 && map[y][x - 1]) {
				neighbors.push([x - 1, y])
			}
			if (x + 1 < map[0].length && map[y][x + 1]) {
				neighbors.push([x + 1, y])
			}
			if (y + 1 < map.length && map[y + 1][x]) {
				neighbors.push([x, y + 1])
			}
			if (!straight) {
				if (y - 1 > -1 && x - 1 > -1 && map[y - 1][x - 1]) {
					neighbors.push([x - 1, y - 1])
				}
				if (y - 1 > -1 && x + 1 < map[0].length && map[y - 1][x + 1]) {
					neighbors.push([x + 1, y - 1])
				}
				if (y + 1 < map.length && x - 1 > -1 && map[y + 1][x - 1]) {
					neighbors.push([x - 1, y + 1])
				}
				if (y + 1 < map.length && x + 1 < map[0].length && map[y + 1][x + 1]) {
					neighbors.push([x + 1, y + 1])
				}
			}
			for (var i = 0; i < neighbors.length; i++) {
				var next = neighbors[i]
				var newCost = costSoFar[current] + Math.abs(next[0] - current[0]) + Math.abs(next[1] - current[1])
				if (!costSoFar.hasOwnProperty(next) || newCost < costSoFar[next]) {
					costSoFar[next] = newCost
					var priority = newCost + Math.abs(next[0] - goal[0]) + Math.abs(next[1] - goal[1])
					frontier.push([next, priority])
					cameFrom[next] = current
				}
			}
		}
		if (!cameFrom.hasOwnProperty(goal)) {
			return null
		}
		var path = []
		var current = goal
		while (current[0] !== start[0] || current[1] !== start[1]) {
			path.unshift(current)
			current = cameFrom[current]
		}
		path.unshift(start)
		return path
	}

	var map = [
		[1, 1, 1, 1, 1, 1, 1, 1],
		[0, 0, 1, 1, 1, 1, 1, 1],
		[1, 1, 1, 0, 0, 1, 1, 1],
		[1, 1, 1, 1, 1, 1, 1, 1],
		[1, 1, 1, 1, 1, 1, 1, 1],
		[1, 1, 1, 1, 1, 1, 1, 1],
		[1, 1, 1, 1, 1, 1, 1, 1],
		[1, 1, 1, 1, 1, 1, 1, 1],
	]
	var start = [0, 0]
	var goal = [7, 7]
	var result = search(map, start, goal)

	var canvas = document.createElement('canvas')
	var ctx = canvas.getContext('2d')

	for (var y = 0; y < 8; y++) {
		for (var x = 0; x < 8; x++) {
			if (!map[y][x]) {
				ctx.fillStyle = 'red'
				ctx.fillRect(x * 10 + 10, y * 10 + 10, 10, 10)
			}
			if (result && result.find(function (location) { return location[0] === x && location[1] === y })) {
				ctx.fillStyle = 'green'
				ctx.fillRect(x * 10 + 10, y * 10 + 10, 10, 10)
			}
			ctx.strokeRect(x * 10 + 10, y * 10 + 10, 10, 10)
		}
	}

	addEventListener('DOMContentLoaded', function () {
		document.body.appendChild(canvas)
	})

</script>