Creating Artificial Intelligence - Developing Games With Ruby (2014)

Developing Games With Ruby (2014)

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 TankMotionFSMwill 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.