Light Racer 2.0 - Days 5 and 6 - Tiling the World for AI

Most of what was done on days 5 and 6 was code to lay the foundation for the new medium and hard AI. Both AIs will make use of path-finding algorithms and because of that, using tiles to approximate coordinates will be far more CPU efficient, so long as creating the tiles themselves doesn't eat too many cycles. My strategy was to have each AI player manage its own tiles relative to itself. This makes it so that the point the player is at is at the center of a tile and that the tile size can be relative to the number of pixels a racer moves between AI updates.

On day 5, I developed a method to "tile" out the board and mark up each tile with a state: Open, Closed, Invalid, Self or Target. This is essentially all the A* algorithm needs to work. I also got a nice visual debugging of the tiles working and am able to show that they are being calculated correctly but I'm having performance problems. I think AI can consume 50% of the CPU time so that would be budgeted out as follows: Game Max AI players: 3. AI updates 10 times per second, so AI total must be under 500ms for all 30 updates, so 16ms max per update. 5ms for the basic tiling may be ok but I'd like it much better if I could keep it under 2. I'm worried that A* is going to really be a CPU killer. The problem I'm having right now is that it's taking 20ms additional to do collision detection on the tiles. I believe the method I'm using may be horribly inefficient so I'm going to take a look at how to write it totally differently.

My new approach will be to search from the world instead of from the tiles. This means that I'd start by assuming all tiles are open. Iterate each player, trace the path and mark each tile the path touches. Right now each tile is checking to see if a path touches it, which means that the full-game collision detection algorithm is run for every tile, or several hundred times.

On Day 6 I tried the new approach and it worked much better. Each full-world tile update takes around 5ms now. When AI Debugging is on, the blue areas are "Open," the red are "Closed" and the regular graphics are underneath. Currently, the MediumAI (the one I'm working on) isn't actually calculating a direction to turn to so it just go straight north. That's ok because the goal of the day is to have a really fast tile generation algorithm working.

I would have posted some code but all in all it's about 150 lines of code that wouldn't really matter much without several other classes. Code like this is usually custom to the game engine so if anyone is needing help, please ask and I can help with math and a general approach.

Some of the things I dealt with were:

final int minMovement = (world.movementRate / LightRacerConstants.AI_FPS);
final int centerOffset = minMovement / 2;
final int firstX = (player.curX + centerOffset) % minMovement;
final int firstY = (player.curY + centerOffset) % minMovement;
AITile[][] tiles = new AITile[tileCountX][tileCountY];
for (int x = 0; x < y =" 0;">

AI_FPS is a constant, set at 10, so that the AI is updated at most every 100ms. The movementRate of the world is how fast the game is playing with a number like 100 pixels per second. This would mean that dividing 100/10 would give us 10 pixels per update, which is the minimum number of pixels the physics will move a racer before the next AI update. I'm using that for the size of the tiles.

centerOffset is simply how many pixels it is to the center of a tile.

firstX is the number of pixels offset of the left wall.
firstY is the number of pixels offset of the top wall.

Since the tiles are always moved to be centered on the AI player in question, they don't usually line up perfectly with 0, 0. Often times the rows and columns around the border are smaller than the center tiles. This makes calculations more reliable because we know that in 5 updates, the racer will probably end up close to the center of a tile 5 tiles away. If we had the tiles set statically, the racer might start 1 pixel off of one tile and end up 7 pixels in to another. That's not good for determining a sound path. The flip side is that other racers and trails end up marginally in some tiles. More on that later.

After that code, I have it iterate the full x and y axis, calculating the bounds for each Tile. Right now, the AITile class looks like this:

public class AITile {
public static final int OPEN = 0;
public static final int CLOSED = 1;
public static final int INVALID = 2;

public int state = OPEN;
public int topLeftX;
public int topLeftY;
public int width;
public int height;
public int tileX;
public int tileY;
}