Design Need Level Generation Ideas or Feedback

[samspade]

I'm looking for ideas, or code if anyone feels generous, for level generation. Essentially my game level works like Downwell - long narrow room, no side passages (with enemies). I've been using the following system:

• Start at top of level. Move down the level a set amount with a random offset and spawn in a platform. Repeat until bottom of level is reached.
• Iterate through platforms and spawn enemies on top of some of them.
• Start at top of level. Move down the level a set amount with a random offset and spawn in a random enemy. Repeat until bottom of level is reached.

It's a little more complicated than that, but that's the basic idea. This worked fine when I was dealing with a limited amount of enemies. But now I have a lot of enemies, many of which have strong types and don't play well with other enemies or platforms, and I need more control over how the level generates.

Given this set up, what seems more appropriate?

• Design a bunch of 'chunks' which in this case I think would be scrips with a preset spawn in load out with maybe some randomness to it?
  
  
• Some type of genetic algorithm?
  
  
• Something else?

The chunks seem easiest but also the most limiting. I like the idea of some genetic algorithm, but I don't have a great idea of how to implement one with the level of complexity I need. And I haven't thought of another system flexible enough.

 

[ScimitarDD]

I don't think chunks are too limited. You could randomize them and connect them in a realistic way like underneath chunk of type 1 can only be chunk of type 4 and 6 (just like snow biomes in Minecraft shouldn't be next to desert biomes).

Using chunks would be similar to how Doodlejump works. Without chunks it would be too random. An example of this is a chunk where platforms are too far apart from each other so you have to jump onto an enemy to reach the next platform.

You can also interlace chunks. Make big chunks that contain smaller chunks. That should make the level interesting and it's not too complex to implement.

Also, levels made with a complete procedural generation are limited too. Players understand the pattern of the random generation after a while and it gets boring.

 

[NightFrost]

Predefined chunks can work. It depends on how many different types you make and how you define potential rules how they can connect to each other. A platformer project I made used small random maze generation and then replaced each segment with a random predefined piece out of five possible ones, each piece being sized 32*32 tiles (so, for example a 10*10 segment maze would equal 320*320 tile room). Yes, the idea was directly lifted from how Spelunky generates its dungeons.

 

[samspade]

Alright, so I've come to a basic solution that I'm going to use for the moment. But I'm sure I'll revisit this later so feel free to give more ideas.

My current solution is a fairly lazy form of chunking. I'm not going to post all the code because it is a lot and most of it fairly specific - but the idea for anyone interested is the following:

• Define level length and section length.
• Divide level length by section length.
• Create an array of that length.
• Run through a for loop of the same length of the array and spawn in additional wall features at random.
• Whenever you spawn a wall add a value (currently using 100) to the array at the same position.
• Run through a for loop of the same length again if the value of the array is >= 100 continue, otherwise spawn in platforms at random.
• Whenever you spawn a platform in add a value (currently using 100)
• Create a script for each enemy type which governs spawning in.
• At level start add the desired enemy scripts to a list.
• Shuffle the list.
• Run through a for loop of the length of the enemy list.
• Use script execute on each script in the list.

Currently, most of my enemy scripts act pretty similar to the add walls and platforms scripts. They use a for loop, check if the value of the array is > 0 and if it isn't have a chance to spawn in and add 1 to the array. But this can be changed.

Current benefits of this approach are that it is flexible, allows me to add any random selection of enemies I want in and keeps them from overlapping walls, platforms and so on. Since each enemy spawn script is unique I can control how it spawns in with much more control than if I just iterated through the level once and selected at random. As a side effect, since multiple enemies can't spawn in the same 'section' which is really just a 200 pixel tall portion of the level and the enemies scripts which run first have a greater chance of finding an empty space and spawning it means that each level gets a sort of significant enemy type by default.

Also it was pretty easy to do in a couple hours.


Downsides are it is still pretty random. The more I think about it, the more I think that some form of chunks, essentially vertical rooms stack on end, is the way to go.

Thanks for the help. And like I said, if people see this and have other thoughts on how to do this, I'd be very interested.

 

[NightFrost]

One general way to reduce noise in randomly generated field is to iterate through it multiple times and apply some rule to fix each grid cell. That is, the cellular automata generation approach. First pass fills the grid with random noise. Second and further passes apply rules: if a cell is empty and has X wall neighbours, the cell receives a wall. If a cell has wall and Y empty neighbours, it is made empty. Results are always saved to a new grid so you don't alter the current one while processing it. Your level design has specific needs though (an uninterrupted downward passage) so it might be better to start with an empty base (besides bordering walls), add some random platform seeds and use the iteration loop to just grow them. Adjust rules so they favor horizontal growth. Testing for connectivity should actually be simple: copy the grid to a motion planning grid and try to make a path from top to bottom (leave a number of top and bottom rows totally empty so start and end are not simply boxed in). If a valid path is returned, there is open passage through the map. If not, reject and generate another.

 

[Yal]

Another approach to extend chunks: have chunks have "generic" and "random" parts that are randomly selected when the chunk is placed. A generic TurretEnemy is replaced by either a NormalTurret, a TripleTurret, a VerticalTurret and so on, a generic DestructiveObjects could be replaced by either some background decorations that are just for show or solid crates that work as cover or gets in the way, and random parts could be filled with completely random tiles.

I like chunks because they let you design stuff top-down (decide WHAT to do and then do it, instead of placing random stuff and then trying to make sense of it). Adding multiple layers of randomness using generic objects and random-tables keeps making it less obvious you reuse the same chunks over and over.

 

[samspade]

One general way to reduce noise in randomly generated field is to iterate through it multiple times and apply some rule to fix each grid cell. That is, the cellular automata generation approach. First pass fills the grid with random noise. Second and further passes apply rules: if a cell is empty and has X wall neighbours, the cell receives a wall. If a cell has wall and Y empty neighbours, it is made empty. Results are always saved to a new grid so you don't alter the current one while processing it. Your level design has specific needs though (an uninterrupted downward passage) so it might be better to start with an empty base (besides bordering walls), add some random platform seeds and use the iteration loop to just grow them. Adjust rules so they favor horizontal growth. Testing for connectivity should actually be simple: copy the grid to a motion planning grid and try to make a path from top to bottom (leave a number of top and bottom rows totally empty so start and end are not simply boxed in). If a valid path is returned, there is open passage through the map. If not, reject and generate another.

CA, that's what I meant instead of genetic algorithms.

Another approach to extend chunks: have chunks have "generic" and "random" parts that are randomly selected when the chunk is placed. A generic TurretEnemy is replaced by either a NormalTurret, a TripleTurret, a VerticalTurret and so on, a generic DestructiveObjects could be replaced by either some background decorations that are just for show or solid crates that work as cover or gets in the way, and random parts could be filled with completely random tiles.

I like chunks because they let you design stuff top-down (decide WHAT to do and then do it, instead of placing random stuff and then trying to make sense of it). Adding multiple layers of randomness using generic objects and random-tables keeps making it less obvious you reuse the same chunks over and over.

Also a great idea.

 

[Niels]

Think downwell used chunks.