• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

Dungeon Generator & Stamp

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Dungeon_Generator.jpg cave.jpg dungeon.jpg

After almost two days of non-stop working on this, I finally finished my masterpiece.


This baby allows generating complete dungeons and cave designs directly by RNG.
For dungeons, it applies a pattern of rooms and connects them with corridors; caves on the other hand are generated by using cellular automata, to create a natural looking flow.

Check the sketch below for an example of how such a generated pattern will look like.

MixedLowDensity.jpg

And to see how this could look ingame, of course check out the demomap for examples of what is possible with this baby. :)


I will add a tutorial tomorrow, for those interested.

JASS:
library DungeonStamp uses Ascii

globals
    //=========================================
    //configurables

    private constant integer TERRAIN_DEFAULT_TILE = 'Ddrt'        //defines the default ground tile for the dungeon
    private constant integer TERRAIN_DEFAULT_VARIANCE = 17        //defines the variation used for the default tile (use -1 for random)
    private constant integer STAMP_SIZE = 5                       //defines the edge size of each stamp; must be an odd number
    private constant integer STAMP_SIZE_SQUARED = 25              //please calculate STAMP_SIZE*STAMP_SIZE and enter the value here
                                                                  //limit:
                                                                  //    -> n * STAMP_SIZE_SQUARED < 8192
                                                                  //    -> for n = number of registered stamps
                                                                  //    -> print registry methods only supported for stamp size of 5
                                                                  //    -> for other sizes use rect registry method instead
                                                            
    private constant integer MAX_DESTRUCTABLES_PER_STAMP = 25     //defines the maximum number of destructables per stamp
                                                                  //limit:
                                                                  //    -> n * MAX_DESTRUCTABLES_PER_STAMP < 8192
                                                                  //    -> for n = number of registered stamps
                                                                  //    -> print registry methods only supported for MAX_DESTRUCTABLES_PER_STAMP = 25
                                                                  //    -> for other values use rect registry method instead
    constant string DUNGEON_PRINT_DIRECTORY = ".\\save\\"         //This is the directory where all generated text files from the print commands will be saved.

    //=========================================


    //=========================================
    constant integer STAMP_SIZE_REAL = STAMP_SIZE*128
    constant integer ORIENTATION_0 = 0
    constant integer ORIENTATION_90 = 200
    constant integer ORIENTATION_180 = 400
    constant integer ORIENTATION_270 = 600

    private constant hashtable HASH = InitHashtable()
    private constant integer CAVE_OFFSET = 20
    private constant integer STAIR_UP_OFFSET = 40
    private constant integer STAIR_DOWN_OFFSET = 80

    /*
        These are the stamp shapes for the dungeon type
    */
    constant integer SHAPE_BLACK = 0
    constant integer SHAPE_HALL = 1                 //  Default Orientation:
    constant integer SHAPE_WALL_L = 2               //              I       = 0°    (left wall)
    constant integer SHAPE_WALL_L_B = 3             //              I_      = 0°    (left wall and bottom wall)
    constant integer SHAPE_WALL_L_B_R = 4           //              I_I     = 0°    (left wall, bottom wall and right wall (dead end))
    constant integer SHAPE_WALL_BL = 5              //              .       = 0°    (wall in bottom left corner)
    constant integer SHAPE_WALL_BL_TL = 6           //              :       = 0°    (wall in bottom left and top left corner)
    constant integer SHAPE_WALL_BL_TR = 7           //              . '     = 0°    (wall in bottom left and top right corner)
    constant integer SHAPE_WALL_BL_TL_BR = 8        //              : .     = 0°    (wall in bottom left, top left and bottom right corner)
    constant integer SHAPE_WALL_BL_TL_BR_TP = 9     //              : :     = 0°    (wall in all corners, plus-shaped corridor)
    constant integer SHAPE_WALL_L_BR = 10           //              I .     = 0°    (left wall and bottom right corner)
    constant integer SHAPE_WALL_L_TR = 11           //              I '     = 0°    (left wall and top right corner)
    constant integer SHAPE_WALL_L_R = 12            //              I I     = 0°    (left wall and right wall)
    constant integer SHAPE_WALL_L_B_TR = 13         //              I_'     = 0°    (left wall, bottom wall, top-right corner)
    constant integer SHAPE_WALL_L_BR_TR = 14        //              I :     = 0°    (left wall, bottom-right corner and top-right corner)

    constant integer SHAPE_STAIRS_UP_WALL = SHAPE_WALL_L + STAIR_UP_OFFSET
                                                            //              I>      = 0°    (Stairs in western wall, poiting east)
    constant integer SHAPE_STAIRS_UP_HALL = SHAPE_HALL + STAIR_UP_OFFSET
                                                            //              >       = 0°    (Stairs inside room, pointing east)
    constant integer SHAPE_STAIRS_UP_END  = SHAPE_WALL_L_B_R + STAIR_UP_OFFSET
                                                            //              I^I     = 0°    (Stairs at dead end, pointing north)

    constant integer SHAPE_STAIRS_DOWN_WALL = SHAPE_WALL_L + STAIR_DOWN_OFFSET
                                                            //              I>      = 0°    (Stairs in western wall, poiting east)
    constant integer SHAPE_STAIRS_DOWN_HALL = SHAPE_HALL + STAIR_DOWN_OFFSET
                                                            //              >       = 0°    (Stairs inside room, pointing east)
    constant integer SHAPE_STAIRS_DOWN_END  = SHAPE_WALL_L_B_R + STAIR_DOWN_OFFSET
                                                            //              I^I     = 0°    (Stairs at dead end, pointing north)

    /*
        These are the stamp shapes for the cavern type
    */
    constant integer SHAPE_CAVE_HALL = 1+CAVE_OFFSET                 //  Default Orientation:
    constant integer SHAPE_CAVE_WALL_L = 2+CAVE_OFFSET               //              I       = 0°    (left wall)
    constant integer SHAPE_CAVE_WALL_L_B = 3+CAVE_OFFSET             //              I_      = 0°    (left wall and bottom wall)
    constant integer SHAPE_CAVE_WALL_L_B_R = 4+CAVE_OFFSET           //              I_I     = 0°    (left wall, bottom wall and right wall (dead end))
    constant integer SHAPE_CAVE_WALL_BL = 5+CAVE_OFFSET              //              .       = 0°    (wall in bottom left corner)
    constant integer SHAPE_CAVE_WALL_BL_TL = 6+CAVE_OFFSET           //              :       = 0°    (wall in bottom left and top left corner)
    constant integer SHAPE_CAVE_WALL_BL_TR = 7+CAVE_OFFSET           //              . '     = 0°    (wall in bottom left and top right corner)
    constant integer SHAPE_CAVE_WALL_BL_TL_BR = 8+CAVE_OFFSET        //              : .     = 0°    (wall in bottom left, top left and bottom right corner)
    constant integer SHAPE_CAVE_WALL_BL_TL_BR_TP = 9+CAVE_OFFSET     //              : :     = 0°    (wall in all corners, plus-shaped corridor)
    constant integer SHAPE_CAVE_WALL_L_BR = 10+CAVE_OFFSET           //              I .     = 0°    (left wall and bottom right corner)
    constant integer SHAPE_CAVE_WALL_L_TR = 11+CAVE_OFFSET           //              I '     = 0°    (left wall and top right corner)
    constant integer SHAPE_CAVE_WALL_L_R = 12+CAVE_OFFSET            //              I I     = 0°    (left wall and right wall)
    constant integer SHAPE_CAVE_WALL_L_B_TR = 13+CAVE_OFFSET         //              I_'     = 0°    (left wall, bottom wall, top-right corner)
    constant integer SHAPE_CAVE_WALL_L_BR_TR = 14+CAVE_OFFSET        //              I :     = 0°    (left wall, bottom-right corner and top-right corner)

    constant integer SHAPE_CAVE_STAIRS_UP_WALL = SHAPE_WALL_L + STAIR_UP_OFFSET + CAVE_OFFSET
                                                            //              I>      = 0°    (Stairs in western wall, poiting east)
    constant integer SHAPE_CAVE_STAIRS_UP_HALL = SHAPE_HALL + STAIR_UP_OFFSET + CAVE_OFFSET
                                                            //              >       = 0°    (Stairs inside room, pointing east)
    constant integer SHAPE_CAVE_STAIRS_UP_END  = SHAPE_WALL_L_B_R + STAIR_UP_OFFSET + CAVE_OFFSET
                                                            //              I^I     = 0°    (Stairs at dead end, pointing north)

    constant integer SHAPE_CAVE_STAIRS_DOWN_WALL = SHAPE_WALL_L + STAIR_DOWN_OFFSET + CAVE_OFFSET
                                                            //              I>      = 0°    (Stairs in western wall, poiting east)
    constant integer SHAPE_CAVE_STAIRS_DOWN_HALL = SHAPE_HALL + STAIR_DOWN_OFFSET + CAVE_OFFSET
                                                            //              >       = 0°    (Stairs inside room, pointing east)
    constant integer SHAPE_CAVE_STAIRS_DOWN_END  = SHAPE_WALL_L_B_R + STAIR_DOWN_OFFSET + CAVE_OFFSET
                                                            //              I^I     = 0°    (Stairs at dead end, pointing north)
endglobals

