Friday, December 16, 2011

Basic movement game AI

I really love to play video games, and for a while I’ve been wanting to learn a bit about video game programming mainly AI and physics.
I have just read the first 20 or so pages of the good book on AI Artificial Intelligence for Games

and I though I was going to try the first easy algorithms that are explained there. So here I will introduce a little bit of the simplest way to develop the seek and arrive algorithm.
I will develop the example in Ruby using the gosu library to draw some simple characters.

The idea of the seek algorithm we are going to implement is very easy, we will control a character in the screen and another computer controlled character will seek our character on the screen and destroy him when he arrives to our character.

So the first thing to know is what is involved in a very simple movement. In the example we will not consider acceleration forces so we will have what is known as Kinematic movement. We will need 3 variables to express the characters static data at moment in time. So we can start with a Ruby module like this:

  1. module Kinematic
  2.  attr_reader :velocity, :orientation, :position
  3. end
  4.  


where all three elements are vectors. The velocity vector will give us the direction and speed of the characters, the orientation vector, in our case will simply be oriented towards the direction, so it will be the velocity vector normalized, and the position is the place where our characters are.

The orientation will also be expressed as a angle in radians using the atan2(-x,y) formula, where y and x are the corresponding coordinates in the velocity vector.

So the position and orientation will be both a function of the velocity like this:
  1. orientation = velocity.normalize
  2. position = velocity * time


where time is a small unit of time that will be a function of the frame rate we have. When the frame rate is bigger, the update time is smaller. It is calculated in our case something like this:

Let’s suppose our character travels at 2 meters per second, and let the frame rate be 60fps in a particular moment. then our time multiplier will be 1/60 which multiplied by 2 will be 1/30 that will be the length of our vector to be summed to the position vector in each frame. However we will change the value and adjusted to some value that makes the movement look good.

Ok so that is the basic movement, but now we need to implement the seek behaviour. The AI character will need to chase our own character in the screen, in the algorithm terminology we’ll be the target of the seek and arrive algorithm. So logically for implementing this algorithm we need both the character and the target kinematic data. We also need to specify a radius of contact (where the character catches the target) and a speed for our velocity vector.

So to our module we add this max_speed

  1. module Kinematic
  2.  attr_reader :velocity, :orientation, :position, :max_speed
  3. end


We create now two classes that include this module

  1. class Target
  2.  include Kinematic
  3. end
  4.  
  5. class Character
  6.  include Kinematic
  7. end


Both character and target include the module, but only the character will be AI controlled, the target will be controlled by ourselves.

So we will create the seek_and_arrive algorithm on the character, in a method that receives the character it is chasing.

First the seek part will be simply to create a velocity of speed ‘max_speed’ and direction pointing to the target’s position. Now for the arrive part we will use a ’radius of impact’ that determines when the character has actually reached the target. We will include this radius as information on the target character. So modifying the algorithm we now have:

  1. def seek_and_arrive(target)
  2.   @position += @velocity * @time_update
  3.   @velocity =  target.position - position
  4.   if  @velocity.magnitude < target.radius
  5.  EventHandler::add_event(:capture,self,target)
  6. end
  7. @velocity = @velocity.normalize
  8. @velocity *= @max_speed
  9. @orientation = @velocity.normalize
  10. end


As we see we are simply adding a condition and then sending an event saying that the target has been captured by the character. This event will be handled in the main loop of the game where it will show Game Over.

We will now create the graphics for the game with Gosu, I won’t explain much here as it is not the focus of the post.

The first thing, we create a character wrapper for our characters that will know about gosu, that way our original class remains graphics framework independent:

  1. class DrawableCharacter
  2.  attr_reader :character
  3.  def initialize(character,window,character_img)
  4.     @image = Gosu::Image.new(window, character_img, false)
  5.     @character = character
  6.  end
  7.  
  8.  def draw
  9.     @image.draw_rot(@character.position[0], @character.position[1], 1, @character.orientation_in_radians)
  10.  end
  11. end


then we create a class for the controlled character and one for the AI Character:

  1. class ControllableCharacter < DrawableCharacter
  2.  def move(side)
  3.     @character.move_ahead if side==:front
  4.     change_velocity_according_to_side(side)
  5.  end
  6.  
  7.  def change_velocity_according_to_side(side)
  8.     return if side == :front
  9.     if side == :right
  10.      sin_radians = Math::sin 0.1
  11.      cos_radians = Math::cos 0.1
  12.     else
  13.     sin_radians = Math::sin -0.1
  14.     cos_radians = Math::cos -0.1
  15.     end
  16.     velocity_x = @character.velocity[0]*cos_radians - @character.velocity[1]*sin_radians
  17.     velocity_y = @character.velocity[0]*sin_radians + @character.velocity[1]*cos_radians
  18.     @character.velocity = Vector[velocity_x,velocity_y]
  19.     @character.velocity = @character.velocity.normalize * (@character.max_speed+1)
  20.  end
  21. end
  22.  
  23. class AICharacter < DrawableCharacter
  24.  def seek_and_arrive(target)
  25.     @character.seek_and_arrive(target)
  26.  end
  27. end


The Controllable character will move depending on input from the keyboard that is captured on the main Game class. The AICharacter delagates its movement to the Character class that contains the seek_and_arrive algorithm.

Now the main Game class:

  1. class Game < Gosu::Window
  2.  
  3.  def initialize
  4.     super 1024, 768, false
  5.     self.caption = "Seek and Arrive"
  6.     @target = ControllableCharacter.new(Target.new(10, 10), self, 'target.gif')
  7.     @character1 = AICharacter.new(Character.new(500, 500), self, 'character.gif')
  8.     @game_state = :game_started
  9.  end
  10.  
  11.  def manage_ai_characters
  12.     @character1.seek_and_arrive(@target.character)
  13.  end
  14.  
  15.  def manage_controllable_character
  16.     if button_down? Gosu::KbLeft or button_down? Gosu::GpLeft then
  17.      @target.move :left
  18.     end
  19.     if button_down? Gosu::KbRight or button_down? Gosu::GpRight then
  20.      @target.move :right
  21.     end
  22.     if button_down? Gosu::KbUp or button_down? Gosu::GpButton0 then
  23.      @target.move :front
  24.     end
  25.  end
  26.  
  27.  def manage_events
  28.     EventHandler::each do |event|
  29.      if event[0]==:capture
  30.        @game_state = :game_over
  31.      end
  32.     end
  33.  end
  34.  
  35.  def update
  36.     manage_events
  37.     if @game_state != :game_over
  38.      manage_ai_characters()
  39.      manage_controllable_character()
  40.     end
  41.  end
  42.  
  43.  def draw
  44.     if @game_state != :game_over
  45.      @target.draw
  46.      @character1.draw
  47.     else
  48.      Gosu::Image.new(self, "game_over.gif", true).draw(0, 0, 0);
  49.     end
  50.  end
  51. end
  52.  
  53. window = Game.new
  54. window.show
The main details to get out from this code are the ‘update’ and ‘draw’ methods. The update method is called 60 times per second by default, and then the show method is called.

The full source code of the example is in github, just download and run the game.rb ruby file.

Of course this introduction is the simplest of the simplest in Game AI, but it is important information to have and very entertaining to learn.

Also of course there are libraries and frameworks that do most of the work for us, but I did this example (and hopefully some following ones) to learn the basics of how it works.