Hash-based World Storage
?
?

Keyboard Navigation

Global Keys

[, < / ], > Jump to previous / next episode
W, K, P / S, J, N Jump to previous / next marker
t / T Toggle theatre / SUPERtheatre mode
V Revert filter to original state Y Select link (requires manual Ctrl-c)

Menu toggling

q Quotes r References f Filter y Link c Credits

In-Menu Movement

a
w
s
d
h j k l


Quotes and References Menus

Enter Jump to timecode

Quotes, References and Credits Menus

o Open URL (in new tab)

Filter Menu

x, Space Toggle category and focus next
X, ShiftSpace Toggle category and focus previous
v Invert topics / media as per focus

Filter and Link Menus

z Toggle filter / linking mode

Credits Menu

Enter Open URL (in new tab)
0:00Intro
0:00Intro
0:00Intro
2:05Fix typo in SetCamera
2:05Fix typo in SetCamera
2:05Fix typo in SetCamera
3:00Recap of world coordinate wrapping problem & sparse world storage design
3:00Recap of world coordinate wrapping problem & sparse world storage design
3:00Recap of world coordinate wrapping problem & sparse world storage design
10:17Introduction to hash tables
10:17Introduction to hash tables
10:17Introduction to hash tables
15:16Hash functions
15:16Hash functions
15:16Hash functions
18:44Hash collisions
18:44Hash collisions
18:44Hash collisions
20:49Handling hash collisions: External chaining
20:49Handling hash collisions: External chaining
20:49Handling hash collisions: External chaining
25:16Handling hash collisions: Internal chaining
25:16Handling hash collisions: Internal chaining
25:16Handling hash collisions: Internal chaining
31:52Replace tile chunk counts with a hash table
31:52Replace tile chunk counts with a hash table
31:52Replace tile chunk counts with a hash table
36:24Creating the hash function
36:24Creating the hash function
36:24Creating the hash function
43:30Looking up entries in the hash table and creating new entries in the table
43:30Looking up entries in the hash table and creating new entries in the table
43:30Looking up entries in the hash table and creating new entries in the table
47:10Reviewing the code that has been written
47:10Reviewing the code that has been written
47:10Reviewing the code that has been written
58:00Moving the world origin
58:00Moving the world origin
58:00Moving the world origin
1:00:45Debugging missing entities
1:00:45Debugging missing entities
1:00:45Debugging missing entities
1:09:50Q&A
🗩
1:09:50Q&A
🗩
1:09:50Q&A
🗩
1:10:34Why not center the world at 0,0,0 and use signed ints for the tile position? [code change]
1:10:34Why not center the world at 0,0,0 and use signed ints for the tile position? [code change]
1:10:34Why not center the world at 0,0,0 and use signed ints for the tile position? [code change]
1:15:42Is a hash map essentially just a creatively shaped tile chunk? If that's the case could you preempt the hash function by contributing more bits from the Z coordinate as opposed to the X and Y for a towery map for example? Am I thinking about this right?
1:15:42Is a hash map essentially just a creatively shaped tile chunk? If that's the case could you preempt the hash function by contributing more bits from the Z coordinate as opposed to the X and Y for a towery map for example? Am I thinking about this right?
1:15:42Is a hash map essentially just a creatively shaped tile chunk? If that's the case could you preempt the hash function by contributing more bits from the Z coordinate as opposed to the X and Y for a towery map for example? Am I thinking about this right?
1:19:11What do you think about, and do you ever do, “free” optimizations in early or late stage development such as […] and instead trying to fail as early as possible? Best case scenario you only did one comparision rather than four.
1:19:11What do you think about, and do you ever do, “free” optimizations in early or late stage development such as […] and instead trying to fail as early as possible? Best case scenario you only did one comparision rather than four.
1:19:11What do you think about, and do you ever do, “free” optimizations in early or late stage development such as […] and instead trying to fail as early as possible? Best case scenario you only did one comparision rather than four.
1:22:32What sort of cookie is best for programming?
1:22:32What sort of cookie is best for programming?
1:22:32What sort of cookie is best for programming?
1:22:40What do you think about splitting the hash map code from the tile code such that you can use hash map for other stuff later on?
1:22:40What do you think about splitting the hash map code from the tile code such that you can use hash map for other stuff later on?
1:22:40What do you think about splitting the hash map code from the tile code such that you can use hash map for other stuff later on?
1:25:12You're not passing the arena to the hash lookup function.
1:25:12You're not passing the arena to the hash lookup function.
1:25:12You're not passing the arena to the hash lookup function.
1:25:46Is the world going to be generated on the fly or at game startup?
1:25:46Is the world going to be generated on the fly or at game startup?
1:25:46Is the world going to be generated on the fly or at game startup?
1:26:45Instead of chunks have you thought about spatial hashing? I'm considering it for my game to allow an open generated world but not confined to grid aligned tiles or fixed size objects.
1:26:45Instead of chunks have you thought about spatial hashing? I'm considering it for my game to allow an open generated world but not confined to grid aligned tiles or fixed size objects.
1:26:45Instead of chunks have you thought about spatial hashing? I'm considering it for my game to allow an open generated world but not confined to grid aligned tiles or fixed size objects.
1:27:21What about using an octree for sparse style storage rather than a hash map?
1:27:21What about using an octree for sparse style storage rather than a hash map?
1:27:21What about using an octree for sparse style storage rather than a hash map?
1:30:33Since you are using a memory arena for all allocations how will you handle dynamic amount of objects like enemies, particles, etc.?
1:30:33Since you are using a memory arena for all allocations how will you handle dynamic amount of objects like enemies, particles, etc.?
1:30:33Since you are using a memory arena for all allocations how will you handle dynamic amount of objects like enemies, particles, etc.?
1:30:54Shouldn't the safe margin be INT32_MAX minus margin?
1:30:54Shouldn't the safe margin be INT32_MAX minus margin?
1:30:54Shouldn't the safe margin be INT32_MAX minus margin?
1:31:39When will this little guy have feet?
1:31:39When will this little guy have feet?
1:31:39When will this little guy have feet?
1:31:50Isn't the explanation where one letter points to the next letter until the end of the word?
1:31:50Isn't the explanation where one letter points to the next letter until the end of the word?
1:31:50Isn't the explanation where one letter points to the next letter until the end of the word?
1:33:13I think you said that a hash table was just one of many ways to store the sparse data. Could you briefly mention one or a couple of the other methods?
1:33:13I think you said that a hash table was just one of many ways to store the sparse data. Could you briefly mention one or a couple of the other methods?
1:33:13I think you said that a hash table was just one of many ways to store the sparse data. Could you briefly mention one or a couple of the other methods?
1:37:24Does starting at 0 cause a problem with the tile chunks since now we are using that as the uninitialized variable? [code change]
1:37:24Does starting at 0 cause a problem with the tile chunks since now we are using that as the uninitialized variable? [code change]
1:37:24Does starting at 0 cause a problem with the tile chunks since now we are using that as the uninitialized variable? [code change]
1:38:54Shouldn't Chunk->TileChunkX=0 be Chunk->NextInHash->TileChunkX? [code change]
1:38:54Shouldn't Chunk->TileChunkX=0 be Chunk->NextInHash->TileChunkX? [code change]
1:38:54Shouldn't Chunk->TileChunkX=0 be Chunk->NextInHash->TileChunkX? [code change]
1:39:34Will you write an analog function to malloc?
1:39:34Will you write an analog function to malloc?
1:39:34Will you write an analog function to malloc?
1:40:05(follow-up) I see. I guess what I was thinking about was what the full 4Bn x 4Bn map would look like if you passed each index in the hash map the opposite way through the hash function. It seems like it doesn't matter in any case becafuse no matter what it's always going to be better than O(n) and most of the time it's O(1) with a tiny bit of performance cost to throw the coordinates through the function.
1:40:05(follow-up) I see. I guess what I was thinking about was what the full 4Bn x 4Bn map would look like if you passed each index in the hash map the opposite way through the hash function. It seems like it doesn't matter in any case becafuse no matter what it's always going to be better than O(n) and most of the time it's O(1) with a tiny bit of performance cost to throw the coordinates through the function.
1:40:05(follow-up) I see. I guess what I was thinking about was what the full 4Bn x 4Bn map would look like if you passed each index in the hash map the opposite way through the hash function. It seems like it doesn't matter in any case becafuse no matter what it's always going to be better than O(n) and most of the time it's O(1) with a tiny bit of performance cost to throw the coordinates through the function.
1:40:31Most of your comments are notes and todos. Do you ever add section title comments to separate long blocks of code?
1:40:31Most of your comments are notes and todos. Do you ever add section title comments to separate long blocks of code?
1:40:31Most of your comments are notes and todos. Do you ever add section title comments to separate long blocks of code?
1:40:53Do you see any value in adding unit tests for certain bits of this functionality?
1:40:53Do you see any value in adding unit tests for certain bits of this functionality?
1:40:53Do you see any value in adding unit tests for certain bits of this functionality?
1:41:43Can you visualize the shape of the map so I can understand why a hash table is better than an array?
1:41:43Can you visualize the shape of the map so I can understand why a hash table is better than an array?
1:41:43Can you visualize the shape of the map so I can understand why a hash table is better than an array?
1:44:40The randomized map only goes up and to the right at the moment. Is it good enough to catch bugs?
1:44:40The randomized map only goes up and to the right at the moment. Is it good enough to catch bugs?
1:44:40The randomized map only goes up and to the right at the moment. Is it good enough to catch bugs?
1:45:07Will the renderer be a separate piece of code as like the platform player so that it can be substituted with something like OpenGL?
1:45:07Will the renderer be a separate piece of code as like the platform player so that it can be substituted with something like OpenGL?
1:45:07Will the renderer be a separate piece of code as like the platform player so that it can be substituted with something like OpenGL?
1:45:18End
🗩
1:45:18End
🗩
1:45:18End
🗩