Strategy game tile and unit storage

Question

I've recently started working on a turn based strategy game much like games from the Fire Emblem or Final Fantasy Tactics series. However, I'm running into a few problems concerning the storage of the tile data and unit data. For example, just like in Fire Emblem I want to show all possible movement when you click on one of the units. Here is an image showing what I mean.

In this image the possible fields to move to have been indicated with a blue color. Fields that are in range for an attack have been indicated with the red color. Normally the tile the enemy unit is on would be in range to move to, however since there is someone standing on the tile the game has recognized that you can't move there.

I understand the need for an algorithm like Breadth-First Traversal to find out all possible fields to move to, but I'm unsure how to exclude fields occupied by an enemy. In order to avoid circular dependencies between fields and units I only store a reference to field in the unit class and not the other way around. So when I work my way through the fields to check all possible moves, how do I best find out if that field is actually valid?

I could of course just loop through the list of all enemies for each field that I process to see if it's occupied. Another way to potentially solve it would be to loop through the list of possible fields and removing fields occupied by enemies from that list, but I think that wouldn't work properly because occupied fields can also have the effect that empty fields around them are no longer reachable (due to the enemy blocking access to them). The easiest way to solve it would be to also store a reference to the unit within the field class. This would of course introduce a circular dependency.

I feel like there should be a much better solution than the ones I can think of, but I just can't figure it out.

Thanks in advance!

Answer 1

It sounds like you already have a walk-map which says which tiles are walkable and which are non-walkable based on the terrain: the static walkmap.

What you need is a second walkmap which tells you which tiles are non-walkable because of object presence: the dynamic walkmap. This map only needs to be recalculated when there is a change, so you can keep it in memory and only need to update it when an object changes its position, is removed or added.

When you calculate paths, check both the static and the dynamic walkmap to determine if a field is walkable.

In a real-time game with lots of actors it would be faster to have the dynamic walkmap keep count of all effects which affect a tile, so when an object moves you remove its old effect and add the new one. This is a cheap constant-time operation for every position change. (it might also make the static walkmap redundant, because any blocking tiles can be represented by an effect on the dynamic map which is added once but never removed).

But because your game is turn-based, performance is not of such a great concern. A small hickup after a unit makes a move would likely not be noticed by the player. And even when it is noticeable, it might in fact add to the suspense. So I would go for a much simpler solution which has linear time complexity but is easier to implement and less error-prone: When an object makes a move, just throw the old dynamic walkmap away and recalculate it from scratch by iterating all objects and mark the fields they occupy as blocked.

When you have a game with two (or more) factions, then you might have a rule that units block tiles only for the enemy faction(s). You might also have units which are bound to different move rules (for example, a flying unit can move through fields occupied by enemy units, unless they are also flying). That means you should not just store if but how a tile is blocked - whether it's blocked for faction A, faction B or both. You could do this by either calculating a separate walkmap for each faction and each movement mode, or by having the walkmap store a bitset for each tile where each bit says for which faction it is blocked.

Answer 2

First go though your list of obstacles an compile a list of fields that are currently unavailable for movement. This list could contain field IDs or grid references or some other way to identify a field that works for your data structures.

Next perform your Breadth-First Traversal and for each field perform a check to see if it is on the list of fields that contain obstacles.

Creating this list will be a low complexity task so it shouldn't matter if it is recreated between each turn.

Answer 3

If you want to store a reference from the tile to the unit(s) occupying it, then just do it. As long as you remember to remove the reference whenever a unit leaves a tile (as you should do anyway, to mark the tile as unoccupied), the circular references will not affect the garbage collection of destroyed units in any way.

The one situations where circular references might be a problem is when you discard the whole level, with its tiles and units and all. In that case, if you don't first unlink the references by hand, the garbage collector may have to work a bit harder to determine which tiles and units are no longer reachable. However, most modern languages (including e.g. Java, JavaScript and C#) feature tracing garbage collectors that can do this, even in the presence of circular references.

---

If you wish to make the garbage collector's job easier, one alternative to manually breaking the references would be to use weak references, which most modern languages also support. These don't contribute to the (strong) reference count of the referenced object, and thus allow it to be garbage collected as soon as there are no more strong references to it. (However, there's no guarantee that an only weakly referenced object will be garbage collected immediately, so you should not rely on it; in particular, you'll still need to manually mark tiles as vacant when a unit is moved or destroyed.)

---

Finally, if your units have unique IDs (and you have some way to efficiently look up a unit by ID), you can simply store the unit ID instead of a reference to the unit. In fact, such "symbolic references" are often a more natural choice for game world models than hard references anyway, since they decouple the existence of game objects from the existence of references to them. After all, in the real world, an object does not disappear simply because everyone forgets about it, nor does a destroyed object linger as some sort of a ghost just because somebody believes it's still there.

(Of course, if you do want to sometimes keep references to units or other game objects that may not actually exist in the world any more (or do not yet exist), then in such cases, hard references may indeed be appropriate.)

Or you could just do as Philipp suggests, and not store actual unit IDs on the map, but simply some flag indicating that this tile is occupied by a unit (of faction X). This may well be enough for your pathfinding purposes.