4

I'm building a little tower-defense game with some friends in Java. Now I'm assigned with the logic for towers and at the moment I'm trying to figure out how a tower has to turn to aim and hit a target monster. Because a monster moves on while the tower is turning and shooting, it needs to aim for a future position. I've implemented a function, which gives me the position of a monster at any time t and also a function, which gives me the smaller angle needed to turn to a monster, but now I'm confused because there are three unknown variables:

  • t1 or angle: the time or angle, the tower needs to turn (the speed at which a tower can turn is given)
  • t2 or shoot distance: the time a bullet needs to travel to hit the target (speed also given, constant).
  • t3 or travel distance: the distance the monster travels in the same time.

So I'm searching for a solution for:

min(t1+t2) = min(t3)

where the target monster is still in range of the tower. I already thought of calculating with the maximal needed turn and maximal possible range and then stepwise decrementing, but I'm curious if there is a "perfect" non-heuristic solution?

Fabian Fritz
  • 390
  • 3
  • 14

2 Answers2

4

For every coordinate we can calculate the time tB that we need to have a bullet at that location. That's the turn time plus the time a bullet needs (t1 + t2).

The earliest time we can hit the monster is the first location on the monsters (predicted) path, where monster and bullet have their fatal meeting.

I'd start from the monsters location, calculate times and locations for the beast and calculate if a bullet will arrive earlier or later.

You could eliminate one of the variables if you just turn and check on every degree or tick if you can kill the monster if you fire now. You'll just have two vectors (aiming, monster move direction) with one intersection point and simply have to test, if monster and bullet meet there at the same time (distance to intersections point, speed).

Andreas Dolk
  • 113,398
  • 19
  • 180
  • 268
3

ADDED INFO:

I assume that a given monster has distance D to the tower, moves on the shortest path to the tower, and the tower starts turning towards the monster. This is the situation at t=0.

FIXED TYPOS:

If your tower turns with an angular speed omega, that is, the angle phi at time t is

phi = omega * t

So if you know that your tower has to turn an angle phi, the bullet will be shot at

t = phi/omega

From this on the distance which the bullet speed v has traveled is

s(t) = v * (t-phi/omega)

If your monster moves with a speed vm, the monster will be at distance d

d(t) = D - vm * t

The bullet hits the monster if

s(t) = d(t)

This equation is easy to solve: just substitute d(t) and s(t) and rearange the terms for getting t:

t = (D + v * phi/omega) / (phi/omega + vm)

And the bullet will have traveled s(t) at this moment. If this value is negative, the monster was too fast and reached the tower before the bullet was fired

rocksportrocker
  • 7,251
  • 2
  • 31
  • 48
  • Please check your first paragraphs - at first, `phi` is a speed, later it's an angle (`phi` should be angle, `omega` angular speed). Then: `t=0` is the *time* the tower starts turing, `phi(t0)` the starting angle. – Andreas Dolk Sep 19 '11 at 11:32
  • Further on - I *think* you assumed that all monsters head towards the tower. The question sounds like this is not the case in this game: monsters move all around the board and the tower(s) try to get them as soon as possible. – Andreas Dolk Sep 19 '11 at 11:44
  • 1
    Yes, I assumed that the monsters head towards the tower. But rewriting the equations for general monster movements is possible. Is anyone interested ? – rocksportrocker Sep 19 '11 at 11:52
  • I'm still not sure whether we have a single solution or a solution set.. if we have a set, then we'd still have to find the best solution (which would be min(t)) – Andreas Dolk Sep 19 '11 at 11:58
  • Yes. For a monster going in an arbitrary direction, stating an equation does not make much sense. Instead of setting "s=t" you have to minimize |s-t|. And if this minimal value is zero, the bullet hits the monster. – rocksportrocker Sep 19 '11 at 12:01
  • The path which the monster will travel is given, so it isn't quite arbirary, is it? But of course, it won't always head towards the tower. I don't care so much for the times needed; in the end I'm interested only in the point the tower can hit the monster at the earliest. But the times need to be equal, else the bullet will reach the point late or too early, no? – Fabian Fritz Sep 19 '11 at 17:07
  • How is the path given ? is it a fixed path, or do they travel in a fixed direction with a fixed speed ??? – rocksportrocker Sep 19 '11 at 17:10
  • 1
    Without knowing the exact path, you only have a chance to find the right time and angle to shoot a bullet if the angular speed of the tower and the bullet speed are much higher than the speed of the monster. – rocksportrocker Sep 20 '11 at 19:11
  • The path is given in the form of waypoints to which the monster moves straightforward. As I stated before, I already have a function which tells me the exact position of a monster at a given time. – Fabian Fritz Sep 22 '11 at 11:21