Not logged in, Join Here! or Log In Below:  
News Articles Search    

 Home / Game Design & Programming / Neighbor distance data structure Account Manager
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.

January 29, 2005, 09:41 AM


I have a 2D field with some units moving around and I need a dynamic data structure to store those units in such a way that , for a on the fly given point P, I can traverse the units in the map from closest to P to farest away from P.
I donít know if there is something like that around. If it isnít possible, it would be also okay to be able to traverse the units from near to far relative to some other unit within the data structure (instead of a random point).

i don't know whether somthing like this exist or is simply impossible and hope it does exist :p


Samuel Hornus

January 29, 2005, 10:29 AM

A simple solution is to slice your 2D plane with a virtual grid accessed via hash-mapping on integer coordinates (of each cell). You can then update it easily at each time step, and you can retrieve neighbor units within neighboring cells, then sort them according to their distance (insertion into a std::set as you collect them will do the sorting job).
Need a "virtual grid" so as not to use memory for unused cells.

This thread contains 2 messages.
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.