dungeon generation using 2d arrays

Hey guys! I’ve decided to change the coding method of my roguelike because of a nudge from a fellow user to use 2d arrays. Using many(and i mean many) iterations and for loops, I figured out how to navigate through the array fairly easily in order to change values.
I decided to make rooms first, then worry about the paths.
I’ve managed to get rooms of various sizes to populate the grid.

1474017--81230--$Screen Shot 2014-01-05 at 10.14.13 PM.png

It usually generates with some overlap

as you can see, the rooms are yet to be connected by paths, which is what I’m trying to figure out.

this is what I have so far:

using UnityEngine;
using System.Collections;

public class roomspreadS : MonoBehaviour
{
	public GameObject tile;
	public GameObject path;
	public GameObject wall;
	const int worldSize = 50;
	int maxTiles = 0;
	static int[,] worldMap = new int[worldSize, worldSize];
	static bool[,] worldCheck = new bool [worldSize, worldSize];

	void Start ()
	{
		clear ();
		room ();
		//road ();
		make ();
	}
	//sets the positions for the initial room size
	void clear ()
	{
		for (int y=0; y<worldSize; y++) {
			for (int x=0; x<worldSize; x++) {
				var shuf = Random.Range (1, 100);
				if (shuf == 2  maxTiles < 20  y > 3  y < worldSize - 3  x > 3  x < worldSize - 3) {
					worldMap [x, y] = 1;
					maxTiles++;
				} else {
					worldMap [x, y] = 0;
				}
			}
		}
		maxTiles = 0;
	}

	void room ()
	{
		for (int a=0; a<3; a++) {
			for (int y=0; y<worldSize; y++) {
				for (int x=0; x<worldSize; x++) {
					if (worldCheck [x, y]) {
						continue;
					}
					if (x > 5  x < worldSize - 5  y > 5  y < worldSize - 5) {
						if (worldMap [x, y] == 1) {
							int shuffle = Random.Range (1, 4);
							for (int b=-shuffle; b<=shuffle; b++) {
								for (int c=-shuffle; c<=shuffle; c++) {
									worldMap [x + b, y + c] = 1;
									worldCheck [x + b, y + c] = true;
								}
							}	
						}
					}		
				}	
			}	
		}
		for (int y=0; y<worldSize; y++) {
			for (int x=0; x<worldSize; x++) {
				if (x > 0  x < worldSize - 1  y > 0  y < worldSize - 1) {
					if (worldMap [x, y] == 1  worldMap [x - 1, y] == 0  worldMap [x + 1, y] == 0  worldMap [x, y - 1] == 0  worldMap [x, y + 1] == 0) {
						worldMap [x, y] = 0;
					}
				}
			}
		}
		for (int y=0; y<worldSize; y++) {
			for (int x=0; x<worldSize; x++) {	
				worldCheck [x, y] = false;
			}
		}
	}
	
	void make ()
	{
		//place game objects
		for (int y=0; y<worldSize; y++) {
			for (int x=0; x<worldSize; x++) {
				if (worldMap [x, y] == 1) {
					Instantiate (tile, new Vector3 (x, 0, y), Quaternion.identity);
				}
				if (worldMap [x, y] == 2) {
					Instantiate (path, new Vector3 (x, 0, y), Quaternion.identity);	
				}
			}
		}
	}

	void Update ()
	{
	}
}

For paths, I’m having a hard time (1) figuring out where to start the paths and (2) how the paths finally stop at certain rooms.
I’ve considered using iterations to find out the distance between rooms and filling in the paths, but I haven’t had much luck.
maybe I’m looking at this the wrong way. Do you guys have any suggestions?

Ah yes, this brings back some fond memories… :slight_smile:

Dungeon generation for roguelike games is a pretty deep topic, and you can probably find some papers on it if you dig deep enough (since Rogue and its derivatives go so far back in time that people used to actually compose papers rather than just posting on forums and blogs!). But the general principles are (1) cheat wherever you can, and (2) it’s all right if it looks good.

With that in mind, there are a lot of different approaches, but here is what I would suggest.

  1. Start by writing a method that creates a path between any two points in the grid. There are several ways to do this, too, but an easy way is:
    a. Randomly choose between “x” and “y” (which axis you’re going to step in).
    b. Step towards the goal in that axis.
    c. If at the goal, you’re done.
    d. Otherwise, with some low probability (e.g. 10%), switch from “x” to “y” or vice versa.
    e. GoTo step b.

This will generate a path that is mostly straight, with a few turns – exactly how turny it gets is controlled by the probability in step d.

  1. Now, make this point-to-point pather a little bit smarter, by having it not touch the worldMap when the point it’s at happens to already be a room. In other words, it keeps stepping through the map, but it doesn’t convert a room square into a path square (since I see you treat these differently).

  2. Finally, if you have a list of rooms in the level, all that’s left is to call this pathing method for every room, with some randomly selected subset of the other rooms.

