[Garmy]

The Legend of Zelda Overworld Generator

Break out the Graph Paper, an infinite series of new quests awaits you!

This is a Windows program that takes in an original LoZ rom and procedurally generates a new overworld map from scratch.

This project is Open Source and can be found Here on Bitbucket

Download Here


Features

A fully randomized map, including new map layouts, screen layouts, dungeon locations, and environments.

• Seed-based generation - The same seed will always produce the same map
• Randomized Map Layouts - Every map is laid out differently
• Randomized Screen Layouts - Each environment has its own rules for procedural generation, creating a new experience every time
• Three new environments - A more convincing Desert, a snaking River, and a Haunted Forest
• Randomized Ladder-Item Location - It can show up on any screen with Coasts or Lakes
• Smartly Placed secret bushes and bombable walls
• Randomized Start Screen - Will always appear along the border of the map, making it easier to chart the world
• Randomized Locations of Dungeons, Caves, Armos Stairs, and Power Bracelet
• New Enemy Placement
• Option to change the overworld's color palette
• Compatible with Fred Coughlin's randomizer[/url] (as long as you run that randomizer before this one)

Scroll through the posts in this thread for more examples of generated screens.

[Trax]

Glad to know that my docs are useful  . Seems like a good start so far. Do you use some kind of noise generator for the generation of regions? Do you reuse the original screen layouts or do you build them randomly as well?

[Garmy]

They were very useful haha. I couldn't have even started without them.

I wrote and rewrote like a dozen algorithms for defining regions until I settled on one. In a nutshell, it does:

• chooses eight screens in a 2x4 pattern along the edges of the map and set that to the start zone
• makes regions out of coast screens with a max length and randomly decides if they're forest or mountain
• makes a mountain range region of a random size with a min and max height and width and places it randomly.
• places a 2x3 or a 3x2 region for a graveyard and randomly fits that in.
• places as many 3x3 chunks of light and dense forest regions as it can fit, each one in a random location
• finds any 1x3 or 3x1 stretches and sets them to Cave biome regions (they currently have a checkered pattern in the screenshots but in the end will mimic the three mountain screens to the right of the start in the original rom)
• finally, loops through all remaining screens that weren't given a region and puts them in the same region as one of its adjacent screens

Deciding which screens exit into which screens is done like this too... That is, a bunch of rules and logic, instead of any sort of pure randomness.




I'm building screen layouts randomly. Well, through procedural generation.

Each screen is built (or will be built) as a tile map, ignoring existing columns in the rom.

When the rom is saved, I have a class that interprets all the screen data and builds columns, layouts, and screen properties, then encodes it all into the the formats the the rom expects.


So far my biggest concern is running out of column data space. I can remove the topleft, topright, bottomleft, and bottomright corners of mountain tiles and that saves a ton of columns but it looks kind of janky.

Hoping at some point I can figure out how to expand the rom or something to allow unlimited columns... But that might be beyond my skill level atm.

[LadyCannock]

B quest can step aside

Will there be some specific areas that remain the same, such as the starting point?

And, will this also affect dungeon layouts?

[Garmy]

The starting point is randomized but will be a screen touching the border. This helps with building a mental map. Neither dungeons or items will be randomized, only the overworld. My hope is that you can run a rom through the existing randomizer, and then run it through this overworld randomizer.

[Vanya]

Nice! Seems like it could be a lot of fun even just on it's own.

[erinnk]

This is really cool, good luck with it!

[Garmy]

Thanks for the support! I think it'll be a lot of fun when its done.


Progress Update

I've been building more biomes and features. I hit a wall at one point where I was running low on column data. Without being too technical, there's a limit to how much rom space you have for designing screens. Looking through the rom's data, I found a chunk of 0x6B0 (1712) unused bytes at the end of Bank 5. The place where that data lived originally had about half that space, so this was a nice find, especially after all the research I did when I thought I had to expand the rom and move the data to a blank bank. There's still a limitation of 256 total unique columns, but I think I can stay under that with some clever decision making in the procedural generation.

After I moved that data out, I realized that the screen layout data immediately preceded the data for columns. Since that following data is now blanked out, I'm able to use that to add more screen layouts. There's a total of 130 layouts needed (128 screens plus the two interior cave screens) and the rom seems to only allow 128 total layouts regardless of space. This means I need to use the same layout on two screens, which isn't so bad because originally, I needed to find 7 screens to use the same layout on. This allowed me to be more strict in the conditions required for a screen to be qualified as an option to clone. For example, I can now ensure the four screens surrounding the cloned screens match, allowing me to control the width and style of the edge tiles.

Okay, enough technomumbojumbo!

To better manage my progress on actual screen building, I made a little chart:



Each biome has to be generated individually and special screens (dungeon entrances, fairy ponds, armos screens, etc) differ slightly from biome to biome. Additionally, each biome has has its own rules for their design... A forest screen looks much different than a mountain screen, and that difference is more than just using trees vs rocks.

Also for my sake of sanity, Biomes that aren't designed yet just have ground tiles, which you'll see in the following screenshots.


Screenshots!

A couple examples of the whole map:





You can see the undesigned screens are blanked out of all features.



And here's a bunch of neat screens I liked that were generated...

Starting screens:



A Dock screen:



Overworld Item can be on lakes and the planks going in other directions:



More varied Graveyards:



Any Road:



Fairy Ponds:



Dungeons:



And then just some random screens I liked:

[pocket]

This is great, if this can play nice with the dungeon randomizer, I feel this will make Zelda 1 the best game to play with a randomizer. Better have stacks of graph paper ready to map everything like it's '87.

[ActionGamer]

Finally!!!!!!!! Someone is cool and smart enough to make a tool like this.

[ultimaweapon]

This is really starting to look awesome. I'm looking forward to trying this out.

[lexluthermiester]

This is really starting to look awesome. I'm looking forward to trying this out.

Have to agree, this looks like it could be a lot of fun!

[DannyPlaysSomeGames]

This actually looks pretty rad, can't wait to see what else you do with this.

[Tomato]

I'm super-excited to see this, as it's something I've wanted to program for years myself, along with randomized dungeon creation. This looks to be a lot of fun and I can't wait!

[ActionGamer]

Thanks for the support! I think it'll be a lot of fun when its done.


Progress Update

I've been building more biomes and features. I hit a wall at one point where I was running low on column data. Without being too technical, there's a limit to how much rom space you have for designing screens. Looking through the rom's data, I found a chunk of 0x6B0 (1712) unused bytes at the end of Bank 5. The place where that data lived originally had about half that space, so this was a nice find, especially after all the research I did when I thought I had to expand the rom and move the data to a blank bank. There's still a limitation of 256 total unique columns, but I think I can stay under that with some clever decision making in the procedural generation.

After I moved that data out, I realized that the screen layout data immediately preceded the data for columns. Since that following data is now blanked out, I'm able to use that to add more screen layouts. There's a total of 130 layouts needed (128 screens plus the two interior cave screens) and the rom seems to only allow 128 total layouts regardless of space. This means I need to use the same layout on two screens, which isn't so bad because originally, I needed to find 7 screens to use the same layout on. This allowed me to be more strict in the conditions required for a screen to be qualified as an option to clone. For example, I can now ensure the four screens surrounding the cloned screens match, allowing me to control the width and style of the edge tiles.

Okay, enough technomumbojumbo!

To better manage my progress on actual screen building, I made a little chart:



Each biome has to be generated individually and special screens (dungeon entrances, fairy ponds, armos screens, etc) differ slightly from biome to biome. Additionally, each biome has has its own rules for their design... A forest screen looks much different than a mountain screen, and that difference is more than just using trees vs rocks.

Also for my sake of sanity, Biomes that aren't designed yet just have ground tiles, which you'll see in the following screenshots.


Screenshots!

A couple examples of the whole map:





You can see the undesigned screens are blanked out of all features.



And here's a bunch of neat screens I liked that were generated...

Starting screens:



A Dock screen:



Overworld Item can be on lakes and the planks going in other directions:



More varied Graveyards:



Any Road:



Fairy Ponds:



Dungeons:



And then just some random screens I liked:

Do you have any idea when the next build will be ready to download?

[Garmy]

Thanks guys I cant wait till everything is polished up and you can all try it out, too.

Current Build

Do you have any idea when the next build will be ready to download?

I just uploaded a preview build of the current state if anyone wants to try it out.

DOWNLOAD PREVIEW BUILD: October 4, 2020

Keep in mind that this is still pre-beta so there are lots of features missing.

To use it, Load your original Zelda.nes rom into it, choose/randomize a seed, and hit Generate. You can save the generated map out as a rom with the Save As button.

On the Full Map tab, you'll see a message that says "Column Bytes Uses: XXXX of 1712 | Columns Used: XXX of 256". If you save a rom where either of those values is over their maximum (like, 280 of 256), it'll be a bad rom. Only save if both values are under their threshold.

Also on the Full Map tab, if you change the scale, you have to generate the map again to see it at that scale.


Progress

I designed and built an algorithm for the Dense Forest Biome.





For fun, here's a few overworld shots when I set every Biome to the Dense Forest. I think it looks pretty neat







Also, I built some Decor screens. Basically these are screens with some aesthetics built into the middle to serve as mental landmarks and vary up the environment a bit.

