# How to manage dependencies between tile map and units

I have a 2D tile-based strategy in the works. I'm wandering how to handle the relationship between the map and the units on the map.

Given a tile coordinate I'll need to be able to get the unit standing on it, if any. At the same time, if given a unit I'll want to be able to get the unit's coordinate.

I've seen two solutions to this. The first solution would be to have units store a coordinate and the map store unit references in its tiles. This creates a cyclic dependency between the map and units. I'd need to make sure that the map an any unit are kept in sync if the unit moves.

The second solution would be to only have the units keep track of their coordinates. To tell if a tile contains a unit and to get that unit, I'd loop through the whole set of units unit I find one with matching coordinates. That get rids of the cyclic dependency, but it looses the O(1) property the first solution had for looking up units from the map. This may add up as I want to be able to scan the map regularly for things such as path finding, determining movement range, and finding valid targets for a given unit.

I also can't just store the units in the map (or can I?). Units are associated with "armies", either player or AI. An army should be able to easily access and iterate over all of its units.

Since this appears to be a common issue in strategy games, are there any other patterns besides the two I described for managing unit/map relationships?

It's not a popular pattern but the relational database world offers a third way: use a data structure that has multiple keys. In tabular form, it might look like this:

Unit id    Location
-------------------
1309     13,15
2357      7,93
8552      7,93


You want to be able to ask, “where is unit 2357?” and get back 7,93. You also want to be able to ask, “what's in location 7,93?” and get back 2357 and 8552. There are data structures that allow multiple keys for looking things up. You can store this outside the units and outside the map if you want to remove dependencies.

However, in practice it's more common to store location in each unit, and then on the side use a spatial partitioning data structure that tells you what units are in a given region. Since it's a separate structure, the regions don't have to be grid spaces; they can be larger areas.

I recommend doing whatever's easiest (your second solution) and then later if it's a performance problem you can add a spatial partition to make lookups faster.

• So, the spatial partitioning data structure you mention could just be the map (which in my case is ostensibly a 2D grid of tiles). I assume when a unit moves (or is added, or is removed) I still need to update both the unit and the spatial partitioning structure to keep them in sync. Perhaps it's one of those things I'll have to live with? – AJM Jan 22 '11 at 16:33
• Yes, the map is the most fine grained spatial partition you would use. The global list of all units is the most coarse grained partition. ;) You only need to update the partition before it's used. If you're using it all the time you probably want to update it every time the unit is moved. However if you're only using it for some phases of the update logic, you can go through the unit list in one pass and compute the partition data structure, then discard it when you're done. That way you don't have to keep them in sync all the time. – amitp Jan 22 '11 at 16:56

Well, you unless you several thousand units per player, I wouldn't worry about memory usage, and use the first solution. Memory is cheaper than CPU it seems.

In fact even if you had 4000 units per player, using two integers to store there location, and 8 players, that only takes 2MB, but with the first solution, you get to use a O(1) co-ord getter, rather than O(n) (assuming unsorted), which with a lot of units could be slow.

Most games seem to be pixel based, rather than tile, now a days so they only need to get the unit to store the co-ords.

• I'm not worried about memory usage, I'm more interested in managing dependencies (in the Object Oriented Design sense). It's not the extra memory the first solution would entail that worries me, it's the cyclic dependency I'm leery of, as much as I like the O(1) co-ord getter. Also, I know a lot of games are pixel based now, but I like tiles so that's what I'm using. :P – AJM Jan 22 '11 at 16:28
• @AJM, same, the paid apps I will be releasing on android will be using tiles. – Ray Britton Jan 22 '11 at 17:21