« General | Main | News »

Thursday, July 09, 2009

A* and Dungeon Generation

It was only a matter of time before I had to implement A* for pathfinding, but I recently read a post that opened my eyes a bit. The thread can be found here:

Over-engineering dungeon generation

Until today, I used to have a massive ConnectRooms function that connected different rooms. It would enter and leave rooms differently based on their type, and would kink around and bend in random locations. After reading this post I realized that my approach was horrible, and the results weren't that great. So I implemented A* and now I just make a call to A* to connect rooms. That's it ... one call ... well, mostly.
I made my A* algorithm flexible enough that I could specify whether I wanted to prefer straight lines, whether the path should follow the bee-line to the goal node. Now the dungeon generator just needs to keep its own pathing array as it draws rooms. The corners of rooms are marked as impossilble to pass, and the floors of the rooms are marked as easy to pass. The walls and the rest of the map are marked as hard to pass.
When I get a path back from A*, I draw the tunnel and update the pathing array to allow easy passage through the tunnels. Like the post states, A* starts to join up with other tunnels and rooms to get to the destination easier. This makes the map look cleaner, and the tunnels make sense.
My A* might need a little tweaking to get the best performance out of it, but I'm actually kind of glad that I allowed myself to just get it working at a good level and put it to use, instead of spending a week optimizing. I have to continually make myself do this, otherwise I get bogged down and don't see much progress.
Posted by Jake at 3:51 PM
Edited on: Thursday, July 09, 2009 3:51 PM
Categories: General Programming
|

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:


 

Normal tiles. A pillared door on stone, brick, and wood.


 

Blended tiles. A broken wood door on wood, sandstone, dark brick, and granite.

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.

Posted by Jake at 12:19 PM
Edited on: Friday, August 22, 2008 12:34 PM
Categories: General Programming
|