Random Zelda-style map generation

Question

Im trying to randomly generate a map of rooms connected by doors, and I've succeeded in generating one using this code:

public void generate(GameContainer gc) {
        rooms = new ArrayList<Room>();
        startingRoom = new Room(0);
        startingRoom.setPosition(viewport.getCenterX(), viewport.getCenterY());
        lastRoom = startingRoom;
        rooms.add(startingRoom);
        int roomsize = 25;

        for (int i = 0; i <= (1000 + Math.random() * 4000); i++) {
            Room room = new Room(i + 1);
            int direction = (int) (Math.random() * (4));

            switch (direction) {
                case 0:
                    room.setPosition(lastRoom.x, lastRoom.y - roomsize);
                    break;
                case 1:
                    room.setPosition(lastRoom.x, lastRoom.y + roomsize);
                    break;
                case 2:
                    room.setPosition(lastRoom.x + roomsize, lastRoom.y);
                    break;
                case 3:
                    room.setPosition(lastRoom.x - roomsize, lastRoom.y);
                    break;
                default:
                    room.setPosition(lastRoom.x, lastRoom.y - roomsize);
                    break;
            }
            rooms.add(room);
            lastRoom = room;
        }
    } 

However, this doesnt allow me to find out which doors the given room has. I need to be able to figure that out so that I can place the doors in the correct places so that they can be used to adjoin rooms. Is this sort of "smart map" possible with my current algorithm, or should I start over? What steps can I take to get this working?

I'm using Slick2d and Java for this

Thanks.

Answer 1

I think that this question is quite open-ended, since there are a few pieces of code you'll need before you can link the rooms properly and how you code that up depends a lot on how things make sense to you.

Having said that, I can make a few recommendations to help you go in the right direction.

First of all, if the room sizes are constant I'd recommend making a higher level coordinate system for the rooms. Something that would look like this:

 _____ _____ _____ _____ _____
|     |     |     |     |     |
|-2,-1|-1,-1| 0,-1| 1,-1| 2,-1|
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|-2,0 |-1,0 | 0,0 | 1,0 | 2,0 |
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|-2,1 |-1,1 | 0,1 | 1,1 | 2,1 |
|_____|_____|_____|_____|_____|

The idea being that when you're making room (0,0) you ask rooms (-1,0) (0,-1) (1,0) and (0,1) where the adjoining doors are. If you need screen coords, it should be easy enough to add a GetScreenCoords method or a transform matrix if you're into those.

Next you'll want to be able to query the list of rooms. Going through all of the rooms in your list (up to 5000!) just to find the neighbouring rooms will get costly. For a quick way to get things up and running, I'd recommend using a HashMap<coord, Room> rooms instead. This way when you're making room (0,0) you ask for existing neighbouring rooms you simply ask for rooms.get((1,0)) etc. and to add your newly generated room at (0,0) you'd do rooms.put((0,0), newroom) If this becomes too slow, it might be worth looking at sorted lists. Perhaps a sorted list(x) of sorted lists(y).

Finally you'll need to add some way to get the door position from the neighbouring rooms. A new method like int GetSouthDoor() should do the trick.

I'm sure there will be a lot more work for you to code a full solution. I hope this will help you get started.

Answer 2

Two things:

1) In your comment, you say you want something like the Binding of Isaac. That game has doors in the middle of each piece, guaranteeing that they line up. If you follow suit, then it only comes down to deciding what kind of door to connect them with (open, locked, bowall, etc).

2) Your code appears to start at one location and procedurally generate new tiles off in one direction. In your switch statement, however, you're not accounting for the direction you're coming from. If you continue with that algorithm, consider keeping track of the last placement as well, so that the tiles don't overwrite each other.

Answer 3

Use a maze generation algorithm

Use a modified form of Prim's Algorithm to create a basic maze of 20 rooms or so. Choose two rooms to be start and end rooms, ensuring the end is always reachable. Block off random doors with different door types and randomly add doors where two adjacent rooms are not connected (with low probability)