Dungeons

Generates connected rooms, caves and mazes from a seed, all at once or a little each frame.

Commands

Import blitz.dungeons As D gives your program these, with D. in front. Each name leads to its part of the reference.

Functions

• LastError:Str()
• DungeonTile:Int(dungeon:Dungeon, x:Int, y:Int)
• CountLocations:Int(dungeon:Dungeon, kind:Int)
• DungeonLocation:Location(dungeon:Dungeon, kind:Int, index:Int = 0)
• BeginDungeon:Generation(width:Int, height:Int, seed:Long, options:DungeonOptions)
• GenerateDungeon:Dungeon(width:Int, height:Int, seed:Long, options:DungeonOptions)
• TakeDungeon:Dungeon(generation:Generation)
• StepDungeon:Int(generation:Generation, work:Int = 1024)

Types

• DungeonOptions
  Fields mode:Int = DungeonMode.Rooms, density:Double = 0.5D, minimumRoomSize:Int = 3, loops:Int = False
• Location
  Methods X:Int(), Y:Int(), Left:Int(), Top:Int(), Width:Int(), Height:Int()
• Dungeon
  Methods Width:Int(), Height:Int(), Seed:Long(), EffectiveSeed:Long(), Attempt:Int(), Mode:Int(), AlgorithmVersion:Str()
• Generation
  Methods Stage:Int(), WorkDone:Long(), Attempt:Int()

Enums

• DungeonMode
  Values Rooms, Caves, Maze
• TileKind
  Values Wall, Floor
• LocationKind
  Values Entrance, ExitPoint, RoomCentre
• GenerationStatus
  Values Pending, Ready, Failed
• GenerationStage
  Values Allocate, SplitRooms, CarveRooms, JoinRooms, CarveMaze, AddLoops, PopulateCaves, SmoothCaves, LabelComponents, ConnectComponents, VerifyConnectivity, SelectEndpoints, Retry, Complete

Guide

Dungeons makes maps for you: rooms joined by corridors, winding caves, or a maze. Give it a size and a seed, and you get back a grid of walls and floors, with an entrance and an exit a long way apart. Every floor can be reached from every other, so a player is never shut in, and the same seed always makes the same map, so a game can have a hundred levels without storing any of them.

Try it

Open explore.bb and run it. Walk from the green entrance to the gold exit with the arrow keys, and the next level appears: rooms, then caves, then a maze. Space skips a level.

; Walk from the green entrance to the gold exit with the arrow keys, and the
; next level is made. Space skips a level. Escape quits.
Dialect "modern"
Import blitz.dungeons As D

Const TILE:Int = 16 ; Each tile is 16 pixels square.
Graphics 640, 500, 0, 2
SetBuffer BackBuffer()
ClsColor 18, 52, 79

Local options:D.DungeonOptions = New D.DungeonOptions
Local level:Int = 1
Local dungeon:D.Dungeon = Null
Local exitPoint:D.Location
Local picture:Int = CreateImage(39 * TILE, 29 * TILE)
Local playerX:Int
Local playerY:Int
Local lastStep:Int
Local x:Int
Local y:Int
Local changed:Int = True

While Not KeyDown(1)
    If changed
        ; Levels take turns: rooms, then caves, then a maze.
        Select level Mod 3
            Case 1
                options.mode = D.DungeonMode.Rooms
            Case 2
                options.mode = D.DungeonMode.Caves
            Default
                options.mode = D.DungeonMode.Maze
        End Select
        ; The level number is the seed, so each level is the same every time.
        Delete dungeon
        dungeon = D.GenerateDungeon(39, 29, Long(level), options)
        If dungeon = Null Then RuntimeError D.LastError()
        ; The dungeon lends us its entrance and exit. We never delete them.
        Local entrance:D.Location = D.DungeonLocation(dungeon, D.LocationKind.Entrance)
        exitPoint = D.DungeonLocation(dungeon, D.LocationKind.ExitPoint)
        playerX = entrance.X()
        playerY = entrance.Y()
        ; Draw the map into a picture once, rather than tile by tile each frame.
        SetBuffer ImageBuffer(picture)
        For y = 0 To 28
            For x = 0 To 38
                Color 30, 70, 110
                If D.DungeonTile(dungeon, x, y) = D.TileKind.Floor Then Color 170, 180, 195
                If x = entrance.X() And y = entrance.Y() Then Color 70, 230, 130
                If x = exitPoint.X() And y = exitPoint.Y() Then Color 255, 185, 70
                Rect x * TILE, y * TILE, TILE - 1, TILE - 1, True
            Next
        Next
        SetBuffer BackBuffer()
        changed = False
    EndIf

    ; Hold an arrow key to walk, one tile every tenth of a second. The map
    ; always has a wall round its edge, so a step never leaves the map.
    If MilliSecs() - lastStep > 100
        Local stepX:Int = KeyDown(205) - KeyDown(203) ; Right minus left
        Local stepY:Int = KeyDown(208) - KeyDown(200) ; Down minus up
        If D.DungeonTile(dungeon, playerX + stepX, playerY) = D.TileKind.Floor Then playerX = playerX + stepX
        If D.DungeonTile(dungeon, playerX, playerY + stepY) = D.TileKind.Floor Then playerY = playerY + stepY
        If stepX <> 0 Or stepY <> 0 Then lastStep = MilliSecs()
    EndIf
    ; Reaching the exit, or pressing Space, makes the next level.
    If KeyHit(57) Or (playerX = exitPoint.X() And playerY = exitPoint.Y())
        level = level + 1
        changed = True
    EndIf

    Cls
    DrawImage picture, 8, 8
    Color 255, 255, 255
    Oval 10 + playerX * TILE, 10 + playerY * TILE, TILE - 5, TILE - 5, True
    Text 8, 478, "Level " + level + "    Arrows: walk    Space: skip a level"
    Flip
