Jump to content
  • Advertisement
Sign in to follow this  
Anteater

Random level generation

This topic is 4078 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

I'm trying to implement random level generation in a platform game. The game is really 3D but mostly plays 2D. I have 1024 cubes which will make up the level. They all are at 0 on the Z axis but the X and Y axis are variable (like I said, it's really 3D but plays 2D). How would I go about implementing random level generation?

Share this post


Link to post
Share on other sites
Advertisement
Well I don't entirely understand your game... Let me get this straight, you want your level to be made of 1024 cubes arranged in 2D for the player to jump around... the question in terms of generating random levels is no so much how to generate them, as what they player is meant to do:
Do you want all areas of the level to necessarily be accesible?
Do you want an upper bound on the size of the level?
Do you want the cubes to be aligned in a grid or in an unstructured way?
Do you want them to all be the same size?
Do you want them all axis aligned?
Do you really want cubes, or do you really want cuboids?
Do you want cubes to be allowed to overlap or touch or do you want gaps between all blocks?
If you do want them touching, do you want large "islands" of blocks, or would you rather touching blocks be the exception?

If you answer all these questions... and explain what the players goal in the game is... then I'd say someone (possibly me) will be able to give you some much more specific advise on random level generation.
Bye for now,

Dan

Share this post


Link to post
Share on other sites
The levels would be made of cubes.
I'd like all areas of the level to be accessible,
no limit to the size,
the level may be lined up or unstructured,
they must be the same size,
they must all be axis aligned,
the cubes may touch, but not overlap,
I'd like islands of blocks.

The players goal is to either get to a random point in the map or kill all enemies on the map.

Share this post


Link to post
Share on other sites
I'm doing something similar. I'm creating Diablo-like top down levels, but one could simply turn the map sideways :b.

A) I create a map filled with walls.

B) Then I create a "room" by changing the "walls," which equal 1, to zero, the "floor," in a box shape(say 5 by 5).

C) Then I find the location of the next room(randomly) and draw a hallway to it(I draw "L" hallways[straight over then up]).
Back to (B).

As a side thought if I were to go about creating a platformer I would have to make sure that any "hallways" had platforms to let the player jump up.

This system could very easily be used to create a CastleVania/Metroid-like platformer, and I can say for that the maps I create do look from the top down like the castle map in SOTN for PS.

Finally I use a 256X256 map and it would work for a castle, I think it would be challenging to create a level with 32X32(if thats what you mean by 1024).

Finally finally :b by creating room then hall then room and so on you are guaranteed full explorability (so you wont have any rooms that don't have hallways to them). Though the level won't linear since hallways and rooms CAN be built on top of other rooms and hallways, thereby connecting rooms to rooms etc.

I love Procedural gen so GL :)

Share this post


Link to post
Share on other sites
ok... I've got an idea of the sort of game you are after... I'm guessing you'll want islands of various sizes connected by paths of either continuous blocks, or "stepping stones". To this end, I'd suggest that you probably want to choose a number of "seed" points in the level... these will be locations from which islands will grow. The number of seeds will determine the number of islands. You can simply decide on a size for the level (eg if you want 1024 cubes... lets say you want them to cover 1/16th the game area, so you want to work with a 128x128 grid). Given the grid size, use a random number generator to choose your seed points. Once these seed points are place on the grid... I suggest you use a type stochastic cellular automata approach to growing your islands. That's to say, for each cell that is "on" (ie would have a cube on) you do a simple statistical test to see if any of it's neighbours should be activated. The probability of each of it's neighbours "on" activated at the iteration might be fixed... or it could be determined by the distance from the centre... eg:
01210
12321
23*32
12321
01210
where * is the original cell... and 0,1,2,3 are the relative probibilities of those cells (around the active one) being activated. When doing these tests, you can simply skip a cell that's already on. I say relative probabilities, because you'll have to multiply them all by some factor (and that factor will be one of the parameters you can set to make levels differ from oneanother). You may also have an anisotropic distribution... that's to say that the probability of cells growing vertically is greater than the probability of cells growing horizontally. Once you've run an appropriate number of iterations, you'll have a number of islands which vary in size (somewhat) and are placed randomly around the world.

Now comes the fun part hehe.. ensuring the world is connected. to this end I thought of various options. The easiest I think is to have a second array, this time of integers all initialised to 128... and in this array transfer one randomly chosen island... eg pick cells until you hit a full one, then add adjacent cells that are also on until it's picked... a "flood fill" type approach. Each cell corresponding to a cell on the main island is then marked with a 0. You will now iterate this array... by looking at every cell marked 0 and placing a 1 on all adjacent cells that contain 128... repeat the process but with the cells containing 1 (ie set adjacent cells that have 128 in to 2)... continue this process until one of the cells you are setting corrseponds to an island cell in your original array (This is a type of breadth first search by the way). Once you've found this cell... you can "follow" the integer field to the other island... to do this you may move to an adjacent cell with equal or lower number. You then mark this cell on the original array as containing a block. You'll have to choose the probablities for equal or lower numbers appropriately so it'll make a path more or less direct... and may fill areas rather than making a narrow path. Once you are on a cell labeled 1... you have reached the other island, so you may now choose (according to some probabilities) to either move to another cell of value 1... or end this pass.

