Voxel Flood Fill for Collision Search — Handmade Hero — Episode Guide

0:00Recap and set the stage for the day

🗩

0:00Recap and set the stage for the day

🗩

0:00Recap and set the stage for the day

🗩

3:21Direct vs path-solved collision voxel movement

🏃

3:21Direct vs path-solved collision voxel movement

🏃

3:21Direct vs path-solved collision voxel movement

🏃

5:04Path solvers: Dijkstra, A*

🏃

5:04Path solvers: Dijkstra, A*

🏃

5:04Path solvers: Dijkstra, A*

🏃

6:14Turning our collision system into more of an A* style search

🏃

6:14Turning our collision system into more of an A* style search

🏃

6:14Turning our collision system into more of an A* style search

🏃

7:25Describe the direct-descent collision in MoveEntity()

📖

7:25Describe the direct-descent collision in MoveEntity()

📖

7:25Describe the direct-descent collision in MoveEntity()

📖

9:53Begin to switch MoveEntity() to do flood fill collision search, separating out the Collision testing and Movement loops

16:46Conceptualising flood fill

🗩

16:46Conceptualising flood fill

🗩

16:46Conceptualising flood fill

🗩

19:41Stack up the voxels to test for collision tracking purposes in MoveEntity()

26:22Automatic stacking by proximity

🗩

26:22Automatic stacking by proximity

🗩

26:22Automatic stacking by proximity

🗩

27:28Respecify UpdateBest() as PushVoxelCheck() in MoveEntity()

30:18Consider checking voxels more efficiently

🗩

30:18Consider checking voxels more efficiently

🗩

30:18Consider checking voxels more efficiently

🗩

34:04Make MoveEntity() consider the voxels in only the six 3D cardinal directions

43:39Consider how to produce the closest point

🗩

43:39Consider how to produce the closest point

🗩

43:39Consider how to produce the closest point

🗩

45:27Note our possible inability to use GetClosestPointInBoxConservative() for LocalFromP

45:52Consider how to produce the closest point (cont.)

🗩

45:52Consider how to produce the closest point (cont.)

🗩

45:52Consider how to produce the closest point (cont.)

🗩

47:56Introduce a voxel_stack and helper functions: PushVoxelStack() and PopVoxelStack()

56:27Molly: Meow

🐱

56:27Molly: Meow

🐱

56:27Molly: Meow

🐱

57:32yanchith_the_kind By the way, does anyone here know why the sphere collision geometries should help sliding around corners with "Search in P"?

🗪

57:32yanchith_the_kind By the way, does anyone here know why the sphere collision geometries should help sliding around corners with "Search in P"?

🗪

57:32yanchith_the_kind By the way, does anyone here know why the sphere collision geometries should help sliding around corners with "Search in P"?

🗪

59:22Make MoveEntity() call PushVoxelStack()

1:00:24Introduce PopVoxelStack()

1:01:06Note an optimisation in PushVoxelStack(): Known early termination

1:02:57Implement PopVoxelStack(), and introduce StackNotEmpty() for MoveEntity() to call

1:07:09Consider how to handle embedding, in our flood search scheme

🗩

1:07:09Consider how to handle embedding, in our flood search scheme

🗩

1:07:09Consider how to handle embedding, in our flood search scheme

🗩

1:08:53Plan our next steps in MoveEntity()

🗩

1:08:53Plan our next steps in MoveEntity()

🗩

1:08:53Plan our next steps in MoveEntity()

🗩

1:09:35Delete UpdateBest() and voxel_move

1:10:18Specify how MoveEntity() accepts motion

1:14:57Consider our problem with GetClosestPointInBoxConservative()

🗩

1:14:57Consider our problem with GetClosestPointInBoxConservative()

🗩

1:14:57Consider our problem with GetClosestPointInBoxConservative()

🗩

1:17:00Fix compile errors in MoveEntity()

1:17:49Consider caching the collision voxel checks

🗩

1:17:49Consider caching the collision voxel checks

🗩

1:17:49Consider caching the collision voxel checks

🗩

1:19:06Make MoveEntity() set up the collision voxel stack

1:25:12Reflect on the current state of our flood search routine

🗩

1:25:12Reflect on the current state of our flood search routine

🗩

1:25:12Reflect on the current state of our flood search routine

🗩

1:26:00TODO(casey): We should use the minimum grid size necessary to bound the from/to points...

1:27:00Q&A

🗩

1:27:00Q&A

🗩

1:27:00Q&A

🗩

1:27:05Make MoveEntity() compute and use the minimum grid size necessary to bound the from / to points

1:35:10Q&A for reals

🗩

1:35:10Q&A for reals

🗩

1:35:10Q&A for reals

🗩

1:36:04thesandvichmaker Q: Does your in-house editor cache tokens for a buffer and keep them around? I have my incremental tokenization but the memory overhead is pretty gross and unnecessary. I'm thinking of just fully caching line states (like whether you're in a block comment or not) and then caching only N lines of tokens with LRU eviction or something. I have a suspicion I am just overcomplicating things

🗪

1:36:04thesandvichmaker Q: Does your in-house editor cache tokens for a buffer and keep them around? I have my incremental tokenization but the memory overhead is pretty gross and unnecessary. I'm thinking of just fully caching line states (like whether you're in a block comment or not) and then caching only N lines of tokens with LRU eviction or something. I have a suspicion I am just overcomplicating things

🗪

1:36:04thesandvichmaker Q: Does your in-house editor cache tokens for a buffer and keep them around? I have my incremental tokenization but the memory overhead is pretty gross and unnecessary. I'm thinking of just fully caching line states (like whether you're in a block comment or not) and then caching only N lines of tokens with LRU eviction or something. I have a suspicion I am just overcomplicating things

🗪

1:36:33bearexplicit Q: PushVoxelStack has typo two times: double I.z?

🗪

1:36:33bearexplicit Q: PushVoxelStack has typo two times: double I.z?

🗪

1:36:33bearexplicit Q: PushVoxelStack has typo two times: double I.z?

🗪

1:36:41Fix typos in PushVoxelStack()

1:36:46Caching considerations in parsing

🗩

1:36:46Caching considerations in parsing

🗩

1:36:46Caching considerations in parsing

🗩

1:40:10yanchith_the_kind Q: What do you think about using Search in P in games with movement that should feel "physically correct" (gravity, jumping, etc.)? Is there an extension of your work on The Witness that would work well there, or would you go with a classical approach like GJK or MPR?

🗪

1:40:10yanchith_the_kind Q: What do you think about using Search in P in games with movement that should feel "physically correct" (gravity, jumping, etc.)? Is there an extension of your work on The Witness that would work well there, or would you go with a classical approach like GJK or MPR?

🗪

1:40:10yanchith_the_kind Q: What do you think about using Search in P in games with movement that should feel "physically correct" (gravity, jumping, etc.)? Is there an extension of your work on The Witness that would work well there, or would you go with a classical approach like GJK or MPR?

🗪

1:45:21thesandvichmaker handmade_hero parsing is definitely what has made this text editor feel like a mistake. I figured I might as well follow through making it because of how easy it is to improve upon the functionality of my daily driver (vim), but text editing is definitely sad. I had been retokenizing fully on every edit but it got too slow especially when making multiple edits on a single keystroke (for example with multiple cursors)

🗪

1:45:21thesandvichmaker handmade_hero parsing is definitely what has made this text editor feel like a mistake. I figured I might as well follow through making it because of how easy it is to improve upon the functionality of my daily driver (vim), but text editing is definitely sad. I had been retokenizing fully on every edit but it got too slow especially when making multiple edits on a single keystroke (for example with multiple cursors)

🗪

1:45:21thesandvichmaker handmade_hero parsing is definitely what has made this text editor feel like a mistake. I figured I might as well follow through making it because of how easy it is to improve upon the functionality of my daily driver (vim), but text editing is definitely sad. I had been retokenizing fully on every edit but it got too slow especially when making multiple edits on a single keystroke (for example with multiple cursors)

🗪

1:48:06technicbeam Jon's streaming today, or at least he is right now

🗪

1:48:06technicbeam Jon's streaming today, or at least he is right now

🗪

