Way to store a lot of data in a dictionary

GGrd

Hello, so Im in the process of making a tile based game (quite similar to games like CDDA and Caves Of Qud). Currently im faced with a problem of storing positions of seen tiles; if a certain tile was ever in your field of view its excluded from fog of war. So basically my idea was to add position of a given seen tile to a dictionary: Dictionary_Name[Tile_Pos]=true, and checking if player ever discovered given tile (via for an example if Dictionary_Name[Tile_Pos]==true). But solution like this would require immense amounts of processing power after a while to check if a given position is a key in a dictionary constructef of hundreds if not thousands of keys.

Im pretty sure solution to this problem was solved somehow but i struggle to find any documentation on this topic. Perhaps making a hash table would help?

DaveTheCoder

I haven't looked into how Dictionaries are implemented. They may already use hash tables or the equivalent. It's worth looking into before implementing an alternative approach.

There's something named OrderedHashMap used in dictionary.cpp. https://github.com/godotengine/godot/blob/3.3/core/dictionary.cpp

xyz

It's very likely some type of hashing is used in dictionary implementation so performance shouldn't be a problem with couple thousand keys. You can easily benchmark this.

xyz

Benchmarked it. 10000 lookups into 100000 entry dictionary with string keys took about 4 milliseconds. You can use dictionary for this without worries.

DaveTheCoder

It might be interesting to implement a Array lookup that produces the same results using sequential searches, and see how the numbers compare.

cybereality

Dictionaries have no limit to the amount of data you can add to them, however, performance may suffer depending on what kind of algorithm you are writing. I haven't looked at the source, but dictionaries are usually implemented using hash tables, meaning to find the value of a given key happens in constant time (whether there are 10 entries or 10,000 entries, it is the same). And, anyway, for a modern computer a few thousand data values is not that much.

GGrd

So seems like its fine i just used "if in Dict" and game seems stable enough even with a lot of data, seems i underestimated how efficient the dicts in godot are