How to Design Human-Feeling AI

Whether you like it or not, life, the universe, you, and your loved ones can be quantified into a very large series of 0’s and 1’s, on’s and off’s, true’s and false’s.  This may sound bleak and a bit nihilistic, but I actually think it is quite beautiful.  Sometimes, I’ll walk down to the river and look at something–some thing or some system of things–and think about what “if-then” statements make that thing operate how it does.  The same analysis can be applied to creating compelling and seemingly human artificial intelligence in video games.

To put into context where this is going, I am working on a local-multiplayer side scrolling deathmatch game called ChargeShot.  We recently both got ChargeShot greenlit on Steam and showcased it at the Indiecade @ E3 booth last week.  The response was overwhelmingly positive, but the question kept coming up: Is there going to be single player?  ChargeShot was designed around the fact that it would be local-mulitplayer only, but I simply cannot conjure up a viable reason to deny those who buy the game the ability to at least try it out if they  bought it with no friends around.

So I started making bots.  At first, the idea scared me.  I’ve hardly done AI.  What if the bots are clunky and weird?  What if they are too stupid or two smart?  What if the single player is so bad that it brings down the entire perceived quality of a primarily multiplayer-centric game?

But I got to work, and within a day, came up with something I was proud of.  ChargeShot is a very human game.  The controls are very weighty; simple, but difficult to master.  Really good players can lose a round through an unperceived threat or a simple mistake.  I came up with a method to create something that feels as though it is being controlled by a real world human being. Basically, the process goes like this:

  • Make a huge list of every instant that a human player would press a button.
  • Categorize these by the goal of pressing the button (in example, press “Up”, “Left”, and “Right” to pursue another player).
  • Feed the AI these goals and make them push buttons on a virtual controller rather than behaving on a contrived pattern.

 

In my case, I calculate a path from the bot to the bot’s target, which is a dynamic reference that changes based on a few rules.  Which potential target is closer?  Is a player close to winning or does he pose a great threat?  Then, rather than simply moving the bot along the path to the target, I have it input buttons to reach the next cell on the path to the target.  Because the game has a lot of weight and acceleration, sometimes this destination is overshot, and in real time the path updates.  On top of that, the target may be moving, so the path has to adjust for that, too.  This creates a relatively nice navigation system.  The AI behaves perfectly imperfect to reach its goal, much like a human player would. But that’s only navigating.  What about competing?  ChargeShot is a game about shooting and reflecting bullets with a momentary shield.  After input is pressed, a separate set of rules with the goal of killing one another and staying alive are fed to the brain of the bot.

Q: When does a human player press the shoot button?
A: When there is another player in his line of sight and nothing obstructing the shot.

Q: When does a human player press the shield button?
A: Either when he recognizes a bullet coming his way, or when he is on top of another player (in order to “bump” the player away).

The shots in ChargeShot have an immense amount of kickback, so doing this alters the path to the target.  The shield temporarily disables the jetpack, causing the player to lose upward velocity, which causes the path to change.  Being “shield bumped” sends you flying across the screen, which, again, adds dynamics to the positions of both the bot and the target pathfinding destination. Finally, so that the bots aren’t perfect in their reactions, a reaction time variable is used to determine how quickly they make decisions.  Rather than have this be a fixed time, to make things a bit more interesting, I use a percentage.  A perfect bot reacts exactly at the times that stimuli are processed.  A high-functioning bot has a 80% chance per frame (at 60 fps) to react to the stimulus.  A low-functioning bot may have a 40% chance per frame to process the stimulus.  What this does is make it so that if you pin 2 bots with the same reaction time together, they won’t behave identically.  They have a much higher chance of reacting in time, therefore, statistically, they will react in time.  People may argue the whole RNG is bad thing, but this is actually how human reaction time works too.  You don’t always, every time, react at 20ms delay.  Not even pro players.  

(Below: what happens if two bots have identical reaction times)

 

The “still left to do” list includes stacking rules on top of rules.  Finding more of those “When do players do ‘x'” things and applying them.  Avoid level hazards, when the wind picks up on a particular left, press in the opposite direction to fight it, never try to navigate through lava, etc.

In conclusion, convincing AI isn’t to difficult if you are willing and able to take the time to think about the rules by which human beings operate a video game.  AI that is supposed to represent human play is not objective, it is very very subjective.  Regardless of how much to win, you know that in order to win you have to do this at that time.  Bot AI should reflect that, not a murderous desire to hunt down the player.  Virtual Controllers bro, get on it.

-C

Instrinsic Value in Game Design (and How to Identify it)

     I recently engaged in an argument on a car ride home about the meaning of the game, Journey, that got me thinking about what it is that defines artistic purpose, particularly in video games. While this analysis primarily focuses on games, its intention is to help critics better understand what components together create both the contrived and inherent value of any given work of art. For long and forever, the argument of subjective versus objective meaning in art analysis has raged on and will continue to rage on. I’m writing today, not to deny either one’s credibility, but to comment on the fact that neither objective nor subjective understanding of a piece of art is necessarily the truth of meaning in that work of art.

     Truth. That is a heavy word. As soon as you pull out the truth card, people get heated. Truth, by definition, is that which is true, or in accordance with fact or reality. The reason that I define this so early on is to separate it from the word “belief”. In this essay, at least, a belief can be the truth, but the truth is not a held belief. When I use “truth” throughout the rest of this writing, I am using it to define things that are separate from individual beliefs and are factual and logically sound. It is important to make this distinction while engaging in debate or literary criticism in that it separates the writer of a piece of critique from the piece that she is critiquing.

      Subjective arguments on the meaning of a piece usually go as such: a belief about the intrinsic meaning of a work of art is stated, the second party rebuts with her individual belief about the meaning, and the debate (hopefully) continues with one party or the other giving evidence about why her view is justified, and where the other’s view is flawed, usually on the basis of another subjective understanding. It is important to understand that while these arguments use a logical system to support themselves, the evidence supporting them are subjective as well, and therefore cannot be held as fact—that is the definition of “subjective” argument—however, these arguments are healthy in order to build a better understanding between the two parties of what other critics’ subjective understandings might be. The product of arguing the subjective value of a work of art, I will refer to as, the “omni-subjective understanding”, where over time, enough of these arguments are held and the majority of viewers come to a common middle ground as to what a piece of art means.

      Objective arguments on the other hand, hopefully ensue in this manner: the first party states his stance, the second states hers, the first provides logical and factual evidence that supports his argument, the second does the same, both are called out on logical errors that they make in their claims, until the ultimate objective truth is obtained. This is the basis for practical decision making. However, the meaning of a work of art is where this gets obfuscated. Can one actually logically support the intrinsic value of a work of art? Usually the objective argument will cite the author’s intent in a work of art, because the creator of a work knows what he meant to convey. But what if the perception of a piece of art is different than the author’s intent? Because people perceive an intangible something, does that mean that that something exists?

      In short, yes and no. At this point, I am going to provide a list of truths about the meaning of a work of art, then, through example, I will explain how this list is useful in identifying intrinsic meaning.


  1. An artist meant to convey a message.

  2. The viewer perceived a message.

  3. In the piece of art’s universe, the artist’s intended message is the truth.

  4. The viewer’s perception of a message will be obfuscated by the conditions under which he perceives it.

  5. The intrinsic message of a work of art is not necessarily either the author’s intended message, or the viewer’s interpretation of the message, nor is it unable to be both.

  6. A work of art has a will, separate of both the creator’s will and the will of the body of individuals who interpret it.

 


 

      I will start by providing a very simplified example, one with no ambiguous moral lesson, to help bring to light the utility of these truths above; the ages old example of Pac-Man. Numeric footnote flags will refer to the list of truths above.

      In the Pac-Man world, if there is such a thing, there is a legend that the creators conceived Pac-Man as a pizza with a slice missing. For the sake of simplicity, we are going to assume that that is true. So the artist meant to convey the avatar of Pac-Man as something vaguely resembling a pizza.(1) The viewer, because of seeing the art on the side of the American cabinet, which represents Pac-Man as a sphere with Pac-Man shaped eyes(4), has a different understanding of Pac-Man as an avatar.(2) If the creator, in the fiction of his game’s universe, intended for Pac-Man to actually be a pizza, then Pac-Man is in fact, a pizza.(3) However, Pac-Man is neither a pizza, nor a sphere with legs, he is a little yellow circle who eats dots.(5) Just because both parties assigned a different value to what Pac-Man is supposed to represent, doesn’t change the fact about what Pac-Man is.(6)

     As you see, there are several truths about Pac-Man. The artists had an image they wanted to convey, the viewers perceived it differently because of the situation under which they were perceiving it, both views were had, therefore it is true that both parties perceived something. In the fiction of the game world, if the creator of the universe says that Pac-Man is a pizza, however much we disagree, that is the truth—but only in the game’s universe. Aside from that, the truth about what Pac-Man really is, has nothing to do with either what the creator wanted him to resemble, nor what the omni-subjective perception of him is. Pac-Man as a work of art, has a will to convey to you a little yellow circle on a black background, and that will, mostly due to technical restrictions, is in place to allow both objective and subjective debate over what Pac-Man is, despite that the argument is not about what Pac-Man is, but what he represents. That, is the truth.

      Back to the Journey debate I was having in the car. We were talking about the point of Journey. I said that I had watched a particularly sad Let’s Play of the game, where the player never even ran into another player, despite being online, and would never get to experience what the game was truly about. One of the people in the car responded with, “Well I’ve played the game several times, and I enjoy it just as much single player.” The debate escalated to trying to understand what the message of Journey was. Their stance was that Journey was enjoyable single player because it represented the “hero’s journey” trope in literature. My stance was that the game, in its design, was to convey the joy and wonder that was sharing your journey with other people. Both are subjectively true. We both understood Journey through different contexts, and both assigned meaning because of that.

      But then, I was told that I couldn’t possibly know what the meaning of the game was because I didn’t create it and that I was speaking as if I had personally created it. It became a fight. Instead of arguing my subjective understanding of the game, I began to argue the correct way to critique a piece of art. I was told I was defending myself, but the reason I stood my ground for the hour long car ride was that I was defending the integrity of art as a whole.

      It is okay to argue your subjective understanding of a piece of art. You want people to feel the things you feel, relate to the things you relate to, speak on a more spiritual level. You want life to be Journey. Everybody perceives a message, therefore that a message was perceived is fact. When the argument spills over into trying to compare subjective delight about a work of art, to what the creator meant by it, the logical integrity of the argument is decimated. Even worse than that is assuming that the objective, creator’s vision, of a work of art is what the art represents. But the most destructive thing that anyone can do to the idea of art as a whole, is deny the fact that aside from the way that we all perceive it, aside from what the artist meant to say, and aside from the situations under which it was created and played, a video game has life breathed into it, and because of that, it has its own meaning that is neither objective nor subjective, nor is it both.

     A work of art—a video game—operates under the assumption that people will assign values and beliefs to it that it personally does not deliver. Despite that, because it exists, it delivers something; something that neither the artist nor the viewer meant for it to convey. It has a factual, intrinsic value, that people make more complex than it is.

     Pac-Man is a game about a little yellow circle dodging ghosts and eating pellets, Zelda is a game about about exploration and acquiring the things you need to defeat evil, and Journey is a game about accidentally either communicating with other people, or not, during an isolated pilgrimage. These are the intrinsic facts about these games, intentional or not, perceived or perceived differently, and that is the truth.

 -C

Fictional Language – Part 1 – Grammatical Structure

I, by no means, identify as a programmer.  I am not smart enough to consider myself a programmer.  Yes, I do the programming for our games, but aside from making things work and feel good, I have virtually no interest in programming.  That being said, what am I?  I am a logical thinker, I love mathematics and physics, and at the same time, I have a creative and abstract understanding of beauty.  The romantics would say, “That it is beautiful is its reason to be,” while the mathematicians may say, “The reason that it is beautiful is that it is.”  I am somewhere else.  I say that the reason something is beautiful is that it operates by a set of rules that we to which we can relate, yet is so profound in having been so simple.

Why the preface on beauty to an article titled “Fictional Language”?  Because language is beautiful.  Communication operates by a series of rules that, at their core, are nearly universal across languages.  When you attempt to communicate with someone who does not speak your language–and you do not speak theirs–there is somewhat of an understanding of what they mean to say.  Usually, this is accented by means of body language and gestures, plus simplified speech.  The simpler the rules, the easier it is to communicate.

Over the next couple of weeks, I am going to be outlining the process of creating an entirely new spoken language for use in video game fiction.  Tolkien created Elvish, as I will be creating Galaga, a language to be used across our joined video game fiction, starting with ChargeShot.

First on the agenda, is defining our grammatical structure.

Continue reading

Bitwise Auto-tiling in Game Maker

So I was fooling around with auto-tiling objects, and went through the long process of comparing neighbors through a series of if statements.  It was a lot of freakin work, but in the end I came up with something that did the job.

autotile1

As you can kinda see, the borders around the tiles adjust themselves based on the surrounding tiles.  Because the project I’m using this for involves destructible terrain, the neighbors above, below, to the left and right are all calculated per step.  While that is all well-to-do when there are only 50 or so blocks in the room, once more and more are added, the amount of collision checking per step is atrocious,  and slows down the frame rate severely, not to mention the amount of body work with all of the ifs and thens.

Then, I happened upon a wonderful way to use binary operations to remove the spaghetti that was a series of if’s.

In the step event of an auto-tiled object, set a variable count to zero and do four place_meeting checks (one in each direction) and store the returned Booleans in a couple variables:

var count = 0;
nUp = place_meeting(x,y-1,obj_autotile);
nDown = place_meeting(x,y+1,obj_autotile);
nRight = place_meeting(x+1,y,obj_autotile);
nLeft = place_meeting(x-1,y,obj_autotile);

Now comes the cool stuff!  Take a look at the diagram below.  The pink square with “TILE” written in it represents the instance of an object calculating these collisions.  Moving from the top, clockwise around it, are numbers that double the last.

autotile2If another tile is meeting our current tile directly above it, we will add “1” to our count.  If one is meeting to the right, add “2”, if below, add “4”, and if to the left, add “8”.
Because each number is double the previous number, and the numbers can only be added once, there is only one way to have our count equal any particular number from 0 to 15.  For example, the only way to make the number 5 in this method is to add the 1 from above and the 4 from below, so we know that image number 5 has to be the tile that is drawn when only a tile above and tile below are meeting our object. Therefore, by adding these numbers based on the collisions that we declared previously, we can determine 16 unique tiles to draw by using five simple lines of code:

if(nUp) count += 1;
if(nRight) count += 2;
if(
nDown) count += 4;
if(nLeft) count += 8;
image_index = count;

The most arduous part of this process is determining exactly which tile corresponds with which count number.  Luckily, since I went through the process already, I’ve made a diagram:

spr_terrain_strip16

This diagram shows which border tile corresponds with which image_index if you use the method above.

On to the other problem, and one that I know everybody has concerning auto-tiling, optimization for real-time auto-tiles.

So with our auto-tiling set up using binary operations, that cuts back on a lot of thinking that the game has to do per frame, but it is still inefficient because it each object has to calculate four collisions each, then determine which image it should display, (assuming the room speed is 60) 60 times per second.  If you have 50 auto-tiling objects, that is 
50*4*60 =
12,000 collision checks per second.

oops.

The solution I came up with is to only update the tiles when a change has been made to the map!  Why should we need to collision check over and over again if nothing has changed?  While this isn’t the most efficient because even unaffected tiles will update themselves if a change to the map has been made elsewhere, it is a simple and more efficient solution than running a four collision checks per object per step.

In the create event of our object, initialize a variable “tile_count” or something of the like:

tile_count = 0;

Then, in our step event, before calculating the collisions, compare this variable to the number of tile-able instances that currently exists, and if tile_count is equal to that number, simply exit the code!

if (tile_count == instance_number(obj_autotile)) exit;
//then your collision stuff

So essentially, on the first step, because we initialized tile_count to be 0, tile_count will not equal the instance_number and will proceed through the code and auto-tile.
Now, after your auto-tile stuff, we also have to update our variable tile_count to equal the instance_number so that way it will not keep looping through the code.

//collisions and autotile stuff
tile_count = instance_number(obj_autotile);

This makes it so that on the next step, the part we put at the beginning of the step will flag “true” and the code will exit itself before doing collision checks and auto-tiling, because nothing has happened.

If the amount of instances changes, either more are added or some are destroyed, the remaining instances’ tile_count will no longer equal instance_number because instance_number has changed, and they will all loop through their auto-tile code once, before tile_count is set to be equal to the new instance_number!

Pretty nifty, eh?

The complete step event should look something like this:


if (tile_count == instance_number(obj_autotile)) exit;

var count = 0;
nUp = place_meeting(x,y-1,obj_autotile);
nDown = place_meeting(x,y+1,obj_autotile);
nRight = place_meeting(x+1,y,obj_autotile);
nLeft = place_meeting(x-1,y,obj_autotile);

if(nUp) count += 1;
if(nRight) count += 2;
if(nDown) count += 4;
if(nLeft) count += 8;
image_index = count;

tile_count = instance_number(obj_autotile);


-Cullen (Coyote) @cullenddwyer

ChargeShot Update #1

Britt Brady and I have been working very hard to bring to you ChargeShota couch-sitting mulitplayer death arena game about space bounty hunters.

ChargeShot started as a Ludum Dare submission, and Britt’s first solo developed game.  I had recently moved into town and connected with the Eugene Area Game Developer’s Facebook page right in time for the compo.  Britt’s entry, ChargeShot, was by far the most fun I had on any LD entry, ever.  (You can play it here).

Britt, at the same time, thought my Ludum Dare submission, “Ludum Bark Beams“, was awesome, so we got to talking.  He had just gotten an OUYA and was thinking about starting a project that he could publish on the microconsole.

“Why not ChargeShot?” I said.

I had a little more experience with the technical side of things, and told him I could probably get the game working on Android.  Then…I opened his Game Maker file.  It was his first ever game, it was made in 48 hours, and it was a mess.  So I told him I would rewrite it from scratch for him, exactly as it was, but cleaner and more manageable.

Then, magic stuff happened.  I asked him for a different shield graphic, I made a slight change to how friction works, I jokingly implemented a Super Smash Bros. style camera that I was working on, when all of a sudden, the game became a full-sized project rather than a one-level deathmatch.  New graphics, modular player select screens, lots of levels!  And in about a month of working on this thing for one whole day a week, it had become something special.

We plan to release ChargeShot on OUYA and PC around mid-Summer.