Creating Artificial Intelligence

Artificial Intelligence is a subject so vast that we will barely scratch the surface. AI in Video Games is usually heavily simplified and therefore easier to implement.

There is this wonderful series of articles called Designing Artificial Intelligence for Games that I highly recommend reading to get a feeling how game AI should be done. We will be continuing our work on top of what we already have, example code for this chapter will be in 08-ai.

Designing AI Using Finite State Machine

Non player tanks in our game will be lone rangers, hunting everything that moves while trying to survive. We will use Finite State Machine to implement tank behavior.

First, we need to think “what would a tank do?” How about this scenario:

  1. Tank wanders around, minding it’s own business.
  2. Tank encounters another tank. It then starts doing evasive moves and tries hitting the enemy.
  3. Enemy took some damage and started driving away. Tank starts chasing the enemy trying to finish it.
  4. Another tank appears and fires a couple of accurate shots, dealing serious damage. Our tank starts running away, because if it kept receiving damage at such rate, it would die very soon.
  5. Tank keeps fleeing and looking for safety until it gets cornered or the opponent looks damaged too. Then tank goes into it’s final battle.

We can now draw a Finite State Machine using this scenario:

Vigilante Tank FSM

Vigilante Tank FSM

If you are on a path to become a game developer, FSM should not stand for Flying Spaghetti Monster for you anymore.

Implementing AI Vision

To make opponents realistic, we have to give them senses. Let’s create a class for that:

08-ai/entities/components/ai/vision.rb

 1 class AiVision
 2   CACHE_TIMEOUT = 500
 3   attr_reader :in_sight
 4 
 5   def initialize(viewer, object_pool, distance)
 6     @viewer = viewer
 7     @object_pool = object_pool
 8     @distance = distance
 9   end
10 
11   def update
12     @in_sight = @object_pool.nearby(@viewer, @distance)
13   end
14 
15   def closest_tank
16     now = Gosu.milliseconds
17     @closest_tank = nil
18     if now - (@cache_updated_at ||= 0) > CACHE_TIMEOUT
19       @closest_tank = nil
20       @cache_updated_at = now
21     end
22     @closest_tank ||= find_closest_tank
23   end
24 
25   private
26 
27   def find_closest_tank
28     @in_sight.select do |o|
29       o.class == Tank && !o.health.dead?
30     end.sort do |a, b|
31       x, y = @viewer.x, @viewer.y
32       d1 = Utils.distance_between(x, y, a.x, a.y)
33       d2 = Utils.distance_between(x, y, b.x, b.y)
34       d1 <=> d2
35     end.first
36   end
37 end

It uses ObjectPool to put nearby objects in sight, and gets a short term focus on one closest tank. Closest tank is cached for 500 milliseconds for two reasons:

  1. Performance. Uncached version would do Array#select and Array#sort 60 times per second, now it will do 2 times.
  2. Focus. When you choose a target, you should keep it a little longer. This should also avoid “jitters”, when tank would shake between two nearby targets that are within same distance.

Controlling Tank Gun

After we made AiVision, we can now use it to automatically aim and shoot at closest tank. It should work like this:

  1. Every instance of the gun has it’s own unique combination of speed, accuracy and aggressiveness.
  2. Gun will automatically target closest tank in sight.
  3. If no other tank is in sight, gun will target in same direction as tank’s body.
  4. If other tank is aimed at and within shooting distance, gun will make a decision once in a while whether it should shoot or not, based on aggressiveness level. Aggressive tanks will be trigger happy all the time, while less aggressive ones will make small random pauses between shots.
  5. Gun will have a “desired” angle that it will be automatically adjusting to, according to it’s speed.

Here is the implementation:

08-ai/entities/components/ai/gun.rb

  1 class AiGun
  2   DECISION_DELAY = 1000
  3   attr_reader :target, :desired_gun_angle
  4 
  5   def initialize(object, vision)
  6     @object = object
  7     @vision = vision
  8     @desired_gun_angle = rand(0..360)
  9     @retarget_speed = rand(1..5)
 10     @accuracy = rand(0..10)
 11     @aggressiveness = rand(1..5)
 12   end
 13 
 14   def adjust_angle
 15     adjust_desired_angle
 16     adjust_gun_angle
 17   end
 18 
 19   def update
 20     if @vision.in_sight.any?
 21       if @vision.closest_tank != @target
 22         change_target(@vision.closest_tank)
 23       end
 24     else
 25       @target = nil
 26     end
 27 
 28     if @target
 29       if (0..10 - rand(0..@accuracy)).include?(
 30         (@desired_gun_angle - @object.gun_angle).abs.round)
 31         distance = distance_to_target
 32         if distance - 50 <= BulletPhysics::MAX_DIST
 33           target_x, target_y = Utils.point_at_distance(
 34             @object.x, @object.y, @object.gun_angle,
 35             distance + 10 - rand(0..@accuracy))
 36           if can_make_new_decision? && @object.can_shoot? &&
 37               should_shoot?
 38             @object.shoot(target_x, target_y)
 39           end
 40         end
 41       end
 42     end
 43   end
 44 
 45   def distance_to_target
 46     Utils.distance_between(
 47       @object.x, @object.y, @target.x, @target.y)
 48   end
 49 
 50 
 51   def should_shoot?
 52     rand * @aggressiveness > 0.5
 53   end
 54 
 55   def can_make_new_decision?
 56     now = Gosu.milliseconds
 57     if now - (@last_decision ||= 0) > DECISION_DELAY
 58       @last_decision = now
 59       true
 60     end
 61   end
 62 
 63   def adjust_desired_angle
 64     @desired_gun_angle = if @target
 65        Utils.angle_between(
 66         @object.x, @object.y, @target.x, @target.y)
 67     else
 68       @object.direction
 69     end
 70   end
 71 
 72   def change_target(new_target)
 73     @target = new_target
 74     adjust_desired_angle
 75   end
 76 
 77   def adjust_gun_angle
 78     actual = @object.gun_angle
 79     desired = @desired_gun_angle
 80     if actual > desired
 81       if actual - desired > 180 # 0 -> 360 fix
 82         @object.gun_angle = (actual + @retarget_speed) % 360
 83         if @object.gun_angle < desired
 84           @object.gun_angle = desired # damp
 85         end
 86       else
 87         @object.gun_angle = [actual - @retarget_speed, desired].max
 88       end
 89     elsif actual < desired
 90       if desired - actual > 180 # 360 -> 0 fix
 91         @object.gun_angle = (360 + actual - @retarget_speed) % 360
 92         if @object.gun_angle > desired
 93           @object.gun_angle = desired # damp
 94         end
 95       else
 96         @object.gun_angle = [actual + @retarget_speed, desired].min
 97       end
 98     end
 99   end
100 end

There is some math involved, but it is pretty straightforward. We need to find out an angle between two points, to know where our gun should point, and the other thing we need is coordinates of point which is in some distance away from source at given angle. Here are those functions:

module Utils
  # ...
  def self.angle_between(x, y, target_x, target_y)
    dx = target_x - x
    dy = target_y - y
    (180 - Math.atan2(dx, dy) * 180 / Math::PI) + 360 % 360
  end

  def self.point_at_distance(source_x, source_y, angle, distance)
    angle = (90 - angle) * Math::PI / 180
    x = source_x + Math.cos(angle) * distance
    y = source_y - Math.sin(angle) * distance
    [x, y]
  end
  # ...
end

Implementing AI Input

At this point our tanks can already defend themselves, even through motion is not yet implemented. Let’s wire everything we have in AiInput class that we had prepared earlier. We will need a blank TankMotionFSM class with 3 argument initializer and empty update, on_collision(with) and on_damage(amount) methods for it to work:

08-ai/entities/components/ai_input.rb

 1 class AiInput < Component
 2   UPDATE_RATE = 200 # ms
 3 
 4   def initialize(object_pool)
 5     @object_pool = object_pool
 6     super(nil)
 7     @last_update = Gosu.milliseconds
 8   end
 9 
10   def control(obj)
11     self.object = obj
12     @vision = AiVision.new(obj, @object_pool,
13                            rand(700..1200))
14     @gun = AiGun.new(obj, @vision)
15     @motion = TankMotionFSM.new(obj, @vision, @gun)
16   end
17 
18   def on_collision(with)
19     @motion.on_collision(with)
20   end
21 
22   def on_damage(amount)
23     @motion.on_damage(amount)
24   end
25 
26   def update
27     return if object.health.dead?
28     @gun.adjust_angle
29     now = Gosu.milliseconds
30     return if now - @last_update < UPDATE_RATE
31     @last_update = now
32     @vision.update
33     @gun.update
34     @motion.update
35   end
36 end

It adjust gun angle all the time, but does updates at UPDATE_RATE to save CPU power. AI is usually one of the most CPU intensive things in games, so it’s a common practice to execute it less often. Refreshing enemy brains 5 per second is enough to make them deadly.

Make sure you spawn some AI controlled tanks in PlayState and try killing them now. I bet they will eventually get you even while standing still. You can also make tanks spawn below mouse cursor when you press T key:

class PlayState < GameState
  # ...
  def initialize
    # ...
    10.times do |i|
      Tank.new(@object_pool, AiInput.new(@object_pool))
    end
  end
  # ...
  def button_down(id)
    # ...
    if id == Gosu::KbT
      t = Tank.new(@object_pool,
                   AiInput.new(@object_pool))
      t.x, t.y = @camera.mouse_coords
    end
    # ...
  end
  # ...
