Another mathematical question

programming
1

Hi,
I am a bit off-topic, because the game I am doing that for is written in C, but the question is a general one, so I hope you will bear with me :slight_smile: (the C-snipplets shown also just contain math, which should be rather similar in other languages)

xpilot or now xpilot-ng is a space-shooter type of game with a physical acceleration - i.e. you thrust your rocket to accelerate, you turn and thrust it again to brake (I.e. from standing still, one can move s=1/2 at^2 within the time t; the acceleration a is a fixed value for all ships).
You might have guessed that, but for completeness: the little ships in that game (amongst other things) try to shoot each other.

I have tried to write a robot, that is able to evade shots - and for simplicity, it just takes the shot that will hit soonest and tries to evade that. The result has been quite impressive… until one figures out how to deal with such an attacker: by fiering multiple shots, the robot will try to evade in one direction in one frame, in the opposite directioni in the next frame… and so on, until it is hit. With some practice, it so becomes nearly trivial to shoot the robots - specially, if one also uses some weaknesses in the attacking logic against them.

There is already some math involved… I’ll share what I got so far, for the case it is useful to someone.
We have, for every shot a set of relative velocities and relative positions as vectors:


        delta_velx=( shot->vel.x -  player->vel.x );
        delta_vely=( shot->vel.y -  player->vel.y );
        delta_x=   WRAP_DCX( shot->pos.cx - player->pos.cx );
        delta_y=   WRAP_DCY( shot->pos.cy - player->pos.cy );

(I am putting this in without further comment, because I think, it is pretty self explanatory)

Now, from the deviation of the distance function for the two objects, we can get the time of encounter, i.e. when the two objects will be closest:


       time_shot_closest =
            -( delta_x * delta_velx + delta_y * delta_vely) /
            ((sqr(delta_velx) + sqr(delta_vely)));

We get that from the (square of) distance function d(t)=(delta_vel*t+delta_s)^2
(delta_vel=relative velocity, delta_s=distance)
and its deviation.
We can skip the square root here, because the time of the minimum of the function of distance^2(t) is also time of the minimum of distance(t).

At the place where the deviation is 0, the distance is at minimal (there cannot be a maximum at this place: if you consider a shot passing an object, there can never be a maximal distance)

Negative times as a result and the shot can be skipped here - the shot has already passed us in this case.

Now, from this we can get the distance - it is the norm of the distance vector: ||d||=sqrt(d^2).


        sqdistance =
            (sqr(delta_velx) + sqr(delta_vely)) * sqr(time_shot_closest)
            + 2 * (delta_velx * delta_x + delta_vely * delta_y)
            * time_shot_closest
            + sqr(delta_x) + sqr(delta_y);

If we now compare this with the radius of the ship, we know which shots will hit us.
For performance reasons, one can also just compare the square of the ship radius with the square of the calculated distance, which is why here “sqdistance”, i.e. the square of the distance is calculated instead of the distance itself.

Now I know which shots are going to hit, and when they do it.
The robot most urgently now needs to evade the shot, that will hit first - so a faster shot that is still far off might need to be evaded earlier than a close shot that is not moving much compared to the robot.

In this “single-shot” version, “time_shot_closest” is compared for all shots, and the one with the smallest time is evaded.

This was the first difficult question - where to evade to?

At least for this single shot, we get close to the optimum for evading it, if we just calculate the vector between the center of the ship and the position of the shot at the time of their encounter and steer in the opposite direction to increase that distance. This vector is just (delta_x, delta_y) at the time of encounter, so one just needs to use “time_shot_closest” in the distance function and will get the vector; we want the opposite direction, so this (x,y) is changed to (-x,-y).

This is as far as I got - and as far as that, this has been more sort of a tutorial :slight_smile:

Does anyone have a good idea how to expand on it such, that multiple shots can be treated in a sane and efficient manner (and preferrably without getting computationally too expensive)?

I already do store “time_shot_closest”, the identification number of the shot and the square of the distance in an array.

My ideas include

  • when evading the most dangerous shot, find/choose a direction in which no other shot hits us
  • use some kind of “least square root fitting” to find a vector. Of course, in this problem, I don’t want to minimize all distances, but maximize them - the ones with the smallest time-until-hit having the biggest influence on the vector. As the “some kind of” suggests: I have no concrete idea how to do this yet.

In any case, it would be very useful to remove the “deadlock” that occurs, when two or more shots arrive from a similar direction, but the result of the calculation yields two opposite directions to use to evade. Another possibility would be to check for a previous evasive action in the last couple of frames and “just keep going” in this case. Looking back just a single frame, this has not been very successful, though.

Any help or ideas would be appreciated - er…, no, sorry, I wanted to say:
PLEASE HELP HELP HELP HELP QUICKLY!!!111111111123
:wink:
(should have put that in the subject… g)

Iri