- Home /
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.
Answer by robertbu · Oct 29, 2014 at 04:46 AM
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.
Your answer
Follow this Question
Related Questions
A* Pathfinding Project Problem with Obstacles 2 Answers
How to do step based movement 3 Answers
infinite 2d grid in an Editor Window 1 Answer
How to create a 2D grid based array with passable/impassable grids for movement ? 1 Answer
How do I distribute cells in a grid with the new UI from script? 1 Answer