Ideas to how to generate lakes on a map

General discussion about LÖVE, Lua, game development, puns, and unicorns.
Post Reply
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Ideas to how to generate lakes on a map

Post by Gunroar:Cannon() »

I use rotLove (needed to run example I posted, sorry) for generating maps. Works okay. But I want to generate maps more like Brogue (using rotLove's Brogue map gen) but it doesn't work well and just gives me either square rooms or one whole cave.

Code: Select all


--[[ Brogue ]]
ROT= require 'src.rot'
function love. load ()
    f  =ROT.Display( 80, 30)
    brg=ROT.Map.Brogue(f:getWidth(), f:getHeight())
    brg:create(calbak, true )
end

function love.draw() f:draw() end
function calbak(x, y, val) f:write(val== 3 and '*' or val== 2 and '+' or val== 1 and '#' or '.' , x, y) end

local update= false

function love.update()
    if update then
        update= false
        brg:create(calbak)
    end
end
function love.keypressed(key) update= true end
But this is how a Brogue level looks
Image

Now I'm wondering how to get those "lakes" (water lakes, chasms and lava lakes) to generate too like Brogue in a way that no room is blocked and there's a path to every where, like brogue.

From this interview (and also the gdc talk that's out there + the wiki) it says that it generates a blob(?) then moves it around until there's always a path to all places and nowhere is blocked. Won't that take some processing time? (But levels load fast in Brogue) And how would I check if there's a path always :? I feel like it wasn't explained to it's fullest.

Anyway, I still attempted. I first tried just using Cellular Automata (it didn't work :awesome: ) ... to rough, hence why Brogue used "blobs" so I went to the code of rotLove and saw how they made cave levels and generate a mini Brogue cave around half the size of the original level (I had to edit the rot code to give me a Brogue cave always when I needed). But 1) The blobs aren't always connected and 2) They don't look as natural, and that's even before I've tried to "move it around" :cry:

Please does anyone know/try to implement this feature?
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Ideas to how to generate lakes on a map

Post by pgimeno »

Gunroar:Cannon() wrote: Wed May 17, 2023 7:40 amAnd how would I check if there's a path always :?
1. Identify a point in every room. Any point inside the room will do. If there are 25 rooms, you will have 25 points.
2. Flood-fill one of these points.
3. Check that every other point has been touched by the fill.
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Ideas to how to generate lakes on a map

Post by Gunroar:Cannon() »

Oh, okay. That helps. Path problem fixed then :) (My dad brain was imagining doing A* path finding for every time :rofl: )

But isn't there a better way to do it than "shift" the blob around until there's a path? Hmmmm. And there's also the problem that the blobs produced aren't as best as the lakes in the picture.

I was browsing around and found this "bombing the contour method" though I'm not sure if it will work well.
www.darkgnosis.com/2018/03/03/contour-b ... -algorithm

I'll test the blob method more.
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
tourgen
Citizen
Posts: 53
Joined: Sat Mar 18, 2023 12:45 am

Re: Ideas to how to generate lakes on a map

Post by tourgen »

Brogue is written in straight C. It's pretty well organized and easy to read. If I remember correctly all of the dungeon generation happens in single C file. Take a look.
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Ideas to how to generate lakes on a map

Post by Gunroar:Cannon() »

tourgen wrote: Wed May 17, 2023 2:55 pm Brogue is written in straight C. It's pretty well organized and easy to read. If I remember correctly all of the dungeon generation happens in single C file. Take a look.
Yeah, I've looked at the code. (And wish it had a moveable setup to load new creatures and stuff from json files because it really does have that setup in the way it loads monsters, but that's besides the point :P)

The map gen code was kinda confusing for me
Here's a sample

Code: Select all

void liquidType(short *deep, short *shallow, short *shallowWidth) {
    short randMin, randMax, rand;

    randMin = (rogue.depthLevel < MINIMUM_LAVA_LEVEL ? 1 : 0);
    randMax = (rogue.depthLevel < MINIMUM_BRIMSTONE_LEVEL ? 2 : 3);
    rand = rand_range(randMin, randMax);
    if (rogue.depthLevel == DEEPEST_LEVEL) {
        rand = 1;
    }

    switch(rand) {
        case 0:
            *deep = LAVA;
            *shallow = NOTHING;
            *shallowWidth = 0;
            break;
        case 1:
            *deep = DEEP_WATER;
            *shallow = SHALLOW_WATER;
            *shallowWidth = 2;
            break;
        case 2:
            *deep = CHASM;
            *shallow = CHASM_EDGE;
            *shallowWidth = 1;
            break;
        case 3:
            *deep = INERT_BRIMSTONE;
            *shallow = OBSIDIAN;
            *shallowWidth = 2;
            break;
    }
}