1:48:06technicbeam Jon's streaming today, or at least he is right now

🗪

1:48:28natte84 Q: How would one store text instead?

🗪

1:48:28natte84 Q: How would one store text instead?

🗪

1:48:28natte84 Q: How would one store text instead?

🗪

1:50:03jojomunki So books are okay as text? But program files would need some sort of idea about discrete chunks, i.e. structs, functions, whatever?

🗪

1:50:03jojomunki So books are okay as text? But program files would need some sort of idea about discrete chunks, i.e. structs, functions, whatever?

🗪

1:50:03jojomunki So books are okay as text? But program files would need some sort of idea about discrete chunks, i.e. structs, functions, whatever?

🗪

1:51:38natte84 How much does compression help with this? Doesn't compression map it better?

🗪

1:51:38natte84 How much does compression help with this? Doesn't compression map it better?

🗪

1:51:38natte84 How much does compression help with this? Doesn't compression map it better?

🗪

1:52:22h0stman What is the alternative?

🗪

1:52:22h0stman What is the alternative?

🗪

1:52:22h0stman What is the alternative?

🗪

1:55:490xf3f3 Q: So a C/C++ file just with free functions and no declarations / definitions between these functions is pretty much random access?

🗪

1:55:490xf3f3 Q: So a C/C++ file just with free functions and no declarations / definitions between these functions is pretty much random access?

🗪

1:55:490xf3f3 Q: So a C/C++ file just with free functions and no declarations / definitions between these functions is pretty much random access?

🗪

1:56:40androthi So C files would have all the defines in a separate data area?

🗪

1:56:40androthi So C files would have all the defines in a separate data area?

🗪

1:56:40androthi So C files would have all the defines in a separate data area?

🗪

1:57:37centhusiast Q: So the JSON format is also bad in that sense because it is a text format?

🗪

1:57:37centhusiast Q: So the JSON format is also bad in that sense because it is a text format?

🗪

1:57:37centhusiast Q: So the JSON format is also bad in that sense because it is a text format?

🗪

1:58:48mtxset But if code is in, let's say AST, you won't be able to use any text editor to modify it. You will need some specific software

🗪

1:58:48mtxset But if code is in, let's say AST, you won't be able to use any text editor to modify it. You will need some specific software

🗪

1:58:48mtxset But if code is in, let's say AST, you won't be able to use any text editor to modify it. You will need some specific software

🗪

1:59:43f__stein Q: You should get the new Remedy if you have not already. It has some nice stuff¹

🗪

1:59:43f__stein Q: You should get the new Remedy if you have not already. It has some nice stuff¹

🗪

1:59:43f__stein Q: You should get the new Remedy if you have not already. It has some nice stuff¹

🗪

2:00:47thesandvichmaker Remedy 0.3.6 was pretty crashy for me when I was on my laptop

🗪

2:00:47thesandvichmaker Remedy 0.3.6 was pretty crashy for me when I was on my laptop

🗪

2:00:47thesandvichmaker Remedy 0.3.6 was pretty crashy for me when I was on my laptop

🗪

2:01:25midnightsun55 Are there any editors or programming languages that don't use text and can highlight gigabyte files currently?

🗪

2:01:25midnightsun55 Are there any editors or programming languages that don't use text and can highlight gigabyte files currently?

🗪

2:01:25midnightsun55 Are there any editors or programming languages that don't use text and can highlight gigabyte files currently?

🗪

2:02:33centhusiast Q: What happened to RAD Game Tools. Did Epic Games buy the company?

🗪

2:02:33centhusiast Q: What happened to RAD Game Tools. Did Epic Games buy the company?

🗪

2:02:33centhusiast Q: What happened to RAD Game Tools. Did Epic Games buy the company?

🗪

2:03:38midnightsun55 If you still worked at RAD would you have got a massive bag of cash?

🗪

2:03:38midnightsun55 If you still worked at RAD would you have got a massive bag of cash?

🗪

2:03:38midnightsun55 If you still worked at RAD would you have got a massive bag of cash?

🗪

2:07:03natte84 Q: How is the sale platform for SCG progressing?

🗪

2:07:03natte84 Q: How is the sale platform for SCG progressing?

🗪

2:07:03natte84 Q: How is the sale platform for SCG progressing?

🗪

2:10:02sentientcoffee Jonathan raid yay

🗪

2:10:02sentientcoffee Jonathan raid yay

🗪

2:10:02sentientcoffee Jonathan raid yay

🗪

2:11:49Thoughts on e-commerce server engineering when your payment processor is, and is not, reliable

🗩

2:11:49Thoughts on e-commerce server engineering when your payment processor is, and is not, reliable

🗩

2:11:49Thoughts on e-commerce server engineering when your payment processor is, and is not, reliable

🗩

2:14:25mindmark42 Q: How do you even test your code against an unreliable payment processor?

🗪

2:14:25mindmark42 Q: How do you even test your code against an unreliable payment processor?

🗪

2:14:25mindmark42 Q: How do you even test your code against an unreliable payment processor?

🗪

2:16:44gir33 The whole idea of crypto is decentralizing "trust"

🗪

2:16:44gir33 The whole idea of crypto is decentralizing "trust"

🗪

2:16:44gir33 The whole idea of crypto is decentralizing "trust"

🗪

2:19:38davr0s Yeah, after an economic collapse, people still still have GPUs going on crypto, they won't just be fighting over food and water

🗪

2:19:38davr0s Yeah, after an economic collapse, people still still have GPUs going on crypto, they won't just be fighting over food and water

🗪

2:19:38davr0s Yeah, after an economic collapse, people still still have GPUs going on crypto, they won't just be fighting over food and water

🗪

2:20:34futuremillennium Q: Can you make your cam bigger for the Q&A?

🗪

2:20:34futuremillennium Q: Can you make your cam bigger for the Q&A?

🗪

2:20:34futuremillennium Q: Can you make your cam bigger for the Q&A?

🗪

2:21:05stathibus Have we had a Casey rant about NFTs yet?

🗪

2:21:05stathibus Have we had a Casey rant about NFTs yet?

🗪

2:21:05stathibus Have we had a Casey rant about NFTs yet?

🗪

2:22:38demonixtb It isn't even that because at no step in creating an NFT you cannot confirm the person creating it actually owns the item

🗪

2:22:38demonixtb It isn't even that because at no step in creating an NFT you cannot confirm the person creating it actually owns the item

🗪

2:22:38demonixtb It isn't even that because at no step in creating an NFT you cannot confirm the person creating it actually owns the item

🗪

2:26:38jazzrabbitt handmade_hero Then you can say the same for any art. What are they solving? What is the painting that is hanging in my room solving?

🗪

2:26:38jazzrabbitt handmade_hero Then you can say the same for any art. What are they solving? What is the painting that is hanging in my room solving?

🗪

2:26:38jazzrabbitt handmade_hero Then you can say the same for any art. What are they solving? What is the painting that is hanging in my room solving?

🗪

2:29:39j_blow With Mona Lisa, they actually hang fakes intentionally most of the time, so they don't get damaged by all the jerks taking flash photography nonstop

🗪

2:29:39j_blow With Mona Lisa, they actually hang fakes intentionally most of the time, so they don't get damaged by all the jerks taking flash photography nonstop

🗪

2:29:39j_blow With Mona Lisa, they actually hang fakes intentionally most of the time, so they don't get damaged by all the jerks taking flash photography nonstop

🗪

2:30:42f__stein I was very surprised how small the Mona Lisa was, when I saw it. Popular media always depicts it as bigger

🗪

2:30:42f__stein I was very surprised how small the Mona Lisa was, when I saw it. Popular media always depicts it as bigger

🗪

2:30:42f__stein I was very surprised how small the Mona Lisa was, when I saw it. Popular media always depicts it as bigger

🗪

2:31:12jazzrabbitt handmade_hero It is an appreciation and value of the creation. If I would create the exact game of yours after two years from publication, no one would buy it. I would say there is an appreciation to creation in society which makes the original piece valuable

🗪

2:31:12jazzrabbitt handmade_hero It is an appreciation and value of the creation. If I would create the exact game of yours after two years from publication, no one would buy it. I would say there is an appreciation to creation in society which makes the original piece valuable

🗪

2:31:12jazzrabbitt handmade_hero It is an appreciation and value of the creation. If I would create the exact game of yours after two years from publication, no one would buy it. I would say there is an appreciation to creation in society which makes the original piece valuable

🗪

2:32:42ultrascientism NFTs produce a lot of excess CO2

🗪

2:32:42ultrascientism NFTs produce a lot of excess CO2

🗪

2:32:42ultrascientism NFTs produce a lot of excess CO2

🗪

2:33:24yanchith_the_kind Totally agree with value being subjective to the person buying the art. How does this tie into supporting the artist? Don't NFTs help there?

🗪

2:33:24yanchith_the_kind Totally agree with value being subjective to the person buying the art. How does this tie into supporting the artist? Don't NFTs help there?

🗪

2:33:24yanchith_the_kind Totally agree with value being subjective to the person buying the art. How does this tie into supporting the artist? Don't NFTs help there?

🗪

2:34:12johnm___ handmade_hero What about using NFT for creating a digital used market? I can't sell you a game I bought off steam

🗪

2:34:12johnm___ handmade_hero What about using NFT for creating a digital used market? I can't sell you a game I bought off steam

🗪

2:34:12johnm___ handmade_hero What about using NFT for creating a digital used market? I can't sell you a game I bought off steam

🗪

2:35:34zufaelligertyp Hey, the idea to want to be close to the actual thing that da Vinci touched with his hands is somewhat relatable. Not important for everybody, but it's certainly not "arbitrary"

🗪

2:35:34zufaelligertyp Hey, the idea to want to be close to the actual thing that da Vinci touched with his hands is somewhat relatable. Not important for everybody, but it's certainly not "arbitrary"

🗪

2:35:34zufaelligertyp Hey, the idea to want to be close to the actual thing that da Vinci touched with his hands is somewhat relatable. Not important for everybody, but it's certainly not "arbitrary"

🗪

2:39:56holophonist MaIlchad No it's because I'm interested in the history of certain pieces of art. If that's "arbitrary" then so is anything else you value

🗪

2:39:56holophonist MaIlchad No it's because I'm interested in the history of certain pieces of art. If that's "arbitrary" then so is anything else you value

🗪

2:39:56holophonist MaIlchad No it's because I'm interested in the history of certain pieces of art. If that's "arbitrary" then so is anything else you value

🗪

2:42:39jwindahouse How did Avengers create value to society? If anything it has negative value because it stole two hours of people's lives they could have used to create actual value

🗪

2:42:39jwindahouse How did Avengers create value to society? If anything it has negative value because it stole two hours of people's lives they could have used to create actual value

🗪

2:42:39jwindahouse How did Avengers create value to society? If anything it has negative value because it stole two hours of people's lives they could have used to create actual value

🗪

2:44:30jazzrabbitt handmade_hero What should be the price of Mona Lisa? Every copy of Mona Lisa should be 1 million, then, or should all be 1 dollar including original?

🗪

2:44:30jazzrabbitt handmade_hero What should be the price of Mona Lisa? Every copy of Mona Lisa should be 1 million, then, or should all be 1 dollar including original?

🗪

2:44:30jazzrabbitt handmade_hero What should be the price of Mona Lisa? Every copy of Mona Lisa should be 1 million, then, or should all be 1 dollar including original?

🗪

2:47:01mtxset handmade_hero This sounds like tulips bubble or more recent coin bubble, or more recent crypto bubble

🗪

2:47:01mtxset handmade_hero This sounds like tulips bubble or more recent coin bubble, or more recent crypto bubble

🗪

2:47:01mtxset handmade_hero This sounds like tulips bubble or more recent coin bubble, or more recent crypto bubble

🗪

2:48:15botondar So how much can I buy the Wacom tablet for that da Vinci painted the Mona Lisa with?

🗪

2:48:15botondar So how much can I buy the Wacom tablet for that da Vinci painted the Mona Lisa with?

🗪

2:48:15botondar So how much can I buy the Wacom tablet for that da Vinci painted the Mona Lisa with?

🗪

