F# Doom - Part 2 - Loading the map

The source code for this part can be found on GitHub here.

After working on unpacking the graphics in the first part this time I’ve concentrated on loading the assets needed for a level. Its a fair amount of grunt work but fortunately (and unlike Wolfenstein) the data structures are pretty well documented - this is a good jump off point.

For the sake of presenting things here I’ve broken it into two parts: things and geography.

Things

The various game objects that populate the Doom game world are referred to as things. Things have a number of core attributes:

Position
Type - examples include enemies, health packs, weapons, ammo etc.)
The angle it is facing
Whether or not it is deaf

The thing type also contains a further set of properties (that are shared across all instances of the type):

Radius - the amount of space they take up
Sprite - the set of sprites that represent them
Sprite sequence - how the sprite set is animated (if it is animated at all)
Class - is it hanging, does it block etc.

There’s a lot of thing types and so to save myself some typing I wrote a simple little tool that takes the tables you can find here and converts them to some F# code:

open System.Globalization

let thingTypeFromDescriptionAndValue description value =
  match value with
  | "10" -> "BloodyMess1"
  | "12" -> "BloodyMess2"
  | "79" -> "PoolOfBlood1"
  | "80" -> "PoolOfBlood2"
  | _ ->
    let textInfo = CultureInfo("en-US", false).TextInfo
    textInfo
      .ToTitleCase(description)
      .Replace(" ", "")
      .Replace("-","")
      .Replace("(","")
      .Replace(")","")
      .Replace(",","")
      .Replace("\"","")
  
let thingClassListFromString (value:string) =
  (* the types we are using are as below:
  type ThingClass =
    | ArtifactItem
    | Pickup
    | Weapon
    | Monster
    | Obstacle
    | HangsOrFloats
  *)
  let content =
    value
    |> Seq.map(fun char ->
      match char with
      | 'A' -> "ArtifactItem"
      | 'P' -> "Pickup"
      | 'W' -> "Weapon"
      | 'M' -> "Monster"
      | 'O' -> "Obstacle"
      | '^' -> "HangsOrFloats"
      | _ -> ""
    )
    |> Seq.filter(fun s -> s.Length > 0)
    |> Seq.map(fun s -> $"ThingClass.{s}")
    |> String.concat ";"
  $"[{content}]"

open FSharp.Data
let csv = CsvFile.Load("thingTypes.csv")
let stringRows =
  csv.Rows
  |> Seq.map(fun row ->
    let value = row.GetColumn "Value"
    let radius = row.GetColumn "Radius"
    let sprite = row.GetColumn "Sprite"
    let sequence = row.GetColumn "Sequence"
    let thingClass = row.GetColumn "Class"
    let description = row.GetColumn "Description"
    let thingType = thingTypeFromDescriptionAndValue description value
    let thingClassList = thingClassListFromString thingClass
    
    // We want something that looks like this:
    //  | 0x7E7 -> { Type = ThingType.Berserk ; Class = Set.ofList [ ThingClass.ArtifactItem ] ; Radius = 20 ; Sprite = "BPAK" ; SpriteSequence = "A" }
    $"    | {value} -> {{ Type = ThingType.{thingType} ; Class = Set.ofList {thingClassList} ; Radius = {radius} ; Sprite = \"{sprite}\" ; SpriteSequence = \"{sequence}\" }}"
  )
  |> Seq.toArray
  |> String.concat "\n"
  
System.IO.File.WriteAllText ("output.fs", stringRows)

Hardly sophisticated but it did the job.

With the thing type defined all we need to do is read them from the THINGS lump in the WAD file:

type ThingDefinition =
  { Type: ThingType
    Class: Set<ThingClass>
    Radius: int
    Sprite: string
    SpriteSequence: string
  }

type Thing =
  { Definition: ThingDefinition
    Position: MapPosition
    AngleFacing: float
    IsDeaf: bool
  }

let load skillLevel (wad:byte array) (lump:LumpEntry) =
  let thingSize = 10
  let xPositionOffset = 0
  let yPositionOffset = 2
  let angleFacingOffset = 4
  let thingTypeOffset = 6
  let flagsOffset = 8
  let numberOfThings = lump.Size / thingSize
  let skillLevelBit =
    match skillLevel with
    | SkillLevel.ImTooYoungToDie
    | SkillLevel.HeyNotTooRough -> 0x1s
    | SkillLevel.HurtMePlenty -> 0x2s
    | SkillLevel.UltraViolence
    | SkillLevel.Nightmare -> 0x4s
  let multiPlayerOnlyBit = 0x10s
  let isDeafBit = 0x8s
  
  {0..numberOfThings-1}
  |> Seq.map(fun thingIndex ->
    let offset = lump.Offset + thingIndex * thingSize
    let flags = getInt16 (flagsOffset + offset) wad
    let isVisibleOnLevel = (flags &&& skillLevelBit > 0s) && (flags &&& multiPlayerOnlyBit = 0s)
    (offset,flags,isVisibleOnLevel)
  )
  |> Seq.filter(fun (_,_,isVisibleOnLevel) -> isVisibleOnLevel)
  |> Seq.map(fun (offset,flags, _) ->
    let x = getInt16 (xPositionOffset + offset) wad
    let y = getInt16 (yPositionOffset + offset) wad
    let angleFacing = getInt16 (angleFacingOffset + offset) wad
    let thingType = getInt16 (thingTypeOffset + offset) wad
    { Position = { X = int x ; Y = int y }
      Definition = ThingDefinition.Create (int thingType)
      AngleFacing = float angleFacing
      IsDeaf = (flags &&& isDeafBit) > 0s
    }
  )
  |> Seq.toArray