// Fills a lake marked in unfilledLakeMap with the specified liquid type, scanning outward to reach other lakes within scanWidth.
// Any wreath of shallow liquid must be done elsewhere.
void fillLake(short x, short y, short liquid, short scanWidth, char wreathMap[DCOLS][DROWS], short **unfilledLakeMap) {
    short i, j;

    for (i = x - scanWidth; i <= x + scanWidth; i++) {
        for (j = y - scanWidth; j <= y + scanWidth; j++) {
            if (coordinatesAreInMap(i, j) && unfilledLakeMap[i][j]) {
                unfilledLakeMap[i][j] = false;
                pmap[i][j].layers[LIQUID] = liquid;
                wreathMap[i][j] = 1;
                fillLake(i, j, liquid, scanWidth, wreathMap, unfilledLakeMap);  // recursive
            }
        }
    }
}

void lakeFloodFill(short x, short y, short **floodMap, short **grid, short **lakeMap, short dungeonToGridX, short dungeonToGridY) {
    short newX, newY;
    enum directions dir;

    floodMap[x][y] = true;
    for (dir=0; dir<4; dir++) {
        newX = x + nbDirs[dir][0];
        newY = y + nbDirs[dir][1];
        if (coordinatesAreInMap(newX, newY)
            && !floodMap[newX][newY]
            && (!cellHasTerrainFlag(newX, newY, T_PATHING_BLOCKER) || cellHasTMFlag(newX, newY, TM_CONNECTS_LEVEL))
            && !lakeMap[newX][newY]
            && (!coordinatesAreInMap(newX+dungeonToGridX, newY+dungeonToGridY) || !grid[newX+dungeonToGridX][newY+dungeonToGridY])) {

            lakeFloodFill(newX, newY, floodMap, grid, lakeMap, dungeonToGridX, dungeonToGridY);
        }
    }
}

boolean lakeDisruptsPassability(short **grid, short **lakeMap, short dungeonToGridX, short dungeonToGridY) {
    boolean result;
    short i, j, x, y;
    short **floodMap;

    floodMap = allocGrid();
    fillGrid(floodMap, 0);
    x = y = -1;
    // Get starting location for the fill.
    for (i=0; i<DCOLS && x == -1; i++) {
        for (j=0; j<DROWS && x == -1; j++) {
            if (!cellHasTerrainFlag(i, j, T_PATHING_BLOCKER)
                && !lakeMap[i][j]
                && (!coordinatesAreInMap(i+dungeonToGridX, j+dungeonToGridY) || !grid[i+dungeonToGridX][j+dungeonToGridY])) {

                x = i;
                y = j;
            }
        }
    }
    brogueAssert(x != -1);
    // Do the flood fill.
    lakeFloodFill(x, y, floodMap, grid, lakeMap, dungeonToGridX, dungeonToGridY);

    // See if any dry tiles weren't reached by the flood fill.
    result = false;
    for (i=0; i<DCOLS && result == false; i++) {
        for (j=0; j<DROWS && result == false; j++) {
            if (!cellHasTerrainFlag(i, j, T_PATHING_BLOCKER)
                && !lakeMap[i][j]
                && !floodMap[i][j]
                && (!coordinatesAreInMap(i+dungeonToGridX, j+dungeonToGridY) || !grid[i+dungeonToGridX][j+dungeonToGridY])) {

//                if (D_INSPECT_LEVELGEN) {
//                    dumpLevelToScreen();
//                    hiliteGrid(lakeMap, &darkBlue, 75);
//                    hiliteGrid(floodMap, &white, 20);
//                    plotCharWithColor('X', mapToWindowX(i), mapToWindowY(j), &black, &red);
//                    temporaryMessage("Failed here.", REQUIRE_ACKNOWLEDGMENT);
//                }

                result = true;
            }
        }
    }

    freeGrid(floodMap);
    return result;
}

void designLakes(short **lakeMap) {
    short i, j, k;
    short x, y;
    short lakeMaxHeight, lakeMaxWidth;
    short lakeX, lakeY, lakeWidth, lakeHeight;

    short **grid; // Holds the current lake.

    grid = allocGrid();
    fillGrid(lakeMap, 0);
    for (lakeMaxHeight = 15, lakeMaxWidth = 30; lakeMaxHeight >=10; lakeMaxHeight--, lakeMaxWidth -= 2) { // lake generations

        fillGrid(grid, 0);
        createBlobOnGrid(grid, &lakeX, &lakeY, &lakeWidth, &lakeHeight, 5, 4, 4, lakeMaxWidth, lakeMaxHeight, 55, "ffffftttt", "ffffttttt");

//        if (D_INSPECT_LEVELGEN) {
//            colorOverDungeon(&darkGray);
//            hiliteGrid(grid, &white, 100);
//            temporaryMessage("Generated a lake.", REQUIRE_ACKNOWLEDGMENT);
//        }

        for (k=0; k<20; k++) { // placement attempts
            // propose a position for the top-left of the grid in the dungeon
            x = rand_range(1 - lakeX, DCOLS - lakeWidth - lakeX - 2);
            y = rand_range(1 - lakeY, DROWS - lakeHeight - lakeY - 2);

            if (!lakeDisruptsPassability(grid, lakeMap, -x, -y)) { // level with lake is completely connected
                //printf("Placed a lake!");

                // copy in lake
                for (i = 0; i < lakeWidth; i++) {
                    for (j = 0; j < lakeHeight; j++) {
                        if (grid[i + lakeX][j + lakeY]) {
                            lakeMap[i + lakeX + x][j + lakeY + y] = true;
                            pmap[i + lakeX + x][j + lakeY + y].layers[DUNGEON] = FLOOR;
                        }
                    }
                }

                if (D_INSPECT_LEVELGEN) {
                    dumpLevelToScreen();
                    hiliteGrid(lakeMap, &white, 50);
                    temporaryMessage("Added a lake location.", REQUIRE_ACKNOWLEDGMENT);
                }
                break;
            }
        }
    }
    freeGrid(grid);
}

