A 20 sided die is commonly called a "d20" by gamers and an "icosahedron" by mathematicians. This blog post will illustrate how I use these angular shapes to create nice soft lights in the Pantheon engine.
We start with a dark hallway, then we fill it with a giant d20. No, not just big. Not large. Not even huge. GIANT. It's taller than the room, so it sticks through both the floor and the ceiling.
Now just like that, it's obviously not very useful. However, as a programmer I've got a number of tricks up my sleeve. Instead having the graphic card draw the visible part, we're going to reverse that and only draw the portion behind the walls, floors, ceiling, etc. In other words, we're only going to draw the portion that's embedded in something else. It looks like this:
Better, it now highlights surfaces in the world instead of blocking visibility, but it's still very hard and edgy. Now I'll round it off in the shader. A shader is code that runs on your graphics card -- it decides which pixels to draw and what color to draw them. In this case we're going to measure the distance from each pixel to the center of the d20. We'll use that to prevent pixels outside a certain radius from getting drawn. The result is that we only draw the pixels inside a sphere.
Much better, though still a bit harsh on the eyes. We'll add additional checks to fade out the light based on distance from the center. We'll also fade out the light for surfaces that aren't facing the light very well.
Yay! Looks good right? Well almost. One problem. It shines right through the wall! It has no bounds and shines right though everything! To fix this, we use the surfaces of the walls, ceiling, and floor to "cut" the mesh so that it never protrudes through geometry. Now the walls will cast a shadow. Subtle, but very necessary
And finally, in motion:
There are many algorithms which procedurally create human styled architecture and layouts. They generally operate on a cartesian grid and produce rooms, hallways, walls, and doors which align with the four cardinal directions. While these provide realistic human styled architecture, they quickly become predictable and boring in a video game setting. This blog post will describe an algorithm to create an interesting floor plan. “Interesting” for this exercise will be defined as non-cardinal, non-orthogonal, and semi-unpredictable.
This video is provided for reader visualization: https://www.youtube.com/watch?v=60fbtJmqvNo
Some additional Screenshots showcasing different parameterizations: http://imgur.com/a/sELIk
We start with a set of points on a grid; the example video uses an 11x23 grid. We add variance to the location of the points. “Variance” in our implementation is a value between 0 and 1 where 0 indicates the points are perfectly aligned to a grid and 1 indicates they have moved as much as possible without leaving their initial grid square. The demonstration video animates the variance of the grid from a value of 0 to a value of 0.8.
Next, we generate a Voronoi Mesh between the points. We modified this implementation to return the room indices for the walls that are generated. Constructing the rooms involved some work as there is no information about external walls, and no order to the walls constructed. Additionally, the implementation has small floating point discrepancies between joints which would ideally be an exact match. Once those are taken into account, you can build a list of rooms with solid perimeters.
Using the list of rooms from the previous step, we calculate the area of each room. Small rooms are joined into larger rooms by removing walls between adjacent rooms. A “Room Join Target” parameter is used to measure when rooms are sufficient size. This value is the approximate minimum number of rooms that will be combined when larger rooms are formed. In the example video, the Room Join Target is 6 so 6-10 small rooms tend to get joined into each large room, though the exact number could be smaller or larger. To implement this, we take the average room size and multiply it by the Room Join Target parameter to get a “Target Room Size”. Rooms smaller than Target Room Size can be combined with adjacent rooms as long as they don’t exceed 4x the Target Room Size. Choosing the smallest rooms first we evaluate neighboring rooms. We choose neighbors using a score based system which attempts to maximize walls removed while also trying to select smaller neighbors.
Combining several small rooms can result in very complex geometry with many small walls. The next step combines several smaller walls into fewer longer walls. Longer walls make it easier to place doors in the following step. Reducing wall count also simplifies spacial logic at runtime (e.g. which room is the player currently standing in?)
In this step we simply iterate over all wall joints. If a joint has exactly two walls attached, it is considered for removal. It is reduced if either of two conditions are met, the angle between the joined walls is close to 180° or the joined walls are shorter than the wall join threshold.
Once the walls are simplified, we add doors by iterating the adjacency graph between the rooms. If you use a depth-first search to add doors, you’ll wind up with longer more linear levels. If you use a breadth-first search the starting room will become the hub for the level with adjacent rooms leading to many shallow paths. We dubbed our method a “Random-First Search” due to the fact that it works just like the first two, but the next room to be visited is selected by a random number generator rather than by insertion order. Additionally, there is a “Connectivity” parameter which allows a random chance to open a door to a neighbor which has already been visited -- being careful however, that it is not requeued for visiting again. The “connectivity” used in the example video is 20%. This provides a porous floor plan which the player can navigate with minimal backtracking.
Conclusion: if you're interested in constructing nontraditional floor plans, manipulation of a Voronoi graph is a great place to experiment.
I made a program which creates castles (Part of: /r/proceduralgeneration). This blog post describes how that program works.
My Castle Gallery: http://imgur.com/a/fbaM4
Included Here: Generating the data your program needs in order to create renderable geometry
Not Included here: Creating the renderable geometry. That article has already been written.
1. Create “Structures”
I started by creating “structures”. Each structure was basically a normal convex polygon (square, hexagon, octagon, etc...) and a height. The height was measured in “floors”. The example image above has three hexagons for it’s main structures. The largest has a height of 4 floors. The Medium one has a height of 8 floors, and the smallest one on the top has a height of 12 floors. I then added more structures which intersected the main structures. Some were randomized, some were strategic.
After creating these, I created a list of “Floors”. Each floor has the following data:
Some Technical terms, as they’ll be used in this blog:
This is important because each piece of data for the floors is stored either as a collection of polygons or a collection of paths.
After generating the structures, we begin filling in the data for the floors
2. Basic Data Gathering
For each structure, find the floor representing the roof of that structure. (E.g. for a 2 story building, you’d want the 3rd floor.) Add that structure’s shape to the Exterior Surface polygon collection for that floor. This will later become the pink sections in the example diagram. Also, add that shape (as a path) to that Floor’s collection of Parapet Walls. Remove any walls which are inside of another polygon.
3. Gather data from above
After gathering basic data for all structures, use higher floors to generate data for lower floors. For each floor, we need to determine the Interior Surface (Blue floors in the diagram). To do this, simply look at the floors above. Combine the Exterior and Interior Surface from the floor above and that creates the Interior Surface for the current floor.
We also need to modify the floor’s Exterior Surface because some of it may now be interior, but before we do, we need to set up some walls. We need the outline of the floor above us. You can generate it from the your brand new Interior Surface, or you can combine the previous floor’s External Walls and Parapet Walls. This set of walls (the walls coming down from above) will either be External Walls, or Roof Access Walls. To determine which, test to see which parts are inside the current floor’s (unmodified) Exterior Surface. If the wall is inside the Exterior Surface, then it’s providing roof access. If it’s not, then it’s a regular External Wall.
Since we’re modifying walls, go through the Parapet Walls and cut off any sections which enter the Interior Surface.
After you’ve divided up the wall sections, then you’re free to adjust the Exterior Surface. Subtract the Interior Surface from the Exterior Surface and you’ll be left with only the Exterior portions. NOTE: When subtracting one convex polygon from another convex poly the result can be:
4. Add Interior Walls
At this point, we have a basic Castle shape in place. The Floors (both inside and out), the External Walls, the Roof Access walls, and the Parapets are all done. Now to fill big interior spaces with hallways and rooms. The following is all done on a floor-by-floor basis.
My approach was to add lots of hallways and allow the rooms to exist as the space between the halls. I should note here that I enjoyed this approach, and I’m convinced of it’s merits, but it was the most time consuming and I did wind up cutting some corners due to time constraints. Rather than describe the flawed version I settled for, I’m going to describe how the code should eventually have worked, if I had leisure to polish it. Here’s the data for this process:
* Collision (Polygon(s))
* Walls (Path Collection)
* Doors (Path Collection)
* Hallway Leads (Array of Leads)
* Wall Leads (Array of Leads)
At this point create a several Hallway templates. Design Hallway Templates assuming that the origin comes off of an existing hallway. Add walls which flow forward and do normal hallway things. Add a collision polygon which is larger than the geometry you’ve created. Example Templates:
* Y Fork to two additional hallways
* X Fork to 3 additional hallways
* L Bend Right, and another to the Left
* Small Dead End, with a door on each side
Now create an “Open List” of Hallway Leads; seed the list with a known good value. I manually created a front door on the main level and seeded that level from there. On other floors, you can use two seeds, back to back, in the center of the level. Also create a list of Wall Leads; we’ll need that later. Now loop:
1) Remove a lead from the Open List. This is the “Current Lead”
2) Look through all the Hallway Templates.
a) For each one, check and see if it’s collision poly can go in front of the current lead.
b) If it can, add it to a list of valid candidates
3) Look through the valid candidates, get one with the highest priority. If there’s tie, choose one at random.
4) Insert the Template into the world at the Current Lead’s Location
a) Add the Template’s walls to the world
b) Add it’s Doors to the Floor’s list of doors.
c) Add it’s Hallway Leads to the “Open List” of Hallway Leads
NOTE: This algorithm assumes you can find at least one valid candidate. To ensure this happens do two things. 1) Make sure your collision for most Templates exceeds the actual walls you’re adding. 2) Have at least one tiny template that has no collision, or minimal collision (See Dead End example).
Finally, there are many locations where hallways stop and it’s handy to note that the area on the other end of the stop needs to be split. This is especially handy for the dead end Template and this is what the “Wall Leads” list is for. Simply iterate through the wall leads and locate a valid destination for the wall. My wall leads attempt to connect to other wall leads. If that fails, they look for a solid wall segment to connect to. You can see examples of these along the bottom and right hand side of the example image.
5. Add Windows & Doors
Creating windows and doors is fairly straightforward. I simply iterate through all of the External Walls placing windows then iterate through the Roof Access Walls placing windows and doors.
Placing a portal (a window or door)
For every edge on the given Path, I check to see if the edge is long enough to contain a portal, with a little extra room on each side. If it is, I create a Rectangle just inside the wall and check to see if the rectangle collides with an interior or exterior wall. If it does, I go a little farther down the edge and check again. If it doesn’t I create the portal, then break the path into two pieces. One path stops at the beginning of the portal and one starts again after the portal. I then continue checking the same edge (now in a new path) until the edge no longer has sufficient room to hold a portal. Then continue on to the next edge.
And that’s it. Your program should now have all the data it needs to generate renderable geometry for the entire castle.
Errors? Feedback? Suggestions? Bored? Go Here: WereCoder@AmpletiChao.com
The Pantheon engine is a work in progress. The primary purpose of ProcJam and Theseus was testing the Pantheon Engine to see what it needs most and how well I can use it to make a full game. Now that they're done, here's my notes on how it performed and what I should be working on next.
This was a known shortcoming of the Pantheon engine. I’ve had it on the “To Do” list for a while. The problem, in a nutshell, is that each time I created a piece of world geometry, the engine created another vertex buffer for it, and necessitated another “Draw” call for that piece. In test environments, I had ten to twelve pieces, so it wasn’t an issue. When I got Theseus up and going, I had ten to twelve thousand pieces. That didn’t work so well. So the second day of ProcJam I had to stop for a couple of hours and rework the vertex allocator for world geometry. Once that change was made, it ran really, really well. It rendered the largest maze, with no culling, in under 3ms. I was happy.
These worked as intended, but “as intended” meant writing new particle logic for each particle effect. I’m not unhappy with that approach, but it occurred to me that a few stock effects, written with good parameterization, could cover a large number of use cases. If only I had a project to put them in ...
No centralized GamePlay project
Common items (The Camera, Particle Effects, Agents) need a home so they can be shared across multiple projects. I made several camera fixes in Theseus that won’t automatically get propagated to Dionysus because their Camera classes live in their respective projects. Likewise, the new particle effect classes aren’t accessible in Dionysus either. I can’t put them in Chaos because Chaos is dynamically linked through interface classes and that would just suck. Prometheus is intended to be very low level, non-game related, project. I need a new (statically linked) project to house the more common gameplay classes.
Procedural Geometry Creation
During ProcJam, I was able to procedurally create simple meshes using the Pantheon Engine’s stock methods. The gold coin, the wall quote symbol, and more were created through data only, but there were issues with texture coordinates. The Pantheon system which creates procedural geometry has only been creating test levels. When I used it to create specific items, I found that I hadn’t exposed control of the UV coordinates. When I start creating more convoluted meshes in Dionysus, this will become an important issue.
The UI was easy to create and worked fairly well. Panels are placed in the scene using a percentage of the scene. For example, the reticle panel is placed at (50%, 50%), halfway across the screen, halfway down the screen -- always in the exact center of the screen. This worked great. Unfortunately I also chose the same system for placing widgets on panels. This means that I can center things easily, but the boundaries between the edge of the widget and the edge of the panel are now scaled by the size of the panel. So if a panel is four times wider than it is tall, it It’s horizontal border will be four times wider than its vertical border. This also happens when placing panels in the scene, but is much less noticeable. This system needs reworked to respect both fixed and dynamic positioning for all elements. Also, it would be a huge benefit to add “snapping” such that the edge of a widget automatically aligns to the edge of a panel or another widget without any manual effort.
A “Build” is a particular version of a game. Creating it, in my case, involved putting a bunch of files into a zip file and uploading that zip file to the internet. I already had a “deploy” process, but there were lots of files present that didn’t need to be put in the build. That meant I had to manually delete files (then retest the game) several times before a build was ready. I created 3 builds during ProcJam, and each of those ate more time than they should have. In the future, I need to be more careful about what files get into the deploy folder, and I also need an automated “build process” which creates a build for me.
I didn’t make an installer, that’s one of those things I need to look into. Actually install PhysX. Make sure DirectX is installed. Make sure DirectX is upgraded to the proper level. Check hardware and make sure it meets the minimum requirements. All that good stuff.
Wow, that was easy. I might integrate a music player into future versions, but the sound FX were the easiest part of this whole project.
Prometheus Data Definition Language (PDDL)
Worked great when it worked. I could type up ten lines of PDDL and it would generate 50 lines of C++ code which defined my data and loaded it for me. All I had to do was go to an Init() function and start using the data. The single problem I had was when I had a typo in a PDDL file. Everything crashed with no explanation. I fixed the typo. I also fixed the crash. Last, I fixed how it’s handles PDDL errors in general. At some point, I’d like to add more descriptive errors when parsing PDDL, but I built it on LEX and YACC and they’re not the friendliest beasts.
In this blog post, I’ll try to answer three highly related questions:
• What’s your obsession with procedural content?
• Why did you choose the name Amplecti Chao?
• What’s going on in the picture with Zeus and Ares?
First, let’s stop and imagine we’re playing a traditional, single-player, campaign style RPG. After exploring the icy mountains, you discover that your next destination is the alpine forest below. You slog your way through hoards of minions toward giant wooden doors which you assume are the exit and just as you reach them ... [AUTOSAVING...]. What happens next? Boss battle of course. The doors open and there’s an Ice Giant on the other side. Obviously you’re supposed to kill the Giant before you’re allowed to the next area in the game.
When I was twelve, this type of encounter was awesome. After so many years of seeing the same thing it’s grown cliche. Let’s examine the scenario above.
1. The player is supposed to play through the mountain area before playing through the alpine forest area.
2. The player is supposed to kill all the minions before reaching the exit.
3. The game is supposed to autosave before the player starts the boss battle.
4. The player is supposed to kill the boss after finishing the mountain zone, but before continuing to the alpine zone.
Note the phrase “supposed to”. It points out intent. It means that, at some point, somewhere, there was a designer who crafted this area so that all players would have a predictable and controlled experience as they played through this area.
That craftsmanship raises the quality bar of the player’s experience. It allows custom storylines, cutscenes, narrative, and scripted sequences, to all enhance the player’s experience. And I’m tired of it.
A few years ago, I visited a forum where someone posted a Minecraft screenshot showing a hole in a cave floor. You could see a dimly lit area below, but there was no way down. The post asked “how am I supposed to get down there”. Many responses provided solutions to the problem at hand, but one tackled the higher level problem. They basically said “you’re not”. They then explained that in Minecraft, there is no “supposed to”. You’re not “supposed to” go down there. You’re not “supposed to” come out alive if you do. In fact, you’re not “supposed to” be in that cave at all. The game does not create guard rails, does not hold your hand, and likewise it has no expectations of you. It doesn’t give a damn if you retreat to the safety above ground, pillage all the treasures from that cave, or die trying. The game, and its design, are intentless. If there is intention within a Minecraft game, it comes from the player, not the designer. Thus began my understanding and my love of the intentless design philosophy.
Intentless game design is the simple notion that games can be created from settings, situations, rules, and mechanics without imposing an expectation upon the player. It explicitly embraces the notion that a player’s actions change the player’s state and the world’s state in a combinatorial fashion such that they cannot be predicted nor planned for. It does not exclude the idea of a goal state, either for the player or the world, but instead it casts aside all predictability of how a player navigates from their initial state to their goal state.
Why is intentless game design valuable? Intentless game design creates explorability within a game. It could be physical explorability, if your physical world is intentless. It could be magical explorability, if your magic system is intentless. The more game systems which are created without expectation, the more play-spaces the player can explore. Per Cliff Bleszinski, “I now believe there's a direct correlation between how good your game is and how many unique Youtube Videos it can yield.”
Additionally, intentless game design moves responsibility back to the player. Modern crafted experiences come with a notion that the game is holding our hand. If we're allowed access to a dungeon, we (the players) have come to expect that we must be properly prepared for the dungeon, otherwise we wouldn't be allowed access. If we're presented with a boss battle, we assume the boss is beatable. We've even developed an expectation that the game will save itself in case we die. Intentless game design moves all of those responsibilities back to the player. That requires some adjustment in thinking for modern gamers (see the Minecraft example above), but the weight of that responsibility -- that idea that you're not supposed to be here and you're not intended to survive -- it creates a valuable dread that I no longer get when I know the scenario was crafted with survivability in mind.
What does this have to do with procedural content generation? Well, as a technicality, nothing. Technically, any content that was procedurally generated could be crafted. And the reverse is technically true as well. However, crafted content has a strong tendency to weave intention into the design. Procedural content lends itself to intentless design, leaning toward a world where the player is free to create their own intention. I prefer procedural content because it tends to create game spaces I want to play in.
So you think procedural content is superior to crafted content? No, actually I think crafted content tends to have higher production values, more mass market appeal, and higher sales. I’m just tired of it. I'm ready to take responsibility for my own gaming experience, and I don’t think I’m alone.
Why did you choose the name Amplecti Chao? Amplecti Chao is latin for “Embrace Chaos”. It’s a reminder that randomness, while scary, can be harnessed to create things which are awesome. Hopefully it’s an obvious reference to procedural content generation, but it’s also a less obvious reference to me giving up a safe reliable paycheck for the chaos of indie game development.
What’s going on in the picture with Zeus and Ares? In this picture, the gods are creating a new world by throwing dice. It’s a mythological depiction of randomized world creation and it illustrates the values I design by. Mad props to Colleen Wilson for that image, I’m ecstatic about her work.
Before I joined the video game industry, I spent about 5 years making corporate software. During this time, I learned a lot about wearing ties, avoiding red tape, and modularizing software. Needless to say, when I began making video games, I was shocked at the "dump everything in the executable" design pattern. After a few projects, I began to see some benefits and rationale, but I was never completely sold on the idea. Now that I'm on my own, it's time to try modular game development. In this post, I'll describe exactly what I'm doing and why.
The Pantheon Engine isn't a traditional engine. Rather than a bucket of code that you integrate into your project, it's a collection of interconnected modules (DLLs mostly) which can be loaded and used as needed. Each module is named for a Greek mythological figure, often a god. Names are chosen which reinforce the purpose of the module:
* Chaos is a Greek mythological entity representing the primordial universe and the source of creation. He is the namesake for the executable which loads all other modules. This executable essentially loads several DLLs into memory, then enters a loop, ticking all modules and checking windows messages, until it's time to exit.
* Prometheus is the most basic module which defines things like strings, collections, and data file formats. It's currently the only statically linked library, all other libraries are dynamically loaded. Prometheus is named after the Greek god who gave mankind the knowledge of fire.
* Aphrodite is the DirectX 11 module which renders the 3D scene and the UI elements. It's named after the Greek goddess of beauty.
* Apollo, the XAudio2 module, is named after the Greek god of music. It's responsible for all sound including music, special effects, vox, and UI chirps.
* Atlas, named after the Greek titan who holds the heavens upon his shoulders, is the PhysX module. It's responsible for all collisions, movements, acceleration and so on.
* Theseus is a game which allows players to navigate a labyrinth -- or at least it will be. That's my ProcJam project. This module is named after the labyrinth defying Greek hero who slayed the Minotaur.
* Dionysus is a lighthearted shooter where players recklessly romp through an alien world. It's named after the Greek god of merriment.
At startup, Chaos loads into memory. Chaos loads a config file which details the other modules that need to be loaded. Then it loads and initializes the modules specified by the config file. For each module, it queries and stores an interface pointer to the main object in that module. It then enters the main loop which ticks each interface and checks windows messages until it's told to exit. In the future, it will accept run-time requests to replace one module with another.
The obvious draw to this approach is replacabilty. Any module can be removed and replaced with another, just so long as the interface to that module is honored. For example, someone could write a DirectX 9 module, update the config file, and without changing anything else, Chaos would load the DirectX 9 module in place of Aphrodite. Everything would work with no external changes. This is a cool benefit but (with one exception which I'll discuss in a minute) not one that's likely to get exercised during my development. Granted, I love the idea that this could happen, but the honest corner of my brain assures me, YAGNI.
There's another, less obvious, benefit though: enforced decoupling. In the Pantheon Engine, this means that data from one module can't be easily shared with another module. My programming mantra has always been "Make good decisions easy to implement. Make bad decisions hard to implement." Tight coupling of data leads to rigid code. A design which makes tight coupling require effort ensures that tight coupling only happens when it's necessary and only after it's been thought through. Using interface classes between DLLs forces coders to be mindful of the boundaries between code systems and highlights the methods which share data between the systems.
Another benefit is compile and link times. By organizing source code such that only necessary headers are included you minimize compile times. By dividing code into separate modules, the linker has less data to look through when resolving externals.
Last but not least, I gain the befit of (drum roll ...) habitability! That's right, my code can now be hacked! Isn't that great? Yes, yes, I know. "Piracy is the bane of all developers." Why would anyone celebrate it? Because, as an indie, Piracy is the least of my concerns. Obscurity is a fight for life itself. If I can't conquer obscurity then piracy isn't even a topic of discussion. By making my code hack-able mod-able I hope to attract the attention of modders and other developers who want to build their own games using the Pantheon engine. As far as cheating is concerned, my first few games aren't going to support multiplayer, so my users are welcome to cheat if they can figure out how.
Oh, remember that exception I promised to talk about? Well, here it is: the one exchangeable module I expect is the game itself. Simply write your own DLL and Chaos will happily load it and fire up your game. No strings attached.