Procedural Dungeon Generation

I was inspired several years ago to create my own procedural dungeon generator after reading a reddit post on the subject (also explained here).  I came up with an algorithm that was pretty simple and generated some pretty good results.

Below is a screenshot  and animation showing how the dungeon is being created at each discrete step.  I'll talk through each step one by one.

Final result of a procedurally generated dungeon.

Algorithm

In my code, I call this the tunneling algorithm.  The idea is to create a series of rooms and connect them by "tunneling" from one room to the next.  The tunneling route is the result of an A* path finding algorithm in which each cell is given a movement cost.  Cells which are floor tiles have a small movement cost and cells which are wall tiles have a high movement cost.  This results in the path route leaning toward using open floor cells over chiseling out wall tiles to get to the destination.  Depending on the layout, however, the path finder may decide to break through a wall instead of going through an existing room/hallway.  This is how circular loops and multiple entrances to a room can be generated throughout the dungeon - which is a pretty nice feature.

Room Generation

Rooms don't just have to be rectangles.  I create rooms by combining a random (usually 1-4) number of rectangles together.  I start with a single rectangle as the root, and then connect other randomly sized rectangles to a random edge of the root.

A single rectangle connected to the root rectangle to generate a room.

It's OK if rectangles overlap.  It can give the room more variation this way.

Two rectangles overlapping each other as they are connected to the root.

This simple technique can give some nice results to create a room.

Example room with 3 rectangles.

Example room with 4 rectangles.

One by one, a room is generated near the average room position on the map and then separated from the existing rooms by pushing it away until there there is no overlap.  The gap between the new room and the existing rooms can be configurable.

Once the room is separated, a path is generated from the previous room to the new room using the A* pathing method described above.  The map then generates new cells along the route in order to connect the rooms. 

The weight of the floor and wall tiles can be adjusted to provide different results.  If the wall tiles heavily out weight the floor tiles, then the algorithm will rarely attempt to tunnel through a wall in order to connect the room.  If the difference between the wall and floor tiles are small, then the algorithm will frequently path through existing walls.

The screenshots below show how the A* algorithm is searching through the map in order to connect each room.

If the cost of moving through an existing floor is significantly cheaper than moving through a wall, the A* algorithm won't even consider pathing through a wall.  The image below show the A* route using a floor cost of 0 and a wall cost of 100.

The search space (shown in orange) as the A* algorithm finds the optimal path.

If the difference between the floor and wall movement costs are small, then the A* algorithm will consider pathing through more walls.  The image below is generated from a floor cost of 30 and a wall cost of 100.

Depending on the map layout, the start position, destination position and the the floor/wall movement costs, the tunneling can create some nice results.  The below image is an example of where tunneling through a wall was cheaper than pathing around to the existing room entrance.

Room which needs to be connected to the rest of the map.

Path tunneled through a wall in order to connect the room to the map.

That's pretty much it.  I didn't go into detail on how A* is implemented, so that may be a future write up.  This algorithm can also be expanded to use a key/lock system in which rooms are broken up into different sectors and given keys to unlock doors of the next sector.

Here are a few more animations of the algorithm at work:

A New Game - Game Pillars, Requirements and More.

I've been working on a game concept for a while now which I initially began in order to prototype multiplayer networking techniques.  It's starting to take more shape into some sort of MOBA-dungeon-crawler type game.

As with all game ideas, this one started out very ambitious and quickly had to be scaled back to something much more manageable.  

I still don't know what the game is going to be, but I've given myself some requirements up front:

• The game shall support a persistent world.
• The game shall support player run servers.
• The game shall support roughly 10 simultaneous players
• The game shall support replayability.
• The game shall focus on gameplay mechanics above artistic style and story.

It's always a good idea to give yourself some constraints when starting a project.  This helps keep the project in focus and not let feature creep set in.  Given a handful of simple high level requirements like this, we can start to make more specific design decisions.

In order to support a persistent world, where players can log on and off at their leisure on player run servers with a no more than 10 players at once, I've decided the client-server model fits best.

In order to create a pillar around strong game mechanics above art and story, I've decided a 2D top-down rendered game using simple geometric shapes fits well.  

