algorithmprocedural

Generating a city/town on a grid (Simply my approach)

Problem

I am trying to make a city generator for a game that creates blocks that have a type (residential, industrial, commercial). All of my streets will be at 90 degrees and there for I want it to be blocky (instead of zig zagging).

Approaches

My first approach was picking a starting point and then randomly moving around the map for X number of moves. If I hit a dead end I back tracked some random number, kind of like a maze generator but this left me with lots of areas where roads where next to roads and roads that didn't travel in straight lines. I've also looked at using perlin noise, but I believe this two would give me roads that zig zagged to often.

Current Solution

I have come up with an approach that gives me pretty much what I want but I think its more complex than it needs to be or at least less efficient than it can be. Currently if I try to scale it up to a larger map it can take a few seconds to process.

JS Fiddle

https://jsfiddle.net/jrj2211/0exe9jne/

Algorithm

  1. Make a 2D grid and populate with empty cells
  2. Get a list of all possible cells and shuffle it
  3. Loop through each cell in shuffled list
    • Generate a randomly sized rectangle off of the cell and give it a unique ID
    • Give each cell in the rectangle the unique ID
    • Randomly pick its type (Residential, commercial, industrial)
  4. Scale the entire array up by 2
  5. Loop through the scaled up array and replace any tiles that have a neighboring tile with a different unique ID as a ROAD tile.

Scaling the array example (kind of like scaling an image):

[1, 2, 2]     [1, 1, 2, 2, 2, 2]
[1, 3, 3] =>  [1, 1, 3, 3, 3 ,3]
[4, 4, 4]     [4, 4, 4, 4, 4, 4]

The reason I scale up the grid is if I don't, any tile that was previously an area of 1x1 it would generate a map where two or more roads tiles would be neighbors.

Visualization

enter image description here

Final output

Note: This is not the same output as in the visualization

enter image description here

Summary

So to sum up my question, does anyone have any suggestions on how to make this more efficient or cleaner. I think its hard to write pseudo code for my current process so I think there's room for improvement. I also will have to make it even more complex to do things like removing cells that are 1x1 because no house would be surrounded by streets on all sides. I also don't want the city to be a perfect square (so I'd have to delete random zones along the border and close off their streets).

Solution

  • One way to circumvent the large array creation is by implementing the desired layout straight away. The key is to scale curTile instead of grid, note the change from ++ to +=2.

    // Get all cells as a 1 dimensional array
function GetAllCells() {
  var cells = [];
  for (var i = 0; i < mapSize; i+=2) {
    for (var j = 0; j < mapSize; j+=2) {
      cells.push(grid[i][j]);
    }
  }
  return cells;
}

    Back to back

    IsInBoundsScaled → IsInBounds

    newGrid → grid

    Iterate

    To get the same order of blocks, we have to double square sizes (ref minSize, maxSize).

    // Get a random order to loop through the cells
var checkOrder = shuffle(GetAllCells());
var minSize = 4;
var maxSize = 10;

for (var id = 1; id < checkOrder.length; id++) {
  var curTile = checkOrder[id];

  if (curTile.type == TYPES.NONE) {
    var direction = (Math.random() > .5 ? 1 : 0);
    var square_width = RandomRange(minSize, (direction ? maxSize : minSize));
    var square_height = RandomRange(minSize, (direction ? minSize : maxSize));

    var zones = [TYPES.RESIDENTIAL, TYPES.COMMERCIAL, TYPES.COMMERCIAL, TYPES.RESIDENTIAL, TYPES.INDUSTRIAL];
    var zone = zones[Math.floor(Math.random() * zones.length)];
    var color = getRandomColor();

    for (var i = 0; i < square_width; i+=2) {
      for (var j = 0; j < square_height; j+=2) {
        if (IsInBounds(curTile.i + i+1, curTile.j + j+1)) {
          grid[curTile.i + i][curTile.j + j].id = id;           // [x] O
          grid[curTile.i + i][curTile.j + j].type = zone;       //  O  O

          grid[curTile.i + i+1][curTile.j + j].id = id;         //  x [O]
          grid[curTile.i + i+1][curTile.j + j].type = zone;     //  O  O

          grid[curTile.i + i][curTile.j + j+1].id = id;         //  x  O
          grid[curTile.i + i][curTile.j + j+1].type = zone;     // [O] O

          grid[curTile.i + i+1][curTile.j + j+1].id = id;       //  x  O 
          grid[curTile.i + i+1][curTile.j + j+1].type = zone;   //  O [O]
        }
      }
    }
  }
}

    JS Fiddle Fork

    https://jsfiddle.net/7srfrx55/

    myTown