struct stamp
    private integer shape
    private integer number
    private integer tile
    private real rare
    integer data
    real value

    integer array destraw[MAX_DESTRUCTABLES_PER_STAMP]
    real array destx[MAX_DESTRUCTABLES_PER_STAMP]
    real array desty[MAX_DESTRUCTABLES_PER_STAMP]
    real array destrot[MAX_DESTRUCTABLES_PER_STAMP]
    integer array terrain[STAMP_SIZE_SQUARED]
    integer array variation[STAMP_SIZE_SQUARED]

    private static thistype temp
    private static integer tempindex = 0
    private static real tempx = 0
    private static real tempy = 0

    static method create takes integer shp, integer tileset, real rarity, integer customdata, real customvalue returns thistype
        local thistype this = thistype.allocate()
        set this.shape = shp
        set this.tile = tileset
        set this.rare = rarity
        set this.data = customdata
        set this.value = customvalue
        set this.number = LoadInteger(HASH, this.shape, 0) + 1
        call SaveInteger(HASH, this.shape, 0, this.number)
        call SaveInteger(HASH, this.shape, this.number, this)
        return this
    endmethod

    static method setDestructableData takes integer raw, real scale, real z, boolean alive returns nothing
        call SaveReal(HASH, raw, 0, scale)
        call SaveReal(HASH, raw, 1, z)
        call SaveBoolean(HASH, raw, 2, alive)
    endmethod
    static method getDestructableScale takes integer raw returns real
        if HaveSavedReal(HASH, raw, 0) then
            return LoadReal(HASH, raw, 0)
        endif
        return 1.
    endmethod
    static method getDestructableZ takes integer raw returns real
        if HaveSavedReal(HASH, raw, 1) then
            return LoadReal(HASH, raw, 1)
        endif
        return 0.
    endmethod
    static method getDestructableAlive takes integer raw returns boolean
        if HaveSavedBoolean(HASH, raw, 2) then
            return LoadBoolean(HASH, raw, 2)
        endif
        return true
    endmethod
    method canHaveStairs takes nothing returns boolean
        local integer shp = ModuloInteger(this.shape, CAVE_OFFSET)
        return (shp == SHAPE_WALL_L or shp == SHAPE_WALL_L_B_R or shp == SHAPE_HALL)
    endmethod

    private static method removeSub takes nothing returns nothing
        call RemoveDestructable(GetEnumDestructable())
    endmethod
    static method remove takes rect area, integer gridX, integer gridY returns nothing
        local integer i = 0
        local integer j
        local real x = GetRectMinX(area)+gridX*STAMP_SIZE_REAL
        local real y = GetRectMinY(area)+gridY*STAMP_SIZE_REAL
        local rect r = Rect(x-16, y-16, x+16+STAMP_SIZE_REAL, y+16+STAMP_SIZE_REAL)
        loop
            exitwhen i >= STAMP_SIZE
            set j = 0
            loop
                exitwhen j >= STAMP_SIZE
                set x = GetRectMinX(area)+gridX*STAMP_SIZE_REAL+i*128
                set y = GetRectMinY(area)+gridY*STAMP_SIZE_REAL+j*128
                if x <= GetRectMaxX(area) and y <= GetRectMaxY(area) then
                    call SetTerrainType(x, y, TERRAIN_DEFAULT_TILE, TERRAIN_DEFAULT_VARIANCE, 1, 1)
                endif
                set j = j + 1
            endloop
            set i = i + 1
        endloop
        if GetRectMaxX(r) <= GetRectMaxX(area) and GetRectMaxY(r) <= GetRectMaxY(area) then
            call EnumDestructablesInRect(r, null, function thistype.removeSub)
        else
            call SetRect(r, GetRectMinX(r), GetRectMinY(r), GetRectMaxX(area), GetRectMaxY(area))
            call EnumDestructablesInRect(r, null, function thistype.removeSub)
        endif
        call RemoveRect(r)
        set r = null
    endmethod
    method place takes rect area, integer gridX, integer gridY, integer orientation returns nothing
        local integer i = 0
        local integer j
        local location loc = Location(0,0)
        local real x
        local real y
        local integer u
        local integer v
        call thistype.remove(area, gridX, gridY) //remove existing stamps
        //paint ground tiles
        if GetRectMinX(area)+gridX*STAMP_SIZE_REAL <= GetRectMaxX(area) and GetRectMinY(area)+gridY*STAMP_SIZE_REAL <= GetRectMaxY(area) then
            loop
                exitwhen i >= STAMP_SIZE
                set j = 0
                loop
                    exitwhen j >= STAMP_SIZE
                    set x = GetRectMinX(area)+gridX*STAMP_SIZE_REAL+i*128
                    set y = GetRectMinY(area)+gridY*STAMP_SIZE_REAL+j*128
                    if orientation == ORIENTATION_0 then
                        set u = i
                        set v = j
                    elseif orientation == ORIENTATION_90 then
                        set u = j
                        set v = STAMP_SIZE-1-i
                    elseif orientation == ORIENTATION_180 then
                        set u = STAMP_SIZE-1-i
                        set v = STAMP_SIZE-1-j
                    else
                        set u = STAMP_SIZE-1-j
                        set v = i
                    endif
                    call SetTerrainType(x, y, this.terrain[u*STAMP_SIZE+v], this.variation[u*STAMP_SIZE+v], 1, 1)
                    if i == (STAMP_SIZE-1) then
                        if this.terrain[u*STAMP_SIZE+v] != TERRAIN_DEFAULT_TILE and GetTerrainType(x+128, y) == TERRAIN_DEFAULT_TILE then
                            call SetTerrainType(x+128, y, this.terrain[u*STAMP_SIZE+v], this.variation[u*STAMP_SIZE+v], 1, 1)
                        endif
                    endif
                    if j == (STAMP_SIZE-1) then
                        if this.terrain[u*STAMP_SIZE+v] != TERRAIN_DEFAULT_TILE and GetTerrainType(x, y+128) == TERRAIN_DEFAULT_TILE then
                            call SetTerrainType(x, y+128, this.terrain[u*STAMP_SIZE+v], this.variation[u*STAMP_SIZE+v], 1, 1)
                        endif
                    endif
                    if u == (STAMP_SIZE-1) and j == (STAMP_SIZE-1) then
                        if this.terrain[u*STAMP_SIZE+v] != TERRAIN_DEFAULT_TILE and GetTerrainType(x+128, y+128) == TERRAIN_DEFAULT_TILE then
                            call SetTerrainType(x+128, y+128, this.terrain[u*STAMP_SIZE+v], this.variation[u*STAMP_SIZE+v], 1, 1)
                        endif
                    endif
                    set j = j + 1
                endloop
                set i = i + 1
            endloop
            //place destructables
            set i = 0
            loop
                exitwhen i >= MAX_DESTRUCTABLES_PER_STAMP
                if this.destraw[i] != 0 then
                    if orientation == ORIENTATION_0 then
                        call MoveLocation(loc, GetRectMinX(area)+gridX*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2+this.destx[i], GetRectMinY(area)+gridY*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2+this.desty[i])
                        if stamp.getDestructableAlive(this.destraw[i]) then
                            call CreateDestructableZ(this.destraw[i], GetLocationX(loc), GetLocationY(loc), GetLocationZ(loc)+stamp.getDestructableZ(this.destraw[i]), this.destrot[i], stamp.getDestructableScale(this.destraw[i]), 0)
                        else
                            call CreateDeadDestructableZ(this.destraw[i], GetLocationX(loc), GetLocationY(loc), GetLocationZ(loc)+stamp.getDestructableZ(this.destraw[i]), this.destrot[i], stamp.getDestructableScale(this.destraw[i]), 0)
                        endif
                    elseif orientation == ORIENTATION_90 then
                        call MoveLocation(loc, GetRectMinX(area)+gridX*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2-this.desty[i], GetRectMinY(area)+gridY*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2+this.destx[i])
                        if stamp.getDestructableAlive(this.destraw[i]) then
                            call CreateDestructableZ(this.destraw[i], GetLocationX(loc), GetLocationY(loc), GetLocationZ(loc)+stamp.getDestructableZ(this.destraw[i]), this.destrot[i]+90, stamp.getDestructableScale(this.destraw[i]), 0)
                        else
                            call CreateDeadDestructableZ(this.destraw[i], GetLocationX(loc), GetLocationY(loc), GetLocationZ(loc)+stamp.getDestructableZ(this.destraw[i]), this.destrot[i]+90, stamp.getDestructableScale(this.destraw[i]), 0)
                        endif
                    elseif orientation == ORIENTATION_180 then
                        call MoveLocation(loc, GetRectMinX(area)+gridX*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2-this.destx[i], GetRectMinY(area)+gridY*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2-this.desty[i])
                        if stamp.getDestructableAlive(this.destraw[i]) then
                            call CreateDestructableZ(this.destraw[i], GetLocationX(loc), GetLocationY(loc), GetLocationZ(loc)+stamp.getDestructableZ(this.destraw[i]), this.destrot[i]+180, stamp.getDestructableScale(this.destraw[i]), 0)
                        else
                            call CreateDeadDestructableZ(this.destraw[i], GetLocationX(loc), GetLocationY(loc), GetLocationZ(loc)+stamp.getDestructableZ(this.destraw[i]), this.destrot[i]+180, stamp.getDestructableScale(this.destraw[i]), 0)
                        endif
                    else
                        call MoveLocation(loc, GetRectMinX(area)+gridX*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2+this.desty[i], GetRectMinY(area)+gridY*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2-this.destx[i])
                        if stamp.getDestructableAlive(this.destraw[i]) then
                            call CreateDestructableZ(this.destraw[i], GetLocationX(loc), GetLocationY(loc), GetLocationZ(loc)+stamp.getDestructableZ(this.destraw[i]), this.destrot[i]+270, stamp.getDestructableScale(this.destraw[i]), 0)
                        else
                            call CreateDeadDestructableZ(this.destraw[i], GetLocationX(loc), GetLocationY(loc), GetLocationZ(loc)+stamp.getDestructableZ(this.destraw[i]), this.destrot[i]+270, stamp.getDestructableScale(this.destraw[i]), 0)
                        endif
                    endif
                endif
                set i = i + 1
            endloop
        endif
        call RemoveLocation(loc)
        set loc = null
    endmethod

    private static method getDest takes nothing returns boolean
        local destructable d = GetFilterDestructable()
        if thistype.tempindex < MAX_DESTRUCTABLES_PER_STAMP then
            set thistype.temp.destraw[thistype.tempindex] = GetDestructableTypeId(d)
            set thistype.temp.destx[thistype.tempindex] = GetDestructableX(d)-thistype.tempx
            set thistype.temp.desty[thistype.tempindex] = GetDestructableY(d)-thistype.tempy
            if GetDestructableLife(d) == GetDestructableMaxLife(d) then
                set thistype.temp.destrot[thistype.tempindex] = 0
            else
                set thistype.temp.destrot[thistype.tempindex] = ModuloReal(GetDestructableLife(d)/GetDestructableMaxLife(d)*1000, 360)
            endif
            set thistype.tempindex = thistype.tempindex + 1
        else
            call BJDebugMsg("ERROR: Stamp contains too many destructables! Increase MAX_DESTRUCTABLES_PER_STAMP or reduce number of destructables!")
        endif
        set d = null
        return false
    endmethod
    static method register takes rect which, integer shp, integer tileset, real rarity, integer customdata, real customvalue returns thistype
        local thistype this = thistype.create(shp, tileset, rarity, customdata, customvalue)
        local integer i = 0
        local integer j
        set thistype.temp = this
        set thistype.tempindex = 0
        set thistype.tempx = GetRectMinX(which)+STAMP_SIZE_REAL/2
        set thistype.tempy = GetRectMinY(which)+STAMP_SIZE_REAL/2
        call EnumDestructablesInRect(which, Condition(function thistype.getDest), null)
        loop
            exitwhen i >= STAMP_SIZE
            set j = 0
            loop
                exitwhen j >= STAMP_SIZE
                set this.terrain[i*STAMP_SIZE+j] = GetTerrainType(GetRectMinX(which)+i*128, GetRectMinY(which)+j*128)
                set this.variation[i*STAMP_SIZE+j] = GetTerrainVariance(GetRectMinX(which)+i*128, GetRectMinY(which)+j*128)
                set j = j + 1
            endloop
            set i = i + 1
        endloop
        return this
    endmethod

    static method placeByLogic takes rect area, integer x, integer y, boolean isCave, boolean isStairs, boolean isUp, integer fromTileset, boolean sw, boolean w, boolean nw, boolean s, boolean c, boolean n, boolean se, boolean e, boolean ne returns thistype
        local integer wc = 0
        local integer cc = 0
        local thistype this
        local thistype array valid
        local integer validcount = 0
        local integer i = 0
        local integer shp = -1
        local integer max = 0
        local integer orient = 0
        local integer stairs = 0
        if isStairs then
            if isUp then
                set stairs = STAIR_UP_OFFSET
            else
                set stairs = STAIR_DOWN_OFFSET
            endif
        endif
        if sw and not (s or w) then
            set cc = cc + 1
        endif
        if nw and not (n or w) then
            set cc = cc + 1
        endif
        if se and not (s or e)  then
            set cc = cc + 1
        endif
        if ne and not (n or e)  then
            set cc = cc + 1
        endif
        if w then
            set wc = wc + 1
        endif
        if s then
            set wc = wc + 1
        endif
        if n then
            set wc = wc + 1
        endif
        if e then
            set wc = wc + 1
        endif
  
        if c then
            set shp = SHAPE_BLACK + ORIENTATION_0
        else
            if wc == 0 then
                if cc == 0 then
                    set shp = SHAPE_HALL + GetRandomInt(0,3)*ORIENTATION_90 + stairs
                elseif cc == 1 then
                    if sw then
                        set shp = SHAPE_WALL_BL + ORIENTATION_0
                    elseif se then
                        set shp = SHAPE_WALL_BL + ORIENTATION_90
                    elseif ne then
                        set shp = SHAPE_WALL_BL + ORIENTATION_180
                    elseif nw then
                        set shp = SHAPE_WALL_BL + ORIENTATION_270
                    endif
                elseif cc == 2 then
                    if sw and nw then
                        set shp = SHAPE_WALL_BL_TL + ORIENTATION_0
                    elseif sw and se then
                        set shp = SHAPE_WALL_BL_TL + ORIENTATION_90
                    elseif se and ne then
                        set shp = SHAPE_WALL_BL_TL + ORIENTATION_180
                    elseif ne and nw then
                        set shp = SHAPE_WALL_BL_TL + ORIENTATION_270
                    elseif sw and ne then
                        set shp = SHAPE_WALL_BL_TR + (GetRandomInt(0,1)*2)*ORIENTATION_90
                    elseif se and nw then
                        set shp = SHAPE_WALL_BL_TR + (GetRandomInt(0,1)*2+1)*ORIENTATION_90
                    endif
                elseif cc == 3 then
                    if not ne then
                        set shp = SHAPE_WALL_BL_TL_BR + ORIENTATION_0
                    elseif not nw then
                        set shp = SHAPE_WALL_BL_TL_BR + ORIENTATION_90
                    elseif not sw then
                        set shp = SHAPE_WALL_BL_TL_BR + ORIENTATION_180
                    elseif not se then
                        set shp = SHAPE_WALL_BL_TL_BR + ORIENTATION_270
                    endif
                elseif cc == 4 then
                    set shp = SHAPE_WALL_BL_TL_BR_TP + GetRandomInt(0,3)*ORIENTATION_90
                endif
            elseif wc == 1 then
                if cc == 0 then
                    if w then
                        set shp = SHAPE_WALL_L + ORIENTATION_0 + stairs
                    elseif s then
                        set shp = SHAPE_WALL_L + ORIENTATION_90 + stairs
                    elseif e then
                        set shp = SHAPE_WALL_L + ORIENTATION_180 + stairs
                    elseif n then
                        set shp = SHAPE_WALL_L + ORIENTATION_270 + stairs
                    endif
                elseif cc == 1 then
                    if w then
                        if se then
                            set shp = SHAPE_WALL_L_BR + ORIENTATION_0
                        elseif ne then
                            set shp = SHAPE_WALL_L_TR + ORIENTATION_0
                        endif
                    elseif s then
                        if ne then
                            set shp = SHAPE_WALL_L_BR + ORIENTATION_90
                        elseif nw then
                            set shp = SHAPE_WALL_L_TR + ORIENTATION_90
                        endif
                    elseif e then
                        if nw then
                            set shp = SHAPE_WALL_L_BR + ORIENTATION_180
                        elseif sw then
                            set shp = SHAPE_WALL_L_TR + ORIENTATION_180
                        endif
                    elseif n then
                        if sw then
                            set shp = SHAPE_WALL_L_BR + ORIENTATION_270
                        elseif se then
                            set shp = SHAPE_WALL_L_TR + ORIENTATION_270
                        endif
                    endif
                elseif cc == 2 then
                    if w then
                        set shp = SHAPE_WALL_L_BR_TR + ORIENTATION_0
                    elseif s then
                        set shp = SHAPE_WALL_L_BR_TR + ORIENTATION_90
                    elseif e then
                        set shp = SHAPE_WALL_L_BR_TR + ORIENTATION_180
                    elseif n then
                        set shp = SHAPE_WALL_L_BR_TR + ORIENTATION_270
                    endif
                endif
            elseif wc == 2 then
                if cc == 0 then
                    if w and s then
                        set shp = SHAPE_WALL_L_B + ORIENTATION_0
                    elseif s and e then
                        set shp = SHAPE_WALL_L_B + ORIENTATION_90
                    elseif e and n then
                        set shp = SHAPE_WALL_L_B + ORIENTATION_180
                    elseif n and w then
                        set shp = SHAPE_WALL_L_B + ORIENTATION_270
                    elseif w and e then
                        set shp = SHAPE_WALL_L_R + (GetRandomInt(0,1)*2)*ORIENTATION_90
                    elseif n and s then
                        set shp = SHAPE_WALL_L_R + (GetRandomInt(0,1)*2+1)*ORIENTATION_90
                    endif
                elseif cc == 1 then
                    if w and s then
                        set shp = SHAPE_WALL_L_B_TR + ORIENTATION_0
                    elseif s and e then
                        set shp = SHAPE_WALL_L_B_TR + ORIENTATION_90
                    elseif e and n then
                        set shp = SHAPE_WALL_L_B_TR + ORIENTATION_180
                    elseif n and w then
                        set shp = SHAPE_WALL_L_B_TR + ORIENTATION_270
                    endif
                endif
            elseif wc == 3 then
                if not n then
                    set shp = SHAPE_WALL_L_B_R + ORIENTATION_0 + stairs
                elseif not w then
                    set shp = SHAPE_WALL_L_B_R + ORIENTATION_90 + stairs
                elseif not s then
                    set shp = SHAPE_WALL_L_B_R + ORIENTATION_180 + stairs
                elseif not e then
                    set shp = SHAPE_WALL_L_B_R + ORIENTATION_270 + stairs
                endif
            elseif wc == 4 then
                set shp = SHAPE_BLACK + ORIENTATION_0
            endif
        endif
        if shp == -1 then
            call BJDebugMsg("ERROR: no shape found by wall logic!")
            return 0
        else
            if isCave then
                set shp = shp + CAVE_OFFSET
            endif
            set max = shp
            set shp = ModuloInteger(shp,ORIENTATION_90)
            set orient = max-shp
        endif
  
        set max = LoadInteger(HASH, shp, 0)
        set i = 1
        loop
            exitwhen i > max
            set this = LoadInteger(HASH, shp, i)
            if this.tile == fromTileset then
                if validcount <= 0 then
                    set valid[validcount] = this
                    set validcount = validcount+1
                elseif GetRandomReal(0,1) <= this.rare then
                    set valid[validcount] = this
                    set validcount = validcount+1
                endif
            endif
            set i = i + 1
        endloop
        if validcount <= 0 then
            if HaveSavedInteger(HASH, shp, 1) then
                set valid[0] = LoadInteger(HASH, shp, 1)
                set validcount = 1
            else
                call BJDebugMsg("ERROR: No registered stamp found. Please register stamps for this tileset before calling the build algorithm!")
                return 0
            endif
        endif
        set this = valid[GetRandomInt(0,validcount-1)]
        call this.place(area,x,y,orient)
        return this
    endmethod

    method print takes nothing returns nothing
        local integer i = 0
        local string terraindump = ""
        local string variationdump = ""
        local string destrawdump = ""
        local string xdump = ""
        local string ydump = ""
        local string facedump = ""
        if MAX_DESTRUCTABLES_PER_STAMP == 25 and STAMP_SIZE_SQUARED == 25 then
            loop
                exitwhen i >= 25
                if i > 0 then
                    set terraindump = terraindump + ",'" + A2S(this.terrain[i]) + "'"
                    set variationdump = variationdump + "," + I2S(this.variation[i])
                    if this.destraw[i] != 0 then
                        set destrawdump = destrawdump + ",'" + A2S(this.destraw[i]) + "'"
                    else
                        set destrawdump = destrawdump + ",0"
                    endif
                    set xdump = xdump + "," + I2S(R2I(this.destx[i]))
                    set ydump = ydump + "," + I2S(R2I(this.desty[i]))
                    set facedump = facedump + "," + I2S(R2I(this.destrot[i]))
                else
                    set terraindump = "'" + A2S(this.terrain[i]) + "'"
                    set variationdump = I2S(this.variation[i])
                    if this.destraw[i] != 0 then
                        set destrawdump = "'" + A2S(this.destraw[i]) + "'"
                    else
                        set destrawdump = "0"
                    endif
                    set xdump = I2S(R2I(this.destx[i]))
                    set ydump = I2S(R2I(this.desty[i]))
                    set facedump = I2S(R2I(this.destrot[i]))
                endif
                set i = i + 1
            endloop
            call PreloadGenClear()
            call PreloadGenStart()
            call Preload("\")\n\n    call data.registerTerrain("+terraindump+")    \n\n//")
            call Preload("\")\n\n    call data.registerVariation("+variationdump+")    \n\n//")
            call Preload("\")\n\n    call data.registerDestructable("+destrawdump+")    \n\n//")
            call Preload("\")\n\n    call data.registerDestX("+xdump+")    \n\n//")
            call Preload("\")\n\n    call data.registerDestY("+ydump+")    \n\n//")
            call Preload("\")\n\n    call data.registerDestFace("+facedump+")    \n\n//")
            call Preload("\")\n\n                                            \n\n//")
            call PreloadGenEnd(DUNGEON_PRINT_DIRECTORY+"stamp(shape"+I2S(this.shape)+").txt")
        else
            call BJDebugMsg("ERROR: Text-based stamp registry only supported for default values of stamp size (5x5) and destructables per stamp (25)!")
        endif
    endmethod

    //==========================================================================
    //The following methods are wrappers designed for use with the .print method
    //==========================================================================
    method registerTerrain takes integer t00, integer t01, integer t02, integer t03, integer t04, integer t10, integer t11, integer t12, integer t13, integer t14, integer t20, integer t21, integer t22, integer t23, integer t24, integer t30, integer t31, integer t32, integer t33, integer t34, integer t40, integer t41, integer t42, integer t43, integer t44 returns nothing
        if STAMP_SIZE_SQUARED == 25 then
            set this.terrain[0] = t00
            set this.terrain[1] = t01
            set this.terrain[2] = t02
            set this.terrain[3] = t03
            set this.terrain[4] = t04
            set this.terrain[5] = t10
            set this.terrain[6] = t11
            set this.terrain[7] = t12
            set this.terrain[8] = t13
            set this.terrain[9] = t14
            set this.terrain[10] = t20
            set this.terrain[11] = t21
            set this.terrain[12] = t22
            set this.terrain[13] = t23
            set this.terrain[14] = t24
            set this.terrain[15] = t30
            set this.terrain[16] = t31
            set this.terrain[17] = t32
            set this.terrain[18] = t33
            set this.terrain[19] = t34
            set this.terrain[20] = t40
            set this.terrain[21] = t41
            set this.terrain[22] = t42
            set this.terrain[23] = t43
            set this.terrain[24] = t44
        endif
    endmethod

    method registerVariation takes integer t00, integer t01, integer t02, integer t03, integer t04, integer t10, integer t11, integer t12, integer t13, integer t14, integer t20, integer t21, integer t22, integer t23, integer t24, integer t30, integer t31, integer t32, integer t33, integer t34, integer t40, integer t41, integer t42, integer t43, integer t44 returns nothing
        if STAMP_SIZE_SQUARED == 25 then
            set this.variation[0] = t00
            set this.variation[1] = t01
            set this.variation[2] = t02
            set this.variation[3] = t03
            set this.variation[4] = t04
            set this.variation[5] = t10
            set this.variation[6] = t11
            set this.variation[7] = t12
            set this.variation[8] = t13
            set this.variation[9] = t14
            set this.variation[10] = t20
            set this.variation[11] = t21
            set this.variation[12] = t22
            set this.variation[13] = t23
            set this.variation[14] = t24
            set this.variation[15] = t30
            set this.variation[16] = t31
            set this.variation[17] = t32
            set this.variation[18] = t33
            set this.variation[19] = t34
            set this.variation[20] = t40
            set this.variation[21] = t41
            set this.variation[22] = t42
            set this.variation[23] = t43
            set this.variation[24] = t44
        endif
    endmethod

    method registerDestructable takes integer t00, integer t01, integer t02, integer t03, integer t04, integer t10, integer t11, integer t12, integer t13, integer t14, integer t20, integer t21, integer t22, integer t23, integer t24, integer t30, integer t31, integer t32, integer t33, integer t34, integer t40, integer t41, integer t42, integer t43, integer t44 returns nothing
        if MAX_DESTRUCTABLES_PER_STAMP == 25 then
            set this.destraw[0] = t00
            set this.destraw[1] = t01
            set this.destraw[2] = t02
            set this.destraw[3] = t03
            set this.destraw[4] = t04
            set this.destraw[5] = t10
            set this.destraw[6] = t11
            set this.destraw[7] = t12
            set this.destraw[8] = t13
            set this.destraw[9] = t14
            set this.destraw[10] = t20
            set this.destraw[11] = t21
            set this.destraw[12] = t22
            set this.destraw[13] = t23
            set this.destraw[14] = t24
            set this.destraw[15] = t30
            set this.destraw[16] = t31
            set this.destraw[17] = t32
            set this.destraw[18] = t33
            set this.destraw[19] = t34
            set this.destraw[20] = t40
            set this.destraw[21] = t41
            set this.destraw[22] = t42
            set this.destraw[23] = t43
            set this.destraw[24] = t44
        endif
    endmethod

    method registerDestX takes real t00, real t01, real t02, real t03, real t04, real t10, real t11, real t12, real t13, real t14, real t20, real t21, real t22, real t23, real t24, real t30, real t31, real t32, real t33, real t34, real t40, real t41, real t42, real t43, real t44 returns nothing
            if MAX_DESTRUCTABLES_PER_STAMP == 25 then
            set this.destx[0] = t00
            set this.destx[1] = t01
            set this.destx[2] = t02
            set this.destx[3] = t03
            set this.destx[4] = t04
            set this.destx[5] = t10
            set this.destx[6] = t11
            set this.destx[7] = t12
            set this.destx[8] = t13
            set this.destx[9] = t14
            set this.destx[10] = t20
            set this.destx[11] = t21
            set this.destx[12] = t22
            set this.destx[13] = t23
            set this.destx[14] = t24
            set this.destx[15] = t30
            set this.destx[16] = t31
            set this.destx[17] = t32
            set this.destx[18] = t33
            set this.destx[19] = t34
            set this.destx[20] = t40
            set this.destx[21] = t41
            set this.destx[22] = t42
            set this.destx[23] = t43
            set this.destx[24] = t44
        endif
    endmethod

    method registerDestY takes real t00, real t01, real t02, real t03, real t04, real t10, real t11, real t12, real t13, real t14, real t20, real t21, real t22, real t23, real t24, real t30, real t31, real t32, real t33, real t34, real t40, real t41, real t42, real t43, real t44 returns nothing
        if MAX_DESTRUCTABLES_PER_STAMP == 25 then
            set this.desty[0] = t00
            set this.desty[1] = t01
            set this.desty[2] = t02
            set this.desty[3] = t03
            set this.desty[4] = t04
            set this.desty[5] = t10
            set this.desty[6] = t11
            set this.desty[7] = t12
            set this.desty[8] = t13
            set this.desty[9] = t14
            set this.desty[10] = t20
            set this.desty[11] = t21
            set this.desty[12] = t22
            set this.desty[13] = t23
            set this.desty[14] = t24
            set this.desty[15] = t30
            set this.desty[16] = t31
            set this.desty[17] = t32
            set this.desty[18] = t33
            set this.desty[19] = t34
            set this.desty[20] = t40
            set this.desty[21] = t41
            set this.desty[22] = t42
            set this.desty[23] = t43
            set this.desty[24] = t44
        endif
    endmethod

    method registerDestFace takes real t00, real t01, real t02, real t03, real t04, real t10, real t11, real t12, real t13, real t14, real t20, real t21, real t22, real t23, real t24, real t30, real t31, real t32, real t33, real t34, real t40, real t41, real t42, real t43, real t44 returns nothing
        if MAX_DESTRUCTABLES_PER_STAMP == 25 then
            set this.destrot[0] = t00
            set this.destrot[1] = t01
            set this.destrot[2] = t02
            set this.destrot[3] = t03
            set this.destrot[4] = t04
            set this.destrot[5] = t10
            set this.destrot[6] = t11
            set this.destrot[7] = t12
            set this.destrot[8] = t13
            set this.destrot[9] = t14
            set this.destrot[10] = t20
            set this.destrot[11] = t21
            set this.destrot[12] = t22
            set this.destrot[13] = t23
            set this.destrot[14] = t24
            set this.destrot[15] = t30
            set this.destrot[16] = t31
            set this.destrot[17] = t32
            set this.destrot[18] = t33
            set this.destrot[19] = t34
            set this.destrot[20] = t40
            set this.destrot[21] = t41
            set this.destrot[22] = t42
            set this.destrot[23] = t43
            set this.destrot[24] = t44
        endif
    endmethod
endstruct


endlibrary
JASS:
library DungeonGenerator uses DungeonStamp

globals
    private constant integer DUNGEON_SIZE_X = 64               //grid dimensions of the dungeon integer field
    private constant integer DUNGEON_SIZE_Y = 64
                                                                //Ingame coordinates: DUNGEON_SIZE_X * TILE_SIZE * 128
                                                          
    private constant real DUNGEON_VERIFICATION_THRESHOLD = 0.1  //fraction of a generated dungeon map that must be verified as reachable before the verification algorithm stops
    private constant integer MAX_VERIFY_ATTEMPTS = 10           //maximum number of verification attempts to reach the specified threshold
                                                                //-> when failing, the generated map is considered unusable and should be discarded by the user
    //====================
    //end of configurables

    constant integer DUNGEON_EMPTY = 0
    constant integer DUNGEON_ROOM = 1
    constant integer DUNGEON_CAVE = 2
    constant integer DUNGEON_CORRIDOR = 3
endglobals



struct Room
     thistype llPrev
     thistype llNext
     integer minx
     integer maxx
     integer miny
     integer maxy
     integer centerx
     integer centery

     method getNext takes nothing returns thistype
         return this.llNext
     endmethod

     static method create takes integer x1, integer y1, integer x2, integer y2 returns thistype
         local thistype this = thistype.allocate()
         set this.llNext = 0
         set this.llPrev = 0
         set this.minx = x1
         set this.maxx = x2
         set this.miny = y1
         set this.maxy = y2
         set this.centerx = (x1+x2)/2
         set this.centery = (y1+y2)/2
         return this
     endmethod

     method onDestroy takes nothing returns nothing
         set this.llPrev = 0
         set this.llNext = 0
     endmethod
endstruct

struct RoomList
     private Room llHead

     static method create takes nothing returns thistype
         local thistype this = thistype.allocate()
         set this.llHead = 0
         return this
     endmethod

     private method llAdd takes Room b returns nothing
         set b.llNext = this.llHead
         if this.llHead != 0 then
             set this.llHead.llPrev = b
         endif
         set this.llHead = b
         set b.llPrev = 0
     endmethod

     private method llRemove takes Room b returns nothing
         if b.llPrev != 0 then
             set b.llPrev.llNext = b.llNext
         else
             set this.llHead = b.llNext
         endif
         if b.llNext != 0 then
             set b.llNext.llPrev = b.llPrev
         endif
     endmethod

     method getFirst takes nothing returns Room
         return this.llHead
     endmethod

     method add takes Room b returns nothing
         call this.llAdd(b)
     endmethod

     method remove takes Room b returns nothing
         call this.llRemove(b)
     endmethod

     method iterator takes nothing returns RoomListIterator
         return RoomListIterator.create(this)
     endmethod

     method onDestroy takes nothing returns nothing
         local RoomListIterator iter = this.iterator()
         local Room nxt
         loop
             exitwhen iter.hasNoNext()
             set nxt = iter.next()
             call this.llRemove(nxt)
             call nxt.destroy()
         endloop
         call iter.destroy()
     endmethod
endstruct

struct RoomListIterator
     private RoomList roomList
     private Room nextRoom

     static method create takes RoomList roomList returns thistype
         local thistype this = thistype.allocate()
         set this.roomList = roomList
         set this.nextRoom = roomList.getFirst()
         return this
     endmethod

     method hasNext takes nothing returns boolean
         return this.nextRoom != 0
     endmethod

     method hasNoNext takes nothing returns boolean
         return this.hasNext() == false
     endmethod

     method next takes nothing returns Room
         local Room tmp = this.nextRoom
         set this.nextRoom = this.nextRoom.getNext()
         return tmp
     endmethod
endstruct

globals
    private constant integer MAX_VERIFY_PER_ITERATION = 64
    private integer array map[DUNGEON_SIZE_X][DUNGEON_SIZE_Y]
    private boolean array verifymap[DUNGEON_SIZE_X][DUNGEON_SIZE_Y]
    private stamp array stamps[DUNGEON_SIZE_X][DUNGEON_SIZE_Y]
    private integer stacksize = 0
    private integer array stackx
    private integer array stacky
    private boolean usable = false
    private integer verified
    private integer veriAttempts = 0
    private trigger veriTrig = null
    private trigger printTrig = null
    private integer printCount = 0
    private trigger clearTrig = null
    private integer clearCount = 0
    private trigger veriClearTrig = null
    private integer veriClearCount = 0
    private trigger clearUnverifiedTrig = null
    private integer clearUnverifiedCount = 0
    private rect buildArea = null
    private timer buildTimer = null
    private trigger buildTrig = null
    private integer buildx = 0
    private integer buildy = 0
    private integer buildTileset
    private integer buildStairsConsidered
    private integer buildStairsUpPickX
    private integer buildStairsUpPickY
    private integer buildStairsDownPickX
    private integer buildStairsDownPickY
    private trigger removeTrig = null
    private rect enumArea = null
    private trigger enumTrig = null
    private trigger enumCallTrig = null
    private integer enumx = 0
    private integer enumy = 0
    private real lastUpX = 0
    private real lastUpY = 0
    private real lastDownX = 0
    private real lastDownY = 0
    private stamp curstamp = 0
endglobals

//For use with .enumerateMap()
function GetEnumStamp takes nothing returns stamp
    return curstamp
endfunction
function GetEnumStampData takes nothing returns integer
    return curstamp.data
endfunction
function GetEnumStampValue takes nothing returns real
    return curstamp.value
endfunction
function GetEnumStampCenterX takes nothing returns real
    return GetRectMinX(enumArea)+enumx*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2
endfunction
function GetEnumStampCenterY takes nothing returns real
    return GetRectMinY(enumArea)+enumy*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2
endfunction

function GetLastCreatedStairs takes boolean up returns location
    if up then
        return Location(lastUpX, lastUpY)
    else
        return Location(lastDownX, lastDownY)
    endif
endfunction

struct Dungeon extends array
    static method isVerified takes integer x, integer y returns boolean
        return verifymap[x][y]
    endmethod
    static method getTile takes integer x, integer y returns integer
        return map[x][y]
    endmethod
    static method isWall takes integer x, integer y returns boolean
        if x >= 0 and x < DUNGEON_SIZE_X and y >= 0 and y < DUNGEON_SIZE_Y then
            return map[x][y] == DUNGEON_EMPTY
        endif
        return true
    endmethod
    static method getAdjacentWalls takes integer x, integer y, integer radius returns integer
        local integer count = 0
        local integer i = -radius
        local integer j
        loop
            exitwhen i > radius
            set j = -radius
            loop
                exitwhen j > radius
                if not (i == x and j == y) then
                    if map[x+i][y+j] <= DUNGEON_EMPTY then
                        set count = count + 1
                    endif
                endif
                set j = j + 1
            endloop
            set i = i + 1
        endloop
        return count
    endmethod

    private static method enumSub takes nothing returns nothing
        local integer j = 0
        local integer i = enumx
        loop
            exitwhen j >= DUNGEON_SIZE_Y
            set curstamp = stamps[enumx][j]
            set enumy = j
            call TriggerExecute(enumCallTrig)
            set j = j + 1
        endloop
        set enumx = enumx+1
        if enumx < DUNGEON_SIZE_X then
            call TriggerExecute(enumTrig)
        endif
    endmethod
    static method enumerateMap takes rect area, code actionFunc returns nothing
        if enumTrig == null then
            set enumTrig = CreateTrigger()
            call TriggerAddAction(enumTrig, function thistype.enumSub)
        endif
        if enumCallTrig != null then
            call TriggerClearActions(enumCallTrig)
            call DestroyTrigger(enumCallTrig)
        endif
        set enumCallTrig = CreateTrigger()
        call TriggerAddAction(enumCallTrig, actionFunc)
        set enumArea = area
        set enumx = 0
        set enumy = 0
        call TriggerExecute(enumTrig)
    endmethod

    private static method removeSub takes nothing returns nothing
        local integer j = 0
        local integer i = buildx
        loop
            exitwhen j >= DUNGEON_SIZE_Y
            call stamp.remove(buildArea,i,j)
            set stamps[i][j] = 0
            set j = j + 1
        endloop
        set buildx = buildx+1
        if buildx < DUNGEON_SIZE_X then
            call TriggerExecute(removeTrig)
        endif
    endmethod
    static method removeAll takes rect area returns nothing
        if removeTrig == null then
            set removeTrig = CreateTrigger()
            call TriggerAddAction(removeTrig, function thistype.removeSub)
        endif
        set buildArea = area
        set buildx = 0
        call TriggerExecute(removeTrig)
    endmethod

    private static method buildSub takes nothing returns nothing
        local integer x = buildx
        local integer y = buildy
        local boolean cave = false
        local stamp s = 0
        local integer rnd
        if map[x][y] == DUNGEON_CAVE then
            set cave = true
        endif
        if map[x][y] >= DUNGEON_ROOM then
            set s = stamp.placeByLogic(buildArea, x, y, cave, false, false, buildTileset, thistype.isWall(x-1,y-1), thistype.isWall(x-1,y), thistype.isWall(x-1,y+1), thistype.isWall(x,y-1), thistype.isWall(x,y), thistype.isWall(x,y+1), thistype.isWall(x+1,y-1), thistype.isWall(x+1,y), thistype.isWall(x+1,y+1))
            set stamps[x][y] = s
            if s == 0 then
            elseif s.canHaveStairs() then
                //reservoir sampling
                set buildStairsConsidered = buildStairsConsidered+1
                set rnd = GetRandomInt(1,buildStairsConsidered)
                if rnd == 1 then
                    set buildStairsUpPickX = x
                    set buildStairsUpPickY = y
                elseif rnd == 2 then
                    set buildStairsDownPickX = x
                    set buildStairsDownPickY = y
                endif
            endif
        elseif map[x][y] == DUNGEON_EMPTY then
            set s = stamp.placeByLogic(buildArea, x, y, cave, false, false, buildTileset, thistype.isWall(x-1,y-1), thistype.isWall(x-1,y), thistype.isWall(x-1,y+1), thistype.isWall(x,y-1), thistype.isWall(x,y), thistype.isWall(x,y+1), thistype.isWall(x+1,y-1), thistype.isWall(x+1,y), thistype.isWall(x+1,y+1))
            set stamps[x][y] = s
        endif
  
        set buildy = buildy+1
        if buildy >= DUNGEON_SIZE_Y then
            set buildy = 0
            set buildx = buildx+1
        endif
        if buildx < DUNGEON_SIZE_X and buildy < DUNGEON_SIZE_Y then
            call TimerStart(buildTimer, 0, false, function thistype.buildSub)
        else
            //place stairs
            set x = buildStairsUpPickX
            set y = buildStairsUpPickY
            if map[x][y] == DUNGEON_CAVE then
                set cave = true
            endif
            set s = stamp.placeByLogic(buildArea, x, y, cave, true, true, buildTileset, thistype.isWall(x-1,y-1), thistype.isWall(x-1,y), thistype.isWall(x-1,y+1), thistype.isWall(x,y-1), thistype.isWall(x,y), thistype.isWall(x,y+1), thistype.isWall(x+1,y-1), thistype.isWall(x+1,y), thistype.isWall(x+1,y+1))
            set lastUpX = GetRectMinX(buildArea)+x*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2
            set lastUpY = GetRectMinY(buildArea)+y*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2
            set x = buildStairsDownPickX
            set y = buildStairsDownPickY
            if map[x][y] == DUNGEON_CAVE then
                set cave = true
            endif
            set s = stamp.placeByLogic(buildArea, x, y, cave, true, false, buildTileset, thistype.isWall(x-1,y-1), thistype.isWall(x-1,y), thistype.isWall(x-1,y+1), thistype.isWall(x,y-1), thistype.isWall(x,y), thistype.isWall(x,y+1), thistype.isWall(x+1,y-1), thistype.isWall(x+1,y), thistype.isWall(x+1,y+1))
            set lastDownX = GetRectMinX(buildArea)+x*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2
            set lastDownY = GetRectMinY(buildArea)+y*STAMP_SIZE_REAL+STAMP_SIZE_REAL/2
            call TriggerExecute(buildTrig)
        endif
    endmethod

    static method build takes rect area, integer tileset, code actionFunc returns nothing
        if buildTimer == null then
            set buildTimer = CreateTimer()
        endif
        if buildTrig != null then
            call TriggerClearActions(buildTrig)
            call DestroyTrigger(buildTrig)
        endif
        set buildTrig = CreateTrigger()
        call TriggerAddAction(buildTrig, actionFunc)
        set buildArea = area
        set buildTileset = tileset
        set buildStairsConsidered = 0
        set buildStairsUpPickX = 0
        set buildStairsUpPickY = 0
        set buildStairsDownPickX = 0
        set buildStairsDownPickY = 0
        set buildx = 0
        set buildy = 0
        call TimerStart(buildTimer, 0, false, function thistype.buildSub)
    endmethod

    private static method clearUnverifiedSub takes nothing returns nothing
        local integer j = 0
        local integer i = clearUnverifiedCount
        loop
            exitwhen j >= DUNGEON_SIZE_Y
            if not verifymap[i][j] then
                set map[i][j] = DUNGEON_EMPTY
            endif
            set j = j + 1
        endloop
        set clearUnverifiedCount = clearUnverifiedCount+1
        if clearUnverifiedCount < DUNGEON_SIZE_X then
            call TriggerExecute(clearUnverifiedTrig)
        endif
    endmethod

    static method clearUnverified takes nothing returns nothing
        if clearUnverifiedTrig == null then
            set clearUnverifiedTrig = CreateTrigger()
            call TriggerAddAction(clearUnverifiedTrig, function thistype.clearUnverifiedSub)
        endif
        set clearUnverifiedCount = 0
        call TriggerExecute(clearUnverifiedTrig)
    endmethod

    static method isMapUsable takes nothing returns boolean
        return usable
    endmethod

    private static method verifyMapClear takes nothing returns nothing
        local integer j = 0
        local integer i = veriClearCount
        loop
            exitwhen j >= DUNGEON_SIZE_Y
            set verifymap[i][j] = false
            set j = j + 1
        endloop
        set veriClearCount = veriClearCount+1
        if veriClearCount < DUNGEON_SIZE_X then
            call TriggerExecute(veriClearTrig)
        endif
    endmethod

    static method verifyMap takes nothing returns nothing
        local integer i = 0
        local integer j
        local integer count = 0
        if veriTrig == null then
            set veriTrig = CreateTrigger()
            call TriggerAddAction(veriTrig, function thistype.verifyMap)
            set veriClearTrig = CreateTrigger()
            call TriggerAddAction(veriClearTrig, function thistype.verifyMapClear)
        endif
        if stacksize <= 0 then
            set stacksize = 1
            set verified = 0
            loop
                set stackx[0] = GetRandomInt(1,DUNGEON_SIZE_X-2)
                set stacky[0] = GetRandomInt(1,DUNGEON_SIZE_Y-2)
                exitwhen map[stackx[0]][stacky[0]] >= DUNGEON_ROOM
            endloop
            set veriClearCount = 0
            call TriggerExecute(veriClearTrig)
        else
            loop
                exitwhen stacksize <= 0
                exitwhen count > MAX_VERIFY_PER_ITERATION
                set stacksize = stacksize-1
                set i = stackx[stacksize]
                set j = stacky[stacksize]
                if map[i][j] >= DUNGEON_ROOM and not verifymap[i][j] then
                    set verifymap[i][j] = true
                    set verified = verified + 1
                    if not verifymap[i][j+1] then
                        set stackx[stacksize] = i
                        set stacky[stacksize] = j+1
                        set stacksize = stacksize+1
                    endif
                    if not verifymap[i][j-1] then
                        set stackx[stacksize] = i
                        set stacky[stacksize] = j-1
                        set stacksize = stacksize+1
                    endif
                    if not verifymap[i+1][j] then
                        set stackx[stacksize] = i+1
                        set stacky[stacksize] = j
                        set stacksize = stacksize+1
                    endif
                    if not verifymap[i-1][j] then
                        set stackx[stacksize] = i-1
                        set stacky[stacksize] = j
                        set stacksize = stacksize+1
                    endif
                endif
                set count = count + 1
            endloop
        endif
        if stacksize <= 0 then
            if I2R(verified)/I2R(DUNGEON_SIZE_X*DUNGEON_SIZE_Y) > DUNGEON_VERIFICATION_THRESHOLD then
                set veriAttempts = 0
                set usable = true
                return
            elseif veriAttempts > MAX_VERIFY_ATTEMPTS then
                set veriAttempts = 0
                set usable = false
                return
            else
                set veriAttempts = veriAttempts+1
            endif
        endif
        call TriggerExecute(veriTrig)
    endmethod


    private static method clearSub takes nothing returns nothing
        local integer j = 0
        local integer i = clearCount
        loop
            exitwhen j >= DUNGEON_SIZE_Y
            set map[i][j] = DUNGEON_EMPTY
            set j = j + 1
        endloop
        set clearCount = clearCount+1
        if clearCount < DUNGEON_SIZE_X then
            call TriggerExecute(clearTrig)
        endif
    endmethod

    static method clearMap takes nothing returns nothing
        if clearTrig == null then
            set clearTrig = CreateTrigger()
            call TriggerAddAction(clearTrig, function thistype.clearSub)
        endif
        set clearCount = 0
        call TriggerExecute(clearTrig)
    endmethod

    private static method printSub takes nothing returns nothing
        local string s = ""
        local integer j = printCount
        local integer i = 0
        if j >= 0 then
            loop
                exitwhen i >= DUNGEON_SIZE_X
                if map[i][j] == DUNGEON_EMPTY then
                    set s = s + " "
                elseif verifymap[i][j] then
                    if map[i][j] == DUNGEON_ROOM then
                        set s = s + "#"
                    elseif map[i][j] == DUNGEON_CAVE then
                        set s = s + "+"
                    elseif map[i][j] == DUNGEON_CORRIDOR then
                        set s = s + "."
                    endif
                else
                    set s = s + "X"
                endif
                set i = i + 1
            endloop
            call Preload("\")\n\n    "+s+"    \n\n//")
            set printCount = printCount-1
            call TriggerExecute(printTrig)
        endif
    endmethod

    static method printMap takes nothing returns nothing
        if printTrig == null then
            set printTrig = CreateTrigger()
            call TriggerAddAction(printTrig, function thistype.printSub)
        endif
        set printCount = DUNGEON_SIZE_Y-1
        call PreloadGenClear()
        call PreloadGenStart()
        call TriggerExecute(printTrig)
        call PreloadGenEnd(DUNGEON_PRINT_DIRECTORY+"layout.txt")
    endmethod
endstruct

struct DungeonCavern
    integer state                                           //determines the generator phase
    boolean doWrite                                         //switches between evolving and writing phase
    integer percentAreWalls                                 //determines the original distribution of walls to rooms
    integer minx                                            //determines the extends of the current map
    integer maxx
    integer miny
    integer maxy
    integer curx
    integer highcut
    integer lowcut
    integer iterations
    integer disableLowcutAfter
    boolean horizontalCut
    boolean finished
    trigger trig
    static thistype temp = 0
    static integer array tempmap[DUNGEON_SIZE_X][DUNGEON_SIZE_Y]

    method onDestroy takes nothing returns nothing
        call TriggerClearActions(this.trig)
        call DestroyTrigger(this.trig)
        set this.trig = null
    endmethod

    method evolve takes integer hc, integer lc returns boolean
        local integer i = this.curx
        local integer j = this.miny+1
        local integer numWalls1
        local integer numWalls2
        loop
            exitwhen j >= this.maxy-1
            set numWalls1 = Dungeon.getAdjacentWalls(i,j, 1)
            if i >= this.minx+2 and i < this.maxx-2 and j >= this.miny+2 and j < this.maxy-2 then
                set numWalls2 = Dungeon.getAdjacentWalls(i,j,2)
            else
                set numWalls2 = numWalls1+5
            endif
            if numWalls1 >= hc or numWalls2 <= lc then
                set thistype.tempmap[i][j] = DUNGEON_EMPTY
            else
                set thistype.tempmap[i][j] = DUNGEON_CAVE
            endif
            set j = j + 1
        endloop
        set this.curx = i+1
        if this.curx >= this.maxx-1 then
            return true
        endif
        return false
    endmethod

    method write takes nothing returns nothing
        local integer i = this.minx
        local integer j
        loop
            exitwhen i >= this.maxx
            set j = this.miny
            loop
                exitwhen j >= this.maxy
                set map[i][j] = thistype.tempmap[i][j]
                set thistype.tempmap[i][j] = DUNGEON_EMPTY
                set j = j + 1
            endloop
            set i = i + 1
        endloop
        set curx = this.minx+1
    endmethod

    method randomize takes nothing returns nothing
        local integer i = this.minx+1
        local integer j
        local integer centery = (this.miny+this.maxy)/2
        loop
            exitwhen i >= this.maxx-1
            set j = this.miny+1
            loop
                exitwhen j >= this.maxy-1
                if map[i][j] == DUNGEON_EMPTY then
                    if (j == centery and this.horizontalCut) or GetRandomInt(1,100) > this.percentAreWalls then
                        set map[i][j] = DUNGEON_CAVE
                    endif
                endif
                set j = j + 1
            endloop
            set i = i + 1
        endloop
    endmethod

    private static method generateSub takes nothing returns nothing
        local thistype this = thistype.temp
        if this.state == 0 then
            call this.randomize()
            set this.state = 1
        elseif this.state >= 1 and this.state <= this.disableLowcutAfter then
            if this.doWrite then
                call this.write()
                set this.state = this.state+1
                set this.doWrite = false
            else
                if this.evolve(this.highcut,this.lowcut) then
                    set this.doWrite = true
                endif
            endif
        elseif this.state <= this.iterations then
            if this.doWrite then
                call this.write()
                set this.state = this.state+1
                set this.doWrite = false
            else
                if this.evolve(this.highcut,-1) then
                    set this.doWrite = true
                endif
            endif
        elseif this.state == this.iterations+1 then
            set this.finished = true
        endif
        if not this.finished then
            call TriggerExecute(this.trig)
        endif
    endmethod

    method generate takes nothing returns nothing
        set thistype.temp = this
        call TriggerExecute(this.trig)
    endmethod

    static method create takes integer x1, integer y1, integer x2, integer y2, integer wallPercent, boolean horizontalBlank, integer cuthigh, integer cutlow, integer phases, integer stopLowcutAfter returns thistype
        local thistype this = thistype.allocate()
        set this.state = 0
        set this.doWrite = false
        set this.percentAreWalls = wallPercent
        set this.minx = x1
        set this.maxx = x2
        set this.miny = y1
        set this.maxy = y2
        set this.curx = x1+1
        set this.highcut = cuthigh
        set this.lowcut = cutlow
        set this.iterations = phases
        set this.disableLowcutAfter = stopLowcutAfter
        set this.horizontalCut = horizontalBlank
        set this.finished = false
        set this.trig = CreateTrigger()
        call TriggerAddAction(this.trig, function thistype.generateSub)
        return this
    endmethod
endstruct

struct DungeonUniform
    RoomList connected                                    //list of already connected rooms
    RoomList unconnected                                  //list of remaining unconnected rooms

    boolean allowIrregular                                  //determines if non-rectangular rooms are allowed                       
    real roomPercentage                                     //we stop createing rooms after this percentage of level area has been dug out
    integer minSize                                         //minimum room dimension
    integer maxWidth                                        //maximum room width
    integer maxHeight                                       //maximum room height
    real extraChance                                        //chance to create an extra corridor per room
    real extraDead                                          //chance to create a deadend corridor per room
    integer maxRoomAttempts                                 //maximum number of attempts to create a valid room
    integer maxRooms                                        //maximum number of created rooms

    integer rooms                                           //counts the number of created rooms
    integer dug                                             //counts the number of cells dug
    integer state                                           //determines the generator phase
    integer minx                                            //determines the extends of the map
    integer maxx
    integer miny
    integer maxy
    boolean finished
    trigger trig
    static thistype temp = 0

    method onDestroy takes nothing returns nothing
        call this.connected.destroy()
        call this.unconnected.destroy()
        call TriggerClearActions(this.trig)
        call DestroyTrigger(this.trig)
        set this.trig = null
    endmethod

    method digLine takes boolean horizontal, integer x, integer y, integer last returns nothing
        local integer i = x
        local integer j = y
        local integer l = last
        if last < x and horizontal then
            set l = x
            set i = last
        elseif last < y and not horizontal then
            set l = y
            set j = last
        endif
        loop
            if map[i][j] == DUNGEON_EMPTY then
                set map[i][j] = DUNGEON_CORRIDOR
                set this.dug = this.dug+1
            endif
            if horizontal then
                set i = i + 1
                exitwhen i > l
            else
                set j = j + 1
                exitwhen j > l
            endif
        endloop
    endmethod

    method digRoom takes integer x1, integer y1, integer x2, integer y2 returns nothing
        local integer i = x1
        local integer j
        loop
            exitwhen i > x2
            set j = y1
            loop
                exitwhen j > y2
                if map[i][j] != DUNGEON_ROOM then
                    set map[i][j] = DUNGEON_ROOM
                    set this.dug = this.dug+1
                endif
                set j = j + 1
            endloop
            set i = i + 1
        endloop
        set this.rooms = this.rooms+1
        call this.unconnected.add(Room.create(x1,y1,x2,y2))
    endmethod

    method generateRoom takes nothing returns boolean
        local integer count = 0
        local integer x1
        local integer y1
        local integer x2
        local integer y2
        loop
            exitwhen count > this.maxRoomAttempts
      
            set x1 = GetRandomInt(this.minx+1,this.maxx-2)
            set y1 = GetRandomInt(this.miny+1,this.maxy-2)
            set x2 = x1+GetRandomInt(this.minSize, this.maxWidth)-1
            set y2 = y1+GetRandomInt(this.minSize, this.maxHeight)-1
            if not this.allowIrregular then
                //snap regular rooms to odd-numbered grid positions
                if ModuloInteger(x1,2) == 0 then
                    set x1=x1-1
                endif
                if ModuloInteger(y1,2) == 0 then
                    set y1=y1-1
                endif
                if ModuloInteger(x2,2) == 0 then
                    set x2=x2-1
                endif
                if ModuloInteger(y2,2) == 0 then
                    set y2=y2-1
                endif
            endif
      
            if x1 > this.minx and y1 > this.miny and x2 < (this.maxx-1) and y2 < (this.maxy-1) then
                if this.allowIrregular or (map[x1][y1] != DUNGEON_ROOM and map[x2][y1] != DUNGEON_ROOM and map[x1][y2] != DUNGEON_ROOM and map[x2][y2] != DUNGEON_ROOM) then
                    call this.digRoom(x1,y1,x2,y2)
                    if GetRandomReal(0,1) <= this.extraDead then
                        set x1 = GetRandomInt(x1,x2)
                        set y1 = GetRandomInt(y1,y2)
                        if GetRandomInt(0,1) == 1 then
                            set x2 = x1+GetRandomInt(-(this.maxWidth), this.maxWidth)
                            if x2 > this.minx+1 and x2 < this.maxx-2 then
                                call this.digLine(true,x1,y1,x2)
                            endif
                        else
                            set y2 = y1+GetRandomInt(-(this.maxHeight), this.maxHeight)
                            if y2 > this.miny+1 and y2 < this.maxy-2 then
                                call this.digLine(false,x1,y1,y2)
                            endif
                        endif
                    endif
                endif
                return true
            endif
      
            set count = count + 1
        endloop
        return false
    endmethod

    method connectRooms takes Room start, Room other returns nothing
        local integer count = 0
        local integer diffX = other.centerx - start.centerx
        local integer diffY = other.centery - start.centery
        local integer minCommonX = -1
        local integer maxCommonX = -1
        local integer minCommonY = -1
        local integer maxCommonY = -1
        local Room s
        local Room o
        local integer temp1
        local integer temp2
  
        //determine common coordinates
        if start.minx <= other.minx then
            set s = start
            set o = other
        else
            set s = other
            set o = start
        endif
        if o.minx <= s.maxx then
            set minCommonX = o.minx
            if s.maxx <= o.maxx then
                set maxCommonX = s.maxx
            else
                set maxCommonX = o.maxx
            endif
        endif
        if start.miny <= other.miny then
            set s = start
            set o = other
        else
            set s = other
            set o = start
        endif
        if o.miny <= s.maxy then
            set minCommonY = o.miny
            if s.maxy <= o.maxy then
                set maxCommonY = s.maxy
            else
                set maxCommonY = o.maxy
            endif
        endif
  
        if minCommonX >= 0 and maxCommonX >= 0 and minCommonY >= 0 and maxCommonY >= 0 then
            //rooms overlap each other; no connection needed
        elseif minCommonX >= 0 and maxCommonX >= 0 and minCommonX != maxCommonX then
            //dig straight along y-axis
            call this.digLine(false, GetRandomInt(minCommonX, maxCommonX), start.centery, other.centery)
        elseif minCommonY >= 0 and maxCommonY >= 0 and minCommonY != maxCommonY then
            //dig straight along x-axis
            call this.digLine(true, start.centerx, GetRandomInt(minCommonY, maxCommonY), other.centerx)
        else
            //L or S-shaped connections
            if IAbsBJ(diffX) > IAbsBJ(diffY) then
                if diffX > 0 then
                    set s = start
                    set o = other
                else
                    set s = other
                    set o = start
                endif
                if s.maxx <= o.minx-4 and GetRandomInt(1,2) <= 1 then //S-shaped connection
                    set temp1 = GetRandomInt(s.miny, s.maxy)
                    set temp2 = GetRandomInt(o.miny, o.maxy)
                    call this.digLine(true, s.centerx, temp1, (s.maxx+o.minx)/2)
                    call this.digLine(false, (s.maxx+o.minx)/2, temp1, temp2)
                    call this.digLine(true, (s.maxx+o.minx)/2, temp2, o.centerx)
                else //L-shaped connection
                    set temp1 = GetRandomInt(s.miny, s.maxy)
                    set temp2 = GetRandomInt(o.minx, o.maxx)
                    call this.digLine(true, s.centerx, temp1, temp2)
                    call this.digLine(false, temp2, temp1, o.centery)
                endif
            else
                if diffY > 0 then
                    set s = start
                    set o = other
                else
                    set s = other
                    set o = start
                endif
                if s.maxy <= o.miny-4 and GetRandomInt(1,2) <= 1 then //S-shaped connection
                    set temp1 = GetRandomInt(s.minx, s.maxx)
                    set temp2 = GetRandomInt(o.minx, o.maxx)
                    call this.digLine(false, temp1, s.centery, (s.maxy+o.miny)/2)
                    call this.digLine(true, temp1, (s.maxy+o.miny)/2, temp2)
                    call this.digLine(false, temp2, (s.maxy+o.miny)/2, o.centery)
                else //L-shaped connection
                    set temp1 = GetRandomInt(s.minx, s.maxx)
                    set temp2 = GetRandomInt(o.miny, o.maxy)
                    call this.digLine(false, temp1, s.centery, temp2)
                    call this.digLine(true, temp1, temp2, o.centerx)
                endif
            endif
        endif
    endmethod

    method generateCorridor takes nothing returns boolean
        local real closedist = DUNGEON_SIZE_X+DUNGEON_SIZE_Y
        local real distance
        local RoomListIterator iter
        local Room current = 0
        local Room closest = 0
        local Room extra = 0
        local Room start = 0
        if this.unconnected.getFirst() != 0 and this.connected.getFirst() == 0 then
            set start = this.unconnected.getFirst()
            call this.unconnected.remove(start)
            call this.connected.add(start)
        endif
        if this.connected.getFirst() != 0 and this.unconnected.getFirst() != 0 then
            set start = this.connected.getFirst()
            set iter = this.unconnected.iterator()
            loop
                exitwhen iter.hasNoNext()
                set current = iter.next()
                set distance = SquareRoot((current.centerx-start.centerx)*(current.centerx-start.centerx) + (current.centery-start.centery)*(current.centery-start.centery))
                if distance < closedist then
                    set closedist = distance
                    set extra = closest
                    set closest = current
                endif
            endloop
            call iter.destroy()
            if closest != 0 then
                call this.connectRooms(start, closest)
                call this.unconnected.remove(closest)
                call this.connected.add(closest)
                if extra != 0 and GetRandomReal(0,1) <= this.extraChance then
                    call this.connectRooms(start, extra)
                endif
                return true
            endif
        endif
        return false
    endmethod

    private static method generateSub takes nothing returns nothing
        local thistype this = thistype.temp
        if this.state == 0 then
            if I2R(this.dug)/I2R((this.maxx-this.minx)*(this.maxy-this.miny)) > this.roomPercentage or this.rooms >= this.maxRooms or not this.generateRoom() then
                set this.state = 1
            endif
        elseif this.state == 1 then
            if not this.generateCorridor() then
                set this.state = 2
            endif
        elseif this.state == 2 then
            set this.finished = true
        endif
        if not this.finished then
            call TriggerExecute(this.trig)
        endif
    endmethod

    method generate takes nothing returns nothing
        set thistype.temp = this
        call TriggerExecute(this.trig)
    endmethod

    method connectClosestRoom takes integer x, integer y returns boolean
        local RoomListIterator iter = this.connected.iterator()
        local Room current = 0
        local Room closest = 0
        local real distance
        local real closedist = DUNGEON_SIZE_X*DUNGEON_SIZE_Y
        loop
            exitwhen iter.hasNoNext()
            set current = iter.next()
            set distance = SquareRoot((current.centerx-x)*(current.centerx-x) + (current.centery-y)*(current.centery-y))
            if distance < closedist then
                set closedist = distance
                set closest = current
            endif
        endloop
        call iter.destroy()
        if closest != 0 then
            set current = Room.create(x,y,x,y)
            call this.connectRooms(closest, current)
            call current.destroy()
            return true
        endif
        return false
    endmethod

    static method create takes integer x1, integer y1, integer x2, integer y2, integer roomAttempts, integer roomsMax, real percent, boolean nonRectangular, integer min, integer width, integer height, real extraCorridorChance, real extraDeadendChance returns thistype
        local thistype this = thistype.allocate()
        set this.connected = RoomList.create()
        set this.unconnected = RoomList.create()
        set this.minx = x1
        set this.maxx = x2
        set this.miny = y1
        set this.maxy = y2
        set this.dug = 0
        set this.state = 0
        set this.rooms = 0
        set this.allowIrregular = nonRectangular
        set this.maxRoomAttempts = roomAttempts
        set this.maxRooms = roomsMax
        set this.roomPercentage = percent
        set this.minSize = min
        set this.maxWidth = width
        set this.maxHeight = height
        set this.extraChance = extraCorridorChance
        set this.extraDead = extraDeadendChance
        set this.finished = false
        set this.trig = CreateTrigger()
        call TriggerAddAction(this.trig, function thistype.generateSub)
        return this
    endmethod
