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: http://blog.bodurov.com/blog/Flash/space-manager/

Share this post:   digg     Stumble Upon     del.icio.us     E-mail

Please post your comments:

Name:  
Email (optional): Your email address will not be posted.
Comments: HTML will be ignored, URLs will be converted to hyperlinks  
Enter the text you see in the box: