Hello, We´re working on a Micro Machine type racer for cell phone and are soon going to start on the AI. I´ve never written AI for a racing game before so i need some help and ideas about what would be the best way to tackle this problem. The considerations are 1) Very slow CPU 2) Very limited ram (190kb) There will be 3 opposition cars to be handle by the AI. The track will be held in a 2D array. I am wondering how to make the opposition 1) race competitively, 2) not get trapped behind objects if and when they crash, 3) corner properly. 4) Each racer may have a slightly different skill level. What way were games like this handled in the past? Is the best way to look ahead and always aim for the road tiles a certain distance ahead of you? With certain conditions for objects being stuck in front of the driver! Any ideas would be greatly appreciated. Thanks, Brian

I think alot of basic racing games use a checkpoint system. The car will just go from one point to the next. If/when the car gets stuck, you can do some logic to get it to backtrack a little, then continue the race.

Quote: Original post by Woody FX
Hello,

We´re working on a Micro Machine type racer for cell phone and are soon going to start on the AI.

I´ve never written AI for a racing game before so i need some help and ideas about what would be the best way to tackle this problem.

The considerations are
1) Very slow CPU
2) Very limited ram (190kb)

There will be 3 opposition cars to be handle by the AI.

The track will be held in a 2D array.

I am wondering how to make the opposition
1) race competitively,
2) not get trapped behind objects if and when they crash,
3) corner properly.
4) Each racer may have a slightly different skill level.

What way were games like this handled in the past?

Is the best way to look ahead and always aim for the road tiles a certain distance ahead of you? With certain conditions for objects being stuck in front of the driver!

Any ideas would be greatly appreciated.

Thanks,
Brian

In the 2D racing game I did for the Amiga (about '93-'94-ish, my memory for dates and times sucks), I remember using an attribute map for this. This is just metadata added to the track map (usually in the map editor). In my implementation, I simply had the track designers place 'arrows' on each drivable tile that told the AI cars which direction to steer towards.
For tiles close to the edge of the track, you point the arrows inwards, towards the centre of the track. As you move closer to the centre of the track, the arrows become straighter, pointing the car straight along the road.


The advantage of this is that checkpoints aren't needed and you don't have to worry about special conditions. Only obstacles need to be explicitly handled.

To achieve a variety of car behaviours, you just give each AI car a slightly different response rate to these arrows, with different acceleration levels, etc. This way, you give the impression of near-human driving technique and plenty of scope for variation.

To save memory, I'd just use an 8-direction resolution for the arrows, which allows you to cram the necessary data into 3 bits per tile. You can also use run-length compression to compact the attribute map quite dramatically as the fenced-off areas beyond the track are irrelevant.

--
Sean Timarco Baggaley

Quote: Original post by stimarco
In my implementation, I simply had the track designers place 'arrows' on each drivable tile that told the AI cars which direction to steer towards.
For tiles close to the edge of the track, you point the arrows inwards, towards the centre of the track. As you move closer to the centre of the track, the arrows become straighter, pointing the car straight along the road.

Sounds interesting, although phones seem a lot slower than what you could do with Amigas, and they have a lot less memory. High end phones are about the same. I was thinking of using vector based lines which car follow. With your approach how do you stop AI cars crashing into each other and getting stuck?

Quote: Original post by stimarco
To save memory, I'd just use an 8-direction resolution for the arrows, which allows you to cram the necessary data into 3 bits per tile. You can also use run-length compression to compact the attribute map quite dramatically as the fenced-off areas beyond the track are irrelevant.

Okay well we have plenty of room for the extra bits! RLE isn't really practical on phone as to avoid memory fragmentation the level is stored as a static 64x64 integer array, it's not a good idea to use byte on a phone either as the JVM casts to everything to int. Copped on the the 8 way direction thing already.

Quote: Original post by pkelly83
Sounds interesting, although phones seem a lot slower than what you could do with Amigas, and they have a lot less memory. High end phones are about the same.

The Amiga had a shared memory architecture, so subtract the display buffer, back buffer and sprite/tile data from the 512Kb standard RAM complement. (The game I was working on was intended for the original A500 model, not the A500+, although the A1200 had just been released at the time, I think.)

The Amiga's CPU was a mere 7.mumblemumble MHz and, while the custom chips for which it was famous were powerful for the time, they're pretty pants by today's standards. Most colour display mobiles could run rings around it. Hell, even the cheap phones I see here have RAM measured in _megabytes_ and CPUs running at least 5-10 times faster than the Amiga -- more than enough to make up for the lack of hardware acceleration that's currently the norm.

So I disagree: mobile phones are more than capable of running a game like this and are easily fast enough to cope. My SonyEricsson P900 (available on a contract for less than £99 here in the UK) has _two_ 150MHz+ CPUs, a colour screen with 16-bit colour (the Amiga A500 only had 32 colours in most games), and MP3 playback support. The A500 was 4-voice polyphonic with only 8-bit sample playback at that.

(I must confess, once I'd worked on an Atari Falcon'030, the Amiga sort of lost its attraction. I was never a fan of Amiga's custom chip designs.)

Quote:
I was thinking of using vector based lines which car follow. With your approach how do you stop AI cars crashing into each other and getting stuck?

Standard collision avoidance is quite easy. I just used bounding box collisions for them and set the cars to repel each other in the AI, so that they tended to steer around each other or slow down. If they hit, they'd just bounce.

I found the waypoint method tends to result in cars visibly driving 'on rails', like those Scalextric (slot car) toys. It's possible to alleviate the effect, but the attribute map system worked well for me and required much less processing power. Each frame, you'd just check each AI car, look at the tile it's sitting on and tell it to turn towards the direction the attribute tells it to. If the mismatch between the car's current heading and the desired heading is greater than a set threshold (you have to experiment with these), you apply the AI car's brakes so that it can turn more sharply.

I think I used a 4-bit (i.e. 16-position) resolution for my attribute map, but 3 bits ought to be acceptable for a game running on a tiny mobile phone display.

Quote:
Okay well we have plenty of room for the extra bits! RLE isn't really practical on phone as to avoid memory fragmentation the level is stored as a static 64x64 integer array, it's not a good idea to use byte on a phone either as the JVM casts to everything to int. Copped on the the 8 way direction thing already.

Ah well, that's fair enough. I've only played with the Symbian SDK and I was using C++ for that. Compression and memory efficiency is a throwback to my 8-bit days, but I don't program professionally these days, so I'm not up to speed with Java's foibles.

(I had the programming bug beaten and kicked out of me when I got talked into 15 months of utter hell working on this excrecence. I still quiver in fear at the very mention of the word "football".)

--
Sean Timarco Baggaley
Professional Grizzled Veteran

Stimarco did you work for SI? Thats who i wanted to work for when i was a student.... oooohhhhh the weeks and months lost to Champo!!

Comparing the P900 to typical mobile phones is like comparing a super computer to a standard PC!

P900 is a monster ! (and i'm getting one soon)

were getting about 11fps on a Siemens s55 and hope for 15+ fps on the Nokia phones so that will be ok for the game to be playable and enjoyable!

We are using an array to hold all the direction data for the AI to follow in everymap. The tiles are 32*32 (cause we can draw the screen faster that say using a 16*16 tiles for obvious reasons) but we hold the direction data for every 16*16 area on the map so we can have more detail for the AI to follow! The cars slide etc on corners so and we are adding a bit of randomness in so it will not have the on rails effect!

Thanks for the help mate!

Oh on the Amiga V phones speed chat..

Phones are running the Virtual Machine that the Java MIDlet runs in so there is another layer for the phone to look after so thats why it is slower etc. Plus all the extra checks for arrays that the Java language has etc etc make it slower that an App writen in C for the amiga. (i know very little about the amiga).

Brian