制作地牢地图生成器：卡在门上

Question

我制作了一个原始的地牢生成器（纯 JavaScript）来创建附近的房间。 Link 一段工作代码在 post 的底部。

现在我卡住了：我需要制作一个好的门和房间之间的通道系统，但我发现很难想出一个合适的算法。从技术上讲，没有问题：在墙上打洞很容易，甚至可以确保地牢的所有部分都相互连接。

问题是找到一个合适的连通房间的想法。拧紧所有可能的连接并关闭多余的？选个大房间，从里面拉出几条走廊，然后把剩下的房间连到公用系统？从一个角落开始，乱走直到所有房间都连通？

如果有任何想法或建议，我将不胜感激。

更新。问题解决了。在 raul.vila 的帮助下，可以使算法进入工作状态。现在生成器会执行到达每个房间所需的最少门数，然后创建几个额外的门来改善地牢的连通性。

旧代码：https://jsfiddle.net/Gerasim/f2a8ujpy/3/

最终代码：https://jsfiddle.net/Gerasim/f2a8ujpy/29/

var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");

const DWIDTH = 32; // Dungeon width
const DHEIGHT = 32; // Dungeon height
const ROOMINTERVAL = 8; // Room density (3+)
const MINROOM = 3; // Min room size. Must be ROOMINTERVAL - 2 or bigger
const EXTRADOORS = 5; // Additional doors for better connectivity

arrayInstruments();
genDungeon();
showDungeon();


// Displays primitive map of the dungeon
function showDungeon() {
  for (var x = 0; x < DWIDTH; x++) {
    for (var y = 0; y < DHEIGHT; y++) {
      switch (dungeon[x][y]) {
        case 0:
          ctx.beginPath();
          ctx.fillStyle = "lightgrey";
          ctx.rect(x * 20, y * 20, 18, 18);
          ctx.fill();
          break;
        case 1:
          ctx.beginPath();
          ctx.fillStyle = "black";
          ctx.rect(x * 20, y * 20, 18, 18);
          ctx.fill();
          break;
        case 2:
          ctx.beginPath();
          ctx.fillStyle = "black";
          ctx.rect(x * 20 + 1, y * 20 + 1, 16, 16);
          ctx.rect(x * 20 + 12, y * 20 + 6, 2, 4);
          ctx.stroke();
          break;
      }
    }
  }
}


// Generates dungeon of rooms and doors
function genDungeon() {

  // Fill full dungeon with walls
  dungeon = new Array();
  dungeon.dup(1, 0, 0, DWIDTH, DHEIGHT);

  // Create random seeds of growth in size MINROOM x MINROOM
  var seeds = new Array();
  while (true) {
    var free = dungeon.biggestFree(0, 0, 0, DWIDTH, DHEIGHT);
    if (free.biggest < ROOMINTERVAL) {
      break;
    } else {
      roomX = free.x + 1 + rnd(free.biggest - 1 - MINROOM);
      roomY = free.y + 1 + rnd(free.biggest - 1 - MINROOM);
      dungeon.dup(0, roomX, roomY, MINROOM, MINROOM);
      seeds.push({
        x: roomX,
        y: roomY,
        width: MINROOM,
        height: MINROOM,
        delete: "no"
      });
    }
  }

  var rooms = [];

  // Now we have seeds of growth in array rooms.
  // Lets try to expand seeds by moving their walls
  while (seeds.length > 0) {
    for (var i = 0; i < seeds.length; i++) {
      // Determine the directions in which the room can grow 
      var dirs = [];
      if (seeds[i].x >= 2 && dungeon.freeRect(0, seeds[i].x - 2, seeds[i].y - 1, 1, seeds[i].height + 2)) {
        dirs.push('left');
      }
      if (seeds[i].x + seeds[i].width < DWIDTH - 1 && dungeon.freeRect(0, seeds[i].x + seeds[i].width + 1, seeds[i].y - 1, 1, seeds[i].height + 2)) {
        dirs.push('right');
      }
      if (seeds[i].y >= 2 && dungeon.freeRect(0, seeds[i].x - 1, seeds[i].y - 2, seeds[i].width + 2, 1)) {
        dirs.push('up');
      }
      if (seeds[i].y + seeds[i].height < DHEIGHT - 1 && dungeon.freeRect(0, seeds[i].x - 1, seeds[i].y + seeds[i].height + 1, seeds[i].width + 2, 1)) {
        dirs.push('down');
      }

      // Now expand room in random direction
      if (dirs.length > 0) {
        dirs.shuffle();
        if (dirs[0] == 'left') {
          dungeon.dup(0, seeds[i].x - 1, seeds[i].y, 1, seeds[i].height);
          seeds[i].x--;
          seeds[i].width++;
        }
        if (dirs[0] == 'right') {
          dungeon.dup(0, seeds[i].x + seeds[i].width, seeds[i].y, 1, seeds[i].height);
          seeds[i].width++;
        }
        if (dirs[0] == 'up') {
          dungeon.dup(0, seeds[i].x, seeds[i].y - 1, seeds[i].width, 1);
          seeds[i].y--;
          seeds[i].height++;
        }
        if (dirs[0] == 'down') {
          dungeon.dup(0, seeds[i].x, seeds[i].y + seeds[i].height, seeds[i].width, 1);
          seeds[i].height++;
        }
      } else {
        seeds[i].delete = "yes";
        rooms.push(seeds[i]);
      }
      seeds = seeds.filter(o => o.delete == "no");
    }
  }

  // Make required doors
  var startRoom = rooms[0];
  startRoom.parentRoom = startRoom;
  connectToOtherRooms(rooms, startRoom);

  // Make extra doors
  var i = EXTRADOORS;
  var limiter = 1000; // protection from an infinite loop
  while (i > 0 && limiter > 0) {
    if (connectToRandom(rooms)) {
      i--;
    }
    limiter--;
  }
}

