Sign in to follow this  

Zelda-like procedural map generation

This topic is 3313 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I'm thinking about doing a procedurally generated Zelda-like adventure game. The game should be divided in screens of about 16x14 tiles, without scrolling, similar to the original Legend of Zelda. Googling around only found stuff for procedural generation of RTS maps, which I don't think that it can scale down and be appropriate for the simple screens I need (although they might be good for generating the global structure of the world map: rivers and mountains). I'd appreciate any suggestions of ways to generate such screens as I'm quite unsure about the way to go for the moment. For reference, I need nothing more than this (ignoring enemies). Thanks!

Share this post


Link to post
Share on other sites
hmmm. well I think what I would do is to first create a random 2d perlin noise heightmap, then i'd average the samples from each 16x16 tile at a time to decide which tile goes there. I'd do multiple layers of noise for different things; a base layer of grass(walkable) and rock(non-walkable), then a layer with different frequencies for obstacles... you could do an overlying layer to determine which areas are prairie, which are desert, mountain, etc... And i'd run a pathfinding algorithm on it at the end to determine if its possible to walk to all the interact-able things.

Share this post


Link to post
Share on other sites
Funkymunky,

I had something similar in mind, and I'm sure it can generate cool results, but maybe it is more useful for "decoration"? (you talked about a theme layer: mountain, prairie, desert, etc.)

Unless I've misunderstood what you said, I'd end up generating a random series of obstacles and then testing if it is traversable, and if it isn't throw it away and restart. I don't know if it is possible, but if there was a way to force the result to be traversable at first that'd be cooler. Unless there's a way to combine both approaches and have the pathfinding "dig" a way to its destination if there isn't one?

But hey thanks I appreciate your suggestions, I've just started playing around with perlin noise and there's cool stuff to do with it, although it looks more like Final Fantasy maps for the moment =).

Share this post


Link to post
Share on other sites
I'd probably go with a set of hardcoded basic configurations which define where the exits are and which links to which (in the linked picture it'd be a T junction). Then you'd generate a whole map of these screens which link together properly. Once you've got that you can start adding more randomness and variety into each screen individually - making the exits bigger or smaller, adding in extra obstacles and enemies to make each screen unique.

Share this post


Link to post
Share on other sites
Thanks for the feedback, I think your ideas are enough to get me "kickstarted" in the good direction. I'll use something like OrangyTang's suggestion, along with perlin noise for the details, as FunkyMunky suggested, and see how it looks like, I'll come back if I run into any problems.

Of course, new suggestions are still welcome, but thanks for what you already provided!

Share this post


Link to post
Share on other sites
You could draw everything in layers like Funkymunky said and the last layer could be to draw the walkable paths. The paths connect to all exits and are randomly connected. So instead of drawing a random scene and then checking if you can walk through it you draw the paths over the top and force them to connect. No need to throw away a scene that didn't work.

Share this post


Link to post
Share on other sites
The original zelda used a simple maze structure for it's levels, but the maze granularity was not tile-sized, it was room-sized. Each room was a cell in the maze, and each room was again it's own mini-challenge.

I would start with a maze generator that used a distinction between nodes and edges - that is, NOT one of the maze generators that fills cells either walkable or not, but one that marks cells as connected or not.

To account for things like locks and keys, generate multiple mazes and then make them overlap. The first maze is from the dungeon entrance to a key. The second maze is from the key to an interesting point (like the compass, or map, or the big treasure, etc) and it should overlap the first maze somewhat but not completely. Wherever it doesn't overlap the first maze is where you put the key door.

After you have several mazes generated and partially overlapping, you can find empty spots on the map and add secret rooms, or you can find two rooms that aren't connected and are far apart (judged by the shortest path from one to the other) and make a secret door between them.

Pick a very few doors randomly to make into one-way doors. Use path finding to make sure you don't completely block off a room (make sure there is some path to the room on each side of the one-way door). You might want to add exits to secret rooms that are one-way, so that bombing into them gives you a reward and then lets you exit to someplace later in the dungeon but doesn't give you a two-way shortcut.

Pick some doors to make into the doors that only open when the room is cleared, and use path-finding to find which of the rooms connected to the door is easier to get to and mark that room as one that should be a challenging fight (no reason to put that kind of door there, otherwise).

As far as making each room interesting on it's own, there three basic properties of rooms: amount of movement restriction, level of monsters, and number of monsters. Some rooms have long lines of blocks, or patterns that make it hard to move much, some have only a block or two that makes moving very easy. Some have tough monsters, some have weak monsters. Some have lots, some have few. Then there are dungeon themes like the one where there are dark rooms, and sometimes the obstacles are different (solid blocks, water, fire, etc).

There are also special occasions where the obstacles completely divide a room in half, so that even though there are several doors, you can't get from some doors to certain other ones, so that could be a special situation where very rarely, a room is split into two nodes in the graph. You might want to do that before the maze generation so it will take the split into account, or you could do it afterward by combining some parts of the maze so that two rooms with opposite doors (such as up and left vs right and down) are combined into one room with a divider, or you might randomly add a door and then block it off (like put a 'U' shape around a top door) just to grant a window into later parts of the dungeon.

The overworld can be generated using the same principles, except that you have far more secrets, and it is much more common for there to be a wall between some exits, and it is possible to generate the maze using tile granularity instead of room/screen granularity. In the original game, it seems the world was made mostly on the screen scale and then small tile-granular mazes were embedded at various points that ignored screen boundaries.

Share this post


Link to post
Share on other sites
Extrarius,
Sorry I didn't reply earlier, I just found your reply. This is going to help A LOT, especially for dungeon generation. I've had time to think about world map generation and got awesome ideas that should produce good results. I've also thought about a good algorithm for generating the individual screens. The only thing that was lacking was the dungeon part, so thanks for providing such exhaustive tips.

A big thanks to you and the other who participated in this thread. I'll be sure to check it again in case another cool post like yours appears.

If anyone's curious about my screen-generating algorithm, here's what it looks like: Path Generation.zip.

Share this post


Link to post
Share on other sites

This topic is 3313 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this