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)
- 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):
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.
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
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:
Sometimes it overshoots (once or twice), but then manage to reach the target:
Sometimes it ends up circling around the target, not being able to reach it:
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.
Also, the approach is usually too fast, making not much space for corrections - hence overshoots and loops.
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.
- 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?