Spatial Maps

GoRogue provides SpatialMap and MultiSpatialMap as convenient data structures for storing game objects on a map.

Table of Contents

• Table of Contents
• Background

Background

For the sake of demonstrating SpatialMap, let us consider a simplified typical roguelike map and break it down into data structures. We'll say that our typical map has two components -- terrain and entities. Terrain will represent... Well... Terrain! Things like walls, floors, grass, etc. Entities will represent most everything else, such as monsters, items and the player.

For our example, each map location will have exactly one piece of terrain. This makes storing terrain objects/data in a traditional data structure like a 2D array a good option -- it doesn't waste space (since every location has a piece of terrain), getting the terrain at a given location is O(1) (just an array access), and iterating over all terrain is O(n) (simply iterating over each location in the 2D array).

That methodology works well for terrain, however it starts to break down when we discuss entities. Since entities represent things like items and monsters, it is very unlikely that we will have one entity at each map location -- in fact, relative to the number of locations on a map, the number of entities will likely be quite small. This makes a 2D array a poor option in terms of scalability, as it wastes (potentially a lot of) memory space since each location does not have an entity. Furthermore, iterating over each entity on the map becomes O(Width*Height), since without doing additional work we have no way to determine which locations actually contain entities and which do not.

A logical alternative might be a simple list of entities. While this solves the memory space scalability issues, this scales poorly with respect to run-time. Determining if there is an entity at a given location becomes an O(n) operation, since we must iterate through all elements in our entity list. Since such an operation might occur very frequently (for example, to attempt a move, to try to attack an enemy, to try to pick up an item), this can prove extremely undesireable as the number of entities scales. Some of these issues can be mitigated by limiting the number of entities, or creating separate entity lists for different areas of the map, however these solutions can rapidly add complexity to your code, and do not solve the core issue.

Enter Spatial Maps!