I'm about 3 weeks away from finishing a new version of a fairly popular game for the Android platform called Light Racer. I've been keeping a blog/journal of the entire development here - Light Racer 3D Development Journal That journal will show you exactly what I'm trying to do and it's generally up-to-date within a few days of development. My game is 2D and has a finite world. Players are represented by a little motorcycle with a light trail following. Players crash when they hit another player, a light trail, a map object or the walls. The goal of the AI is to cause the human player to crash into any of these things. Power-up items are randomly spawned which can give a player a significant advantage. My biggest constraint is that this is on a mobile platform and I don't have a ton of CPU to work with. My first approach was to use A* to find the path that leads to one tile in front of the human player. My theory was that the relentless pursuit of that destination would certainly end in a human crash. Problems with that: 1) It's predictable and easy to work around. 2) My A* algorithm is eating up too much CPU when it has to search more than half of the world. 3) It doesn't take into account items or what the items can do to help the player. I'm about to start working on this again and would really appreciate some general direction. Here are some links to give some background on the game and problem: The first two show how I implemented the "Medium" AI. This was done before I had added all of the items and map objects. Now the game world is more complex so I have to take that into account. Tiling the world for AI Implementing Medium AI Here is the current state of the game, which will show a few levels. Light Racer 2 - new graphics So, any takers? Any significant contributions will receive mention in the game credits. Thanks!

A buddy of mine was in a programming class a number of years back, and the project was to program a connect 4 game with an AI that played against you.

The AI he programmed was to randomly choose the column to the right, the column to the left, or the same column as you chose on your last turn.

Really crappy AI, but the teacher was amazed at how smart it was and that it seemed to play like a real person.

... until he saw the source code! :P

lesson being - games are illusions and you don't actually need to make AI smart, you only need to make it seem smart (or act smart).

Maybe just some simple rules such as...

#1 - if the player is farther away than X distance, chase the player
#2 - else if the player is within X distance, try to get in front of them and cut them off with a light cycle trail.
#3 - if at any time you are heading towards a wall, turn to avoid it! (choose randomly whether to turn left or right)

Simple rules, but perhaps something like that would be enough (:

it deffinately should be a lot lighter on CPU usage, but its hard to tell until you try it if it plays well enough.

Good suggestions. The one problem I have with the more simple rules is that the AI tends to get itself into a really obvious corner. That's one of the big reasons I added A*. It keeps the AI from doing really stupid things.

You're totally right about the illusion factor. I don't care how smart it really is, I just need the game to run fast and the AI to be challenging.

I've been thinkin about this and i was thinking there might be a good way to do it with some ray casts and rolling your own path finding that way. something like see about where the ai is headed, if there is a wall in front, trace the wall to the left and right to see if it puts you in better shape to go left or right.

But, growl, can't think of the details for that and it might start getting expensive :/

You might try a genetic algorithm just so the ai's behave ok based on input around them?

shrug... sorry, wish i had some better suggestions for you...

Quote: You might try a genetic algorithm just so the ai's behave ok based on input around them?

I guess I don't really see how a genetic algorithm would help here. They usually take a very long time to train before producing any reasonable results.

How about this really simple one:
The computer player just drives in a straight line until it has to turn. It then randomly chooses a direction that won't cause it to immediately crash (if one exists).
You could also weight the probabilities of each direction; maybe the computer more often chooses to turn in the general direction of the human. You could even add some randomness with very low probability at each step to make it slightly less predictable.

I was thinking a GA that would take in various parameters like density of walls in the near vicinity, whether it was blocked relatively closely to the right, left, front, and back, vector to the player, stuff like that.

Then, train it to give pretty good behavior (survive for a long time - although im not sure how you would simulate the player) and out of that hopefully would come a well behaved AI.

::shrug::

I would contend that in this case, the right approach is a rule-based engine. The rules that you are interested in are fairly concrete. At that point, using a GA (or NN, even) is the lazy approach to coming up with a small handful of parameters that should be able to be ascertained by logically approaching the problem. Put another way, a GA is serious overkill.

Hey Guys, thanks for the responses!

I've used a combination of rules, probabilities and actions to get my different level of AI. When a condition is met, some percentage of the time an action will be taken. This makes it so that for easy AI, 5% of the time it decides to switch direction. When it switches direction, 50% of the time will be towards the human player.

In Medium AI, I have modes, so for 2000-4000ms it will be hunting the opponent using a pathfinder targeted a few squares in front of the opponent. Then for 400-800ms it will do something random so that it's not too predictable.

My Hard AI can target the opponent, or power-up items if they are available and uses pathfinding 100% of the time to get to where it wants to go. It's choosing between those things randomly that gives the game some variation.

So far so good. Thanks for all the help!