Sống gấp: Light Racer 2.0 - Days 3 and 4

Much like the first two days of work, days 3 and 4 involved mostly refactoring the existing code to bring it all in to the new architecture. The end of the fourth day was much more exciting than the rest because nearly 100% of the design was completed and I was able to work on new code again. I implemented 2D coordinate interpolation for the racer physics and AI, which I had a few problems with but overcame. I also implemented visual AI debugging which is key in developing better AI.

Before I started modifying the game or adding anything, I was almost purely refactoring. This approach has paid off because now I have a great new design that will allow me to add all of the new features and the game is still in a 100% usable state. In fact, I could still package it up and put it on the market with little effort. I keep pushing this idea because I believe it's very fundamental to a successful developer. Notice how through the days of refactoring, I was able to keep the game working exactly as it had before. That's the big difference between refactoring and rewriting. Call it semantics if you wish, but I have not lost a single piece of functionality and I've been able to test it several times every day and verify that everything is still working exactly the way it was when I started the project.

The great thing about what I'm doing is that I'm so confident the entire way. I'm not scared that I'm going to make a huge mess that will be a major headache to clean up. It's one thing at a time and by dealing with only one small issue at a time as I go, I'm able to tackle every issue that comes up. In software, it's simply overwhelming to deal with tons of issues all in one go. Slow and steady wins the race here, no pun intended. At the end of the refactoring, the new design was fully implemented and the game was still working exactly as I left it. Now it all works and I'll be able to add in all of the new features I want. How cool is that?

Day 3: What was completed?

The LightRacerWorld is now used consistently and several things were added to the world. It has game state information, the pixel size of the game area of the screen, all of the players, the last, current and delta tick time, the level and the current movement rate (game speed). This was important because the world is the part that is passed into GameObject update() methods, which in turn will run AI algorithms. All of these things are needed for AI to process and for physics to interpolate.

I moved SoundManager into resources. This made it so that GameObjects can trigger and control their own sounds.

I combined AI and player physics updates into a single update. This improved the interface from the main game class to the players. Now the main loop just iterates through players and calls update(world) on each. Before it had some logic to determine if the player was AI and what to do.

I moved path updates into Player. This is just to further simplify the main game loop. The more simple, the better. Here's some game testing from the end of Day 3, just to confirm that the core game was still working correctly.

Day 4: What was completed?

Player now controls all of its own sounds. This wasn't complete before but now is 100%.

Player has one update() method. It was many updates before but all of that logic exists only in the Player class and the main loop has a very easy interface to update the Players.

Changed Receiver to PlayerInputSource. I renamed that class because I think that it is more appropriate this way. The PlayerInputSource is fundamental because it is either a network client, network host, human player or AI player. It is the keystone that will allow for different kinds of AI and network configurations.

LightRacerAI now implements PlayerInputSource. It's official. The AI is now a PlayerInputSource.

Created HumanInputSource. This was to finish implementing that part of the design.

Renamed PlayerPhysics to Collisions. All that was in the class was a method to check for collisions. I made that public and static, so it's really just a utility class now. I don't normally do that but it was needed by a few different classes and didn't fit well into the hierarchy.

GameObject created but can't standardize draw methods because of layering. I have a GameObject now but because this game is 2D, I can't have one draw method. Drawing order must occur like this: Background, light paths, racers, explosions, text. If I were to do one player at a time instead of one layer at a time for all players, you would end up with paths and racers on top of explosions, which would not look good at all. I don't have a good solution for this yet but it's not the worst thing ever to have one custom interface and everything else is looking very good.

Refactoring is complete! Now for the fun stuff...

Implementing Interpolation in a 2D World
I changed the physics of the game to use time distance interpolation instead of moving a set number of pixels per tic. The idea is that the game will run the exact same speed but at different FPS depending on how much load is already on the device. I found that for different phones with different numbers of services running, the game would run faster or slower and I wanted it to be consistent.

The interpolation works really well. It's really straight forward to write interpolation for a 3D coordinate system because you can actually move a floating point number away but in 2D land there are a set number of pixels and so you must move a nice round number. This was problematic at first because when I set the movement rate to 100 pixels per second, I ended up getting about 80. Why do you think that is?