void createWreath(short shallowLiquid, short wreathWidth, char wreathMap[DCOLS][DROWS]) {
    short i, j, k, l;
    for (i=0; i<DCOLS; i++) {
        for (j=0; j<DROWS; j++) {
            if (wreathMap[i][j]) {
                for (k = i-wreathWidth; k<= i+wreathWidth; k++) {
                    for (l = j-wreathWidth; l <= j+wreathWidth; l++) {
                        if (coordinatesAreInMap(k, l) && pmap[k][l].layers[LIQUID] == NOTHING
                            && (i-k)*(i-k) + (j-l)*(j-l) <= wreathWidth*wreathWidth) {
                            pmap[k][l].layers[LIQUID] = shallowLiquid;
                            if (pmap[k][l].layers[DUNGEON] == DOOR) {
                                pmap[k][l].layers[DUNGEON] = FLOOR;
                            }
                        }
                    }
                }
            }
        }
    }
}

void fillLakes(short **lakeMap) {
    short deepLiquid = CRYSTAL_WALL, shallowLiquid = CRYSTAL_WALL, shallowLiquidWidth = 0;
    char wreathMap[DCOLS][DROWS];
    short i, j;

    for (i=0; i<DCOLS; i++) {
        for (j=0; j<DROWS; j++) {
            if (lakeMap[i][j]) {
                liquidType(&deepLiquid, &shallowLiquid, &shallowLiquidWidth);
                zeroOutGrid(wreathMap);
                fillLake(i, j, deepLiquid, 4, wreathMap, lakeMap);
                createWreath(shallowLiquid, shallowLiquidWidth, wreathMap);

                if (D_INSPECT_LEVELGEN) {
                    dumpLevelToScreen();
                    hiliteGrid(lakeMap, &white, 75);
                    temporaryMessage("Lake filled.", REQUIRE_ACKNOWLEDGMENT);
                }
            }
        }
    }
}
To understand the code completely I think one needs to understand the whole project, though I guess I can make sense out of some of it.
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
darkfrei
Party member
Posts: 1169
Joined: Sat Feb 08, 2020 11:09 pm

Re: Ideas to how to generate lakes on a map

Post by darkfrei »

Cellular automaton day-night after 200 iterations makes good results for lakes, mountains, forests etc.
https://en.wikipedia.org/wiki/Day_and_N ... automaton)
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
tourgen
Citizen
Posts: 53
Joined: Sat Mar 18, 2023 12:45 am

Re: Ideas to how to generate lakes on a map

Post by tourgen »

Gunroar:Cannon() wrote: Wed May 17, 2023 3:51 pm Yeah, I've looked at the code. (And wish it had a moveable setup to load new creatures and stuff from json files because it really does have that setup in the way it loads monsters, but that's besides the point :P)

The map gen code was kinda confusing for me

To understand the code completely I think one needs to understand the whole project, though I guess I can make sense out of some of it.
I think the author gave a talk about his level generation method somewhere on youtube at a conference. was it already posted here? I didn't check.

If I remember, he brute-forced it. He tried a random lake area added as a 'glob' area and then checked for reach-ability for each room on the floor. keep trying until something works. I'm probably completely wrong.

apologies if it was already posted:
https://www.youtube.com/watch?v=Uo9-IcHhq_w

this wiki has a section on lakes and Brogue level generation:
https://brogue.fandom.com/wiki/Level_Generation

There's an old interview and it has a paragraph about how he generated lakes in Brogue:
"Then we move onto lakes. Lakes are masses of a particular terrain type -- water, lava, chasm or brimstone -- that can span almost the entire level. They’re atmospheric, they enable long-distance attacks, and they impose structure on the level at a large scale to prevent it from feeling like a homogenous maze of twisty passages. We pull out the cellophane and draw a lake on it using the cellular automata method, and then we slide the cellophane around to random locations until we find a place that works -- where all of the passable parts of the level that aren’t covered by lake are still fully connected, so the player is never required to cross the lake. If twenty random tries fails to find a qualifying location, we draw a smaller lake and try again. If we can find a qualifying location, we drop the lake onto the map there and overwrite the terrain underneath it. Some lakes have wreaths -- shallow water surrounds deep water, and “chasm edge” terrain surrounds chasms -- and we draw that in at this stage."

Best of luck and Godspeed! I love rogue games.
Post Reply

Who is online

Users browsing this forum: Google [Bot], 麻猫和黄猫 and 51 guests