3 ms·

It is interesting to see how the levels are basically made up of axis aligned cubes Does this mean they are made on a 3d grid, like minecraft? Or just tha

by ido 5y ago

It is interesting to see how the levels are basically made up of axis aligned cubes Does this mean they are made on a 3d grid, like minecraft? Or just that all angles are 90 degrees?

phoboslab 5y ago
The levels are stored as 6 bytes per "brush" (i.e. block): 1 byte per each x, y, z coordinates and width, depth and length[1]. The y (vertical) resolution of these values is a bit higher than the x/z resolution to allow for stairs while allowing for bigger levels on the horizontal plane. So the level files are not directly stored as a grid, but as a collection of axis aligned blocks. The collision detection however builds a grid out of these, so the game can quickly look up any position within the game world[2]. [1] https://github.com/phoboslab/q1k3/blob/master/pack_map.c#L789-L792 https://github.com/phoboslab/q1k3/blob/master/pack_map.c#L78... [2] https://github.com/phoboslab/q1k3/blob/master/source/map.js#L69-L82 https://github.com/phoboslab/q1k3/blob/master/source/map.js#...
- ido 5y ago
  Thanks for the explanation! I assume you built a visual map editor to make these levels, rather than writing that data directly?
  - phoboslab 5y ago
    I used TrenchBroom[1] to build the levels. It was initially created to build Quake maps but now supports many derivative games like Half-Life, too. I can't speak highly enough of it; it's really really good! [1] https://trenchbroom.github.io/ https://trenchbroom.github.io/
n3k5 5y ago
The latter — each edge is parallel to one of three coordinate axes (X, Y, Z), which forces angles between different edges and surfaces to be multiples of 90 degrees. They don't need to be on a grid, just parallel to one. One way in which this simplifies things, for example, is checking whether two boxes overlap: They do so exactly when there is an overlap on each axis. (E.g. you look at them from the front, side, and top, and there is no gap between them. This test wouldn't be sufficient if they could be rotated arbitrarily.) The original Quake levels make use of this: a lot of things have an invisible axis-aligned bounding box (i.e. a cuboid just large enough to contain them) around them. Before checking for an exact intersection, the much cheaper test for the AABBs is performed first. This is useful even when only one of the objects tested is approximated in this way; the other one could be a bounding cylinder around a player/enemy, or a surface in the level geometry.

by ido 5y ago

It is interesting to see how the levels are basically made up of axis aligned cubes Does this mean they are made on a 3d grid, like minecraft? Or just that all angles are 90 degrees?

phoboslab 5y ago

The levels are stored as 6 bytes per "brush" (i.e. block): 1 byte per each x, y, z coordinates and width, depth and length[1]. The y (vertical) resolution of these values is a bit higher than the x/z resolution to allow for stairs while allowing for bigger levels on the horizontal plane. So the level files are not directly stored as a grid, but as a collection of axis aligned blocks. The collision detection however builds a grid out of these, so the game can quickly look up any position within the game world[2]. [1] https://github.com/phoboslab/q1k3/blob/master/pack_map.c#L789-L792 https://github.com/phoboslab/q1k3/blob/master/pack_map.c#L78... [2] https://github.com/phoboslab/q1k3/blob/master/source/map.js#L69-L82 https://github.com/phoboslab/q1k3/blob/master/source/map.js#...

ido 5y ago
Thanks for the explanation! I assume you built a visual map editor to make these levels, rather than writing that data directly?
- phoboslab 5y ago
  I used TrenchBroom[1] to build the levels. It was initially created to build Quake maps but now supports many derivative games like Half-Life, too. I can't speak highly enough of it; it's really really good! [1] https://trenchbroom.github.io/ https://trenchbroom.github.io/

n3k5 5y ago

The latter — each edge is parallel to one of three coordinate axes (X, Y, Z), which forces angles between different edges and surfaces to be multiples of 90 degrees. They don't need to be on a grid, just parallel to one. One way in which this simplifies things, for example, is checking whether two boxes overlap: They do so exactly when there is an overlap on each axis. (E.g. you look at them from the front, side, and top, and there is no gap between them. This test wouldn't be sufficient if they could be rotated arbitrarily.) The original Quake levels make use of this: a lot of things have an invisible axis-aligned bounding box (i.e. a cuboid just large enough to contain them) around them. Before checking for an exact intersection, the much cheaper test for the AABBs is performed first. This is useful even when only one of the objects tested is approximated in this way; the other one could be a bounding cylinder around a player/enemy, or a surface in the level geometry.