2:48:35Assuming the great masters all used an iPad Pro, would they all have been arrested for child porn after Apple flagged them?

🗩

2:48:35Assuming the great masters all used an iPad Pro, would they all have been arrested for child porn after Apple flagged them?

🗩

2:48:35Assuming the great masters all used an iPad Pro, would they all have been arrested for child porn after Apple flagged them?

🗩

2:50:55creikey handmade_hero If the value of art is arbitrarily decided by people, why can't originality be arbitrarily chosen as valuable?

🗪

2:50:55creikey handmade_hero If the value of art is arbitrarily decided by people, why can't originality be arbitrarily chosen as valuable?

🗪

2:50:55creikey handmade_hero If the value of art is arbitrarily decided by people, why can't originality be arbitrarily chosen as valuable?

🗪

2:54:44holophonist Yeah, instead of curating and verifying priceless art, they should be doing something productive like making a videogame!

🗪

2:54:44holophonist Yeah, instead of curating and verifying priceless art, they should be doing something productive like making a videogame!

🗪

2:54:44holophonist Yeah, instead of curating and verifying priceless art, they should be doing something productive like making a videogame!

🗪

2:56:26pengaruu Pyramids are pretty damn useless and quite permanent

🗪

2:56:26pengaruu Pyramids are pretty damn useless and quite permanent

🗪

2:56:26pengaruu Pyramids are pretty damn useless and quite permanent

🗪

2:57:12Closing thoughts about energy wasted on NFTs and cryptocurrencies

🗩

2:57:12Closing thoughts about energy wasted on NFTs and cryptocurrencies

🗩

2:57:12Closing thoughts about energy wasted on NFTs and cryptocurrencies

🗩

2:59:54ultrascientism Crypto also carries anti-bank, anti-government ideological strain

🗪

2:59:54ultrascientism Crypto also carries anti-bank, anti-government ideological strain

🗪

2:59:54ultrascientism Crypto also carries anti-bank, anti-government ideological strain

🗪

3:01:31creikey handmade_hero The payment processors aren't the government, though, they're a private institution who don't own a military and couldn't stop something like crypto

🗪

3:01:31creikey handmade_hero The payment processors aren't the government, though, they're a private institution who don't own a military and couldn't stop something like crypto

🗪

3:01:31creikey handmade_hero The payment processors aren't the government, though, they're a private institution who don't own a military and couldn't stop something like crypto

🗪

3:02:13midnightsun55 handmade_hero By that argument, having passwords is useless, because a robber can make you type the password by force

🗪

3:02:13midnightsun55 handmade_hero By that argument, having passwords is useless, because a robber can make you type the password by force

🗪

3:02:13midnightsun55 handmade_hero By that argument, having passwords is useless, because a robber can make you type the password by force

🗪

3:04:32ultrascientism With crypto, governments technically can't confiscate your money (without torturing passwords out of you). They can make it very difficult to spend that money

🗪

3:04:32ultrascientism With crypto, governments technically can't confiscate your money (without torturing passwords out of you). They can make it very difficult to spend that money

🗪

3:04:32ultrascientism With crypto, governments technically can't confiscate your money (without torturing passwords out of you). They can make it very difficult to spend that money

🗪

3:05:08infinityjest handmade_hero But couldn't society decide that we switch to crypto for our currency, and change the laws accordingly?

🗪

3:05:08infinityjest handmade_hero But couldn't society decide that we switch to crypto for our currency, and change the laws accordingly?

🗪

3:05:08infinityjest handmade_hero But couldn't society decide that we switch to crypto for our currency, and change the laws accordingly?

🗪

3:07:04mailchad Oh yeah, turns out that's not true: blockchain is public, if you know the size of the transaction and when, you can trace it back quite quickly

🗪

3:07:04mailchad Oh yeah, turns out that's not true: blockchain is public, if you know the size of the transaction and when, you can trace it back quite quickly

🗪

3:07:04mailchad Oh yeah, turns out that's not true: blockchain is public, if you know the size of the transaction and when, you can trace it back quite quickly

🗪

3:07:39That's it

🗩

3:07:39That's it

🗩

3:07:39That's it

🗩

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