代码之家 › 专栏 › 技术社区 › vxs8122

创造和解决一个没有边界的迷宫?

maze algorithm

vxs8122 · 技术社区 · 6 年前

好吧,假设你试着穿过迷宫的“北边”,你会回到同一个迷宫,但在“南边”。有点像在迷宫里航行。

有可能产生和解决这样一个迷宫吗?我还没有找到关于这个问题的文件。。。

1 回复 | 直到 6 年前

Richard 6 年前

关键是将迷宫从像素网格重新构造为图形。然后可以连接图形,使其形成圆环体。

威尔逊的算法可能特别容易理解。它的另一个优点是生成了一个统一的生成树,它是从空间中所有可能的生成树集合统一绘制的生成树。

执行以下操作:

随机选择任意顶点并将其添加到UST。
选择任何不在UST中的顶点并执行 loop-erasing random walk 直到遇到UST中的顶点。您可以修改此随机行走,使其在遇到边时环绕。
将在随机漫游中接触的顶点和边添加到UST。
重复2和3,直到所有顶点都添加到UST。

可以进行讨论 here 和 here .

下面是算法的草图(剩余的粉红色单元格是绘图例程中的一个人工制品,但不会影响结果)。

<!DOCTYPE html>
<meta charset="utf-8">
<style>

body {
  background: #000;
}

</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>

var width  = 200,
    height = 200;

var N = 1 << 0,
    S = 1 << 1,
    W = 1 << 2,
    E = 1 << 3;

var cellSize    = 4,
    cellSpacing = 4,
    cellWidth   = Math.floor((width - cellSpacing) / (cellSize + cellSpacing)),
    cellHeight  = Math.floor((height - cellSpacing) / (cellSize + cellSpacing)),
    cells       = new Array(cellWidth * cellHeight), // each cellâs edge bits
    remaining   = d3.range(cellWidth * cellHeight),  // cell indexes to visit
    previous    = new Array(cellWidth * cellHeight), // current random walk path
    i0, x0, y0; // end of current random walk

var canvas = d3.select("body").append("canvas")
    .attr("width", width)
    .attr("height", height);

var context = canvas.node().getContext("2d");

context.translate(
  Math.round((width - cellWidth * cellSize - (cellWidth + 1) * cellSpacing) / 2),
  Math.round((height - cellHeight * cellSize - (cellHeight + 1) * cellSpacing) / 2)
);

// Add the starting cell.
context.fillStyle = "white";
var start         = remaining.pop();
cells[start]      = 0;
fillCell(start);

// While there are remaining cells,
// add a loop-erased random walk to the maze.
context.fillStyle = "magenta";
d3.timer(function() {
  for (var k = 0; k < 50; ++k) {
    if (loopErasedRandomWalk()) {
      return true;
    }
  }
});

function loopErasedRandomWalk() {
  var i1;

  // Pick a location thatâs not yet in the maze (if any).
  if (i0 == null) {
    do if ((i0 = remaining.pop()) == null) return true;
    while (cells[i0] >= 0);
    previous[i0] = i0;
    fillCell(i0);
    x0 = i0 % cellWidth;
    y0 = i0 / cellWidth | 0;
    return;
  }

  // Perform a random walk starting at this location,
  // by picking a legal random direction.
  i1 = Math.random() * 4 | 0;
  if (i1 === 0) {
    if (y0 <= 0){
      y0 = cellHeight-1;
      i1 = i0 - cellWidth + cellWidth*cellHeight;
    } else{
      --y0;
      i1 = i0 - cellWidth;
    }
  } else if (i1 === 1) {
    if (y0 >= cellHeight - 1){
      y0 = 0;
      i1 = i0 + cellWidth - cellWidth*cellHeight;
    } else {
      ++y0;
      i1 = i0 + cellWidth;
    }
  } else if (i1 === 2) {
    if (x0 <= 0){
      x0 = cellWidth-1;
      i1 = i0+cellWidth-1;
    } else {
      --x0;
      i1 = i0 - 1;
    }
  } else { 
    if (x0 >= cellWidth - 1) {
      x0 = 0;
      i1 = i0-cellWidth+1;
    } else {
      ++x0;
      i1 = i0 + 1;
    }
  }

  // If this new cell was visited previously during this walk,
  // erase the loop, rewinding the path to its earlier state.
  if (previous[i1] >= 0) eraseWalk(i0, i1);

  // Otherwise, just add it to the walk.
  else {
    previous[i1] = i0;
    fillCell(i1);
    if (i1 === i0 - 1) fillEast(i1);
    else if (i1 === i0 + 1) fillEast(i0);
    else if (i1 === i0 - cellWidth) fillSouth(i1);
    else fillSouth(i0);
  }

  // If this cell is part of the maze, weâre done walking.
  if (cells[i1] >= 0) {

    // Add the random walk to the maze by backtracking to the starting cell.
    // Also erase this walkâs history to not interfere with subsequent walks.
    context.save();
    context.fillStyle = "#fff";
    fillCell(i1);
    while ((i0 = previous[i1]) !== i1) {
      fillCell(i0);
      if (i1 === i0 + 1) cells[i0] |= E, cells[i1] |= W, fillEast(i0);
      else if (i1 === i0 - 1) cells[i0] |= W, cells[i1] |= E, fillEast(i1);
      else if (i1 === i0 + cellWidth) cells[i0] |= S, cells[i1] |= N, fillSouth(i0);
      else cells[i0] |= N, cells[i1] |= S, fillSouth(i1);
      previous[i1] = NaN;
      i1 = i0;
    }
    context.restore();

    previous[i1] = NaN;
    i0 = null;
  } else {
    i0 = i1;
  }
}

function eraseWalk(i0, i2) {
  var i1;
  context.save();
  context.globalCompositeOperation = "destination-out";
  do {
    i1 = previous[i0];
    if (i1 === i0 - 1) fillEast(i1);
    else if (i1 === i0 + 1) fillEast(i0);
    else if (i1 === i0 - cellWidth) fillSouth(i1);
    else fillSouth(i0);
    fillCell(i0);
    previous[i0] = NaN;
    i0 = i1;
  } while (i1 !== i2);
  context.restore();
}

function fillCell(i) {
  var x = i % cellWidth, y = i / cellWidth | 0;
  context.fillRect(x * cellSize + (x + 1) * cellSpacing, y * cellSize + (y + 1) * cellSpacing, cellSize, cellSize);
}

function fillEast(i) {
  var x = i % cellWidth, y = i / cellWidth | 0;
  context.fillRect((x + 1) * (cellSize + cellSpacing), y * cellSize + (y + 1) * cellSpacing, cellSpacing, cellSize);
}

function fillSouth(i) {
  var x = i % cellWidth, y = i / cellWidth | 0;
  context.fillRect(x * cellSize + (x + 1) * cellSpacing, (y + 1) * (cellSize + cellSpacing), cellSize, cellSpacing);
}

d3.select(self.frameElement).style("height", height + "px");

</script>