How should I track which monster is first in a Tower Defense game, and is it ok create an extra attribute just for this purpose?

Question

So I'm creating a Tower Defense game and I want to have different ways for towers to prioritize their targets (I'm using Python but looking for a generic design answer):

class TargetPriority(enum.Enum):
    LOW_HEALTH = 1
    HIGH_HEALTH = 2
    FIRST = 3
    LAST = 4
    CLOSEST = 5


class Tower(Entity):
    def __init__(self, *args, **kwargs, target_priority=TargetPriority.FIRST):
        super().__init__(*args, **kwargs)
        self.target_priority = target_priority

    def find_target(self, all_monsters):
        sort_functions = {
            TargetPriority.LOW_HEALTH: lambda monster: monster.health,
            TargetPriority.HIGH_HEALTH: lambda monster: -monster.health,
            TargetPriority.FIRST: ???,
            TargetPriority.LAST: ???,
            TargetPriority.CLOSEST: self.distance_to,
        }
        func = sort_functions[self.target_priority]
        return next(sorted(all_monsters, key=func), None)

As you can see, I'm not sure how to get the "first" or "last" monster from the wave of monsters. The way my monsters work right now is by getting a Checkpoint object and once they reach the checkpoint, they call it's check_in() method to get new instructions:

class Monster(Entity):
    def __init__(self, *args, **kwargs, health, checkpoint):
        super().__init__(*args, **kwargs)
        self.health = health
        self.checkpoint = checkpoint

    def update(self, dt):
        travel = self.velocity / 1000 * dt
        remaining_distance = self.distance_to(self.checkpoint)
        if travel.length < remaining_distance:
            self.position += travel
        else:
            self.checkpoint.check_in(self)

The Checkpoint.check_in(monster) method can invoke any callback given to the checkpoint, usually it just changes the monster's checkpoint to the next checkpoint, but it can also do something else like take a life away from the player and remove the monster (the last checkpoint always does this). I can change the way these checkpoints work (or how the monsters move in general) if required by an "optimal" solution though.

Here are few things I've considered:

• I can't use the order of the monsters in the all_monsters list because some towers may slow some monsters down, thus changing their order
• For the same reason I can't use any other kind of indexing
• I can't use the monsters' position on the map because there's no way of knowing which way the monster is going or where the checkpoints are
• I can't use the monsters' distance to checkpoints because the monsters can be at different checkpoints already

So far the only actual solution I could come up with was to store a total_distance_travelled for each monster, so in update() I would have:

self.position += travel
self.total_distance_travelled += travel.length

But there are two reasons why I hesitate:

• It's not 100% fail proof: although not currently possible, what if I will have something like towers that teleport monsters back to their previous checkpoint?
• I'm adding an instance attribute just for the sole reason of towers being able to sort these monsters

Am I worrying too much, or is there a better solution that I'm just missing?

Answer 1

What you have is the most practical solution as I see it:

self.total_distance_travelled += travel.length

For first and last targeting you have to have some concept of progress and it shouldn't be so intricate to code. If you have teleporters which can push monsters back, then they're being pushed back and their progress should be decremented, and you should be able to compute the path and the length of that path for the teleport and simply decrement total_distance_travelled by that length.

It's not 100% fail proof: although not currently possible, what if I will have something like towers that teleport monsters back to their previous checkpoint?

Of course if you teleport monsters backwards by a random distance, e.g., then you might have to do pathfinding to figure out where to teleport them or use this checkpoint system you have. However, you can think of that like, "How many steps/feet/meters/pixels backwards did I move the monster?" And just decrement total_distance_travelled by that amount.

I'm adding an instance attribute just for the sole reason of towers being able to sort these monsters

Not to worry, as that should be perfectly normal in TDs that have first/last targeting priorities. If you're worried about efficiency here, the bigger priority is usually accelerating the search for monsters within proximity to the tower (since that can suffer scalability problems if you throw a boatload of monsters on the map at once), for which partitioning monsters into plain old grid cells can be useful: https://gamedev.stackexchange.com/questions/150754/performance-problems-with-quadtree-for-dynamic-objects/152014#152014

An Alternative: Time to Reach Final Goal

The one alternative I can think of is to implement a very scalable distance_to_goal() kind of function you can call on monsters on the fly, potentially every frame, which computes the total distance to reach the final goal (not the next checkpoint). The ones with the minimum value would be first priorities, the ones with the maximum value would be last. That would be very robust but shifts a lot of challenge towards optimization and coming up with a very rapid way to compute that distance to the goal and see if you can use cheaper computations depending on the situation. Most TDs, I think, just use what you're doing.

If you try this, you might combine it with what you're doing now except turn total_distance_travelled to something like total_distance_remaining which gets decremented as the monster progresses towards the final end goal where they subtract a life from the player and ultimately lead to game over. Then you might recompute that if the path changes for some reason or if the monster gets teleported.

Actually never put that much thought into targeting priorities before (just ended up going with the pragmatic kind of solution you're already using), but the above technique using "distance remaining to final goal" would definitely be the most robust if you can compute and update that efficiently enough.

It just also occurred to me if you do it that way that you might be able to better model player intentions if you also factored in the monster's speed and divide that distance remaining by the monster's speed to get, "time to reach final goal", because the player will probably want first priority targeting to target faster monsters if they're going to reach the end sooner, even if they start off a little bit behind.

Fun idea with that: you could look for the monster with the lowest time to reach the final goal and if it's just seconds away, you might accelerate a beating heart or start turning the screen red or fade in scary music or something like that, getting more intense as the minimum "time to reach final goal" works towards zero. For testing you might use a development feature to draw the time remaining over each monster to make sure that's being computed correctly at all times.

Answer 2

If you have branching paths, you really don't have a single, objective, "First" monster in the wave (same "Last"). There are a couple of things that probably play well:

Ignore actual position, and just count spawn order.

• Pro: very simple implementation, you just keep the all_monsters order
• Con: Pushback towers don't affect the priority like you would want.

Do a topological sort of the checkpoints, sort by checkpoint then distance to checkpoint.

• Pro: gives a sensible total order over each linear subgraph
• Con: basically arbitrarily favours one path over another, not obvious to the player why

A variation of the topological sort would be to compute a "minimum distance path to exit" for each checkpoint (once, when you setup the level), and add that to the distance to the checkpoint. Then the player has a better intuition of "these ones might take that shortcut, so they have to die first", even if only a fraction actually would

You could also do both

def find_target(self, all_monsters):
    counter = 0
    def first(monster):
        counter += 1
        return -counter
    def last(monster):
        counter += 1
        return counter
    def compare_topological(left, right):
        if (comparable(left.checkpoint, right.checkpoint)):
            return (checkpoint_order(left.checkpoint), left.distance_to(left.checkpoint)) < 
                   (checkpoint_order(right.checkpoint), right.distance_to(right.checkpoint))
        else:
            return 0 # incomparable

    sort_functions = {
        TargetPriority.LOW_HEALTH: lambda monster: monster.health,
        TargetPriority.HIGH_HEALTH: lambda monster: -monster.health,
        TargetPriority.FIRST_SPAWNED: first,
        TargetPriority.LAST_SPAWNED: last,
        TargetPriority.FIRST_TOPOLOGICAL: functools.cmp_to_key(compare_topological),
        TargetPriority.CLOSEST: self.distance_to,
    }
    func = sort_functions[self.target_priority]
    return next(sorted(all_monsters, key=func), None)