Need help with random map/city generator

[louie999]

So I'm lost here in this part, how can I can create a good random map generator? In the game I'm making the player will be in a zombie infested city, so I need to create a map generator, as I don't want the map to always be the same. I hope someone can help me with this as it's hard for me

[Jasoco]

There's no single correct way to do it. You should Google because there's dozens of articles out there describing different methods. I'm working on a random dungeon generator, but it wouldn't work for a city. A city is completely different. Usually it's easiest to create templates or puzzle pieces and then use logic to fit them together in workable ways like games like Spelunky do. If you play through Spelunky you start to notice patterns in the level layout where you start to see the different pieces being used.

It depends on how the map data will be formatted too.

[ivan]

With terrain generation there are 2 major techniques.
The first method is where you run a simulation for a while and allow the different terrain features to 'evolve' naturally. For example, if you want to have rivers, you would add a few water sources and allow the water to flow/erode the terrain.
The second technique involves running an algorithm that FIRST puts in terrain features like rivers (or streets in your case) and THEN adjusts the terrain based on where these features are so it looks more believable.
City generation is not easy, and it depends on what you have in the city in addition to streets.
And as Jasoco mentioned, it depends if your map is a grid or vector based.

[louie999]

Well my map is gonna be grid-based. I searched for some topics/articles about that like how they generate a minecraft world etc. but it's still a bit complicated to me . The only random map generator I could probably do would probably be sucky as it would just place tiles randomly and messily in the map...

[Imaculata]

I'm currently building a random dungeon generator, and I'm trying to figure out the same thing. My game is a sort of Zelda clone. This means that the player will encounter locked doors, and will need to find keys, and key items, before heading to the exit.

I have all my rooms in a separate table, along with links between each room. Each room uses a prefab template. I basically have about 10 variations of every type of room, and the game is supposed to pick a fitting room. For example, if the room is a T-junction, then the game should pick from the folder containing 10 different T-junction-rooms. The doors are pasted into the rooms separately. So each room template is basically without any doors, but the connections are added later.

So how do I make sure that the game not only finds a path from the entrance to the exit, but also takes into account the proper placement of doors and the keys needed to open them? Because I don't want my players to get stuck.

[Rickton]

Unfortunately, nobody's going to be able to give you an easy answer, because it really depends on what you want to have in the game, and it's going to be a personalized solution.

The best advice I could give would be to start simple. You're making just a city, not a whole world, so Minecraft-style world building, or simulated terrain generation like ivan talked about aren't really necessary. You said it's also going to be grid-based, so that makes it a little easier, too (especially since a lot of cities are on a grid layout anyway!).
Here's how I would do it:
Just focus on putting down some roads and buildings first. Try just drawing a few roads between different points, and putting buildings in the places the roads aren't, or, putting the buildings down first, and drawing the roads around them. A pathfinding library like Jumper will probably be very helpful.
Once you've got the basics down, add more complexity...other things in the city (parks, parking lots, a river running through town, whatever), making the roads all connect to each other, tightening up the algorithm to make it make more sense, etc.
If you've never done anything like this before, you might end up having to throw away large portions of the map generator, but that's OK. A lot of this is experimentation and seeing how things work.

If you want to also have the buildings be enterable, that'll be a completely different generator, too, obviously.


Here are a few links about "dungeon" generation. They won't be directly applicable, but they might give you some ideas.
On the Procedural Content Generation Wiki
On the roguelike wiki (a specific method that goes in-depth into how it works)
If there's any code on there, it's not going to be lua, but a lot of articles in those places go in-depth step-by-step how the generator works, so you should be able to roll your own.


That was a big post, and there's a lot to learn about, but don't stress out too much! Procedural generation can be pretty fun, seeing what kind of craziness your generators come up with. Like I said, just start simple and work your way up.

[louie999]

Here's how I would do it:
Just focus on putting down some roads and buildings first. Try just drawing a few roads between different points, and putting buildings in the places the roads aren't, or, putting the buildings down first, and drawing the roads around them. A pathfinding library like Jumper will probably be very helpful.
Once you've got the basics down, add more complexity...other things in the city (parks, parking lots, a river running through town, whatever), making the roads all connect to each other, tightening up the algorithm to make it make more sense, etc.
If you've never done anything like this before, you might end up having to throw away large portions of the map generator, but that's OK. A lot of this is experimentation and seeing how things work.

