So as I was reading up on Octrees and beginning to implement them and I realized that although they would be great for a world that is more or less square-ish in shape (or you could even use a number of them for longer worlds), for my purposes it's not ideal. The levels I will be building are by nature going to be more elongated, which doesn't seem to be well suited to be used with octrees. So I have decided an easier way to get things done; first of all, all the level segments are contained in a list, what I plan to do is store the indices of the tunnel segments in a hash table using their unique locations in some hashing function (haven't figured it out yet). That way, I could hash everything once before the game starts, and then using the player's location with the hashing function, find out which tunnel segment the player is nearest. From there I have the player's location relative to the list of tunnel segments and can easily check the immediate segment and the one before and after (to take care of the boundary case of collision detection).
It may not be the most space efficient (to ensure I don't get too many clusters, I may need to increase the size of the hash table if I can't figure out a better hashing function) but that is why I limited the hash table to hold only the indices, therefore only integer values. I could even use a smaller data type since I won't have nearly as many segments as an integer could represent. All the computations for the tunnel segments are done offline and only any objects that are dynamic will recalculate their hashing values online.
Overall I'm feeling pretty good about this method, the implementation is very simple, it should work great, all I need to do is spend the time to figure out a quality hashing function.
No comments:
Post a Comment