Here are some examples:









Other than these, most of my progress lately has been code-related. General refactoring, taking care of bugs, re-organizing some architecture. Fine tuning the algorithms of Biomes. The invisible stuff.


He's an updated Progress chart:




A Major Concern

During the last update, I mentioned how I found more space for screen data, but still had a limitation of 256 columns.

I still have a few Biomes to design, and already I'm over-budget by an average of 20 or so columns.

I don't know what to do about this.

One idea is to take off the Trim. Trim is when you set the edges of rock and water features to edge tiles. Maybe a visual example would help.

No Trim:


Yes Trim:


It's a huge difference, with the main difference being that one looks like trash. I hate it.

But, it does save 50 to 100 columns on average.

So after I design the remaining biomes, I'm going to have to take some serious audits and figure out where all the overhead tends to come from.

I did build a Column viewer, which looks like this:



The white number is the Column ID, and the Yellow number represents how many times that column was used in the whole map. Ideally there shouldn't be too many 1's, and the average should be around 8 uses per column.


If I cant figure this out and stay under budget, I only have a few options:


1. Don't include Trim
2. Figure out some ASM hack or something that'll remove the 256 limit (which is way more advanced than I'm capable of)
3. Let this rot in my "Unfinished Projects" folder and go do something else.

🤷‍♂️🤷‍♂️🤷‍♂️

[Vanya]

That 256 limit is because it is programmed to only use one byte for column IDs, right?
That could be quite a hassle, yeah. Might be worth it though.

Removing the trim does indeed look terrible.

Think it over, I'm sure a solution will pop up when you least expect it.

[Queue]

My suggestion would be to manage the overflow in the random generator.

One approach would be to keep what you have now, and if there are more than 256 column types, iterate through them, and on each that is only used once, check for a near match and replace its use with the near match until you're down to exactly 256 types.

To avoid always killing the first single-use columns encountered, you could set it up to keep looping through columns, using a random number (deterministic, using the same system you're already using for randomness) to decide if the current column should be replaced, and a fairly strict matching requirement (so if there are no matches similar enough, skip it and continue). In an extreme case this cause an infinite loop; plenty of options to deal with that though.

The mechanism to find a near match is what I expect would take most programming time. This is a brute force approach, but would retain most of what you have while conforming to the game engine's limitations.

[Garmy]

That 256 limit is because it is programmed to only use one byte for column IDs, right?
That could be quite a hassle, yeah. Might be worth it though.

Removing the trim does indeed look terrible.

Think it over, I'm sure a solution will pop up when you least expect it.

That's correct. It would definitely be worth it if I had any idea how to do it. I've done a ton of research into it, but not knowing ASM is a huge hurdle obviously haha. I'd have to rewrite the routine to look at two Bytes for a column ID, but even then, there's not enough space in the Rom to jam double the bytes in for that space. There's almost enough room if I used 1.5 bytes per column ID. I'd have to add some banks and dedicate one to the column data. This kind of work is a bit out of my league at the moment.

My suggestion would be to manage the overflow in the random generator.

One approach would be to keep what you have now, and if there are more than 256 column types, iterate through them, and on each that is only used once, check for a near match and replace its use with the near match until you're down to exactly 256 types.

To avoid always killing the first single-use columns encountered, you could set it up to keep looping through columns, using a random number (deterministic, using the same system you're already using for randomness) to decide if the current column should be replaced, and a fairly strict matching requirement (so if there are no matches similar enough, skip it and continue). In an extreme case this cause an infinite loop; plenty of options to deal with that though.

The mechanism to find a near match is what I expect would take most programming time. This is a brute force approach, but would retain most of what you have while conforming to the game engine's limitations.

I've thought about doing something like this. The biggest challenge would be determining what qualifies as an acceptable near match for the column. There's a high potential for screens to have columns looking wildly out of place, especially if two adjacent columns get replaced.




I think the only real solution is to come up with creative ways to re-use layout configurations. For example, if I remove all lakes and coasts, I save between 60 and 100 column, which is huge! I could keep lakes and coasts in if I limit the circumstance they're used. I could make it so that dungeons can't appear on screens with lakes, or disallow lakes from appearing in Graveyard. Other thing I could do would be to make it so the center screen of lakes can only exit west and east, positioning armos statues so that theyre not in the same column as ladders/blank edges, and forcing both Fairy lakes to use the same environment. I think these are the types of things I'll have to focus on.

It's kind of a bummer since that'll lead to less variation between seeds, but I don't see any other way around it.

[Cyneprepou4uk]

No need to restrain yourself. Contact me here or here, we'll discuss how make more than 256 columns.