0
\$\begingroup\$

When trying to store data related to objects in my 2d top-down tile based game (specifically, blocks), I realized that I don't have an efficient solution to storing them. I could have, for example, a 2D array of them, but that would be extremely inefficient considering the amount of possible locations there are. Also, an ArrayList is inefficient becauase number one, it severly impacts cpu usage when adding/subtracting/looking up elements, and number two, it isn't ordered.

Therefore, my question is how would I go about setting up an efficient way to store objects so as to be able to find them within a certain area and also to add and subtract from them quickly?

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

If your area is very sparse you can use a Quadtree.

https://en.wikipedia.org/wiki/Quadtree

However I doubt your grid is large enough to be an issue on any modern computers. For example, a 1024x1024 grid of pointers (references) to objects would only be 4MB or 8MB depending on pointer size.

\$\endgroup\$
0
\$\begingroup\$

Just use a 1 dimensional array, it's quite easy to look thing up in it with the formulae:

index = x + y * width

Getting the coordinates from index is also simple:

x = index % width
y = floor(index / width)

Also, it's one of the smallest way in terms of memory usage

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .