Help with C# program design implementation: multiple array of lists or a better way?

Question

I'm creating a 2D tile-based RPG in XNA and am in the initial design phase. I was thinking of how I want my tile engine to work and came up with a rough sketch. Basically I want a grid of tiles, but at each tile location I want to be able to add more than one tile and have an offset. I'd like this so that I could do something like add individual trees on the world map to give more flair. Or set bottles on a bar in some town without having to draw a bunch of different bar tiles with varying bottles.

But maybe my reach is greater than my grasp. I went to implement the idea and had something like this in my Map object:

List<Tile>[,] Grid;

But then I thought about it. Let's say I had a world map of 200x200, which would actually be pretty small as far as RPGs go. That would amount to 40,000 Lists. To my mind I think there has to be a better way. Now this IS pre-mature optimization. I don't know if the way I happen to design my maps and game will be able to handle this, but it seems needlessly inefficient and something that could creep up if my game gets more complex.

One idea I have is to make the offset and the multiple tiles optional so that I'm only paying for them when needed. But I'm not sure how I'd do this. A multiple array of objects?

object[,] Grid;

So here's my criteria:

• A 2D grid of tile locations
• Each tile location has a minimum of 1 tile, but can optionally have more
• Each extra tile can optionally have an x and y offset for pinpoint placement

Can anyone help with some ideas for implementing such a design (don't need it done for me, just ideas) while keeping memory usage to a minimum?

If you need more background here's roughly what my Map and Tile objects amount to:

public struct Map
{
    public Texture2D Texture;
    public List<Rectangle> Sources; //Source Rectangles for where in Texture to get the sprite
    public List<Tile>[,] Grid;
}
public struct Tile
{
    public int Index; //Where in Sources to find the source Rectangle
    public int X, Y; //Optional offsets
}

Answer 1

It seems like your approach is confusing presentation with behavior. If the behavior of the game is tile based then design for that functionally and then code up a presentation as the result of the state of the board.

Answer 2

What you could do is simply have an array of Tile:

class Grid
{
    Tile[,] grid;
}

... and have that Tile class have a List<Sprite> in it:

class Tile
{
    List<Sprite> sprites;
}

... and that Sprite class would have your texture and offset:

class Sprite
{
    Vector2 offset;
    Texture2D texture;
}

Finalize all that by having draw methods:

class Grid
{
    Tile[,] grid;

    void Draw(GraphicsDevice graphics)
    {
        // call your tiles Draw()
    }


}

class Tile
{
    List<Sprite> sprites;
    void Draw(GraphicsDevice graphics, int x, int y)
    {
        // call your sprites Draw()
    }
}

class Sprite
{
    Vector2 offset;
    Texture2D texture; // or texture and rectangle, or whatever

    void Draw(GraphicsDevice graphics, int x, int y)
    {
        // draw the sprite to graphics using x, y, offset and texture
    }
}

Of course it gets much more complicated than that but you should get the idea.

Separating all your concerns in different classes let you easily add new fonctionnality that won't conflict with existing code. Trying to mash all your data in a single object such as your List<Tile>[,] is bad form and will eventually bite you when you try to expand.

Answer 3

You essentially want a sparse matrix to represent "decorations" on each tile. A sparse matrix is a matrix structure where not all elements need have a value. There are C# libraries out there that represent them.

A simple approach would be to use an ordinary dictionary where the key is a Tile # (unique number of each tile) that could for example be calculated using the same type of formula used to address video memory: Y * MAXIMUM_X + X. For a given tile, just check if there's an entry for it's unique Tile #. The dictionary should probably contain a list of decorations for that particular tile:

Dictionary<int, List<Sprites>> spritesPerTile;
// ...
if (spritesPerTile.ContainsKey(tileNumber))
{
    List<Sprites> decorationsThisTile = spritesPerTile[tileNumber];
    // Proceed to render sprites on this tile.
}