Second Pass At ASCII Open-World Map Generation
Now You're Thinking With Blocks
(This post is a continuation of the concepts and problem statement laid out in this previous post, go read, or at least hastily skim, that one first)
Wow this way of doing it is so much easier lol.
Mental Blocks
So, at the end of the last iterative cycle of mapgen, I came to the conclusion that using a singular space of the map as the atomic unit during procedural map generation was, to use the technical terms, stinky and bad. For any playable-size map, the runtime complexity of my mapgen algorithms led to the whole thing chugging like Thomas with a hangover, and it also led to really bizarrely shaped maps that didn’t really feel like a city.
This iteration, I decided the first step I should take is to reconsider the fundamental unit used in generation from the space to a block. Programmatically, a block is an NxN collection of spaces, and the objects contained therein, which can be gridded together to former a larger space. Design-wise, a block is a simulacra of a city block: a unit of space defined by the four streets which encapsulate it which contains streets, buildings, people, landmarks, etc.
The move to blocks naturally leads itself to dramatic gains in algorithmic performance. Since they serve as abstractions of large sections of the game map, random map generation can be performed with a proportionally much smaller number of blocks than spaces, meaning that algorithmic inefficiencies which proved fatal in the old logic are now easily swept under the rug. If you want a 1000 space by 1000 space game map, processing it space-by-space required the handling of one million spaces, enough to potentially turn into a slog in iterative algorithms. However, if you divide that map up into 100 space by 100 space blocks, suddenly we have a 10 block by 10 block game map, and retooling those old algorithms to work on a basis of blocks means they only have a total of 100 blocks to deal with, a reduction of the problem space by a factor of 10,000, which is pretty fuckin’ good if I do say so myself.
The use of blocks will also help down the line (implementation outside the scope of this post, but definitely coming) with map streaming, a commonplace practice of conserving memory-usage in open world games like this one.
In a naiive approach, one might simply load the entirety of a game’s open world at once as soon as the game is launched (this is technically impossible for high-fidelity 3D open world games like your modern Rockstar or Bethesda game, but hypothetically doable for something as small as Ascetic, so let’s humor the idea). However, on top of this requiring a massive consumption of space, in a simulation-heavy game such as Ascetic, having all of the map loaded at once means you’ll be running those simulation tasks, such as evaluating NPC AI actions based on their environment, for literally everything in the game, hogging valuable processor cycles.
Instead, most games opt to stream their maps in based on proximity to the player, essentially freezing all of the game world except that which the player is either currently interacting with, or within their near range. Consider the below diagram:
In this example, the hastily-drawn-with-a-laptop-trackpad pink dot is the player. Only the 3x3 grid of game map, centered upon them and shaded in green, is loaded, with the various “living” systems of the game being tracked and simulated. Everything in white is essentially in cold-storage, not being tracked at all as it is currently irrelevant to the current game-state. As the player moves into the block north of them, the spaces they are moving away from are de-loaded and put back into cold-storage (drawn in red), while the spaces they are moving towards get loaded in to replace them (drawn in yellow). For a AAA example, check out this GIF of a similar concept called frustum culling (which is the same idea, but instead loads or unloads based on if something would be in view of the player) in Horizon: Zero Dawn.
Anyways, yeah, dividing the world map into blocks will help me implement something akin to this down the line. Let’s dive into some code and I can show how much easier this is then that old bullshit I was doing.
Generating The Blocks
world_size = game_constants.size_world
initial_block_size = game_constants.initial_block_size
if initial_block_size > world_size:
raise ValueError("Size of initial starting landmass cannot be larger than size of initial map")
world_fill_percentage = game_constants.world_size_percentage
filled_spaces = []
#1. Instantiate an empty grid of blocks, then fill with the initial blob
world_map = [[0 for x in range(world_size)] for y in range(world_size)]
center_fill_count = world_size - initial_block_size
for n in range(floor(center_fill_count/2), len(world_map) - ceil(center_fill_count/2)):
for m in range(floor(center_fill_count/2), len(world_map) - ceil(center_fill_count/2)):
world_map[n][m] = 1
filled_spaces.append((n, m))So, our logic starts somewhat similarly to how it did previously, by first reading in parameters from our game config on the total size of the game world world_size and the percentage of the world we want filled world_fill_percentage. Remember, these now represent blocks, not spaces, so a world_size of N represents a game world of NxN blocks, or (N*M)x(N*M) spaces, where M is the edge length in spaces of a single block.
We also have an extra bit here, initial_block_size. This ties into another logical change I made in this implementation: instead of filling the world and whittling it down to the desired size like I did last time, we’re instead going to start with a really small initial landmass in the center and build out. This means I get to skip all of the island detection stuff that I had to mess with in the last implementation. initial_block_size is the size of the square of blocks in the middle of the map that will be initialized to filled, and we have a quick check there to make sure it doesn’t exceed the size of the whole map.
We then instantiate the map, again starting off just by using an integer value to represent the state of a given block (0 being “nothing’s here”). We then do a little bit of math to determine where our initial blob of filled blocks should go given the size of the map and the initial_block_size, and toggle all of those blocks to a value of 1 (the value for “city block”).
You’ll also note that when I fill a block, I’m appending its coordinate to a filled_spaces list. A couple operations down the line only need to be done to blocks that have something in them, so by maintaining this (relatively memory light) list as we generate the map, I save myself the work of having to identify if blocks are filled or not later.
#2. Append new blocks randomly onto the edges of the playable game space
goal_world_size = ceil((world_size ** 2) * world_fill_percentage)
while len(filled_spaces) < goal_world_size:
space_to_build_upon = choice(filled_spaces)
direction_to_build = randrange(0, 4)
if direction_to_build == 0:
new_space = (space_to_build_upon[0], space_to_build_upon[1] + 1)
elif direction_to_build == 1:
new_space = (space_to_build_upon[0], space_to_build_upon[1] - 1)
elif direction_to_build == 2:
new_space = (space_to_build_upon[0] + 1, space_to_build_upon[1])
elif direction_to_build == 3:
new_space = (space_to_build_upon[0] - 1, space_to_build_upon[1])
if new_space not in filled_spaces and new_space[0] in range(0, world_size) and new_space[1] in range(0, world_size):
world_map[new_space[0]][new_space[1]] = 1
filled_spaces.append(new_space)Now, from our initial blob of blocks, we build outwards. We do a quick calculation to figure out how many blocks we should fill by the end of mapgen (which also means we can compare that number to the length of filled_spaces to make a really simple loop terminator).
Then, until we have the number of blocks we need, we simply randomly select a block from filled_spaces, randomly select one of the cardinal directions from that block, and if that adjacent block isn’t filled and is in the map, we fill it!
Is this efficient? Hell no, there’s gonna be a lot of loops wasted on attempting to fill blocks which cannot be filled or don’t exist and failing, but also, I don’t care! The newly shrunk size of our problem space means I really don’t care about those inefficiencies, and don’t think they’ll meaningfully impact our runtime (but if I do need to shave milliseconds down the line, here’s a perfectly acceptable place to do so).
Edging For Fun And Profit
This next step requires a little bit of preamble (although it isn’t actually that complicated).
Conceptually, in order to make sure all of the game map fits together the way I want it to, I’ll be designing all of the city blocks in such a way that their edges double as roads. That way, when I fill the grid of them together, they will naturally generate a gridded road system which spans the entire city and helps stitch the entire thing together, making it look a little more cohesive. I can even fill in some extra roads within a single block to vary the cityscape a little bit, as so long as I maintain the edge roads, it should all connect together.
However, framing all of my blocks in these sort of half-streets doesn’t work if that block is on the edge of the city, adjacent to an empty space. Doing so leaves that outward-facing edge this weird sort of half-street, split down the middle. As a result, I need to define a sort of “in-between” sort of block, one which isn’t a full city block, but needs to essentially stitch together the city block on one or more of its sides with the empty blocks on the other. Moreover, multiple versions of this edge-stitcher block are needed, depending on the exact shape of edge it is adjacent to. Luckily, we can use the fact that we are currently storing all of our blocks as integers to our advantage here.
#3. Identify spaces on the boundaries of the created land-mass, identifying what kind of edge they are for later population
for x in range(world_size):
for y in range(world_size):
if (x, y) not in filled_spaces:
bit_flags = 0
# Check each neighbor and, if it exists, flip the corresponding flag bit
if (x+1, y) in filled_spaces: # Below
bit_flags += 2
if (x-1, y) in filled_spaces: # Above
bit_flags += 4
if (x, y+1) in filled_spaces: # Right
bit_flags += 8
if (x, y-1) in filled_spaces: # Left
bit_flags += 16
world_map[x][y] = bit_flagsAh, shit, I need to explain to you how binary works.
How Binary Works
The number system you are most used to is what we call a decimal numbering system: that is, it increments a digit whenever exceed a power of 10. So, for example, 0 through 9 are all one-digit numbers, but when you increment 9 to 10, you’ve reached a power of 10 (that is, 10 to the first), and thus your value spills over into the next digit column and you reset the last one to 0. More generally, a number of digits ABCD is equivalent to a value of A times 10 to the third plus B times 10 to the second plus C times 10 to the first plus D times 10 to the zeroeth. So, if you have 9341, that number is equal to:
(9 * (10^3)) + (3 * (10^2)) + (4 * (10 ^1)) + (1 * (10^1))
(9 * 1000) + (3 * 100) + (4 * 10) + (1 * 1)
9000 + 300 + 40 + 1
9341This is self-evident to the point of ludicrousness when dealing with decimal numbers, but sometimes we want to use a counting system with a base other than 10. For instance, in the realm of computers, the funamental unit of memory is a bit, which can only be in a state of “on” or “off”, and thus if we want to represent numbers in such a system we use a base of 2 instead of 10, which is what binary is.
So, take the binary number 1001. We can determine its value the same way we did 9341, just by swapping out the base of 10 for a 2.
(1 * (2^3)) + (0 * (2^2)) + (0 * (2^1)) + (1 * (2^0))
(1 * 8) + (0 * 4) + (0 * 2) + (1 * 1)
8 + 0 + 0 + 1
9So, binary 1001 is equal to decimal (or, if you prefer, regular) 9. We could increment this number by 1 to 1010, which is 10, and then again to 1011, which is 11, and so on, eventually maxing out the fourth digit and needing a new column, leading to 10000, which is 16.
Why Did I Just Teach You Binary
So, back to the code block.
#3. Identify spaces on the boundaries of the created land-mass, identifying what kind of edge they are for later population
for x in range(world_size):
for y in range(world_size):
if (x, y) not in filled_spaces:
bit_flags = 0
# Check each neighbor and, if it exists, flip the corresponding flag bit
if (x+1, y) in filled_spaces: # Below
bit_flags += 2
if (x-1, y) in filled_spaces: # Above
bit_flags += 4
if (x, y+1) in filled_spaces: # Right
bit_flags += 8
if (x, y-1) in filled_spaces: # Left
bit_flags += 16
world_map[x][y] = bit_flagsOne of the nice things about binary is that, if you want to manage a variety of two-state conditions (that is, things that can only be one way or another), a simple, compact way you can represent all of those conditions at once is by using a binary number and associating each column (or bit, if you will) of the number with one of those conditions.
That’s precisely what I’m doing here. So, what I’m trying to do is identify which of those blocks not currently filled are adjacent to one or more edges of the filled blocks, and note specifically where the adjacencies lie, so that I may fill the block with content so as to better mesh with the city as generated.
Towards this goal, I give each of these blocks a five digit binary number, and toggle each column between 1 and 0 based on if the block is adjacent to a filled block in that direction. The lower edge is given the second column or bit (2^1, or 2), the top edge is given the third (2^2, or 4), the right edge the fourth (8), and the left edge the fifth (16).
You might notice that I’m not using that far-right first column, the ones place. That’s because I’m reserving the numbers 0 and 1 in the map for totally empty blocks and filled city blocks, respectively, so I don’t want to also use those values to represent one of these edge blocks, so that bit is off-limits.
So, if you want an example, imagine an empty block has a filled city block to its north and east, like so:
When I check that empty space, using the logic above, its value will be equal to 12, as the above and right edges are adjacent to filled city spaces. 12 in binary is 01100, which means that, down the line, if I want to see if this particular space has a northern neighbor, all I need to do is check to see if that third column has a 1 in it, the rest of the number is totally irrelevant. 5 unique states of data are all able to be stored, without interfering with each other, in a single number with up to 32 different states of configuration. If I need more, all I’d need to do is add a single extra column to the number, and I’ll double the number of states I can assume.
Once we generate this state-storing number for a given space, it gets reinserted as its value in the world_map.
The Space Between Us
I’ve been throwing around the words “blank” or “empty” to refer to spaces that aren’t being filled with city blocks, but the more I think of it, the more I think that verbage shouldn’t necessarily be correct. A city is not literally an island, and I think it instead would lead to some far more interesting design space if instead of filling those “empty” spaces with a literal, untraversable nothing, if instead I filled them more with the poetic nothing: the sticks, the boonies, more of the road trip-vernacular version of nothing.
This opens up some extremely interesting design space for me. I can have these city outskirts serve as a sort of staging area for player’s runs, being a low-difficulty external area in which the player starts and can prepare to enter the city proper, filled with hostiles and dangers as it is, once they’ve collected some resources (and, in early runs, some game sense). It also literally allows the player to tackle the city from multiple angles, as they may circumnavigate the city through the outskirts until they find the exact spot they wish to enter and begin their would-be assault.
It also just gives me a little bit more possibility space in the world and narrative design. When the Big City is filled with eldritch gods and their worshippers and dark magic and monsters and all sorts of crazy shit like that, what is driven out towards its outskirts? The surroundings of a city are a lot of things: it contains the less-than-glamorous infrastructure the city needs to survive but doesn’t want within its borders, it frequently contains a city’s working class, irrevocably bound to the city but unable to afford it, and with big enough cities it frequently contains its opposite, driven out and calcified against the city’s prevailing ideology (my lovely home of Seattle, bastion of liberalism and leftism as it is, is surrounded by towns which are, to use the political jargon, chockablock with racists). What do all of those things look like for a city filled with literal monsters. Is it a bastion of sanity and normalcy, or is it full of the people so crazy that even the crazy people don’t want to associate with them? Maybe both?
Next Steps
With where we’re at now, we have a layout of the entire game map in terms of blocks, and we know, at least vaguely, what should be in those blocks. The immediate next step is to take that map of blocks and translate it into actual traversable game world: take each block, generate what that block should actually contain, on an individual-space scale, and save that generation in such a place that it can be streamed in on the fly during gameplay.
As a part of that, we should once again rebuild the Neighborhood generation: determine where the 5 Gods our player hopes to kill are, and extend their influence over the map, using that to determine precisely what kinds of things to spawn where.
We’re also going to need to define those things that can actually be spawned: characters, items, buildings, geographic features, and the like. This, frankly, is going to be a massive proportion of the design work, as games such as these live and die on the variety they can produce from the individual atoms of their game content, each enemy and item a sort of Lego brick that the procedural generation algorithms tear down and rebuild every run to generate something hopefully novel enough to keep the player’s attention.
On top of that, as we start thinking through all of these things that we generate, we want to start thinking about what I like to call systemic dimensions of interaction, or more plainly, the various traits of all of the things in the game world that I want to track for the purpose of systems-driven gameplay. The greater fidelity I render all of these things in, not graphical fidelity but their systemic properties, the (hypothetically) more complex systemic interactions can emerge naturally through gameplay.
For example, one dimension of interaction I definitely want to include is flammability. Fire’s fun, it does a lot of crazy shit, and if properly implemented, can result in a lot of very interesting game moments. Wooden barrier in your way? Burn it down! Need to deal with a large group of low-health enemies? Start a big ol’ fire! Imagine the reaction a player will have when they approach a boss battle and see him flinging fireballs, and remember an off-handed comment that some shopkeeper made an hour ago that their healing potions, the ones the player bought 30 of before this fight, are super flammable. Do you huck them all in a corner? Do you just try not to get hit? Do you start hurling them like molotov cocktails? Hell, maybe you’re feeling a little lucky, and hurl yourself at the boss like a human powder keg, hoping you make it out of the blast better than he does.
I find this sort of systemic design the most interesting part of the entire field of game development, the place where game design and player ingeneuity form a feedback loop with each other to produce increasingly interesting situations, like if you set up an ant farm and then came back to see that the ants accidentally simulated a mass pandemic event, or started a religion, or had somehow built another, smaller ant farm inside of the ant farm.
In Fact It’s So Compelling I’m Putting This Project On Ice And Coming Back To It Later LMAO
It’s the new year, commonly a time when people reevaluate their goals and set a guiding philosophy for themselves for the next 12 months. I don’t really do New Year’s Resolutions (I find that creating such a large timebox for lofty goals often results in a sense usually around April or May that I’ve “fallen behind” on my goals in such a way that I need to “catch up”, usually an effort so large due to the size of the goal that I just absolutely give up on the whole thing, take the L, and accomplish nothing resembling the goals I set. I might actually write a post soon about my new habit-tracking, er, habit), but what I do instead is pretty frequently do a bit of self-reflecting and thing about what I want to get done, and what I want to do for the near future is work on developing my ability to finish.
I tweeted about this in response to Much Better Game Developer Than Me Rami Ismail (also, go check out Rami’s stuff, all of his and his co-developers’ games are incredible, he’s given dozens of super fascinating talks, is a fantastic advocate for Muslim and Middle Eastern representation in video games including the absolutely deplorable state of the use of Arabic in games, and has a wonderful substack of his own), and he gave me this extremely good piece of advice.
Anyone who has made the absolute mistake of talking with me about the stuff I’m working on knows I suck absolute ass at finishing a project. I’ll change projects again and again and again, but I’ll never finish them, just lose interest and move on from one to another to another, slowly building a sort of Island of Misfit Toys in my wake, things I spent a month on and tossed aside.
And yes I’m aware that I am doing that again, right now with Ascetic, but with good reason. That last section about cool systems and procgen and emergent gameplay, all of that is scope, all of that is time I need to spend, skills I need to develop, knowledge I need to learn, and as it stands right now, I can do all of that. I do all of that a lot. What I am absolutely awful at doing is finishing a project, and that’s the skill I want and need to develop right now, and Ascetic is not a project that’s going to let me practice that skill as much as I want.
So, Ascetic is, hopefully, the last new arrival to my Island of Misfit Toys. I’ll come back for it, I find this idea too compelling, but to do it justice, there’s one skill in my skillset that is absolutely not up to snuff, and that’s my ability to cross that finish line. So, I’m developing that now.
Up Next
I’m going to continue to post regular devlogs, but they’re going to be for the new set of projects I have for myself, and projects plural is key there. If I want to develop my Finishing Stuff Muscle, I have to do that through repeated use, and that means taking on small projects, being mindful of pacing and scope, and releasing them.
This also means a bit more learning on my end: I’ve historically stuck to fairly powerful but also high-investment game development architectures, either programming games entirely from scratch (such as Ascetic) or using the extremely beefy but also extremely fiddly Unity.
No more of that, that’s standing in the way of me being Done. This year, I’ll be embracing tools which help me to iterate and release games faster. I’ll be working in Godot, a game engine and development tool which is generally less powerful than Unity in exchange for a far greater ease of use, and I’ll be embracing highly specialized development tools like GB Studio, PICO-8 and, fuck it, maybe even RPG Maker, tools which abstract away a lot of the underlying coding of game development, trading away control and the possibility space of development in exchange for ease of use.
With these together, I’m gonna make games, a lot of games, a lot of small games. Honestly, probably a lot of weird, shitty, broken little games, because I’ve realized recently that I really, really love little, weird, shitty, broken games, and that I should make some too. Maybe I’ll write on here about some of my favorite little weird shitty broken games, too.
When this exercise is done, or perhaps more accurately once I’ve been doing it for a while, because ideally this is a kind of development I want to keep doing in perpetuity, I’ll have a great sense of scope control, a greater ability to call something done, a greater ability to call something good-enough and move on, and most importantly of all, a greater rigor and regularity in how I work on games which will allow me to make constant progress on my projects towards a visible end, a rigor and regularity I will be happy to bring back to projects like this.