尝试实施广度优先搜索可视化工具需要帮助来制作动画过程

Question

所以我已经实现了算法的静态版本，它绘制了从起始节点到结束节点的路径。我需要帮助的是如何使这个过程充满活力。任何帮助将不胜感激。这里link到项目的GitHub页面

访问：https://a8hay.github.io/path-finding-algo-simulations/

我已经尝试了一些东西，但没有任何效果，就像我尝试突出显示起始节点访问绘图循环中每一帧的每个相邻单元格一样，但那不起作用。？

Answer 1

太棒了！

要可视化每个步骤，您需要将其记录下来，以便之后可以可视化。（例如 here and here

有几种方法可以做到这一点。例如：

您将记录完整网格数据的深层副本，稍后您可以 display/render 甚至 debug/display 额外的可视化数据。 How to Deep Copy Objects and Arrays in JavaScript 是一个很好的指南。
您可以为每个步骤渲染一个帧并将其记录为图层可视化播放的列表

目前您无法单独可视化步骤，因为 while 循环阻碍了渲染，但是没有什么能阻止您显式调用 draw() 渲染和 get()克隆框架供以后使用：

// XXXXXXXXXXXXXXXXXX HUD VARIABLES XXXXXXXXXXXXXXXXXXXX
let startButton;
let resetButton;
let cellType;
let algoType;
// XXXXXXXXXXXXXXXXXX HUD VARIABLES XXXXXXXXXXXXXXXXXXXX

// XXXXXXXXXXXXXXXXX SKETCH VARIABLES XXXXXXXXXXXXXXXXX
let GRID = [];
let cellSize = 15;
let startX;
let startY;
let endX;
let endY;
// XXXXXXXXXXXXXXXXX SKETCH VARIABLES XXXXXXXXXXXXXXXXX
// holds a grid per iteration step
let algoVisSteps = [];
// current iteration step counter
let algoVisStep = 0;
// display the visualisation or not
let displayAlgoViz = false;
// visualisation interval

function setup() {
  createCanvas(675, 315);
  initialiseGrid();
  createHud();
}

function draw() {
  background(100);
  
  if(displayAlgoViz){
    image(algoVisSteps[algoVisStep],0,0);
    // gotoNextFrame();
    algoVisStep = (algoVisStep + 1) % algoVisSteps.length;
  }else{
    // draw the grid
    for (let row = 0; row < GRID.length; row++) {
      for (let col = 0; col < GRID[0].length; col++) {
        GRID[row][col].show();
      }
    }
  
    placeMarkers();
  }
}

function placeMarkers() {
  let posx = floor(map(mouseX, 0, width, 0, GRID[0].length));
  let posy = floor(map(mouseY, 0, height, 0, GRID.length));
  let markerType = cellType.value();

  if (posx >= 0 && posy >= 0 && posx < GRID[0].length && posy < GRID.length) {
    if (mouseIsPressed && markerType == "START") {
      GRID[startX][startY].isStart = false;
      GRID[posy][posx].isStart = true;
      startX = posy;
      startY = posx;
    }
    if (mouseIsPressed && markerType == "END") {
      GRID[endX][endY].isEnd = false;
      GRID[posy][posx].isEnd = true;
      endX = posy;
      endY = posx;
    }
    if (mouseIsPressed && markerType == "WALLS") {
      GRID[posy][posx].isWall = true;
    }
  }
}

function createHud() {
  startButton = createButton("START");
  startButton.mousePressed(applyAlgo);
  resetButton = createButton("RESET");
  resetButton.mousePressed(initialiseGrid);

  cellType = createSelect();
  cellType.option("WALLS");
  cellType.option("START");
  cellType.option("END");

  algoType = createSelect();
  algoType.option("BREADTH FIRST SEARCH!");
  algoType.option("DEPTH FIRST SEARCH");
  algoType.option("DIJKASHTRA");
  algoType.option("A*");
}

