Map Generation Algorithm

ID:145829
 
Nov 28 2005, 9:29 pm
Code:
proc/GenMap(var/x,var/y,var/z,var/floortype,var/walltype,var/iterations)
    GenRect(rand(-10,-5)+x,rand(-10,-5)+y,rand(10,5)+x,rand(10,5)+y,z,floortype)
    var/list/turf/posswalls=FindValidWalls(z,walltype,floortype)
    var/xsize
    var/ysize
    var/turf/t
    var/x1
    var/y1
    var/x2
    var/y2
    var/n
    for(var/i=1 to iterations)
        n=0
        while(!n)
            t=pick(posswalls)
            xsize=rand(1,10)
            ysize=rand(1,10)

            switch(rand(1,4))
                if(1)
                    x1=t.x-0.5*xsize
                    x2=t.x+0.5*xsize
                    y1=t.y+1
                    y2=t.y+1+ysize

                if(2)
                    x1=t.x-0.5*xsize
                    x2=t.x+0.5*xsize
                    y1=t.y-1
                    y2=t.y-1-ysize

                if(3)
                    x1=t.x+1
                    x2=t.x+1+xsize
                    y1=t.y-0.5*ysize
                    y2=t.y+0.5*ysize

                if(4)
                    x1=t.x-1
                    x2=t.x-1-xsize
                    y1=t.y-0.5*ysize
                    y2=t.y+0.5*ysize
            if(IsValidRect(x1,y1,x2,y2,z,walltype)) n=1
        GenRect(x1,y1,x2,y2,z,floortype)
        new floortype (locate(t.x,t.y,z))
        posswalls=FindValidWalls(z,walltype,floortype)

proc/GenRect(var/x1,var/y1,var/x2,var/y2,var/z,var/type)
    for(var/turf/t in block(locate(x1,y1,z),locate(x2,y2,z))) new type(t)

proc/FindValidWalls(var/z,var/floortype,var/walltype)
    var/list/results=list()
    for(var/turf/t in block(locate(1,1,z),locate(world.maxx,world.maxy,z))) if(t.type==walltype) for(var/turf/t2 in range(t,1))    if(t2.type==floortype)
        results+=t
        break
    return results

proc/IsValidRect(var/x1,var/y1,var/x2,var/y2,var/z,var/walltype)
    if((x1<1||x2<1||y1<1||y2<1)||(x1>world.maxx||x2>world.maxx||y1>world.maxy||y2>world.maxy)) return 0
    for(var/turf/t in block(locate(x1,y1,z),locate(x2,y2,z))) if(t.type!=walltype) return 0
    else return 1


Problem description:
Okay, I haven't tested that, but as far as I know it works.

My problem is thus: How do I make that more elegant? It's an ugly, ugly algorithm currently. I'll run through what it's supposed to do:

1 - Generate a room on the centre of the Z-level being created.
2 - Find every wall with a floor square next to it.
3 - Pick one of those walls at random.
4 - Pick a feature at random
5 - Check if there's enough space to generate 'feature' at 'wall'
6 - If yes, generate the feature and go to 2
7 - If no, go to 2.
8 - Repeat until bored.

A secondary problem - What would be a good way to encode a room layout so that I can have non-rectangle features? It would be fairly easy to write a proc to draw hexagons, crosses, etc., but surely there's a way of defining a sort of 'room mask' of turfs to draw. The only thing I can come up with is a multidimensional list, but that's going to be very, very ugly.
Nov 29 2005, 10:47 am
For the procedure as a whole, have multiple z levels on the map file. Every z level with have a shape that you will use for a template except for one blank, if all you need is one blank map. These shapes will be drawn out with a special sort of turf. Then, loop through every "special turf" and place an object corresponding to their location on the blank z level. For less use of if() procs, make an associative list that describe their level.
var/list/Maps=list("Square"=2,"Hexagon"=3)
var/shape=pick("Square","Hexagon")
for(var/turf/special/T in world)
    if(z.level=Maps[shape])

Something like that, I dunno.

Or, you can just place objects directly on the template maps and delete them after you are done using them.

