0

Recently I am working on a tower-defense game in python (3.7). One crutial point in the code is haveing the all towers target appropriate enemies.

As of now im using the straightforward approach: Each time a tower attacks check all enemies if they are in range. Actually I'm doing this several times per tower (because of area damage and more than 1 target per tower (see below))

I have asked a question about checking the distances effectively: confused about runtime of differents methods for distance of (2-d) points So it is not part of this question to discuss how to code fast distance-checks for 2-d points.

What I would like to discuss in this questions are (effective) ways to handle enemie-targeting in context of my TD-game. I will write more detailed questions below.

Before discussions approaches for targeting, let me state some (in my view) relevant facts of the game I am making:

  1. The center of the tower / enemy is the only relevant information for targeting-range checks
  2. The range of towers is not fixed. It can have 101 different values. The maximal size covers almost the entire screen. The range can be modified at any time during playing
  3. The gamescreen is 1600 times 800 pixel
  4. Towers can target up to 101 enemies at once. This amount can be modified at any time during playing
  5. The towers can have area damage. Each of the (possible 101) targets of a tower has an own check for enemies in range of the area damage
  6. The area damage size is not fixed. It can have 101 different values. The maximal size covers almost the entire screen. The area size can be modified at any time during playing
  7. After a certain point in the game I expect each tower has maximal range / area / number of targets, but in theory each tower can have their on specific values
  8. The player is not restricted in the number of towers he can build. But having more than 100 is hardly possible
  9. Enemies come in waves. The waves consists of 5-20 enemies. If you play in a particular way it is possible to get maybe 100-300 active enemies at the same time. Having more is hardly possible
  10. The enemies move each frame
  11. Different enemies can have the exact same pixel position
  12. The gamescreen is already divided into 32 times 32 pixel blocks (total 50*25 = 1250 blocks). Some features in the game use this grid already and I keep track in which of those blocks enemies / towers are
  13. Different Towers do not attack at the same time
  14. Towers attack every 30 frames (I have avoided attack speed changes, because of performance fears)

I am asking this question, because my current approach for targeting seems wasteful. With

  • tower_count = number of attacking towers
  • target_count = number of targets per attacking tower (this number may vary for different towers, but let us ignore this fact)
  • enemy_count = number of active enemies

We have to check tower_count * target_count * enemy_count many enemies per attack cycle (30 frames). In the above description worst case scenario 100 * 101 * 300 ~ 3 * 10^6 positions. After finding the appropriate enemies I have also to make actions with these enemies (e.g. have the enemies take damage etc.). This can also be a problem for 3*10^6 enemies and I might ask a question about it later, but this is not the primary focus of this question.

As of now I know of the following alternativ approache for targeting:

  1. spatial partition

Unfortunatly I am not sure how to use spatial patition with a flexible tower range. Here is how I would try to implement it at the moment:

  1. For every possible range / area size (101 values each) and each of the 32^2 possible positions pixel positions in a basetile precompute all basetiles which are relevant. As example: For an area damage check we would have:
    • input:
      • The (originally targeted) enemy as
        • enemy is on basetile (i,j)
        • and position (x,y) in this basetile
        • the area size is 40 pixel
    • (precomputed) output: you need only to worry about enemies at basetiles (i,j),(i+1,j), (i-1,j), ..., (i-1, j-1)
  2. Divide those relevant base tiles in 2 sets:
    • The basetiles in one set are completely in range and all enemies within them are
    • The basetiles in the other set only intersect with the range and each enemy on them has to checked separatly
  3. Each of the basetiles has a lists of enemies on them. Unite the list of enemies for the 2 different base tile sets and handle them. In the worst case I have to unite over 1250 (mainly empty) lists here.

This approach does not seem more effective to me. One could also try to forget basetiles and an similar implementation for each pixel, but this seems even worse.

My Questions at the moment are:

  1. Is the appraoch to spatial partition, which I described here, reasonable or am I missing important ideas for the implementation?
  2. Is spatial partition a real solution here or is it not possible with flexible ranges?
  3. Are the other options for targeting, which could be applied here?
31415926535
  • 3
  • 1

0 Answers0