首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

A*在Javascript (带有p5.js)中不起作用

A*算法是一种常用的路径搜索算法,用于在图形或网络中找到最短路径。它通过评估每个节点的代价函数来确定下一步要探索的节点,直到找到目标节点。

在Javascript中,可以使用p5.js库来实现A算法。p5.js是一个基于Processing的JavaScript库,用于创建交互式图形和动画。它提供了一些方便的函数和方法,可以简化A算法的实现过程。

下面是一个简单的示例代码,演示了如何在Javascript中使用p5.js实现A*算法:

代码语言:txt
复制
// 创建一个表示节点的类
class Node {
  constructor(x, y) {
    this.x = x;
    this.y = y;
    this.g = 0; // 从起点到当前节点的实际代价
    this.h = 0; // 从当前节点到目标节点的估计代价
    this.f = 0; // 总代价:f = g + h
    this.neighbors = []; // 相邻节点
    this.previous = undefined; // 前一个节点
  }
  
  // 计算当前节点到目标节点的估计代价(使用曼哈顿距离)
  heuristic(target) {
    return Math.abs(this.x - target.x) + Math.abs(this.y - target.y);
  }
  
  // 添加相邻节点
  addNeighbors(grid) {
    let x = this.x;
    let y = this.y;
    
    if (x > 0) {
      this.neighbors.push(grid[x - 1][y]);
    }
    if (x < grid.length - 1) {
      this.neighbors.push(grid[x + 1][y]);
    }
    if (y > 0) {
      this.neighbors.push(grid[x][y - 1]);
    }
    if (y < grid[x].length - 1) {
      this.neighbors.push(grid[x][y + 1]);
    }
  }
}

// 创建一个表示网格的二维数组
let grid = new Array(cols);

// 初始化网格
function setup() {
  // 设置画布大小
  createCanvas(400, 400);
  
  // 初始化每个节点
  for (let i = 0; i < cols; i++) {
    grid[i] = new Array(rows);
  }
  
  // 创建节点对象
  for (let i = 0; i < cols; i++) {
    for (let j = 0; j < rows; j++) {
      grid[i][j] = new Node(i, j);
    }
  }
  
  // 添加相邻节点
  for (let i = 0; i < cols; i++) {
    for (let j = 0; j < rows; j++) {
      grid[i][j].addNeighbors(grid);
    }
  }
  
  // 设置起点和目标节点
  start = grid[0][0];
  target = grid[cols - 1][rows - 1];
  
  // 开始A*算法
  astar();
}

// A*算法
function astar() {
  // 创建开放列表和关闭列表
  let openSet = [];
  let closedSet = [];
  
  // 将起点添加到开放列表
  openSet.push(start);
  
  while (openSet.length > 0) {
    // 在开放列表中找到f值最小的节点
    let winner = 0;
    for (let i = 0; i < openSet.length; i++) {
      if (openSet[i].f < openSet[winner].f) {
        winner = i;
      }
    }
    
    let current = openSet[winner];
    
    // 如果当前节点是目标节点,路径搜索完成
    if (current === target) {
      console.log("路径搜索完成");
      break;
    }
    
    // 将当前节点从开放列表中移除,并添加到关闭列表中
    openSet.splice(winner, 1);
    closedSet.push(current);
    
    // 遍历当前节点的相邻节点
    let neighbors = current.neighbors;
    for (let i = 0; i < neighbors.length; i++) {
      let neighbor = neighbors[i];
      
      // 如果相邻节点不在关闭列表中且不是障碍物
      if (!closedSet.includes(neighbor)) {
        let tempG = current.g + 1; // 计算从起点到相邻节点的实际代价
        
        // 如果相邻节点不在开放列表中,或者新的代价更小
        if (!openSet.includes(neighbor) || tempG < neighbor.g) {
          neighbor.g = tempG;
          neighbor.h = neighbor.heuristic(target);
          neighbor.f = neighbor.g + neighbor.h;
          neighbor.previous = current;
          
          // 如果相邻节点不在开放列表中,将其添加到开放列表中
          if (!openSet.includes(neighbor)) {
            openSet.push(neighbor);
          }
        }
      }
    }
  }
  
  // 重构路径
  let path = [];
  let temp = current;
  path.push(temp);
  while (temp.previous) {
    path.push(temp.previous);
    temp = temp.previous;
  }
  
  // 绘制路径
  for (let i = 0; i < path.length; i++) {
    path[i].show(color(0, 0, 255));
  }
}

// 绘制网格
function draw() {
  background(255);
  
  for (let i = 0; i < cols; i++) {
    for (let j = 0; j < rows; j++) {
      grid[i][j].show(color(255));
    }
  }
}

在这个示例中,我们创建了一个表示节点的Node类,其中包含了计算代价、添加相邻节点等方法。然后,我们使用p5.js库创建了一个表示网格的二维数组,并初始化每个节点。接下来,我们使用A*算法来搜索最短路径,并将结果绘制在画布上。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

领券