15 August 2019

Overworld Generation I

After all the art mockups, I’ve created a decent amount of tile art and I’ve been itching to get started on using it in some procedurally-generated (PCG) maps. Before going down that rabbit hole, I want to figure out my PCG goals. Or maybe just my higher level goals.

  • A single, streamable overworld. No arbitrary screen partitions like the rooms of most RLs or 2d Zeldas
  • The overworld can have distinct chokepoint(s) that isolate one region from another. The connecting regions can be determined before generation
  • A navigation graph can be defined before generation that describes the top level traversal of the overworld
  • To help with future playthroughs, regions will have a distinct theme and these themes are traversed in roughly the same order

Top-Level Navigation Graph

StartFinal Boss

The purpose of this graph is to guarantee a traversal order of specific landmarks and ensure chokepoints are created to separate the early, mid, late game section of the map. I think starting from a graph is going to offer the most flexibility in the future. It doesn’t really help with the actual placement of landmarks, but having access to graph analysis tech could be useful.

For example, I was thinking of having random events that disable the main path to a region. It unbalances the game by forcing the player to use new dangerous routes. Min-Cut is useful here to identify the route to disable and even to verify the number of routes available. Edge weights are also an interesting way to approximate path difficulty based on monsters and in-game distance.

And thinking on it more, maybe a graph could be used directly in map generation. If each node was represented by a rectangle, I could place constraining springs between rectangles to represent edges. If you put all the rectangles together in the center of the map and used a collision solver to resolve the overlap the placement should satisfy the graph restrictions.

I’m imagining something like this d3 example. Once the rough placement is figured out, I could use standard PCG techniques to fill in the area inside a rect.

graph node collision resolved


I’ve been going back and forth on the theme for a while now. I was pretty sure I would go with either a dnd/fantasy setting or something Sci-fi like Aliens. Both are great settings. The lore is rich, the setting is supportive of interesting mechanics. And there is a wide design space for interesting creatures.

The main drawback of the dnd/fantasy setting is it’s a very common setting already done to death many long running roguelikes and other properties. You’d need to have an especially interesting spin on the genre to break apart from the pack.

I was gearing up to go all in on a Sci-fi setting, but I think I really am more attached to the * Aliens* setting than Sci-fi itself.

So, fallback plan, I’m committing to a fantasy world with vampires and werewolves. Not so much elves and orcs fantasy, but a semi-realistic fantasy set in a Classical civilization. Leaning towards an Egyptian aesthetic, but with Ancient Rome levels of technology and prosperity.

I don’t know if I’ll commit to it, yet, but I like the idea of it being a post-collapse civilization that’s the final holdout against a world filled with dark forces. The humans have come back from complete collapse, but there’s no memory anymore of the modern past. Probably been a few thousands years since the peak at least. There’s a few hints (christianity, plastic?) about the past. The big giveaway of the past are buried mega-structures in the sewer system. I probably shouldn’t explain too much, but the collapse would probably have been caused by a combination of climate change and peak oil.

As is though, I think this collapse thing is little too random. Seeing a bunch of broken, modern tech in a sewer is just going to come across as strange. I think it needs to be tied into the vamps. Could borrow from Vampire Hunter D and make the vamps guardians of old tech. I dunno. I kind of prefer more feral vamps than the decadent ones from VHD. I’ll stick with feral vamps for now and see if another solution comes to me.

Progression Gates

I mentioned above that I want to control progress via locks and other gating mechanisms. Ideally there could also be a way to re-add the lock at a later time. This would be part of a random event feature where I’d alter layout of the map to force the use of alternative routes. At the same time, I don’t want to make a sequential dungeon disguised an an open world. Sequence breaking is fun, and could be a great way to switch up future playthroughs and make them feel new.

I also want to provide exit gates. They’re gates that are convenient one-way paths, usually providing a shorter path to early regions from later regions. You see these a lot in Metroidvanias. Typically as cliffs that you can drop down from but can’t get back up.

