numeric identifiers associative array

Question

edit: clarified my question. I also realized that I didn't pick a very conclusive question title, which unfortunately I cannot change anymore, sorry.

Hey everyone,

to improve my programming skills a little and getting familiar with good design patterns, I'm trying to program a litte turn based strategy game, and I am at the point to choose a good data structure for the configuration of different terraintypes and unittypes etc. which do exist.

What I have implemented so far is a big "Game Object" with knowledge about everything in the game, and many of its properties are big associative arrays (I'm using PHP, but my question doesn't really have to do much with the language), for example an arrays of units, a map array.... What my array structure is comparable to is the type object pattern mentioned here.

Example: A single unit is of a certain type, say 'Infantry', and shares many data with all the other infantry untis on the field. Instead of copying all these values, I give every unit a "type" so it can look up the details there. Similar with terraintypes. Example:

terraintypes = array()
terraintypes[0] = array()
terraintypes[0]['name'] = 'Forest'
terraintypes[0]['capturable'] = false

unittypes = array()
unittypes[0] = array()
unittypes[0]['name'] = 'Infantry'
unittypes[0]['movecost'] = array()
unittypes[0]['movecost'][0] = 5 //Movementpoints needed for forest
unittypes[0]['movecost'][1] = 7 //Movementpoints needed for terraintype 1

A specific unit or tile on the map wouldn't know its movement costs or name, but would be able to look that up in the unittypes array. Example:

sometile = array();
sometile['owner'] = whatever
sometile['type'] = 0; //this tile is a forest

someunit = array()
someunit['type'] = 0 //This is an "Infantry".

The problem is that getting any kind of information will produce very verbose code, for example finding out how much it costs for a unit to move onto a tile will be

unittypes[unit['type']]['movecost'][tile['type']]

I am trying right now to move to using more objects and classes, so if I give a unit a reference to its unittype, it can lookup information itself, for example

terraintypes[0] = new Terraintype('Forest')
unittypes[0] = new Unittype('Infantry')
someunit = new Unit(unittypes[0])

Now, if I ask a unit something only its unittype would now, the unit can look it up itself, e.g. someunit.getName() will be implemented in the unit like this.unittype.getName().

So far so good. However, how could a unittype store its movecost on the different terrains? Basically I would need an array indexed with terraintypes, but as that is not possible, I will have to swhich back to translate everything to numeric keys, and have a movecost value for every pair (terraintype, unittype).

Who assigns these numeric keys and where? Will every single unittype need to store some kind of identifier which is unique among all the unittypes? Should I use some constants like const FOREST = 0; const ROAD = 1; const INFANTRY = 0; const VEHICLES = 1 etc?

Another of my problems for finding a good data structure is that if I don't give the game all the data directly, but break everything down to smaller parts, then many parts will need to know about the same objects.

For example, if the Map object knows about all tiles of the map and the units on it, then the game doesn't really know anything about the units, it only knows about the map, and every command in the game which affects a unit needs to be passed to the map, even though its not actually a "map task", like healing units.

This seems like breaking the single responsibility pattern. However, storing references to all the units in several places (so both the Map and something else store references to units) seems to be troublesome with bookkeeping.

To sum it up a little, can you hint me to data structure which are suitable to represent what I am describing? Thanks in advance!

Answer 1

First your organization of data is pretty good. Using arrays or objects does not really matter much although an object is cleaner, as it provides a clean interface and avoids simple problems like unset properties. I don't think that verbosity of yours a bad thing. unittypes[unit['type']]['movecost'][tile['type']] can easily be encapsulated, so you need it only once. And for that it's ok.

@Draco18s answer only changes where you store the data. In your case you store the instances in global arrays. Storing them in the class itself as static data might be cleaner. Storing them in an array might actually be the better option, as this allows iterating and hence searching them. So you could do TerrainType::GetTerrain("Forest") or the like. You could also store integer references by doing something like:

public class TerrainType {
    public static FOREST = AddTerrain("Forest",false,0.25f);
    public static PLAINS = AddTerrain("Plains",true,0.75f);
    public static ROAD = AddTerrain("Road",false,1.5f);

    public static terrains = array();
    private AddTerrain(params...){
        idx = len(terrains);
        terrains[idx] = TerrainType(params...);
        return idx;
    }
}

Or store the ID in the TerrainType itself.

As for the mapping from Units to Movement speeds I'd note that this is a mapping: f(Unit, Terrain): speed. You could store this in either the Terrain or the unit or in both. Easiest way would be: Store a unit "base" speed and a terrain "multiplier". Then when unit x is on terrain y you multiply them to get the actual speed (at that point you do have access to both the UnitType and the TerrainType or something is wrong ;-) )

Otherwise you would need to maintain a table and I'd make it a table: Speed[UnitType][TerrainType] however maintaining/creating this might be quite cumbersome due to the NxM relationship here which easily explodes as you add more units/terrains. Note that you have integer keys which you can use as indices into that table if you use the above code. Of course the mapping needs to be done with the constants assigned during TerrainType/UnitType initalization. If you have arrays, you could have a GetIdx method that scans the array and returns the index. As this would also need to be done when accessing a speed, you want to encapsulate this into GetSpeed(UnitType, TerrainType)

Last about passing messages from Game->World->Unit: Nothing bad about this either. Just make it layered. E.g. Game.MoveUnit(unitId, X, Y) -> World.MoveUnit(unitId, X, Y) -> Unit.Move(X, Y) Or more abstract messages. Each message has an ID and data. Like UnitMessage("Move", X, Y). The game passes all messages it does not understand to the world, which would then pass it to the unit.

Answer 2

I would create a custom data type (a "class") for your terrains. You'd end up with something like this:

public class TerrainType {
    public static FOREST = new TerrainType("Forest",false,0.25f);
    public static PLAINS = new TerrainType("Plains",true,0.75f);
    public static ROAD = new TerrainType("Road",false,1.5f);

    //I am not sure how PHP handles readonly fields
    public final string name;
    public final bool capturable;
    public final float move_cost;

    private TerrainType(string name, bool capture, float move_speed) {
        this.name = name;
        this.capturable = capture;
        this.move_cost = move_speed;
    }
}

This gives you a singleton-like structure that holds your terrain types and their associated properties without making your code stringly typed.

Then your map object can consist of a 2D array where each position holds a reference to its terrain type. e.g. mapArr[x][y] = TerrainType.FOREST; although your map might be another class as well, holding the terrain type, who owns the tile, and the units there.