commit ae068a9ad665bbdb451b6f4665cd232de774908a
parent 71cc0b2476ba24d62a16203dbf13c4192e1541b7
Author: amin <dev@aminmesbah.com>
Date: Sat, 4 May 2019 05:33:02 +0000
Store rooms in chunks in a hash table
FossilOrigin-Name: a262f048273aa5c531fa28a33216339929f6bf9b779955f9fcd9ef4fd2e96084
Diffstat:
5 files changed, 163 insertions(+), 26 deletions(-)
diff --git a/src/am_math.h b/src/am_math.h
@@ -193,6 +193,12 @@ internal inline v2i math_v2i_a(v2i vec1, v2i vec2)
return r;
}
+internal inline bool math_v2i_eq(v2i vec1, v2i vec2)
+{
+ bool result = (vec1.x == vec2.x && vec1.y == vec2.y);
+ return result;
+}
+
internal inline v3 math_v3_cross(v3 vec1, v3 vec2)
{
// cross product, a.k.a. outer product or vector product
@@ -570,11 +576,7 @@ internal inline bool math_v2_ge(v2 v, v2 compare)
return is_ge;
}
-internal inline bool math_is_pow_2(u64 n)
-{
- bool is_pow_2 = (n & (n - 1)) == 0;
- return is_pow_2;
-}
+#define math_is_pow_2(n) ((n) & ((n) - 1)) == 0
internal inline void math_v2_print(v2 v)
{
diff --git a/src/game.c b/src/game.c
@@ -61,9 +61,8 @@ internal void game_init(struct GameMemory *game_memory, v2u framebuffer)
},
};
- game_state->world->rooms[0] = collision_test_zone;
- game_state->world->rooms[1] = knytt_hanging_fly_village;
- game_state->world->num_rooms = 2;
+ world_room_set(game_state->world, collision_test_zone, &game_state->world_allocator);
+ world_room_set(game_state->world, knytt_hanging_fly_village, &game_state->world_allocator);
// set up and load tiles
{
@@ -183,10 +182,9 @@ void game_update_and_render(struct GameMemory *game_memory, struct GameInput *ga
m4 projection = math_projection_ortho(0.0f, framebuffer.width, framebuffer.height, 0.0f, -1.0f, 0.0f);
v2i current_room_i = game_state->player.pos.room;
- struct RoomSearchResult r = get_room_at_index(game_state->world->rooms, game_state->world->num_rooms, current_room_i);
- assert(r.room_found);
- struct Room current_room = game_state->world->rooms[r.room_array_index];
- u32 *tiles = current_room.tiles;
+ struct Room *r = world_room_get(game_state->world, current_room_i);
+ assert(r);
+ u32 *tiles = r->tiles;
// render tiles
{
@@ -478,7 +476,7 @@ void game_update_and_render(struct GameMemory *game_memory, struct GameInput *ga
}
#undef RENDER_COLLISION_DEBUG_QUAD
- player->pos = pos_recanonicalize(player->pos);
+ player->pos = world_pos_recanonicalize(player->pos);
}
// render player
diff --git a/src/game.h b/src/game.h
@@ -27,6 +27,7 @@ struct RendererState
struct Shader shader;
};
+// TODO: Move this to world.h
struct AbsolutePos
{
v2i room;
diff --git a/src/world.c b/src/world.c
@@ -1,4 +1,4 @@
-internal struct AbsolutePos pos_recanonicalize(struct AbsolutePos p)
+internal struct AbsolutePos world_pos_recanonicalize(struct AbsolutePos p)
{
struct AbsolutePos p_final = p;
v2i room_index_delta = {0};
@@ -29,24 +29,137 @@ internal struct AbsolutePos pos_recanonicalize(struct AbsolutePos p)
return p_final;
}
-struct RoomSearchResult
+internal inline v2i world_room_get_chunk_index(v2i room_i)
{
- bool room_found;
- size_t room_array_index;
-};
+ // NOTE(amin): integer division here is intentional. We want a square of
+ // CHUNK_NUM_ROOMS rooms to all have the same chunk index.
+ v2i chunk_i = {
+ (room_i.x - (room_i.x % CHUNK_ROOMS_PER_SIDE)) / CHUNK_ROOMS_PER_SIDE,
+ (room_i.y - (room_i.y % CHUNK_ROOMS_PER_SIDE)) / CHUNK_ROOMS_PER_SIDE,
+ };
+ return chunk_i;
+}
+
+internal u32 world_index_hash(v2i index)
+{
+ // http://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious
+ u16 low_x = index.x & 0xFFFF;
+ u16 low_y = index.y & 0xFFFF;
+ u32 morton_code = 0;
+
+ // TODO: profile this
+ for (u32 i = 0; i < sizeof(u32); i++)
+ {
+ morton_code |= (low_x & 1u << 0) << 0 | (low_y & 1u << 0) << (0 + 1);
+ }
+ // NOTE(amin): We're not really after any of the specific cool things about
+ // morton codes. I just picked a hash function that seemed sensible given
+ // the requirements. It makes intuitive sense to mix, rather than
+ // concatenate the bits of the two numbers, since information from both
+ // will remain even if the upper bits of the hash value are discarded (for
+ // example, when the hash value is modulo'd against the number of hash
+ // table buckets).
+ return morton_code;
+}
+
+internal struct WorldChunk* world_chunk_get(struct World *world, v2i chunk_i)
+{
+ struct WorldChunk *result = NULL;
+
+ u32 hash_value = world_index_hash(chunk_i);
+ size_t hash_table_bucket = hash_value % NUM_CHUNK_BUCKETS;
+ assert(hash_table_bucket < NUM_CHUNK_BUCKETS);
+
+ struct WorldChunk *chunk = world->chunk_ht[hash_table_bucket];
+ while (chunk)
+ {
+ if (math_v2i_eq(chunk->index, chunk_i))
+ {
+ result = chunk;
+ break;
+ }
+ chunk = chunk->next;
+ }
+
+ return result;
+}
-internal struct RoomSearchResult get_room_at_index(struct Room *rooms, u32 num_rooms, v2i room_i)
+internal struct WorldChunk* world_chunk_get_or_create(struct World *world, v2i chunk_i, struct StackAllocator *allocator)
{
- struct RoomSearchResult result = {0};
- for (size_t i = 0; i < num_rooms; i++)
+ struct WorldChunk *result = NULL;
+
+ u32 hash_value = world_index_hash(chunk_i);
+ size_t hash_table_bucket = hash_value % NUM_CHUNK_BUCKETS;
+ assert(hash_table_bucket < NUM_CHUNK_BUCKETS);
+
+ struct WorldChunk *chunk = world->chunk_ht[hash_table_bucket];
+ while (chunk)
{
- struct Room *r = &rooms[i];
- if (r->index.x == room_i.x && r->index.y == room_i.y)
+ if (math_v2i_eq(chunk->index, chunk_i))
{
- result.room_found = true;
- result.room_array_index = i;
+ result = chunk;
+ break;
}
+ chunk = chunk->next;
+ }
+
+ if (!result)
+ {
+ struct WorldChunk *prev_head_chunk = world->chunk_ht[hash_table_bucket];
+ struct WorldChunk *new_chunk = mem_st_alloc_struct(allocator, struct WorldChunk);
+ new_chunk->index = chunk_i;
+ // TODO: Init rooms to 0?
+ new_chunk->next = prev_head_chunk;
+ world->chunk_ht[hash_table_bucket] = new_chunk;
+ result = new_chunk;
}
+
+ return result;
+}
+
+internal size_t world_room_get_index_within_chunk(v2i room_i)
+{
+ v2u room_i_lower_bits = {
+ room_i.x & CHUNK_MASK_FOR_INTERNAL_ROOM_INDEX,
+ room_i.y & CHUNK_MASK_FOR_INTERNAL_ROOM_INDEX,
+ };
+ assert(room_i_lower_bits.x < CHUNK_ROOMS_PER_SIDE);
+ assert(room_i_lower_bits.y < CHUNK_ROOMS_PER_SIDE);
+
+ size_t room_i_within_chunk = room_i_lower_bits.x + room_i_lower_bits.y * CHUNK_ROOMS_PER_SIDE;
+ assert(room_i_within_chunk < CHUNK_NUM_ROOMS);
+ return room_i_within_chunk;
+}
+
+internal struct Room* world_room_get(struct World *world, v2i room_i)
+{
+ struct Room *result = NULL;
+ v2i chunk_i = world_room_get_chunk_index(room_i);
+
+ struct WorldChunk *chunk = world_chunk_get(world, chunk_i);
+ if (chunk)
+ {
+ size_t room_i_in_chunk = world_room_get_index_within_chunk(room_i);
+ result = &chunk->rooms[room_i_in_chunk];
+ }
+
+ return result;
+}
+
+internal struct Room* world_room_set(struct World *world, struct Room room, struct StackAllocator *allocator)
+{
+ struct Room *result = NULL;
+ v2i chunk_i = world_room_get_chunk_index(room.index);
+
+ struct WorldChunk* chunk = world_chunk_get_or_create(world, chunk_i, allocator);
+
+ if (chunk)
+ {
+ size_t room_i_in_chunk = world_room_get_index_within_chunk(room.index);
+ chunk->rooms[room_i_in_chunk] = room;
+ result = &chunk->rooms[room_i_in_chunk];
+ }
+
return result;
}
diff --git a/src/world.h b/src/world.h
@@ -1,18 +1,41 @@
// TODO: delete
#define MAX_ROOMS 120
+
#define ROOM_TILE_DIM_X 25
#define ROOM_TILE_DIM_Y 10
#define ROOM_TILE_COUNT ROOM_TILE_DIM_X * ROOM_TILE_DIM_Y
#define ROOM_ASPECT_RATIO (f32)ROOM_TILE_DIM_X / (f32)ROOM_TILE_DIM_Y
+#define NUM_CHUNK_BUCKETS 2048
+static_assert(
+ math_is_pow_2(NUM_CHUNK_BUCKETS),
+ "Must be a power of 2 for the hash table"
+);
+
+// TODO: Tune chunk size
+#define CHUNK_ROOMS_PER_SIDE 4
+static_assert(
+ math_is_pow_2(CHUNK_ROOMS_PER_SIDE),
+ "Must be a power of 2 for the chunk mask to work"
+);
+#define CHUNK_NUM_ROOMS (CHUNK_ROOMS_PER_SIDE * CHUNK_ROOMS_PER_SIDE)
+#define CHUNK_MASK_FOR_INTERNAL_ROOM_INDEX ((1 << CHUNK_ROOMS_PER_SIDE) - 1)
+
struct Room
{
v2i index;
u32 tiles[ROOM_TILE_COUNT];
};
+struct WorldChunk
+{
+ v2i index;
+ struct Room rooms[CHUNK_NUM_ROOMS];
+ struct WorldChunk *next;
+};
+
struct World
{
- struct Room rooms[MAX_ROOMS];
+ struct WorldChunk *chunk_ht[NUM_CHUNK_BUCKETS];
u32 num_rooms;
};
