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 There is a visualization WPF app that can be found as one of the projects there:

Here you can see a video recording of the visualization app:

Share this post:   digg     Stumble Upon     E-mail

Commenting temporarily disabled