Note
SHIPPED 🚢 at https://con-dog.github.io/chunked-z-level-raycaster/
A brand-new, old-school game-engine inspired by the likes of Wolfenstein 3D (1992) and Ultima Underworld: The Stygian Abyss (1992). Uses simple raycasting techniques and a uniform cell grid to render 3D.
See previous versions of this project at: v1 v2 v3
Interact with the browser-ported version here: https://con-dog.github.io/chunked-z-level-raycaster/
Vertical walls, chunks, representing a wall with 1 bit, and 2 bytes representing a vertical stack of 16 walls. Huge performance boosts (memory and speed) - But, having issues with rendering logic for verticals
 |
 |
 |
 |
Example of a 16x16x16 chunk of a map, where a bit '1' in binary represents a wall, where '0' represents no wall
uint16_t map_chunk[CHUNK_X][CHUNK_Y] = { // 0x000F means z [0-3] has walls, z [3-15] has no walls
{0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F},
{0x000F, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x0000, 0x0000, 0x0001, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x000F, 0x0000, 0x0000, 0x0002, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x0007, 0x0000, 0x0000, 0x0000, 0x0004, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x0001, 0x0001, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x000F, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x000F},
{0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F, 0x000F}};This is as memory efficient as I thought I could make a map chunk.
map_chunk_memory = 16x16x16 Bits
= 512 bytes
The value 16 for a chunk dimension works nicely, as each actual wall (non-empty cells) will have an associated struct entry, and we can pack its x-y-z coordinate (0->15) into 4 bits per-axis, which means we can use a single uint16_t to represent the coordinate of the wall within a chunk, and have room to spare:
typedef struct Wall
{
uint16_t coord; // coords in chunk - [4 flags/unused][4 bits x][4 bits y][4 bits z]
uint16_t texture_id; // Texture ID -> Value of 0 means this isn't a wall, its empty
} Wall;And for every wall there are 4 unused bits in the coord variable, that we can use as flags later on (collision modes, interactive wall etc). Could even use those 4 bits as part of the texture id, and drop the texture_id type to a uint8_t to save more memory if needed.
This is the memory footprint of 1 Wall:
wall_memory = 4 bytes
Then there is the question of the actual Chunk that stores the walls. Theoretically each chunk could store 16x16x16 = 4096 individual walls. But that memory footprint is 4bytes x 4096 = 16.384kB per chunk! But in reality, most chunks will be very sparse (sky etc empty cells) so most chunks will only need to store ~0-512 walls (just over 10% of the max). Knowing this, we can use a much smaller fixed sized array as a hash map for the actual walls in this chunk, only storing walls with data (non-empty).
For now I'm just using a fixed sized array given by WALL_HASH_SIZE, and hashing the given walls x-y-z wall coordinates with a hash function to determine an appropriate bounded index in the array to place the Wall. This hash does have collisions, so on item insertion I just keep incrementing the index until you find an empty index.
typedef struct Chunk
{
uint16_t coord; // coords in world - [8 flags/unused][8 bits x][8 bits y][8 bits z]
Wall walls[WALL_HASH_SIZE]; // Flat Array of entries, use hash_value as index into walls array
size_t length; // Number of non-empty walls, same as WALL_HASH_SIZE
} Chunk;
uint16_t do_hash_coords(uint8_t x, uint8_t y, uint8_t z)
{
uint32_t hash = (x << 8) | (y << 4) | z;
// Multiply by large prime
hash *= 2654435761u;
// Take bits 16-25 for better distribution
return (hash >> 16) & 0x3FF;
}Why do I use a fast hash map instead of a variable sized sorted array? Because I'm potentially going to be rendering a shitload of walls in one scene, I need instantaneous look-up times for walls within chunks and this method on average is O(1) access whereas binary search is Olog2(n) or a linked-list implementation is O(n)
That means on average, a chunk memory footprint is:
chunk = 4 bytes x 512 entries + (size_t + 2 bytes)
~= 2048 bytes
~= 2.048 Kilobytes
So a full map of 100x100x10 full chunks is ~204.8mB without compression.
Realistically however, most chunks (~80-90%) will be completely empty (sky , open areas etc) and so the final memory footprint is more like 204.8mB x 0.1 ~= 20.48mB on average. Pretty good! And then for chunks that aren't near the player, they can probably be compressed, getting further memory savings.
And just for completeness, here is the World data structure. Note that it only stores chunks that have content.
typedef struct World
{
Chunk chunks[CHUNK_HASH_SIZE]; // Hashed chunks coords
size_t length; // Number of chunks with walls, probably same as CHUNK_HASH_SIZE
Point_3D extent; // Max [x, y, z] of chunks
} World;
- 100x100x10 chunks maps
- Texture Atlas, different tetxures per side of wall
- Lighting system
- Thin walls
- Destructible walls/buildable walls
- Remake / Demake a Pokemon town in this "engine"
- Add 8bit audio, music blocks/textures that make a sounds on collision
- Procedurally generated worlds
- Texture transparency (ray pass-through to next texture, for things like windows etc)
- Sprites are all square/rectangular like minecraft and always face the player, but can "change direction" by changing the texture currently displayed
- Separate drawing/raycasting logic from window width and height
Animated textures, floor/wall collisions based on surface manifest, walk through doors, and just for fun - sprites - fishing.
- Levels are represented in memory as Jagged Arrays (to save memory)
- Wall and Floor maps are just CSV's (So I can quickly make levels in Excel/LibreOffice)
- Wall and Floor textures are represented by strings so I can very quickly iterate
- Walls/Floors are separate CSV's (this needs runtime tests (todo) so memory access doesn't corrupt)
- Textures/Assets are declared via a manifest.json
- Fixed visual artifacts and pixel densities
- Wall collision detection
- Basic texture mapping for walls
- Very warped tetures with many artifacts
- Very basic ray-casting
- No collision detection