 <\/td><\/tr><\/table><\/p>\nAll those hours spent looking at my TV from sixteen inches away. Ouch. <\/p>\n 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:<\/p>\n 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!) <\/p>\n 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.<\/p>\n 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:<\/p>\n 1) Up
\n2) Down
\n3) Left
\n4) Right<\/p>\n 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:<\/p>\n 1) Right
\n2) Left
\n3) Up
\n4) Down<\/p>\n Two ghosts preferred vertical movement first, the other two preferred horizontal movement first. The rules they used were:<\/p>\n 1) Can’t pass through walls.
\n2) You may NEVER reverse direction.
\n3) You MUST move.
\n4) Check your direction priority, and see if you can move TOWARDS the player without violating rules 1 through 3.
\n5) If you can’t move towards the player, just select the highest-rated direction that doesn’t violate rule 1 through 3.<\/p>\n 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.<\/p>\n 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.<\/p>\n 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”.<\/p>\n 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<\/em> opponent. <\/p>\nIt turns out that this is a complete pain in the ass.<\/p>\n","protected":false},"excerpt":{"rendered":" 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. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"class_list":["post-4496","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/4496","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4496"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/4496\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4496"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4496"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4496"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}} |
<\/a><\/td><\/tr>
<\/td><\/tr>