// Makes tree of rooms
function connectToOtherRooms(rooms, currentRoom) {
  var adyacentRoom = connectToAdyacent(rooms, currentRoom);
  if (adyacentRoom) {
    connectToOtherRooms(rooms, adyacentRoom);
  } else {
    if (currentRoom.parentRoom == currentRoom) {
      return;
    } else {
      connectToOtherRooms(rooms, currentRoom.parentRoom);
    }
  }
}

// Makes door to the adyacent room
function connectToAdyacent(rooms, room) {
  var nonVisitedRooms = rooms.filter(o => o != room && !o.parentRoom);
  for (var i = 0; i < nonVisitedRooms.length; i++) {
    var nonVisitedRoom = nonVisitedRooms[i];
    if (makeDoor(room, nonVisitedRoom)) {
      nonVisitedRoom.parentRoom = room;
      return nonVisitedRoom;
    }
  }
}


// Makes door to the random room nearby
function connectToRandom(allRooms) {
  var room = rnd(allRooms.length);
  for (var i = 0; i < allRooms.length; i++) {
    if (makeDoor(allRooms[room], allRooms[i])) {
      return true;
    }
  }
  return false;
}


// Makes door between two rooms
function makeDoor(room1, room2) {
  var walls = commonWalls(room1, room2);
  if (walls && !foundDoor(walls)) {
    walls.shuffle();
    dungeon[walls[0].x][walls[0].y] = 2;
    return true;
  } else {
    return false;
  }
}


// Checks if there is a door in walls already to avoid double doors
function foundDoor(walls) {
  for (var i = 0; i < walls.length; i++) {
    if (dungeon[walls[i].x][walls[i].y] > 1) {
      return true;
    }
  }
  return false;
}


// Returns array of cells between two rooms (if any)
function commonWalls(room1, room2) {
  var walls = new Array();
  var per1 = perimeter(room1);
  var per2 = perimeter(room2);
  for (var i = 0; i < per1.length; i++) {
    var common = per2.filter(o => o.x == per1[i].x && o.y == per1[i].y);
    if (common.length > 0) {
      walls.push(common[0]);
    }
  }
  if (walls.length > 0) {
    return walls;
  } else {
    return false;
  }
}


// Returns array of cells on the external perimeter of room
// Corner cells are excluded, since the door is not made there
function perimeter(room) {
  var per = new Array();
  for (x = room.x; x < room.x + room.width; x++) {
    per.push({
      x: x,
      y: room.y - 1
    });
    per.push({
      x: x,
      y: room.y + room.height
    });
  }
  for (y = room.y; y < room.y + room.height; y++) {
    per.push({
      x: room.x - 1,
      y: y
    });
    per.push({
      x: room.x + room.width,
      y: y
    });
  }
  return per;
}


// rnd(4): returns 0, 1, 2 or 3
function rnd(ceil) {
  return Math.floor(Math.random() * ceil);
}


// Several instruments that I need to work with arrays
function arrayInstruments() {

  // Shuffles array in random order
  Array.prototype.shuffle = function() {
    var j, temp;
    for (var i = 0; i < this.length; i++) {
      j = rnd(this.length);
      temp = this[i];
      this[i] = this[j];
      this[j] = temp;
    }
    return (this);
  }

  // Fills rectangle in 2D-array with filler
  Array.prototype.dup = function(filler, startX, startY, lengthX, lengthY) {
    for (var x = startX; x < startX + lengthX; x++) {
      if (!Array.isArray(this[x])) {
        this[x] = new Array();
      }
      for (var y = startY; y < startY + lengthY; y++) {
        this[x][y] = filler;
      }
    }
  }


  // Checks whether the specified area of the two-dimensional array is free of filler
  // If it is free, it returns true
  Array.prototype.freeRect = function(filler, startX, startY, lengthX, lengthY) {
    for (var x = startX; x < startX + lengthX; x++) {
      for (var y = startY; y < startY + lengthY; y++) {
        if (this[x][y] == filler) {
          return false;
        }
      }
    }
    return true;
  }


  // Returns the coordinates of the largest empty square.
  // If there are several equally large empty squares, returns the coordinates of the random
  Array.prototype.biggestFree = function(filler, startX, startY, lengthX, lengthY) {
    var found = new Array();
    for (biggest = Math.min(lengthX, lengthY); biggest > 0; biggest--) {
      for (var x = startX; x <= startX + lengthX - biggest; x++) {
        for (var y = startY; y <= startY + lengthY - biggest; y++) {
          if (this.freeRect(filler, x, y, biggest, biggest)) {
            found.push({
              x: x,
              y: y
            });
          }
        }
      }
      if (found.length > 0) {
        found.shuffle();
        return {
          biggest: biggest,
          x: found[0].x,
          y: found[0].y
        };
      }
    }
  }
}

Answer 1

我将尝试描述一种算法。这个想法是创建一棵树，从一个随机房间开始，并访问从当前房间到未访问过的相邻房间的所有房间。

这应该有效：

创建 currentRoom 指向随机初始房间的变量
设置currentRoom.parentRoom = currentRoom，一个识别初始房间的技巧
与 currentRoom：
1. list adyacents non-visited rooms (adyNonVisRooms)，你可以检查一个房间是否有 parentRoom 属性定义来查看它是否被访问过
2. 如果adyNonVisRooms.length > 0：
  1. 设置nextRoom = adyNonVisRooms[0]（非确定性结果可获得随机房间）
  2. 连接 currentRoom 与 nextRoom 添加门
  3. 设置nextRoom.parentRoom = currentRoom
  4. 设置currentRoom = nextRoom
  5. 转到 3
3. 如果adyNonVisRooms.length == 0：
  1. 如果currentRoom == currentRoom.parentRoom：
    1. 列出未访问过的房间（adyNonVisRooms）
    2. 如果adyNonVisRooms.length > 0：转到321
    3. if adyNonVisRooms.length == 0: 退出
  2. 如果currentRoom != currentRoom.parentRoom：
    1. 设置currentRoom = currentRoom.parentRoom
    2. 转到 3

我有一个工作版本，你需要做一些工作才能获得随机房间位置（函数 connectIfOnTop 和 connectIfOnRight）：Jsfiddle

var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");

const DWIDTH = 32; // Dungeon width
const DHEIGHT = 32; // Dungeon height
const ROOMINTERVAL = 8; // Room density (3+)
const MINROOM = 2; // Min room size. Must be ROOMINTERVAL - 2 or bigger

arrayInstruments();
genDungeon();
showDungeon();

function showDungeon() {
  for (var x = 0; x < DWIDTH; x++) {
    for (var y = 0; y < DHEIGHT; y++) {
      ctx.beginPath();
      ctx.rect(x * 20, y * 20, 18, 18);
      if (dungeon[x][y] == 1) {
        ctx.fillStyle = "black";
      } else {
        ctx.fillStyle = "lightgrey";
      }
      ctx.fill();
    }
  }
}

function genDungeon() {

  // Fill dungeon with walls
  dungeon = new Array();
  dungeon.dup(1, 0, 0, DWIDTH, DHEIGHT);

  // Create random seeds of growth in size MINROOM x MINROOM
  var rooms = new Array();
  while (true) {
    var free = dungeon.biggestFree(0, 0, 0, DWIDTH, DHEIGHT);
    if (free.biggest < ROOMINTERVAL) {
      break;
    } else {
      roomX = free.x + 1 + rnd(free.biggest - 1 - MINROOM);
      roomY = free.y + 1 + rnd(free.biggest - 1 - MINROOM);
      dungeon.dup(0, roomX, roomY, MINROOM, MINROOM);
      rooms.push({
        x: roomX,
        y: roomY,
        width: MINROOM,
        height: MINROOM,
        delete: "no"
      });
    }
  }

  var finalRooms = [];

  // Now we have seeds of growth in array rooms.
  // Lets try to expand seeds by moving their walls
  while (rooms.length > 0) {
    for (i = 0; i < rooms.length; i++) {
      // Determine the directions in which the room can grow 
      var dirs = [];
      if (rooms[i].x >= 2 && dungeon.freeRect(0, rooms[i].x - 2, rooms[i].y - 1, 1, rooms[i].height + 2)) {
        dirs.push('left');
      }
      if (rooms[i].x + rooms[i].width < DWIDTH - 1 && dungeon.freeRect(0, rooms[i].x + rooms[i].width + 1, rooms[i].y - 1, 1, rooms[i].height + 2)) {
        dirs.push('right');
      }
      if (rooms[i].y >= 2 && dungeon.freeRect(0, rooms[i].x - 1, rooms[i].y - 2, rooms[i].width + 2, 1)) {
        dirs.push('up');
      }
      if (rooms[i].y + rooms[i].height < DHEIGHT - 1 && dungeon.freeRect(0, rooms[i].x - 1, rooms[i].y + rooms[i].height + 1, rooms[i].width + 2, 1)) {
        dirs.push('down');
      }

      // Now expand room in random direction
      if (dirs.length > 0) {
        dirs.shuffle();
        if (dirs[0] == 'left') {
          dungeon.dup(0, rooms[i].x - 1, rooms[i].y, 1, rooms[i].height);
          rooms[i].x--;
          rooms[i].width++;
        }
        if (dirs[0] == 'right') {
          dungeon.dup(0, rooms[i].x + rooms[i].width, rooms[i].y, 1, rooms[i].height);
          rooms[i].width++;
        }
        if (dirs[0] == 'up') {
          dungeon.dup(0, rooms[i].x, rooms[i].y - 1, rooms[i].width, 1);
          rooms[i].y--;
          rooms[i].height++;
        }
        if (dirs[0] == 'down') {
          dungeon.dup(0, rooms[i].x, rooms[i].y + rooms[i].height, rooms[i].width, 1);
          rooms[i].height++;
        }
      } else {
        rooms[i].delete = "yes";
      }
      finalRooms = finalRooms.concat(rooms.filter(o => o.delete == "yes"));
      rooms = rooms.filter(o => o.delete == "no");
    }
  }

  var startRoom = finalRooms[0];
  startRoom.parentRoom = startRoom;
  connectToOtherRooms(dungeon, finalRooms, startRoom);
}

function connectToOtherRooms(dungeon, allRooms, currentRoom) {
  var adyacentRoom = connectToAdyacent(dungeon, allRooms, currentRoom);
  if (adyacentRoom) {
    connectToOtherRooms(dungeon, allRooms, adyacentRoom);
  } else {
    if (currentRoom.parentRoom == currentRoom) {
      return;
    } else {
      connectToOtherRooms(dungeon, allRooms, currentRoom.parentRoom);
    }
  }
}

// {x: 9, y: 12, width: 3, height: 6, delete: "yes"}

function connectToAdyacent(dungeon, allRooms, room) {
  var nonVisitedRooms = allRooms.filter(function(r) {
    return (r != room) && !r.parentRoom;
  });
  for (var i = 0; i < nonVisitedRooms.length; i++) {
    var nonVisitedRoom = nonVisitedRooms[i];
    if (connectIfAdyacent(dungeon, room, nonVisitedRoom)) {
      nonVisitedRoom.parentRoom = room;
      return nonVisitedRoom;
    }
  }
}

function connectIfAdyacent(dungeon, room1, room2) {
  return connectIfOnTop(dungeon, room1, room2) ||
    connectIfOnTop(dungeon, room2, room1) ||
    connectIfOnRight(dungeon, room1, room2) ||
    connectIfOnRight(dungeon, room2, room1);
}

function connectIfOnTop(dungeon, roomBase, room) {
  var roomBase_x1 = roomBase.x - 1;
  var roomBase_x2 = roomBase.x + roomBase.width;
  var roomBase_y1 = roomBase.y - 1;
  //var roomBase_y2 = roomBase.y + roomBase.height;

  var room_x1 = room.x - 1;
  var room_x2 = room.x + room.width;
  var room_y1 = room.y - 1;
  var room_y2 = room.y + room.height;

  if (
    room_y2 == roomBase_y1 &&
    (room_x1 < (roomBase_x2 - 1)) &&
    (room_x2 > (roomBase_x1 + 1))
  ) {
    dungeon[Math.max(room_x1, roomBase_x1) + 1][room_y2] = 0;
    return true;
  }
}

function connectIfOnRight(dungeon, roomBase, room) {
  var roomBase_x1 = roomBase.x - 1;
  //var roomBase_x2 = roomBase.x + roomBase.width;
  var roomBase_y1 = roomBase.y - 1;
  var roomBase_y2 = roomBase.y + roomBase.height;

  var room_x1 = room.x - 1;
  var room_x2 = room.x + room.width;
  var room_y1 = room.y - 1;
  var room_y2 = room.y + room.height;

  if (
    room_x2 == roomBase_x1 &&
    (room_y1 < (roomBase_y2 - 1)) &&
    (room_y2 > (roomBase_y1 + 1))
  ) {
    dungeon[room_x2][Math.max(room_y1, roomBase_y1) + 1] = 0;
    return true;
  }
}


// rnd(4): returns 0, 1, 2 or 3
function rnd(ceil) {
  return Math.floor(Math.random() * ceil);
}


// Several instruments that I need to work with arrays
function arrayInstruments() {

  // Shuffles array in random order
  Array.prototype.shuffle = function() {
    var j, temp;
    for (var i = 0; i < this.length; i++) {
      j = rnd(this.length);
      temp = this[i];
      this[i] = this[j];
      this[j] = temp;
    }
    return (this);
  }

  // Fills rectangle in 2D-array with filler
  Array.prototype.dup = function(filler, startX, startY, lengthX, lengthY) {
    for (var x = startX; x < startX + lengthX; x++) {
      if (!Array.isArray(this[x])) {
        this[x] = new Array();
      }
      for (var y = startY; y < startY + lengthY; y++) {
        this[x][y] = filler;
      }
    }
  }

  // Checks whether the specified area of the two-dimensional array is free of filler
  // If it is free, it returns true
  Array.prototype.freeRect = function(filler, startX, startY, lengthX, lengthY) {
    for (var x = startX; x < startX + lengthX; x++) {
      for (var y = startY; y < startY + lengthY; y++) {
        if (this[x][y] == filler) {
          return false;
        }
      }
    }
    return true;
  }


  // Returns the coordinates of the largest empty square.
  // If there are several equally large empty squares, returns the coordinates of the random
  Array.prototype.biggestFree = function(filler, startX, startY, lengthX, lengthY) {
    var found = new Array();
    for (biggest = Math.min(lengthX, lengthY); biggest > 0; biggest--) {
      for (var x = startX; x <= startX + lengthX - biggest; x++) {
        for (var y = startY; y <= startY + lengthY - biggest; y++) {
          if (this.freeRect(filler, x, y, biggest, biggest)) {
            found.push({
              x: x,
              y: y
            });
          }
        }
      }
      if (found.length > 0) {
        found.shuffle();
        return {
          biggest: biggest,
          x: found[0].x,
          y: found[0].y
        };
      }
    }
  }
}

* {
  padding: 0;
  margin: 0;
}

canvas {
  background: eee;
  display: block;
  margin: 0 auto;
}

<html>

<head>
  <title>Maze Generator</title>
  <meta charset="utf-8" />
</head>

<body>
  <div style="padding: 15;">
    <canvas id="canvas" width="640" height="640" style="background: lightgrey"></canvas>
  </div>
</body>

</html>

制作地牢地图生成器：卡在门上

Making dungeon map generator: stuck with doors

javascript

maps

path-finding

2d-games