1
$\begingroup$

Background

First of all, it is a tough decision on which SE site should I post this question, because it belongs (sort of) to Mathematics, Physics, Computer Science (algorithm) and maybe even partially in Code Golf. Since it's mostly geometry-related question, I'll ask it here. Dear moderator, if you read this and have better idea on where to move it, by all means, please do.

Since I didn't do any fun programming project for some time, I decided to design a game similar to Sean O'Connor's Critical Mass. Long story short, it's a turn-based action space shooter, from what I know, one of its kind. During the battle, time stops and you may decide on where your ship should go, which missles should it fire and when you finish your round, action resumes (for around 1 second) and you may make your decisions again.

The most challenging part is to design a physics system, which allows choosing path for the ship. From what I saw in Critical Mass, I guess, that developer chose to use Bezier curves - the simplest solution, but one requiring dramatically simplifying physics model. For instance, ships can only fly in direction they are facing, there is no inertia (other than one forced by game's engine - eg. continuation of speed vector after entering pause mode) etc. I wonder, whether more complex physics can be simulated with an AI pilot, who can maneuver the ship in order to reach the destination.

I assumed the following physics (some simplifications must be made, obviously)

  • World is 2D
  • There is inertia in terms of movement. All objects have their speed vectors, which can be altered by means of thrust.
  • There is no inertia in terms of rotation. Ship can rotate up to its maximum rotation "speed" and may stop or reverse rotation at any time.
  • Objects have their maximum speed

I decided to introduce the following rules as well:

  • Time is divided to n fragments (around 100). At each 1/100 periods, ship's pilot may make decision on rotation and thrust, though maximum thrust is limited to 1/100 of ship's capabilities and similarly the rotation. So if ship can rotate 90 degrees a second, it may rotate 0.9 degree a (1/100) second.
  • Ship can apply both forward and reverse thrust

Starting conditions are described by a set of values:

  • Starting position (x, y)
  • Target position (x, y)
  • Starting ship orientation (deg)
  • Starting ship speed (px/s) (for simplicity, I assume, that in the beginning ship's speed vector has the same orientation as the ship, this can be changed)
  • Maximum thrust (px/s^2)
  • Maximum speed (px/s)
  • Maximum rotation (deg/s)

Also,

  • Simulation time (s)
  • Steps per second (1)

Since there is no fun in designing algorithm without visualization, I wrote a simple application to simulate ship's movement in space. It looks like following (clicking on preview area quickly sets new target):

Simulator

If you're interested in playing with the application, feel free to fork the repository. It's a little bit buggy, but not that much. After all, it's a simple PoC application.

Current algorithm

The AI pilot is presented with:

  • Complete set of starting conditions mentioned earlier (though starting position quickly becomes obsolete, obviously)
  • Current state: ship's position, speed vector and orientation

At each step the pilot needs to make a decision about:

  • Ship's thrust
  • Ship's rotation

World engine applies pilot's decision to current ship's state (rotates ship, applies thrust to speed vector, then speed vector to position) and asks AI pilot for the decision again.

My current idea for an algorithm is the following:

  • If ship is near the target (5 pixels), attempt to stop (align ship with speed vector and apply reverse thrust)
  • If not, try to reach the target:
    • Model the perfect trajectory: maximum speed until reaching braking distance, then brake to reach target
    • Model the (current) perfect speed vector, which would put ship on that perfect trajectory
    • Calculate difference between perfect speed vector and current speed (a vector)
    • Rotate the ship to reach that difference
    • Apply thrust, which makes the speed vector closest to perfect trajectory

The whole algorithm may be found in AIPilot.cs file.

My simulator visualizes some of vectors:

  • Perfect trajectory is pink
  • Current speed vector is green
  • Current thrust applied is orange

Vectors

Results

The algorithm seems to perform relatively well. There are actually a few outcomes. Sometimes it manages to reach the target and stop on first attempt:

Destination reached

Sometimes it overshoots (once or twice), but then manage to reach the target:

Overshoot

Sometimes it ends up circling around the target, not being able to reach it:

Circling around

Problems

The main problem is that initial attempt to approach the target usually overshoots a little. "Pilot" realizes it quite quickly and starts to counteract the overshoot, but does that not optimally, by rotating the ship around.

Approach

Also, the approach is usually too fast, making not much space for corrections - hence overshoots and loops.

Ideas

The algorithm is a greedy, decision-based one. I'm thinking of the following improvements:

  • Temporarily moving the target, basing on current speed - making the pilot make more aggressive changes of speed vector. The more ship is aligned with the target, the less "virtual" movement would be.
  • Changing the model of "perfect" trajectory to make the pilot brake faster, leaving him more time to adjust trajectory.
  • Promote being aligned with the target, such that pilot won't rotate the ship around too often.

Questions

Finally.

  • Is the world simple enough, such that deterministic algorithm may be designed?
  • Is my algorithm good enough, such that it may be tweaked to be good enough?
  • If yes, how may I modify it?
  • If no, what approach should I take? Pre-planning the whole route and following it? Maybe heuristic approaches? PID?
$\endgroup$

closed as off-topic by JonMark Perry, Claude Leibovici, Sahiba Arora, Namaste, Raskolnikov Jan 1 '18 at 22:26

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is not about mathematics, within the scope defined in the help center." – JonMark Perry, Claude Leibovici, Sahiba Arora, Namaste, Raskolnikov
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I suggest first solving the problem analytically for the 1-dimensional case, then working on an algorithm to direct the trajectory of the ship straight toward the target in a reasonably efficient way. I will try to write more tomorrow. $\endgroup$ – Taneli Huuskonen Jan 3 '18 at 23:51
  • $\begingroup$ @TaneliHuuskonen I already did, I'm simply modeling uniformly delayed movement for 1-dimensional case. If you place target right ahead the ship, it will reach it accurately. The problem lies more in inertia of movement, which makes reaching the target harder. AI pilot does not compensate for the inertia and overshoots the target (sometimes indefinitely). $\endgroup$ – Spook Jan 4 '18 at 9:15

Browse other questions tagged or ask your own question.