CODEWITHSUNDEEP
algorithmdata-structuresdictionary
MoonBun
MoonBun

Reputation: 4402

Data structure for tiled map

I want to make an infinite tiled map, from (-max_int,-max_int) until (max_int,max_int), so I'm gonna make a basic structure: chunk, each chunk contain char tiles[w][h] and also it int x, y coordinates, so for example h=w=10 so tile(15,5) is in chunk(1,0) on (5,5) coordinate, and tile(-25,-17) is in chunk(-3,-2)on(5,3) and so on. Now there can be any amount of chunks and I need to store them and easy access them in O(logn) or better ( O(1) if possible.. but it's not.. ). It should be easy to: add, ??remove??(not must) and find. So what data structure should I use?

Upvotes: 1

Views: 603

Answers (2)

ony
ony

Reputation: 13253

So all your space is splited into chunks (rectangular clusters). Generally problem is storing data in sparse (since clusters already implemented) matrix. Why not to use two-level dictionary-like containers?.. I.e. rb-tree by row index where value is rb-tree by column index. Or if you are lucky you can use hashes to get your O(1). In both cases if you can't find row you allocate it in container and create new container as value but initially with only single chunk. Of course allocating new chunk on existing row will be a bit faster than on new one and I guess that's the only issue with this approach.

Upvotes: 0

Mranz
Mranz

Reputation: 1278

Read into KD-tree or Quad-tree (the 2d variant of Octree). Both of these might be a big help here.

Upvotes: 3

Related Questions