In order to support game replayability, I will lean heavy on procedural generation to create most content and player mods.

Find your why.

I jumped ahead of myself.  I've just listed a bunch of high level requirements that the game needs to meet, but where did they come from and why are they important?  What are the fundamental messages for your players?  What kind of experiences and emotions are you trying to create for them?  Once you understand the answers to these questions, you can start to identify the the core pillars of the game and every design decision should somehow link to them.

Most of my requirements and subsequent design decisions feed into these core game pillars:

• Teamwork
• Players should be able together as a team and work cooperatively toward a common goal.  They should feel a sense of camaraderie and feel how their contribution impacts the team.  
• Continuous Improvement
• With every play session the player should feel they've increased in power - whether it's earning experience points, loot, or increase stats, etc.

The rest of my requirements are simply non-functional.  They are constraints either due to time/budget or lack of artistic ability.

Screenshots

Finally some initial screenshots my progress.  It's currently implemented with client-server networking model including player movement, chat, and procedural dungeon generation.  More to come!

Login Screen

In-Game Diagnostic Menus and Tools

Player Movement

Procedural Dungeon Generation

How do multiplayer games really work?

I was curious how multiplayer games actually worked and I decided to do a deep dive to learn about game networking techniques.  I found that different strategies are used depending on the type of game.

All of these methods are very well known and available across the internet, so I'll just summarize them below.

Some notable links which helped me on the subject:

• The obligatory Gaffer on Games articles 
• An excellent series on client-server game architecture by Gabriel Gambetta 

Deterministic Lockstep

Games with a very large game state (impractical to send over the network) and a reasonable number of players can be implemented using deterministic lockstep.  In this implementation each client runs a deterministic local simulation in lockstep with all players in the game.  When the simulation advances forward in time (called a game tick) all players broadcasts their input to each other so clients can deterministically advance the game simulation.  The result is all players seeing and experiencing identical game simulations.

An example of a game that implement this method is Starcraft - a real-time strategy game (RTS). An RTS can simulate hundreds of units per player during a match each containing position, health, and various other state which would be much too large to practically send over the network.  The player count for these games will vary between 2-10 per game.

Benefits to deterministic lockstep include:

1. Network bandwidth is very low.  Since clients literally only need to send input across the network, the total network bandwidth is negligible compared to the entire game state.
2. Game states can be very large.  Since game states are all computed locally, they don't need to be transferred over the network.
3. Game replays are trivial.  If inputs of each game tick are recorded, it is trivial to re-simulate the game by reapplying the inputs associated with each game tick.

Cons to deterministic lockstep include:

1. Limited players.  Game ticks can't advance until inputs from each player is received - meaning any player in the game with a high latency connection will keep the rest of the players from advancing their local game simulations.  Each player must advance their game ticks together.  So in practice, the number of players per game really must be limited unless a good connection can be guaranteed (i.e. local network).
2. Latency.  Input lag is measured as the time between when a key is pressed to when the screen updates reflecting the user's input.  Latency is an issue in every networked game, but techniques like client-side prediction can not be used to reduce the perception of latency.  However, clients can play audio or play animations to help provide immediate feedback to user input.
3. Determinism complexity.  It is absolutely critical that the game simulation is deterministic.  This may be easier said that done.  This means handling random number generators appropriately and all floating point math adhere to strict floating point math (i.e. IEEE-754).  If two clients get out of sync due to a small round-off error, then the butterfly effect will take its toll and all bets are off.  Synchronization can be verified by having each client hash the game state and verify the hashes match on each game tick.

Client-Server Model (Authoritative Server)

Games with a large number of players and a reasonably sized game state can be implemented using the client-server model.  In this implementation, each client communicates with a single centralized server.  The client sends their input to the server each game tick and in return the server sends the entire game state.  Determinism is still a good idea here, but not a strict requirement like the previous architecture. The absence of player lockstep allows each player to experience the game based on their own latency connection.  Each player may or may not experience the same simulation, depending if client-side prediction is used.

Benefits of using a client-server model include:

