Light Racer 2.0 - Days 25-30 - More AI and Performance Tuning

Wow, so much has happened in the past 6 days. My tasks were to finalize how items and NPCs spawned and finish Easy, Medium and Hard AI. Most of the time was spent optimizing algorithms, adding collision checks, changing little bits of design here and there and testing. Testing testing testing. This is the stage where it really gets tiring to play your own game. It just starts to lose some luster after the 100th time you've tried the same level against an Easy CPU. That's ok though because I pushed through and 6 days later, I've got most of the core game done. I also sped the game up by an average of 50% by optimizing my path finding algorithms and drawing things more efficiently.

Day 25 - What was done:

Performance Tweaks
Randomized Item Spawning
Finished all collision checks

To determine the correct locations of item spawns, I had to finish implementing several collision detection algorithms for various game objects that I had previously put off doing. This includes the ability for a game object to determine if it intersects with another rectangle, which is what we usually refer to as a bounds-based collision check. The algorithm itself is very simple for non-rotated rectangles, which is what this game uses for everything except the laser. The problem that I had is that performance slowed down a bit after I finished all of the implementations. I will need to work on that very soon.

The item spawner picks a random spot for the item and then loops to see if that spot is already occupied (bounds check) by something else. If it is, it adds 5 to both x and y and tries again. It will do this until it ends up out of the world, at which point a new random spot is chosen and the cycle repeats. This could potentially end up causing an infinite loop if there isn't a single 20x20 pixel spot in the world where the item can go, but I have yet to see that scenario.

Overall the item spawning works very nicely now. At any given point in time there can be 2 items in the world and they can be the same type of item.

Day 26 - What was done:

Began work optimizing pathfinding algorithms

I spent the entire day trying to speed up my A* path finding algorithm that is used to control the AI players. I received some help on gamedev.net and eventually settled on using a BinaryHeap with every little optimization I could think of that would make the code run faster.

The original implementation was based on a Java A-Star example I found online somewhere, but it was generic and was far too slow to run two AI players each at 10FPS (my AI update speed) on a phone. I was able to triple its speed by performing some very basic optimizations - I had ripped out any code that I didn't need, got rid of all the interfaces, coupled it tightly with my AITile class and minimized member references.

This ran fast enough to test the game with but I still needed to quadruple the speed of the algorithm to get a longer path in under 10ms. I first got rid of the closed list that the algorithm uses and instead use a closed flag on each AITile. that was a big boost because checking for the existance of an element in an ArrayList was a linear operation which was totally unnecessary since I had the element in-hand and could just keep a closed flag on it.

The next thing that I did was replace the sorted open array with a linked list, which substantially improved speeds once again. It's not necessarily optimal though and for the small space I have (1440 tiles max), a Binary Heap will be a better overall performer. I then switched to an optimized Binary Heap that is tightly coupled to my AITile and did a few more optimizations in an effort to reduce floating-point math and reduce indirection, index look-ups and member references.

The resulting algorithm can run 160 search iterations in 8-14ms, compared to the previous 40 iterations in about the same amount of time. I think that will work for what I want and I can use some tricks in the AI to reduce the number of path finding searches further.

Day 27 - What was done:

Tweaked A* algorithm more.
Began implementing ADA* Algorithm.
Stopped working on ADA* because it's looking like it will consume too much time. My A* is fairly fast now and can be modified to return a partial result, which will let me tighten down the CPU cap on it and still have some good playable AI.

Day 28 - What was done:

Performance testing and tweaking
AI enhancements

I found that drawing the background (static) as RGB_565 was a huge performance boost for the game.

Added game objects to AI tiling

Refactored Medium AI to prepare for Hard AI

Day 29 - What was done:

More AI enhancements. I finally have the code factored out so that I can set up rules and probabilities to get the right effect.

Medium and Hard AI will use the same class. The difference is that Hard will be item-aware, and medium will not. Medium also will go into random states of mindless navigation for 400-800ms. I found that with the 2-tile lead and having both AI players always go for the human, medium is a little more difficult than I'd like but it's also a little predictable. The random navigation state should take care of that.

Day 30 - What was done:

Finished implementing Medium and Hard AI.

I have to update the collision checks to account for invincibility. While invincibility works in the game, the AI code uses a different check to see if a move is valid. This check didn't support the collision detections.

I tested Medium with the seek and default mode switching and it works very well now. It's not quite as hard as it was, which is good, and it's a little unpredictable, which I like.

Hard AI is a lot of fun to play against. It is fairly strong and picks up items, using them against you. I like that.
'
I have to say that AI programming is fun but can be very meticulous and tedious to test. It's not my area of expertise and I just spent about a week working to tweak everything. I accomplished a lot in that week as I was able to significantly speed up the game and make the AI much more fun to play against.

While making the progress video, I saw that there are some really obvious bugs with the Hard AI so I'll need to address those but I'm going to wait until I'm doing the final testing to work on it. I'm thinking that I'll let the testers determine if the AI is hard enough. If it is, then I'm done. If not, then I have to work on the things I see as bugs. What's funny about AI programming is that some times things the developer sees as bugs, the user sees as just how the computer plays. They have no idea what the actual code is doing most of the time. To them, they are just playing the computer.