Random map generation

Pages: 12
So I've been working on this thing. The idea is sort of like a top-down adventure game... not unlike classic Zelda... but without the secret passages and stuff.

But to keep it interesting, I figured "make the maps random, that way it'll have replay value". So it's more like a roguelike in that sense... except actiony instead of turn-based.

I've been working on-and-off on this for quite a while (when real work doesn't keep me busy). I just recently got back into the groove with it... and more or less finished the random map generator.

So I felt like showing it off.

Pics of 5 generated maps here:

http://imgur.com/AJD7d1N,MMqAROX,PUxzoYL,YnuCgM0,9TnCrZP#0


The real maps will be bigger... I just have to fudge some parameters. Also take a note of the zoom... it looks tiny from a distance but even those skinny passageways have lots of room.
Looks pretty interesting.

Are you using SFML or what library?

Also, that map is very large 25,000 x 20,000 are you going to turn it into several small maps then when you get close to a border load the next section? I would imagine a map that size would need to take a lot of memory if you tried to load it all at the start.
I was wondering what you've been up to; I held off on asking because I knew you would post once you had something to show off. Some colorization would be cool but otherwise the maps look great! Tell us, did you win an award for the fjords? (I couldn't resist the reference).
Thanks for the interest, guys =)

giblit wrote:
Are you using SFML or what library?


Yeah SFML. But I'll be doing most of the rendering with OpenGL directly in the actual game. Though for these test apps it's strictly SFML.

Also, that map is very large 25,000 x 20,000


I'm a sucker for big maps. Especially in exploratory games. Though really, 25k x 20k doesn't seem that big to me. The screen res will likely be full widescreen (1920x1080). So really this is more like 12x20 "screens" which is smaller than the map in classic NES Zelda.

The tricky part will be making the terrain graphics interesting so it doesn't get repetitive. But I have a few ideas for that.

are you going to turn it into several small maps then when you get close to a border load the next section?


Basically yeah. It'll be broken up into sections and I'll only have nearby sections loaded. It'll load new ones on the fly so it'll be seamless.

Plus, this is just the overworld map. You'll go into "sub maps" for the dungeons and stuff. Though I'll probably use the same generator, just tweak the params a bit differently for each one.



Computergeek01 wrote:
Some colorization would be cool but otherwise the maps look great!


Yeah this is just the physical map boundaries. Next hurdle is graphics. I actually want a sort of 2.5D thing where I'll actually have 3D polygons with depth for the walls. (Which explains my recent questions about smallest enclosed circle http://www.cplusplus.com/forum/lounge/141261/ , and that 'starfield' generation http://www.cplusplus.com/forum/lounge/141313/ -- both of which I will need to build the polygons the way I want.

We'll see how that works out.


