Pixelate:Issue 10/Artificial Intelligence

From Allegro Wiki

Artificial Intelligence
Original author:	Niunio
Website:	http://www.burdjia.com
zip:

1. Introduction

Hi. I wrote the article 'Game objects with C++', in Pixelate #8. Now, I'll try to explain how to write artificial intelligence (AI) in games.

I must warn you: there are thousands of different allgorithms around AI. Here I'll explain the simplest and how to create AI systems by your own.

I'll assume you did your "homework": a description of the game, initial graphics (at least a paper and pencil design) and a simple flow chart (only to have an idea of how the program will work). Why you must to do this? Because each game is different, and each one has different needs.
So, with this "homework" you'll discover what are the way that AI must work.

(Mmmm... I've read this in other article, haven't you? ;^) ).

Note: About the examples; I must warn you that they are incomplete. If you want to use them in your programs you have to add several things, not only to the functions' code, but also some data.

2. AI basics: how the phantom can eat pac-mans.

The next can be the simplest AI system in the world. We can name it 'the look and follow' algorithm. If you remember the Pac-Man(TM) game, there are some phantoms trying to catch and 'eat' the pac-man. But how do it decide where to go? That's what I'll to explain.

The maze is built by a grid. Here, I'll use the '#' for a wall and the '.' for a blank.
i.e:

##############
 #.......#....#
 #####.#.#.##.#
 #...#........#
 ###...#.#.#.##
 #...#.#...#..#
 ##############

That's a nice maze! Now, we put the pac-man 'C' and a phantom 'A':

##############
 #....A..#....#
 #####.#.#.##.#
 #...#C.......#
 ###...#.#.#.##
 #...#.#...#..#
 ##############

In this case, obiously, the phantom must go down if he wants to catch the pac-man. Later, the pac-man is moved to the right and the phantom goes down:

##############
 #.......#....#
 #####.#.#.##.#
 #...#A..C....#
 ###...#.#.#.##
 #...#.#...#..#
 ##############

Of course, the phantom must go to the right now. All that can be coded as follow:

struct sprite {
   int x, y;
} phantom, pac_man;

void AI_phantom(void)
{
/* Go to catch the pac-man */
   if (phantom.x > pac_man.x) {
      phantom.x -= 1;
      return;
   }
   if (phantom.x < pac_man.x) {
      phantom.x += 1;
      return;
   }
   if (phantom.y > pac_man.y) {
      phantom.y -= 1;
      return;
   }
   if (phantom.y < pac_man.y) {
      phantom.y += 1;
      return;
   }
}

It must work. See the 'return' in each 'if' block. If you erase them then the phantom can go in diagonal! But I've forgotten one thing: the walls. In Pac-Man phantoms can't go through walls, so we must change our code:

char maze[14][7];

void AI_phantom(void)
{
/* Go to catch the pac-man */
   if (phantom.x > pac_man.x && maze[phantom.x-1][phantom.y]!=WALL) {
      phantom.x -= 1;
      return;
   }
   if (phantom.x < pac_man.x && maze[phantom.x+1][phantom.y]!=WALL) {
      phantom.x += 1;
      return;
   }
   if (phantom.y > pac_man.y && maze[phantom.x][phantom.y-1]!=WALL) {
      phantom.y -= 1;
      return;
   }
   if (phantom.y < pac_man.y && maze[phantom.x][phantom.y+1]!=WALL) {
      phantom.y += 1;
      return;
   }
}

See next:

##############
 #...A...#....#
 #####.#.#.##.#
 #...#...C....#
 ###...#.#.#.##
 #...#.#...#..#
 ##############

If you make a 'hand execute' of the AI_phantom() function you'll see how finally the phantom catches the pac-man. Great and simple, isn't it? But what if the game comes to the next situation?

##############
 #......C#....#
 #####.#.#.##.#
 #..A#........#
 ###...#.#.#.##
 #...#.#...#..#
 ##############

Try to execute the code. What happened? The phantom can't to move! Don't worry, just add some code:

void AI_phantom(void)
{
   int cnt;

/* Go to catch the pac-man */
   if (phantom.x > pac_man.x && maze[phantom.x-1][phantom.y]!=WALL) {
      phantom.x -= 1;
      return;
   }
   if (phantom.x < pac_man.x && maze[phantom.x+1][phantom.y]!=WALL) {
      phantom.x += 1;
      return;
   }
   if (phantom.y > pac_man.y && maze[phantom.x][phantom.y-1]!=WALL) {
      phantom.y -= 1;
      return;
   }
   if (phantom.y < pac_man.y && maze[phantom.x][phantom.y+1]!=WALL) {
      phantom.y += 1;
      return;
   }
/* The phantom can't follow the pac-man, so get a random move. */
   for (cnt=0; cnt<100; cnt++){
      switch (rand()%4){
      case 0:
         if (maze[phantom.x-1][phantom.y]!=WALL) {
            phantom.x -= 1;
            return;
         }
         break;
      case 1:
         if (maze[phantom.x+1][phantom.y]!=WALL) {
            phantom.x += 1;
            return;
         }
         break;
      case 2:
         if (maze[phantom.x][phantom.y-1]!=WALL) {
            phantom.y -= 1;
            return;
         }
         break;
      default:
         if (maze[phantom.x][phantom.y+1]!=WALL) {
           phantom.y += 1;
           return;
         }
         break;
      }
   }
}

Now the phantom will move everytime.

As you see, writing an AI system is quite simple. Just think what must be done in each case and write the code. Of course that 'look and follow' algorithm is most simple than the 'chess' one! 8^) But don't worry. I'll explain 2 other AI systems bellow.

3. State machines.

I'm sure you're read that expression sometime before. But what is a 'state machine'? Lets go to see it in an example.

In 'pac-man', when the pac-man eats an 'energy tablet', he gets 'power' and can eat the phantoms. So, we have now 2 states:

• state 'normal': phantoms eats pac-man
• state 'power-up': pac-man eats phantoms, so phantoms flees

That's a 'state machine'. Now, here you have one implementation of this state machine:

 struct sprite {
    int x, y;
 } phantom, pac_man;
 
 char maze[14][7];
 
 /* Defines the 'state machine' */
 #define STATE_NORMAL  0
 #define STATE_POWERUP 1
 
 int state = STATE_NORMAL;
 
 void AI_phantom(void)
 {
    int cnt;
 
 /* Check the 'state machine' */
    switch (state){
    case STATE_NORMAL: /* Go to catch the pac-man */
       if (phantom.x > pac_man.x && maze[phantom.x-1][phantom.y]!=WALL) {
          phantom.x -= 1;
          return;
       }
       if (phantom.x < pac_man.x && maze[phantom.x+1][phantom.y]!=WALL) {
          phantom.x += 1;
          return;
       }
       if (phantom.y > pac_man.y && maze[phantom.x][phantom.y-1]!=WALL) {
          phantom.y -= 1;
          return;
       }
       if (phantom.y < pac_man.y && maze[phantom.x][phantom.y+1]!=WALL) {
          phantom.y += 1;
          return;
       }
       break;
    case STATE_POWERUP: /* Flee */
       if (phantom.x > pac_man.x && maze[phantom.x+1][phantom.y]!=WALL) {
          phantom.x += 1;
          return;
       }
       if (phantom.x < pac_man.x && maze[phantom.x-1][phantom.y]!=WALL) {
          phantom.x -= 1;
          return;
       }
       if (phantom.y > pac_man.y && maze[phantom.x][phantom.y+1]!=WALL) {
          phantom.y += 1;
          return;
       }
       if (phantom.y < pac_man.y && maze[phantom.x][phantom.y-1]!=WALL) {
          phantom.y -= 1;
          return;
       }
       break;
    }
 /* The phantom can't follow the pac-man or flee from him, so get a random move. */
    for (cnt=0; cnt<500; cnt++){
       switch (rand()%4){
       case 0:
          if (maze[phantom.x-1][phantom.y]!=WALL) {
             phantom.x -= 1;
             return;
          }
          break;
       case 1:
          if (maze[phantom.x+1][phantom.y]!=WALL) {
             phantom.x += 1;
             return;
          }
          break;
       case 2:
          if (maze[phantom.x][phantom.y-1]!=WALL) {
             phantom.y -= 1;
             return;
          }
          break;
       default:
          if (maze[phantom.x][phantom.y+1]!=WALL) {
            phantom.y += 1;
            return;
          }
       }
    }
 }
 

The think you must keep in mind is that 'state machines' allows to divide one big AI problem in to a lot of small AI problems. And small problems are more easy to answer than big ones.

Example: if we're writing a chess game we can create a 'state machine' like that:

- STATE_START   while the game is on the first movements.
- STATE_ATTACK  when the computer have more [chess pieces] than the player.
- STATE_DEFENSE if the computer lost the queen, the horses... and player none.
- STATE_WARNING if the player can kill any strong piece of computer (queen, horse...)
- STATE_CHECK   if the player attacks the king.
- STATE_VOID    if the 2 players have similar pieces, kings aren't attacked...

So, the AI function must find what's the state of the game, looking danger pieces, future captures, etc. Then it calls one function for each state. And it can have 'state machines' inside each state.

In most of times, the 'state machine' is mixed with other algorithms.

Finally, do not abuse about it, some times it isn't the best way.

4. Beamed scale

The first time I meet this AI system was reading a book by Master Tim Hartnell, tittled 'The Giant Book of Computer Games'. But I didn't see it implemented until I found the game 'Marauder', by Master Shawn Hergreaves. You can find this game in his web site, at http://www.talula.demon.co.uk , complete sources included.

The idea of this system is that: each 'game element' and 'game goal' has a weight. So, the AI just checks each weight, looking for the biggest one, then takes the appropiate action.

Complex? I think... yes it's complex. I'll try to explain, in a simplified way, how 'Marauder' works.

The goal of 'Marauder' is to earn money, by interplanetary trade or being a space pirate.

The way used by aliens to decide what to do (trade or pirate) is checking the next:

- Distance and direction to a possible [buy trade planet].
- Distance and direction to a possible [sell trade planet].
- Distance to any 'weapon bullet', as laser, missile, mines...
- How many goods the alien's ship has.
- How many money the alien's ship has.

With that values, it calculates the weight of the next actions:

- Go to the nearest [buy trade planet] and buy goods.
- Go to the nearest [sell trade planet] and sell goods.
- Shoot to the nearest star-ship and try to stole his goods and money.
- Flee from a battle.

Example: The weight of 'Go to the nearest [sell trade planet] and sell goods' vary proportionately by the amount of goods it has but vary inversely by the distance of the planet.

When it has calculated all weights, it looks for the biggest one to decide what to do.

The problem of this AI system is what and how to weight, specially the related math formulae. What must weight more, the distance or the amount of goods? Each game and situation is different, and only the 'try and fail' and the experience can help.

5. Conclusion

There are a lot of AI systems, like Genetic Algorithms, Neural Networks, Fuzzy Logic and more. Anyway here are some hints to help you on your way:

- Practice creating games in many different ways and styles: strategy, action, simulation... Try with simple ones first and get some experience.

- Look the source code of every game you love (if you can obtain some). See how it works.

- Go to the public library and looks for books about AI or games. My recommendation is 'The Great Book of Computer Games' and 'Artificial Intelligence', both by Master Tim Hartnell. An advice: first look for old books with games, programs or examples written in GW-BASIC or LOGO, they're easier to read and understand than newer ones. I must persist about LOGO, because all books about this languaje has any chapter or example of AI, and also because LOGO is a very easy to understand and very powerful. Really.