Public
Edited
Jan 18
example = [[0,1,0],[1,0,0],[0,1,0], [0,0,0]]
drawPath(example)
a_star = (start, board) => {
const boardWidth = board[0].length
const goal = board.length * boardWidth - 1
let openSet = [start]
const cameFrom = []
const gScore = []
gScore[start] = 0
const fScore = []
fScore[start] = h_score(start, board)
let i = 0
while(openSet.length > 0 && i < 100) {
i += 1
console.log({openSet})
const current = openSet.reduce((prev, curr) => fScore[curr] < fScore[prev] ? curr : prev, start)
if (current == goal) return reconstructPath(cameFrom, current)
openSet = openSet.filter(c => c != current)
const neighbors = []
const currentX = current % boardWidth
const currentY = Math.floor(current / board.length)
if (currentX < boardWidth - 1) neighbors.push([current + 1, 1])
if (currentY < board.length - 1) neighbors.push([current + boardWidth, 1])
if (neighbors.length == 2 && board[currentY][currentX] == 1) neighbors.push([current+boardWidth+1, 0])
for (let [neighbor, weight] of neighbors) {
const potentialG = gScore[current] + weight
let existingG = gScore[neighbor]
if (existingG == undefined) existingG = 9999
if (potentialG < existingG) {
cameFrom[neighbor] = current
gScore[neighbor] = potentialG
fScore[neighbor] = potentialG + h_score(neighbor, board)
if (!openSet.includes(neighbor)) openSet.push(neighbor)
}
}
}
}
reconstructPath = (cameFrom, current) => {
const ret = []
while (current !== undefined) {
ret.push(current)
const current = cameFrom[current]
}
return ret
}
h_score = (from, board) => {
// best case scenario is that you only need to add/remove extra items
console.log('board', board)
const height = board.length
console.log(board[0])
const width = board[0].length
const dx = (width - 1) - (from % width)
const dy = (height - 1) - Math.floor(from / height)
return Math.abs(dx-dy)
}
x = a_star(0, example)
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
