5
\$\begingroup\$

Is it a bad idea to use a map data structure (an associative array or dictionary) in game development?

According to this flowchart, the ideal container for storing game object's container would actually be a map for many games. But I've heard anecdotal claims that maps are a very bad choice for games.

Fig1

Is this true?

\$\endgroup\$
8
  • \$\begingroup\$ It depends on the map container implementation really.. But for example, a std::map from the c++ STL has many uses and one just cant predict it will be inappropriate in every situation. There are always places it can be used without any concerns and may actually be a great tool for the job.. \$\endgroup\$
    – Grimshaw
    Jun 19 '13 at 8:35
  • \$\begingroup\$ Alright, well to be specific, let's say the container will hold all of the game's GameObjects. Everything that can be rendered or needs data, as its own "Game Object". Is a map still "horrendous"? The answer I am referring to is from a high rep user who said that you should ALWAYS (emphasized) use an Array or Vector, and that a Map or Linked List is "horrendous" for game design, period. Are you saying he is wrong? \$\endgroup\$
    – user32109
    Jun 19 '13 at 8:51
  • \$\begingroup\$ I dont think that you need to find gameobject by key. Depending on a game, some game mechanics might require you to find a specific game object in some way. But thats not a problem of something that holds all game objects. \$\endgroup\$
    – Kikaimaru
    Jun 19 '13 at 9:50
  • \$\begingroup\$ associative containers are great for many things. probably not the most fit for your particular example. Whenever you have many objects and need fast iteration, its awesome to have an array or vector instead. Contiguous data in memory is very important because of cache-misses and so on. As long as you know your associative container very well, you can obtain performance gains from it you could never with arrays. \$\endgroup\$
    – Grimshaw
    Jun 19 '13 at 13:05
  • 1
    \$\begingroup\$ @Eric Hm...I get how that helps their rendering, but that still doesn't fit the use case of a map. You'd never be coding and think "I need to find the object drawn at Z-index 247; and only that one". Usually, you'd just be looping through all of them sequentially, and other data structures tend to be better for that. In that case, something to the effect of an array or vector might be better - but I'm afraid I don't immediately know which. (You could have a map in addition, to get the specific object you need for game logic though) \$\endgroup\$
    – Katana314
    Jun 19 '13 at 16:36
13
\$\begingroup\$

Are associative arrays a good idea for games? Perhaps, depending on your needs.

However, you need to differentiate between comments about "associative arrays" and specifically about the class std::map.

Associative Arrays

Associative arrays are just some kind of data structure that allows you to associate one kind of value with another, such that you can look up a value with another value. There are many kinds of associative arrays, some of which are really implemented with a regular array.

Hash tables are a form of associative array.

The "conventional wisdom" among many C-style game developers is that looking up entities by name is not worth it. This "wisdom" effectively says that your entities should be in one big global fixed-size array. When you create a new one, you find an unused index, set it to be used, and you pass the "index" around as the name.

Entities may have an actual string name, but you won't be using that to find the entity by name very often; generally speaking, you will reference entities by either pointer or index. This is still an associative array; it just uses an index rather than a name as its key value.

One pitfall you may have with associative arrays is that you may need to collate entities based on different properties. Things like "find all entities with blue hands" or whatever. Your associative array isn't going to help you; you'll have to take a linear walk down the entire list of entities to deal with that.

If your game does this kind of collation a lot, then adding other data structures might be a better way to go. Of course, that's rather complex.

std::map

std::map is a specific implementation of an associative array. And while it is the shortest associative array in the standard library, it has certain performance quirks.

Specifically, every insertion is a memory allocation. But more than that, because the memory is likely not contiguous, accessing different elements will likely miss the cache. If you ever need to walk through the list of all entities (to render them, update their position, etc), every entity is basically going to be a full cache miss.

You can read more in this PDF; it talks about std::set, but they're both the same under the hood.

