Downward: Lost within a 3D labyrinth.

[Valigarmander]

Don't mind the title for now. I'm not even sure what "Downward" means right now, I just needed something to put there and thought that sounded cool.

I've never finished a game of my own (though there was that one abortion in 2006), yet I still enjoy fiddling around with OHRRPGCE, and I like to sprite and come up with game concepts in my spare time. Since I don't like the crap I produce to go to waste, I thought I'd share it here instead. In particular, I'll be messing with OHRRPGCE and HSS, seeing what fun things I can do with them. I don't have any big concepts in mind just yet, but hey, maybe we'll go with the flow and see what happens?

Today I went about writing a script that randomly generates mazes, also known as "Baby's First Algorithm". Not only am I a greenhorn when it comes to creating complex scripts, I'm also terribly rusty with HSS. Therefore this has been quite an adventure. But somehow I got a working product, which I'm about to show off like a kindergartener with a macaroni-and-glue portrait.

My goal was to create a simple maze: one that covers the entire grid, with where you're able to get from any point in the maze to any other point (i.e. there are no sections completely blocked off from one another). I'll get to script in a minute, but first here's the premade map that I'm working with for this demo:



This is the blank slate that the maze will be chiseled into, complete with hideous placeholder graphics. Right now orange tiles represent solid walls, while black tiles (of which there are none at the moment) represent "excavated" passages. To make this thing a little easier to read:



The green tiles here represent "cells," as I will be calling them. Every single cell will be excavated, and every cell will be connected to every other cell in the end. As you can see, this simple demo map is 6x6 cells. Yellow tiles are the walls that lie between cells. Some of them will be excavated to create paths between cells, while others will remain solid walls. Orange tiles will always be solid. The orange tiles with the black x's designate the border of the map. All the fun stuff will happen in the middle.

That blank map is starting to bug me, so let's get started making a maze.

Code: Select all

variable (CurrentCellEReady)
variable (CurrentCellNReady)
variable (CurrentCellSReady)
variable (CurrentCellWReady)
variable (CurrentCellX)
variable (CurrentCellY)
variable (ExtraPathNumber)
variable (ExtraPaths)
variable (GoodToGo)
variable (MapSize)
variable (RandomNumberGod)
variable (TotalCells)
variable (VisitedCells)
variable (WallCleared)

We start off by naming all the lovely variables that will be put to use.

Code: Select all

MapSize := 6
TotalCells := MapSize*MapSize

MapSize determines the length (in cells) of the map that we'll be making. This variable can be changed to whatever number you want, though you need a premade map to support it, like my 6x6 map shown above. This script produces square-shaped mazes (since they're all I really need), though you could probably easily alter it to allow for rectangular mazes.

TotalCells gives the volume of the grid (in cells). Since it's a square map, the math is easy. In the case of my size-6 map, the total number of cells is 6 times 6, or 36.

Code: Select all

CurrentCellX := random(1,MapSize)*2
CurrentCellY := random(1,MapSize)*2

Here, the script picks a random cell to start out from. Note that since cells are always located on even-numbered map coordinates, the random output is multiplied by two. The upper-left corner of the map will always be at 2,2 on the map. In the case of our 6x6 maze, the bottom-right corner corresponds to 12,12.

Code: Select all

while &#40;VisitedCells < TotalCells&#41; do &#40;

	if &#40;&#40;read map block &#40;CurrentCellX,CurrentCellY--2&#41;&#41; == 2&#41; then &#40;CurrentCellNReady &#58;= 1&#41; else &#40;CurrentCellNReady &#58;= 0&#41;
	if &#40;&#40;read map block &#40;CurrentCellX,CurrentCellY+2&#41;&#41; == 2&#41; then &#40;CurrentCellSReady &#58;= 1&#41; else &#40;CurrentCellSReady &#58;= 0&#41;
	if &#40;&#40;read map block &#40;CurrentCellX--2,CurrentCellY&#41;&#41; == 2&#41; then &#40;CurrentCellWReady &#58;= 1&#41; else &#40;CurrentCellWReady &#58;= 0&#41;
	if &#40;&#40;read map block &#40;CurrentCellX+2,CurrentCellY&#41;&#41; == 2&#41; then &#40;CurrentCellEReady &#58;= 1&#41; else &#40;CurrentCellEReady &#58;= 0&#41;
	#Checks to see which neighboring cells are excavated and which aren't.

	if &#40;CurrentCellNReady == 1 || CurrentCellSReady == 1 || CurrentCellWReady == 1 || CurrentCellEReady == 1&#41; then &#40;
	#If at least one of the neighboring cells is excavated...

		while &#40;WallCleared == 0&#41; do &#40;
			RandomNumberGod &#58;= random&#40;1,4&#41;
			if &#40;RandomNumberGod == 1&#41; then &#40;
				if &#40;CurrentCellNReady == 1&#41; then &#40;
					write map block &#40;CurrentCellX,CurrentCellY--1,0&#41;
					write map block &#40;CurrentCellX,CurrentCellY--2,0&#41;
					CurrentCellY -= 2
					VisitedCells += 1
					WallCleared &#58;= 1
				&#41;
			&#41;
			if &#40;RandomNumberGod == 2&#41; then &#40;
				if &#40;CurrentCellSReady == 1&#41; then &#40;
					write map block &#40;CurrentCellX,CurrentCellY+1,0&#41;
					write map block &#40;CurrentCellX,CurrentCellY+2,0&#41;
					CurrentCellY += 2
					VisitedCells += 1
					WallCleared &#58;= 1
				&#41;
			&#41;
			if &#40;RandomNumberGod == 3&#41; then &#40;
				if &#40;CurrentCellWReady == 1&#41; then &#40;
					write map block &#40;CurrentCellX--1,CurrentCellY,0&#41;
					write map block &#40;CurrentCellX--2,CurrentCellY,0&#41;
					CurrentCellX -= 2
					VisitedCells += 1
					WallCleared &#58;= 1
				&#41;
			&#41;
			if &#40;RandomNumberGod == 4&#41; then &#40;
				if &#40;CurrentCellEReady == 1&#41; then &#40;
					write map block &#40;CurrentCellX+1,CurrentCellY,0&#41;
					write map block &#40;CurrentCellX+2,CurrentCellY,0&#41;
					CurrentCellX += 2
					VisitedCells += 1
					WallCleared &#58;= 1
				&#41;
			&#41;
		&#41;
		#Randomly chooses a neighboring, unexcavated cell and clears out a path to it.
		WallCleared &#58;= 0

	&#41; else &#40;
	#If none of the neighboring cells are excavated...

		while &#40;GoodToGo == 0&#41; do &#40;
			CurrentCellX &#58;= random&#40;1,MapSize&#41;*2
			CurrentCellY &#58;= random&#40;1,MapSize&#41;*2
			if &#40;&#40;read map block &#40;CurrentCellX,CurrentCellY&#41;&#41; == 0&#41; then &#40;GoodToGo &#58;= 1&#41;
		&#41;
		#Selects a new, excavated cell to work from.
		GoodToGo &#58;= 0

	&#41;

&#41;

Oh boy, here comes the big part! First, the script checks to see which neighboring cells have been excavated and which haven't. (When the maze generation begins, obviously none of them have, but later on this is important.) If one or more neighboring cells are unexcavated, then one of those unexcavated cells will be chosen at random. That cell along with the wall between it and the current cell will be excavated. Then the new cell becomes the current cell, and the script loops back to checking which neighboring cells have or haven't been excavated.

(When reading map blocks, 0 is the excavated black tile, 1 is the X-orange border tile, and 2 is the plain orange wall tile. The script will never attempt to excavate a border tile.)

If the script finds that all neighboring cells have been excavated, then it will randomly select another excavated cell and try from there. The script continues until every cell on the grid has been visited.

Code: Select all

ExtraPathNumber := random(1,TotalCells/3)
	
while &#40;ExtraPaths < ExtraPathNumber&#41; do &#40;
	
	CurrentCellX &#58;= random&#40;1,MapSize&#41;*2
	CurrentCellY &#58;= random&#40;1,MapSize&#41;*2
	#Selects a new cell to work from.
	
	RandomNumberGod &#58;= random&#40;1,4&#41;
	
	if &#40;RandomNumberGod == 1&#41; then &#40;
		if &#40;&#40;read map block &#40;CurrentCellX,CurrentCellY--2&#41;&#41; == 0&#41; then &#40;
			write map block &#40;CurrentCellX,CurrentCellY--1,0&#41;
		&#41;
	&#41;
	if &#40;RandomNumberGod == 2&#41; then &#40;
		if &#40;&#40;read map block &#40;CurrentCellX,CurrentCellY+2&#41;&#41; == 0&#41; then &#40;
			write map block &#40;CurrentCellX,CurrentCellY+1,0&#41;
		&#41;
	&#41;
	if &#40;RandomNumberGod == 3&#41; then &#40;
		if &#40;&#40;read map block &#40;CurrentCellX--2,CurrentCellY&#41;&#41; == 0&#41; then &#40;
			write map block &#40;CurrentCellX--1,CurrentCellY,0&#41;
		&#41;
	&#41;
	if &#40;RandomNumberGod == 4&#41; then &#40;
		if &#40;&#40;read map block &#40;CurrentCellX+2,CurrentCellY&#41;&#41; == 0&#41; then &#40;
			write map block &#40;CurrentCellX+1,CurrentCellY,0&#41;
		&#41;
	&#41;
	#Attempts to break down a wall.

	ExtraPaths += 1

&#41;

This little bit of script here is just to make the maze a bit more interesting. It simple goes around knocking down a few extra walls, adding circular paths to the maze. Again, you can mess around with the numbers a little. I have the number of attempts the script will make set to a third of the TotalCells variable. Higher than that and there will be tons of loops and circular paths in the maze; lower than that and it'll be closer to a "perfect maze."

That's all there is to the script (for now). When you run it, you'll get something like these:







Pretty nifty, huh? And just for one, here's what a 64x64 randomly-generated maze looks like:



The script works very quickly. Even that 64x64 maze I just posted was generated instantaneously. Still, I'm sure my script is less efficient than it would be had it been written by someone more experience than I; feel free to share criticism.

That's all I have for now. Maybe next time I'll add more features to the generation... perhaps start and finish spots, rooms, different wall types, randomly-placed objects and other features. Share any comments or suggestions you have. Peace out.

[Bob the Hamster]

Very nice!

The maze looks great, and the generation time is fast.

I think it might already be better than my own maze-generating algorithm in Crypt of Baconthulhu :)

[TMC]

Cool!

I notice that it generates lots of 1x1 islands. Preventing these in an efficient way (rather than using pathfinding) probably isn't the easiest thing to do.

I wouldn't change too much in the scripts, (which look pretty efficient) but here are a few suggestions. Rather than using the GoodToGo variable, you can use the break command to simplify this block of code:

Code: Select all

      while (true) do (
         CurrentCellX := random(1,MapSize)*2
         CurrentCellY := random(1,MapSize)*2
         if (read map block (CurrentCellX,CurrentCellY) == 0) then (break)
      ) 

You can get rid of the WallCleared variable in the same way.

I strongly suggest defining constants for the 3 types of tiles rather than using 0, 1, 2. That would make it a lot easier to read.

Would you consider posting this on the wiki as an example script?

By the way, anyone interested in maze generation should have a look at these beautiful visualised algorithms.

[Valigarmander]

^ Much appreciated! I didn't know about that break command. And I'd be glad to put this on the wiki.

Messed around with the script a little more today. First off, changed it so there is no need to create a "blank slate" map for the script to work with. The script now generates the slate by itself.

Code: Select all

while &#40;PrinterY < &#40;&#40;MapSize*2&#41;+3&#41;&#41; do &#40;

	while &#40;PrinterX < &#40;&#40;MapSize*2&#41;+3&#41;&#41; do &#40;
		if &#40;PrinterX < 2 || PrinterY <2> &#40;MapSize*2&#41; || PrinterY > &#40;MapSize*2&#41;&#41; then &#40;write map block &#40;PrinterX,PrinterY,1&#41;&#41; else &#40;write map block &#40;PrinterX,PrinterY,2&#41;&#41;
		PrinterX +=1
	&#41;
	PrinterY += 1
	PrinterX &#58;= 0