Wend
FreeImage picture
Delete dungeon
Delete options
End

GenerateDungeon makes the whole map at once and gives it to you. DungeonTile then says whether each tile is a wall or a floor, and DungeonLocation tells you where the entrance and the exit are. The module only makes the map: drawing it, and what happens in it, are up to your game.

How do I...

Make caves or a maze?

Set mode in the options. Rooms are the usual, and you get them when you pass Null instead of options.

Local options:D.DungeonOptions = New D.DungeonOptions
options.mode = D.DungeonMode.Caves
Local dungeon:D.Dungeon = D.GenerateDungeon(60, 40, 7L, options)
Delete options ; The module keeps its own copy.

Make bigger or smaller rooms?

density, from 0 to 1, makes rooms bigger or smaller, and minimumRoomSize sets the smallest a room can be, in tiles. With caves, density says how much floor to start with, so more makes more open caves.

options.density = 0.9D      ; Big rooms.
options.minimumRoomSize = 4 ; Fewer, bigger rooms, none smaller than 4 by 4.

Add more ways round?

Set loops to True, for rooms or a maze. Some extra corridors join places that were only joined the long way round before, so players can go round in circles.

options.loops = True

Put treasure in every room?

Each room has a centre. Ask how many rooms there are, then where each one is. Caves and mazes have no rooms, so for them the count is zero.

Local index:Int
For index = 0 To D.CountLocations(dungeon, D.LocationKind.RoomCentre) - 1
    Local room:D.Location = D.DungeonLocation(dungeon, D.LocationKind.RoomCentre, index)
    PlaceTreasure room.X(), room.Y()
Next

A room's Left(), Top(), Width() and Height() say where its edges are, for spreading things round it.

Build the dungeon in 3D?

Put a cube on each wall tile. A cube is two units across, so space them two apart.

Local x:Int
Local y:Int
For y = 0 To dungeon.Height() - 1
    For x = 0 To dungeon.Width() - 1
        If D.DungeonTile(dungeon, x, y) = D.TileKind.Wall
            Local wall:Int = CreateCube()
            PositionEntity wall, x * 2, 1, y * 2
        EndIf
    Next
Next

walk.bb, below, does this, with a floor and collisions so you can't walk through the walls.

Make a big map without the game stuttering?

Spread the work over several frames. Start the map once, then do a little of it each frame until it's ready.

Local job:D.Generation = D.BeginDungeon(256, 256, 99L, Null)
; Then, each frame:
If job <> Null
    Local status:Int = D.StepDungeon(job, 2000) ; Do up to 2000 units of work.
    If status = D.GenerationStatus.Ready
        Delete dungeon ; The old map, if there is one.
        dungeon = D.TakeDungeon(job)
    EndIf
    If status <> D.GenerationStatus.Pending
        Delete job ; The dungeon you took is yours now, and outlives the job.
        job = Null
    EndIf
EndIf

With caves, the status can be Failed instead, and then D.LastError() says why. Deleting a job before it's ready stops it.

Blip's tip

Each option is only for some kinds of map: loops for rooms and mazes, density for rooms and caves, and minimumRoomSize for rooms. Change one for a kind of map it isn't for, and the program stops with an error. The program above uses one set of options for all three kinds, which works because it only ever changes mode. If you change the others too, put them back before you switch.

Good to know

• The same seed, size and options always make the same map, on every computer, however the work is spread over frames. Save those rather than the map itself. dungeon.AlgorithmVersion() names the way the map was made, in case a later version of the module makes different maps.
• Maps are 7 to 512 tiles each way, with a solid wall all round the edge.
• Use odd sizes for mazes. An even width or height leaves a spare line of wall along the right or bottom edge.
• Sparse caves can fail. If a cave still has almost no floor after four tries, GenerateDungeon returns Null, and D.LastError() says why. Rooms and mazes always work.
• The locations are lent. Never delete the entrance, the exit or a room. Deleting the dungeon deletes them too, so use them before that.
• Walls and floors are all you get. Doors, keys, furniture and monsters are up to your game.

More examples

Three more complete programs come with the module:

• incremental.bb makes big caves a little at a time, while the screen keeps moving. Space starts a new one, C stops it, and + and - change how much work it does each frame.
• preview.bb shows maps from above. 1, 2 and 3 choose rooms, caves or a maze, and Left and Right change the seed.
• walk.bb builds a maze from cubes and lets you walk through it in 3D to the gold marker at the exit. W, A, S and D move, Left and Right turn, and R takes you back to the entrance.

The reference below has every function, option and rule.

Reference

Needs

blitz.random

Examples

incremental.bb, preview.bb, walk.bb

Unpublished 0.1.0 preview, Extended only; requires object-lifecycle-v1 (runtime 1114 / module ABI 5 or compatible newer). Blitz3D+ comes with this module and blitz.random, which it imports, so any Extended program can Import blitz.dungeons.

Open examples/preview.bb and run it. Keys 1/2/3 select Rooms/Caves/Maze, Left/Right change seed, Esc closes. The green and gold tiles are the entrance and exit. examples/walk.bb is a complete generated 3D maze: WASD moves, Left/Right turns, R restarts, and gold marks the reachable exit. Its generated cubes use runtime ellipsoid/triangle collision, including a floor. examples/incremental.bb keeps a live UI while generating 128x128 caves: Space replaces the job, C cancels, and +/- changes the per-frame work allowance. All three accept --verify, exercise their advertised paths, clean up and end. They need no image, mesh, sound or downloaded asset.

Dialect "modern"
Import blitz.dungeons As D
Local dungeon:D.Dungeon = D.GenerateDungeon(41, 35, 42L, Null)
If dungeon = Null Then RuntimeError D.LastError()
Local start:D.Location = D.DungeonLocation(dungeon, D.LocationKind.Entrance)
Print start.X() + "," + start.Y()
Print D.DungeonTile(dungeon, start.X(), start.Y())
Delete dungeon ; also deletes start; never Delete a borrowed location
End

Configuration and failure

DungeonOptions is a caller-owned, mutable input record. BeginDungeon and GenerateDungeon copy it; editing or deleting it afterward has no effect. Pass explicit Null for defaults. LocationKind.ExitPoint replaces the design notation Exit, which is reserved. The compiler does not support an optional object argument with a Null default, so the proposed optional spelling was replaced by a required final options argument, as in the accepted noise package.

Inapplicable fields must retain their defaults. Density is not a promised final floor percentage: smoothing, margins and connections change it. Zero density Rooms still fits minimum rooms; zero density Caves deterministically exhausts all four attempts. Maze has no density setting.

Dimensions must each be 7..512 (up to 262,144 cells). Validation occurs before resource allocation. Invalid sizes, non-finite density, unsupported fields, unknown enum values, negative work/indexes, bad coordinates, or Null/deleted resources are programming errors reported by RuntimeError. Typed Null is a valid options default, not a valid dungeon/job. There are no silent clamps.

A valid cave configuration may produce fewer than two floor cells even after four attempts. GenerateDungeon returns Null; StepDungeon returns Failed. LastError():Str explains exhaustion and is cleared at the next factory/Step call; copy it immediately. Re-stepping a failed job restores its diagnostic. TakeDungeon returning Null while pending/failed/already-taken is an ordinary polling result and does not alter LastError. Runtime allocation failure remains a runtime error, not a successful empty dungeon.

Local options:D.DungeonOptions = New D.DungeonOptions
options.mode = D.DungeonMode.Caves
options.density = 0D
Local dungeon:D.Dungeon = D.GenerateDungeon(7, 7, 10L, options)
If dungeon = Null Then Print D.LastError()
Delete dungeon
Delete options

Jobs, ownership and queries

Local job:D.Generation = D.BeginDungeon(128, 128, 2026L, Null)
; In a game, do this once per frame between input/decisions and rendering.
While D.StepDungeon(job, 256) = D.GenerationStatus.Pending
    ; job.Stage(), job.WorkDone(), job.Attempt() can drive a progress display.
Wend
Local dungeon:D.Dungeon = D.TakeDungeon(job)
Delete job ; a transferred dungeon survives
Delete dungeon

Dungeon has immutable read methods Width(), Height(), Seed() (original), EffectiveSeed(), Attempt(), Mode() and AlgorithmVersion(). Location has X(), Y(), Left(), Top(), Width(), Height(); a RoomCentre reports the centre and fitted room bounds. Endpoint bounds are 1x1. Example: D.DungeonLocation(dungeon, D.LocationKind.RoomCentre, 0) may be Null in a maze. Result metadata and locations use private fields plus small read methods because Extended has no immutable public fields. There are no duplicate global getters.

Delete job cancels pending work and frees all owned state; it does not finish or publish a partial result. Delete dungeon deletes its locations and containers. As throughout Extended, scope exit/assignment/End is not a user destructor. Delete explicitly. Never Delete a borrowed Location; privacy is not ownership checking. Typed Null/already-deleted aliases are safe to Delete.

No callback or behaviour Interface is needed: the caller schedules Step and reads immutable results. There is no hidden clock, callback reentrancy, global loop or mutation hook. Jobs can be interleaved on the main thread; they are not worker-safe. Stop/Save/Commit are not operations of this logical generator; Delete's cancellation cannot save a game, commit world geometry or award rewards.

Algorithm contract: blitz-dungeons-v1

All output is four-way connected and has exact requested dimensions with a solid one-tile outer border. Endpoints are walkable interior cells, distinct on every accepted dungeon. Logical tiles never imply a doorway or collision body.

Rooms subdivides the usable rectangle with an explicit region stack. Each leaf fits a non-overlapping room with a wall margin, scaled by density and bounded by the minimum. The stable depth-first leaf order supplies a spanning chain of axis-aligned centre corridors. Optional skip-one links add alternative routes. Corridors can cross other rooms; their extents are not included in room bounds.

Maze uses randomized iterative depth-first carving on the odd coordinate lattice, with an explicit Int Stack and stable N/E/S/W candidate ordering. The requested size never changes: an even axis leaves an extra unused wall fringe at its high end. Optional loop carving scans interior connector walls, opening one in eight candidates with opposite walkable neighbours. Without loops the carved lattice is a tree; with loops the topology can have cycles.

Caves samples initial floors then performs four majority rounds over each 3x3 neighbourhood (including self). Five or more walls produces a wall. Separate read/write Lists prevent update-order bias; borders always stay walls. Flood fill labels all components. Consecutive row-major component anchors are connected with horizontal-then-vertical corridors; no islands are discarded. A separate final flood verifies reachability of every floor.

That final breadth-first sweep selects a farthest entrance from the first floor. A second sweep selects a farthest exit from that entrance. This is a distant-pair heuristic, not an exact graph diameter on cyclic layouts. First-visited ties use N/E/S/W order. Every room centre must lie in the same connected floor component.

Attempt 1 uses the requested Long seed. Attempt n uses wrapping Long arithmetic seed + (n-1) * 1442695040888963407L, with blitz.random sequence 1. Maximum is four attempts. Effective seed/attempt are result metadata; saving just that seed without the version/options/dimensions is not a complete replay description. Fixed seeds/options/version produce identical tile and location bytes regardless of scheduling budgets or interleaved instances; the built-in RNG is untouched.

Every scan, flood queue pop, corridor cell, DFS step and retry reset yields to the budget. One operation handles at most nine cell neighbours or a constant number of records. List/Stack/Queue capacity growth can reallocate, so this is an algorithmic work allowance, not a hard real-time deadline. Teardown frees all state immediately and is proportional to owned allocations. Basic scans/floods are O(width*height). Component and room corridors additionally cost their total Manhattan lengths; worst case O(cells*(width+height)). Storage is O(cells). The fixed dimension cap bounds allocation, not process-wide available memory.

Deferred work

Deferred: worker adapters, streamed/infinite maps, hex grids, extra tile kinds, doors/keys, furnishing and enemy placement, weighted traversal, editor tools, serialized jobs and arbitrary cellular/BSP tuning. Pathfinding is unnecessary for core generation; the example's small BFS is local and not a new dependency.