The Random Dungeon That Isn't So Random pt. 2

A tile can have any number of doors, in any position in the tile -- they shouldn't be limited to the outside edges of a tile. This means that when other tiles are attached, simply having a door of the same width is not sufficient. The algorithm will have to handle:

1. There are no tiles that have a door of the same width.
2. There are no tiles that could be added that do not overlap an already placed tile.

The first way to handle these exceptions is to evaluate a different door in the dungeon. This means that the "bad" door will have to be marked as so, and can't be evaluated again. If there are no good doors available in the rest of the dungeon, there are two options:

1. Create a random door of a random width in a random location in the dungeon.
2. "Finish" the dungeon and place the exits and entrances.

Right now, I'm leaning toward option two, which leaves more up to the user to create good tiles. Perhaps display a message that tells the user the dungeon level was ended prematurely.

Doors

Doors are the crux of the dungeon, and there are still a few things about them that will be tricky.
Determining a door's width is straightforward:

1. Iterate through all the Tile's Blocks until youyou hit a "Door" block.
2. Mark this block as "evaluated"
3. Evaluate the blocks to the right and under the current block. Find where the door "continues" and count how many door blocks are reached in that direction until a non-door block is hit.
4. Do the same evaluation in the opposite direction. This will be the true width. Mark each door block as "evaluated" as they are evaluated.
5. When a non-door block is reached, the position of this block will be the door's position within the tile.
6. Add the door, with it's position and width, to the Tile's list of Doors.

So, when a tile is up for being placed, the door widths can be easily compared. It may also be useful to store the orientation of the door -- horizontal or vertical -- in order to easily know if the tile needs to be rotated. If the tile attempts to be placed and cannot fit without overlapping, the tile can be flipped horizontally or vertically, respectively. If the door is one pixel wide, it can be rotated 90, 180, or 270 degrees and placed if/when it fits.

However, this algorithm does not say what to do if the door shares a corner with another door...

The random dungeon that isn't so random

There is an SNES game I played when I was younger called Breath of Fire II. It was pretty standard RPG fare, except for the bonus dungeon.

Many RPGs have bonus dungeons to explore when you beat the game. Usually, the bonus dungeon has the hardest enemies in the game, and is not related to the story. The bonus dungeon in Breath of Fire II, however, was a Rogue-like dungeon. It was a dungeon that shared qualities with the game "Rogue," namely randomly generated levels with a focus on combat. It turned out to be my favorite part of the game.

Fast forward a few years. I created a Mario Bros. Clone named Super Comrade Oriam that used picture files to create playable levels. I liked this idea, so after I completed Super Comrade Oriam, I decided to create a Rogue-like RPG where random dungeon "tiles" could be easily created by the user with picture files.

That is where the problem lies.

All other random dungeon algorithms I have come accross are completely random. Either the algorithm spawns "rooms" that then get connected randomly with thin hallways, or the tiles to create the dungeon are premade by the designer, so he/she already knows how the tiles could fit together. The best example I found is here, but even this example is too random, and cannot be user defined. I want the user to create their own rooms, as well as hallways, that can lend to an overall style of a particualr set of dungeon levels. So the user can define a large, open dungeon with many columns, not just rooms that randomly sprout off other rooms.

I need to create an algorithm that can read in a tile, and figure out how that tile connects with other tiles. I have decided on some restrictions:

1. Tiles will require at least one "door" that will be an opening for other tiles.
2. Tiles that fit together will share at least one door of the same width.
3. A tile that can fit will be rotated and moved until the matching doors align.

This allows enough randomization to be new and unique every time, but not too unorganized. Because the doors have to be the same width, connected tiles must share some element of the same style. To place a new tile, a random available door will be chosen form the map to consider. When finished, place an entrance and an exit randomly on a blank space. This method poses some problems:

1. How do I determine the width of a door?
2. How do I know if a tile section is unreachable?
3. If placing between two tiles, do all doors have to match?

I must do more research, but this is a good place to start.

Introduction

I created this blog to detail my code-based creations. Too often, the people in this industry get caught up in the details. "My code is faster than your code!" they'll say, or, "How can you not know how to code a Bucket Sort?" Does an empty string equivalent to a null string? Who cares?
We need to get beyond the point of debating who's right and who's wrong, and remember that coding is an art form. Sure, there are "faster" ways to code things, but in the end there is no "right" or "wrong." Slower code is easier to understand and conceptualize just as faster code is faster. Inline if statements? Who gives a damn.
The stereotypical software engineer is antisocial. He is territorial, judgmental, and does not know how to communicate. He does not see out of his own box. I hope we can move forward and get past this stereotype. We are artists. We create something from nothing. Lets debate our creations with gusto on the ideas behind it, not the brushwork.