Hmm, I think I could try that then I'll improve it until I get the desired results. Thanks guys for your answers

[Jasoco]

So how do I make sure that the game not only finds a path from the entrance to the exit, but also takes into account the proper placement of doors and the keys needed to open them? Because I don't want my players to get stuck.

The easiest way to do this, and it's how I did it for a dungeon generator I was working on (Which I styled like Zelda as well) is to draw the path from the start room to the exit first randomly, then fill in all the empty space with random paths until the map is filled. The style is called "Hunt and Kill".

Basically step by step you'd:
Place a start room at a random location based on criteria (Like maybe the entrance should always be at the bottom of the map)
Move in a random direction and place a room.
Pick another random direction and place a room.
Keep doing this until you either hit a maximum chain length, or the "crawler" gets stuck and at this point place the exit.
Next scan the grid for the first empty cell and pick an adjacent filled room to start a new chain then start a new crawler in this direction and do the same thing until it hits a max length or gets stuck.
Keep doing this until you fill the map. (See the link above for a neat demo of how it works.)

Obviously as you go you'll want to add some metadata to each room like which walls have doors to other rooms.

What I do at the same time is have a counter that starts at 0 for start and increments with each room and marks each room as a "depth" from the start of the map. When you start a new chain, start its depth from the depth value of that room.

Alternatively instead of setting the first chains end as the exit, you can keep a record of all the chains and find out which room has the highest depth when all is said and done and have the exit be the furthest from the entrance as possible.

As for picking where to lock doors and making sure you can still get through, well, look at Isaac. They determined this was way too unnecessary for their game and made it so locked doors would never be in the way of the path to the boss. But rather only side paths are locked since keys are totally random (Not every level will have the same amount of locked doors and keys. Some might not even have keys at all.) You'd have to decide later if you want to lock off rooms and maybe traverse the chain backwards, place the locked door, then before reaching the beginning of the chain, place a key. You could also have the final room be a boss door and place the boss key in another chain. (This is what I'm doing with my current generation algorithm)

[Imaculata]

That is extremely helpful Jasoco. I'm going to try your approach of adding chains, and marking them with a depth. Then when I start adding items, I can simply put them in another chain. I'm not sure yet if I want locked doors to appear in the main chain that leads to the exit. It would be preferable, but then I'll need to make sure that the start of the chain that the key is in, appears before you reach the door.

I suppose what I could do is this:

1. Create the main chain from start to finish. Rooms in this chain are marked as "main", and are assigned a depth.

2. Pick a random unused room that is adjacent to the main chain, and start a new chain from there, which we'll call chain "B". This chain "remembers" the depth of the room it is attached to. I'll create multiple chains this way, all attached to chain "main".

3. Place a key at the end of chain "B", by searching for the room that has the highest depth AND is inside chain "B".

4. Place a door with the same color as the key, in a chain that is not chain "B", and has a higher depth than chain "B" 's origin.

This way I make sure that the key is accessible before the player reached the door that it opens. One problem though. Currently I place both the entrance and the exit randomly, thus forcing me to trace a path from start to exit, which is a bit tricky. Maybe I'd be better off just placing the exit at the end of chain "main".

[Jasoco]

Yeah, the way I am currently experimenting is I'd have the start room, then keep adding chains and place the exit in one dead end and a key in another. The key would open the exit. The exit may be a boss so I guess it'd be a boss key. I don't even know what my generator is going to be used for yet actually. I don't have a plan. I'm just experimenting.

Actually the current generator I'm playing with doesn't use a grid for room placement rather uses a grid as a canvas and rooms are carved into it. I am using a method described here.

Screen Shot 2015-08-20 at 4.00.38 PM.png (461.62 KiB) Viewed 5758 times

So it's not really the same as the Hunt and Kill method I explained above but it works for making maps with odd shaped rooms.