• The server is authoritative.  Since clients are not simulating their own local game state, hacks and cheats can be avoided.
• Large player count.  A client-server model scales well with additional players.  Additionally, players with poor connections (high latency) will not affect other players.
• Lower input latency.  If client-side prediction is implemented, the perception of network latency can be reduced.

Cons of using a client-server model include:

• Bandwidth usage.  The bandwidth of sending the game state to each player scales linearly with the player count.  Unlike deterministic lockstep, where only player inputs are transferred over the network, each tick the server must send the game state to each player connected to the game.  Optimizations can be made to send only delta game states to each player, but this still doesn't scale well as the number of players increases.

Without Client-Side Prediction

Games that can tolerate a large amount of input lag do not require client-side prediction.  Inputs are simply sent to the server to advance the game simulation and round-trip-time later a game state arrives which can be rendered on the screen.  This is generally acceptable for games tolerant of slower reaction times or third-person control of a character.  An example of a game which implements a client-server model without client-side prediction is League of Legends.

With Client-side Prediction

Games which require minimal input lag should implement client-side prediction.  This is generally needed with game mechanics requiring quick reaction times or first-person camera views where the player needs to see immediate response from controller input.

With client-side prediction, the client is allowed to simulate ahead of the server before the authoritative game state is received.  The game state is authoritative because the server's simulation is truth regardless of what the client is predicting.  This is what prevents players from cheating.  When the game state finally arrives (round-trip time later), the client reverts back the authoritative game state and then re-applies the remaining player input to put the client back to the predicted time.  If everything goes well (i.e. the client is not cheating), the client will be simulated back to the exact position it predicted before the authoritative game state was applied.

Lag Compensation

Client-side prediction breaks the paradigm that the game state is coherent for each player.  Therefore each player is actually experiencing a different simulation, where the is player is ahead (in the future) of the server.  The rest of game state (other players, other entities, etc) are in the past.  This gets tricky when the player needs to interact with the other players in the game, which is where lag compensation comes in.

Lag compensation will attempt to reduce the time difference caused the player (in the future) and the other entities (in the past).  In general when two players interact with each other, the server must make a choice on how to resolve that interaction.  For example, if Player A shoots Player B (where in Player A's perspective has clear line of sight to Player B) and Player B (from their perspective) has activated a shield, the server must make a decision on who to favor.  Since each client has predicted ahead before receiving the authoritative game state indicating truth of the game state, they are therefore experiencing completely different views of the game at that moment in time.  They each think that their own simulations are truth and expect to have a favorable outcome - Player A expects to be rewarded with a head-shot, while Player B expects to be shielded from the shot.

If the server keeps a record of the past N game states, the server can reconstruct the exact state of the simulation from the perspective of each player at that moment in time.  The server will then see that from Player A's perspective they indeed did shoot Player B before Player B's shield was active.  It will also see that from Player B's perspective that their shield was active before the shot from Player A.  The server will need to favor one of the two players by either applying damage to or shielding damage from Player B.  Depending on the game mechanic at play the decision to favor the shooter or defender may vary.

A great video explaining both client-side prediction and lag compensation can be found in Overwatch's Developer Update | Let's Talk Netcode video.

A journey through game development and software engineering

I've never blogged before, so here it goes...

Hello, my name is Billy Brandstetter and this is my blog.  I'm actually a pretty underwhelming writer in the sense that I generally write sentences like I write code - short, elegant, to the point, no extra fluff what-so-ever.  These posts probably won't be interesting to anyone unless A) you are a software engineer or B) I become a better writer.

I intend this blog to be a vehicle to share my thoughts on general software engineering, game development and game engine programming.  I've been working as a professional software engineer for almost 15 years - the majority of it outside the game industry.  Many years ago I started a hobby project to build a game engine written mostly from scratch using C++, OpenGL, for Windows.  During this time I've learned a lot about software development - lessons learned, best practices and techniques which I'd like to share with anyone else who is interested in working on their own software projects.

There are several blogs out there full of great information.  Some of the best articles and write-ups regarding programming and software development I've found tucked away on blog as opposed to other publications.  These are absolute gems and I wouldn't have near the amount of knowledge I have today without them. I would also like to give back by providing my own expertise to individuals aspiring to get into the software world.