Procedural Generations in Games: An Intuitive Approach
Chapter I: First Impressions
The towering brick walls stand high, dwarfing you in their shadow. The dimly-lit lamps can only offer you a fleeting sense of comfort, with its pale and flickering light that blurs onto the rough-hewn bricks. The air is heavy with the smell of cold metal and the ring of your echoing footsteps. As you wander through the never-ending corridors and rooms of this place, you cannot help but feel this endless expanse of darkness swallow you.
Peering into every steel-barred window leads you into another abandoned prison cell, recursively opening into multiple similar cells. And yet, every cell is unique. Like a siren, every cell will haunt you with her unique melody, drawing you deeper into these abandoned spaces of confinement and isolation, a vast and unknowable void that seems to stretch out in every direction. Just standing here, your insignificance is so overwhelming that it’s easy to lose sight that you’re just a player in this game.
Chapter II: What?
This is exactly how I felt floating above the dynamic construction designed for our 4th semester Graphics project. Every direction you WASD to rolls out a path that is endless. It’s natural to feel like you’re stuck in a maze, except that this was an endless maze: an infinite labyrinth with no exits and no escape.
It’s always curious how games like Minecraft are designed to be perpetually endless, updating every game asset in real time, constantly allocating and deallocating memory on your hard drive. Heck, it’s curious just trying to simply peek behind the curtains, and imagine how such mega productions even work, flipping bits on your PC every nanosecond or so, for you to explore and be washed ashore with only a sense of wonder and awe at the complexity of an infinitely vast world.
Chapter III: Err… but why?
It wouldn’t be wrong to say that gameplay experience today stands on a completely different dimension with modern day’s dynamic, HD renders, for what started back in the day from pixelated, repetitive gaming assets. We’re far ahead from the time when levels were painstakingly hand-crafted or environments were manually designed, and despite the time and labour that it took, were often limited in scope and variety.
This meant that developers had to create every aspect of the game world manually, including level layouts, the placement of enemies and obstacles, and overall design of the environments. Also, talk about the file size required to store these pre-designed levels and assets. Back in the 80s, every KB of storage on your 1 MB floppy disk (yes, you read that right!) was so precious that deciding which of your games to delete felt like choosing which of your children to be given up for adoption. In all seriousness, nobody’s ever enjoyed playing a high-stake game of Russian roulette with their beloved video games.
Thanks to procedurally generated worlds today, gaming experience has become so much more real and immersive, minus the time and labour invested. This is how games like Minecraft and Proteus are actually produced, selectively recombining 2D and 3D visuals in a seemingly random manner so that a player can navigate infinitely in her environment in any direction without the architecture feeling redundant.
At first glance, procedural generation looks overwhelming; with very fine resemblance to complex neural networks, it is easy to expect machine learning algorithms to grind under the hood. But as we dive deeper, you’ll notice how these generations, although not simpler, are far more intuitive that you’ve originally imagined.
Chapter IV: Hmmm… how does that work?
The fascinating thing about Procedural Generations is that the program is only fed individual 3D models of different building assets, here being doors, window frames, lamps, lampstands, sand, walls, etc. and the final assembly is achieved using a set of algorithms and pre-defined adjacency rules. Let’s call every square of floorspace in the game as a tile, where what piece goes on which tile is decided by these rules. It is the program that assembles these structures, positions what goes next to what, and what texture applies to what asset, so that the final scene looks right to the human eye.
Chapter V: Tell me more.
At any instance in the game, our user is surrounded by 5 x 5 tiles in the grid. We’ll suppose our user always remains at the centre of our screen on a sand tile. We now try to guess what tiles are allowed to be adjacent to sand in each direction in this 5 x 5 grid. This design might sound familiar, somewhat similar to a game of Sudoku.
Before scribbling any numbers in, every unfilled box has an equal chance of all numbers 1–9 to be scribbled in, until we’ve specified a number ourselves. In the same way, every tile is believed to contain all assets unless one of them is chosen. A state of superposition, if you call it.
Once a number is scribbled into a box, this superposition state collapses since a selection has been made. This is the crux of the ‘Wave Collapse Algorithm.’
Which box is to be filled first is determined by how definite our value is in that grid. Like in the figure, box g5 seems like a good starting place: the intersection of the most-filled rows and columns gives us a lesser quantity of probable numbers, making our choice more plausible.
1: Entropy
In fancy technical jargon, this is what’s called entropy. Simply, entropy is the measure of randomness. The more random the numbers in a box are, the less deterministic they are. Hence, they have higher entropy. The less random the numbers in a box are, the more deterministic they remain. No wonder, they possess lower entropy.
Our selection begins from lowest entropy; what we call ‘lowest entropy heuristic’.
We proceed filling every box sequentially in our Sudoku, that is, we proceed to determine what goes into each tile in our 5 x 5 grid following hierarchy.
The set of adjacency rules are fixed beforehand by setting each building asset as a node in a Graph data structure and connecting these nodes to all possible next-door neighbours in the graph with their corresponding orientation info.
2: Contradictions and Back Tracking
The only contradictory condition reached with this algorithm is filling in all neighbours radially outward only to realise a particular tile can have no building asset as it opposes all other neighbours. We can see this in the Sudoku alternate universe as a case where we go on filling an entire column and a particular box seems to fit only a ‘3’ say according to the square but its row already has a 3. In such a case, the only way out is to start all over again one step back each time.
This is the same thing we do in the procedural universe. During a period of contradiction, a particular box is at its lowest entropy because there are no values it can satisfy. By going back each time, we correct our initially made wrong assumptions of which building asset is the best choice for a tile and make the ultimate model as predictable and accurate as possible. After a few false starts, we finally reach a state of full collapse — one where every neighbour is okay with who’s next door and all assets in the 5 x 5 are completely filled.
Chapter VI: Back to the Future!
With repeated attempts of collapsing and backtracking, what we eventually arrive at is a procedurally-generated construction that is uniquely crafted in real time. Every gameplay generated this way is a doorway to a fresh, custom world of your own, constantly changing and adapting to your actions, urging exploration and paralleled discovery.
The beauty of procedural generations is that it allows us to be more than just a player in a game. It allows us to become a part of the world, to shape it and mould it to our will. As we move into a future with AI and meta on the rise, it’s clear that the potential applications for procedural generations go far beyond just gaming. We can anticipate this technique to be used to create virtual patient simulations for medical training purposes or to prototype engineering designs for new products and structures. But the possibilities remain broader than I can imagine.
Chapter VII: The End Game
Having said that, no matter how ahead we’ve come, it still intrigues me how these generations can never truly capture the artistic expression and emotional depth playing a hand-crafted game brings. Just imagining the emotional investment that somebody’s spent hours creating a cohesive narrative over a specific incident or story, attending to every detail and polishing all the seams, and staying up nights trying to resolve a glitch, fix a bug or tweak some game mechanics is beyond impressive to me. I doubt if something so unique can ever be replaced by some artificially generated content that relies on randomness and may not even define a clear sense of purpose and direction.
But what it can certainly provide is an element of surprise and novelty, as well as a sense of scale and continuity to games. Just the sheer scale of some games drive a sense of purpose; that you’re intensely charging to rescue a flourishing civilization from the horrors of an extraterrestrial invasion as giant ships descended from the skies, unleashing a barrage of destruction upon the planet and the fate of humankind rests in your hands! The sense of continuity can be so immersive and rewarding that even side quests aren’t that boring anymore. It’s kinda bitter too when you know you’ve finished the last level of a game, just how quickly it all ended. The attachment to the characters, plot, and storyline can be so strong, that it’s natural to want to continue spending time in this world forever. Thanks to procedural generations, somebody’s got that covered for you!
Chapter VIII: Tempted enough, eh?
If you’re tempted to navigate around by yourself in first person, check out our GitHub!
https://github.com/pramesh025/Procedural-Village-Generation
Developer Credits: Prashant Karn, Pramesh Shrestha, Tripti Sharma :)