end

Implementing Tank Motion States

This is the place where we will need Finite State Machine to get things right. We will design it like this:

  1. TankMotionFSM will decide which motion state tank should be in, considering various parameters, e.g. existence of target or lack thereof, health, etc.
  2. There will be TankMotionState base class that will offer common methods like drive, wait and on_collision.
  3. Concrete motion classes will implement update, change_direction and other methods, that will fiddle with Tank#throttle_down and Tank#direction to make it move and turn.

We will begin with TankMotionState:

08-ai/entities/components/ai/tank_motion_state.rb

 1 class TankMotionState
 2   def initialize(object, vision)
 3     @object = object
 4     @vision = vision
 5   end
 6 
 7   def enter
 8     # Override if necessary
 9   end
10 
11   def change_direction
12     # Override
13   end
14 
15   def wait_time
16     # Override and return a number
17   end
18 
19   def drive_time
20     # Override and return a number
21   end
22 
23   def turn_time
24     # Override and return a number
25   end
26 
27   def update
28     # Override
29   end
30 
31   def wait
32     @sub_state = :waiting
33     @started_waiting = Gosu.milliseconds
34     @will_wait_for = wait_time
35     @object.throttle_down = false
36   end
37 
38   def drive
39     @sub_state = :driving
40     @started_driving = Gosu.milliseconds
41     @will_drive_for = drive_time
42     @object.throttle_down = true
43   end
44 
45   def should_change_direction?
46     return true unless @changed_direction_at
47     Gosu.milliseconds - @changed_direction_at >
48       @will_keep_direction_for
49   end
50 
51   def substate_expired?
52     now = Gosu.milliseconds
53     case @sub_state
54     when :waiting
55       true if now - @started_waiting > @will_wait_for
56     when :driving
57       true if now - @started_driving > @will_drive_for
58     else
59       true
60     end
61   end
62 
63   def on_collision(with)
64     change = case rand(0..100)
65     when 0..30
66       -90
67     when 30..60
68       90
69     when 60..70
70       135
71     when 80..90
72       -135
73     else
74       180
75     end
76     @object.physics.change_direction(
77       @object.direction + change)
78   end
79 end

Nothing extraordinary here, and we need a concrete implementation to get a feeling how it would work, therefore let’s examine TankRoamingState. It will be the default state which tank would be in if there were no enemies around.

Tank Roaming State

08-ai/entities/components/ai/tank_roaming_state.rb

 1 class TankRoamingState < TankMotionState
 2   def initialize(object, vision)
 3     super
 4     @object = object
 5     @vision = vision
 6   end
 7 
 8   def update
 9     change_direction if should_change_direction?
10     if substate_expired?
11       rand > 0.3 ? drive : wait
12     end
13   end
14 
15   def change_direction
16     change = case rand(0..100)
17     when 0..30
18       -45
19     when 30..60
20       45
21     when 60..70
22       90
23     when 80..90
24       -90
25     else
26       0
27     end
28     if change != 0
29       @object.physics.change_direction(
30         @object.direction + change)
31     end
32     @changed_direction_at = Gosu.milliseconds
33     @will_keep_direction_for = turn_time
34   end
35 
36   def wait_time
37     rand(500..2000)
38   end
39 
40   def drive_time
41     rand(1000..5000)
42   end
43 
44   def turn_time
45     rand(2000..5000)
46   end
47 end

The logic here:

  1. Tank will randomly change direction every turn_time interval, which is between 2 and 5 seconds.
  2. Tank will choose to drive (80% chance) or to stand still (20% chance).
  3. If tank chose to drive, it will keep driving for drive_time, which is between 1 and 5 seconds.
  4. Same goes with waiting, but wait_time (0.5 - 2 seconds) will be used for duration.
  5. Direction changes and driving / waiting are independent.

This will make an impression that our tank is driving around looking for enemies.

Tank Fighting State

When tank finally sees an opponent, it will start fighting. Fighting motion should be more energetic than roaming, we will need a sharper set of choices in change_direction among other things.

08-ai/entities/components/ai/tank_fighting_state.rb

 1 class TankFightingState < TankMotionState
 2   def initialize(object, vision)
 3     super
 4     @object = object
 5     @vision = vision
 6   end
 7 
 8   def update
 9     change_direction if should_change_direction?