Once your pass has ended... your two islands are now considered as 1. This is your new "base island" from which to iterate again. You keep repeating this process until your search has no more cells to fill. At this stage every island is now connected to every other island.

At this stage you could potentially run a pass to randomly remove blocks. As long as the blocks removed are at least 1 cell apart, then they will never cause the map to lose connectivity. To this end, you could select only odd or even numbered elements (this decision could be made at random).

In practise this system has a lot of statistical parameters.. but if you find what ranges of values work together by experimentation... you can let your computer randomly set these parameters itself. Another option is to have a set of exact parameters (or parameter ranges) that your computer can pick from at each step. You can also seed the random number generator explicitly. in that way you could have a single number corresponding to a certain level... so someone could note down the number of a level they couldn't complete and come back to it... or even have a list of set numbers corresponding to levels.

I am assuming here that you didn't need exactly 1024 blocks... as this method can be tuned to give you roughly 1024 blocks... but not exactly that number... if you want a specific number... you could apply the same "depth first seach" method (in fact... when you found out the method was finished you already had this result):
If you have too few blocks, you can safely add to any element marked 1.
If there are too few, fill all of those, then start on the ones marked 2... if there are too few, start on the ones marked 3 and so on.
If you have too many blocks... you can repeat the depth search process.. but considering the sea to be an island... You may now remove any cell marked 1 that has a neighbour marked 2 (this ensure it remains connected). If there are too few... repeat the process until you have exactly the correct number of cells.

This sounds like quite a complicated approach to a fairly simple problem, but I think it'll yield quite a nice result. If you wanted, you could also interpolate the boundary of the island in some way to give it a less angular appearance. There are many alternatives like fractal noise (or probably in your case... a normal fractal noise composited with a ridged fractal noise), or starting with a full grid and removing cells according to that depth first search for element removal method I described (which would probably work quite well too... but I was worried it't tend to make one big island).

Anyway, I just thought of this algorithm and I haven't tried it... but I think it'll yield good results. I might even program it up :) (If I do I'll post the code on here).
Good luck,

Dan

Share this post


Link to post
Share on other sites
Hello again,

Well I was a little bored last night, so I actual made the random level generator I proposed. It's in C++ and it's not hugely well written as I didn't design it at all up front, but it does work. The main function hopefully illustrates how you should use it... you could make an init method that called the functions will appropriate parameters automatically (or even add a new constructor).

It has two features I mentioned that are not implemented:
1. When joining islands it always picks one (of potentially many) of the routes between the islands if minimum length.
2. The pass to correct the number of elements can only add elements to the array, it returns to tell you if it managed to get exactly the number of elements you wanted.

It also has one bug, which I am no that inclined to track down. If the Seeding and Automata pass (or passes) overfill the array, an infinite loop is caused somewhere in the remaining code. This may sound serious... but since it can add elements to bulk up the initially generated level, you can simply ensure that the seeding, automata and island joining processes do not fill too much of the level.

With the parameters I've included in main... I've not had any problems. If you uncomment those extra lines you can see how the level is generated through the passes. The program also takes a command line parameter which is a number from 0-1 representing how much of the array you'd like to be filled.

Another point is that none of the code is that efficiently implemented, so if that's an issue for you (at the level size you are using) then you'll have to rewrite some of it. The random number generator is seeded from the time in seconds, so if you run it twice within a second you'll get the same result.

Anyway, here it is. I built it in cygwin under windows (using -mno-cygwin) and have included a prebuilt executable. It runs from the command line and doesn't pause at the end, so run it from a command prompt/console to see its output. It also contains a makefile that should build happily under *nix, mingw, cygwin and OSX (I presume). The code itself should work on anything. The text format is most probably be unix so you may have to convert the files to load into your windows IDE (wordpad can do this).
Hope you find it useful, and if not, hope someone else does,

Dan

PS: I have no idea how long that link will work... so if you want the code, be sure to keep hold of the archive. Feel free to do what you want with the code.

EDIT: Another note, the world it creates is cyclic, and all the code follows this arrangement. You'd have to go through changing all the % somethings to make it clip at the edge. It'd be most important to do this on the path finding parts... ie the BFS routine and the fill routine. If you changed it there the connectivity routes would never loop off one side of the world and come back on the other. Changing the BFS and fill only would still potentially have partially cut islands on the edge of the world, but it'd all be connected internally. If you want the islands be cut off less frequently... you can generate the seed points towards the centre of the grid... and alter the Automata step to stop elements looping. Everything should be fine as is. I thought it'd be a nice feature that the world could tile... but this'd require you to deal with that in your game code (probably by effectively drawing 9 copies of the world surrounding and including the one the player sits on.

[Edited by - mrcheesewheel on July 27, 2007 3:12:15 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!