&#41;

Messing around with the MapSize variable changes how the size of the slate generated. The script just moves from left to right, writing either a border tile or wall tile, and then starting over at the next row once it reaches the edge. Like a typewriter!

I also added a few features to the generation algorithm. Mazes now have an entrance and an exit, as well as a number of treasure chests.



These three features only appear in nooks surrounded by three walls, so they aren't blocking corridors or anything.

One more thing I added was a "room generator". This runs just before the maze generation phase. A prefabricated room is randomly selected, the script checks to see if there's room to place it at the randomly chosen position on the map, and if so, places it there. A number of such rooms are placed throughout the map. Then the maze script I showed you in my first post runs, and fills the rest of the map with labyrinth. Prefabs have their own special tiles, so the maze generation algorithm will avoid them the way it avoids border tiles, keeping the room intact. After this phase, the "doors" of the rooms are knocked down, connecting the rooms to the rest of the map.



Here's another 64x64 map. I changed the color of the chests to green to make it easier to see them here, though there's definitely more in this maze than are visible (this is just what the automap shows). At the moment the prefabs are all kind of lame (most are just empty square rooms, as you can see), but I'll make them more interesting within time. For now I just wanted to see if I could make it work.

[TMC]

Make sure to check "Disable HTML in this post" when posting scripts, otherwise the angle brackets cause parts of the scritp to get eaten, as happened there.

Looks like you're using about 4 prefabs there? How are you placing the doors for the prefab rooms?

Are you counting the total number of tiles that all the rooms take up and subtracting that when generating the maze? You have to be careful here otherwise you could end up with a maze that's not connected. But simply counting tiles (correctly) should be sufficient. Also, it looks like you're not allowing the prefabs to be immediately adjacent? That prevents them from being able to randomly cut off a corner of the map (with very low probability).

[Valigarmander]