Just friendly ideas.
Nov 29 2005, 2:53 pm
In response to CaptFalcon33035
Ooo... I never thought of that. A slightly less turf-using system might use Lummox's SwapMaps - It cures the common cold!

I'll try something like that. Thanks.
Nov 29 2005, 3:14 pm
In response to Jp
ive got an idea, not that great, but test it cuz im too lazy.

Basically, do this, make a multiple lists or sumthing, i don't care, but make a grid of random numbers depending on how many turfs you have and you can go into numbers and the such. Basically, the code could match the numbers and letters and so forth with corresponding turfs, thus making a map generating thingamajig. Just spewing out suggestions. Well, example below.

11111111111111
10000000000001
10000000000001
10000000000001
10000000000001
11111111111111

and if 1 equals a land turf, and 0 equals a water turf? what do you get? a weird ffed up map. If you use it, just remember to set the map size, and do a little spiffing so the map isn..'t ffed up.
Nov 29 2005, 3:34 pm
In response to Lou
I've thought of using multidimensional lists to represent turfs in a feature already, and rejected it on the groundof extreme ugliness.
Nov 29 2005, 4:00 pm
In response to Jp
Uh huh, but see, let me go further in depth with that map generating feature.

OK...you see, while normally, it would make a patchmark piece of crap reminiscent of a recently bombed ditch, with random patches of water, incomplete roads, and so on, but taking stuff out of Capt Falcons idea, maybe you could try different lists for different features of the map like split it into basic landscape, buildings, and so forth. note: loop through land to see how many ones there are (do that search thing with the lists) and THEN you go ahead and subtract that from area of block, and voila, the ratio, but do this BEFORE the mapping of the landscape and be sure to set a variable controlling the ratios. e.g.

11111110000
11111000000
11111111000
11000000000
11100000000

1=land 0=water (ratio here is 5/11 which is land/water)

and THEN you have another map that has...say the roads

222
2
222

You'd just overlay the second over the first. and it'd then be...

22211110000
11211000000
22211111000
10000000000
11100000000

With buildings and such, you would have to implement, "blocks" of preset buildings that would simply overlay the landscape, but the tricky thing about this and the roads is that you have to "pathfind" with an if() statement to first see if it is on land turf (use the hierarchy thing to do this, e.g /turf/land and /turf/water) and then you'd have to
set settings to see if its to close to the edge, or its on top of something else with a bunch of crap.

Now specifics on roads, you gotta pathfind for sure, but you also have to make sure it LOOKs like a road, and not a checkerboard gone wrong. Ways to do this are...

1. Tracer object designed to go ontop of landscape and "search around" for a path to make.

2. Map preset path onto map through txt template.

Oh! Finally, for the borders of all that crap? Loop around objects and find the surrounding 8 blocks around each turf. Depending on how it turns out, you can determine which state to use. E.g.

111
120
000

by seing that 2 (same turf as a 1) is surounded on the west, sw, s, and se parts by water, its gonna be shaped like a..
reflected L
Nov 29 2005, 4:04 pm
In response to Lou
1 - You didn't read my original post. It doesn't just randomly place turfs down - Read the actual algorithm

2 - It generates dungeons, not aboveground areas.

3 - I have already rejected multidimensional lists for representing turfs in a feature.
Nov 29 2005, 4:50 pm
In response to Jp
I'm sorry if that wasn't what you wanted, but I am only trying to help.

Well, an answer to your whatever, i did read your post, i just suggested an alternative. Yes I see that it makes rectangular rooms. I just suggested another way to make maps, it could easily be suited to make a dungeon, simply make the list generate random numbers from 1-5 or sumthing, and make a fake "gravitational" attraction for floortiles to the numbers with...say a 5, and smaller rooms for 4 and so on, with nothing for 1 and 2.

1. Now bout that z level thing, why don't you just find then center of the place, and use your already present box making...algorithmy thing.

2. Simply loop through the walls and see if the surrounding area has any floors. e.g.

(for /turf/floor/F in orange(1,src))
//blah blah...

3.
var/list/feature["Door","KeyDoor"]

and

(pick(feature)

The stuff after that I really don't get, cuz wouldn't the feature be on the wall?
Nov 29 2005, 4:55 pm (Edited on Nov 29 2005, 5:26 pm)
In response to Lou
It works, but the code is ugly. That's one problem.

A secondary problem is finding an elegant way of representing features.

In response to 2, I'm trying to construct it so that it doesn't 'know' what type floors and walls are, but gets passed them. Hence the floortype and walltype arguments. That precludes me looping through all 'floor' turfs, because I don't know what type they are.

The problem isn't randomly selecting the feature, it's finding an elegant way of representing features. I need to have a data construct that tells the program what types of turf and what locations they should be placed in.

I'm going to test the current version right now, just to make sure it works. I'll be back later.

EDIT:
It works, but it just makes rectangles. I made a few mistakes in the original code - Here's the new version:

proc/GenMap(var/x,var/y,var/z,var/floortype,var/walltype,var/iterations)
    GenRect(rand(-5,-2)+x,rand(-5,-2)+y,rand(5,2)+x,rand(5,2)+y,z,floortype)
    var/list/turf/posswalls=FindValidWalls(z,walltype,floortype)
    var/xsize
    var/ysize
    var/turf/t
    var/x1
    var/y1
    var/x2
    var/y2
    var/n
    var/cx
    var/cy
    var/xpat=0
    var/ypat=0
    for(var/i=1 to iterations)
        xpat=0
        ypat=0
        n=0
        while(!n)
            t=pick(posswalls)
            xsize=rand(1,5)
            ysize=rand(1,5)
            switch(rand(1,4))
                if(1)
                    x1=t.x-0.5*xsize
                    x2=t.x+0.5*xsize
                    y1=t.y+2
                    y2=t.y+2+ysize
                    cx=t.x
                    cy=t.y+1
                    xpat=1
                    ypat=1

                if(2)
                    x1=t.x-0.5*xsize
                    x2=t.x+0.5*xsize
                    y1=t.y-2
                    y2=t.y-2-ysize
                    cx=t.x
                    cy=t.y-1
                    xpat=1
                    ypat=-1

                if(3)
                    x1=t.x+2
                    x2=t.x+2+xsize
                    y1=t.y-0.5*ysize
                    y2=t.y+0.5*ysize
                    cx=t.x+1
                    cy=t.y
                    xpat=1
                    ypat=1
                if(4)
                    x1=t.x-2
                    x2=t.x-2-xsize
                    y1=t.y-0.5*ysize
                    y2=t.y+0.5*ysize
                    cx=t.x-1
                    cy=t.y
                    xpat=-1
                    ypat=1
            x1=round(x1)
            x2=round(x2)
            y1=round(y1)
            y2=round(y2)
            if(IsValidRect(x1-xpat,y1-ypat,x2+xpat,y2+ypat,z,walltype)) n=1
        GenRect(x1,y1,x2,y2,z,floortype)
        new floortype (locate(cx,cy,z))
        posswalls=FindValidWalls(z,walltype,floortype)

proc/GenRect(var/x1,var/y1,var/x2,var/y2,var/z,var/type)
    for(var/turf/t in block(locate(x1,y1,z),locate(x2,y2,z))) new type(t)

proc/FindValidWalls(var/z,var/floortype,var/walltype)
    var/list/results=list()
    for(var/turf/t in block(locate(1,1,z),locate(world.maxx,world.maxy,z))) if(t.type==walltype) for(var/turf/t2 in range(t,1))    if(t2.type==floortype)
        results+=t
        break
    return results

proc/IsValidRect(var/x1,var/y1,var/x2,var/y2,var/z,var/walltype)
    if((x1<1||x2<1||y1<1||y2<1)||(x1>world.maxx||x2>world.maxx||y1>world.maxy||y2>world.maxy)) return 0
    for(var/turf/t in block(locate(x1,y1,z),locate(x2,y2,z))) if(t.type!=walltype) return 0
    return 1
Nov 29 2005, 5:54 pm
You don't need a multidimensional list for anything here. A simple list will do just nicely if all it holds are turfs. You could even use areas for that; add turfs for your shape to the area.contents, then build new turfs one by one.

Lummox JR
Nov 30 2005, 3:18 am
Jp wrote:
A secondary problem - What would be a good way to encode a room layout so that I can have non-rectangle features? It would be fairly easy to write a proc to draw hexagons, crosses, etc., but surely there's a way of defining a sort of 'room mask' of turfs to draw. The only thing I can come up with is a multidimensional list, but that's going to be very, very ugly.

I use a special datum for rooms in my sd_MapSuite library (not released yet.) The room simply stores a list of turfs that are within it, and doesn't even fill in those turfs unless you instruct it too.
sd_MapRoom
    var
        x
        y
        z
        width
        height
        list
            turfs = list()

    New(X,Y=1,Z=1,Width=1,Height=1)
        /* may be created as new(atom_at_low_left, width, height
            or new(x_left_side, y_bottom_side, z, width, height) */
        ..()
        if(istype(X,/atom))
            var/atom/A = X
            x = A.x
            y = A.y
            z = A.z
            width = Y
            height = Z
        else
            x = X
            y = Y
            z = Z
            width = Width
            height = Height

    proc
        Turfs()
            /* generates & returns list of all turfs in room.
                Override for different shapes. */
            turfs = block(locate(x,y,z),locate(x+width-1,y+height-1,z))
            return turfs

        Fill(turftype)
            /* Fill room with the specified turf type.
                Will automatically call Turfs() if needed. */
            if(!turfs) Turfs()
            for(var/turf/T in turfs)
                new turftype(T)
            return turfs

        Border(Dirs = 15)
            /* returns a list of turfs adjacent to the room
                Dirs    - filter of directions to check.
                            for example Dirs = EAST will return turfs
                            that border east side of the room
                            The default Dirs or 15 will get borders on all sides.
            */
            var/list/border
            for(var/turf/T in turfs)
                var
                    dir = 1
                    turf/T2
                for(var/X in 1 to 4)
                    if(dir&Dirs)
                        T2 = get_step(T,dir)
                        if(!(T2 in turfs))
                            border -= T2
                            border += T2
                        dir = dir << 1
            return border


You may define different shaped rooms as children of the room datum and override Turfs() to give the appropriate shape.
sd_MapRoom/oval
    Turfs()
        var
            a = width/2      // x radius
            b = height/2 // y radius
            h = x + a - 0.5    // center x
            k = y + b - 0.5    // center y
            s
            X
            Y

        for(X = 0 to a)
            s = X/a
            Y = abs(b * sqrt(1 - (s*s)))
            turfs += block(locate(h+X, k-Y, z),locate(h+X, k+Y, z))
            if(X) turfs += block(locate(h-X, k-Y, z),locate(h-X, k+Y, z))

        return turfs

sd_MapRoom/IsoTriangle  // isometric triangle
    var
        dir

    Turfs()
        var
            a = width/2      // x radius
            b = height
            h = x + a - 0.5    // center x
            k = y
            X
            Y
        if(!dir) dir = rand(1,4)
        if(dir<3)
            a = width
            b = height / 2
            h = x
            k = y + b - 0.5
        for(X = 0 to a)
            Y = abs(b * (1 - X/a))
            switch(dir)
                if(1)    // right
                    turfs += block(locate(x+X, k+Y, z),locate(x+X, k-Y, z))
                if(2)    // left
                    turfs += block(locate(x+width-X, k+Y, z),locate(x+width-X, k-Y, z))
                if(3)    // up
                    turfs += block(locate(h+X, y, z),locate(h+X, y+Y, z))
                    if(X) turfs += block(locate(h-X, y, z),locate(h-X, y+Y, z))
                else    // down
                    turfs += block(locate(h+X, y+height-Y, z),locate(h+X, y+height, z))
                    if(X) turfs += block(locate(h-X, y+height-Y, z),locate(h-X, y+height, z))

        return turfs


Yes, the default Border() proc is somewhat inefficient for rectangular rooms, but it will work for any shaped room. If you want a more efficient Border() routine for specific shapes, you can override it as well.
Nov 30 2005, 2:28 pm
In response to Lummox JR
That will maintain their locations relative to each other? I suppose I could give turfs two seperate 'mx' and 'my' variables that store where they should be placed, but then specifying the shape of a particular feature requires messing around with it's New() proc, and gets ugly.