A possible algorithm for Zeldalike overworlds

The 2012 7DRL challenge is one month away!


I've been thinking about how to procedurally create a Zeldalike map for a roguelike. By Zeldalike I mean the important parts that I remember from playing the original Zelda game: it was broken into screen-sized chunks, everywhere was reachable (although sometimes you had to get an item first), there were different themed areas, it wasn't too dense or too sparse - it was interesting, charming, and fun.


Here's an algorithm that should come up with something interesting like Zelda's overworld Hyrule. It creates one array of tiles and one array with details about each screen-sized chunk of the world.

Since the world will be broken into screen sized chunks, we can start by determining how those screens will be connected. Let's start with a 16x5 array of screens that have no connections to any neighbors. This is a high-level view of the world. If you were to print it out, it may look something like this where each screen is represented as a blank space and the walls between them are solid spaces.	################################# # # # # # # # # # # # # # # # # # ################################# # # # # # # # # # # # # # # # # # ################################# # # # # # # # # # # # # # # # # # ################################# # # # # # # # # # # # # # # # # # ################################# # # # # # # # # # # # # # # # # # #################################
With the array of screens, create a simple perfect maze. When printing out how the screens are connected to make a big maze, it would look something like this. We can see that this time, the top left screen has an open path to the screen to the east. After traveling east a few screens, you can go south.	################################# # # # ####### ### ##### ############### # # # # # # # ### # # ######### # ### ### # # # # # # # # # # # ### # # ####### ### # ##### # # # # # # # # # # # # # # ##### # # ############# # # # # # # # # # # # #################################
Remove some of the walls to connect screens. There are now loops and many ways to move around. Now when traveling east from the top left screen you can go south on the second screen or continue to the fourth screen and go south.	################################# # # # ### ### ### ##### # # ########### # # # # # ### # # ######### # ### ### # # # # # # # # # # ### # # ####### ### # ##### # # # # # # # # # # # # # # ##### # # ############# # # # # # # # # # # # #################################
Assign themes to some of the screens. I'm just using 1 through 5 as arbitrary themes. They could be like the original zelda: brown rock, green rock, brown forest, green forest, cemetary, etc or they could be your own themes.	################################# # 1 # 2 3 # ### ### ### ##### # # ########### # 4# 4 # # # ### # # ######### # ### ### # # # # # 1# # # # # ### # # ####### ### # ##### # # # # #5# 3 5# # 2# # # # # # ##### # # ############# # # # # # # # # # # # #################################
Spread the themes to adjacent screens that are connected.	################################# #1 1 1 4#2 2 3 3 # ### ### ### ##### # # ########### # 1 4 4# 2 4 4 # # # ### # # ######### # ### ### # # # # 5 #3 1# # # # # ### # # ####### ### # ##### # # # # #5# 3 3 5# # 2 2# # # # # # ##### # # ############# # # # # # # # # # # # #################################
Continue spreading them until all screens have a theme. This ensures that the themes match the path that the player has to walk through and the user should feel like they spend some time in each theme before entering a different one.	################################# #1 1 1 4#2 2 3 3 3 3 3 3 3 3 3 3# ### ### ### ##### # # ########### #1 1 4 4#2 2 4 4 4 4 4 2 2 2 2 2# # # ### # # ######### # ### ### # #1#1#5 5 5 2 2 2#3 1#4#2 2 2 2#2# # ### # # ####### ### # ##### # # #1#5 5#5#5 3 3 3 3 5#4#2 2 2#2#2# # # # ##### # # ############# # # #1#5#5 5#3 3#3#3 3 3 3 3 3 3#2#2# #################################