The "conventional wisdom" I stated earlier tends to avoid that issue. But really, it's bad coding for C++. It's really just a poorly-designed pool allocator, and an actual pool allocation system would be far better at achieving the same effect.

A better alternative would be using Boost.Container's flat_map class. It essentially takes the concept of a sorted vector from the PDF and implements a variation of set and map from it. Insertion and deletion will be slightly painful, as it will have to shuffle elements around. They'll be more painful than the pool allocator case, certainly. But iteration will be quite fast.

However, what matters most is that you think about how much this matters. Is your game performance heavy at all? More specifically, is your game's performance going to be contingent on the memory performance of the class that contains your entities? If not, then what matters for you is user convenience. Do what it takes to get the job done. And if map does the job, use it. If it starts to become a performance issue, you should be able to replace it with something else.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ +1: Almost exactly what I would've said but you put it much better than I could have, plus I learned about boost::flat_map from this. \$\endgroup\$ Jun 19 '13 at 17:09
4
\$\begingroup\$

Take blanket statements like that with a grain of salt. Only a tiny fraction of the code in a game is performance sensitive. If a map is the collection you need, use it. Otherwise don't.

You're trying to be specific with an example of holding a bunch of "GameObjects" in a map. What are you mapping to/from? Why do you need to sort your GameObjects? If you can answer both of those questions well, then a map may very well be what you need.

From my experience, when dealing with any sort of entity system, the entity container does not have any additional data that needs to be stored outside of the GameObject, nor does the container have to be sorted. I just need everything in one place so I can quickly complete actions on all of them, an array or vector is perfect for that.

But perhaps your game, for some reason, needs a LOT of arbitrary communication between GameObjects. You give each GameObject and ID and want to be able to tell your container to get another GameObject by it's ID. After some profiling, you realize that searching through an unsorted array of GameObjects is your bottleneck because of how much searching you have to do. You figure you can refactor the ID outside of the GameObject and you want your data to stay sorted to make searching quicker. In this case you could try replacing the array with a map and see if there are any noticeable performance improvements.

On the other hand, there is something to be said about a map not being stored contiguously in memory. Looking at it through a data-oriented programming lens, maps (and all hierarchical data structures) are a nightmare. Flat data structures have less iteration overhead and cause less cache misses. Additionally, it makes parallelizing code much easier. Give each thread an index and a length and tell them to go. Assigning nodes to threads from a tree is significantly more complicated.

\$\endgroup\$
4
\$\begingroup\$

A data structure is a tool, like any other. That means it has places where it is appropriate and places where it is not, and a map is no different.

If it fulfills the need of your program, makes logical sense in the use case and contributes to the improved readability of your code, then use a map.

If that use case ever becomes a performance concern (which you'll know through regular profiling of your game), address that concern then.

You've provided no references or citations to the assertions that maps have no place in game development, but if you had I suspect those claims would be easy to dismiss as overgeneralized hand-wavy FUD.

\$\endgroup\$
3
\$\begingroup\$

Ill add that it's also very dependent on the data you're modelling, and the operations that you perform on the data. If you're just writing something simple, you're not likely to suffer the same performance problems that people who are actively pushing the hardware very hard.

Maps, or associative containers, as your diagram suggests, are fantastic for random access patterns. they're not so great for linear access. They're also pretty decent for when you need to insert and remove a lot of items. being STL, they're also going to work with very very minimal bugs (read "if it breaks, its 99.99% your code).

As always make it work first, make it fast later. The key to doing that effectively is good API design which is optimised around your access patterns, but hides the underlying data structures. Once you've got it working. profile profile profile. Its quite likely that any performance issues you will have wont be based on your usage of std::map.

The only data structure you should try and avoid at all costs is the linked list. They're terrible for linear processing due to being cache inefficient, and they're horrible for random access as you have no way to jump to a particular node without iterating the list. doubly linked lists are somewhat better, but you're far better off just using an array, or a tree.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy