The speed of the doors

A lesson I learned from Super Comrade Oriam is that as much as I hate to admit it, runtime speed is a great equalizer among games. SCO was bloated, and probably relied too heavily on it's physics simulator. The game ran well, but only on pretty new machines.

When I found doors in the post below, I used a Tile object. When I wrote the rotating 2D array code, I also included twin methods that rotated an array of ints. Is the int rotation faster? I don't know, but it certainly can't be slower. So I took a look at my findDoors() method on my Tile class, and thoght, "How can I make this work with just integers?"

* * *

C# has support for enums, as any good high-level language does. So instead of worrying about "Blocks" and "Block types" I translated all the info I would need into an enum. Essentially, the enum is the tileType, meaning I don't have to compare strings when I want to figure out Block types.

I had to get rid of the idea of a 'visited' block, or at least, the idea of a boolean that lives on the Block object. That changed the logic of my findDoors() in such a way that I couldn't figure out how to move forward. It was one of those instances where I just had to put the idea on a back burner, and let it simmer.

After about a week, something clicked and I knew I knew the answer, I just had to code it. Instead of checking whether or not a block was 'visited', I simply gave it a new BlockType of 'Visited.' 'Visited' is only given to door blocks that have been visited by one of the Peek() methods. So when looking at a door to figure out the width, it must simply be a BlockType.Door. When Peeking() right or down to determine the width of a door, though, either BockType.Door or BlockType.Visited will count toward the width. This is because Doors can share corners. Also, Since each Block is only looked at once, this also guarantees that I won't accidentally make duplicate doors.

Pretty exciting if I say so myself.

XNA and Drawable Game Components

XNA has this feature of letting your classes inherit from DrawableGameComponent, or GameComponent. What this inheritance does is let you write your own overridden Draw, Update, Initialize, etc. methods that will be executed during the corresponding base.* call in the main game class.

The overridden Draw, however, does not take a spritebatch, or anything else but gameTime, though. So how do you actually draw anything in those methods? The answer is two-fold:

1. Don't make too many classes that actually draw something. Make more 'master classes' that draw everything contained in them, like maps or menus.
2. Game.Services.GetService

"Game.Services.GetService?" you say, "how does that do anything?" To that I say, "ah, it lets you pull generic services defined on the game!" So when your spriteBatch gets initialized in the main game class:

spriteBatch = new SpriteBatch(GraphicsDevice);

you can add it to the services of the game:

Services.AddService(typeof(SpriteBatch), spriteBatch);

and pull this service from any class:

spriteBatch = (SpriteBatch)Game.Services.GetService(typeof(SpriteBatch));

Just remember to declare your own spriteBatch variable in the subclass, and pull it from the game some point after it's been initialized!

There are very few articles or threads I could find that dealt with this exact problem. Most ranged from either a really simple drawing that occured in the main game Draw(), or more complex drawing that didn't use a spritebatch, at least not on the top level. I finally found an article here that was simple and consice enough for me to decypher what was going on. Props to the author!

Rotating a 2-D array

Not as easy as you would think:

public static Object[,] rotateClockWise(Object[,] inArray)
        {
            int width = inArray.GetLength(1);
            int height = inArray.GetLength(0);
            Object[,] outArray = new Object[width, height];

            for (int i = 0; i < width; i++)
            {
                for (int j = 0; j < height; j++)
                {
                    outArray[i, j] = inArray[height - 1 - j, i];
                }
            }

            return outArray;
        }

        public static Object[,] rotateCounterClockWise(Object[,] inArray)
        {
            int width = inArray.GetLength(1);
            int height = inArray.GetLength(0);
            Object[,] outArray = new Object[width, height];

            for (int i = 0; i < width; i++)
            {
                for (int j = 0; j < height; j++)
                {
                    outArray[i, j] = inArray[j, width - 1 - i];
                }
            }

            return outArray;
        }

Doors have been found!

Here is what I ended up using to find all doors in a tile. It could use a little refactoring, but it works!

        private List findDoors()
        {
            List foundDoors = new List();

            for (int i = 0; i < blockGrid.GetLength(0); i++)
            {
                for (int j = 0; j < blockGrid.GetLength(1); j++)
                {
                    if (blockGrid[i, j].type == "door" && !blockGrid[i, j].visited)
                    {
                        foundDoors.AddRange(figureWidth(i, j));
                        blockGrid[i, j].visited = true;
                    }
                }
            }

            return foundDoors;
        }

        //Figures width of a door. Will check both horizontally and vertically.
        private List figureWidth(int i, int j)
        {
            List doors = new List();
            int width = 1;
            Vector2 position = new Vector2(i, j);

            width = PeekRight(i, j, width);

            if (width > 1)
            {
                doors.Add(new Door(width, position, Orientation.Horizontal));
            }

            width = 1;
            width = PeekDown(i, j, width);

            if (width > 1)
            {
                doors.Add(new Door(width, position, Orientation.Vertical));
            }

            if (doors.Count == 0)
            {
                doors.Add(new Door(1, position, Orientation.None));
            }

            return doors;
        }

        private int PeekRight(int i, int j, int width)
        {
            if (DoorOnRight(i, j))
            {
                width = PeekRight(i, j + 1, width + 1);
                blockGrid[i, j + 1].visited = true;
                if (DoorBelow(i, j + 1)) 
                {
                    blockGrid[i, j + 1].visited = false;
                }
            }
            return width;
        }

        private int PeekDown(int i, int j, int width)
        {
            if (DoorBelow(i, j))
            {
                width = PeekDown(i + 1, j, width + 1);
                blockGrid[i + 1, j].visited = true;
                if (DoorOnRight(i + 1, j))
                {
                    blockGrid[i + 1, j].visited = false;
                }
            }
            return width;
        }

        private bool DoorOnRight(int i, int j)
        {
            bool doorOnRight = false;
            if (j < blockGrid.GetLength(1) - 1 && blockGrid[i, j + 1].type == "door")
            {
                doorOnRight = true;
            }
            return doorOnRight;
        }

        private bool DoorBelow(int i, int j)
        {
            bool doorBelow = false;
            if (i < blockGrid.GetLength(0) - 1 && blockGrid[i + 1, j].type == "door")
            {
                doorBelow = true;
            }
            return doorBelow;
        }

The trick was the VISITED boolean. I wondered how I could make sure to evaluate doors that were on corners, but I didn't see how to do the evaluation without going through the tile twice -- once looking for vertical doors, and once looking for horizontal doors.

This way, each block is evaluated one-at-a-time. As the width of a door is found, it sets each block to 'visited' status, so it doesn't look for another door. Unless, that is, there is another door block to the right or below the current block. Then, the block is considered not visited, and will still be evaluated when the one-at-a-time evaluation hits.

Think of it as like a going through a maze. If you come to an intersection, you want to consider that intersection 'unexplored' until you have a chance to come back and explore the other paths.

2-D Arrays

I graduated my Computer Science focus, you would've thought that I would know how to reference a 2-D array. First number is the array number, and the second number is the number within that array. I thought It was like a grid, where a reference took x/y coordinates. Instead, it's y/x. Lesson learned!

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.