For now the doors are built right into the prefab. This means most prefabs are variations on the same thing (i.e. "3x3 room with a door on the west side, 3x3 room with a door on the north side, 3x3 room with a door on the west and north side...). Next thing I wanted to do was make it so the script randomly determines where and how many doors are placed. That would save a ton of space in the script, for sure.

When the script places a room, it adds the proper number of cells to the VisitedCells variable. So a 3x3 room would add 9 to the count. I actually forgot to include this in the first draft, and it caused the script to get stuck in an endless loop because it became impossible for VisitedCells to equal TotalCells.

The prefabs include the room and its surrounding walls. An example prefab might look like this:

Code: Select all

### ###
#. . .#
#     #
#. . .#
#     #
#. . .#
### ###

# = wall
. = cell

The room generation algorithm will never try to build a room overlapping a border wall or another room, ensuring that rooms will always have a buffer around them at least one cell wide. This prevents any areas from getting cut off.

[TMC]

Incidentally, how are drawing those prefabs? A long list of writemapblocks? There's much nicer ways of doing it.

The most flexible is to draw the prefabs on a spare map in the map editor, and then use a script which reads those tiles into an array (I would just use globals), like so:

Code: Select all

# array is the global variable number to start writing at
script, load room, array, x, y, w, h, begin
  variable(idx, xi, yi, layer)
  writeglobal(array, w)
  writeglobal(array + 1, h)
  idx := array + 2
  for (xi, x, x + w -- 1) do (
    for (yi, y, y + h -- 1) do (
      for (layer, 0, 0) do (   #as many layers as needed
        writeglobal(idx, read map block (xi, yi, layer))
        idx += 1
      )
    )
  )
end

And then you would have the opposite script to write the room back out. Before drawing the maze you'd teleport to the spare map and load in all the rooms.

The other alternative is to draw the rooms in your scripts, using strings. Like so:

Code: Select all

script, draw room 1, x, y, begin
  $1= "### ###"
  $1+ "#. . .#"
  $1+ "#     #"
  $1+ "#. . .#"
  $1+ "#     #"
  $1+ "#. . .#"
  $1+ "### ###"
  draw room(x, y, 7, 7)
end


script, draw room, x, y, w, h, begin
  variable(xi, yi, idx, char, tile)
  idx := 1
  for (yi, y, y + h -- 1) do (
    for (xi, x, x + w -- 1) do (
      char := ascii from string(1, idx)
      idx += 1
      switch(char) do (
        case (35)  # #
          tile := 2
        case (32)  # space
          tile := 1
        case (46)  # .
          tile := 0
      )
      write map block(xi, yi, tile)
    )
  )
end

Search online for a table of ASCII codes to see how to interpret the 'char' value.

I might have gotten a little carried away, but I needed those script for something else anyway...


I've noticed that painting a bunch of tiles in-game, such as removing a wall or adding a tree, is something that people want to do often enough that it would be great to build it into the engine. But I'm not sure how that should work...

[Valigarmander]

^ I really like that first method. I might try to implement that one.

~~~~~

So I have all these mazes now, and I was thinking of what to do with them. The obvious thing would be to have the player explore them, but the difficulty of a maze is diminished if you can see the whole thing from above.

This was what I came up with:



The randomly-generated map is still there, underneath a layer of slices that give you a first-person visual of the labyrinth. Your position in the maze is tracked by an NPC. Using the arrow keys to move will alter the position or direction of the NPC, and the visual display will update accordingly.

I've actually got a working demo at this point, if you fancy trying it out. Every level has an entrance (a big cyan circle) and an exit (a big red circle). Locating and walking into the exit will take you to the next level. Floors will get progressively larger the deeper you go. Chests are represented by big yellow circles, and do nothing at this point but stand around looking pretty. You can hit F1 to open the automap, though it won't tell you where exactly you are. There's not much to do at the moment, although it it a surprisingly fun waste of time.

There's no bugs that I know of, though the "draw distance" is pretty short at the moment, and this can make walking through larger rooms a bit disorienting.

[Spoonweaver]

Love it!
I think feenicks is doing something almost exactly like this.
Can't wait to see which one turns out better.

[Bob the Hamster]

Nice! Any plans for monsters?

[Valigarmander]

^ Maybe. ;) I'm starting to develop a picture in my head of what I'd like to do with this.

[Spoonweaver]

ShiningInTheDarkness.ohr

[Gizmog]

You should do some kinda mini-map! Since you already got the tile data, it should be trivial but it'll blow people's sliming minds!

[Feenicks]

[Man, I should get a direction indicator in my own 3d maze... as well as a minimap or at least coordinates up]

But yeah, this seems really neat. I've been a bit negligent on my own 3d maze thing (which is a bit different from yours, seeing as it can have slightly tighter mazes and has the dubious utility of highlighting tiles with edges on them), seeing as I still need to throw in stuff for actually showing NPCs on the map and all, much less doors or any other sort of alternate walls or floors.

How are you doing the moving around, anyway? Is it just a dude walking around and then visualization happens, or is there something else going on? And what happens when the maze eventually fills up the entire map?

[Valigarmander]

I'd like to implement a minimap at some point. It'd make navigation a heck of a lot less confusing.

To answer your question, Phoenix, there is a NPC on the dungeon map that serves as the player's orientor. The script keeps track of the NPC's position and the direction it's facing. Pressing left or right makes the NPC rotate counter-clockwise and clockwise, respectively. Pressing up causes the NPC to jump ahead one tile (assuming there's nothing blocking it), and pressing down causes it to move backwards (again, if not blocked). The 3D visual updates every time the player moves or rotates: the old slices are discarded and a new set is drawn based on the player's new position and line of sight.

(I'd copy and paste the code here, but my damnable router is frazzled and I'm posting from my phone right now. )

As for the maze filling the entire map... The mazes increase in size by one cell on each axis for every two levels you descend. There is a cap at 64 cells though, which would take forever to reach (about level 128) and is freakishly huge anyway (64x64 cells equals 127x127 tiles). It won't get any bigger than that, but I don't think it needs to.