0
\$\begingroup\$

I'm writing a sorting algorithm for a tower defense mobile game. As a quick synopsis, I have a "tower" that can shoot at incoming threats that are within X distance from the base of the tower.

Each incoming enemy, will have an associated {distance_from_tower} and {enemy_weight}. The {distance_from_tower} will be a value between 0 and X (X being the max range of the tower). The {enemy_weight} is a valued weight of "how important" it is to target that enemy mob. For example:

Three enemies:

Archer: {distance_from_tower} = 3 , {enemy_weight} = 1

Knight: {distance_from_tower} = 7 , {enemy_weight} = 5

Zombie: {distance_from_tower} = 10 , {enemy_weight} = 3

Currently, I have a simple sorting algorithm that only sorts enemies by their distance from the tower. (So, in the above example, the tower would target: Archer --> Knight --> Zombie)

Which is a "fine" first logical step, but I want my towers targeting to be more robust. I want the sorting to take into account both the {distance_from_tower} AND the {enemy_weight}. (For reference as well, these two values are updated at every Z seconds during the game, so they are constantly being recalculated).

I would like for the tower to be "smarter" and have a more robust sorting mechanism, that takes into account both weights, as said above. That could potentially lead to the tower targeting an enemy mob that is further away because the {enemy_weight} value of that respective enemy mob is of "high priority". (So, in the above example, the inclusion of using both weights could lead to the tower targeting in this order: Knight --> Archer --> Zombie).

I've been digging around for a few possible solutions, such as using a Travelling Salesman approach, Dijkstra's algorithm, or Floyd's algorithm, and I can't figure out the best way to go about sorting using both weights in a manner that makes sense to me. Any intuition or help is greatly appreciated! Thanks!

\$\endgroup\$
4
  • \$\begingroup\$ Welcome to GDSE. Generally speaking, you either combine the two factors mathematically (.3*dist+.7*weight etc) or you do something like how names get sorted where one variable takes precedence & ties are broken by the other. Also, the algorithms you listed are graph search / pathing algorithms & not well suited to ordering a list of priorities. \$\endgroup\$
    – Pikalek
    Apr 6, 2021 at 18:07
  • \$\begingroup\$ @Pikalek GDSE? Thanks for the response, appreciate it. \$\endgroup\$ Apr 6, 2021 at 18:40
  • \$\begingroup\$ The Game Development Stack Exchange :) \$\endgroup\$
    – Pikalek
    Apr 6, 2021 at 18:53
  • \$\begingroup\$ @Pikalek - ah, thank you! Happy to be here, looking forward to your reply. \$\endgroup\$ Apr 6, 2021 at 19:15

2 Answers 2

2
\$\begingroup\$

I'd argue that allowing the towers to disperse the firepower over multiple priorities is the opposite of "robust", because the towers would tend to avoid finishing the targets. To get a better mental model of priority, think about the cost of missed opportunity: how much damage would the player take, if given enemy would be allowed to pass.

For that calculation, the distance to the tower will be completely useless, unless there is the damage fall-off over the distance. The distance metric could actually make things much worse: imagine an almost killed enemy getting out of the range because the tower got distracted by someone closer.

Much more interesting metrics would be the distance, that the enemy has to travel — that's what the pathfinding algorithms would be needed for. Use remaining travel distance together with the tower's fire rate and the enemy's traveling speed to calculate the fraction of enemy's health that could be removed. Multiply that by the penalty to get the final missed opportunity cost.

Most TDs I've played so far are using much simpler heuristics, such as:

  • choose one enemy and stick to it
  • the enemy closest to the finish
  • the enemy with least health

And yet these rules would work much smarter that just biting a chunk out of everyone while not actually trying to kill anyone.


If you absolutely want to stick to these 2 metrics, I advise to introduce some form of configurable target priority: either via the tower variety, or as an per-tower setting.

  • The "killer mode" should prioritize most dangerous enemies, to minimize the risk in the long term.
  • The "finisher mode" is for a single tower closer to the finish, to finish low-health enemies that slipped by. It should prioritize by distance. Although I want to repeat that distance metric is virtually useless.
\$\endgroup\$
0
\$\begingroup\$

There are two common approaches to the problem of prioritizing or sorting with multiple values of interest. I'm going to use your example of sorting based on distance & weight, but the idea holds true for multidimensional data in general & can be applied to a variety of algorithms.

Ranked Data Comparison

This approach gives precedence (ranks) the various criteria and then applies them in some order. For instance, first you compare items based on weight. In the event that their weight are identical, you then compare them by distance.

In some respects this is similar to some of the ways we sorting names: comparing last name and in the event of a tie, comparing first name. While simple, this approach will only give good results if there is a meaningful precedence between your categories of data.

Aggregated Data Comparison

Math Version
This approach combines the different criteria mathematically. For instance, we might use the formula dist * weight to combine the criteria into a single value. These values could then be used to sort the list.

This reveals a new problem: in your original problem statement small distances have priority over large ones whereas heavy weights have priority over low ones. Let's reverse the weights such that we have the following:

 Knight.weight = 1;
 Zombie.weight = 3;
 Archer.weight = 1;

Now when we apply the dist * weight formula, we get:

  • the closest & most important enemies will get the lowest values
  • the furthest & least important enemies will get the highest values
  • enemies of equal distance will be prioritized by weight

And when sorted from least to greatest, your highest priorities will be at the front of your list. This makes more sense, though you will likely need to tune the weights to get good results with mixed situations.

Math + Logic Version
In some cases you'll want something more sophisticated to account for other aspects of your base problem. For example, let's say it takes two hits to neutralize an incoming enemy. If an enemy is so close that it can reach the tower before two shots can be fired at it, there might be no value in attacking it even though it is closest! By assigning it a special category that get sorted separately and appended after 'normal' enemies you can prevent your tower from wasting shots on it unless nothing else is present.

We could also have handled the last situation by assigning a very large penalty weight. But it's easy to turn the math into a mess with too many special penalties &/or bonuses. Sometimes it's simpler to add clean layer of game logic instead of hunting for a universal algebraic formula. This approach of using math and logic is what I have used the most often with problems of this sort.

Bonus

By using different weight presets &/or formulas, you can also support different behaviors. For example, instead of assigning the weights directly to the enemies, we can give each enemy an index and give each tower type a table of enemy weights. Thus you could make a special tower that prioritized zombies simply by giving them a higher weight in that tower's lookup table.

Conclusion

Ultimately, sorting/prioritizing a list means that for any two items we can definitively determine which one comes first. Even if there are multiple values of interest for each item, it comes down to using some means to say "this comes before that". Working through small example by hand and saying that out loud can help get the process started.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .