How to manage dependencies between tile map and units

Question

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?

Answer 1

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.

Answer 2

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.