Вы можете перепроверить свою реализацию Astar, ниже приведен пример реализации, каким-то образом сохраняющий ваши функции
Вы можете посмотреть строку '+++', чтобы найти места, где я добавил некоторый код
//https://en.wikipedia.org/wiki/A*_search_algorithm
function reconstruct_path (cameFrom, current, id) {
const total_path = [current]
while(cameFrom.has(id(current))) {
current = cameFrom.get(id(current))
total_path.unshift(current)
}
return total_path
}
// keyword astar
// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h, neighbours, id = x=>x, d=(a,b)=>1) {
// The set of discovered nodes that may need to be (re-)expanded.
// Initially, only the start node is known.
const openSet = new Map([[id(start), start]])
// For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start to n currently known.
const cameFrom = new Map()
// For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
const gScore = new Map()
gScore.set(id(start), 0)
// For node n, fScore[n] := gScore[n] + h(n).
const fScore = new Map()
fScore.set(id(start), h(start))
let count = 0
while (openSet.size) {
//current := the node in openSet having the lowest fScore[] value
let current
let bestScore = Number.MAX_SAFE_INTEGER
for (let [nodeId, node] of openSet) {
const score = fScore.get(nodeId)
if (score < bestScore) {
bestScore = score
current = node
}
}
if (id(current) == id(goal)) {
return reconstruct_path(cameFrom, current, id)
}
openSet.delete(id(current))
neighbours(current).forEach(neighbor => {
const neighborId = id(neighbor)
// d(current,neighbor) is the weight of the edge from current to neighbor
// tentative_gScore is the distance from start to the neighbor through current
const tentative_gScore = gScore.get(id(current)) + d(current, neighbor)
if (!gScore.has(neighborId) || tentative_gScore < gScore.get(neighborId)) {
// This path to neighbor is better than any previous one. Record it!
cameFrom.set(neighborId, current)
gScore.set(neighborId, tentative_gScore)
fScore.set(neighborId, gScore.get(neighborId) + h(neighbor))
if (!openSet.has(neighborId)){
openSet.set(neighborId, neighbor)
}
}
})
}
// Open set is empty but goal was never reached
return false
}
// ---- end of AStar ---
//rows and width N*N
const N = 16;
class PriorityQueue {
constructor(maxSize) {
// Set default max size if not provided
if (isNaN(maxSize)) {
maxSize = N*N;
}
this.maxSize = maxSize;
// Init an array that'll contain the queue values.
this.container = [];
}
// Helper function to display all values while developing
display() {
console.log(this.container);
}
// Checks if queue is empty
isEmpty() {
return this.container.length === 0;
}
// checks if queue is full
isFull() {
return this.container.length >= this.maxSize;
}
enqueue(data, priority) {
// Check if Queue is full
if (this.isFull()) {
console.log("Queue Overflow!");
return;
}
let currElem = new this.Element(data, priority);
let addedFlag = false;
// Since we want to add elements to end, we'll just push them.
for (let i = 0; i < this.container.length; i++) {
if (currElem.priority > this.container[i].priority) {
this.container.splice(i, 0, currElem);
addedFlag = true; break;
}
}
if (!addedFlag) {
this.container.push(currElem);
}
}
dequeue() {
// Check if empty
if (this.isEmpty()) {
console.log("Queue Underflow!");
return;
}
return this.container.pop();
}
peek() {
if (this.isEmpty()) {
console.log("Queue Underflow!");
return;
}
return this.container[this.container.length - 1];
}
clear() {
this.container = [];
}
}
// Create an inner class that we'll use to create new nodes in the queue
// Each element has some data and a priority
PriorityQueue.prototype.Element = class {
constructor(data, priority) {
this.data = data;
this.priority = priority;
}
};
//priority queue
//graph
var width=N;
var height=N;
var visited = [];
const indexToPositionX = (index) => index % width;
const indexToPositionY = (index) => Math.floor(index / width);
const posToIndex = (x, y) => (y * width) + x;
const removeDuplicates = (array) => array.filter((a, b) => array.indexOf(a) === b);
function heuristic(a,b){
let x = indexToPosition(a);
let y = indexToPosition(b);
return Math.abs(x.x - y.x) + Math.abs(x.y - y.y);
}
class Cell{
constructor(index){
this.index = index;
this.y = indexToPositionY(index);
this.x = indexToPositionX(index);
}
}
var blocks = new Array(N);
const indexToPosition = (index) => ({
x: index % width,
y: Math.floor(index / width)
})
// Initialize
for (var i = 0; i < width*height; i++) {
const position = indexToPosition(i)
blocks[i] = new Cell(position.x, position.y)
}
// When cell is clicked
const container = document.getElementById("container");
function makeRows(rows, cols) {
container.style.setProperty('--grid-rows', rows);
container.style.setProperty('--grid-cols', cols);
for (c = 0; c < (rows * cols); c++) {
let cell = document.createElement("div");
cell.innerText = (c);
cell.setAttribute("id",c);
container.appendChild(cell).className = "grid-item";
}
}
var nodes = [256];
function init(){
for(let i=0; i<N*N; i++){
nodes[i] = new Cell(i);
}
}
const isOnMap = (x,y) => x >= 0 && y >= 0 && x < width && y < height;
// +++
const obstacles = new Set([3, 19, 35])
function findNeighbors(index){
let x = nodes[index].x;
let y = nodes[index].y;
let neighbors = [];
for (let xx = -1; xx <= 1; xx++) {
for (let yy = -1; yy <= 1; yy++) {
if (xx == 0 && yy == 0) {
continue; // You are not neighbor to yourself
}
if (Math.abs(xx) + Math.abs(yy) > 1) {
continue;
}
// +++
if (obstacles.has(posToIndex(x + xx, y + yy))) {
continue
}
if (isOnMap(x + xx, y + yy)) {
neighbors.push(new Cell(posToIndex(x + xx, y + yy)));
}
}
}
return neighbors;
}
function findDistance(a,b){
let x1 = nodes[a].x;
let x2 = nodes[b].x;
let y1 = nodes[a].y;
let y2 = nodes[b].y;
let first = x2-x1;
let second = y2-y1;
let d = Math.sqrt( Math.pow(first,2) + Math.pow(second,2));
return d;
}
makeRows(N, N);
init();
var cell = document.querySelectorAll('.grid-item');
// +++
[...obstacles].forEach(id => {
cell[id].style.backgroundColor = 'pink'
})
const start = new Cell(1)
const end = new Cell(21)
cell[start.index].style.backgroundColor = "blue";
cell[end.index].style.backgroundColor = "red";
let came_from = A_Star(start, end, function (cell) {
return heuristic(cell.index, end.index)
}, function(cell) {
return findNeighbors(cell.index)
}, cell => cell.index)
came_from.slice(1, -1).forEach(c => {
cell[c.index].style.backgroundColor = 'green'
})
:root {
--grid-cols: 1;
--grid-rows: 1;
}
#container {
display: grid;
grid-template-rows: repeat(var(--grid-rows), 1fr);
grid-template-columns: repeat(var(--grid-cols), 1fr);
}
.grid-item {
padding: 4rem 2rem;
border: 1px solid rgba(0,0,0,.3);
text-align: center;
background-color:rgba(0,0,0,.05);
}
<html>
<head>
<link rel="stylesheet" href="style.css">
</head>
<body>
<div id="container">
</div>
</body>
<script src="astar.js"></script>
<script src="index.js"></script>
</html>