Loading Quake engine maps in THREE.js: Part #1 - Parsing

#javascript #quake

Why to use Quake maps

For game development mostly. It is a really simple process to create complex 3D scenes using popular Quake map editors even if you are not working on a FPS game. I can imagine you can use this map format in other applications, also when creating VR environments or just prototyping.

Required skills

I assume that:

You know how to setup a JavaScript development environment and use ES modules.
You know how to use ES6 generators.
You know how to use Fetch

What can I learn here?

.map file format is pretty easy to comprehend, so I will show here how to write a simple parser that does not require full blown lexer, provided we can assume several things that simplify the process.

You can also learn how 3D objects were represented in classic games and how that approach can be still useful in modern development.

Tools

I am using Trenchbroom editor to create maps and rely on it's .map file whitespace formatting, so if you want to try this approach on your own you should use Trenchbroom also. You do not have to own classic games like Quake, Daikatana etc to create maps.

Quake map format

Those are great resources to learn more about Quake map format:

You should start there, but I will paraphrase some knowledge here and highlight important bits I found.

Quake .map files are plain text files with specific syntax, to a small degree similar to JSON. They contain a list of "entities", which can be any object that can be placed on a map (wall, 3D model, abstract metadata like player location boxes).

Roughly, .map file is a series of entities with their properties and optional brushes (brush is a definition of a 3D object):

{
 // entity 0
 "property_key" "property_value"
 {
  // brush (optional)
 }
}
{
  // entity 1
}
// (...)
{
  // entity N
}

Example map

In the image above you can see two entities:

The cube
Light box

.map file looks like this:

// Game: PersonalIdol
// Format: Standard
// entity 0
{
    "classname" "worldspawn"
    "light" "0.3"
    "_tb_textures" "./debug;./textures"
    // brush 0
    {
        ( -64 -64 128 ) ( -64 -64 -0 ) ( -64 64 -0 ) textures/texture-crate-128x128 0 0 0 1 1
        ( 64 -64 128 ) ( 64 -64 -0 ) ( -64 -64 -0 ) textures/texture-crate-128x128 0 0 0 1 1
        ( -64 -64 -0 ) ( 64 -64 -0 ) ( 64 64 -0 ) textures/texture-crate-128x128 0 0 0 1 1
        ( 64 -64 128 ) ( -64 -64 128 ) ( -64 64 128 ) textures/texture-crate-128x128 0 0 0 1 1
        ( -64 64 -0 ) ( 64 64 -0 ) ( -64 64 128 ) textures/texture-crate-128x128 0 64 0 1 1
        ( -64 64 128 ) ( 64 64 -0 ) ( 64 -64 128 ) debug/texture-uv-1024x1024 0 -0 0 1 1
        ( 64 64 -0 ) ( 64 -64 -0 ) ( 64 -64 128 ) textures/texture-crate-128x128 0 64 0 1 1
    }
}
// entity 1
{
    "classname" "light"
    "origin" "224 192 192"
    "decay" "2"
    "light" "1"
}

I think that entity definition itself is quite straightforward. It's a set of properties between brackets { "foo" "bar" }. It kind of resembles JSON, but there are no commas and colons between properties. They are organized in pairs.

Brushes

The tricky part is how to handle brushes. Quake used BSP and other algorithms that worked well with half spaces.

It means that brush definition does not give you a set of vertices to render as you might have expected, instead you have a set of at least 4 half-spaces defined by three points. To have a list of vertices we need to find intersections between those half-spaces. I'll show you how in the next parts of this series, here I'll just focus on parsing the file.

Parsing

Assumptions

To parse, we can use a few assumptions, which are true when using Trenchbroom map editor:

Each bracket (opening or closing) is in a new line
Comments only start at the beginning of the line and the entire line can be then ignored.
Each entity property is defined in a new line
Each half-space is defined in a new line

Algorithm

With those assumptions we can parse the file using this algorithm:

1. Split the `.map` file into the separate lines
2. Iterate over each line.
    1. If the line is a comment, then ignore it.
    2. If the line is empty, then ignore it.
    3. If the line is an opening bracket:
        1. If you are inside the entity definition:
            1. If you already are inside the brush definition, then it is an error.
            2. Start current brush buffer and store the current line inside it.
        2. If you are not inside the entity definition, start a new entity buffer.
    4. If it is a closing bracket: 
        1. If you have an opened brush buffer, then close it and save the brush.
        2. If you do not have an opened brush buffer:
            1. If you are not inside the entity definition, then it is an error.
            2. If you are inside the entity definition, then the entity definition is complete.
    5. If you are inside the brush, then it is the half-space definition.
    6. If you are inside the entity, but not in a brush, then it's the entity property.

This way you do not need the complex parser, lexer etc and you will still preserve the information about the line number.

Sample JavaScript implementation

This implementation follows the above algorithm and yields new entity definition each time it is sure that it's complete using a generator.

*parse() {
  const lines = this.content.split(/\r?\n/);


  let currentBrushSketch = null;
  let currentEntitySketch = null;

  // 2. Iterate over each line.
  for (let lineno = 0; lineno < lines.length; lineno += 1) {
    const line = lines[lineno];

    // 2.1. If the line is a comment, then ignore it.
    if (line.startsWith("//") || line.trim().length < 1) {
      continue;
    }

    // 3. If the line is an opening bracket:
    if (line.startsWith("{")) {
      // 3.1. Start current brush buffer and store the current line inside it.
      if (currentEntitySketch) {
        currentBrushSketch = [];
        continue;
      // 3.2. If you are not inside the entity definition, start a new entity buffer.
      } else if (!currentEntitySketch) {
        currentEntitySketch = {
          brushes: [],
          props: [],
        };
        continue;
      // 3.1.1. If you already are inside the brush definition, then it is an error.
      } else {
        throw new Error("Unexpected opening bracket.");
      }
    }

    // 2.4 If it is a closing bracket: 
    if (line.startsWith("}")) {
      // 2.4.1. If you have an opened brush buffer, then close it and save the brush.
      if (currentBrushSketch) {
        if (!currentEntitySketch) {
          throw new Error("Expected brush to be nested inside entity");
        }
        currentEntitySketch.brushes.push(new QuakeBrush(breadcrumbs.add("QuakeBrush"), currentBrushSketch));
        currentBrushSketch = null;
        continue;
      // 2.4.2. If you do not have an opened brush buffer:
      } else if (currentEntitySketch) {
        // 2.4.2.2. If you are inside the entity definition, then the entity definition is complete.
        yield {
          brushes: currentEntitySketch.brushes,
          properties: currentEntitySketch.props,
        }

        currentEntitySketch = null;
        continue;
      } else {
        // 2.4.2.1. If you are not inside the entity definition, then it is an error.
        throw new Error("Unexpected closing bracket.");
      }
    }

    if (currentBrushSketch) {
      // 5. If you are inside the brush, then it is the half-space definition.
      currentBrushSketch.push(line);
      continue;
    }

    // 6. If you are inside the entity, but not in a brush, then it's the entity property.
    if (currentEntitySketch) {
      currentEntitySketch.props.push(line);
      continue;
    }

    throw new Error("Unexpected line.");
  }

  // these two protect us from corrupted maps
  if (currentBrushSketch) {
    throw new Error("Unexpected end of brush data.");
  }

  if (currentEntitySketch) {
    throw new Error("Unexpected end of entity data.");
  }
}

Summary

To sum up, you should now have at least the basic idea how to approach Quake maps parsing in a really simple ways. In the next part I'll show how to find brush vertices using half-spaces intersections.

In the meantime, you can also check my project where I implemented this parser:
https://github.com/mcharytoniuk/personalidol
https://github.com/mcharytoniuk/personalidol/blob/b2e5d84b3d800eeaf0d7dae98d7108176eee33de/src/framework/classes/QuakeMapParser.js

Thanks for bearing with me! :)