Storing tile grid in a matrix: row major vs column major

Question

I'm using a generic matrix container to store the tile grid for my RTS game.

This is where I am confused: a matrix is traditionally row major, i.e. matrix(0, 10) means 'at 0th row, 10th column.' A map on the other hand is 'column major,' i.e. grid(0, 10) intuitively means 'a tile at X=0, Y=10.'

This leads to a quite a few places where I need to swap X and Y to access proper element of the map.

I tried to make them both consistent (i.e. make a matrix column major or a grid row major) but that adds more confusion, maybe because I'm a slave of my habits.

How should I do this?

Answer 1

"Row-major" and "column-major" are describing the storage layout of the data, not the indexing API. What you have provided in your question is a decision between indexing a conceptual 2D grid as (x, y) pairs or as (row, column) pairs (essentially y, x pairs, since rows stack vertically).

You can implement either indexing interface regardless of the underlying storage layout. Consequently, it generally makes more sense to make the indexing APIs consistent.

It will be somewhat less error-prone and easier to maintain. An alternative is to make it very clear when you are doing (row, column) access by naming the function getValueAtRowColumn or something obvious like that.

Answer 2

I usually store the map in a 1D array and then have accessor-functions that take the intuitive (x, y) format:

// 0 = ground
// 1 = wall
// 3 = door
tiles = [ 0,0,0,0,0,0,0,
          0,0,0,1,1,1,1,
          0,0,0,1,0,0,0,
          0,0,0,1,0,0,0,
          0,0,0,2,0,0,0,
          0,0,0,1,1,1,1 ]

map_width = 7
map_height = 6


function validate_coordinates(x, y):
    if 0 < x < map_width or 0 < y < map_height:
        throw Error


function get_tile(x, y):
    validate_coordinates(x, y)
    return tiles[y * map_width + x]


function set_tile(x, y, t):
    validate_coordinates(x, y)
    tiles[y * map_width + x] = t

If you're using C++ you can even define the accessor functions with the preprocessor to avoid the overhead.

Answer 3

Not directly an answer but too large for a comment...

You actually want to break down a tile grid into smaller chunks.

Reasoning: say you are looking at a row-major matrix. If you are drawing just the visible section of the screen, how far away in memory is the first visible tile of the second row compared to the last visible tile of the first row? If you just have a huge row-major tile matrix, the answer is "the length of the row." That is rarely as efficient as it could be.

Break your world into smaller NxN chunks, where N is a relatively small number. At that point, row-major is certainly convention for tiles, but it really doesn't matter. Every tile on screen is relatively close to the tiles near it in memory.

Draw whole chunks at a time (rather than whole rows or columns at a time) to leverage this fact.

The end result is that your indexing API kind of becomes irrelevant; just pick whatever you want and know that locality of reference will usually be pretty high.

This also has advantages in data streaming from files or the network. You can more easily load just the nearby chunks and now worry about tile data far away. Maybe not super relevant for an RTS but handy in the general sense.

Answer 4

Here is an abstract base class for storing a grid of tiles ( from my HexgridUtilities library, hence the naming scheme:

  public abstract class BoardStorage<THex> : IDisposable {
    /// <summary>Initializes a new instance with the specified hex extent.</summary>
    /// <param name="sizeHexes"></param>
    protected BoardStorage(Size sizeHexes) {
      MapSizeHexes   = sizeHexes;
    }

    /// <summary>Extent in hexes of the board, as a <see cref=" System.Drawing.Size"/> struct.</summary>
    public          Size MapSizeHexes           { get; private set; }

    /// <summary>Returns the <c>THex</c> instance at the specified coordinates.</summary>
    [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", 
      "CA1043:UseIntegralOrStringArgumentForIndexers")]
    public abstract THex this[HexCoords coords] { get; internal set; }

    /// <summary>Returns whether the hex with <see cref="HexCoords"/> <c>coords</c> is 
    /// within the extent of the board.</summary>
    public          bool IsOnboard(HexCoords coords) { 
      return 0<=coords.User.X && coords.User.X < MapSizeHexes.Width
          && 0<=coords.User.Y && coords.User.Y < MapSizeHexes.Height;
    }

    /// <summary>Performs the specified <c>action</c> serially on all hexes.</summary>
    public abstract void ForEach(Action<THex> action);

    /// <summary>Performs the specified <c>action</c> in parallel on all hexes.</summary>
    public abstract void ParallelForEach(Action<THex> action);

    #region IDisposable implementation with Finalizeer
    bool _isDisposed = false;
    /// <inheritdoc/>
    public void Dispose() { Dispose(true); GC.SuppressFinalize(this); }
    /// <summary>Anchors the Dispose chain for sub-classes.</summary>
    protected virtual void Dispose(bool disposing) {
      if (!_isDisposed) {
        if (disposing) {
        }
        _isDisposed = true;
      }
    }
    /// <summary>Finalize this instance.</summary>
    ~BoardStorage() { Dispose(false); }
    #endregion
  }

