Here I would like to share a data structure that I use for navigation in 3D space of a game. In essence it is a binary tree build out of linked lists.
It attempts to combine best of the two worlds 1.Linked Lists and 2.Binary Trees. So you can find a specific item in log(n) time or explore near by items in n time. This is very useful in a game where you always need to know what is near the camera, but once in a while you have to find a specific object. Below you can see the basic schema of the structure:
This pictures only one single dimension. In a game I use three dimensions but the structure allows N dimensions.
I share it as open source project on GitHub. You can find the code at https://github.com/vbodurov/space-manager. There is a visualization WPF app that can be found as one of the projects there: https://github.com/vbodurov/space-manager/tree/master/com.bodurov.NdSpace.Visualizations
Here you can see a video recording of the visualization app: