Light Racer 2.0 - Days 7 and 8 - Medium AI

Developing AI for an action/puzzle game can certainly be a challenge. What is the best approach? How do I want the computer to "feel?" How hard is too hard? What algorithms will be efficient enough to work well on a mobile device? These are all questions I had to ask myself when I was planning Light Racer 2.0. Light Racer 1.0 had just one AI implementation. 2.0 has 3: Easy, Medium and Hard. Easy will be the old Light Racer 1.0 AI. I made the decision to make Medium AI use a pathfinder algorithm and always target 1 tile in front of the opponent. A* seemed like an obvious choice for this task, but once I implemented it, I started to find that the AI is still lacking.

On Day 7, I did the first A* implementation. I found one that someone else had done in Java and modified it to make it work well with Android's limitations, which basically means that the AStar class never creates new objects and is very careful about referencing members and virtuals. This worked, but I had a few problems.

Here are some screen shots with AI debugging enabled. The white line from the yellow to the blue player is the path that A* has determined is the shortest path to the target tile. This works, except when the racer turns toward the existing trail and ends up colliding with it, as you will see in the video.

The path finding algorithm doesn't take into account how long the racer is. It is basically assuming that if you're in a tile, you can move into another adjacent tile without penalty. This is causing the Ai to run the racer into walls when turning into them while too close. Also the performance is good until A* has to do a really deep search. There are a few very inefficient pieces of code in my A* implementation that I believe I can speed up.

On Day 8, I did the following:

Tweaked the A* heuristic
Did more performance optimizations (long searches still cause a bit of slow-down)
Added better opponent selection to medium ai
tweaked collision prediction for medium ai

These changes have made the Medium AI work significantly better. I was originally planning on developing the Hard AI next, but the lack of game depth has been really bothering me throughout the last few weeks of development. I decided to switch directions and build the levels and items before going any further with the AI. Since I don't have any levels or items right now, I need to start designing the code to be able to handle them. I designed a speed-boost icon in photoshop and decided that the game should have 10 levels that can be played at 3 different difficulties. More on that tomorrow.