Note that if the random subset is less than 100%, then you will sometimes end up with a small set of rooms that aren’t connected to the larger set. But that’s OK; a lot of roguelikes had this feature on occasion. You could only get to the disconnected rooms by mining, teleporting, blasting, coming up/down from another level, etc.

Also note that the paths generated this way will often intersect… and that’s OK too. You’ll get branching corridors, T intersections, etc. The player will infer intention, even though there really wasn’t any!

Have fun,

  • Joe

There are also tons of roguelike variants out there that are open source, so you can grab the source and sniff around and see what people have tried.

One approach I like is in Jeff Lait’s POWDER game, which is (coincidentally) my favorite Roguelike:

http://www.zincland.com/powder/index.php?pagename=release

If you look in the source distro there is a rooms subdirectory that has a bunch of room templates, which gets you away from having pure rectangles for your rooms.

Another key insight that is very useful with Unity3D is to make your level at a higher abstraction layer, out of “cells” or “rooms and cells,” and once you are done generating it, only THEN turn it into a Unity3D scene made of blocks, planes, etc. This will mean you have a nice data representation to work with for collision, travel, spawning, etc. right away, rather than trying to infer it from what you “detect” in the scene.

Kurt

@joestrout so I took your advice to try and build paths between my rooms but I ran into another issue:

1475627--81410--$Screen Shot 2014-01-07 at 8.41.53 AM.png

the paths make some sort of grid like pattern, rather than making turns, which isn’t really what I want

do you know why this is happening?

here’s the updated code:

using UnityEngine;
using System.Collections;

public class roomspreadS : MonoBehaviour
{
	public GameObject tile;
	public GameObject path;
	public GameObject wall;
	const int worldSize = 50;
	int maxTiles = 0;
	bool change=false;
	bool start=false;
	bool stayfalse=false;
	int savenum=0;
	bool swap=false;
	static int[,] worldMap = new int[worldSize, worldSize];
	static bool[,] worldCheck = new bool [worldSize, worldSize];

	void Start ()
	{
		clear ();
		room ();
		road ();
		make ();
	}
	//sets the positions for the initial room size
	void clear ()
	{
		for (int y=0; y<worldSize; y++) {
			for (int x=0; x<worldSize; x++) {
				var shuf = Random.Range (1, 100);
				if (shuf == 2  maxTiles < 20  y > 3  y < worldSize - 3  x > 3  x < worldSize - 3) {
					worldMap [x, y] = 1;
					maxTiles++;
				} else {
					worldMap [x, y] = 0;
				}
			}
		}
		maxTiles = 0;
	}

	void room ()
	{
		for (int a=0; a<3; a++) {
			for (int y=0; y<worldSize; y++) {
				for (int x=0; x<worldSize; x++) {
					if (worldCheck [x, y]) {
						continue;
					}
					if (x > 5  x < worldSize - 5  y > 5  y < worldSize - 5) {
						if (worldMap [x, y] == 1) {
							int shuffle = Random.Range (1, 4);
							for (int b=-shuffle; b<=shuffle; b++) {
								for (int c=-shuffle; c<=shuffle; c++) {
									worldMap [x + b, y + c] = 1;
									worldCheck [x + b, y + c] = true;
								}
							}	
						}
					}		
				}	
			}	
		}
		for (int y=0; y<worldSize; y++) {
			for (int x=0; x<worldSize; x++) {
				if (x > 0  x < worldSize - 1  y > 0  y < worldSize - 1) {
					if (worldMap [x, y] == 1  worldMap [x - 1, y] == 0  worldMap [x + 1, y] == 0  worldMap [x, y - 1] == 0  worldMap [x, y + 1] == 0) {
						worldMap [x, y] = 0;
					}
				}
			}
		}
		for (int y=0; y<worldSize; y++) {
			for (int x=0; x<worldSize; x++) {	
				worldCheck [x, y] = false;
			}
		}
	}
	void road(){
		//iterate through the entire map in intervals of 10
		for (int y=0; y<worldSize; y+=5) {
			for (int x=0; x<worldSize; x+=5){
				//start digging a path when a room is found with the pathfinder
				for(int a=0; a<worldSize-1; a++){
					if(x+a<worldSize  x+a>0  y+a<worldSize  y+a>0){
					if(worldMap[x+a,y]==1  !swap){
						start=true;
						}
					else if(worldMap[x,y+a]==1  swap){
						start=true;
						}
						//when another room is touched, stop digging
					if(x+a+1<worldSize  x+a+1>0  y+a+1<worldSize  y+a+1>0){

						if(worldMap[x+a-1,y]==2  worldMap[x+a+1,y]==1  !swap){
						start=false;
						}
					else if(worldMap[x,y+a]==2  worldMap[x,y+a+1]==1  swap){
						start=false;
						}
					}
				}
					//randomize the switch between the x and y axis
						int chance=Random.Range(1,10);
						if(chance==3  !swap){
							swap=true;
						}
						if(chance==5  swap){
							swap=false;
						}
					    if(x+a<worldSize  x+a>0  y+a<worldSize  y+a>0){
						if(start  worldMap[x+a,y+savenum]==0  !change){
							worldMap[x+a,y+savenum]=2;
								if(swap){
								a=savenum;
								change=true;
							}
						}
					}
							    if(x+a<worldSize  x+a>0  y+a<worldSize  y+a>0){
								if(start  worldMap[x+savenum,y+a]==0  change){
							worldMap[x+savenum,y+a]=2;
								if(!swap){
								a=savenum;
								change=false;
									}
								}
							}
						}
					}
				}
			}
	void make ()
	{
		//place game objects
		for (int y=0; y<worldSize; y++) {
			for (int x=0; x<worldSize; x++) {
				if (worldMap [x, y] == 1) {
					Instantiate (tile, new Vector3 (x, 0, y), Quaternion.identity);
				}
				if (worldMap [x, y] == 2) {
					Instantiate (path, new Vector3 (x, 0, y), Quaternion.identity);	
				}
			}
		}
	}

	void Update ()
	{
	}
}

I think it’s because you didn’t break up the problem as I advised. :wink: You’re trying to do too much at once, which both makes it less likely to work, and harder to understand what’s wrong when it doesn’t work. Start by writing this function:

void MakePath(Vector2 startPos, Vector2 endPos) {
   // make a path that goes from startPos to endPos in fairly direct manner
}

This is different from your road() method, which appears to be trying to make all the roads at once, without the benefit of a simple helper method like this. Test the above method by putting, in your Start method, something like:

    MakePath(new Vector2(3,20), new Vector2(15,7));

Take out just about everything else, so you can clearly see the path that’s being made. Then, work on that MakePath method until it does what you want. (I sketched out an algorithm for that a couple posts up, but of course if you get stuck, post it here and we’ll try to help.)

Only then will you be ready to find all the rooms, and make paths among them.

I tried making a path from the x axis of startPos, to the x axis of endPos, which worked fine, but I couldn’t do it when making a path from the x axis of endPos to the final destination along the y axis. Instead I ended up with this:
1477100--81549--$Screen Shot 2014-01-08 at 10.40.11 AM.png
there would just be a tile at endPos, but no path leading there along the y axis

makepath code:

void makepath(Vector2 startPos, Vector2 endPos){
		int startX=System.Convert.ToInt32(startPos.x);
		int startY=System.Convert.ToInt32(startPos.y);
		int endX=System.Convert.ToInt32(endPos.x);
		int endY=System.Convert.ToInt32(endPos.y);
		for(int a=startX; a<endX; a++){
			if(worldMap[startX+a,startY]==0){
				worldMap[startX+a,startY]=2;
			}
		}
		for(int b=startY; b<endY; b++){
			if(worldMap[endX,startY+b]==0){
				worldMap[endX,startY+b]=2;
		}
	}
}

function call:

makepath (new Vector2(3,20), new Vector2(30,21));

I’m probably still missing out on something important. am I at least on the right track?

Yep, you’re getting there. There are two problems with this code. First, the way you’re doing these for-loops, they will work only when the end is greater than the start, but not when the end is less than the start. Second, you’re not including the endpoint (so in the Y of this example, which goes from 20 to 21, you’re only going from 20 to 20 — which is not much help at all). Third, if you always do X and then Y, you’ll always get a boring L-shaped path. (OK then, three problems. :))

Please give this (untested) code a try:

void makepath(Vector2 startPos, Vector2 endPos) {
   // Randomly choose between "x" and "y" (which axis you're going to step in).
   bool moveInX = (Random.value > 0.5f);
   Vector2 pos = startPos;
   // Repeat (until we find we're done)
   do {
      // fill in the current position
      if (worldMap[(int)pos.x, (int)pos.y] == 0) worldMap[(int)pos.x, (int)pos.y] = 2;
      // are we there yet?
      if (pos == endPos) return;
      // step towards the goal in our selected axis
      if (moveInX) {
         if (pos.x < endPos.x) pos.x++;
         else if (pos.x > endPos.x) pos.x--;
      } else {
         if (pos.y < endPos.y) pos.y++;
         else if (pos.y > endPos.y) pos.y--;
      }
      // with low probability, change which axis we're moving by
      if (Random.value < 0.1f) moveInX = !moveInX;
   }
}

I think that’ll do it, but there could be typos or other silliness, for which I apologize in advance… let me know if you can’t get it to work!

I get the error

and a few similar errors above that. It does’t make much sense to me as to why it would be expecting a while loop though.

Nuts, I’m sorry, I knew there’d be some silly mistake there… I accidentally slipped into another language. A ‘do’ in C# does indeed require a while condition at the end, but we don’t need one here. Please replace “do” with “while (true)” at the top of the loop.

It works!!! Thanks for all your help, I’ll try to figure the rest out by myself. One other question, since I was planning on turning this into a full game someday, can I use the code you gave me commercially if I credit you. Other than that, thanks so much. I wish I could return the favour somehow.

Shoot, in my view, if code is posted here it’s in the public domain — do with it whatever you want, no credit needed.

If you like, send me a copy of the game when it’s done; I’m sure I’ll enjoy playing it!