Sign in to follow this  

Clicking Predictable Fields: Unordered Map vs Arrays

This topic is 414 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello forum!

 

I want that my player is able to click on tiles. Since my tiles have a predictable position, I use a math function that calculates the coordinates to check for a tile. 

 

My question now is the following: Should I store my fields in an 2d array or unordered map and access via a tuple?

On the one hand, I bet arrays are more cache-friendly? On the other hand, the array might become very large with a lot of empty entries as well - since not every tile-slot within my grid will be filled.

 

I also thought about running my own implementation, as I need to know neighbours of a tile, as in tile[3][1]'s left neighbour would be tile[4][1] and lower neighbour would be tile[3][2]. Neighbours are nothing more but references.

 

Maybe making my very own implementation for this an overkill, as I do not want to look up 500 objects.

 

I would be very thankful if you could help me with my approach.

Thanks for taking your time to read my thread!

Share this post


Link to post
Share on other sites

So how many tiles are we talking about and how many tiles of that are not used?

How much memory does that involve (ie how large is a tile in bytes)?

 

As a general rule, go with the simplest solution and ignore any sub-optimalities is usually the best way.

 

If you suspect you may want to change eg map representation, wrap an access object around it (if you don't have one already), so you can change the representation without everything around it dying.

Share this post


Link to post
Share on other sites
Cache friendly storage is most beneficial when your access patterns are cache friendly too (i.e. predicatable / linear).

If your user will be clicking on "random" tiles, then the cache won't be great at handling this.

That said, users are very slow compared to your computer. From your program's point of view, the user is like a glacier - hardly moving at all! There probably won't be a huge difference between the two for this use case.

However, if the tiles are accessed by other parts of your program, e.g. A.I. needing to determine what to do, then a storage model that supports this access pattern might be still be worthwhile.

Share this post


Link to post
Share on other sites
Basically, where possible, always choose an array/vector. This isn't even just game advice - you see the same advice tossed around by the folks at Google, Facebook, Microsoft, etc. Arrays are the superior data structure, assuming you

An index into an array is a much faster O(1) than a hash table lookup. _Much_ faster. Possibly a single LEA instruction (on x86) compared to a big ball of hash computations and bucket chain indirection and key comparisons that goes into a hash table.

If you're worried about the size of your arrays, chunk them. This can actually make your code _even faster_, btw, as it can improve the cache locality of adjacent tile lookups (in an array, tiles next to each other in separate rows are a full pitch-length away from each other in memory, so keeping that pitch-length small can allow all your tiles in a local region to fit in cache); this is what a GPU does with a texture for instance to make texture sampling faster. The basics is to break your map down into some kind of X-by-X chunks. For instance, 64 tiles by 64 tiles. The tiles within a chunk are looked up as array accesses. The chunks themselves are stored in an efficient lookup structure like an octree or hash. Even with hashes, this reduces your hash lookups from one lookup per tile to one lookup per chunk, which is quite a bit faster. With the right data in your chunks, you don't even necessarily need to do that - your camera should have an idea which chunk it is centered on and then can use inter-chunks links to find all the adjacent chunks in a single pointer indirection.

This essentially gives you a spare tiled world in an efficient form. You only pay for empty tiles if you have empty space cutting through the middle of a chunk, which is easy to avoid to doing at design time, and is a small cost to pay even if you don't avoid it since it'll only happen at boundaries with empty space.e linked list walk for every lookup, rather than the kinds of hash tables games like that require no extra allocation and either no linked list following or a cache-aware bucket probing.)

On a mildly related note, unordered_map is a pretty bad hash table. You can do a lot better if you're even mildly familiar with how to implement such things. (It's a known issue and somewhat difficult to fix adeque

Share this post


Link to post
Share on other sites

This topic is 414 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this