PROJECT NAME: Zgrid
Zgrid is a lightweight library for fast spatial queries in 2D scenes. I started working on it when dipping my toe into basic game development and wondering how best to handle collision detection. I wanted a data structure that was a bit more flexible than a uniform grid, and a bit more performance aware than the pointer-centric quad-trees I’d been introduced to at uni. I think I sort of achieved that in the end (2 years later! - though for most of the time the project lay forgotten while I was focused on other things).
Here are links to the library and a demo project built with zgrid and SDL (using Carl Åstholm’s port - which worked beautifully on every machine I tried, including a barely functioning Windows 10 laptop and a raspberry pi 5):
I also attempted to make a short youtube video which goes over installing the demo, and includes some footage from it. Unfortunately it’s come out looking a bit crap (can you tell its my first time?), but here it is anyway:
The central data structure in the library today is a SquareTree, which can be a fixed-depth BVH, or a uniform grid, or something in between depending on a parameter I’ve called compression. A little ironically, a square tree that uses maximum compression (which is effectively a uniform grid) is the fastest option in most scenarios I’ve benchmarked. The BVH only really seems to pay off when there is a very wide-range of volume sizes, or there’s a huge number of volumes packed into a small area. Anyway, even when using it as a uniform grid, the library should perform well (I put quite a bit of effort into optimising it) and hopefully the ergonomics are reasonably okay. Please let me know if you have ideas for improvements though (particularly on the API design): constructive feedback is very welcome.
I don’t want to ramble on too long in this initial post: the readme already provides an overview of the library. Would be happy to talk about implementation details if anyone is curious though!
Supported Zig versions
Zig 0.17.
AI / LLM usage disclosure
All zgrid code is handwritten, though I did make use of chat-based LLM tools for:
- Research
- Debugging
- Analysing benchmarks results
In particular I found AI very useful for 3. Dumping loads of benchmark results into text files and getting an LLM to analyse them in detail while I prepared the next batch felt really productive. Not only because of the time saved, but because I just don’t have the temperament to spend a lot of time doing this sort of work myself. Local LLMs (I’ve been using Qwen 3.8 27B) are also more than enough for this task these days.