Search code examples
pseudocode

Pseudocode -> C++, any tips?

So I have been given this pseudo code, but I don't get what is meant by it. We have to make a recursive backtracking random maze generator. Can someone explain it?

enter image description here

Solution

  • You start with some kind of cell in the maze. Further, if you have not visited it, you move from it immediately to all neighboring cells and start there from the beginning. i.e. first you are in one cell, then for example in three. Since, in fact recursion call is executed sequentially, it seems that the traveler enters these paths in turn.

    async function findPath(from, to){ 
  /* 1 */ visited[from.y][from.x]=true;

          drawMaze()
          await sleep(150)

  /* 2 */ if (from.x === to.x && from.y === to.y) return true;
  /* 3 */ let neighbours = getNeighbours(from.x, from.y);
  /* 4 */ for (let n in neighbours) {
      /* 1 */   if (visited[neighbours[n].y][neighbours[n].x] === 0){
            /* 1 */ if (await findPath(neighbours[n], to)) return true  
                } 
          }
  /* 5 */ visited[from.y][from.x] = false;
  /* 6 */ return false; 
}

const maze = [
  [0,1,1,1,1,1,1,1,1,1,1,1],
  [0,0,0,0,0,1,0,1,1,1,1,1],
  [1,1,0,1,0,1,0,1,1,1,1,1],
  [1,1,0,1,0,0,0,0,1,1,1,1],
  [1,1,0,1,1,0,1,1,1,1,1,1],
  [1,1,0,1,1,0,1,1,1,1,0,1],
  [1,1,0,0,1,1,1,1,1,0,0,1],
  [1,1,0,1,1,0,0,0,1,0,1,1],
  [1,0,0,0,1,0,1,1,1,0,0,1],
  [1,0,1,0,0,0,0,0,0,0,1,1],
  [1,0,0,0,1,1,1,1,1,0,1,1],
  [1,1,1,1,1,1,1,1,1,0,0,0]]

const visited = [
  [0,0,0,0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0,0]]

const c = document.querySelector("canvas");
const h2 = document.querySelector("h2");
const ctx = c.getContext("2d");
const f = {x: 0, y: 0 }  // from (red)
const t = {x: 11, y: 11} // to (green)
const CANVAS_SIZE = 120;
const sz = CANVAS_SIZE / maze.length; 

function drawMaze() {
  for (let y = 0; y < maze.length; y++ ){
    for (let x = 0; x < maze[0].length; x++ ){
          ctx.fillStyle = maze[y][x] === 0 ? "white": "black";  
          ctx.fillRect(x * sz, y * sz, sz, sz);
          if (visited[y][x]){
            ctx.fillStyle = "lightblue"
            ctx.fillRect(x * sz, y * sz, sz, sz);
          } 
      }
   }
   // draw start point
   ctx.fillStyle = "red" 
   ctx.fillRect(f.x * sz, f.y * sz, sz, sz);
   // draw finish point
   ctx.fillStyle = "green"
   ctx.fillRect(t.x * sz, t.y * sz, sz, sz);
} 

function isValidStep({x, y}){
  if (x < 0 
    || x >= maze[0].length 
    || y < 0 
    || y >= maze.length
  ) return false
  return true  
}

function getNeighbours(x, y){
  let neighbours = {}
  if (isValidStep({x: x - 1, y}) 
    && maze[y][x - 1] === 0) {
    neighbours.left = { x: x - 1, y}
  }  
  if (isValidStep({x, y: y - 1}) 
    && maze[y - 1][x] === 0) {
    neighbours.top ={x, y: y - 1}
  }  
  if (isValidStep({x: x + 1, y}) 
    && maze[y][x + 1] === 0) {
    neighbours.right = {x: x + 1, y }
  }  
  if (isValidStep({x, y: y + 1}) 
    && maze[y + 1][x] === 0) {
    neighbours.bottom = {x, y: y + 1}
  }  
  return neighbours
}

function sleep(ms) {
  return new Promise(resolve => setTimeout(resolve, ms));
}

async function test(){
  h2.textContent="?"
  const result = await findPath(f, t) ? "TRUE" : "FALSE"
  h2.textContent=result
}

test();
    <html>
  <head>
    <title></title>
    <meta content="">
    <style>
       canvas {
         border: 1px solid black;
         height: 120px;
         width:  120px;
       }
    </style>
  </head>
  <body>
    <canvas height="120" width="120"></canvas>
    <h2></h2>
  </body>
</html>

    Your task is to generate algorithms and check in this way.