Hash-based World Storage — Handmade Hero — Episode Guide

0:00Intro

2:05Fix typo in SetCamera

3:00Recap of world coordinate wrapping problem & sparse world storage design

10:17Introduction to hash tables

15:16Hash functions

18:44Hash collisions

20:49Handling hash collisions: External chaining

25:16Handling hash collisions: Internal chaining

31:52Replace tile chunk counts with a hash table

36:24Creating the hash function

43:30Looking up entries in the hash table and creating new entries in the table

47:10Reviewing the code that has been written

58:00Moving the world origin

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: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: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: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: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: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: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: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:38:54Shouldn't Chunk->TileChunkX=0 be Chunk->NextInHash->TileChunkX? [code change]

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: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: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: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

🗩

Keyboard Navigation

Global Keys

Menu toggling

In-Menu and Index Controls

Quotes and References Menus and Index

Quotes, References and Credits Menus

Filter Menu

Filter and Link Menus

Credits Menu