It is desired that the client application not care whether a row-major or column-major ordering has been used, as his is an implementation detail. In fact, as Sean notes, it is often desired to use a blocked storage. Here is a blocked implementation of the abstract class above:

/// <summary>A <c>BoardStorage</c> implementation optimized for large maps by blocking 
/// 32 x 32 arrays of hexes for improved caching.</summary>
/// <remarks>This <c>BoardStorage</c> implementation stores the board cells in blocks
/// that are 32 x 32 cells to provide better localization for the Path-Finding and
/// Field-of-View algorithms.</remarks>
[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", 
  "CA1034:NestedTypesShouldNotBeVisible"), System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1709:IdentifiersShouldBeCasedCorrectly", MessageId = "x")]
public sealed class BlockedBoardStorage32x32 : BoardStorage<THex> {
  const int _grouping = 32;
  const int _buffer   = _grouping - 1;

  /// <summary>TODO</summary>
  public BlockedBoardStorage32x32(Size sizeHexes, Func<HexCoords,THex> initializer) 
    : base (sizeHexes) {
    backingStore  = new List<List<List<THex>>>((MapSizeHexes.Height+_buffer) / _grouping);
    for(var y = 0;  y < backingStore.Capacity;  y++) {
      backingStore.Add(new List<List<THex>>((MapSizeHexes.Width+_buffer) / _grouping));
      for(var x = 0; x < backingStore[y].Capacity; x++) {
        backingStore[y].Add(new List<THex>(_grouping*_grouping));
      }
    }

    Parallel.For(0, backingStore.Capacity, y => {
      var boardRow    = backingStore[y];
      for(var x = 0;  x < boardRow.Capacity;  x++) {
        var boardCell = backingStore[y][x];
        for (var i=0; i<_grouping; i++) {
          for (var j=0; j<_grouping; j++) {
            var coords = HexCoords.NewUserCoords(x*_grouping+j,y*_grouping+i);
            boardCell.Add(IsOnboard(coords) ? initializer(coords) : default(THex));
          }
        }
      }
    } );
  }

  /// <summary>TODO</summary>
  public override THex this[HexCoords coords] { 
    get { 
      var v = coords.User;
      return IsOnboard(coords) 
        ? backingStore [v.Y/_grouping]
                       [v.X/_grouping]
                       [(v.Y % _grouping) * _grouping + v.X % _grouping]
        : default(THex);
    }
    internal set {
      var v = coords.User;
      backingStore [v.Y/_grouping]
                   [v.X/_grouping]
                   [(v.Y % _grouping) * _grouping + v.X % _grouping] = value;
    }
  }

  /// <inheritdoc/>
  public override void ForEach(Action<THex> action) {
    if (action==null) throw new ArgumentNullException("action");
    foreach(var hex in backingStore.SelectMany(lh=>lh).SelectMany(lh=>lh)) action(hex);
  }

  /// <summary>TODO</summary>
  public override void ParallelForEach(Action<THex> action) {
    Parallel.ForEach<THex>(
      backingStore.SelectMany(lh=>lh).SelectMany(lh=>lh).Where(h=>h!=null), 
      hex => action(hex)
    );
  }

  List<List<List<THex>>> backingStore { get; set; }
}

More details, as well as a flat row-major implementation, are available here: Hexgrid Utilities for Board Game Implementations.