1. Find your way through the deepest dungeon in the 18th Mini Mapping Contest Poll.
    Dismiss Notice
  2. A brave new world lies beyond the seven seas. Join the 34th Modeling Contest today!
    Dismiss Notice
  3. Check out the Staff job openings thread.
    Dismiss Notice
Dismiss Notice
Hive 3 Remoosed BETA - NOW LIVE. Go check it out at BETA Hive Workshop! Post your feedback in this new forum BETA Feedback.
Dismiss Notice
60,000 passwords have been reset on July 8, 2019. If you cannot login, read this.

Dungeon Generator & Stamp

Discussion in 'JASS Resources' started by Zwiebelchen, Jun 30, 2016.

  1. Zwiebelchen

    Zwiebelchen

    Joined:
    Sep 17, 2009
    Messages:
    7,014
    Resources:
    12
    Models:
    5
    Maps:
    1
    Spells:
    1
    Tutorials:
    1
    JASS:
    4
    Resources:
    12
    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.

    Code (vJASS):
    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

    Code (vJASS):
    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
     

    Attached Files:

    Last edited: Jul 1, 2016
  2. Zwiebelchen

    Zwiebelchen

    Joined:
    Sep 17, 2009
    Messages:
    7,014
    Resources:
    12
    Models:
    5
    Maps:
    1
    Spells:
    1
    Tutorials:
    1
    JASS:
    4
    Resources:
    12
    API DungeonStamp
    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:

    Code (vJASS):
        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)



    API DungeonGenerator
    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: Jul 2, 2016
  3. Zwiebelchen

    Zwiebelchen

    Joined:
    Sep 17, 2009
    Messages:
    7,014
    Resources:
    12
    Models:
    5
    Maps:
    1
    Spells:
    1
    Tutorials:
    1
    JASS:
    4
    Resources:
    12
    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
    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
    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
    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:

    Code (vJASS):
    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
    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
    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:

    Code (vJASS):
    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
    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:

    Code (vJASS):
    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:

    Code (vJASS):
    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".

    Code (vJASS):
    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.

    Code (vJASS):
    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.


    Code (vJASS):
    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.
     

    Attached Files:

    Last edited: May 6, 2019
  4. btdonald

    btdonald

    Joined:
    Dec 3, 2011
    Messages:
    346
    Resources:
    8
    Maps:
    1
    Spells:
    7
    Resources:
    8
    I'll test this soon. It's awesome jaja
     
  5. One of the greatest systems I've seen.

    The map "Roguelike" should use this!
     
  6. Zwiebelchen

    Zwiebelchen

    Joined:
    Sep 17, 2009
    Messages:
    7,014
    Resources:
    12
    Models:
    5
    Maps:
    1
    Spells:
    1
    Tutorials:
    1
    JASS:
    4
    Resources:
    12
    With this, I finally finished the tutorial. Have fun with this, guys! :)
     
  7. DatBoi

    DatBoi

    Joined:
    Jul 1, 2016
    Messages:
    104
    Resources:
    0
    Resources:
    0
    Really impressive, is it possible to make rooms like in TBoI (The Binding of Isaac)?
     
  8. Zwiebelchen

    Zwiebelchen

    Joined:
    Sep 17, 2009
    Messages:
    7,014
    Resources:
    12
    Models:
    5
    Maps:
    1
    Spells:
    1
    Tutorials:
    1
    JASS:
    4
    Resources:
    12
    I never played that game, but from the screenshots, it looks like normal rectangular rooms, so yes.
     
  9. DatBoi

    DatBoi

    Joined:
    Jul 1, 2016
    Messages:
    104
    Resources:
    0
    Resources:
    0
    But i mean with no corridors, one room after another.


    Can you add the posibility to make rare rooms, like, %15 chance to spawn that room in the dungeon.
     
  10. Zwiebelchen

    Zwiebelchen

    Joined:
    Sep 17, 2009
    Messages:
    7,014
    Resources:
    12
    Models:
    5
    Maps:
    1
    Spells:
    1
    Tutorials:
    1
    JASS:
    4
    Resources:
    12
    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.
     
  11. DatBoi

    DatBoi

    Joined:
    Jul 1, 2016
    Messages:
    104
    Resources:
    0
    Resources:
    0
    Just seeing what your system can do. :p
     
  12. Dr Super Good

    Dr Super Good

    Spell Reviewer

    Joined:
    Jan 18, 2005
    Messages:
    26,190
    Resources:
    3
    Maps:
    1
    Spells:
    2
    Resources:
    3
    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.
     
  13. Zwiebelchen

    Zwiebelchen

    Joined:
    Sep 17, 2009
    Messages:
    7,014
    Resources:
    12
    Models:
    5
    Maps:
    1
    Spells:
    1
    Tutorials:
    1
    JASS:
    4
    Resources:
    12
    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.

    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:

    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:

    Code (vJASS):

      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: Jul 18, 2016
  14. IcemanBo

    IcemanBo

    Joined:
    Sep 6, 2013
    Messages:
    6,549
    Resources:
    23
    Maps:
    3
    Spells:
    11
    Template:
    1
    Tutorials:
    5
    JASS:
    3
    Resources:
    23
    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.

    • Code (vJASS):
      method hasNoNext takes nothing returns boolean
          return this.hasNext() == false
      endmethod

      can be ->
      Code (vJASS):
      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:
      Code (vJASS):
      GetEnumStampData()
      GetEnumStampValue()

      ->
      Code (vJASS):
      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.
     
  15. Zwiebelchen

    Zwiebelchen

    Joined:
    Sep 17, 2009
    Messages:
    7,014
    Resources:
    12
    Models:
    5
    Maps:
    1
    Spells:
    1
    Tutorials:
    1
    JASS:
    4
    Resources:
    12
    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.
    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.

    Not sure what you mean.

    It's a weird quirk of mine. Sometimes I just dont feel like using
    not
    .

    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).

    Agreed.

    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.

    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: Oct 9, 2017
  16. IcemanBo

    IcemanBo

    Joined:
    Sep 6, 2013
    Messages:
    6,549
    Resources:
    23
    Maps:
    3
    Spells:
    11
    Template:
    1
    Tutorials:
    5
    JASS:
    3
    Resources:
    23
    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)
    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.
     
  17. Zwiebelchen

    Zwiebelchen

    Joined:
    Sep 17, 2009
    Messages:
    7,014
    Resources:
    12
    Models:
    5
    Maps:
    1
    Spells:
    1
    Tutorials:
    1
    JASS:
    4
    Resources:
    12
    Ah I see now. Yes a link is needed.

    Looks solid to me. Guess I will use that in the future. Switching to that resource now would probably be too much work though. I'll keep it in mind if I rework this system in the future.