One common problem of open-world roguelikes is storing the map in an efficient manner, while still making it easy to access in code. These maps are often randomly generated with an infinite expanse. Every once in a while a thread will pop up in r.g.r.d asking what structure is "best", and the options presented are usually of the form:
- Tile classes or structs for every tile
- An enum/other pre-coded method for identifying tile types as lookup values
- JavaScript-style prototypal instancing: each cell in the array is a reference to a prototype object that can be constructed at run-time
Option #1: Instances of a tile class
This method involves creating a tile class that has properties for that tile type. Examples are character to display, background & foreground, and a list of contained entities or items (although these can both be separately maintained). Instances of these can be constructed through a factory method that can make use of configuration files.
The primary advantage of this system is that it is very easy to immediately implement and to make use of it throughout your code.
The major disadvantages are memory usage and data duplication. Every grass tile having the same info and repeated across thousands of squares isn't very appealing.
public class TileMap : MapBase {
private Tile[,] Tiles { get; set; }
public void Render() {
for (var y = 0; y < Tiles.Length; y++) {
for (var x = 0; x < Tiles.GetLength(1); x++) {
Render(Tiles[y,x].Character);
}
}
}
public class Tile {
public char Character { get; set; }
public List Entities { get; set; }
}
}
Option #2: Lookup-value tiles
In this system, you have a pre-defined list of tile types, perhaps in an enum. Your rendering system has cases for each value and renders accordingly.
It's quick to setup, but it takes a large chunk of time to maintain and you have to change many places in order to make a change to one tile type. It's also very inflexible, forcing you to update your code to make a change to what should be simple data.
Code example:
public class EnumMap : MapBase {
private TileTypes[,] Tiles { get; set; }
public void Render() {
for (var y = 0; y < Tiles.Length; y++) {
for (var x = 0; x < Tiles.GetLength(1); x++) {
switch (Tiles[y, x]) {
case TileTypes.Grass: Render('.');
break;
case TileTypes.Rock: Render(',');
break;
case TileTypes.WallHor: Render('-');
break;
case TileTypes.WallVert: Render('|');
break;
}
}
}
}
public enum TileTypes {
Grass = 1,
Rock = 2,
WallVert = 3,
WallHor = 4
}
}
Option #3: Prototypal tiles
In this system, the 'tile' array is an array of references to TilePrototype objects. TilePrototype objects are constructed on the fly when a tile is generated, and holds the same type of properties as option #1, with the exception of entity/object lists. When a tile is generated, the cache of all tile types that have already been built is scanned. If there's a match, then the system just reuses this tile. Entities, objects, and items are all stored in separate lists.
This system is essentially an extension of option #2, but using runtime-constructed objects instead of enum values.
This method has the advantage of using a minimal amount of memory for constructing a vast amount of new tiles & tile types on the fly. It also allows you to manage the lists of entities in any manner you like (quadtrees for instance) without tying it to your map data structure. It really shows when using sparsely populated maps.
One major disadvantage is that this creates overhead for creating tiles. Another is that attempting to add unique features to the tile tends to cause issues - you need to invent a solution such as copying the prototype and then changing its values. I started down this path with Partridge, implementing some features (such as changing character/color) as extension methods, but ended up scrapping it.
public class PrototypeMap {
private TilePrototype[,] Tiles { get; set; }
public class TileFactory {
private static List TileCache { get; set; }
public static TilePrototype Create(char character, ConsoleColor color) {
var tile = new TilePrototype { Character = character, Color = color };
var found = TileCache.First(x => x.Equals(tile));
if (found != null)
return found;
TileCache.Add(tile);
return tile;
}
}
public class TilePrototype {
public char Character { get; set; }
public ConsoleColor Color { get; set; }
public override int GetHashCode() {
return (Character + "|" + Enum.GetName(typeof(ConsoleColor), Color)).GetHashCode();
}
public bool Equals(TilePrototype other) {
return other.Character == Character && other.Color == Color;
}
}
}
Naturally, I came up with my own solution to the tiling problem. Partridge's world is vast, but sparsely populated, and the player will only interact with a small subset of it. More importantly, the player will only change a small part of it. With this in mind, I devised the following system, based on option #3. Note that this system also implies usage of a splitting pattern, to only load in the current 'tile' of tiles and the surrounding ones, while the rest is stored to disk.
New tiles are instantiated from prototype objects, as in option #3. Certain flags - like visibility, whether it blocks light, and walkability - are stored in a separate array of bytes for quick lookup for other algorithms (these can be modified by whether or not the tile contains an entity).
a
When a tile is modified - say, a door is opened or a wall smashed down - an object (or entity) is spawned with the relevant information, and the old tile reference is set to null. In my case I'm actually storing the tiles in a separate lookup array for easier serialization, so I just set the value to 0.
public class FinalMap : MapBase {
private byte[,] TileFlags { get; set; }
private ushort[,] Tiles { get; set; }
private const int VisibleFlag = 0x01;
public void Render() {
for (var y = 0; y < Tiles.Length; y++) {
for (var x = 0; x < Tiles.GetLength(1); x++) {
if ((TileFlags[y, x] & VisibleFlag) == 1)
Render(TileManager.TileCache[Tiles[y, x]].Character);
}
}
}
public TileEntity ConvertToEntity(int x, int y) {
var tile = TileManager.TileCache[Tiles[y, x]];
var ent = new TileEntity();
ent.Character = tile.Character;
ent.Color = tile.Color;
ent.Solid = !tile.Walkable;
return ent;
}
public class TileEntity : Entity {
public char Character { get; set; }
public ConsoleColor Color { get; set; }
public bool Solid { get; set; }
//Other entity things here
//Would normally be using components
}
public class TileManager {
public static List TileCache { get; set; }
public static int CreateAndGetId(char character, ConsoleColor color) {
var tile = new TilePrototype { Character = character, Color = color };
var found = TileCache.FindIndex(x => x.Equals(tile));
if (found > 0)
return found;
TileCache.Add(tile);
return (TileCache.Count - 1);
}
}
public class TilePrototype {
public char Character { get; set; }
public ConsoleColor Color { get; set; }
public bool Walkable { get; set; }
public override int GetHashCode() {
return (Character + "|" + Enum.GetName(typeof(ConsoleColor), Color)).GetHashCode();
}
public bool Equals(TilePrototype other) {
return other.Character == Character && other.Color == Color;
}
}
}