Generating a Battle Space - Procedural Map Generation Using the Dungeon Building Algorithm

For the boarding battles in Infinity Raider I implemented a variation of the Dungeon-Building Algotihm. The basic idea of the Dungeon-Building Algorithm is to place a room in the center of the map (everything else is a wall) and then randomly pick walls connected with floor tiles and place random features (rooms, corridors etc.). In my implementation I placed the start room at the top of the map ("the bridge") and only used half the width of the map, so it can later be mirrored along the vertical axis. The only features used are rooms, larger rooms are created if rooms happen to lie next to each other. This combining of rooms only happens, because the implementation ignores the walls of rooms when checking for overlap. The hardest part to figure out probably is the detection of the floor tile and that a new feature needs to be build into the opposite direction. The methods "MirrorMap", "GenerateUnits" and "ParseMap" are ommited in the code listing. "MirrorMap" mirrors the map along the vertical axis. "GenerateUnits" randomly places units for the player and for the AI. "ParseMap" creates the needed GameObjects from the bool array.

using UnityEngine;
using System.Collections.Generic;

public static class MapGenerator {

private class Room
{
  public int width;
  public int height;
  public Vector2 position;

  public Room(int w, int h, Vector2 pos)
  {
    width = w;
    height = h;
    position = pos;
  }
}

public static GameObject[,] GenerateSpaceShip()
{
  int width = 30;
  int height = 30;

  bool[,] layout = new bool[width,height];

  Room bridge = new Room (5, 5, 
                          new Vector2 (width / 2, height - 3));
  AddRoomToMap (bridge, layout);

  int tries = 10000;
  for (int i = 0; i < tries; i++)
  {
    //pick random wall
    int x = Random.Range(0,width/2);
    int y = Random.Range(0,height);

    if(!layout[x,y])
    {
      bool left = false;
      bool right = false;
      bool top = false;
      bool bottom = false;
      //check for floor in neighbourhood
      if(x -1 >= 0)
      {
        right = layout[x-1,y];
      }
      if(x + 1 < width/2)
      {
        left = layout[x+1,y];
      }
      if(y - 1 >= 0)
      {
        top = layout[x,y-1];
      }
      if(y + 1 < height)
      {
        bottom = layout[x,y+1];
      }

      Vector2 roomPos = Vector2.one;
      int roomWidth = Random.Range(3,6);
      int roomHeight = Random.Range(3,6);

      if(left)
      {
        roomPos = new Vector2(x-1 - roomWidth/2,y);
      }
      else if(right)
      {
        roomPos = new Vector2(x + 1 + roomWidth/2,y);
      }
      else if(bottom)
      {
 roomPos = new Vector2(x, y-1 - roomHeight/2);
      }
      else if(top)
      {
        roomPos = new Vector2(x, y+ 1 + roomHeight/2);
      }

      if(!roomPos.Equals(Vector2.one))
      {
 Room nextRoom = new Room(roomWidth,roomHeight,roomPos);
 if(TestRoomPlacement(nextRoom,layout))
 {
   layout[x,y] = true;
   AddRoomToMap(nextRoom,layout);
 }
      }
    }
  }
  MirrorMap (layout);
  GenerateUnits (layout,10);
  return ParseMap(layout);
}

private static void AddRoomToMap(Room r, bool[,] map)
{
  Vector2 pos = r.position;
  for (int x =  (int)pos.x - r.width / 2;
           x <= (int)pos.x + r.width /2; x++) 
  {
    for(int y = (int)pos.y - r.height / 2;
            y <= (int)pos.y + r.height/2; y++)
    {
      map[x,y] = true;
    }
  }
}

private static bool TestRoomPlacement(Room r, bool[,]map)
{
  Vector2 pos = r.position;
  int width = map.GetLength (0);
  int height = map.GetLength (1);
  for (int x =  (int)pos.x - r.width / 2;
           x <= (int)pos.x + r.width /2; x++) 
  {
    for(int y = (int)pos.y - r.height / 2;
            y <= (int)pos.y + r.height/2; y++)
    {
      if(x < 0 || x >= width/2 || y < 0 || y >= height || map[x,y])
      {
        return false;
      }
    }
  }
  return true;
}

}

Where to go from here? It might be a good idea to replace the bool array with an int array and then post process the map with a cellular automaton (or something else) to place enemies, objects, decorations etc. Also the rooms should be stylized in some way, so that the player knows what kind of environment it is supposed to be. Thanks for reading and happy experimenting with your own space ships (or dungeons or ...)