Random River Generation

A few weeks ago, I did a tutorial on generating random dungeons. Today I'll continue the 'tradition' and show you a nifty way of generating random rivers or roads. You can see a modified version of the algorithm running here: River Generator.

To complete this tutorial you'll need a noise generator (Perlin, Simplex, Voronoi, etc...) as well as an implementation of the A* algorithm (or something similar).

Step 1

Generate a tile map. The map should be as big as the bounding box that encapsulates your path. That is, if your path stretches from [10, 10] to [110, 110], your tile map will be 100 x 100.

Step 2

Populate your map with random values based on whichever noise function you chose. Note that you can simply make it completely random but for best results, don't. In this screenshot, I've used Perlin noise to generate a map which I then drew by interpreting each cell's value as the green value.

Step 3

This is the important bit: Set up your A* function to calculate the F costs (distance from your source to your target, where the source is our river's starting point and the target is your river's endpoint) to include each cell's random value. Each cell's F cost will be equal to: distance to the target + cell's random value.

Step 4

Using your AI, build a path between the two points. Because we used the noise function to influence our F costs the path will be interesting and unique, rather than straight and boring.

Further Steps

You can also implement a little recursive function that will 'fill' an area where the river ends by interpreting the height at the endpoint and making the water tile overflow onto any tiles that are lower than your initial tile.

If you have any further questions, feel free to leave a message.

Random Dungeon Generation

For all of you who have ever wanted to do something like this but couldn't figure out what exactly that algorithm is trying to tell you to do: Here is the easiest way to generate a random (and ok looking) dungeon.

Note that this algorithm doesn't care if it cuts through another room to get to the room it's trying to connect to. To fix this, you can use the A* algorithm to go around certain rooms when placing hallways.

Also, there are two issues that you should keep in mind.

Firstly, it is possible for the while loop to go into an infinite loop for certain map sizes (or bad luck when placing rooms). One way to get around this might be to have a counter run in the while loop and exit the loop when the counter reaches some number.

Secondly, it is possible for some rooms to remain separate from all other rooms. This will be the case when two rooms connect to each-other and are too far away from any other rooms to have corridors pass through them. For simplicity, I've chosen to not factor that scenario into the algorithm.

Scroll down to see the algorithm

//Create Data Structure
map = new array[width][height]
for each value in the 2d array
     map[i][j] = empty_cell

//How many rooms?
minimum_rooms = (width * height) / 300
maximum_rooms = (width * height) / 150
room_count = random(minimum_rooms, maximum_rooms)

//Room sizes?
width_root = square_root(width * 2)
height_root = square_root(height * 2)
minimum_width = (width * 0.5) / width_root
maximum_width = (width * 2.0) / width_root
minimum_height = (height * 0.5) / height_root
maximum_height = (height * 2.0) / height_root

//Create rooms
roomList = new list
for i = 0 to room_count
{
   ok = false
   //This while loop runs until we find somewhere the room fits
   //There are faster ways of doing this but for the map sizes I'm
   //using, it serves my needs and is fast enough.
   while (!ok)
   {
      room.x = random(0, width)
      room.y = random(0, height)
      room.w = random(minimum_width, maximum_width)
      room.h = random(minimum_height, maximum_height)

      if (room outside bounds of map)
         continue

      if (room overlaps with other room)
         continue

      //If we reach this point, the room can be placed
      ok = true
      roomList.add(room)
   }
}

//Connect Rooms
connectionCount = roomCount
connectedCells = new list
for i = 0 to connectionCount
{
   roomA = roomList[i]
   roomB = random other room to connect to

   //Increasing this number will make hallways straighter
   //Decreasing this number will make halways skewer
   sidestepChance = 10
   pointA = random point in roomA
   pointB = random point in roomB

   //This is a type of drunken/lazy walk algorithm    
   while (pointB != pointA)
   {
      num = random(0, 100)
      if (num < sidestepChance)
      {
         if (pointB.x != pointA.x)
            increase/decrease pointB.x depending on where pointA.x is
            add new point to connectedCells
      }

      if (we didn't change the x position)
      {
         if (pointB.y != pointA.y)
            increase/decrease pointB.y depending on where pointA.y is
            add new point to connectedCells
      }
   }
}

//Create Map Data
for i = 0 to roomCount
{
   for every cell in a room
      map[x][y] = room_cell
}

for i = 0 to connectedCells
{
   for every cell where we put a connector earlier
      map[x][y] = hallway_cell
}

//Lastly, create walls using tessellation
for every cell that is empty but touches a room or corridor cell
   map[x][y] = wall_cell