Romhacking.net

Romhacking => Personal Projects => Topic started by: Garmy on September 05, 2020, 05:48:33 pm

Title: Infinite Hyrule - Legend of Zelda Overworld Randomizer [Released!]
Post by: Garmy on September 05, 2020, 05:48:33 pm
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 (https://bitbucket.org/Garmichael/infinite-hyrule/src/master/)

Download Here (https://bitbucket.org/Garmichael/infinite-hyrule/downloads/)


Features

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


(https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/overworldss1.png)
(https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/overworldss2.png)
(https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/overworldss3.png)

(https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss1.png)(https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss2.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss3.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss4.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss5.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss6.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss7.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss8.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss9.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss10.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss11.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss12.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss13.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss14.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss15.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss16.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss17.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss18.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss19.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss20.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss21.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss22.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss23.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss24.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss25.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss26.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss27.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss28.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss29.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss30.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss31.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss32.png) (https://bitbucket.org/Garmichael/infinite-hyrule/raw/f006f6e6feffe24a9abe4291671be1262b1b9cd5/Screenshots/ss33.png)

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


Title: Re: Legend of Zelda Overworld Generator
Post by: Trax 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?
Title: Re: Legend of Zelda Overworld Generator
Post by: Garmy 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:


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.
Title: Re: Legend of Zelda Overworld Generator
Post by: LadyCannock 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?

Title: Re: Legend of Zelda Overworld Generator
Post by: Garmy 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.
Title: Re: Legend of Zelda Overworld Generator
Post by: Vanya on September 10, 2020, 10:14:28 am
Nice! Seems like it could be a lot of fun even just on it's own.
Title: Re: Legend of Zelda Overworld Generator
Post by: erinnk on September 10, 2020, 01:43:34 pm
This is really cool, good luck with it!
Title: Re: Legend of Zelda Overworld Generator
Post by: Garmy 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:

(https://www.develteam.com/userdata/garmichael/ProgressChart_9-17.png)

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:

(https://www.develteam.com/userdata/garmichael/Overworld_9-17.png)

(https://www.develteam.com/userdata/garmichael/Overworld2_9-17.png)

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:

(https://www.develteam.com/userdata/garmichael/screen_9-17_01.png) (https://www.develteam.com/userdata/garmichael/screen_9-17_10.png) (https://www.develteam.com/userdata/garmichael/screen_9-17_15.png)

A Dock screen:

(https://www.develteam.com/userdata/garmichael/screen_9-17_02.png)

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

(https://www.develteam.com/userdata/garmichael/screen_9-17_12.png)

More varied Graveyards:

(https://www.develteam.com/userdata/garmichael/screen_9-17_09.png) (https://www.develteam.com/userdata/garmichael/screen_9-17_11.png) (https://www.develteam.com/userdata/garmichael/screen_9-17_13.png)

Any Road:

(https://www.develteam.com/userdata/garmichael/screen_9-17_04.png)

Fairy Ponds:

(https://www.develteam.com/userdata/garmichael/screen_9-17_08.png)

Dungeons:

(https://www.develteam.com/userdata/garmichael/screen_9-17_07.png) (https://www.develteam.com/userdata/garmichael/screen_9-17_17.png) (https://www.develteam.com/userdata/garmichael/screen_9-17_16.png)

And then just some random screens I liked:

(https://www.develteam.com/userdata/garmichael/screen_9-17_05.png) (https://www.develteam.com/userdata/garmichael/screen_9-17_06.png) (https://www.develteam.com/userdata/garmichael/screen_9-17_19.png)

Title: Re: Legend of Zelda Overworld Randomizer
Post by: pocket 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.
Title: Re: Legend of Zelda Overworld Randomizer
Post by: ActionGamer on September 18, 2020, 03:57:47 pm
Finally!!!!!!!! Someone is cool and smart enough to make a tool like this.
Title: Re: Legend of Zelda Overworld Randomizer
Post by: ultimaweapon on September 19, 2020, 02:03:29 pm
This is really starting to look awesome. I'm looking forward to trying this out.
Title: Re: Legend of Zelda Overworld Randomizer
Post by: lexluthermiester 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!
Title: Re: Legend of Zelda Overworld Randomizer
Post by: DannyPlaysSomeGames on September 22, 2020, 01:51:42 pm
This actually looks pretty rad, can't wait to see what else you do with this.
Title: Re: Legend of Zelda Overworld Randomizer
Post by: Tomato 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:
Title: Re: Legend of Zelda Overworld Generator
Post by: ActionGamer 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:

(http://garmichael.develteam.com/content/depot/ProgressChart_9-17.png)

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:

(http://garmichael.develteam.com/content/depot/Overworld_9-17.png)

(http://garmichael.develteam.com/content/depot/Overworld2_9-17.png)

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:

(http://garmichael.develteam.com/content/depot/screen_9-17_01.png) (http://garmichael.develteam.com/content/depot/screen_9-17_10.png) (http://garmichael.develteam.com/content/depot/screen_9-17_15.png)

A Dock screen:

(http://garmichael.develteam.com/content/depot/screen_9-17_02.png)

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

(http://garmichael.develteam.com/content/depot/screen_9-17_12.png)

More varied Graveyards:

(http://garmichael.develteam.com/content/depot/screen_9-17_09.png) (http://garmichael.develteam.com/content/depot/screen_9-17_11.png) (http://garmichael.develteam.com/content/depot/screen_9-17_13.png)

Any Road:

(http://garmichael.develteam.com/content/depot/screen_9-17_04.png)

Fairy Ponds:

(http://garmichael.develteam.com/content/depot/screen_9-17_08.png)

Dungeons:

(http://garmichael.develteam.com/content/depot/screen_9-17_07.png) (http://garmichael.develteam.com/content/depot/screen_9-17_17.png) (http://garmichael.develteam.com/content/depot/screen_9-17_16.png)

And then just some random screens I liked:

(http://garmichael.develteam.com/content/depot/screen_9-17_05.png) (http://garmichael.develteam.com/content/depot/screen_9-17_06.png) (http://garmichael.develteam.com/content/depot/screen_9-17_19.png)

Do you have any idea when the next build will be ready to download?
Title: Re: Legend of Zelda Overworld Randomizer
Post by: Garmy 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 (https://www.develteam.com/userdata/garmichael/ZeldaOverworldRandomizer_10_4_2020.exe)

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.

(https://www.develteam.com/userdata/garmichael/ZeldaOverworldRandomizer_10_4_2020_01.png)
(https://www.develteam.com/userdata/garmichael/ZeldaOverworldRandomizer_10_4_2020_02.png)
(https://www.develteam.com/userdata/garmichael/ZeldaOverworldRandomizer_10_4_2020_03.png)

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

(https://www.develteam.com/userdata/garmichael/ZeldaOverworldRandomizer_DF_10_4_2020_02.png)
(https://www.develteam.com/userdata/garmichael/ZeldaOverworldRandomizer_DF_10_4_2020_03.png)
(https://www.develteam.com/userdata/garmichael/ZeldaOverworldRandomizer_DF_10_4_2020_04.png)



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:

(https://www.develteam.com/userdata/garmichael/screen_10-04_01.png)
(https://www.develteam.com/userdata/garmichael/screen_10-04_02.png)
(https://www.develteam.com/userdata/garmichael/screen_10-04_03.png)





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:

(https://www.develteam.com/userdata/garmichael/ProgressChart_10-04.png)


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:
(https://www.develteam.com/userdata/garmichael/trimComparision_noTrim.png)

Yes Trim:
(https://www.develteam.com/userdata/garmichael/trimComparision_yesTrim.png)

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:

(https://www.develteam.com/userdata/garmichael/columnViewer.png)

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.

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


Title: Re: Legend of Zelda Overworld Randomizer
Post by: Vanya 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.
Title: Re: Legend of Zelda Overworld Randomizer
Post by: Queue 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.
Title: Re: Legend of Zelda Overworld Randomizer
Post by: Garmy 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.


Title: Re: Legend of Zelda Overworld Randomizer
Post by: Cyneprepou4uk on October 06, 2020, 01:53:45 pm
No need to restrain yourself. Contact me here (https://t.me/cyneprepou4uk) or here (https://vk.com/cyneprepou4uk), we'll discuss how make more than 256 columns.
Title: Re: Legend of Zelda Overworld Randomizer
Post by: ifightdragons on October 06, 2020, 04:25:55 pm
No need to restrain yourself. Contact me here (https://t.me/cyneprepou4uk) or here (https://vk.com/cyneprepou4uk), we'll discuss how make more than 256 columns.

As a big Zelda fan, I'm grateful you've been participating in the Zelda threads lately. The more skillful people working on these projects, the better.
Title: Re: Legend of Zelda Overworld Randomizer
Post by: gzip on October 06, 2020, 06:21:16 pm
This is looking pretty cool! Here are a few suggestions after trying it out:


May I suggest that you look at this tool as a starting point for any given Zelda hack which would then be further modified with other tools and/or by hand. Maybe give the user more options to resolve column problems themselves (like 3 and 4 above). It would be a first if the user could even edit the column combos themselves.

I guess my biggest question is it really necessary to create all new combos or can you achieve something similar by using the existing columns (maybe changing a few critical columns if necessary)?

October 06, 2020, 06:26:58 pm - (Auto Merged - Double Posts are not allowed before 7 days.)
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.

These all sound reasonable. Part of the joy of hacking is working within the established limitations!
Title: Re: Legend of Zelda Overworld Randomizer
Post by: Garmy on October 09, 2020, 02:06:16 pm
Progress Update

I only have one new screenshot to show, but it's a very cool one.

(https://www.develteam.com/userdata/garmichael/screen_10-9.png)


So what's happening here?

I made a Junkyard Biome. All it does is fill the screen with random tiles from a collection of 32 tiles, and then carves out a vertical and horizontal path through the middle.

In my last post, I was commenting about how I ran into an issue with only having 256 unique columns. This screenshot shows a lot more! Each column is a series of 10 tiles, each randomly selected from a pool of 32 tiles. This means that each column has 1,125,899,906,842,624 possible configurations. Likely, every single column shown in this screenshot is unique, and the game still works.

How tho!


Not all heroes wear green tunics

After my last post, Cyneprepou4uk (https://www.romhacking.net/forum/index.php?action=profile;u=75353) commented that there was no need to restrict myself and so I reached out to him. After some discussion back and forth, he came up with a great idea to make each column on each screen unique, and then wrote the ASM to make it work. It's a really solid implementation that makes writing to the rom much easier in my application and makes it a lot less bug-prone.

The technical stuff (or: Skip this if you don't care)
He expanded the rom, adding 8 banks. Then with some ASM magic got rid of the column groups, column definitions, pointers, and basically re-architected the entire method the game figures out what tiles to place on the screen.

With 8 extra banks, four go unused, but in the other four, each bank is set up to define 32 screen layouts. Instead of having a layout reference 16 columns in another table by their group and id, each layout directly contains the 176 tiles for that layout.

(https://www.develteam.com/userdata/garmichael/screen_10-9_02.png)

The way that this is set up, I dont have to worry about setting Start Column bits, or Double Tile bits, or collecting columns into groups, redefining pointers to those groups, or encoding all the column data in the rom's funky format. But most importantly, I dont have to worry about space limitations!

So HUGE thanks to Cyneprepou4uk for making this possible!

Moving Forward

With constraints out of the way, I am free to get more creative with Biome generation. Previously, I had no plans to make a Desert Biome because of the extra columns it would make, but now I can include them. I also have an idea to make a Wetlands Biome that will have a lot of 3x3 to 4x4 tile-sized lakes throughout it with rivers connecting them and bridges crossing over them.

Here's a little mockup of the Wetlands Biome:

(https://www.develteam.com/userdata/garmichael/screen_10-9_03.png)

I also want to design a bunch more Decor screens for each Biome and a handful of new Dungeon Entrance screen layouts.


I'm also open to ideas for Biomes or even layouts of Dungeon Entrance screens. A pretty easy way to make mockups would be to use Pyxel Edit (https://pyxeledit.com/) and use the template I created (https://www.develteam.com/userdata/garmichael/zeldatiles.pyxel).
Title: Re: Legend of Zelda Overworld Randomizer
Post by: ActionGamer on October 09, 2020, 02:13:10 pm
Coolio cant wait to see it all done
Title: Re: Legend of Zelda Overworld Randomizer
Post by: Cyneprepou4uk on October 09, 2020, 04:44:47 pm
@Garmy  :woot!:



Part of the joy of hacking is working within the established limitations!

 :laugh:
Title: Re: Legend of Zelda Overworld Randomizer
Post by: ultimaweapon on October 09, 2020, 08:29:47 pm
It's good to hear that everything is shaping up nicely.
Title: Re: Legend of Zelda Overworld Randomizer
Post by: DannyPlaysSomeGames on October 10, 2020, 12:59:35 am
Wow, that's pretty impressive! It's pretty clear that a lot of hard work is going into this project, and I'm glad with how it's turning out so far.

So considering that your overhaul leaves you with 4 extra banks of space, would you consider doing a dungeon randomizer as well? I'm really curious at how you'd approach something like that.

I'm also curious about making the screen overhaul its own standalone thing; I think it'd be a pretty great addition in allowing ROM hackers to be more creative with their overworld design (though compatibility with the standard tools might be an issue, I still think it'd be brilliant).
Title: Re: Legend of Zelda Overworld Randomizer
Post by: Vanya on October 10, 2020, 03:39:08 am
I love everything I've seen here so far.
All the ideas going into this tool are interesting.
However, if you really want to impress me, turn the vertically oriented bridge tiles 90 degree so it doesn't  look like Hyrule has some strange building code concerning bridge construction. :P ;D :3
Title: Re: Legend of Zelda Overworld Randomizer
Post by: Garmy on November 10, 2020, 11:19:47 pm
It's been a while since I've posted an update, but boy have I been busy!

First thing first, let's see some maps:
(https://www.develteam.com/userdata/garmichael/map_11-10_01.png)
(https://www.develteam.com/userdata/garmichael/map_11-10_02.png)
(https://www.develteam.com/userdata/garmichael/map_11-10_03.png)
You probably noticed some new Biomes!


The River Biome

(https://www.develteam.com/userdata/garmichael/screenshot_11-10_01.png)

This Biome starts at the top of the map and winds its way down, generating bridges along the way. Zora swim in these waters, so beware!

The Desert Biome

(https://www.develteam.com/userdata/garmichael/screenshot_11-10_02.png)

The desert heats bakes your back as you navigate boulders and rocky outcrops, dodging Leevers and Peahats.

But if you're lucky, you might find some relief at an Oasis

(https://www.develteam.com/userdata/garmichael/screenshot_11-10_03.png)

Deserts also hide secrets

(https://www.develteam.com/userdata/garmichael/screenshot_11-10_04.png)

Changes to the Mountain Range and Start Zone

After some careful thought, I realized that mountains just dont work that well anywhere except the top rows. The ladders are supposed to make you feel like youre climbing up, but when it's positioned anywhere else on the map, that illusion is broken. So that's where they're placed now. They also take up less screens horizontally than the original map to make room for more biome diversity. Finally, the algorithm for creating these screens has been vastly improved.

Since the Mountains now appear at the top of the map, the Start Zone area now appears only on the edges of the map and below the bottom half. As an aside, the Start Zone region has been reduced to 3x2, down from 4x2.

Changes to the Tunnel Regions

The Tunnel Regions used to just copy the Mountain Range region algorith, but have now been given a new one. They appear a little more craggy and will be filled with Tektites.

(https://www.develteam.com/userdata/garmichael/screenshot_11-10_05.png)

Just for Fun: Palettes!

You can now select a palette. Here are the options:

(https://www.develteam.com/userdata/garmichael/zelda_pallets.png)

(My favorite is the Vintage one)

Other Changes


Remaining Tasks


Ready for Beta Testing

If you're interested in helping out, I'm looking for issues in the map generation.


[Download the current build (https://www.develteam.com/userdata/garmichael/ZeldaOverworldRandomizer_Nov_10_2020.exe)]
Title: Re: Legend of Zelda Overworld Randomizer [Beta Testers Requested]
Post by: ActionGamer on November 11, 2020, 02:51:19 pm
It works great so far, however when I try to patch a randomized map rom with the Zelda 1 Redux hack, the game just crashes when you get passed the name select screen. Which is weird because if I do it the other way around, the game works but none of the redux features show up. Also sometimes with a randomized map when I move up a screen there is a wall tile blocking the way forcing me to go back down. It's not a huge problem, just something that can be addressed. Another thing you can do is figure out how we can be able to edit the randomized map because ZeldaTech doesn't work right with it.

Title: Re: Legend of Zelda Overworld Randomizer [Beta Testers Requested]
Post by: Garmy on November 11, 2020, 07:49:21 pm
It works great so far, however when I try to patch a randomized map rom with the Zelda 1 Redux hack, the game just crashes when you get passed the name select screen. Which is weird because if I do it the other way around, the game works but none of the redux features show up. Also sometimes with a randomized map when I move up a screen there is a wall tile blocking the way forcing me to go back down. It's not a huge problem, just something that can be addressed. Another thing you can do is figure out how we can be able to edit the randomized map because ZeldaTech doesn't work right with it.

Unfortunately, I don't think I'll be able to get this to work with Zelda Redux. This Randomizer expands the rom and writes to the extra banks, which ZR also does. There's overlapping code between the two patches that would make it really difficult to make them work together.

When you find bugs like edges not lining up, please send me the seed number so I can investigate.


As far as existing map editors go, none of them will work with the roms output by this randomizer. The whole format of how screens are built in the code is different. This is something that I'm fine with because when Version 1.0 releases, it won't show a preview of the map anymore. Having a level editor that can read the rom would make it easy for cheating.




Also, side note.. I did some testing and it looks like Fred Coughlin's randomizer works with this, as long as you run your rom through his randomizer first.

I'm pretty excited about this!
Title: Re: Legend of Zelda Overworld Randomizer [Beta Testers Requested]
Post by: lexluthermiester on November 12, 2020, 12:23:18 am
This looks cool! Is there a seeding function that can be used to replicate maps that have already been generated?
Title: Re: Legend of Zelda Overworld Randomizer [Beta Testers Requested]
Post by: Garmy on November 12, 2020, 02:21:27 am
Yea it uses seeds that generate the same map every time.

The seeds will be affected with updates though
Title: Re: Legend of Zelda Overworld Randomizer [Beta Testers Requested]
Post by: Trax on November 13, 2020, 01:15:27 am
Impressive work, so far, Garmy. Maps look quite organic and there's very few glitches. Even if you get a few weird layouts, someone could use that as a starting point and tweak with their own touch afterwards. Here's an idea: being able to set a weight value for each biome, higher weight means higher probability for screens of that kind.

I tried to run the app with Wine on Mac, but the display is very glitchy. The map does generate, though. Color palettes don't work. Maybe with the latest update of Wine, I could get better results, but I'm usually quite hesitant to do that because I always fear it will break something else. What kind of framework do you use?

Some time ago, I tried to implement a more "free" system for Zelda 1 maps, where you can lay down each tile individually instead of having to work with columns. I thought about a simple compression system (RLE), and have the option to choose between horizontal draw or vertical draw, whichever run gives you the least number of bytes. The caveat is, obviously, that it still takes a lot of space, despite compression. It was put on ice, most likely because I was not skilled enough. Maybe I could give it another try, if I have time. Do you think that could make map generation more interesting?
Title: Re: Legend of Zelda Overworld Randomizer [Beta Testers Requested]
Post by: Garmy on November 13, 2020, 02:42:17 am
Thanks Trax! Your work gave me the initial motivation and starting information to work on this.


I have some weighting involved throughout the project, but it's not generated with an equation of any sort (like noise or whatever) . A lot of the generation is done by hand with RNG determining the variation. For example, the mountains always have a height of 3 screens and a width between 6 and 9 (iirc), then its placed on the top row somewhere. Rivers always start in the top row and randomly make their way down. After placing the mountain, the river, the desert, and the graveyard, I push in as many 3x3 forests as can fit, and then assign any remaining screens to adjacent biomes. It's probably a little too manual but I gave me a lot of control. Also it's hard to use an equation when the canvas size is effectively only 16x8.

I do want some new biomes eventually.. Things like swamps or maybe villages (if this expands enough to warrant new tiles). At that point I'd probably throw in more weighting to determine which biomes end up getting used in a seed.

Thanks for testing in Wine. If I understand right, you mean that palettes don't affect the preview map in the editor,correct? If so, that's expected. I don't read the graphic data from the rom. I just made a tile atlas as a bmp and use that when drawing the map. At some point, I'll update it so that the preview map shows the correct palette.

I'm curious what glitches you're seeing though. Would you be able to take a screenshot of it for me?

I use the WPF Framework for the UI and a styling plug in called Adonis. It's written in C#. I wasn't sure C# was the right choice but it's a lot easier than asm!

Cyneprepou4uk did some asm work on it and achieved what you were looking to do. He expanded the rom and banks 0x07, 0x08, 0x09, and 0x10 are used for layouts, with each tile being represented individually. If you open an output rom in an hex editor, you'll see the data beautifully formatted. It really did open the possibilities a lot.

Making map generation more interesting with the given tiles is a bit of an challenge though, even with no column limitations. I definitely do want more variety from screen to screen though.

A couple friends and I have made up a bunch of island and dungeon entrance layouts that I want to add to the pool of options, as well as some decor screens (basically unique looking screens that can be used as landmarks). I haven't implemented many of them yet.


After I squash some of these bugs, I'll make it open source. I think having more creative input on making biomes and stuff would be pretty awesome.
Title: Re: Legend of Zelda Overworld Randomizer
Post by: Rogles on November 21, 2020, 08:44:07 pm
Progress Update


Here's a little mockup of the Wetlands Biome:

(https://www.develteam.com/userdata/garmichael/screen_10-9_03.png)

I also want to design a bunch more Decor screens for each Biome and a handful of new Dungeon Entrance screen layouts.



That Wetlands Biome looks great! I can't think of many other biome ideas except for maybe having a small area in the mountains with lots of waterfalls and single tile width streams or an area in the mountains that has more ladders and small pockets of traversable terrain (kinda maze-like).

Would it be possible to have a snow biome (white rocks and trees) or would that be too difficult? It would basically look like the graveyard but with the normal ground color instead of grey.

November 22, 2020, 07:36:56 pm - (Auto Merged - Double Posts are not allowed before 7 days.)
Here are a few mockups of biome and dungeon entrance ideas. They were made in ZQuest so some of them might not be 100% doable due to the extra tiles and flexibility it has. They should be close though.

Mountain Streams
(https://vurez.com/zelda/screens/zelda_mountain_streams1.gif)
(https://vurez.com/zelda/screens/zelda_mountain_streams2.gif)
(https://vurez.com/zelda/screens/zelda_mountain_streams3.gif)
(https://vurez.com/zelda/screens/zelda_mountain_streams4.gif)
(https://vurez.com/zelda/screens/zelda_mountain_streams5.gif)

Great Waterfall
(https://vurez.com/zelda/screens/zelda_great_waterfall.gif)

Green Cave
(https://vurez.com/zelda/screens/zelda_green_cave.gif)

Grave Mountain Top
(https://vurez.com/zelda/screens/zelda_mountaintop.gif)

Maze
(https://vurez.com/zelda/screens/zelda_maze.gif)

Snow - I'm assuming this wouldn't be doable unless it replaced the grave area.
(https://vurez.com/zelda/screens/zelda_snow1.gif)
(https://vurez.com/zelda/screens/zelda_snow2.gif)



Title: Re: Legend of Zelda Overworld Randomizer [Beta Testers Requested]
Post by: Vanya on November 23, 2020, 02:00:23 pm
What about changing the snow palette so the ground is white, maybe have light grey rocks, and lighter blue waters to look a bit more icy. Any way to use the dead tree trunk entrance tiles to make little grey trees?
Title: Re: Legend of Zelda Overworld Randomizer [Beta Testers Requested]
Post by: Garmy on November 24, 2020, 10:24:49 am
Some of those mockups look pretty awesome. I especially like the grave mountain top. I also like the mountain streams but they're hard to make a biome out of through procedural generation. I bookmarked the post tho so I can return to it.

Unfortunately i can't do the snowy ones. They're mixing palettes. The four colors come as a set and can't be changed around without changing them for every screen and modifying the graveyard palette.

Title: Re: Infinite Hyrule - Legend of Zelda Overworld Randomizer [Released!]
Post by: julcreutz on February 13, 2021, 11:16:34 am
Any updates on this?
Title: Re: Infinite Hyrule - Legend of Zelda Overworld Randomizer [Released!]
Post by: DragonAtma on February 13, 2021, 05:22:28 pm
Actually, having both snow and graveyard should be doable with a bit of coding. My first idea was splitting them (like Terraria's Jungle and Dungeon), but you should be able to place them almost anywhere (as long as they're not directly adjacent; corner-adjacent should be fine). Just silently change the palette before moving into a snow or graveyard screen.

You could even do something similar for other palette changes (say, water/lava) as long as the two don't share a border.
Title: Re: Infinite Hyrule - Legend of Zelda Overworld Randomizer [Released!]
Post by: PolishedTurd on February 14, 2021, 08:04:03 pm
Congratulations, this looks great! At this point, it seems like adding randomization for dungeons would really round out the features. Even though that feature exists in another program, having a one-stop shop for randomization is attractive.

Just a thought.
Title: Re: Infinite Hyrule - Legend of Zelda Overworld Randomizer [Released!]
Post by: crabycowman123 on April 11, 2021, 12:37:54 pm
Has anyone been able to get this randomizer working on Linux? I've tried running ZeldaOverworldRandomizer_Nov_10_2020.exe with Wine and Mono, but both give the same error message: "The entry point method could not be loaded due to Could not load file or assembly or one of its dependencies. assembly:PresentationFramework, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35 type:<unknown type> member:<none>"

I think I'm missing a library or something, but I can't seem to find information about how to install/load it.
Title: Re: Infinite Hyrule - Legend of Zelda Overworld Randomizer [Released!]
Post by: julcreutz on April 20, 2021, 05:08:23 am
Has anyone been able to get this randomizer working on Linux? I've tried running ZeldaOverworldRandomizer_Nov_10_2020.exe with Wine and Mono, but both give the same error message: "The entry point method could not be loaded due to Could not load file or assembly or one of its dependencies. assembly:PresentationFramework, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35 type:<unknown type> member:<none>"

I think I'm missing a library or something, but I can't seem to find information about how to install/load it.

The Randomizer is written in C#, so you need the .NET Runtime.
Title: Re: Infinite Hyrule - Legend of Zelda Overworld Randomizer [Released!]
Post by: lexluthermiester on April 23, 2021, 12:40:07 pm
Has anyone been able to get this randomizer working on Linux? I've tried running ZeldaOverworldRandomizer_Nov_10_2020.exe with Wine and Mono, but both give the same error message: "The entry point method could not be loaded due to Could not load file or assembly or one of its dependencies. assembly:PresentationFramework, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35 type:<unknown type> member:<none>"

I think I'm missing a library or something, but I can't seem to find information about how to install/load it.
No. You're just going to have to use Windows for now.