And that’s it. We have our things.

Geography

I’m going to focus here on simply loading these things rather than diving into how they service the renderer - we’ll come back to that when I’ve worked on the renderer itself (next, gulp).

The geography is a fair bit more complicated than the things, and the Wolfenstein map, as the data structures not only represent a level that can have different floor and ceiling heights and isn’t grid aligned but also is organised to support efficient rendering.

I’m loading all these structures but here we’ll focus on the LINEDEFS component and the VERTEXES required by them. Essentially this defines the shape of the level - where the walls are.

The vertexes are very simple - just X and Y pairs stored as int16s:

type Vertex =
  { X: int
    Y: int
  }

let loadVertexes (wad:byte array) (lump:LumpEntry) =
  let vertexByteArray = wad[lump.Offset..lump.Offset+lump.Size-1]
  let vertexSize = 4
  {0..vertexSize..lump.Size-1}
  |> Seq.map(fun baseOffset ->
    { X = getInt16 baseOffset vertexByteArray |> int
      Y = getInt16 (baseOffset+2) vertexByteArray |> int
    }
  )
  |> Seq.toArray

I’m converting everything to an int as I load it - it just makes the rest of the code simpler.

Linedefs are also pretty simple - the start and the end of them are indexes into the vertex array we loaded above.

type Linedef =
  { StartVertexIndex: int
    EndVertexIndex: int
    Flags: Set<LinedefFlags>
    SpecialType: int
    SectorTag: int
    RightSidedefIndex: int
    LeftSidedefIndex: int
  }

let loadLinedefs (wad:byte array) (lump:LumpEntry) =
  let linedefByteArray = wad[lump.Offset..lump.Offset+lump.Size-1]
  let startVertexIndex = 0
  let endVertexIndex = 2
  let flagsOffset = 4
  let specialType = 6
  let sectorTag = 8
  let rightSidedefIndex = 10
  let leftSidedefIndex = 12
  let linedefSize = 14
  
  let flags value =
    (if value &&& 0x0001 > 0 then [LinedefFlags.BlocksPlayersAndMonsters] else [])
    @ (if value &&& 0x0002 > 0 then [LinedefFlags.BlocksMonsters] else [])
    @ (if value &&& 0x0004 > 0 then [LinedefFlags.TwoSided] else [])
    @ (if value &&& 0x0008 > 0 then [LinedefFlags.UpperTextureUnpegged] else [])
    @ (if value &&& 0x0010 > 0 then [LinedefFlags.LowerTextureUnpegged] else [])
    @ (if value &&& 0x0020 > 0 then [LinedefFlags.Secret] else [])
    @ (if value &&& 0x0040 > 0 then [LinedefFlags.BlocksSound] else [])
    @ (if value &&& 0x0080 > 0 then [LinedefFlags.NeverShowsOnAutomap] else [])
    @ (if value &&& 0x0100 > 0 then [LinedefFlags.AlwaysShowsOnAutomap] else [])
    |> Set.ofList
  
  {0..linedefSize..lump.Size-1}
  |> Seq.map(fun baseOffset ->
    { StartVertexIndex = getInt16 (baseOffset + startVertexIndex) linedefByteArray |> int
      EndVertexIndex = getInt16 (baseOffset + endVertexIndex) linedefByteArray |> int
      Flags = getInt16 (baseOffset + flagsOffset) linedefByteArray |> int |> flags
      SpecialType = getInt16 (baseOffset + specialType) linedefByteArray |> int
      SectorTag = getInt16 (baseOffset + sectorTag) linedefByteArray |> int
      RightSidedefIndex = getInt16 (baseOffset + rightSidedefIndex) linedefByteArray |> int
      LeftSidedefIndex = getInt16 (baseOffset + leftSidedefIndex) linedefByteArray |> int
    }
  )
  |> Seq.toArray

I’m going to skip the loading of the other structures as they are all conceptually much the same, as I said at the start this is mostly a load of grunt work to get out the way but if you want to go through the code you can find it here.

Its worth noting that I expect to come back to Node to link it up into a tree with a discriminated union for the children.

Rendering an overhead map

The map of E1M1 in the original Doom is seared into my memory and so I thought it would be fun to quickly see if I could display an overhead map as a quick and easy way of making sure I’d got this right - or at least in the right ballpark.

As you might remember from part 1 we’re rendering by manipulating an array (via a pointer) and so I don’t have a library with a handy “draw line” feature. Fortunately drawing a line is fairly straightforward and their are a variety of algorithms you can use. I considered Wu’s algorithm before settingling on the Bresenham line algorithm as I felt that a none-anti aliased approach was more in keeping with early 90s PC gaming.

You can find the algorithm documented at the link above and my F# implementation looks like this:

let line (buffer:nativeptr<Rgba>) bufferWidth color x1 y1 x2 y2 =
  let w = x2-x1
  let h = y2-y1
  let absWidth = abs w
  let absHeight = abs h
  let dx1 = if w < 0 then -1 elif w > 0 then 1 else 0
  let dy1 = if h < 0 then -1 elif h > 0 then 1 else 0
  let dx2 =
    if absWidth <= absHeight then
      0
    else
      if w < 0 then -1 elif w > 0 then 1 else 0
  let dy2 =
    if absWidth <= absHeight then
      if h < 0 then -1 elif h > 0 then 1 else 0
    else
      0        
  let longest,shortest = if absWidth > absHeight then absWidth,absHeight else absHeight,absWidth
  
  {0..longest}
  |> Seq.fold(fun (x,y,numerator) _ ->
      NativePtr.set buffer (y*bufferWidth+x) color
      let newNumerator = numerator + shortest
      if not (numerator < longest) then
        x+dx1,y+dy1,newNumerator-longest
      else
        x+dx2,y+dy2,newNumerator
  ) (x1,y1,longest >>> 1)
  |> ignore

It doesn’t, as things stand, do any boundary checking so if you attempt to draw outside of the bounds of the buffer you’ll get a nasty memory exception due to the unsafe code. Shockingly I think last time I implemented something like this it was in the 80s in 6502 on a BBC.

We have to scale the map to fit the screen (its actual co-ordinate space is a few thousand units high and wide) but now we have our line algorithm rendering it is pretty simple:

let render (screen:FSharpDoom.Image.Image) (level:Assets.Loader.Level) =
  let left,top,right,bottom =
    level.Map.Linedefs
    |> Array.fold(fun (left,top,right,bottom) lineDef ->
      let startVertex = level.Map.Vertexes.[lineDef.StartVertexIndex]
      let endVertex = level.Map.Vertexes.[lineDef.StartVertexIndex]
      let minX = min startVertex.X endVertex.X
      let maxX = max startVertex.X endVertex.X
      let minY = min startVertex.Y endVertex.Y
      let maxY = max startVertex.Y endVertex.Y
      (
        min left minX,
        min top minY,
        max right maxX,
        max bottom maxY
      )
    ) (System.Int32.MaxValue, System.Int32.MaxValue, System.Int32.MinValue, System.Int32.MinValue)
  let width = right - left
  let height = bottom - top
  let scale = min (float (screen.Width-2) / float width) (float (screen.Height-2) / float height)
  
  use screenPtr = fixed screen.Data
  let drawLine = line screenPtr screen.Width
  
  let lineDefColor = { R = 255uy ; G = 255uy ; B = 255uy ; A = 255uy }
  let playerColor = { R = 255uy ; G = 0uy ; B = 0uy ; A = 255uy }
    level.Map.Linedefs
  |> Array.iter (fun lineDef ->
    let startVertex = level.Map.Vertexes[lineDef.StartVertexIndex]
    let endVertex = level.Map.Vertexes[lineDef.EndVertexIndex]
    
    let x1 = float (startVertex.X - left) * scale |> int
    let y1 = screen.Height - 1 - (float (startVertex.Y - top) * scale |> int)
    let x2 = float (endVertex.X - left) * scale |> int
    let y2 = screen.Height - 1 - (float (endVertex.Y - top) * scale |> int)
    
    drawLine lineDefColor x1 y1 x2 y2
  )
  
  let px = float (level.PlayerStart.X - left) * scale |> int
  let py = screen.Height - (float (level.PlayerStart.Y - top) * scale |> int)
  drawLine playerColor px (py - 3) px (py + 3)
  drawLine playerColor (px - 3) py (px + 3) py

If you run the current build you’ll see something like the below: Lumps index If you played the original Doom I’m sure that looks rather familiar!

Next Steps

With all this data loaded I can’t put off the difficult bit any longer - rendering the 3D view of the map using the original rendering techniques.

I’m not getting much spare time at the moment so it might be a good few weeks until I’ve got enough done that its worth blogging about but please - wish me luck!

If you want to discuss this or have any questions then the best place is on GitHub. I’m only really using Twitter to post updates to my blog these days.