koobas.hobune.stream
Irregular grid, data structure
Hi, Im wondering what is the best data structure for grid containing different sized rectangles/squares as game map sectors. I need to acces object within that grid by simple xyz coordinates.
I searched for KdTrees, but they seem to find nearest object, I found also segment trees/interval trees but there is little info about them Cheers.
Your data structure will depend on 1) what operations can be done on the sectors at runtime, 2) if the sectors can be divided along a regular grid, 3) the number of sectors, 4) the frequency of searches, 5) 2D vs 3D, 6) etc.
Why not just a simple list of rectangles or bounds...one entry for each sector? Then you could just scan through the list looking if a point is in each rect or bounds. Or if your larger objects are built around a smaller primitive grid, create an array of integers where every cell indicates what sector it belongs to. Or you could create a data structure based on a regular grid of cells with each cell indicating what sectors are inside it.