I think these would fit in well with my theme:

  • Hard Locks
    • City wall door. Needs unique key. Gate could be re-added by changing the lock, or breaking hte door
    • river+open locks. Lock as in a boat-raising lock. Needs to be closed using a control. To re-add this gate the lock could be blown up
    • sewer entrance. Needs unique key
  • Soft Locks
    • Hardwood: Closer to a hard lock, but can be cut down. You’ll go through a lot of weapons while you do and I mean a lot. You’d have to repeatedly look for new weapons or become a permanent enemy of the guards by stealing their weapons cache.
    • Softwood: Can be cut down without damaging your weapon
    • Locked door: Needs common key. Or can be kicked in
    • City guard: Blocks progress until required event is triggered. Can be killed. but that has severe consequences
  • Exit Gate
    • the sewer has many secret exits that lead into homes or temples. Only visible from the sewer until opened.
    • slum alleyway locked doors

Some of these hard lock - like hte hardwood and river - would also work nicely as map/region borders. Could use them with mountains and city walls to prevent any wandering.

Rough Map Plan

Before I get into PCG, I wanted to rough up how I imagine the game world looking. The idea being to figure out the look of individual set pieces and how they could fit together.

This first layout is a bit rough, but I can explain. Before that the green dot is where you’d start; Skull is the final boss/goal; Black squares are buildings; Grey lines are roads/walkways, except the light-grey is a wall :p; A friendly blue river; And red squares are hard locks.


Some key points:

  • The starting area is simple. I’d like to follow a classic design principle where the intro is mostly sequential/confined so it isn’t overwhelming and can teach basic mechanics
  • Gate/Hard Locks prevent unlimited exploration. There’s a river crossing and a city wall door. Most likely, one lock would only be opened by exploring the other locked region.
  • Compact map design. The map generation should do its best to create hubs where many parts of the map can be accessed. A good mix of breadth and depth.

This next map is a top-down view of some of the landmarks that would appear. I’m taken inspiration from Ancient Rome, so the most common structures are going to be apartments (with variations on room size), large homes owned by the rich (with unique layouts), public baths, and temples.

map concept

In the top-left you can see a bath and temple. And another temple near the bottom. I think there’s all kind of interesting ways to generate these. Secret rooms in the back could work like mini dungeons.

map concept baths

The right of this is a manor design, though I think it’d need to be much bigger. I was imagining this as the hiding place of the final boss. It’s completely surrounded by hardwood and walls making it inaccessible except from the entrance on the left. Probably guarded by high-level thralls.

I like the ideas of the hardwood wall being adjacent to the starting area. I feel like it’d make it extra shocking when you find out how close you were to the main baddie this entire time. And if you were curious you could try and cut it down and have a go at the boss early.

map concept boss

Every city needs a main road for parades and junk. i drew little green dots on mine to represent softwood after I saw the similar on a recreation of Alexandria. The main road will be a consistent feature in every PCG city, being a direct path to the city walls and having some consistent landmarks along its route. It’ll be one of several landmarks providing familiarity on future playthroughs.

map concept roads

The rest of the city is more apartments, homes, and baths. I hadn’t thought too much about gates when I made this. It’s more of an exploration of interesting landmarks that could populate the city.

And I should mention the rural area. Outside the city wall is a little rural region with farms and forests. This is where one would become exposed to werewolves and other dangerous beings that can take advantage of large open areas. I don’t have it shown, but this is where I’d likely place entrances to initially access the sewer region. The sewer would be more of a late-game region. It pretty much opens up everything since it connects to so many parts of the city.

Map Size

For fun, I took a map of the Legend of Zelda: A Link to the Past and shrunk it so 1 px = 1 tile. It ends up being 256x256 px; Not too far from the map concept above. I thought this was an interesting comparison because it can take a good 3-5 minutes to travel between some of the farthest areas in ALTTP.

zelda snes map

Exploration is a key feature of ALTTP and it expects you to backtrack a fair amount over the course of the game. I’d like to think the developers kept a close eye on the travel time as they designed the map. One, to ensure it didn’t get too big and, two, that landmarks connected in ways that the travel time never got too long.

There’s a fine line between an large, interesting overworld and a giant, boring one. I think gamers prefer the latter these days, and quick travel is mostly a response to that. The sense of scale of a large world is interesting, but I don’t think it’s an inherent good. Balance.

I’d also like to emphasize exploration, but more on the scale of ALTTP, so I think I’ll be keeping an eye on the size of my maps.