Friday, August 22, 2008
Rendering in OpenGL
My last post brought up an important issue - rendering. Most Roguelikes use ascii to represent everything. Those that use tile graphics.....I'm not sure what they use for rendering. Like the title says, RogueRunner uses OpenGL. It's platform independent, clean and easy to use, and easy to learn. For those who might consider OpenGL there are excellent tutorials by Nehe that are a great kick start.
The biggest advantage of using OpenGL, at least in my mind, is the use of alpha blending. For those who don't know, alpha blending allows for images to use transparency so that when 1 image is painted on top of another, it doesn't completely cover the underlying image. For example, a sword tile is drawn on top of a floor tile. This can be done any number of times, and so facilitates layering.
RogueRunner makes extensive use of this. Most notably when rendering doors, stairs, and decorations. More specifically, the doors and stairs themselves are different tiles to be blended on top of whatever you want. This means that instead of having a set of tiles that have a common door but different background, you just have 1 door and as many background tiles as you want. Example:
Using this method means I don't have to store every combination of every type of door with every type of background. Just combine any door with any background!
Another of the big advantages of OpenGL is lighting. I'm using the Angband tileset made by David Gervais, and many of the tiles are dedicated to drawing the same texture at different light levels. OpenGL elliminates the need for this. Textures can be colored in any way you want. For example, the tiles around the player can be tinted slightly yellow to simulate torch light, or the cells around a fireball can be lit red as it travels towards its target, or the player's color can change when they're poisoned or petrified. All this and more with no changes at all to the tiles themselves.
The last thing I'll mention is the square grid. I'm not bound to it in any way with OpenGL, though I stick to it when rendering most things. Without adhering to the grid arrows can fly straight at their target, explosions can look better, creatures can be scaled to be bigger or smaller, and magic in general can be made to look better. None of this is done yet, but it's all planned for.
The bottom line is, OpenGL simplifies the task of rendering and adds certain abilities that a pure tile based approach couldn't produce.
Edited on: Friday, August 22, 2008 12:34 PM
Categories: General Programming
Door Mechanics
I don't know how other Roguelikes have implemented their doors. In RogueRunner, Cells have a pointer to a door object, which is NULL if there is no door. Here's a rundown of what the door object holds:
State - The state of the door i.e. closed, open, broken
Locked Rating - If this is greater than 0, the door is locked. The higher it is, the more difficult it is to pick the lock.
Hidden Rating - If this is greater than 0, the door is hidden. The higher it is, the more difficult it is to find the door by searching.
Key ID - If this holds a value, the door is magically locked. Magically locked doors can only be unlocked with the key with matching ID. This could be difficult to make work on completely random levels, but can easily be used when making hand designed levels through the level editor.
Door Set Index - There is a global array that defined the tiles to use for closed, open, and broken doors. A door just needs to know which set of tiles to use.
When a door is attempted to be opened or searched ( when hidden ), the door is passed a pointer to the creature trying to do it, and the door decides what happens. The ratings for locked and hidden doors determines how long it will take to succeed at the action. The exact numbers have yet to be finalized because I don't even have character stats finalized, but the idea is for the rating of doors to decrease on each attempt based on how good the character is at picking locks or searching. In the case of magically locked doors, the door simply checks the inventory of the creature opening the door and sees if they have the right key.
|Tuesday, August 19, 2008
Line of Site Using Shadowcasting
Now that I have some dungeons that I can actually move around in, line of site needs to be handled. There is an article at RogueBasin by Bjorn Bergstrom that explains in great detail a method called shadowcasting. If done correctly, this method actually avoids altogether cells that lie in shadowed areas. So even though everything is handled recursively, it's still very fast - especially when the player is in tighter locations, like a dungeon.
Even in open areas it can handle very large vision radii. I ran a test on an open 256 X 256 map with the character standing in the middle at 128, 128. With a vision radius of 128 it took 5 milliseconds to calculate. That's radius, so it basically checked the whole map. This took 1 millisecond to calculate:
The one thing I will add to his description is how I handled the different octants. The optimal solution is to write a different method for each octant. This is bulky and time consuming, and lots of code is duplicated. Instead, I wrote one method that uses a MapToOctant method whenever it actually looks up cells. The solution is simple and elegant.
|Monday, August 18, 2008
Dungeon Generation Part VI: Tunnelling
All of these rooms need to get connected. Since doors will get created at a separate time, all I need to do is gaurantee connectivity to all rooms. After considering all my options, I decided on the easiest way I could come up with, which involved a small change in the dungeon generation process as a whole. Dungeon generation can be summed up like this:
1. Create a room and randomly place it on the map using the block scheme.
2. Connect that room with the room created before it. Go to 1.
I doubt anybody has my algorithm memorized from before, so I bolded the difference - randomly placing rooms instead of scanning methodically for the first place it would fit. The reason for this change will become apparent when I explain the actual tunnelling code.
Tunnelling consists of 2 parts - carving out the main tunnel and connecting the 2 ends to the actual rooms. The end of a tunnel to a rectangle room is going to connect a little differently from a blob room or a chamber. So the main tunnel connects the outer edges of the room ( the square that surrounds a blob room, for example ), then separate code attaches it to the room.
The main tunnel has a few parameters that determine how often it changes directions, and how often kinks occur. A kink is when the tunnel turns perpendicular to where it should go. Adjusting the parameters allows for the tunnels to more closely match the feel of the rooms of the level.
The only other point of significance is that the tunnelling immediately stops when it touches any floor cell. Since rooms are placed 1 at a time and immediatly connected, I can always gaurantee that at any stage of the generation process there is complete connectivity in the dungeon. So bumping into any floor cell will connect me to the rest of the dungeon. Doing things this way makes life easier, and also makes the connectivity of the dungeon more interesting.
Since we're adding rooms after tunnels have been created, rooms are going to write over the top of tunnels and disrupt connectivity. To avoid this, the room drawing code just needed to be tweaked so that the outer walls of rooms skipped over already existing tunnels.
Here are a few screenshots of fully connected dungeons using all the room types so far. Keep in mind I'm using very plain tiles to emphasize the different parts of the dungeon, like rooms, walls of rooms, tunnels, etc:
The dungeon generator works! It's usable for the game, so I'm going to move on for now. Dungeon generation will be revisited in the future when it comes time to add doors, monsters, items, stairs, and room features. I've got some good ideas to add flavor beyond interesting room shapes. But for now I'm happy with it.
Edited on: Friday, August 22, 2008 12:34 PM
Categories: Dungeon Generation
Friday, August 15, 2008
Dungeon Generation Part V: Chambers
This will be the last description of room types until I get around to vaults ( which will be further down the road ). There is one type I'm not explaining, the overlapped room, which is simple - two rectangles criss-crossing each other. We'll instead be looking at chambers, which are a series of directly overlapping rooms. Here's an example so you know what I'm talking about:
This example shows a surrounding "courtyard" area drawn in the lighter color. These chambers will be rare and will house many strong monsters and valuable treasure. The algorithm to create the chamber is not that difficult:
1. This is still considered 1 large room, so up front I randomize just how much space of the true room the chambers will take up. Based on this I calculate a maximum number of tries to place a chamber room. This avoids infinite loops. Create a room list to hold all the rooms of the chamber.
2. Create a random room of appropriate size and position it randomly. Compare each room in the list to the new room and see how much they overlap.
3. If any of them overlap too much, don't draw the room and go back to 2. If none of the rooms overlap at all, it's not connected to the chamber, so don't draw the room and go back to 2.
4. Draw the room and add it to the list.
5. Go to 2.
This will create the system of rooms. The limits are up to you as far as overlapping goes. Currently it has to overlap at least 6 cells to be considered connected and can't overlap more than 40% of either the new room or the room in the list. The next part of the algorithm involves creating the courtyard.
1. Scan each cell of the entire room. If I'm on a normal wall If it borders a cell of type inner wall, draw a floor tile. This will surround the entire chamber will 1 floor cell.
2. Scan each cell of the entire room. If I'm on a normal wall and I border 3 floor cells, draw a floor tile 70% of the time. If I'm on a normal wall and I border more than 3 floor tiles, always draw a floor tile.
3. Go back to 2 'n' times, where n = the width of the courtyard.
The reason for the 70% on step 2 is that the courtyard starts to look a little too perfect. A little randomization goes a long way in this case. The only other issue making sure that the whole system is connected. I have some ideas how I'm going to do this, mostly involving flood filling and such. I haven't even implemented doors yet, so I'll leave this one for later.
Edited on: Friday, August 22, 2008 12:34 PM
Categories: Dungeon Generation
Tuesday, August 12, 2008
Dungeon Generation Part IV: Blob Rooms
The next type of room we'll look at are what I call blob rooms. There are a number of different methods out there for generating cave-like levels or cave-like rooms, but most of them didn't fit my needs. For one, I need to gaurantee connectivity in the room itself. The Cellular Automata algorithms I've seen can't gaurantee this. Next, I'm starting with a room of set width and height, so the room has bounds. Algorithms like the Drunken Walk may wander out of these bounds, and if I restrict the walk to the bounds nothing is keeping it from walking along the room edges, creating flat portions of the room. This is undesireable. Raycasting seemed like a lot of work, and the results I've seen don't look that great. So I came up with my own algorithm, which I'm rather proud of. Here's the psuedo code:
1. Randomly choose n values to seed the wave function to be used. I am currently using n=6, but I've gone as low as n=3 and still got good results. We'll call these values phase, and they should be different from each other. I have a variable called wavyness that provides the range for each value. A wavyness of 2.0 would put n[ 0 ] between 0.0 and 2.0, n[ 1 ] would be between 2.0 and 4.0, and so forth. For even more variance you can also randomly generate a shift values for each of the terms as well.
2. These seed values will drive a wave function of the form cos( phase[ 0 ] * x ) + cos( phase[ 1 ] * x ) + ... + cos( phase[ n ] * x ). Find the min and max of this function between 0.0 and 2 * PI. This is the worst part of the algorithm, as I currently brute force this. Using the min and max, you can now shift and scale any value of the function to the range 0.0 to 1.0.
3. Loop through each of the cells of the room rectangle and determine the angle to the center of the room. This angle becomes your 'x' to the wave function.
4. Plug this value into the wave function, then scale and shift it to the 0.0 to 1.0 range. There is also a fluctuation variable that takes the 0.0 to 1.0 range and adjusts it to something like 0.5 to 1.0. This gives control over how far into the center of the room the edges will dip. Notice - since the wave function won't loop at exactly 2 * PI, the values near 0 and 2 * PI need to be blended in some way. I linearly blend these 2 values and the results are great.
5. If the distance to the center is less than the radius of the room multiplied by the function result, draw a floor cell.
6. Go back to 3.
A final pass can then be made to draw the walls to the cell by checking if any neighboring cells are floor. The general idea of the algorithm is that a circle is a midpoint with a constant radius, and a blob is simply a midpoint with a varying radius. The cosine wave function provides a nice way to create smooth radius changes while staying seemingly random. It is very flexible and can create a variety of rooms, depending on the parameters given it. The current code only allows for rooms with square dimensions, but could be adapted to use a horizontal radius and a vertical radius.
Below are some example screenshots of possible uses. Note that fluctuation indicates how far the edge dips in. For example a fluctuation of 0.3 will result in walls that are 0.7 to 1.0 of the total radius of the room:
Edited on: Friday, August 22, 2008 12:34 PM
Categories: Dungeon Generation
Monday, August 11, 2008
Dungeon Generation Part III: Circle Rooms
The room drawing step of the dungeon creation algorithm is where the most variety is introduced. Using generic positions and sizes, the code can draw certain types of rooms. The first ( apart from the obvious rectangle ) I'll discuss is the circle.
First, the walls of the room are drawn. This is done using the midpoint circle algorithm. It's also sometimes called the Bresenham circle algorithm, but he actually didn't invent it. The gist of the algorithm is that a circle can be divided into 8 octants, and anything done to one octant can be mirrored to the other 7. Here is C++ code of the algorithm:
void rasterCircle(int x0, int y0, int radius)
{
int f =
1 - radius;
int ddF_x = 0;
int ddF_y
= -2 * radius;
int x = 0;
int y =
radius;
setPixel(x0, y0 + radius);
setPixel(x0, y0 - radius);
setPixel(x0 + radius, y0);
setPixel(x0 - radius, y0);
while(x y)
{
if(f >= 0)
{
y--;
ddF_y += 2;
f += ddF_y;
}
x++;
ddF_x += 2;
f += ddF_x + 1;
setPixel(x0 + x, y0 + y);
setPixel(x0 - x, y0 + y);
setPixel(x0 + x, y0 - y);
setPixel(x0 - x, y0 - y);
setPixel(x0 + y, y0 + x);
setPixel(x0 - y, y0 + x);
setPixel(x0 + y, y0 - x);
setPixel(x0 - y, y0 - x);
}
}
Second, the area of the entire room is scanned left to right and the cells between the walls are filled in with the floor tile. That's it - nothing overly complicated about this one either. Here are some samples of dungeons with circle rooms. Once again 128 X 128 dungeon, circle room size between 10 and 20:
Edited on: Friday, August 22, 2008 12:34 PM
Categories: Dungeon Generation
Dungeon Generation Part II: Rectangle Rooms
There really is nothing special about generating rectangular rooms, but I'll use this post to explain the general algorithm to create the dungeon. Here's how it works:
1. Fill the dungeon with the filler tile.
2. Create a 2D array of free blocks ( a boolean ), each block representing an 8x8 section of the dungeon. Mark each block as being free. Calculate the number of tries the algorithm will attempt to create and place a room. This keeps the algorithm from looping infinitely.
3. Create a random room skeleton ( the type and size ) based on the probabilities of the area description.
4. Determine how many blocks the room will take up. A sparsity variable read from the XML is added to the room size in order to create more spacing between the rooms of the dungeon. Starting from the top left, move through the free blocks until a big enough chunk of them is found.
5. If no chunk of blocks is found, go back to 3 if the number of tries is not surpassed. Otherwise, mark the free blocks as being used. Randomly position the room somewhere within the chosen block range.
6. There is an erase parameter read from the XML. It is a percentage of rooms that make it to this point that still use the space but are simply not drawn. Check if that's the case. If it passes, draw the room based on room type.
7. Go back to 3 if the number of tries is not surpassed
Edited on: Friday, August 22, 2008 12:34 PM
Categories: Dungeon Generation
Dungeon Generatino Part I: Overview
With the overall world organization explained I can go on to the specifics of dungeon creation, which is going to be generating the vast majority of areas the player visits. As mentioned before, an area XML file will be loaded into memory and used to generate the levels it represents. The exact organization of the XML isn't important, it's what parameters it contains that matter.
I wanted level design in RogueRunner to be intelligent, flavorfull, and themed - something that makes sense to the player. I was inspired a lot by reading Andrew Doull's blog at ASCII Dreams. Definately good reading. I also want authors to have control over these themes. So for now, there are a set number of room types. How often these room types appear, how big they are, what tiles to use for them, etc. are specified in the XML. I'll be creating a separate post for each of the room types, which, for now, are rectangles, circles, overlaps, blobs, chambers, and vaults. Vaults aren't implemented right now because they aren't random. They'll be read from a template file like the *bands do them. Other room types will most certainly follow.
All of the room types share certain things. They all have probability to be created, they have min and max room heights and widths ( right now circle rooms and blob rooms must be square in dimension. Later I'll probably add on oval room type and tweak the blob to handle rectangular dimensions ). They also have a list of themes to choose from. A room theme is a simple pallate of tiles to use for floors, walls, doors( if needed ), etc. These themes make it so otherwise identical rooms look and feel different.
Most of this is finished, though there is a lot of tweaking to do, and I haven't implemented connecting rooms together yet. But here are some things I have planned for the future:
To further add flavor to rooms, certain features which will be room type specific. For example, rectangular rooms may contain a smaller room with a door, be lined with pillars, be filled with pillars, have a chasm with a bridge across, etc. I'm not even sure how I'm going to implement these, but they will really add to the feel of the game.
Since area files can describe multiple levels, some mechanisms need to be placed for allowing the levels to change as they get deeper ( or higher ). Many of these are related to the monsters and items created, which I'm not dealing with right now. Some things apply to the dungeon, however, like the size of rooms getting larger on average, the number of rooms, the density of rooms, the probablitilty of certain types of rooms, etc. Most of these cases will most likely involve an extra paramter or two to specify the rate at which things change.
Underground rivers and lakes seem easy enough to add. These would be added before any room generation and rooms would simply write over the top of them. Most of the room types would exclude walls so that the edge of the room would be an opening out to the water feature.
Edited on: Friday, August 22, 2008 12:34 PM
Categories: Dungeon Generation
Thursday, August 07, 2008
Dungeon Generation Intro
Before I get started, I need to stress one major design feature of RogueRunner. It's really more of an engine than a game in and of itself. That's why I chose the name - authors create and define worlds, and the engine runs them. The system that I'm designing will hopefully lead to worlds that can be completely random, completely hand designed, and everywhere in between. If ever there is a community that actually plays this game, they can create worlds and share them with others. That's my vision. Of course, the RogueRunner "engine" will have at least 1 or 2 worlds designed by me that will be considered the "official" worlds that everybody play at least at first.
So after some basic groundwork for the game ( I'm using OpenGL for rendering ), the first real task I'm tackling is dungeon generation. At this point I'm talking mainly the generation of the game world, not so much monsters or items. Those will come later.
First, I don't think I'm doing anything revolutionary when it comes to dungeon representation. The cell is the basic building block. A cell can potentially hold a lot of infomation, depending on design preference. For now, my cells don't hold much - just some flags on whether you can walk through it, whether you can see through it, whether it's been explored before, what tile graphic to use, etc. A 2D grid of cells makes what we'll call a level. There will be exactly 1 level in memory at a time - the one where the player currently is. When a player leaves a level, it is saved to disk, which is called persistence. Persistence means the level layout never changes once you've been there for the first time, something not all Roguelikes implement. Newly entered levels will be generated using an area descriptor file, which is in XML. Why XML? Mostly because I got sick of writing code to parse through some arbitrary file format for describing things. With XML, reading the file is taken care of automatically, and I just validate and use the data according to the situation.
An area descriptor file defines the generation parameters or hand designed layout for the given set of levels it represents. An area might be a 10 level random dungeon, or a simple hand designed town. Areas link up to other areas to create the world. For example:
Areas can link up to each other in different ways. In the above example, all the areas are linked vertically - when you go up from Area 2 you get to a specific point in Area 1. In the code, this is more like a warp than simple stairways, although it could easily be made to look like simple stairways by the level author. Authors can also define what happens when the player walks off the edge of an area. For example, walking out of town could take you to a specific point on an overworld map, or while in a dungeon walking on a warp tile that's been made to look like a door could take you to another section of the dungeon that's meant to be on the same "level" as the one you just left, which creates a horizontal dungeon instead of a vertical one.
I think the system is very flexible and will allow for a wide variety of worlds to be designed. Authors have the ability to easily include special hand designed areas in their worlds, while still having all the randomness available that drives the genre.
Next I'll be looking more at exactly how the XML files are used to generate levels.
Edited on: Friday, August 22, 2008 12:33 PM
Categories: Dungeon Generation
Welcome!
Hello and welcome to my development blog. I am currently in the middle of developing a Roguelike game called RogueRunner. For those of you who don't know what a Roguelike is, go to RogueBasin to find out more. I'm basically a 1 man team, and it's becoming more and more difficult to create games with just 1 guy these days. Because the roots of Roguelikes go so far back their gameplay is their key feature, as opposed to 3D graphics, sound, networking, etc. And so, many Roguelikes out there have been done by 1 guy.
So that's what I'm setting out to do. It most certainly will be a long journey, and there will be times when I don't want to work on it any more. But hopefully I can get some people interested and following this blog to help motivate me in the difficult times. The end will be very rewarding, and I hope a fun game is the result!
At the same time, I hope that some of my research, ideas, solutions to problems, etc. will be helpful to others. I know I already owe a lot to others who have documented their work.
Thanks again for reading, and wish me luck!
|