function initialiseGrid() {
  resetVisualisation();
  GRID = create2dArray(floor(height / cellSize), floor(width / cellSize));

  for (let col = 0; col < GRID[0].length; col++) {
    for (let row = 0; row < GRID.length; row++) {
      let newCell = new Cell(col * cellSize, row * cellSize);
      GRID[row][col] = newCell;
    }
  }

  startX = 0;
  startY = 0;
  GRID[startX][startY].isStart = true;
  endX = GRID.length - 1;
  endY = GRID[0].length - 1;
  GRID[endX][endY].isEnd = true;

  addNeighbours();
}

// XXXXXXXXXXXXXXXX HELPER FUNCTIONS XXXXXXXXXXXXXXXXXX
function create2dArray(m, n) {
  // array of m rows and n columns
  resultArray = [];
  for (let row = 0; row < m; row++) {
    let tempRow = [];
    for (let col = 0; col < n; col++) {
      tempRow.push(0);
    }
    resultArray.push(tempRow);
  }
  return resultArray;
}

function applyAlgo() {
  algo = algoType.value();
  if (algo === "BREADTH FIRST SEARCH!") {
    bfs();
    startAlgoVisualisation();
  }else{
    console.warn(algo,"not yet implemented");
  }
}

function addNeighbours() {
  // add only non diagonal elements
  // add neighbours of non boundary cells
  for (let row = 1; row < GRID.length - 1; row++) {
    for (let col = 1; col < GRID[0].length - 1; col++) {
      let current = GRID[row][col];
      current.neighbours = [
        GRID[row - 1][col],
        GRID[row][col - 1],
        GRID[row + 1][col],
        GRID[row][col + 1]
      ];
    }
  }
  // add neighbours of upper and lower boundary cells
  for (let col = 1; col < GRID[0].length - 1; col++) {
    let upper_boundary = GRID[0][col];
    upper_boundary.neighbours = [
      GRID[0][col - 1],
      GRID[0][col + 1],
      GRID[1][col]
    ];
    let lower_boundary = GRID[GRID.length - 1][col];
    lower_boundary.neighbours = [
      GRID[GRID.length - 1][col - 1],
      GRID[GRID.length - 1][col + 1],
      GRID[GRID.length - 1 - 1][col]
    ];
  }
  // add neighbours of left and right boundary cells
  for (let row = 1; row < GRID.length - 1; row++) {
    let left_boundary = GRID[row][0];
    left_boundary.neighbours = [
      GRID[row - 1][0],
      GRID[row + 1][0],
      GRID[row][1]
    ];
    let right_boundary = GRID[row][GRID[0].length - 1];
    right_boundary.neighbours = [
      GRID[row - 1][GRID[0].length - 1],
      GRID[row + 1][GRID[0].length - 1],
      GRID[row][GRID[0].length - 1 - 1]
    ];
  }
  // add neighbours of four corner cells
  let upper_left_corner = GRID[0][0];
  upper_left_corner.neighbours = [GRID[0 + 1][0], GRID[0][0 + 1]];

  let upper_right_corner = GRID[0][GRID[0].length - 1];
  upper_right_corner.neighbours = [
    GRID[0 + 1][GRID[0].length - 1],
    GRID[0][GRID[0].length - 1 - 1]
  ];

  let lower_right_corner = GRID[GRID.length - 1][GRID[0].length - 1];
  lower_right_corner.neighbours = [
    GRID[GRID.length - 1 - 1][GRID[0].length - 1],
    GRID[GRID.length - 1][GRID[0].length - 1 - 1]
  ];

  let lower_left_corner = GRID[GRID.length - 1][0];
  lower_left_corner.neighbours = [
    GRID[GRID.length - 1 - 1][0],
    GRID[GRID.length - 1][0 + 1]
  ];
}
// XXXXXXXXXXXXXXXX HELPER FUNCTIONS XXXXXXXXXXXXXXXXXX
function addVisualisationStep(){
  draw();
  algoVisSteps.push(get());
  console.log("recorded",algoVisSteps.length,"frames");
}

function startAlgoVisualisation(){
  displayAlgoViz = true;
}

function stopAlgoVisualisation(){
  displayAlgoViz = false;
}

function resetVisualisation(){
  stopAlgoVisualisation();
  algoVisStep = 0;
  while(algoVisSteps.length > 0){
    delete algoVisSteps[0];
    algoVisSteps.shift();
  }
}

