Procedurally Generated Maze

Rllulium

New Member
Reaction score
10
Random dungeon? Funfunfun.

This is a little heavyweight at the moment, but I'd be delighted to get some feedback on how to improve it.
Note that the maze is being built with coordinates 0.0 as its lower left corner and that this is to be considered the starting point of the maze.
The destructable "Dungeon Gate" is being used for the walls.

JASS:
library DungeonStructs initializer OnInit

globals
    private constant integer HORIZONTAL = 'DTg1'
    private constant integer VERTICAL   = 'DTg3'
    private constant real    TILE_SIZE  = 512
    private constant integer MAX_SIZE   = 8
    
    tile array tiles
    integer tIndex = 0
    wall array vWalls
    integer vIndex = 0
    wall array hWalls
    integer hIndex = 0
endglobals

struct tile
    integer x
    integer y
    boolean flag
    
    static method create takes integer x, integer y returns thistype
        local thistype new = thistype.allocate()
        set new.x = x
        set new.y = y
        set new.flag = false
        return new
    endmethod
    
    static method setupAll takes nothing returns nothing
        local integer x = 0
        local integer y = 0
        loop
            set y = 0
            loop
                set tiles[tIndex] = tile.create(x, y)
                set tIndex = tIndex + 1
                set y = y + 1
                exitwhen y == MAX_SIZE
            endloop
            set x = x + 1
            exitwhen x == MAX_SIZE
        endloop
    endmethod
    
    static method resetAll takes nothing returns nothing
        if tIndex > 0 then
            loop
                set tIndex = tIndex - 1
                call tiles[tIndex].destroy()
                exitwhen tIndex == 0
            endloop
        endif
    endmethod
endstruct

struct wall
    integer x
    integer y
    boolean vertical
    boolean build
    destructable object
    
    static method create takes integer x, integer y, boolean vertical returns thistype
        local thistype new = thistype.allocate()
        set new.x = x
        set new.y = y
        set new.vertical = vertical
        set new.build = true
        return new
    endmethod
    
    method onDestroy takes nothing returns nothing
        call RemoveDestructable(object)
        set .object = null
    endmethod
    
    method generate takes nothing returns nothing
        if build then
            if .vertical then
                set .object = CreateDestructable(VERTICAL, x*TILE_SIZE, TILE_SIZE/2 + y*TILE_SIZE, 180, 0.8, 1)
            else
                set .object = CreateDestructable(HORIZONTAL, TILE_SIZE/2 + x*TILE_SIZE, y*TILE_SIZE, 270, 0.8, 1)
            endif
        endif
    endmethod
    
    static method generateAll takes nothing returns nothing
        local integer i = 0
        loop
            call hWalls<i>.generate()
            call vWalls<i>.generate()
            set i = i + 1
            exitwhen i &gt; hIndex
        endloop
    endmethod
    
    static method setupEdges takes nothing returns nothing
        local integer i = 0
        loop
            set vWalls[vIndex] = wall.create(MAX_SIZE, i, true)
            set vIndex = vIndex + 1
            set hWalls[hIndex] = wall.create(i, MAX_SIZE, false)
            set hIndex = hIndex + 1
            set i = i + 1
            exitwhen i == MAX_SIZE
        endloop
    endmethod
    
    static method setupAll takes nothing returns nothing
        local integer x = 0
        local integer y = 0
        loop
            set y = 0
            loop
                set vWalls[vIndex] = wall.create(x, y, true)
                set vIndex = vIndex + 1
                set hWalls[hIndex] = wall.create(x, y, false)
                set hIndex = hIndex + 1
                set y = y + 1
                exitwhen y == MAX_SIZE
            endloop
            set x = x + 1
            exitwhen x == MAX_SIZE
        endloop
        call .setupEdges()
    endmethod
    
    static method resetAll takes nothing returns nothing
        if hIndex &gt; 0 then
            loop
                set vIndex = vIndex - 1
                call vWalls[vIndex].destroy()
                set hIndex = hIndex - 1
                call hWalls[hIndex].destroy()
                exitwhen hIndex == 0
            endloop
        endif
    endmethod
endstruct

private function OnInit takes nothing returns nothing
    
endfunction

endlibrary</i></i>

JASS:
library DungeonGeneration initializer OnInit

globals
    private constant integer MAX_SIZE   = 8
    
    private integer array backtrack
    private integer bIndex
endglobals

private function DivideByEight takes integer i returns boolean
    local real r = I2R(i)/8
    local integer t = R2I(r)
    return r != t
endfunction
    
struct maze
    integer index
    boolean backtracking = false
    
    method checkValidity takes integer i returns boolean
        if i == 1 then
            return DivideByEight(index + 1)
        elseif i == 2 then
            return (index + MAX_SIZE) &lt; 64
        elseif i == 3 then
            return DivideByEight(index)
        elseif i == 4 then
            return (index - MAX_SIZE) &gt;= 0
        endif
        return false
    endmethod
    
    method checkFlag takes integer i returns boolean
        if i == 1 then
            return not tiles[index + 1].flag
        elseif i == 2 then
            return not tiles[index + MAX_SIZE].flag
        elseif i == 3 then
            return not tiles[index - 1].flag
        elseif i == 4 then
            return not tiles[index - MAX_SIZE].flag
        endif
        return false
    endmethod
    
    method GetSeed takes nothing returns integer
        local integer r = 0
        local integer i = 1
        local boolean break = false
        loop
            if checkValidity(i) and checkFlag(i) then
                set r = 1
            endif
            set i = i + 1
            exitwhen i &gt; 4
        endloop
        if r == 0 then
            return r
        endif
        loop
            set r = GetRandomInt(1, 4)
            if checkValidity(r) and checkFlag(r) then
                set break = true
            endif
            exitwhen break
        endloop
        return r
    endmethod
    
    method finish takes nothing returns nothing
        call stopPeriodic()
        call wall.generateAll()
        call BJDebugMsg(&quot;Done!&quot;)
    endmethod
    
    private method periodic takes nothing returns nothing
        local integer r = GetSeed()
        if not backtracking then
            set bIndex = bIndex + 1
            set backtrack[bIndex] = index
        endif
        set backtracking = false
        if r == 0 then
            set bIndex = bIndex - 1
            if bIndex &lt; 0 then
                call finish()
            else
                set index = backtrack[bIndex]
                set backtracking = true
            endif
        elseif r == 1 then
            set hWalls[index+1].build = false
            set index = index + 1
        elseif r == 2 then
            set vWalls[index+MAX_SIZE].build = false
            set index = index + MAX_SIZE
        elseif r == 3 then
            set hWalls[index].build = false
            set index = index - 1
        elseif r == 4 then
            set vWalls[index].build = false
            set index = index - MAX_SIZE
        endif
        set tiles[index].flag = true
    endmethod
    
    static method craft takes nothing returns nothing
        local maze new = maze.create()
        set new.index = 0
        set bIndex = -1
        call new.startPeriodic()
    endmethod
    
    implement T32x
endstruct

private function Check takes nothing returns boolean
    call tile.resetAll()
    call wall.resetAll()
    call tile.setupAll()
    call wall.setupAll()
    call maze.craft()
    return false
endfunction

private function OnInit takes nothing returns nothing
    local trigger t = CreateTrigger()
    call TriggerRegisterPlayerChatEvent(t, Player(0), &quot;new&quot;, true)
    call TriggerAddCondition(t, Condition(function Check))
endfunction

endlibrary

EDIT: To be honest, I did not know where to put this. It's not really a project, and I wasn't planning on submitting it. I guess this section is a good as any.
 

Magthridon96

Member
Reaction score
2
I tested it, and I must say, I'm quite impressed :)
Just a few things:
You don't need T32 for this. It could all be generated instantly.
If it hits the op limit, you could use trigger evaluations :)
In the GetSeed function:
JASS:
if r == 0 then
    return r
endif


You could change return r to return 0.
The speed difference is very marginal though, so you don't have to :p

Also:

JASS:
private function DivideByEight takes integer i returns boolean
    local real r = I2R(i)/8
    local integer t = R2I(r)
    return r != t
endfunction


Change this function to:

JASS:
function DB8 takes integer i returns boolean
    return i-(i/8)*8 != 0
endfunction
 

Narks

Vastly intelligent whale-like being from the stars
Reaction score
90
I tested it, and I must say, I'm quite impressed :)
Just a few things:
You don't need T32 for this. It could all be generated instantly.
If it hits the op limit, you could use trigger evaluations :)

no, you need to generate it over time, or you will screw players with low-end computers
 

Narks

Vastly intelligent whale-like being from the stars
Reaction score
90
people with low-end computers are the primary players of war3 >.>
 

Sgqvur

FullOfUltimateTruthsAndEt ernalPrinciples, i.e shi
Reaction score
62
>people with low-end computers are the primary players of war3 >.>
Haha I can't believe this, someone actually cares about performance of his map on old machines nowadays. People think if their map loads fast on their super computer and they don't notice any kind of performance reduction while playing for 2 hours that it is all good. But no. If it loads for more than a minute on an old 1.5 GHz 256 RAM computer then f$@% it. If your map happens to take more then 2/3 of the 256 RAM then it has some problems (and I'm not playing it =)). I guess 128 RAM goes for warcraft but the rest 42 RAM is all yours. I can't even play custom games anymore. Let me give you an example: LegionTDWar or something. This map ... this map has so many so many leaks that it's not playable even on a super computer. You need 1 of those TOP500 computers to play it and not get frustrated of it's spawing/leaking.
 

Narks

Vastly intelligent whale-like being from the stars
Reaction score
90
well, with such low RAM, a procedurally generated maze you're screwed no matter what haha

more on topic:
I find it interesting you've decided to surround solid cells with walls, rather then simply state is a cell is solid or empty and stick a giant block in it (which would be the roguelike approach)
 

Rllulium

New Member
Reaction score
10
Well, it all comes down with what I have to work with. The dungeon gate is alot better suited for this type of maze as opposed to the setup you were suggesting.
 
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Members online

      No members online now.

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top