I almost knew immediately what the problem was. Interpolation is calculated by using the the last known location of the object, the direction the object is moving in, the rate of movement and the last tic time and the current tick time. If you have that information, you simply take the difference in time, multiply that against the rate of movement and then move the object that far from the last position in the direction it is moving. The formula could be expressed as newPosition = oldPosition + (tickDelta * movementRate * direction).

Here is an example that also shows the problem:

Movement Rate = 100 pixels per second
Racer is located at (x,y) (100,100) and is facing North.
The last tic time was at 1000
The current tic time is 1078
Where should he be now?

The math looks like this: 78 (tick delta in ms) * movementRate (in seconds) / 1000 (to convert seconds to milliseconds) = 7 pixels.

So we should move 7 pixels in the north direction (subtract from Y axis) so that would put our racer at 100, 93. That works, but with a tic delta of 78, how did we end up with 7 pixels? What happened to the other .8 pixels? In a floating point world, we would have moved the racer 7.8 pixels. Since we can't do that we can either discard the remainder, which is what I was doing and was causing the game to run slower than it should have, or we can use a trick that I came up with.

Since there is usually a remainder, I changed the code so that it works like this:
movement = (tickDelta * movementRate + carryOver) / 1000
carryOver = (tickDelta * movementRate + carryOver) % 1000

carryOver must be an instance field on the GameObject you are interpolating, because it will need to be the remainder from the last physics update. This worked, because now that .8 pixels from the example is carried to the next update, and if that next update has a remainder that is at least .2 pixels, then an entire pixel will be added to the movement, thus making the movements add up to 100 pixels per second.

This worked ok but I was able to see the little jumps sometimes if there were small remainders for a few updates and then they finally added up to 1000 to add a pixel. I realized that only rounding down wasn't the most even way of approaching the movement and remainder problem so I also implemented a negative carry over for remainders over 500. Now the carry over value will, instead of being 0 to 900, be -400 to 500. This worked to smooth out the 2D interpolation. Here's some physics code from the game:

long targetMovementAmount = (world.tickDelta * world.movementRate) + movementCarryOver;
int pixelsToMove = (int) (targetMovementAmount / 1000);
movementCarryOver = (int) (targetMovementAmount % 1000);
if (movementCarryOver > 500) {
// round up and carry over a debt.
movementCarryOver = movementCarryOver - 1000;
pixelsToMove++;
}

All said and done, the game runs really well now. It's much smoother than before and it doesn't feel like there's any lag even when the phone slows down for a brief second.

Making AI work consistently in a variable update-time environment
After I added the interpolation to the Player physics, I got rid of the old cap I had placed on updates. Now the game will update as fast as the SurfaceView will allow for draws, so 60FPS. My emulator runs at around 45FPS so that's not too bad. I haven't tried it on the phone yet with my FPS text turned on but I'll have more on performance later in the book. For now, a new problem has come up. I used to run the game at a set 30 updates per second (or slower) and my AI was designed to run at that speed. The new AI has to be able to also interpolate or it runs totally different on one system to the next and also it takes up far more CPU cycles than are necessary. AI doesn't actually need to recalculate 45 times per second. 10 will do just fine. Is it even fair to play a computer player that can process everything faster than your eye registers motion?

I updated the AI to use interpolation similar to that of the Player. All the AI really needs to know is "How far will the racer move until I get to make another decision?" For that I decided to combine that with an AI update limit of 10 updates per second. This made the math simple: If the AI updates every 100 milliseconds, then the furthest the racers could go before getting to make another decision is 1/10th of the current movement rate. This doesn't take into account if the game runs slower than 10FPS, in which case there will be a problem here but I'm assuming that it is unplayable at that speed anyway. It works this way because the AI needs to be able to make sure that it's not going to run into a wall before getting to decide to turn again. That number is how many pixels it will go so it can pipe that through the collision detection code and see if there is something in the way.

Limiting the AI to 10FPS is a great thing because it works well and now I have some extra CPU cycles to use for even better AI. My Medium and Hard AI are going to be far more CPU intensive than the current Easy implementation. I knew I was going to need a better way to debug the algorithms so I added in a visual AI debugging feature. The PlayerAI interface has a drawDebug(canvas) method which is called by the main loop when the AI debugging is turned on. I implemented a little bit of it for the EasyAI to make sure it was all working. The EasyAI sometimes decides to "come after" a human opponent. Each time it makes this decision, I had it draw a "targeting" line that you can see in red in this screenshot.

Light Racer Easy AI debugging