How do I generate a 2d grid-based map without screwing it up?

Question

I'm relatively new to the mechanics of game development - catching up fast, but there are still some things that escape me. For example: generating a fully-accessible map on a 2d grid.

See the example at http://crawl.s-z.org. Each floor map starts with dozens of winding labyrinthine passages and randomly drops in points of interest - temples, boss lairs, bazaars, etc. I know there's a lot of factors that go into this: generating passages that always have at least one exit (no isolated tunnels in the walls), making sure passages have at least a one-cell-width wall between them and adjacent parallel passages, and dropping points of interest in such a way that they connect to the dungeon.

I've taken a shot at it, and it's very easy to ranomly place lines in a 2d matrix that represent passages - but they're never guaranteed to connect, and it's not nearly as elegant as the maps at the above example.

I suppose my question is, what do I need to know to reproduce the example at crawl.s-z.org? I know this is a large question - I'd be fine with someone handing me a link to a reference site and telling me to learn it there. I'm just new enough at this that I don't even know what terms to google - maybe there are names for different generation processes? Available techologies are JS (jQuery) and PHP, so a solution tailored to one of those would be ideal. Thanks!

Answer 1

I recently created a test program for an algorithm I found.

It works on the premise of:

I'm an evil overlord and I want more space.

Basically the room is seems to be built out of necessity rather than uniformly with corridors.

The stages are as follows.

1. Fill the whole map with solid earth
2. Dig out a single room in the centre of the map
3. Pick a wall of any room
4. Decide upon a new feature to build
5. See if there is room to add the new feature through the chosen wall
6. If yes, continue. If no, go back to step 3
7. Add the feature through the chosen wall
8. Go back to step 3, until the dungeon is complete
9. Add the up and down staircases at random points in map
10. Finally, sprinkle some monsters and items liberally over dungeon

now at 4 the new feature in the Java example provided on that page, only builds a rectangle room or a corridor this could be expanded to have different kinds of rooms and at 5 implement a method to check your room will fit.

This ensures you can always reach the rooms/corridors as they have to be built off each other.

Answer 2

I didn't make random generating maps yet. But I'm sure I would use some path finding algoritms which aren't difficult to write.

For example path finding using queues. You add starting field to queue, then your function recursively takes first element from queue and adds every adjacent field of this taken field to queue. Then again you take first field from queue and so on.

Let's say you have two types of field (solid, nonsolid). When you get field from queue you can set it a type if it pass given conditions.

In example if adjacent field has already set type (nonsolid) that means you are going to make link between two routes or not going this way (setting it as solid) or if adjacent field is already in queue then dont add it to queue again so you wont go same route twice (unless you want to).

You have plenty of options and there is much more of explaining which I dont have time for. But queues is a way to go imo.