News: 11 March 2016 - Forum Rules
Current Moderators - DarkSol, KingMike, MathOnNapkins, Azkadellia, Danke

Author Topic: Legend of Zelda Overworld Randomizer  (Read 2652 times)

Garmy

  • Jr. Member
  • **
  • Posts: 9
  • Filthy gemini
    • View Profile
Legend of Zelda Overworld Randomizer
« on: September 05, 2020, 05:48:33 pm »
The Legend of Zelda Overworld Generator

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


Progress

Rom Data
  • ✅ Digest and understand existing knowledge on the rom (Huge thanks to Trax for their documentation and various forum posts)
  • ✅ Load and Decode Rom Data
  • ✅ Encode data into Rom Data
  • ✅ Save Rom Data to a file

Region/Pathing Generation
  • ✅ Break up the screens into Regions, defined by one of several "biomes" (StaringZone, MountainRange, Cave, Rocky Coast, Forest Coast, Light Forest, Dense Forest, Graveyard)
  • ✅ Build pathing between screens within Regions (pathing: exits between screens)
  • ✅ Build pathing from Region to Region

Feature Assignment
  • ✅ Assign the Start Screen
  • ✅ Assign Lake Screens
  • ✅ Assign the two Dock Screen
  • ✅ Assign "Twin Screens" (7 screen layouts must be duplicated to fit in the rom)
  • ✅ Assign two Fairy Ponds Screens
  • ✅ Assign Ladder-reachable Overworld Item Screen
  • ✅ Assign Each screen's Cave Destination, including Dungeon Locations
  • ✅ Assign the six screens where Armos hide staircases
  • ✅ Assign the one screen where Armos hides the Power Bracelet
  • 🟩 Assign Buddy Screens (two-screen within a biome that are meant to act as single screens)

Screen Building



« Last Edit: October 05, 2020, 12:57:51 am by Garmy »

Trax

  • RHDN Patreon Supporter!
  • Hero Member
  • *****
  • Posts: 567
    • View Profile
    • Trax ROM Hacking
Re: Legend of Zelda Overworld Generator
« Reply #1 on: September 07, 2020, 03:09:41 am »
Glad to know that my docs are useful  :thumbsup: . 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

  • Jr. Member
  • **
  • Posts: 9
  • Filthy gemini
    • View Profile
Re: Legend of Zelda Overworld Generator
« Reply #2 on: September 07, 2020, 04:37:07 am »
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.
« Last Edit: September 17, 2020, 06:36:13 pm by Garmy »

LadyCannock

  • Jr. Member
  • **
  • Posts: 7
    • View Profile
Re: Legend of Zelda Overworld Generator
« Reply #3 on: September 08, 2020, 05:40:26 pm »
B quest can step aside :D

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

And, will this also affect dungeon layouts?


Garmy

  • Jr. Member
  • **
  • Posts: 9
  • Filthy gemini
    • View Profile
Re: Legend of Zelda Overworld Generator
« Reply #4 on: September 09, 2020, 03:28:03 pm »
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

  • Hero Member
  • *****
  • Posts: 1795
    • View Profile
Re: Legend of Zelda Overworld Generator
« Reply #5 on: September 10, 2020, 10:14:28 am »
Nice! Seems like it could be a lot of fun even just on it's own.

erinnk

  • Jr. Member
  • **
  • Posts: 7
    • View Profile
Re: Legend of Zelda Overworld Generator
« Reply #6 on: September 10, 2020, 01:43:34 pm »
This is really cool, good luck with it!

Garmy

  • Jr. Member
  • **
  • Posts: 9
  • Filthy gemini
    • View Profile
Re: Legend of Zelda Overworld Generator
« Reply #7 on: September 17, 2020, 06:33:06 pm »
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

  • Full Member
  • ***
  • Posts: 173
  • Super Mario Bros. Super Nerd
    • View Profile
    • my gaming tumblr
Re: Legend of Zelda Overworld Randomizer
« Reply #8 on: September 18, 2020, 02:22:44 pm »
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.
Somebody alert me when a user friendly BS Zelda hacking tool is made. I will give my soul to work on a faithful SNES remake of Zelda 1.

ActionGamer

  • Jr. Member
  • **
  • Posts: 49
    • View Profile
Re: Legend of Zelda Overworld Randomizer
« Reply #9 on: September 18, 2020, 03:57:47 pm »
Finally!!!!!!!! Someone is cool and smart enough to make a tool like this.

ultimaweapon

  • Sr. Member
  • ****
  • Posts: 264
    • View Profile
Re: Legend of Zelda Overworld Randomizer
« Reply #10 on: September 19, 2020, 02:03:29 pm »
This is really starting to look awesome. I'm looking forward to trying this out.
Trust in the Heart of the Cards

lexluthermiester

  • Submission Reviewer
  • Hero Member
  • *****
  • Posts: 837
    • View Profile
Re: Legend of Zelda Overworld Randomizer
« Reply #11 on: September 22, 2020, 02:08:47 am »
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

  • Full Member
  • ***
  • Posts: 103
  • Wait, this isn't Burger King
    • View Profile
Re: Legend of Zelda Overworld Randomizer
« Reply #12 on: September 22, 2020, 01:51:42 pm »
This actually looks pretty rad, can't wait to see what else you do with this.
Hey there

Tomato

  • Sr. Member
  • ****
  • Posts: 343
    • View Profile
    • Legends of Localization
Re: Legend of Zelda Overworld Randomizer
« Reply #13 on: September 30, 2020, 01:07:00 pm »
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! :thumbsup:

ActionGamer

  • Jr. Member
  • **
  • Posts: 49
    • View Profile
Re: Legend of Zelda Overworld Generator
« Reply #14 on: October 04, 2020, 11:26:27 am »
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

  • Jr. Member
  • **
  • Posts: 9
  • Filthy gemini
    • View Profile
Re: Legend of Zelda Overworld Randomizer
« Reply #15 on: October 05, 2020, 12:51:02 am »
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

  • Hero Member
  • *****
  • Posts: 1795
    • View Profile
Re: Legend of Zelda Overworld Randomizer
« Reply #16 on: October 05, 2020, 03:18:16 pm »
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

  • Sr. Member
  • ****
  • Posts: 439
    • View Profile
Re: Legend of Zelda Overworld Randomizer
« Reply #17 on: October 05, 2020, 04:29:08 pm »
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

  • Jr. Member
  • **
  • Posts: 9
  • Filthy gemini
    • View Profile
Re: Legend of Zelda Overworld Randomizer
« Reply #18 on: October 06, 2020, 12:24:45 pm »
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

  • Hero Member
  • *****
  • Posts: 504
  • I am the baldest romhacker
    • View Profile
Re: Legend of Zelda Overworld Randomizer
« Reply #19 on: October 06, 2020, 01:53:45 pm »
No need to restrain yourself. Contact me here or here, we'll discuss how make more than 256 columns.
iromhacker.ru - NES ROM hacking tutorials for beginners. Please use Google Translate browser extension