0
\$\begingroup\$

This question already has an answer here:

I'm working on a roguelike and would like to know how to structure my map data. I suppose this question could also be extended to any sort of top down 2d game. Anyways! My game will contain object types like terrain, doors, switches, monsters, and items. How should the objects be stored within a map?

Some ideas I've gathered online:

  1. The map is a 2d array. Each cell in the array can store multiple references to objects occupying it.
  2. The map contains several layers of 2d arrays, and each layer stores references to objects of a specific type.
  3. Like 1. but only store static terrain information in the 2d array. The rest of the objects are dynamic and stored in lists for each type.
\$\endgroup\$

marked as duplicate by Anko, bummzack, Seth Battin, MichaelHouse Nov 22 '13 at 20:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
\$\begingroup\$

Answering specifically for classic-style roguelikes:

Option 3 is hands-down the most efficient choice in terms of memory usage and implementation simplicity. You could store all objects in a multi-map keyed on their coordinates. You might have different data structure for items vs mobs or the like.

Option 1 requires a bunch of data for each tile to hold the lists that will always be empty for the vast majority of tiles. Option 2 duplicates even more data (the whole array) for each object type, and sounds rather inflexible.

The only thing you need for objects in the map is a fast way to query "give me everything at position (X,Y). Using some kind of map/dictionary/table works perfectly.

You may need a data structure capable of more spatial queries for more visually rich roguelikes with a lot of objects on screen at once. In this case, a quadtree (sized by tiles) would likely be better, but I've not personally ever hacked on such a roguelike. You're basically in regular 2D game territory at that point, though.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.