hyarion wrote:
Let's say you have a 2d grid for a game.
e.g. tile[1000][1000] (1000x1000 tiles = 1mil tiles)
If every tile is used, this is fine. If you have a lot of 'holes', you may want to change storage of tiles.
hyarion wrote:
1. Add a variable (or array) to the tile object and store values in there.
The drawback I see to this is the waste of memory (variables/arrays for every tile even though they may not have objects).
I'd start with each object pointing to the next object in the room. That way, storage in a tile is reduced to a single pointer.
If most of the rooms have at least one object, this is fine.
The big advantage of this is that it is easy and fast to find objects at a tile.
If you have other queries, like 'give me all chairs', the above is very awkward.
hyarion wrote:
2. Have a seperate list of objects/items and do a for...next loop to find any items for the tile being drawn.
The drawback I see to this is speed. The loop is run for every single tile. If the item list is small it's fine, but if there's say 2,000 items? 20,000 items?
With 1 million tiles, only 20000 objects? That very few, I'd expect several 100 thousand tbh.
But you are right, you are wasting a lot of CPU time here :)
One simple step is to sort your objects, and use bisection. A second step is to sort them such that your order of tile drawing matches with the sort order, so you can 'walk' through the list objects in parallel with drawing tiles.
Another approach is to use hash your objects on position into a table. The basic idea is that the position becomes the key to find something (much like an index number in an array finds you the n-th item). There are a lot of different hashing forms. Read about them :)
hyarion wrote:
Is there is a better way to do this? Or which of the above is the preferred method?
Yes, it depends.
There is really no single-best solution. It depends on what questions you need answered, and how often. Getting objects based on position may cause a completely different data structure from queries on type of objects.
Some keywords to look for: lists, sets, maps/dictionaries/associative arrays, linked list, data structures, binary trees, searching, sorting
(not sure about the last two, but they are vast areas, Knuth wrote a complete book about each of them).
Another direction is to look at programming languages and their libraries. Many have the above data structures standard available.
hyarion wrote:
I was wondering if there's some way to "index" the list perhaps for faster finding of items? Databases such as MSSQL and MySQL and such have the index option to speed up queries, is there something similar that's possible to implement?
They do either hashing or some form of binary trees (or even n-ary trees).
Have fun exploring this area :D