endstruct


endlibrary
 

Attachments

  • DungeonGenerator.w3x
    393 KB · Views: 383
Last edited:

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
library DungeonStamp

Configurable constants:

constant integer TERRAIN_DEFAULT_TILE = 'Ddrt' defines the default ground tile for the dungeon
constant integer TERRAIN_DEFAULT_VARIANCE = 17 defines the variation used for the default tile (use -1 for random)
constant integer STAMP_SIZE = 5 defines the edge size of each stamp; must be an odd number
constant integer STAMP_SIZE_SQUARED = 25 please calculate STAMP_SIZE*STAMP_SIZE and enter the result here
limits: STAMP_SIZE_SQUARE * number of registered stamps in the system must be smaller than 8192.​
  • So for a STAMP_SIZE of 5, this allows a couple hundreds of registered stamps.
  • Please note that the text registry (see the function API below) is only available for STAMP_SIZE = 5.
constant integer MAX_DESTRUCTABLES_PER_STAMP = 25 defines the maximum number of destructables per stamp
limits: MAX_DESTRUCTABLES_PER_STAMP * number of registered stamps in the system must be smaller than 8192.​
  • So for a value of 25, this allows a couple hundreds of registered stamps.
  • Please note that the text registry (see the function API below) is only available for MAX_DESTRUCTABLES_PER_STAMP = 25.
constant string DUNGEON_PRINT_DIRECTORY = ".\\save\\" is the directory where all generated text files from the print commands will be saved.
Use a dot at the beginning to save the files relative to the Warcraft III directory.​




struct stamp

static method create takes integer shp, integer tileset, real rarity, integer customdata, real customvalue returns thistype
Creates a new stamp and sets it's properties.
This method will not write any struct members and requires manual registering of destructables and ground tiles by code.
If you want to create stamps with the required data automaticly, use .register instead.​
  • shp:
Select a SHAPE one of the SHAPE identifiers; see list below​
  • tileset:
Allows entering an integer to create "dungeon themes".
For example, a fire-based theme could be tileset = 1, a water-based theme could be tileset = 2​
  • rarity:
Allows entering a value between 0 and 1 to define the weight of this tile compared to other tiles of the same shape and tileset.
This is interesting if you want multiple variations of the same stamp, but want one variation much rarer than the other.
So if you have one stamp with a rarity of 1 and one stamp with a rarity of 0.5, the second stamp will only be placed in 25% of cases.​
  • customdata and customvalue:
Allows entering a custom integer and a custom real value that will be associated to the stamp.
These values can be used for whatever the user wants and serve no pre-defined purpose.
For example, the user could use the custom real to set a spawn rate for creatures/items for that tile.
The integer also allows associating a struct to a stamp.​

static method register takes rect which, integer shp, integer tileset, real rarity, integer customdata, real customvalue returns thistype
Same as .create, but this will also automaticly "scan" a preplaced tile/destructable layout on the map and write all the struct members automaticly.
This is your go-to method to add new stamps!​
  • which:
Place a rect on top of the area you want to register as a new stamp.
Make sure the rect has the correct size:
Width/Height of the rect = STAMP_SIZE*128​

static method setDestructableData takes integer raw, real scale, real z, boolean alive returns nothing
Destructables created by placing stamps will default to a scale of 1, be placed directly on the ground and will be created in the alive state.
This method allows registering different values for all destructables with the specified rawcode.​

static method getDestructableScale takes integer raw returns real
static method getDestructableZ takes integer raw returns real
static method getDestructableAlive takes integer raw returns real
These methods are the reverse and will retrieve the specified values.​

static method remove takes rect area, integer gridX, integer gridY returns nothing
Removes all constructed destructables and ground tiles of a stamp in the selected area.
This method takes GRID coordinates, not game-coordinates.​
  • area:
Pass a rect to determine the area containing your GRID.
Most likely, this will be the rect spanning your entire dungeon area.​
  • gridX/Y:
Defines the stamp to be removed by GRID coordinates. 0,0 will remove the bottom left stamp. 0,1 will remove the stamp above, etc.​

method canHaveStairs takes nothing returns boolean
Returns true if the stamp is also eligible for being replaced by a shape containing stairs.
For simplicity reasons, only single-wall, deadend and hall stamps are allowed for stair shapes.​

method place takes rect area, integer gridX, integer gridY, integer orientation returns nothing
Drops all destructables and tiles registered to the stamp at the designed GRID coordinates.​
  • area:
Pass a rect to determine the area containing your GRID
Most likely, this will be the rect spanning your entire dungeon area.​
  • gridX/Y:
Defines where the stamp should create tiles and destructables by GRID coordinates.
1 GRID coordinate equals STAMP_SIZE * 128 in ingame-coordinates.​
  • orientation:
Use one of the following 4 orientation constants here to turn the stamp by 0°,90°,180° or 270°.
Supported orientation constants:
ORIENTATION_0
ORIENTATION_90
ORIENTATION_180
ORIENTATION_270

static method placeByLogic takes rect area, integer x, integer y, boolean isCave, boolean isStairs, boolean isUp, integer fromTileset, boolean sw, boolean w, boolean nw, boolean s, boolean c, boolean n, boolean se, boolean e, boolean ne returns thistype
Drops destructables and tiles registered to a stamp at the designed GRID coordinates.
Unlike .place, this method does not require knowing the stamp before dropping it's contents.
Instead, this method will apply a certain logic to determine which stamp to select from the input parameters.​
  • area:
Pass a rect to determine the area containing your GRID
Most likely, this will be the rect spanning your entire dungeon area.​
  • x/y:
Defines where the stamp should create tiles and destructables by GRID coordinates.
1 GRID coordinate equals STAMP_SIZE * 128 in ingame-coordinates.​
  • isCave:
If true, the stamp will be selected from the CAVE stamps instead of the DEFAULT stamps.​
  • isStairs:
If true, the stamp will be selected from the STAIR stamps, but only if the stamp is eligible for stairs.
For simplicity reasons, only single-wall, deadend and hall stamps are allowed for stair shapes.
In case the input parameters wouldn't support a STAIR stamp, it will just create the normal stamp instead.​
  • isUp:
If isStairs is true, this will determine if the staircase should go up or down.​
  • fromTileset:
Only selects stamps from the specified tileset identifier. If the system can not find a stamp from the specified tileset, it will use the default instead.​
  • sw,w,nw,s,c,n,se,e,ne:
Pass true for any of these values depending on if the neighbour of the stamp is a wall or blocked off.
The algorithm will then select a stamp shape automaticly depending on which areas in the neighbourhood of the stamp are blocked.​

method print takes nothing returns nothing
Allows to print all data from the stamp into a .txt file of specified filepath.
This textfile will contain the raw vJASS commands to register the stamp by text input instead of placing it directly on your map.
This is great for exchanging tile data between maps or if you don't have enough space for all stamps on your map.
Just .print the stamp, copy & paste the vJASS code in your map in and you can safely remove the stamp from your map!​

method registerTerrain
method registerVariation
method registerDestructable
method registerDestX
method registerDestY
method registerDestFace
These methods take 25 parameters each and allow to manually register a stamp without having to place it on your map.
Designed for use with the .print method above.




List of availables SHAPES for the .create and .register method:

JASS:
    constant integer SHAPE_BLACK = 0
    constant integer SHAPE_HALL = 1                 //  Default Orientation:
    constant integer SHAPE_WALL_L = 2               //              I       = 0°    (left wall)
    constant integer SHAPE_WALL_L_B = 3             //              I_      = 0°    (left wall and bottom wall)
    constant integer SHAPE_WALL_L_B_R = 4           //              I_I     = 0°    (left wall, bottom wall and right wall (dead end))
    constant integer SHAPE_WALL_BL = 5              //              .       = 0°    (wall in bottom left corner)
    constant integer SHAPE_WALL_BL_TL = 6           //              :       = 0°    (wall in bottom left and top left corner)
    constant integer SHAPE_WALL_BL_TR = 7           //              . '     = 0°    (wall in bottom left and top right corner)
    constant integer SHAPE_WALL_BL_TL_BR = 8        //              : .     = 0°    (wall in bottom left, top left and bottom right corner)
    constant integer SHAPE_WALL_BL_TL_BR_TP = 9     //              : :     = 0°    (wall in all corners, plus-shaped corridor)
    constant integer SHAPE_WALL_L_BR = 10           //              I .     = 0°    (left wall and bottom right corner)
    constant integer SHAPE_WALL_L_TR = 11           //              I '     = 0°    (left wall and top right corner)
    constant integer SHAPE_WALL_L_R = 12            //              I I     = 0°    (left wall and right wall)
    constant integer SHAPE_WALL_L_B_TR = 13         //              I_'     = 0°    (left wall, bottom wall, top-right corner)
    constant integer SHAPE_WALL_L_BR_TR = 14        //              I :     = 0°    (left wall, bottom-right corner and top-right corner)

    constant integer SHAPE_STAIRS_UP_WALL = SHAPE_WALL_L + STAIR_UP_OFFSET
                                                            //              I>      = 0°    (Stairs in western wall, poiting east)
    constant integer SHAPE_STAIRS_UP_HALL = SHAPE_HALL + STAIR_UP_OFFSET
                                                            //              >       = 0°    (Stairs inside room, pointing east)
    constant integer SHAPE_STAIRS_UP_END  = SHAPE_WALL_L_B_R + STAIR_UP_OFFSET
                                                            //              I^I     = 0°    (Stairs at dead end, pointing north)

    constant integer SHAPE_STAIRS_DOWN_WALL = SHAPE_WALL_L + STAIR_DOWN_OFFSET
                                                            //              I>      = 0°    (Stairs in western wall, poiting east)
    constant integer SHAPE_STAIRS_DOWN_HALL = SHAPE_HALL + STAIR_DOWN_OFFSET
                                                            //              >       = 0°    (Stairs inside room, pointing east)
    constant integer SHAPE_STAIRS_DOWN_END  = SHAPE_WALL_L_B_R + STAIR_DOWN_OFFSET
                                                            //              I^I     = 0°    (Stairs at dead end, pointing north)

    /*
        These are the stamp shapes for the cavern type
    */
    constant integer SHAPE_CAVE_HALL = 1+CAVE_OFFSET                 //  Default Orientation:
    constant integer SHAPE_CAVE_WALL_L = 2+CAVE_OFFSET               //              I       = 0°    (left wall)
    constant integer SHAPE_CAVE_WALL_L_B = 3+CAVE_OFFSET             //              I_      = 0°    (left wall and bottom wall)
    constant integer SHAPE_CAVE_WALL_L_B_R = 4+CAVE_OFFSET           //              I_I     = 0°    (left wall, bottom wall and right wall (dead end))
    constant integer SHAPE_CAVE_WALL_BL = 5+CAVE_OFFSET              //              .       = 0°    (wall in bottom left corner)
    constant integer SHAPE_CAVE_WALL_BL_TL = 6+CAVE_OFFSET           //              :       = 0°    (wall in bottom left and top left corner)
    constant integer SHAPE_CAVE_WALL_BL_TR = 7+CAVE_OFFSET           //              . '     = 0°    (wall in bottom left and top right corner)
    constant integer SHAPE_CAVE_WALL_BL_TL_BR = 8+CAVE_OFFSET        //              : .     = 0°    (wall in bottom left, top left and bottom right corner)
    constant integer SHAPE_CAVE_WALL_BL_TL_BR_TP = 9+CAVE_OFFSET     //              : :     = 0°    (wall in all corners, plus-shaped corridor)
    constant integer SHAPE_CAVE_WALL_L_BR = 10+CAVE_OFFSET           //              I .     = 0°    (left wall and bottom right corner)
    constant integer SHAPE_CAVE_WALL_L_TR = 11+CAVE_OFFSET           //              I '     = 0°    (left wall and top right corner)
    constant integer SHAPE_CAVE_WALL_L_R = 12+CAVE_OFFSET            //              I I     = 0°    (left wall and right wall)
    constant integer SHAPE_CAVE_WALL_L_B_TR = 13+CAVE_OFFSET         //              I_'     = 0°    (left wall, bottom wall, top-right corner)
    constant integer SHAPE_CAVE_WALL_L_BR_TR = 14+CAVE_OFFSET        //              I :     = 0°    (left wall, bottom-right corner and top-right corner)

    constant integer SHAPE_CAVE_STAIRS_UP_WALL = SHAPE_WALL_L + STAIR_UP_OFFSET + CAVE_OFFSET
                                                            //              I>      = 0°    (Stairs in western wall, poiting east)
    constant integer SHAPE_CAVE_STAIRS_UP_HALL = SHAPE_HALL + STAIR_UP_OFFSET + CAVE_OFFSET
                                                            //              >       = 0°    (Stairs inside room, pointing east)
    constant integer SHAPE_CAVE_STAIRS_UP_END  = SHAPE_WALL_L_B_R + STAIR_UP_OFFSET + CAVE_OFFSET
                                                            //              I^I     = 0°    (Stairs at dead end, pointing north)

    constant integer SHAPE_CAVE_STAIRS_DOWN_WALL = SHAPE_WALL_L + STAIR_DOWN_OFFSET + CAVE_OFFSET
                                                            //              I>      = 0°    (Stairs in western wall, poiting east)
    constant integer SHAPE_CAVE_STAIRS_DOWN_HALL = SHAPE_HALL + STAIR_DOWN_OFFSET + CAVE_OFFSET
                                                            //              >       = 0°    (Stairs inside room, pointing east)
    constant integer SHAPE_CAVE_STAIRS_DOWN_END  = SHAPE_WALL_L_B_R + STAIR_DOWN_OFFSET + CAVE_OFFSET
                                                            //              I^I     = 0°    (Stairs at dead end, pointing north)


library DungeonGenerator

Configurable constants:

constant integer DUNGEON_SIZE_X = 64
constant integer DUNGEON_SIZE_Y = 64
These two values define the GRID dimensions of the dungeon field.
Ingame coordinates can be calculated by DUNGEON_SIZE_X * TILE_SIZE * 128
As you can see, a DUNGEON_SIZE of 64 GRID coordinates for the default stamp size of 5 is massive and fits only into a 480x480 map.

constant real DUNGEON_VERIFICATION_THRESHOLD = 0.1
This value determines the fraction of the map that must be reachable by units before the verify method accepts it as a usable map.
This is to prevent disjoint dungeons for low density designs.
constant integer MAX_VERIFY_ATTEMPTS = 10
This is the amount of retries for the verify method, before it will give up on finding a usable part of the dungeon.

struct Room
struct RoomList
struct RoomListIterator
These structs are used internally by the system and will most likely never be important for any user but those who want to break the system or tinker around.

function GetLastCreatedStairs takes boolean up returns location
This function will return a location at the center of the last created set of stairs up or down.
  • up:
Determines if returned location is for the last created upstairs or downstairs shape.​



struct Dungeon


static method isVerified takes integer x, integer y returns boolean

  • x,y:
Tests if the GRID coordinates for the generated dungeon field are reachable by units after using .verifyMap().​

static method getTile takes integer x, integer y returns integer
  • x,y:
Returns the tiletype of the tested position in the dungeon field.
Returned tiletypes are:
DUNGEON_EMPTY = 0
DUNGEON_ROOM = 1
DUNGEON_CAVE = 2
DUNGEON_CORRIDOR = 3


static method isWall takes integer x, integer y returns boolean
Checks if the tested position in the dungeon field equals DUNGEON_EMPTY.
  • x,y:
Tested position in the dungeon field by GRID coordinates.​


static method getAdjacentWalls takes integer x, integer y, integer radius returns integer
Returns the number of adjacent positions in the dungeon field that equal DUNGEON_EMPTY.
  • x,y:
Tested position in the dungeon field by GRID coordinates.​
  • radius:
How large the tested square should be.
radius = 1 only checks the 8 directly adjacent positions.
radius = 2 checks the 24 closest neighbouring positions.​

static method enumerateMap takes rect area, code actionFunc returns nothing
Enumerating all stamps of a generated dungeon map, just like you would enumerate units or destructables by defining a function to be called for each stamp.
  • area:
Rect to be checked for placed stamps.​

Inside the enumeration callback, you can use the following functions to refer to the stamp being enumerated:
function GetEnumStamp takes nothing returns stamp
function GetEnumStampData takes nothing returns integer
function GetEnumStampValue takes nothing returns real
function GetEnumStampCenterX takes nothing returns real
function GetEnumStampCenterY takes nothing returns real


static method removeAll takes rect area returns nothing
Removes all placed tiles and destructables inside an enumerated area.
  • area:
Rect to be checked for placed stamps.​

static method clearMap takes nothing returns nothing
Flushes the currently generated dungeon map and resets every field position to DUNGEON_EMPTY.
This will only remove internal dungeon map data and will not remove any placed destructables or tiles.

static method verifyMap takes nothing returns nothing
Tests the generated map for usability.
Both available generators can sometimes create disjoint parts.
  • The verification process will select a random point of the generated dungeon map that is not flagged as DUNGEON_EMPTY and will then use a floodfill algorithm to detect all positions that are directly reachable from this position without having to go through walls.
  • If the fraction of reachable positions compared to the size of the map is less than DUNGEON_VERIFICATION_THRESHOLD, it will repeat the verification process up to MAX_VERIFY_ATTEMPTS times.
  • After finishing the verification process (no matter if successful or not), all reachable parts of the map will be flagged as verified.
  • Afterwards, you can use static method isVerified to determine if a grid position is accessable or not.

static method isMapUsable takes nothing returns boolean
Can only be used after the verification of a map.
Returns true if the verification attempt was successful and the map has more than DUNGEON_VERIFICATION_THRESHOLD of reachable parts.

static method clearUnverified takes nothing returns nothing
Can only be used after the verification of a map.
This method will clear all unreachable parts from the dungeon map and overwrite them with the DUNGEON_EMPTY flag.

static method printMap takes nothing returns nothing
This method will print the generated dungeon map into a .txt file for quick analysis.
  • You can use this method at any point after a .generate() call. This saves of lot of processing time since you do not have to .build() a dungeon before checking out how it looks.
  • Great for rapid prototyping or finding out how the input parameters affect the dungeon algorithms!

static method build takes rect area, integer tileset, code actionFunc returns nothing
This method will deploy the builder and place all destructables and tiles based on the stamp and dungeon map rules.
This process is heavy on runtime. Depending on the size of the map, it might cause a small lag of several seconds.
This is perfectly normal and nothing to worry about.
Also remember that unlike all the other methods, building is NOT instant and will not be finished before the next line of code.
This is why it allows specifying a custom callback function just like a timer.
If you want to do something right after finishing the dungeon builder, simply put it into the callback function.
  • area:
The rect that spans the entire dungeon. All dungeon map data outside of this rect will not be considered, so make sure it is at least as large as your dungeon map.​
  • tileset:
Specifies which stamps should be selected by tileset identifier. If it can not find stamps of the specified tileset identifier, the build algorithm will use the default instead.​
  • actionFunc:
The custom callback function that should be called after the dungeon builder has finished. This can be used to move your heroes to the last created staircase or generate the units and items for the dungeon.​





Available dungeon generator algorithms:
Currently, there are only two algorithms available: a normal generator for rooms and corridors and a generator for cave-like patterns.
Both have many available methods for those who like to tinker around. However, for most applications, only the following will be needed:


struct DungeonUniform

static method create takes integer x1, integer y1, integer x2, integer y2, integer roomAttempts, integer roomsMax, real percent, boolean nonRectangular, integer min, integer width, integer height, real extraCorridorChance, real extraDeadendChance returns thistype
  • x1,y1,x2,y2:
The GRID coordinates of the lower left and top right corner of the dungeon (not game coordinates!).
This is useful because you might not want the generator to process the entire dungeon map and create some parts of the map with a different generator.​

The following three parameters define the break condition for the room generation part of the algorithm; whatever is reached first.
  • roomAttempts:
The algorithm will randomly place rooms at the beginning. This parameter defines how many attempts it will run before a room is considered unplacable.​
  • roomsMax:
The maximum number of rooms to be placed.​
  • percent:
The fraction of the total dungeon map that is supposed to be filled with rooms.​

  • nonRectangular:
Rooms will be discarded if they intersect an already placed rooms, except if this option is enabled.
In this case, they will be merged with the existing room to create non-rectangular rooms.​
  • min:
Defines the minimum room size in GRID positions.
A value of 3 means the minimum room size is 3x3 stamps.​
  • width/height:
These values define the maximum room width and height in GRID positions.​
  • extraCorridorChance:
The generator will only try to connect rooms with the minimum amount of corridors possible to make the map fully reachable by default.
This parameter sets the chance for an extra corridor to spawn for each room.​
  • extraDeadendChance:
The generator will only create corridors to link the two closest rooms each by default. Which means that there are never any dead ends by default.
This parameter sets a chance to dig an extra corridor in a random direction that might have a dead end.​


method generate takes nothing returns nothing
This will fire the generator and write the generated layout into the dungeon map.

method connectClosestRoom takes integer x, integer y returns boolean
This method allows to connect a specified GRID position with the closest nearby room.
This can be used to connect a seperately generated dungeon part with another one inside the same dungeon map.
It can also be used to open an "entry" to the outside world by digging a corridor to a fixed point in your design.


struct DungeonCavern
The cavern generator applies cellular automata to generate natural looking caves. This is done by first generating a random distribution of rooms to walls.
Then, it will apply a number of "evolving" stages in which a position will either become a wall or a room depending on the number of walls it has a neighbours.
After a certain amount of generations, you will always end up with a cavernous design instead of the white noise created by pure random distribution.
This generator should always be used before the uniform dungeon generator, since it requires a blank map to work properly.

static method create takes integer x1, integer y1, integer x2, integer y2, integer wallPercent, boolean horizontalBlank, integer cuthigh, integer cutlow, integer phases, integer stopLowcutAfter returns thistype
  • x1,y1,x2,y2:
The GRID coordinates of the lower left and top right corner of the dungeon (not game coordinates!).
This is useful because you might not want the generator to process the entire dungeon map and create some parts of the map with a different generator.​
  • wallPercent:
Determines the percentage of positions that should be considered walls in the first generation. Typical values: 40-50.
Typically a larger value will create less and smaller rooms. A smaller value will tend to create larger, possibly blocky rooms after a few generations.​
  • horizontalBlank:
Depending on the initial wall percentage and the amount of evolving generations applied, the algorithm tends to form vertical walls, isolating cave sections from another.
If this parameter is set to true, it will introduce a horizontal blanked-out line in the first generation, which will reduce the likelyhood of that to happen.
However, it will also slightly reduce the natural feel of the result, since you will most likely get a "web"-style cave with many rooms connected to many other instead of getting more remote locations aswell.​
  • cutHigh:
If a position has more adjacent walls than this value within a radius of 1, if will become a wall in the next generation.
A lower value will create smaller rooms. A higher value will create larger rooms. Typical values: 4-6.​
  • cutLow:
If a position has less adjacent walls than this value within a radius of 2, if will become a wall in the next generation.
A higher value will prevent rooms getting too large and will add some natural noise to created rooms. Typical values: 0-3.​
  • phases:
Determines the amount of evolving stages applied. The more phases applied, the more "round" a cave will look like. Lower values will create edgy, more chaotic caves. Typical values: 3-6.​
  • stopLowcutAfter:
After this amount of evolving stages, the cutLow value will be reset to 0. This is great if you don't want to create too much "white noise" by the lowcut rule in the final result. Typical values: phases - 1​

method generate takes nothing returns nothing
This will fire the generator and write the generated layout into the dungeon map.
 
Last edited:

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Dynamic Dungeon Generation - TUTORIAL


Yes, I understand. You went through the API and told yourself: I have no idea what is going on, right?
Well, don't worry, I got you covered!
Since I was implementing this thing into Gaias Retaliation ORPG anyway, I figured: why not just write down all the steps I take as a tutorial?

Just follow these steps and you will have your dungeon set up in no time.

--------------------------------------------------



Step I: Preparations

First and foremost, we need to decide where we want to put our randomized dungeon.
This is important, because we need to know how large our dungeon must be for the system to create proper maps. If you want more than just one randomized dungeon on your map, just measure the largest area you have. It's easier to downscale than to upscale.

So, here I will start by finding an empty area of the map.

I found a nice, large spot at the southwestern part of the map. First, let's create the region we will use later to adress the dungeon area.
Draw a region, but make sure that it's size are multiples of 640 coordinates.

Simply draw a rect, press 'enter' and set up its coordinates manually. Do some calculus to find the right size. Also make sure it's not too close to the border of the map, so that players won't get issues with the camera bounds.
Take the difference between upper and lower, such as the left and right bounds of the region and divide it by 640. The result should be a whole number; if not, adjust the size until it fits.
Also, don't forget to name your region. Let's go with "Dungeon Area" for now.

Step1_Region.jpg

Here, we got ourselves a nice 17x18 dungeon map. Large enough for complex patterns, but small enough to not get too boring.


Now, we go into the trigger editor and import our scripts:
Create two triggers called "DungeonStamp" and "DungeonGenerator", convert them to custom text and replace everything by the two system scripts in the thread opener.

Next go into "DungeonGenerator" and set the DUNGEON_SIZE_X/Y variables to what you calculated before.

Step1_Config.jpg

Next, go into "DungeonStamp" and set TERRAIN_DEFAULT_TILE to whatever tile you want to use as a basis for the dungeon.
To find out the correct id, just create another trigger in GUI and select the action "Environment - Set Terrain Type" and pick the tile you want. Then convert it to custom text and the JASS command will show you the correct id.

For TERRAIN_DEFAULT_VARIANCE, you can select one tile variation you like, or just enter -1 for using random variance.

Step1_Config2.jpg

In my example, I just selected a tile I overwrote with some neat and simple black texture, but anything is fine, really.

And that's it for the configuration already. Most of the other settings are already in the ballpark and shouldn't be touched unless you know what you're doing.




Step II: Creating the first stamp

Now that we prepared the generator, it's time to get artistic!

Move back to where you created your dungeon region and create a new region on top of it (be careful not to accidentally move your dungeon region in the process).
Your new region should be exactly 640x640 in size. Make sure to calculate your min and max bounds properly!
Also, don't forget to name it. Let's call it "DungeonStamp01".

Now go to "view" and enable "Terrain grid - medium" if you haven't already.
Make sure that both your Dungeon Area and your newly created region perfectly align with the terrain grid. If the bounds are exactly between two grid lines, move them so they align properly.

Step2_Stamps1.jpg

Now we can start registering our first stamp!

Stamps are pretty much our "puzzle pieces" that we will use to build a good-looking dungeon.
The stamp system will select from a variety of puzzle pieces we registered, use them when required and rotate them if necessary.

But first, we need a default wall stamp. This will be the stamp that gets used for all those areas that should not be walkable by our heroes.
In most cases, simply using black tiles or a black box yields the best-looking results, but you can also get creative and do something completely different, like using an invisible alpha tile and creating the illusion of an endless pit and make the heroes actually walk on bridges over the abyss.
I attached a simple black box model I used in my map. It's already scaled perfectly to fit into the stamp size, so I highly recommend using it.

Click

First, we import that model, restart the editor, then go to the object editor and create a new destructable based on "Visibility Blocker (Big)".
Set it up like in the picture below.

Pay attention to the pathing map. You want a 10x10 default map. There is no GUI-option to pick that, but you can enter it manually by editing the string at the bottom.
And yes, no need to import that. It's in the game files, just not accessable by the GUI.
Make sure that "fog visibility" is enabled, otherwise the model will not get rendered under the fog of war. Also make sure that occluder height is set to 230 so that the destructable actually blocks sight.

Step2_Stamps2.jpg

Now let's place our destructable. The model should perfectly align and be able to fill the entire stamp area with just four destructables without any kind of rescaling.
Make sure that your destructables are placed inside the stamp region you created previously.

Step2_Stamps3.jpg

So now that our stamp is finished, we can register it to the system.
Create a new trigger (let's call it "DungeonReg"), add the "map initialization" event and add the action "Do nothing". Then convert it to custom text.
Replace the "DoNothing" line with the following JASS-script:
call stamp.register(gg_rct_DungeonStamp01, SHAPE_BLACK, 0, 1, 0, 0)

Congratulations, you have now properly registered your new stamp to the system! Don't mind the other parameters of this function for now, we will come to that later.


Step III: Setting up more stamps

Well, obviously, just a piece of pure blackness alone won't create a proper dungeon, right?
So, we need more stamps to make it look right. One for each possible shape our puzzle pieces can have.

Let's go back to the "DungeonStamp" trigger and take a peek into the list of possible shapes.
Here is what you will find there:

JASS:
constant integer SHAPE_BLACK = 0
constant integer SHAPE_HALL = 1  //  Default Orientation:
constant integer SHAPE_WALL_L = 2  //  I  = 0°  (left wall)
constant integer SHAPE_WALL_L_B = 3  //  I_  = 0°  (left wall and bottom wall)
constant integer SHAPE_WALL_L_B_R = 4  //  I_I  = 0°  (left wall, bottom wall and right wall (dead end))
constant integer SHAPE_WALL_BL = 5  //  .  = 0°  (wall in bottom left corner)
constant integer SHAPE_WALL_BL_TL = 6  //  :  = 0°  (wall in bottom left and top left corner)
constant integer SHAPE_WALL_BL_TR = 7  //  . '  = 0°  (wall in bottom left and top right corner)
constant integer SHAPE_WALL_BL_TL_BR = 8  //  : .  = 0°  (wall in bottom left, top left and bottom right corner)
constant integer SHAPE_WALL_BL_TL_BR_TP = 9  //  : :  = 0°  (wall in all corners, plus-shaped corridor)
constant integer SHAPE_WALL_L_BR = 10  //  I .  = 0°  (left wall and bottom right corner)
constant integer SHAPE_WALL_L_TR = 11  //  I '  = 0°  (left wall and top right corner)
constant integer SHAPE_WALL_L_R = 12  //  I I  = 0°  (left wall and right wall)
constant integer SHAPE_WALL_L_B_TR = 13  //  I_'  = 0°  (left wall, bottom wall, top-right corner)
constant integer SHAPE_WALL_L_BR_TR = 14  //  I :  = 0°  (left wall, bottom-right corner and top-right corner)
constant integer SHAPE_STAIRS_UP_WALL = SHAPE_WALL_L + STAIR_UP_OFFSET
  //  I>  = 0°  (Stairs in western wall, poiting east)
constant integer SHAPE_STAIRS_UP_HALL = SHAPE_HALL + STAIR_UP_OFFSET
  //  >  = 0°  (Stairs inside room, pointing east)
constant integer SHAPE_STAIRS_UP_END  = SHAPE_WALL_L_B_R + STAIR_UP_OFFSET
  //  I^I  = 0°  (Stairs at dead end, pointing north)

constant integer SHAPE_STAIRS_DOWN_WALL = SHAPE_WALL_L + STAIR_DOWN_OFFSET
  //  I>  = 0°  (Stairs in western wall, poiting east)
constant integer SHAPE_STAIRS_DOWN_HALL = SHAPE_HALL + STAIR_DOWN_OFFSET
  //  >  = 0°  (Stairs inside room, pointing north)
constant integer SHAPE_STAIRS_DOWN_END  = SHAPE_WALL_L_B_R + STAIR_DOWN_OFFSET

This is basicly our list of possible "puzzle pieces". To make the generator work, you will need at least one stamp for each shape.
At the top of the list, you will find our SHAPE_BLACK we just created.
Our next two shapes therefore are SHAPE_HALL and SHAPE_WALL_L.

SHAPE_HALL is basicly the opposite of SHAPE_BLACK: It's a shape that allows full walkability in all directions.
SHAPE_WALL_L is a shape that has one direction blocked off by a wall: the western wall ("left" => L).

So let's create those two now.


Go back to regions and copy and paste the first stamp region. Let's name them "DungeonStamp02" and DungeonStamp03" and place them next to our first stamp.

Obviously, our SHAPE_HALL will most likely only consist of ground tiles, since it is meant to be fully walkable in all directions. But we can apply some nice ground ornaments via tiles if we feel like it.

SHAPE_WALL_L requires to have a wall blocking the western direction. So let's pick a model suited for it.
For starters, we could begin with a great model collection made by The_Silent, which contains both corner and wall models properly sized to fit our new destructables:
Dungeon Wall [Hell Stone]
Dungeon Wall Corner [Hell Stone]
Dungeon Wall Corner [Hell Stone]

So let's just import these and create new destructables based on the big visibility blocker, just like we did the first time.
Adjust the pathing map to something that fits the models and don't forget to turn that fog visibility on, otherwise your walls will have weird pop-ups under the fog of war.
Also, set the rotation to -1, this will allow us to rotate our new destructables freely.

Then place them in our third stamp region so that they completely block of the western direction.

Step3_More_Stamps.jpg

Looks a bit boring, right? Well, let's spice it up a bit by adding another destructable with a lovely Moria pillar:
AshenObilisk

Again, don't forget the fog visibility, but this time set the occluder height to 0, since the pillar is supposed to be small.
Rescale the pillar until it fits our wall.
For the pathing map, we can use "PathTextures\4x4Column.tga", which has a nice round shape to it; just what we need.

Step3_More_Stamps2.jpg

Now that looks much nicer, doesn't it?

Here is the big issue with setting up stamps, though: There are some things that the system can not detect via script.
These things are: Facing, the z-coordinate and the destructable scale.

Wait, what? Facing? Isn't that a problem for us, if we want the stamp to be turned around if needed?
And you are totally right about that! However, when creating this system, I applied a small workaround to overcome that issue.
Instead of only setting the rotation value, you also have to set the life percentage of the destructable to the rotation value you need.

Step3_More_Stamps3.jpg

So, let's select the walls, press "enter" and set the life percentage.
Now here are two problems: Obviously, we can not enter values over 100. So when I wrote the script, I simply designed it with the convention that you divide the degrees by 10 and enter that.
So for a rotation value of 270°, enter 27% life, for 180°, enter 18% and for 90°, enter 9%.
Remember that 0° equals 360°, so if you need a 0° orientation, enter 36%.

Now let's fix the scaling issue with the pillar. Obviously, we can't use the life value to fix that again, but since we likely want every destructable of the same type have the same scale, I just added a small function that allows to enter custom scaling and height values.

So let's go back to our registry trigger and add the following line:
call stamp.setDestructableData('B02F', 0.60, 0, true)
This will register a scaling value of 0.6 for destructables of type 'B02F' to the system.
Of course, your destructable will have a different rawcode, so enter that instead of 'B02F'.

Notice the other two parameters we haven't touched? Well, the parameter after the scaling value allows setting up a custom destructable placement height. This can be useful for stuff that is supposed to "fly" or hang on the walls, like torches.
Also, there is a boolean parameter at the end of the function. This one determines if the destructable should be created in it's alive state or dead state.
Set this to "false" and the destructable will be created in dead state. True for alive. This can be useful for creating opened & closed destructable doors.

Step3_More_Stamps4.jpg

When we are finished with setting up the pillar destructable, let's not forget to register our newly created stamps aswell!
call stamp.register(gg_rct_DungeonStamp02, SHAPE_HALL, 0, 1, 0, 0)
call stamp.register(gg_rct_DungeonStamp03, SHAPE_WALL_L, 0, 1, 0, 0)


Well done! You now know everything you need to know to setup all the stamps required!
Just check out the comments in the SHAPE list to see what the requirement for that title are, but the naming convention is pretty much self-explanatory:
L = Left wall
B = Bottom wall
R = Right Wall
T = Top wall
BL = Bottom left corner
TL = Top left corner
BR = Bottom right corner
TR = Top right corner
These suffixes will tell you which parts of the shape should be blocked off by destructables.

Remember that there are three variations of stair stamps aswell, that follow the same rules. Stair stamps are different in that every dungeon will have exactly one Stair Up stamp and one Stair Down stamp placed by default.
You can use these for whatever you want as an entry or point-of-interest in your dungeon. These could be portals that get the player to the next level. Or these could be just stairs.

Notice how there is also a second set of SHAPEs in the DungeonStamp globals?
Well, here is good news: Each tileset actually allows having two different variants; a "dungeon" variant that we just created and a "cave" variant.
And of course, you don't want dungeon walls for a cave, right?
So, if you want to use the generator to also create natural looking caves, you can do so by setting up the extra shapes for the cave variant!
The logic applied to the shapes is exactly the same as for dungeons. It's just about setting up more stamps and make them look natural and seamless.


Congratulations! You just finished the stamp part of dungeon generation. Set up at least one stamp for each shape, then proceed to the next part of the tutorial!
Remember to always set the life percentage of destructables to the required rotation value, if the destructable can be turned!




Step IV: Tileset, Rarity and Custom Data

Phew, we did it; we register one stamp for each shape of the dungeon type (I didn't add the cave shapes, though, but we won't need them for now).

Here is some screens of how these shapes could look like when you're done.

Step4_more_shapes.png

The stairs downwards were a bit tricky to make, since the ground has to be flat; but by using the mighty Alpha tile, we actually pulled it off fine.

Now let's take a look in the registry, shall we?

Step4_registry.png

See those values at the end we ignored up until now? Time to learn about those!
As you can see, the first integer is called "Tileset". It is basicly just a number you can use to create a "set" of stamps that always go together. As long as stamps of the requested identifier are available, the system will always select these. For example, we could create another set of stamps with blue tinting, add some ice destructables aswell and give them the tileset identifier "1" instead of "0". Then, when a dungeon requests the tileset "1", it will only pick from the stamps grouped in the same set.

If a tileset is incomplete or missing stamps, it will use the first ever registered stamp of that shape as a default. So going as basic as possible for our first tileset is always a good idea.


Next up is "Rarity", a real variable that allows specifying the weight of a stamp. You can use this when you want to register more than one stamp of the same shape to the same tileset, to allow for more visual variety. By setting the rarity value to some value between 0 and 1, we can make that extra stamp rarer than the other registered stamps of the same shape.

Let's say we want to add another stamp for the SHAPE_HALL, since large halls will look like crap without having at least a bit of variety in design. I place another set of tiles and destructables and register the new stamp just like I did the first time. But this time, I want this SHAPE to only be picked 25% of the time. If I set the rarity to 1 again, both stamps would be just as likely and be picked 50% of the time. But we want this one to be rarer than that. So I set the rarity to 0.5. Now, my second stamp will only be half as likely as before, resulting in a distribution of 75%/25% for my first and my second stamp:

call stamp.register(gg_rct_DungeonStamp02, SHAPE_HALL, 0, 1, 0, 0)
call stamp.register(gg_rct_DungeonStamp22, SHAPE_HALL, 0, 0.5, 0, 0)


I highly recommend registering 2-3 extra stamps each for the following shapes: SHAPE_HALL, SHAPE_WALL_L and SHAPE_WALL_L_R. These are by far the most common shapes used by the algorithm, so make sure you create some visual variety here! You could add some pillars in one or add some extra decoration? Or maybe change the way how the walls go through the stamp. Your imagination is the limit.



Last but not least, let's talk the last two parameters.
These allow defining a custom integer and a custom real value for later use. These parameters have no effect by default and are just something added for your convenience! Later, when our dungeon is finished, we can use these two values for whatever we want to populate our dungeon with creatures and establish spawning rules, etc.
For example, I could decide to use the real value as a spawning chance for creatures and use the integer value as the maximum level of the creature spawned. Again, time to get creative!

In the next part of the tutorial, we will finally create our first dungeon. Let's do this!


Step V: Building


First, create a new trigger for testing; let's call it "DungeonTest" or whatever.
Add the event "player enters chat message containing (exact match) "-dungeon".
Add the "Do Nothing" action, then convert the trigger to custom text.

Replace the "DoNothing()" call will the following line:

local DungeonUniform newdung = DungeonUniform.create(0,0,17,18, 10,10,0.25,true,2,5,5,0.1,0.2)

Cool! But, wait, obviously, we need to explain what each value does, since your dungeon will not have the same dimensions as mine, right?

So let's go through that one by one. We start with the first four numbers:

0,0,17,18
These are our bottom left (x=0,y=0) and top right (x=17,y=18) corner of the created dungeon. Remember; these will not take ingame coordinates, but grid coordinates inside our dungeon area.
So 0,0 will be the bottom left stamp and DUNGEON_SIZE_X,DUNGEON_SIZE_Y will be the top right stamp. Each stamp placed increments a coordinate by 1.
So you can find your "real world" dimensions by just taking the minimum bounds of your dungeon region and adding our grid coordinates multiplied by 640.

10,10,0.25
The next three values determine the room placement logic.
The first number decides how often the system will try to place a room before it gives up and considers the map as completed. This could happen if your map is already full of rooms and there is no more space for further rooms.
The second number determines the maximum number of rooms placed. If the algorithm hasn't given up until this point, it will definitely stop after placing this number of rooms. This is great if you want a layout with only a few scattered rooms.
The third number determines the fraction of the area that should be filled with rooms. A value of 0.25 means: if the algorithm hasn't given up until filling 25% of the map with rooms, it will stop now. This is great if you want a variety of different sized rooms, but don't want the map too dense after getting a huge room by the algorithm.

true
The boolean determines if the system is allowed to place two rooms above each other. This will most likely result in non-rectangular rooms to be created. Depending on if you want non-rectangular rooms or not, you can switch this option off if you want.
I'll leave it at true because rectangular rooms are boring.

2,5,5
These values determine the size of the created rooms. The first value is the minimum size a room must have. A value of 2 means a 2x2 sized room.
The next two numbers determine the maximum width and height of a room. If your dungeon area is very "stretched" in x-direction, you might want to have rooms that have larger dimensions in width than height.
My area is pretty much a perfect square, so I decided to have both values at 5, so my rooms can be between 2x2 and 5x5 in size.

0.1,0.2
The last two values are some flavor settings. By default, a room will only connect with it's closest neighbour. The first value determines the chance that the system spawns an extra redundant corridor that connects the room also with the second closest room. Setting this value higher than 0 will result in a more web-like architecture, whereas a value of 0 will create a more maze-like dungeon. I selected 0.1 (=10% chance per room) since we want a more linear experience.
The second value adds a chance to spawn an extra corridor in a random direction that will not purposely try to connect rooms. So, depending on the density of rooms in your map, this will create some extra dead-end corridors. I selected a healthy value of 0.2 (=20% per room) since dead ends are perfect for hiding treasure or strong creatures.


So, we got that one down. Don't forget to change the minimum and maximum coordinates to match your DUNGEON_SIZE limits!

Let's go to the next command. Add the following lines below the first:
call Dungeon.clearMap()
call newdung.generate()
The first line will clear the internal dungeon map memory, since we want a blank map to start with.
The second will start the dungeon generation and will write the new layout into the cleared memory. It will not yet create any objects, though.

Before we create any objects, we need to clean up the stamps that we preplaced, since they take up precious space in our dungeon area.
Don't worry, since we already registered these stamps at map initialization, they are basically useless now and can be safely deleted.

So we add another command:
call Dungeon.removeAll(gg_rct_Dungeon_Area)
This will clean a rect of all preplaced destructables and ground tiles, leaving us with some fresh space to use for our new dungeon!

Next, we we need to verify our created dungeon map.
Verification is a process that selects random coordinates in your Dungeon and tries to connect these points with others by "walking" through the layout.
If a part is cut off for whatever reason, the verification process will find these parts and mark them as unreachable. This is useful, because we do not want unreachable parts in our map.
It's very good practice to always do this before building a dungeon, because depending on which generator algorithm you use, some are more prone to creating isolated parts than others.

So we add this line:
call Dungeon.verifyMap()

Now, we can remove all parts of the map that were marked as unreachable by the verification process:
call Dungeon.clearUnverified()

Convenient, isn't it? Now we have a nice and clean dungeon layout in our game memory.

But before we finally build this dungeon, let's check out some nice handy debug tool first!
Add the following line:
call Dungeon.printMap()


So this is how your whole trigger should look like now:

JASS:
function Trig_DungeonTest_Actions takes nothing returns nothing
  local DungeonUniform newdung = DungeonUniform.create(0,0,17,18, 10,10,0.25,true,2,5,5,0,0.2)
  call Dungeon.clearMap()
  call newdung.generate()
  call Dungeon.removeAll(gg_rct_Dungeon_Area)
  call Dungeon.verifyMap()
  call Dungeon.clearUnverified()
  call Dungeon.printMap()
endfunction

//===========================================================================
function InitTrig_DungeonTest takes nothing returns nothing
  set gg_trg_DungeonTest = CreateTrigger(  )
  call TriggerRegisterPlayerChatEvent( gg_trg_DungeonTest, Player(0), "-dungeon", true )
  call TriggerAddAction( gg_trg_DungeonTest, function Trig_DungeonTest_Actions )
endfunction


... Now run your map and try it out by typing whatever chat command you entered as the triggering event!

...

Nothing happened?
Well, not quite. As you can see, your preplaced stamps have been properly removed and replaced by whatever tile you selected as the default.
But there was also something happening behind the scenes:
Go to your WarcraftIII/save directory and check it for a newly created file called "Layout.txt" and open this file.

What you see here is a preview of what your generated dungeon looks like at this point.

This is great because it allows you to test your generator settings fast and easy without actually having to build these dungeons every time.


But, well, we want to finally play this dungeon, right? So here we go!

Add another line to our test trigger:
call Dungeon.build(gg_rct_Dungeon_Area, 0, null)
... and voila, your dungeon has been created!
The integer argument after the region input determines the tileset to use for the building process. We only used the integer 0 so far, so we just left it at that.
But as you populate your map with more tilesets, you can set the tileset to use here!

Be warned; the build function is meaty and will take some time to process and (depending on the size of the dungeon) might even lag your game for some seconds.

At the next step, we will populate our dungeon with creatures and make use of the custom function callback and stamp enumeration.





Step VI: Build Callback and Enumeration


Great! We made our first dungeon. Let's wrap this up now by learning the last important features provided by the system.

First, let's generate a cavern aswell.
You registered stamps for that already, right?


Step_6_stamps.jpg

Those are just the bare minimum needed, so our cave will probably not look too natural, but it's fine for our first try. We can always add more stamp variations later.

Go back to our test trigger and replace the line with DungeonUniform.create() with this:

local DungeonCavern newdung = DungeonCavern.create(0,0,17,18, 45, true, 5, 2, 5, 5)

Again, let's quickly go through the parameters here:

0,0,17,18
Same as the last time; these will define the bottom left and top right corner of your sub-section of the dungeon map.

45
The cave algorithm generates a random distribution of walls and rooms at start, then applies some evolving mechanics for multiple generations (similar to how cells behave) to carve out actual caves from the random noise.
This fifth parameter in the function defines the distribution of walls to rooms at the first generation. Lower numbers will create larger, open caves. Higher numbers will create smaller, scattered caves. Typical values range from 40 to 50.

true
This boolean enables an option in which a horizontal line is introduced in the first generation. This reduces the likelyhood of generating isolated cave sections, but will also make them look slightly less natural, as they will tend to generate connected web-like structures with that.

5, 2, 5, 5
These numbers will affect the looks of the generated cave. The first number determines a rule after which walls and rooms will change their state at each generation. Typical values range from 4-6.
The second number changes a behaviour in which new walls will be introduced again in places that are already fully carved out. Typical values range from 0 to 3.
The third number determines the number of generations applied. The more generations we have, the smoother our cave will look like. However, if we apply too many generations, they will lose a lot of the chaotic character of natural caves. Typical value: 3-7.
The last number determines after how many generations the wall introduction mechanic will be removed. This prevents noise introduced by the mechanic. Typical values are 1 or 2 numbers lower than the number of evolving generations.

I recommend playing around with these settings and using the .printMap() command to see how they affect your result. There is no rule of thumb here. It's a bit of trial and error to find suitable input sets for the size of your dungeon.
Even small changes might have a strong impact on generated layouts, so make sure not to change the values too fast.


Anyway, let's compile this map and check it out ingame!


Cave.jpg

Looks decent enough, right? And that's just the bare minimum of stamps used. The more stamps we register, the more interesting our dungeon will look like, especially if we make use of the rarity feature to introduce special places into our dungeon, like a well, a magic machine, a portal, a statue, etc.


So, let's continue by populating our map with creatures. This time, we will make use of the custom callback of the .build() function.


Create a new function on top of your Triggeractions. Let's call it "Populate".

Then, change the line in which we build our dungeon to this one:
call Dungeon.build(gg_rct_Dungeon_Area, 0, function Populate)

This will make our build command fire the "Populate" function as soon as it finishes building.


Your trigger should now look similar to this:

JASS:
function Populate takes nothing returns nothing
endfunction

function Trig_DungeonTest_Actions takes nothing returns nothing
  //local DungeonUniform newdung = DungeonUniform.create(0,0,17,17, 10,10,0.30,false,2,4,4,0,0.2)
  local DungeonCavern cavedung = DungeonCavern.create(0,0,17,17, 45, true, 5, 2, 5, 5)
  call Dungeon.clearMap()
  call cavedung.generate()
  //call newdung.generate()
  call Dungeon.removeAll(gg_rct_Dungeon_Area)
  call Dungeon.verifyMap()
  call Dungeon.clearUnverified()
  call Dungeon.printMap()
  call Dungeon.build(gg_rct_Dungeon_Area, 0, function Populate)
endfunction

//===========================================================================
function InitTrig_DungeonTest takes nothing returns nothing
  set gg_trg_DungeonTest = CreateTrigger(  )
  call TriggerRegisterPlayerChatEvent( gg_trg_DungeonTest, Player(0), "-dungeon", true )
  call TriggerAddAction( gg_trg_DungeonTest, function Trig_DungeonTest_Actions )
endfunction

Let's start by moving our hero to the dungeon entrance.

For this, we add the following lines to our Populate function:

JASS:
function Populate takes nothing returns nothing
  local location loc = GetLastCreatedStairs(true)
  call SetUnitPosition(YourUnit, GetLocationX(loc), GetLocationY(loc))
  call DestroyLocation(loc)
  set loc = null
endfunction
This will move "YourUnit" to the last created staircase by the algorithm. The builder will always place one of the "stair up" stamps and one of the "stair down" stamps.
With the boolean in GetLastCreatedStairs, you can determine if you want to retrieve the location of the last created stairs up or down.
We want our hero to descent into a dungeon, so let's create him at the last stairs up, to imply that he just went down the stairs and reached this new level.



Now, let's apply the enumeration function to enumerate all the stamps in our dungeon and do stuff for each stamp:
Add the following line to your Populate function:

call Dungeon.enumerateMap(gg_rct_Dungeon_Area, function PopEnum)

This works just like enumerating destructables or units in an area, in the way that we need to pass another function as an argument to the command.

So let's create another function on top of the Populate function called "PopEnum".

JASS:
function PopEnum takes nothing returns nothing
  local integer data = GetEnumStampData()
  local integer value = GetEnumStampValue()
  local real x = GetEnumStampCenterX()
  local real y = GetEnumStampCenterY()
endfunction

As you can see, this works just like your typical enumerations for units or destructables.
Inside the custom function callback PopEnum, we have access to the data of whatever stamp is currently enumerated.
We can also get the (game-)coordinates of the currently enumerated stamp.

We can use these coordinates as a baseline to create creatures and treasure.

JASS:
function PopEnum takes nothing returns nothing
  local integer data = GetEnumStampData()
  local integer value = GetEnumStampValue()
  local real x = GetEnumStampCenterX()
  local real y = GetEnumStampCenterY()

  call CreateUnit(...)
  call CreateItem(...)
endfunction

Remember when we talked about the "custom data" and "custom value" parameter of the register function? Here is where it comes in handy.
For example, we can decide which creatures to create by checking what "danger level" was registered to that stamp or what spawnrate was registered.


JASS:
function PopEnum takes nothing returns nothing
  local integer data = GetEnumStampData()
  local integer value = GetEnumStampValue()
  local real x = GetEnumStampCenterX()
  local real y = GetEnumStampCenterY()

  //just an example
  if data > 10 and GetRandomReal(1,100) <= value then
   call CreateUnit(...)
   call CreateItem(...)
  endif
  ...
endfunction

function Populate takes nothing returns nothing
  local location loc = GetLastCreatedStairs(true)
  call SetUnitPosition(YourUnit, GetLocationX(loc), GetLocationY(loc))
  call Dungeon.enumerateMap(gg_rct_Dungeon_Area, function PopEnum)
  call DestroyLocation(loc)
  set loc = null
endfunction

function Trig_DungeonTest_Actions takes nothing returns nothing
  //local DungeonUniform newdung = DungeonUniform.create(0,0,17,17, 10,10,0.30,false,2,4,4,0,0.2)
  local DungeonCavern cavedung = DungeonCavern.create(0,0,17,17, 45, true, 5, 2, 5, 5)
  call Dungeon.clearMap()
  call cavedung.generate()
  //call newdung.generate()
  call Dungeon.removeAll(gg_rct_Dungeon_Area)
  call Dungeon.verifyMap()
  call Dungeon.clearUnverified()
  call Dungeon.printMap()
  call Dungeon.build(gg_rct_Dungeon_Area, 0, function Populate)
endfunction

//===========================================================================
function InitTrig_DungeonTest takes nothing returns nothing
  set gg_trg_DungeonTest = CreateTrigger(  )
  call TriggerRegisterPlayerChatEvent( gg_trg_DungeonTest, Player(0), "-dungeon", true )
  call TriggerAddAction( gg_trg_DungeonTest, function Trig_DungeonTest_Actions )
endfunction


That's it!

You now know everything you need to know to create cool dungeon designs.
 

Attachments

  • DungeonWall_Black_Large.mdx
    1.8 KB · Views: 236
Last edited:

EdgeOfChaos

E

EdgeOfChaos

One of the greatest systems I've seen.

The map "Roguelike" should use this!
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
You can create single rooms with no connections just fine. Just set the maximum number of rooms created to 1 and run the .generate() method multiple times on the same map to create the number of unconnected rooms you like.

There is no rarity tied to rooms in this algorithm. Rarity is applied to stamps, not rooms. So specific pieces of rooms might be more rare than others, but not the rooms themselves.


But if you only need non-connected rectangular rooms, why would you even need a generator algorithm? You can just preplace the rooms and place the details manually.
 

Dr Super Good

Spell Reviewer
Level 63
Joined
Jan 18, 2005
Messages
27,178
Might want to add functionality for supporting bespoke rooms. I would imagine such rooms being useful for boss fights, quests or anything that might be optimized/designed for a non-random layout while still being inside a random dungeon. Fundamentally they would be very large stamps which make up a single room or large part of room. Instead of being randomly selected, they would have to be explicitly ordered before generating a dungeon.

Also might want to add functionality to feed in stamps as data directly. The stamp approach is very easy to use however it is not very space efficient as far as terrain goes. Although in theory a 480*480 map should never run out of space, it could potentially be quite difficult for people wanting to retrofit a map with this system and still have a good stamp variety.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Might want to add functionality for supporting bespoke rooms. I would imagine such rooms being useful for boss fights, quests or anything that might be optimized/designed for a non-random layout while still being inside a random dungeon. Fundamentally they would be very large stamps which make up a single room or large part of room. Instead of being randomly selected, they would have to be explicitly ordered before generating a dungeon.
You can already do that. You just build new stamps that are exclusive to your bespoke room and set their rarity to 0. That way, they will never be chosen by the algorithm.

The way I would do it is just run the .generate() method only in a specific area and leave something empty for your unique room, like the top left corner of the dungeon area.

Then you can simply place the stamps of the unique room manually using the .place() method and connect the door of that room with the random dungeon via the .connectClosestRoom() method. That's it's primary purpose after all.

If you want the unique room to naturally be placed inside the random dungeon, you can also just remove the stamps the area where you want your unique room, then place the unique stamps there.

Also might want to add functionality to feed in stamps as data directly. The stamp approach is very easy to use however it is not very space efficient as far as terrain goes. Although in theory a 480*480 map should never run out of space, it could potentially be quite difficult for people wanting to retrofit a map with this system and still have a good stamp variety.
This is already possible, albeit only for a stamp size of 5x5 or smaller, as JASS doesn't allow dynamic input parameters.


This isn't covered by the tutorial, but it's in the stamp API:

method print takes nothing returns nothing

Allows to print all data from the stamp into a .txt file of specified filepath.
This textfile will contain the raw vJASS commands to register the stamp by text input instead of placing it directly on your map.
This is great for exchanging tile data between maps or if you don't have enough space for all stamps on your map.
Just .print the stamp, copy & paste the vJASS code in your map in and you can safely remove the stamp from your map!

method registerTerrain
method registerVariation
method registerDestructable
method registerDestX
method registerDestY
method registerDestFace

These methods take 25 parameters each and allow to manually register a stamp without having to place it on your map.
Designed for use with the .print method above.

I register all my stamps like that, as preplaced stamps increase the loading time.

A single stamp will be compressed into 7 lines of code that way:

JASS:
  set data = stamp.create(SHAPE_CAVE_HALL, TILESET_LAVA, 0.3, 0, 0)
  call data.registerTerrain('Ydrt','Ksmb','Ksmb','Ksmb','Ydrt','Ksmb','Ksmb','Ksmb','Ksmb','Ksmb','Ksmb','Ksmb','Ksmb','Ksmb','Ksmb','Ksmb','Ksmb','Ksmb','Ksmb','Ksmb','Ydrt','Ksmb','Ksmb','Ksmb','Ksmb')
  call data.registerVariation(8,8,8,8,8,8,8,15,8,8,8,15,15,15,8,8,8,15,15,8,8,8,8,8,8)
  call data.registerDestructable('B028','B03N','B01Y','B03E','B029','B03K','B03M','B01Y','B03I','B03M','B03N','B01Z','B03N','B03E','B025','B03I','B01Y','B03N',0,0,0,0,0,0,0)
  call data.registerDestX(-224,-128,-128,32,0,0,-64,0,-32,0,192,192,-192,160,-64,96,192,192,0,0,0,0,0,0,0)
  call data.registerDestY(32,-64,-128,-32,0,0,0,-192,-32,-64,-64,-64,64,96,192,96,192,192,0,0,0,0,0,0,0)
  call data.registerDestFace(320,100,150,0,0,0,60,30,0,210,200,170,30,0,300,0,340,290,0,0,0,0,0,0,0)

I initially planned to compress all the stamp data into a single big integer, like we do it with savecodes, but I figured that this would be way too heavy on processing if you register many hundreds of stamps that way.
 
Last edited:
I think it's very powerful. I can't give too good critiques, because I haven't used it. But from reading your docu and API it seems pretty solid.

  • Using 'public' keyword could be useful for some members. Though names are good, I can imagine "orientation_blah" or "shape_bla" having a chance to come in conflict with an other special system.

  • Why functionality exists to bind integer/real to a stamp? Couldn't I create my own struct or what ever to bind data to my stamp, if required? Like here, I'm anyways "limited to only" 1 integer, and 1 real. Or do you maybe think this covers most use cases? Would be good to understand.

  • Much info is in this thread provided by your. The first lib could contain a link to here.

  • JASS:
    method hasNoNext takes nothing returns boolean
        return this.hasNext() == false
    endmethod
    can be ->
    JASS:
    method hasNoNext takes nothing returns boolean
        return this.nextRoom == 0
        // or
        return not this.hasNext()
    endmethod

  • Outsourcing logics can be good, too. Like, using external List logics.

  • One static location could be used.

  • onDestroy method should not be used, if it's not an extending struct.
    destroy() -> normal function call
    onDestroy() -> generate trigger, triggercondition, and will run through a trigger evaluation each time called

  • You said yourself you maybe will refactor the API to make headers a bit more unitform.
    Not sure I can give good tips here. Maybe if you keep binding data:
    JASS:
    GetEnumStampData()
    GetEnumStampValue()
    ->
    JASS:
    GetEnumStampDataInt()
    GetEnumStampDataReal()
It's not very simple to use, but it can help a lot. I think it might be useful and we should just finaly approve this.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Using 'public' keyword could be useful for some members. Though names are good, I can imagine "orientation_blah" or "shape_bla" having a chance to come in conflict with an other special system.
I personally don't like the public keyword as it creates ugly looking names (and its also unintuitive to use in JASS, as the name within the scope of the library is different to outside). Imho that's a matter of taste. I don't think the names I selected would clash with anything.
Why functionality exists to bind integer/real to a stamp? Couldn't I create my own struct or what ever to bind data to my stamp, if required? Like here, I'm anyways "limited to only" 1 integer, and 1 real. Or do you maybe think this covers most use cases? Would be good to understand.
StampData is there to be used with enumerateMap() and GetEnumStampData(). This allows directly attaching a struct to a stamp that you can retrieve elegantly in the callback.
And yes, StampValue is kind of redundant in that regard. I added it just as a convenience thing.

Much info is in this thread provided by your. The first lib could contain a link to here.
Not sure what you mean.

return this.hasNext() == false
It's a weird quirk of mine. Sometimes I just dont feel like using not.

Outsourcing logics can be good, too. Like, using external List logics.
Did we agree on a standard on a general linked list lib on Hive? I often browse systems and notice that many people manually implement their lists (probably for performance reasons).

One static location could be used.
Agreed.

onDestroy method should not be used, if it's not an extending struct.
  • destroy() -> normal function call
    onDestroy() -> generate trigger, triggercondition, and will run through a trigger evaluation each time called
I dislike manual implementations of destroy simply because it robs me of the possibility to extend on my structs in the future. There is a reason why Vex implemented it this way and I'm on board with that.
And in this case, I don't mind the speed difference, since I'm spamming triggeractions anyway to bypass the operation limit.

You said yourself you maybe will refactor the API to make headers a bit more unitform.
  • Not sure I can give good tips here. Maybe if you keep binding data:
    JASS:
    GetEnumStampData()
    GetEnumStampValue()
    ->
    JASS:
    GetEnumStampDataInt()
    GetEnumStampDataReal()
It's not very simple to use, but it can help a lot. I think it might be useful and we should just finaly approve this.
I tried to mimic the naming conventions of vanilla JASS here (UnitPointValue und UnitUserData). If I change the API in the future, I would rather take an aggressive struct-based approach with static methods for these.
 
Last edited:
Not sure what you mean.
Iirc somewhere is written something like "read the api docu" for more info, or something alike. I just didn't see then a link to this thread, where all this descriptions are actually provided. (if someone reads this lib in a map, then he might want to know)
Did we agree on a standard on a general linked list lib on Hive? I often browse systems and notice that many people manually implement their lists (probably for performance reasons).
I guess, not. I guess many maps have still Nes' resources imported, I used them too (github now).
But for hive, idk, I like Banner's coding much. Maybe his [Containers] List<T> is good for future codes.
 
Top