#####################&&&&&&&********* # ## ## #& &* ** # 1 ## 1 ## 1 #& 4 &* 2 ** # ## ## #& &* ** #####################&&&&&&&********* ##############&&&&&&&&&&&&&&********* # ## #& && &* ** # 1 ## 1 #& 4 && 4 &* 2 ** # ## #& && &* ** ##############&&&&&&&&&&&&&&********* ##############%%%%%%%%%%%%%%%%%%%%%%% # ## #% %% %% %% # 1 ## 1 #% 5 %% 5 %% 5 %% # ## #% %% %% %% ##############%%%%%%%%%%%%%%%%%%%%%%% #######%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% # #% %% %% %% %%	Now we can build the real world map based on the array of screens created in the earlier part. For each cell in the array of screens, plop down a screen sized chunk in the world array. For this example I'll make each screen 7x5 tiles large and just show the top left few screens but a real game would have much larger screens. I will also put the theme number and use different border tiles for each theme.
#####################&&&&&&&********* # ## ## #& &* ** # 1 1 1 4 &* 2 # ## ## #& &* ** ########## ##########&&& &&&********* ########## ###&&&&&&&&&& &&&********* # ## #& && &* ** # 1 1 4 4 &* 2 # ## #& && &* ** ### ###### ###&&&&&&&&&& &&&*** ***** ### ###### ###%%%%%%%%%% %%%%%% %%%%% # ## #% %% %% %% # 1 ## 1 #% 5 5 5 # ## #% %% %% %% ### ##########%%% %%%%%% %%%%%% %%%%% ### ###%%%%%%%%%% %%%%%% %%%%%% %%%%% # #% %% %% %% %%	Then remove the walls for screens that should be connected. It would be easiest to always remove the one or two center blocks from a wall that separates connected screens but you could also make a wider path, a path at a different spot, or multiple paths between two screens. That would add variety but the screens are too small to do that here. After this, we have a themed maze to walk around in based on the array of screens.
#####################&&&&&&&********* # ## ### ##& & & &* $ $ ** # $ # # &* # ## ### ##& & & &* $ $ ** ########## ##########&&& &&&********* ########## ###&&&&&&&&&& &&&********* ######## #& &&# #&* ** ### &&& ? &* ### #### #& &&# #&* ** ### ###### ###&&&&&&&&&& &&&*** ***** ### ###### ###%%%%%%%%%% %%%%%% %%%%% ## #### ##%% %%% %% %% # # ### ##% *** ! ## ####!$!##%% %%% %% %% ### ##########%%% %%%%%% %%%%%% %%%%% ### ###%%%%%%%%%% %%%%%% %%%%%% %%%%% #% %#%%%%%%%% %% %% %%	Randomly select different things to fill the screens with based on its theme: a center lake, small blocks of rock, rows of tree's, bordering trees, statues, etc. You could also have special things that only appear at dead ends: temples, towns, caves, treasure, bosses, puzzles, etc. Putting things at the dead ends makes it worth the time spent getting there - a good idea since most players hate dead ends and mazes in general. Secret areas and bad guys could also be placed now.
#####################&&&&&&&********* # ## ### ##& & & &* $ $ ** # $ # # &* # ## ### ##& & ~~~~~~ $ ** ########## ##########&&& ~~~~~~****** ########## ###&&&&&&&&&& ~~~~~~****** ######## #& &&# ~~~~~~ ** ~~# &&& ? &* ~~# #### #& &&# #&* ** ~~# ###### ###&&&&&&&&&& &&&*** ***** ~~# ###### ###%%%%%%%%%% %%%%%% %%%%% ~~ #### ##%% %%% %% %% ~~ # ### ##% *** ! ~~ ####!$!##%% %%% %% %% ~~# ##########%%% %%%%%% %%%%%% %%%%% ~~# ###%%%%%%%%%% %%%%%% %%%%%% %%%%% ~~ %#%%%%%%%% %% %% %%	Hyrule had shore lines along some the edges and small lakes at the corner of four screens. You can add those too.
#####################&&&&&&&********* # ## ### ##& & & &* $ $ ** # $ # # &* # ## ### ##& & ~~~~~~ $ ** ########## ##########&&& ~~~~~~****** ########## ###&&&&&&&&&& ~~~~~~****** ######## #& &&# ~~~~~~ ** ~~# &&& ? ~&* ~~# #### #& &&# ~&* ** ~~# ###### ###&&&&&&&&&& &~&*** ***** ~~# ###### ###%%%%%%%%%% %~%%%% %%%%% ~~~=~~~~~~=~~~~~~~~~~~~~=~~%% %% ~~ ### ##% * * ! ~~ ####!$!##%% %%% %% %% ~~# ##########%%% %%%%%% %%%%%% %%%%% ~~# ###%%%%%%%%%% %%%%%% %%%%%% %%%%% ~~ %#%%%%%%%% %% %% %%	Rivers could connect some of the lakes to the edges. It would be necessary to place bridges if the river is cutting off a path that used to be passable. A final step could involve looking at each screen or tile in the world and placing more treasure, creatures, or structures at interesting points.

I haven't implemented this yet so I'm not sure if this will really work or not. I'm also not sure how difficult this will be or how fun the results will be. It's something I haven't seen in any roguelike or non-Zelda game and if each screen has something interesting then it should avoid having long spans of time where all you do is walk around. I will probably use this for my entry into the 2012 7DRL challenge.