Pigeon Hole Stepping v2

Pigeon Hole Stepping v2

I had originally written an article on how to implement PHS here. Having found the maps generated slightly redundant I decided to take another look. Here are the steps taken to successfully generate a more realistic "town." It's essentially a drunken walker like Diffusion Limited Aggregation mixed with a hallway constraint that mimics the large part of PHS.

  1. Start somewhere in the middle, add this and all possible directions up to a certain dynamic length (I used a standard deviation of 1.4 with a mean of 5, ) as nodes: [{x,y,direction},...].
  2. We will be looping until all nodes and edges (we'll describe that shortly,) are gone.
  3. When we have node then check to see if the path between it's x,y and x2,y2 (given the length and direction) is clear. If it is, then add the entire path minus the start and end as edges, and add the end as a new node. Shuffle nodes after adding a new one. After building the path run through the path array randomly attempting to build a room in all directions. (this won't be entirely possible and will leave negative space to fill with edges.)
  4. If there are no nodes, repeat step 3 except with edges (this helps fill the map negative space.)
  5. After all nodes and edges are gone then cover all cells adjacent to floors with walls if it's empty.

I found it helpful to use this simple formula to generate hallway lengths with a mean and standard deviation constraint. Both the x and y would work fine, here we're using the y only.

// Given a mean and standard deviation, compute
// a random length
function getHallwayLength(){  
  let X = Math.random()*Math.PI*2,
      Y = Math.random(),
      r = hallwayLengthSigma*Math.sqrt(-2*Math.log(Y)),
      //x = r*Math.cos(X)+hallwayLengthMean,
      y = r*Math.sin(X)+hallwayLengthMean;

  return y|0||1; //Grid, can't have partial/0 lengths
} //end getHallwayLength()

About Nathaniel Inman

I'm a gamer, graphic designer, musician and software engineer. C++ and Javascript are my favorite two programming languages for which I develop exclusively in vim, tmux and zsh on Arch Linux.

Kansas City, Missouri http://www.theoestudio.com