I am trying to solve this puzzle using a genetic algorithm. Since I need to determine how well some set of instructions does, I am trying to reverse engineer the game engine such that I can accurately simulate the outcome of those instructions. My current understanding is as follows, I put strange/annoying behavior in italics and questions in bold, please correct me if I'm wrong:
The position and velocity are stored as floating point numbers. (float or double?)
At the beginning of each turn, the angle and the power are instantly updated to be as close as possible to the output of your program. If you are out of fuel, the power wil be set to zero. The power stays the same during the entire turn, even if the lander runs out of fuel during that turn. (Either lazy programming, or to make the problem slightly easier.)
Then the new position and velocity are calculated with the exact mathematical formulas:
x[t+1] = x[t] + v[t] + a[t]/2
v[t+1] = v[t] + a[t]
where a[t] is the acceleration at turn t based on the angle, power and gravity and x[t] and v[t] are the position and velocity at the beginning of turn t respectively.
Finally, there is a collision check:
- if you collide with non flat ground, you crash
for the following two checks, the speed you would have had at the end of the turn if there was no collision is used, rounded to the nearest integer rather than the unrounded speed at the time of the collision (Either lazy programming, or to make the problem slightly easier.)
- if you collide with the landing site, and your speed or angle is too high, you crash
- if you collide with the landing site and your speed and angle are both safe, you land
- if there is no collision, the new position, velocity, angle, power and fuel are given to your program as input. However, the position and velocity are first rounded to the nearest integer. (Ridiculous. Why would you do that?)
Each turn, I simulate the trajectory myself using the assumptions above (I use doubles). My rounded simulated values always correspond to the integer input every turn, which suggests that those assumptions are correct, and my simulation accurately implements them.
I now need to figure out how the collision check is done. It is possible to derive an exact formula for that, and I expected the game engine to do that as well, since it also uses exact formulas to calculate the next position and velocity. However, I made a disturbing (to my inner mathematician) discovery:
In Mars Lander 1, keeping the angle at zero, I got to a simulated y-value of around 99.8. Since the landing site is at y = 100, I expected to have landed, but the simulation went on for another turn.
It appears that the position is rounded, before the collision check is done. This means that the game engine does not use the exact trajectory to detect a collision. So my question is: how exactly does the game engine detect collisions? The only way I can think of, consistent with this, is as follows:
The trajectory used for the collision detection is a straight line between the rounded previous position, and the rounded current position. Is this correct? If so, why is this bad approximation being used? Has anyone had any issues with inaccurate collision detection?