Menu
I am currently writing a plugin for a game where one feature includes the ability to set areas defined by 2 two dimensional coordinates ( The upper left and lower right areas of a rectangle). These regions are then to be stored, and will have various other data associated with each region. As the player is moving about the world, I need to determine when he enters one of these regions from only the coordinates of the player, and the method of doing so must be efficient, as this will end up being called hundreds of times per second.
Are there any data structures that can efficiently support this kind of search, and if so, where can I find documentation on it, to either find a java implementation to use, or if necessary, implement it myself?
I also want to note, I found a few tree structures that only seemed to support bulk-loading, but I must be able to add and remove values from this structure in real time.
706
you should use array or vector which offers O(1) lookup-by-position to store the map.
Arrays. An array is a linear data structure that holds an ordered collection of values. It's the most efficient in storing and accessing a sequence of objects.
R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found significant use in both theoretical and applied contexts.
A heap is only really preferred if you're primarily interested in finding and/or removing the minimum / maximum, along with insertions. Either can be constructed in O(n) if you're given already-sorted data.
A good datastructure for determining collision in a part of space is the quad-tree datastructure. The quad-tree recursively divides a space according to the number of elements in a given area. Thus it can do a search if coordinates are inside a region in logarithmic time.
EDIT: I have found an implementation here but no license information is given.
107
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