10     if substate_expired?
11       rand > 0.2 ? drive : wait
12     end
13   end
14 
15   def change_direction
16     change = case rand(0..100)
17     when 0..20
18       -45
19     when 20..40
20       45
21     when 40..60
22       90
23     when 60..80
24       -90
25     when 80..90
26       135
27     when 90..100
28       -135
29     end
30     @object.physics.change_direction(
31       @object.direction + change)
32     @changed_direction_at = Gosu.milliseconds
33     @will_keep_direction_for = turn_time
34   end
35 
36   def wait_time
37     rand(300..1000)
38   end
39 
40   def drive_time
41     rand(2000..5000)
42   end
43 
44   def turn_time
45     rand(500..2500)
46   end
47 end

We will have much less waiting and much more driving and turning.

Tank Chasing State

If opponent is fleeing, we will want to set our direction towards the opponent and hit pedal to the metal. No waiting here. AiGun#desired_gun_angle will point directly to our enemy.

08-ai/entities/components/ai/tank_chasing_state.rb

 1 class TankChasingState < TankMotionState
 2   def initialize(object, vision, gun)
 3     super(object, vision)
 4     @object = object
 5     @vision = vision
 6     @gun = gun
 7   end
 8 
 9   def update
10     change_direction if should_change_direction?
11     drive
12   end
13 
14   def change_direction
15     @object.physics.change_direction(
16       @gun.desired_gun_angle -
17       @gun.desired_gun_angle % 45)
18 
19     @changed_direction_at = Gosu.milliseconds
20     @will_keep_direction_for = turn_time
21   end
22 
23   def drive_time
24     10000
25   end
26 
27   def turn_time
28     rand(300..600)
29   end
30 end

Tank Fleeing State

Now, if our health is low, we will do the opposite of chasing. Gun will be pointing and shooting at the opponent, but we want body to move away, so we won’t get ourselves killed. It is very similar to TankChasingState where change_direction adds extra 180 degrees to the equation, but there is one more thing. Tank can only flee for a while. Then it gets itself together and goes into final battle. That’s why we provide can_flee? method that TankMotionFSM will consult with before entering fleeing state.

We have implemented all the states, that means we are moments away from actually playable prototype with tank bots running around and fighting with you and each other.

Wiring Tank Motion States Into Finite State Machine

Implementing TankMotionFSM after we have all motion states ready is surprisingly easy:

08-ai/entities/components/ai/tank_motion_fsm.rb

 1 class TankMotionFSM
 2   STATE_CHANGE_DELAY = 500
 3 
 4   def initialize(object, vision, gun)
 5     @object = object
 6     @vision = vision
 7     @gun = gun
 8     @roaming_state = TankRoamingState.new(object, vision)
 9     @fighting_state = TankFightingState.new(object, vision)
10     @fleeing_state = TankFleeingState.new(object, vision, gun)
11     @chasing_state = TankChasingState.new(object, vision, gun)
12     set_state(@roaming_state)
13   end
14 
15   def on_collision(with)
16     @current_state.on_collision(with)
17   end
18 
19   def on_damage(amount)
20     if @current_state == @roaming_state
21       set_state(@fighting_state)
22     end
23   end
24 
25   def update
26     choose_state
27     @current_state.update
28   end
29 
30   def set_state(state)
31     return unless state
32     return if state == @current_state
33     @last_state_change = Gosu.milliseconds
34     @current_state = state
35     state.enter
36   end
37 
38   def choose_state
39     return unless Gosu.milliseconds -
40       (@last_state_change) > STATE_CHANGE_DELAY
41     if @gun.target
42       if @object.health.health > 40
43         if @gun.distance_to_target > BulletPhysics::MAX_DIST
44           new_state = @chasing_state
45         else
46           new_state = @fighting_state
47         end
48       else
49         if @fleeing_state.can_flee?
50           new_state = @fleeing_state
51         else
52           new_state = @fighting_state
53         end
54       end
55     else
56       new_state = @roaming_state
57     end
58     set_state(new_state)
59   end
60 end

All the logic is in choose_state method, which is pretty ugly and procedural, but it does the job. The code should be easy to understand, so instead of describing it, here is a picture worth thousand words:

First real battle

First real battle

You may notice a new crosshair, which replaced the old one that was never visible:

class Camera
  # ...
  def draw_crosshair
    factor = 0.5
    x = $window.mouse_x
    y = $window.mouse_y
    c = crosshair
    c.draw(x - c.width * factor / 2,
           y - c.height * factor / 2,
           1000, factor, factor)
  end
  # ...
  private

  def crosshair
    @crosshair ||= Gosu::Image.new(
      $window, Utils.media_path('c_dot.png'), false)
  end
end

However this new crosshair didn’t help me win, I got my ass kicked badly. Increasing game window size helped, but we obviously need to fine tune many things in this AI, to make it smart and challenging rather than dumb and deadly accurate.

Up next

Making The Prototype Playable