Join us! Nintendo Enthusiast Forums
Flegma blog header photo
Flegma's c-blog
Fronts 3Posts 828Blogs 85Following 0Followers 19



Fledgling retrodev: AI and Data Reuse


Like I said in my previous blog on Bumper Ship Racing, my future blogs on that game won't focus on a single topic. This time, we have two topics: an unnecessarily fancy reuse of data for little practical purpose and how the AI in the game was implemented and created.

Reusing data as pseudorandom numbers

BSR was the first time I've run out of 16kB ROM space and had to use another 16kB memory page for the ROM. As such, compressing data became a necessity. Uncompressed, the visuals of the 22 tracks would've taken 22*32*20 bytes, that is, 14080 bytes. With run-of-the-mill Huffman coding, this was cut to about 5000 bytes. There would've still been room to compress the data further: run-length encoding would've probably also worked well.

This means that not every stone needed to be turned, and there are hundreds of bytes that could still be freed reasonably easily. And that's where some unnecessarily fancy code came to be.

Huffman coding works best when the dictionary isn't big and the fewer rare bytes are used, the better it compresses.

That in mind, I had alternative visual styles for three types of blocks. They are functionally identical, they just look a bit different to break up the monotony in the visuals. Throwing in some of these wouldn't help in the data compression, or with my Huffman decoder, which has certain limitations on what data it can handle.

 Tile variants circled.

While I wasn't hurting for extra ROM space yet, I didn't think writing the visuals in the data would be "cool" enough to do. Using a pseudo-RNG to choose which tiles to flip certainly was one option, I just would've had to have deterministic seeding for the generator to not have the track visually change every reload.

This would mean starting from the top-left corner's RAM address, produce a random positive integer and add that to the address, check if we're still within the map (starting address + 32 * 20 bytes), if we can change that tile, and then continue. This is procedural generation in a very limited sense.

Still not imaginative enough for me, though.

Time to do something even less imaginative and rip off from a legend, so to speak.

One of the memorable stories of Yar's Revenge (Howard Scott Warshaw/Atari, 1982) is that it renders the program code itself on screen. The "neutral zone" in the middle of the screen is actually the game's program code passed through some filters. You can hear the game dev himself, Howard Scott Warshaw, tell about it on a GDC classic game postmortem presentation (it's in the questions and answers section at the end of the video).

That's effectively what I chose to do. All I needed was a point in the ROM for byte data that was "random" and I could use those to replace the random numbers. Data that has little visible structure and high entropy. A bit like the Huffman-encoded level data, so that's what I used.

This wasn't perfect, though. To add more altered tiles per row, I limited the offset to be at most 32 (one full row on screen). The next problem is that this routine doesn't know and won't care where the previous tiles were set. As a result, it is very much possible to have vertically adjacent tiles flipped this way.

This was all probably a pointless endeavour for no appreciable benefit, because I still haven't checked how many bytes this would have saved; bytes that I still do not need.

AI for the racers

The original requirements for the AI weren't very well-defined. "It has to be fast to execute and prodive a good challenge" would be a verbose description of the goal.

How to create an AI that won't spend much time to deliberate? First off, ignore the other ships. The AI will need to be able to recover from hitting them anyway and bumping into others will fit well with the game's theme. The importance of bouncing right meant the AI couldn't just try and avoid walls but look ahead one or more turns -- something that would eat up precious cycles if done on the fly.

Hence, a static map would be the only input for the AI, and precomputing the AI's decisions in advance would involve least time spent pondering during the actual game. The AI would be defined in a tilemap, and each tile in that map would tell the desired X- and Y-velocities. If the ship didn't match those, then it would turn and apply thrusters to that goal.

This meant very little computation on the fly: check the ship coordinate, compare the difference between actual and desired velocities along the axes, permit a bit of variation and then decide which direction to turn to and whether to accelerate or not. No need for trigonometry. No need for any fancier geometry (after I limited the AI to want to turn in only eight directions rather than the full 16 the ships could have).

With that, the time side is well in hand. But then there's the size taken on ROM that needs to be within reason as well.

The AI map itself is reduced in accuracy compared to how the ships' positions are recorded. Each tile in the AI map is 2x2 track tiles. Furthermore, while the actual velocity is defined in two 16-bit variables, the AI map uses only two 8-bit variables. The bits that are compared are actually bits 4 to 11 in the velocity variable: four bits on both sides of the decimal point. And even that has too much room towards the top: the ships' speed is capped at four pixels per frame along each axis, and the value in the AI map can represent a speed up to 8 pixels per second.

This reduced the memory footprint of the stages to 12.5%, meaning the AI maps of all 22 tracks take (uncompressed) 7040 bytes. Compressed, the total would be just below 4000 bytes, but I didn't need to do this.

Defining a simple AI by hand is easy enough -- fill in a grid of 16 by 10 with numbers between 0 and 15, and use those as the target directions. Then just define a constant speed factor v to all entries and there you have it: the entries would be just pairs (cos(direction) * v, -sin(direction) * v). The additive inverse of sin is used because the origin is in the top-left corner and not the bottom-left while the directions increase in the counter-clockwise direction.

But how about getting the AI to be a good challenge and make it so that it can't get stuck in any corner? At this point, an optimization routine comes into play.

In short, I implemented the racing engine again with Python on PC (without graphics), and wrote a very simple optimization algorithm to do the actual work for me. The optimizer was a local search algorithm and instead of (dX, dY) pairs, it used (direction, velocity) search space.

The local search optimizer here can be described as "try to make little changes wherever one at a time, and keep only those changes that improved the solution at that time". This one never goes for a worse solution, even if there'd be a better solution to be found after making first a step for the worse.

The "small changes" were changing the direction by 22.5 degrees either way and slightly changing the velocity. The suggested direction changes were put all in a stack at the start, and whenever a change was approved, all the small changes for the adjacent tiles were returned to the stack if they had already been tested and removed. This meant that if a change in one corner of the track improved the AI, it would look for more improvements there.

Finally, there were three vehicles and three speed classes. This meant nine different vehicle configurations, none of which would be allowed to get stuck anywhere on any of the maps.

To avoid this, the optimization function was actually the total number of frames spent getting a complete lap finished from all non-blocked track tiles (not AI tiles!) with all vehicles. The end result is that the AI isn't optimal for any single ship.

Furthermore, and this is just a supposition because I haven't verified it, the slow racers have more weight than the fastest ones. Not only would a fast-moving ship speed through an AI tile quickly with less time to act on what they're supposed to do, but slowing down a fast-moving ship by one frame is an acceptable cost of speeding up a slower ship by two frames.

Something worth pointing out is that the laps do not (always) end the first time the finish line is crossed. The laps are tracked as they are in the game: there are two checkpoints before the finish line, and the ship has to pass the checkpoints in order. First checkpoint 1, then checkpoint 2, then finish line. If the ship starts between checkpoints 1 and 2, they should fly first through checkpoint 2, then the finish line and then do complete lap.

The big point here is that the optimizer doesn't ignore the approach speed and angle for a new lap. In this sense, the averaging over all the different starting positions took care of chaining laps in succession before I even thought about it.

The averaging effect for simultaneously optimising the AI for all ship types wasn't sufficiently strong, though. The AI became too good to play against on any speed class and any ship. This meant I had to dumb down the AI, again with the same script.

The ships still had to finish the lap, but ideally 50% slower than the optimal. This meant the optimisation target wasn't minimising the lap times but minimising the sum of absolute errors from the target lap time for each configuration and starting point. (In hindsight, I should've tried the sum of squares of errors instead.)

At this point, the next question is "how long did it take to teach the AI". With four processes running in parallel, I'd say finding the best AI took maybe a week in total on my PC. The optimiser itself wasn't very optimised either and there were many bugs in the optimiser that meant I had to redo the AI for all the levels (but using the previously optimised state as the starting point).

While I didn't keep track of how the AI evolved (plus the optimiser had several bugs I had to fix on the fly), I chose to optimise a single track from scratch for this blog.

This chart shows the total lap times as a progression of small changes tried out.

 In total, the AI spent in the end 28% fewer frames than at the start. The Y-axis is the total number of simulated frames needed (50 per second) for the AI-controlled ship to finish one lap starting from a standstill at all empty track tiles on all nine different vehicle configurations. This optimisation took about half a day to finish (and the velocities weren't even properly optimised).

And here is how the AI changed over four repetitions of the optimiser. The lines show the direction the AI ships attempt to fly in that tile.

 There's an obvious problem in the middle, though, where the lines point backwards; that's because of how the optimiser tried to solve the hangups in the hand-made AI (which was very poor there). But the AI apparently can still recover from there.

I'm not sure optimising the AI this way would've been feasible back in the 1980s. This took a large amount of processing power that wasn't commonly available at the time. Then again, I shouldn't underestimate the developers of that time and I don't know how the AI in similar games were actually implemented.

And next?

There's not much more I can write on the game that I haven't already said. One possible topic is describing the thought process that led me to the current campaign structure and how I designed the tracks; that is, on the game design choices.

Until the next installation of Fledgling retrodev, whenever that may be published.

EDIT 2019-01-06: Changed "bank" to "page" in an attempt to correct the terminology.

Login to vote this up!


bong264   21
Salador   17
Roager   7



Please login (or) make a quick account (free)
to view and post comments.

 Login with Twitter

 Login with Dtoid

Three day old threads are only visible to verified humans - this helps our small community management team stay on top of spam

Sorry for the extra step!


About Flegmaone of us since 11:34 PM on 01.17.2015

Very much unprofessional writer, don't take anything I write without a truckload of salt.

On a hopefully long-term break from saying anything.