向网格添加障碍物

问题描述 投票：0回答：1

我正在尝试为我的网格添加障碍，以实现最佳的首次搜索。

这里是没有障碍的代码：

//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 start = 0;
var end = 0;
var visited = [];
var obstacles = [];

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);
		this.isActive = false;
		this.isStart = false;
		this.isEnd = false;
		//isFree = false for obstacles
		this.isFree = true;
	}
}
var firstClick = true;
var secondClick = false;

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";
  }
}

function greedy(){

	frontier =  new PriorityQueue();
	frontier.enqueue(nodes[start],0);
	
	let came_from = [];
	let came_from_counter = 0;

	while(!frontier.isEmpty()){
		let current = frontier.peek();
		frontier.dequeue();


		if(current.data.index == nodes[end].index){
			
			came_from[came_from_counter] = current.data.index;
			return came_from;
		}
			let neighbors = findNeighbors(current.data.index);
			for(let i=0; i< findNeighbors(current.data.index).length; i++){
				let next = neighbors.pop();
				if(!(next in came_from)){
					came_from_counter++;
					let priority = heuristic(nodes[end].index, next.index);
					visited.push(next.index);
					frontier.enqueue(next, priority);
					came_from[came_from_counter] = current.data.index;
				}
			}
			
		
	}
	return came_from;
}

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;

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 (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;
}

function checkClick(i){
	if(firstClick){
		//click starting node
		nodes[i].isStart = true;
		nodes[i].isActive = true;
		start = i;
		cell[i].style.backgroundColor = "blue";
		firstClick = false;
		secondClick = true;
	
	}else{
		//click end goal node
		nodes[i].isEnd = true;
		end = i;
		nodes[i].isActive = true;
		cell[i].style.backgroundColor = "red";
		let came_from = greedy();
		came_from = removeDuplicates(came_from);
    console.log('came_from ',came_from);		
	}
}




makeRows(N, N);
init();

var cell = document.querySelectorAll('.grid-item');
for(let i=0; i<N*N; i++){
	cell[i].onclick = function(){let y = indexToPositionY(this.id); 
		let x = indexToPositionX(this.id);
		checkClick(this.id);
	}
}
: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>
</html>

现在，我相信此代码可以正常工作。我试图通过向Cell类添加bool isFree来添加障碍。我修改了函数findNeighbors来检查节点是否也空闲。

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 (isOnMap(x + xx, y + yy) **&& nodes[posToIndex(x + xx, y + yy)].isFree**) {
                neighbors.push(new Cell(posToIndex(x + xx, y + yy)));
            }
        }
    }
    return neighbors;
}

但是，这不起作用:(有没有更好的方法为网格添加障碍？

javascript algorithm math graph collision-detection
1个回答
0
投票

您可以通过某种方式保留功能的示例来交叉检查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>
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.