Here are some thoughts on the goals of an AI programmer, which should have gone at the beginning of this series. Let me put them up now before we go any further.
My first computer (which you can read about here) was the Tandy MC-10. 4k of memory. Less than a single megahertz of speed. Once I got my programming legs under me, the first thing I tried to do was
make a game clone Pac-Man. For reference, here is what the original looked like:
As a programmer, displaying something like that on the Tandy was about as likely as getting Crysis running on a 486. If I’d wanted to display my ghosts with the same level of detail, they would have needed to take up most of the screen. On the MC-10 the screen was 40 characters wide by 20 lines tall. It had a fixed character set. Character codes 0 through 127 were standard ASCII. 128 through 255 were a bunch of stupid shapes that were, in theory, for doing graphics but which didn’t really look very interesting and were more hassle than they were worth.
So my Pac-Maze ended up being made mostly of ASCII characters. Periods for dots. Asterisks for power pills. A solid block of pixels for the walls. I’ll bet a lot of thirty and forty-somethings out there authored something very, very similar. Here is a very close re-creation of what it looked like, according to my memories:
|The difference in maze layout is due to the fact that the original Pac-Maze can’t actually exist on a 40×20 grid. This was as close as I could come.|
Well, that was the platonic ideal anyway. In reality, the computer was hooked up to a television, and ended up looking more or less like this:
All those hours spent looking at my TV from sixteen inches away. Ouch.
Anyway, this was my first attempt at AI pathfinding. It ended in disaster, but I think it was an admirable effort for a junior-high school kid. I can still remember the rules that the ghosts used:
Each ghost can move in one of four directions. Note that “moving” here is not a smooth thing. The ghosts did not slide smoothly around the board like they did in the arcade. They could only occupy one of the given character positions. And so they blinked around, hopping from one dot to the next like pieces on a chess board. A single turn would take a full second. Imagine counting one Mississippi, two Mississippi, etc. That’s how long it took poor Pac-man to jump from one dot to the next. (The game ran much smoother without the dot-eating sound effect, but I couldn’t give that up!)
Originally, they all ranked each direction the same. (That is, they would consider moving up before they considered moving left.) But this uniformity of rules led to uniformity of behavior. If two ghosts ever got close to each other, they would keep making the same decisions and thus move together. Eventually the whole gang would pile up and it was pretty much like running from one ghost for the rest of the board.
If I wanted different behavior, I needed different rules for each ghost. I made it so that each had their own order in which they “preferred” each of these directions. So, ghost #1 might rank the four directions:
That is, if given a choice between going down or left, it will prefer down more than left, left more than right, etc. Another might prefer:
Two ghosts preferred vertical movement first, the other two preferred horizontal movement first. The rules they used were:
1) Can’t pass through walls.
2) You may NEVER reverse direction.
3) You MUST move.
4) Check your direction priority, and see if you can move TOWARDS the player without violating rules 1 through 3.
5) If you can’t move towards the player, just select the highest-rated direction that doesn’t violate rule 1 through 3.
The upshot of these rules was that if you removed the player from the game entirely, the ghosts would fan out, each heading to a different corner. They would then run in circles around the wall in that corner forever. Two would go clockwise around their little wall, the other two would go un-clockwise. This was really cool. Diverse behavior! I was so proud of myself.
But if the player was in the game, the ghosts would fan out and envelop poor Pac-Man from all sides within seconds. The game was essentially impossible. I discovered that “interesting” behavior was not the same thing as “efficient” behavior, and that “interesting” was way harder.
My solution was to slow them down. Ghosts only got to move half as often as the player, which meant you could escape their grasp. It was still much harder than the arcade, and a lot less interesting. You could stay alive if you stayed near the middle of the board where you had lots of options, but it was fatal to go after the dots in the corners because they would manage to cover all of your escape routes before you could get back out. If I made them move one-third the speed of the player, it became too easy. You could ditch them on one side of the board and go work on the other. They were a constant nuisance, but they weren’t a threat and they were always moving towards you. (They sort of “camped” the middle, which made dots close to the center almost impossible to grab. Not that “camping” was part of anyone’s gaming vocabulary yet.) I began to gain an appreciation for just how much thought had gone into the original game. It was easy to make the game either effortless or impossible, and the designer managed to find the precise balance between the two, a narrow band of behaviors that could be labeled as “fun”.
Sometimes AI is used to make the game seem less smart by making it miss more, ignore you at the right time, or as with my example above, chase you less efficiently. Sometimes AI is used to make the game “smarter”. So the goal of AI is not to simply increase intelligence. And it’s not to make the computer opponents more efficient. The goal of AI is to make the computer an interesting opponent.
It turns out that this is a complete pain in the ass.
Do It Again, Stupid
One of the highest-rated games of all time has some of the least interesting gameplay.
Fixing Match 3
For one of the most popular casual games in existence, Match 3 is actually really broken. Until one developer fixed it.
A video discussing Megatexture technology. Why we needed it, what it was supposed to do, and why it maybe didn't totally work.
What did web browsers look like 20 years ago, and what kind of crazy features did they have?
There are two major schools of thought about how you should write software. Here's what they are and why people argue about it.