Nicholas Dewberry

A casual blog.

Spatial hash grids make me happy to move out of engineless game development

One of the most commmon operations you’ll be doing in a video game is going to be collision detection.

"I fire this 'nade, what do I hit" or "I grab the enemy that’s closest to me."

Now, when making a game, doing this unoptimally is trivial. You take a list of objects, and to see what objects you collide with you calculate the blast radius and iterate to see what’s inside of the blast radius. For the closest enemy, you iterate through everything and find what has the lowest distance.

Now, doing it optimally is a actually a really really deep rabbit hole.

The game programming book is already mandatory reading for programmers who want to get into game development, and I am shamelessly recommending it again.

The gist of this chapter: On spatial partitioning is that you need a specialized data structure for storing the position of entities, because you need to have a data structure that can do it quickly and efficiently.

By front-loading architecture work to make your game more efficient, the development process becomes significantly easier.

When developing a small game in pygame-ce in Python, I ended up using a custom spatial grid implementation - a really, really basic one.

It feels really nice to be able to dive into the underlying data structure, and implement a lot of custom logic, rather than relying on a pre-made library that handles it.

I feel like that’s one of the differences between regular gamedev and no-engine gamedev. With no-engine gamedev I feel like I’m doing things "the right way" from first principles a lot more.

game