Tell us, did you win an award for the fjords? (I couldn't resist the reference).


The reference went over my head =x

I had to look up what a fjord was. =P
Nice work Disch, those look pretty nice. It's also cool that they are self contained. Have you considered on-the-fly generation rather than a preset map?
Last edited on
LB:

Do you mean on-the-fly as in "generate the map as the user is playing"? If so, then no. I don't really see the value to that... and it'd be a LOT harder.

But if you mean "a completely new set of maps each time the user starts a new game", then yes, that is my goal.



I figure I'll have a few seconds of loading time when the user starts a new game. Currently the map is generated practically instantly, but once I get the graphic stuff in there it might take a hot minute. I might use that time to run a little intro story thing for the player -- or maybe a little tutorial. But that's step 16749, I'm still on step 6.



EDIT:


I'm really proud of the algorithm I used, too. Came up with it myself. I'll take some more pics and explain it in a bit.
Last edited on
So the way it works is... I create a "grid" that consists of many "blocks". I didn't want to use a normal 2D grid, as that tends to make it too recognizable as a pattern... so instead I had blocks of random size and just crammed them into the world:

http://imgur.com/xbK2VEk,s8gwkps,9NU2HEm#0

I then have "points of interest" for things like dungeons, towns, etc. I mark a few of those blocks as having a point of interest, then start carving out a path with a A* style search technique, joining one point of interest to another. I then discard any blocks that were not part of the path:

http://imgur.com/xbK2VEk,s8gwkps,9NU2HEm#1 (highlighted blocks are where there are points of interest)

So now I have a series of blocks... as well as where those blocks border other blocks (ie, where each block's 'exit' is). I feed that to my block generator which does this:

http://imgur.com/xbK2VEk,s8gwkps,9NU2HEm#2

The soft color lines in the middle are the "main path". They're basically randomized lines joining all the exits (and the "point of interest" if the block has one, which is the one part that juts out to the right)

To prevent the user from getting blocked in behind an impassible wall.. I simply say that the wall lines cannot come with a certain distance of the "main path" line. Ensuring there will always be room to maneuver from point A to B.

The wall lines are generated similarly to the main path lines, just with different params. It's basically just getting from point A to point B... but squiggling around and being kind of random as it goes. I then threw in some obstacles and stuff to spice it up.


So yeah... make a bunch of blocks like that.... then glue them all together... and you've got the world!
Very cool.
By on-the-fly, I mean the map is boundless but only generates near the player.
@Lowest0ne: Thanks. ^^

@LB:

Nah that wouldn't jive with the kind of game I'm trying to make. Is that what Minecraft does?
Sort of, Minecraft uses a mix of various techniques.
By colorization I meant exactly what you had in your second set of images. I just saw boundaries and had no idea what was transverseable and what wasn't.

The reference went over my head =x

No one reads Douglas Adams anymore. :(

When you say "top down ... 2.5D + 3D graphics" I'm having a hard time picturing this. Do you mean isometric like the Diablo franchise? Otherwise the description brings to mind an nostalgic memories of Lands of Lore: Guardians of Destiny, except that was first person.
closed account (z05DSL3A)
No one reads Douglas Adams anymore. :(

I got it. ;0)

"Look at me - I design coastlines. I got an award for Norway... I've been doing fjords all my life...for a fleeting moment they become fashionable and I get a major award." — Slartibartfast

Off main topic, but on the topic of Douglas Adams. Have any of you guys ever watched the 6 episode miniseries? It stars the actors who did the radio show
Last edited on
closed account (z05DSL3A)
All Hitchhiker's: http://www.cplusplus.com/forum/lounge/141379/

Trying not to derail this threadTM
Last edited on
Computergeek01 wrote:
By colorization I meant exactly what you had in your second set of images. I just saw boundaries and had no idea what was transverseable and what wasn't.


Ah... yeah. That'd be harder to add than it's worth for this test app.

No one reads Douglas Adams anymore. :(


I generally don't read fiction. =P Any book quote is likely to go over my head.

When you say "top down ... 2.5D + 3D graphics" I'm having a hard time picturing this. Do you mean isometric like the Diablo franchise?


Nah... isometric is isometric. To me, 2.5D is a game that has 2D gameplay but has [some] 3D graphics. See Shadow Complex for an example. The game is completely rendered in 3D, but it plays exactly like a 2D platformer.
closed account (10X9216C)
Personally i don't find randomized maps make the game all that replayable, especially since you are making the points of interest static except in different locations on the map. The overworld loses all the fine details you can do by hand crafting it. In rogue-like games the "exploring" factor isn't really that great as there isn't really anything major to find, when there is, it usually is the same static thing to find so replaying the map for the different paths doesn't make sense to me at least. I know there's a top-down zelda/dark souls-like game coming out soon that i'm looking forward to, "Below" ( http://en.wikipedia.org/wiki/Below_(video_game) ).
Last edited on
Random map generation works for some genres.
It is true that one of my favorite things about Skyrim are little nooks that I can tell the developers had a fun time making. On the other hand, after you've seen them once, there isn't much point to go back.

Games like Civilization or Sim City are very much replayable because of the ability to have a ranomdly generated map. This is because there is so much that depends upon the map. So I think that if the map is randomly generated, major aspects of the play need to be dependent upon the map.

As simple of an example idea as possible, monster X might be spawned in a certain layout, as with monster Y. If these two layouts happen to be close to each other, then there will be some sort of dynamic interaction happening between the monsters.

I often think about what would make a great rpg, but I also don't want to derail this thread.

Hi Disch,

Just wondering whether you have considered using fractals to generate your terrain / paths / maps. I guess you may already know that fractals were discovered from this exact problem.

Although you already have a 2D map, maybe you could make use of it to make the 3D fractal terrain.

As per usual, it is just my 2 cents worth - but one never knows how much potential value there is in an idea, so I am putting it out there.

P.S I will be travelling & working tomorrow, but I am sure there is plenty of vastly better advice than mine on Google & elsewhere.

Regards
Pages: 12