// BFS
function bfs() {
  console.log("applying BREADTH FIRST SEARCH");
  let startNode = GRID[startX][startY];
  let endNode = GRID[endX][endY];
  let Q = [];

  startNode.isDiscovered = true;
  Q.push(startNode);

  while (Q.length > 0) {
    let current = Q.shift();
    if (current == endNode) {
      console.log("found end node");
      break;
    } else {
      for (let nebr of current.neighbours) {
        if (nebr.isWall) {
          continue;
        }
        if (!nebr.isDiscovered) {
          nebr.isDiscovered = true;
          nebr.parent = current;
          Q.push(nebr);
          addVisualisationStep();
        }
      }
    }
  }

  //   mark the cells which are in the path(that is solution path bw start and end)
  let end = endNode;
  while (end.parent != null) {
    if (!end.isStart) {
      end.isPath = true;
    }
    addVisualisationStep();
    end = end.parent;
  }
}

// Cell

class Cell {
  constructor(x, y) {
    this.x = x;
    this.y = y;
    this.isStart = false;
    this.isEnd = false;
    this.isWall = false;
    this.isDiscovered = false;
    this.isPath = false;
    this.parent = null;
    this.neighbours = [];
    this.clr = [255, 255, 255, 255];
  }

  show() {
    if (this.isStart) {
      this.clr = [0, 255, 0, 255];
    } else {
      this.clr = [255, 255, 255, 255];
    }
    if (this.isEnd) {
      this.clr = [255, 0, 0, 255];
    }
    if (this.isWall) {
      this.clr = [51, 51, 51, 255];
    }
    if (this.isDiscovered && !this.isStart) {
      this.clr = [0, 255, 255, 180];
    }
    if (this.isPath) {
      this.clr = [255, 255, 0, 255];
    }
    stroke(115);
    fill(this.clr[0], this.clr[1], this.clr[2], this.clr[3]);
    rect(this.x, this.y, cellSize, cellSize);
  }
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.0.0/p5.min.js"></script>

请注意，我已经减小了渲染的大小以节省 RAM。对于具有大量高分辨率帧的模拟，它将变得昂贵。

在这里您可以合理化每帧可以存储到redraw/visualise算法

的最小信息片段是什么

更新

这是一个对网格进行浅表复制的版本，只复制渲染网格所需的数据（位置、状态），但丢弃搜索相关数据（例如 isParent/neighbours/等）：

// XXXXXXXXXXXXXXXXXX HUD VARIABLES XXXXXXXXXXXXXXXXXXXX
let startButton;
let resetButton;
let cellType;
let algoType;
// XXXXXXXXXXXXXXXXXX HUD VARIABLES XXXXXXXXXXXXXXXXXXXX

// XXXXXXXXXXXXXXXXX SKETCH VARIABLES XXXXXXXXXXXXXXXXX
let GRID = [];
let cellSize = 15;
let startX;
let startY;
let endX;
let endY;
// XXXXXXXXXXXXXXXXX SKETCH VARIABLES XXXXXXXXXXXXXXXXX
// holds a grid per iteration step
let algoVisSteps = [];
// current iteration step counter
let algoVisStep = 0;
// display the visualisation or not
let displayAlgoViz = false;
// visualisation interval

function setup() {
  createCanvas(675, 315);
  initialiseGrid();
  createHud();
}

function draw() {
  background(100);
  
  if(displayAlgoViz){
    drawGrid(algoVisSteps[algoVisStep]);
    // gotoNextFrame();
    algoVisStep = (algoVisStep + 1) % algoVisSteps.length;
  }else{
    
    drawGrid(GRID);
    
    placeMarkers();
  }
}

function drawGrid(GRID){
  // draw the grid
  for (let row = 0; row < GRID.length; row++) {
    for (let col = 0; col < GRID[0].length; col++) {
      GRID[row][col].show();
    }
  }
}

function placeMarkers() {
  let posx = floor(map(mouseX, 0, width, 0, GRID[0].length));
  let posy = floor(map(mouseY, 0, height, 0, GRID.length));
  let markerType = cellType.value();

  if (posx >= 0 && posy >= 0 && posx < GRID[0].length && posy < GRID.length) {
    if (mouseIsPressed && markerType == "START") {
      GRID[startX][startY].isStart = false;
      GRID[posy][posx].isStart = true;
      startX = posy;
      startY = posx;
    }
    if (mouseIsPressed && markerType == "END") {
      GRID[endX][endY].isEnd = false;
      GRID[posy][posx].isEnd = true;
      endX = posy;
      endY = posx;
    }
    if (mouseIsPressed && markerType == "WALLS") {
      GRID[posy][posx].isWall = true;
    }
  }
}

function createHud() {
  startButton = createButton("START");
  startButton.mousePressed(applyAlgo);
  resetButton = createButton("RESET");
  resetButton.mousePressed(initialiseGrid);

  cellType = createSelect();
  cellType.option("WALLS");
  cellType.option("START");
  cellType.option("END");

  algoType = createSelect();
  algoType.option("BREADTH FIRST SEARCH!");
  algoType.option("DEPTH FIRST SEARCH");
  algoType.option("DIJKASHTRA");
  algoType.option("A*");
}

function initialiseGrid() {
  resetVisualisation();
  GRID = create2dArray(floor(height / cellSize), floor(width / cellSize));

  for (let col = 0; col < GRID[0].length; col++) {
    for (let row = 0; row < GRID.length; row++) {
      let newCell = new Cell(col * cellSize, row * cellSize);
      GRID[row][col] = newCell;
    }
  }

  startX = 0;
  startY = 0;
  GRID[startX][startY].isStart = true;
  endX = GRID.length - 1;
  endY = GRID[0].length - 1;
  GRID[endX][endY].isEnd = true;

  addNeighbours();
}

// XXXXXXXXXXXXXXXX HELPER FUNCTIONS XXXXXXXXXXXXXXXXXX
function create2dArray(m, n) {
  // array of m rows and n columns
  resultArray = [];
  for (let row = 0; row < m; row++) {
    let tempRow = [];
    for (let col = 0; col < n; col++) {
      tempRow.push(0);
    }
    resultArray.push(tempRow);
  }
  return resultArray;
}

function applyAlgo() {
  algo = algoType.value();
  if (algo === "BREADTH FIRST SEARCH!") {
    bfs();
    startAlgoVisualisation();
  }else{
    console.warn(algo,"not yet implemented");
  }
}

function addNeighbours() {
  // add only non diagonal elements
  // add neighbours of non boundary cells
  for (let row = 1; row < GRID.length - 1; row++) {
    for (let col = 1; col < GRID[0].length - 1; col++) {
      let current = GRID[row][col];
      current.neighbours = [
        GRID[row - 1][col],
        GRID[row][col - 1],
        GRID[row + 1][col],
        GRID[row][col + 1]
      ];
    }
  }
  // add neighbours of upper and lower boundary cells
  for (let col = 1; col < GRID[0].length - 1; col++) {
    let upper_boundary = GRID[0][col];
    upper_boundary.neighbours = [
      GRID[0][col - 1],
      GRID[0][col + 1],
      GRID[1][col]
    ];
    let lower_boundary = GRID[GRID.length - 1][col];
    lower_boundary.neighbours = [
      GRID[GRID.length - 1][col - 1],
      GRID[GRID.length - 1][col + 1],
      GRID[GRID.length - 1 - 1][col]
    ];
  }
  // add neighbours of left and right boundary cells
  for (let row = 1; row < GRID.length - 1; row++) {
    let left_boundary = GRID[row][0];
    left_boundary.neighbours = [
      GRID[row - 1][0],
      GRID[row + 1][0],
      GRID[row][1]
    ];
    let right_boundary = GRID[row][GRID[0].length - 1];
    right_boundary.neighbours = [
      GRID[row - 1][GRID[0].length - 1],
      GRID[row + 1][GRID[0].length - 1],
      GRID[row][GRID[0].length - 1 - 1]
    ];
  }
  // add neighbours of four corner cells
  let upper_left_corner = GRID[0][0];
  upper_left_corner.neighbours = [GRID[0 + 1][0], GRID[0][0 + 1]];

  let upper_right_corner = GRID[0][GRID[0].length - 1];
  upper_right_corner.neighbours = [
    GRID[0 + 1][GRID[0].length - 1],
    GRID[0][GRID[0].length - 1 - 1]
  ];

  let lower_right_corner = GRID[GRID.length - 1][GRID[0].length - 1];
  lower_right_corner.neighbours = [
    GRID[GRID.length - 1 - 1][GRID[0].length - 1],
    GRID[GRID.length - 1][GRID[0].length - 1 - 1]
  ];

  let lower_left_corner = GRID[GRID.length - 1][0];
  lower_left_corner.neighbours = [
    GRID[GRID.length - 1 - 1][0],
    GRID[GRID.length - 1][0 + 1]
  ];
}
// XXXXXXXXXXXXXXXX HELPER FUNCTIONS XXXXXXXXXXXXXXXXXX
function addVisualisationStep(){
  //draw();
  algoVisSteps.push(shallowCopyGrid(GRID));
  console.log("recorded",algoVisSteps.length,"frames");
}

function startAlgoVisualisation(){
  displayAlgoViz = true;
}

function stopAlgoVisualisation(){
  displayAlgoViz = false;
}

function resetVisualisation(){
  stopAlgoVisualisation();
  algoVisStep = 0;
  while(algoVisSteps.length > 0){
    delete algoVisSteps[0];
    algoVisSteps.shift();
  }
}

function shallowCopyGrid(grid){
  let copy = [];
  
  for(let i = 0; i < grid.length; i++){
    let list = [];
    
    for(let j = 0; j < grid[i].length; j++){
      list.push(grid[i][j].shallowCopy());
    }
    
    copy.push(list);
  }
  
  return copy;
}

function bfs() {
  console.log("applying BREADTH FIRST SEARCH");
  let startNode = GRID[startX][startY];
  let endNode = GRID[endX][endY];
  let Q = [];

  startNode.isDiscovered = true;
  Q.push(startNode);

  while (Q.length > 0) {
    let current = Q.shift();
    if (current == endNode) {
      console.log("found end node");
      break;
    } else {
      for (let nebr of current.neighbours) {
        if (nebr.isWall) {
          continue;
        }
        if (!nebr.isDiscovered) {
          nebr.isDiscovered = true;
          nebr.parent = current;
          Q.push(nebr);
          addVisualisationStep();
        }
      }
    }
  }

  //   mark the cells which are in the path(that is solution path bw start and end)
  let end = endNode;
  while (end.parent != null) {
    if (!end.isStart) {
      end.isPath = true;
    }
    addVisualisationStep();
    end = end.parent;
  }
}

class Cell {
  constructor(x, y) {
    this.x = x;
    this.y = y;
    this.isStart = false;
    this.isEnd = false;
    this.isWall = false;
    this.isDiscovered = false;
    this.isPath = false;
    this.parent = null;
    this.neighbours = [];
    this.clr = [255, 255, 255, 255];
  }

  show() {
    if (this.isStart) {
      this.clr = [0, 255, 0, 255];
    } else {
      this.clr = [255, 255, 255, 255];
    }
    if (this.isEnd) {
      this.clr = [255, 0, 0, 255];
    }
    if (this.isWall) {
      this.clr = [51, 51, 51, 255];
    }
    if (this.isDiscovered && !this.isStart) {
      this.clr = [0, 255, 255, 180];
    }
    if (this.isPath) {
      this.clr = [255, 255, 0, 255];
    }
    stroke(115);
    fill(this.clr[0], this.clr[1], this.clr[2], this.clr[3]);
    rect(this.x, this.y, cellSize, cellSize);
  }
  
  // copy without neighbours
  shallowCopy() {
    let copy = new Cell(this.x,this.y);
    
    copy.isStart = this.isStart;
    copy.isEnd = this.isEnd;
    copy.isWall = this.isWall;
    copy.isDiscovered = this.isDiscovered;
    copy.isPath = this.isPath;
    copy.clr = [].concat(this.clr);
    
    return copy;
  }
  
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.0.0/p5.min.js"></script>

尝试实施广度优先搜索可视化工具需要帮助来制作动画过程

trying to implement breadth first search visualiser need help in animating the process

processing

p5.js