3

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?

  • Sounds like an interesting problem to work on. If the monsters are travelling between checkpoint, can we infer that they are able to choose their own path to the next checkpoint? Or do your monsters follow a more narrow (like a line) path and the checkpoint is effectively a point on that line? If the latter, could you add additional checkpoints at the intersections of the tower's range with the path? That way you could narrow down your search to just monsters between certain checkpoints and then try to decide which one is "first" or "last" with a more expensive algorithm. – Maybe_Factor Dec 12 '17 at 7:00
  • Another idea (building on your idea of keeping track of position and total_distance_travelled): I think that could work as long as any teleporting checkpoint also subtracts (or adds) an appropriate amount of distance. – Maybe_Factor Dec 12 '17 at 7:02
  • @Maybe_Factor The latter, where monster will take the shortest line possible to each checkpoint, like this. I believe your first suggestion could work but it seems like a little too much trouble. At that point it would be hard to decide the order of checkpoints already lol. Your teleport subtraction idea makes sense, I suppose I'll stick to it, let the "weird" towers handle that. – Markus Meskanen Dec 12 '17 at 9:34
  • 1
    Do the checkpoints form a single path, or are there branches and joins? Can you know in advance what the next checkpoint will be when a monster reaches its current destination? It sounds like you may only have a Partial Order – Caleth Dec 12 '17 at 9:45
  • Ah sorry, the image was misleading, the path can indeed branch and join. – Markus Meskanen Dec 12 '17 at 11:30
5

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.

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)
  • "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" – Markus Meskanen Dec 12 '17 at 9:35
  • I still think spawn order is a reasonable idea, but I have sketched an alternative. Your main problem is that there is sometimes no order between two monsters – Caleth Dec 12 '17 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.