Building Advanced AI - Developing Games With Ruby (2014)

Developing Games With Ruby (2014)

Building Advanced AI

The AI we have right now can kick some ass, but it is too dumb for any seasoned gamer to compete with. This is the list of current flaws:

1. It does not navigate well, gets stuck among trees or somewhere near water.

2. It is not aware of powerups.

3. It could do better job at shooting.

4. It’s field of vision is too small, compared to player’s, who is equipped with radar.

We will tackle these issues in current chapter.

Improving Tank Navigation

Tanks shouldn’t behave like Roombas, randomly driving around and bumping into things. They could be navigating like this:

1. Consult with current AI state and find or update destination point.

2. If destination has changed, calculate shortest path to destination.

3. Move along the calculated path.

4. Repeat.

If this looks easy, let me assure you, it would probably require rewriting the majority of AI and Map code we have at this point, and it is pretty tricky to implement with procedurally generated maps, because normally you would use a map editor to set up waypoints, navigation mesh or other hints for AI so it doesn’t get stuck. Sometimes it is better to have something working imperfectly over a perfect solution that never happens, thus we will use simple things that will make as much impact as possible without rewriting half of the code.

Generating Friendlier Maps

One of main reasons why tanks get stuck is bad placement of spawn points. They don’t take trees and boxes into account, so enemy tank can spawn in the middle of a forest, with no chance of getting out without blowing things up. A simple fix would be to consult with ObjectPool before placing a spawn point only where there are no other game objects around in, say, 150 pixel radius:

class Map

# ...

def find_spawn_point

while true

x = rand(0..MAP_WIDTH * TILE_SIZE)

y = rand(0..MAP_HEIGHT * TILE_SIZE)

if can_move_to?(x, y) &&

@object_pool.nearby_point(x, y, 150).empty?

return [x, y]

end

end

end

# ...

end

How about powerups? They can also spawn in the middle of a forest, and while tanks are not seeking them yet, we will be implementing this behavior, and leading tanks into wilderness of trees is not the best idea ever. Let’s fix it too:

class Map

# ...

def generate_powerups

pups = 0

target_pups = rand(20..30)

while pups < target_pups do

x = rand(0..MAP_WIDTH * TILE_SIZE)

y = rand(0..MAP_HEIGHT * TILE_SIZE)

if tile_at(x, y) != @water &&

@object_pool.nearby_point(x, y, 150).empty?

random_powerup.new(@object_pool, x, y)

pups += 1

end

end

end

# ...

end

We could also reduce tree count, but that would make the map look worse, so we are going to keep this in our pocket as a mean of last resort.

Implementing Demo State To Observe AI

Probably the best way to figure out if our AI is any good is to target one of AI tanks with our game camera and see how it plays. It will give us a great visual testing tool that will allow tweaking AI settings and seeing if they perform better or worse. For that we will introduce DemoState where only AI tanks will be present in the map, and we will be able to switch camera from one tank to another.

DemoState is very similar to PlayState, the main difference is that there is no player. We will extract create_tanks method that will be overridden in DemoState.

class PlayState < GameState

attr_accessor :update_interval, :object_pool, :tank

def initialize

# ...

@camera = Camera.new

@object_pool.camera = @camera

create_tanks(4)

end

# ...

private

def create_tanks(amount)

@map.spawn_points(amount * 3)

@tank = Tank.new(@object_pool,

PlayerInput.new('Player', @camera, @object_pool))

amount.times do |i|

Tank.new(@object_pool, AiInput.new(

@names.random, @object_pool))

end

@camera.target = @tank

@hud = HUD.new(@object_pool, @tank)

end

# ...

end

We will also want to display a smaller version of score in top-right corner of the screen, so let’s add some adjustments to ScoreDisplay:

class ScoreDisplay

def initialize(object_pool, font_size=30)

@font_size = font_size

# ...

end

def create_stats_image(stats)

# ...

@stats_image = Gosu::Image.from_text(

$window, text, Utils.main_font, @font_size)

end

# ...

def draw_top_right

@stats_image.draw(

$window.width - @stats_image.width - 20,

20,

1000)

end

end

And here is the extended DemoState:

13-advanced-ai/game_states/demo_state.rb


1 class DemoState < PlayState

2 attr_accessor :tank

3

4 def enter

5 # Prevent reactivating HUD

6 end

7

8 def update

9 super

10 @score_display = ScoreDisplay.new(

11 object_pool, 20)

12 end

13

14 def draw

15 super

16 @score_display.draw_top_right

17 end

18

19 def button_down(id)

20 super

21 if id == Gosu::KbSpace

22 target_tank = @tanks.reject do |t|

23 t == @camera.target

24 end.sample

25 switch_to_tank(target_tank)

26 end

27 end

28

29 private

30

31 def create_tanks(amount)

32 @map.spawn_points(amount * 3)

33 @tanks = []

34 amount.times do |i|

35 @tanks << Tank.new(@object_pool, AiInput.new(

36 @names.random, @object_pool))

37 end

38 target_tank = @tanks.sample

39 @hud = HUD.new(@object_pool, target_tank)

40 @hud.active = false

41 switch_to_tank(target_tank)

42 end

43

44 def switch_to_tank(tank)

45 @camera.target = tank

46 @hud.player = tank

47 self.tank = tank

48 end

49 end


To have a possibility to enter DemoState, we need to change MenuState a little:

class MenuState < GameState

# ...

def update

text = "Q: Quit\nN: New Game\nD: Demo"

# ...

end

# ...

def button_down(id)

# ...

if id == Gosu::KbD

@play_state = DemoState.new

GameState.switch(@play_state)

end

end

end

Now, main menu has the option to enter demo state:

Overhauled main menu

Overhauled main menu

Observing AI in demo state

Observing AI in demo state

Visual AI Debugging

After watching AI behavior in demo mode for a while, I was terrified. When playing game normally, you usually see tanks in “fighting” state, which works pretty well, but when tanks go roaming, it’s a complete disaster. They get stuck easily, they don’t go too far from the original location, they wait too much.

Some things could be improved just by changing wait_time, turn_time and drive_time to different values, but we certainly have to do bigger changes than that.

On the other hand, “observe AI in action, tweak, repeat” cycle proved to be very effective, I will definitely use this technique in all my future games.

To make visual debugging easier, build yourself some tooling. One way to do it is to have global $debug variable which you can toggle by pressing some button:

class PlayState < GameState

# ...

def button_down(id)

# ...

if id == Gosu::KbF1

$debug = !$debug

end

# ...

end

# ...

end

Then add extra drawing instructions to your objects and their components. For example, this will make Tank display it’s current TankMotionState implementation class beneath it:

class TankMotionFSM

# ...

def set_state(state)

# ...

if $debug

@image = Gosu::Image.from_text(

$window, state.class.to_s,

Gosu.default_font_name, 18)

end

end

# ...

def draw(viewport)

if $debug

@image && @image.draw(

@object.x - @image.width / 2,

@object.y + @object.graphics.height / 2 -

@image.height, 100)

end

end

# ...

end

To mark tank’s desired gun angle as blue line and actual gun angle as red line, you can do this:

class AiGun

# ...

def draw(viewport)

if $debug

color = Gosu::Color::BLUE

x, y = @object.x, @object.y

t_x, t_y = Utils.point_at_distance(x, y, @desired_gun_angle,

BulletPhysics::MAX_DIST)

$window.draw_line(x, y, color, t_x, t_y, color, 1001)

color = Gosu::Color::RED

t_x, t_y = Utils.point_at_distance(x, y, @object.gun_angle,

BulletPhysics::MAX_DIST)

$window.draw_line(x, y, color, t_x, t_y, color, 1000)

end

end

# ...

end

Finally, you can automatically mark collision box corners on your graphics components. Let’s take BoxGraphics for example:

# 13-advanced-ai/misc/utils.rb

module Utils

# ...

def self.mark_corners(box)

i = 0

box.each_slice(2) do |x, y|

color = DEBUG_COLORS[i]

$window.draw_triangle(

x - 3, y - 3, color,

x, y, color,

x + 3, y - 3, color,

100)

i = (i + 1) % 4

end

end

# ...

end

# 13-advanced-ai/entities/components/box_graphics.rb

class BoxGraphics < Component

# ..

def draw(viewport)

@box.draw_rot(x, y, 0, object.angle)

Utils.mark_corners(object.box) if $debug

end

# ...

end

As a developer, you can make yourself see nearly everything you want, make use of it.

Visual debugging of AI behavior

Visual debugging of AI behavior

Although it hurts the framerate a little, it is very useful when building not only AI, but the rest of the game too. Using this visual debugging together with Demo mode, you can tweak all the AI values to make it shoot more often, fight better, and be more agile. We won’t go through this minor tuning, but you can find the changes by viewing changes introduced in 13-advanced-ai.

Making AI Collect Powerups

To even out the odds, we have to make AI seek powerups when they are required. The logic behind it can be implemented using a couple of simple steps:

1. AI would know what powerups are currently needed. This may vary from state to state, i.e. speed and fire rate powerups are nice to have when roaming, but not that important when fleeing after taking heavy damage. And we don’t want AI to waste time and collect speed powerups when speed modifier is already maxed out.

2. AiVision would return closest visible powerup, filtered by acceptable powerup types.

3. Some TankMotionState implementation would adjust tank direction towards closest visible powerup in change_direction method.

Finding Powerups In Sight

To implement changes in AiVision, we will introduce closest_powerup method. It will query objects in sight and filter them out by their class and distance.

class AiVision

# ...

POWERUP_CACHE_TIMEOUT = 50

# ...

def closest_powerup(*suitable)

now = Gosu.milliseconds

@closest_powerup = nil

if now - (@powerup_cache_updated_at ||= 0) > POWERUP_CACHE_TIMEOUT

@closest_powerup = nil

@powerup_cache_updated_at = now

end

@closest_powerup ||= find_closest_powerup(*suitable)

end

private

def find_closest_powerup(*suitable)

if suitable.empty?

suitable = [FireRatePowerup,

HealthPowerup,

RepairPowerup,

TankSpeedPowerup]

end

@in_sight.select do |o|

suitable.include?(o.class)

end.sort do |a, b|

x, y = @viewer.x, @viewer.y

d1 = Utils.distance_between(x, y, a.x, a.y)

d2 = Utils.distance_between(x, y, b.x, b.y)

d1 <=> d2

end.first

end

# ...

end

It is very similar to AiVision#closest_tank, and parts should probably be extracted to keep the code dry, but we will not bother.

Seeking Powerups While Roaming

Roaming is when most picking should happen, because Tank sees no enemies in sight and needs to prepare for upcoming battles. Let’s see how can we implement this behavior while leveraging the newly made AiVision#closest_powerup:

class TankRoamingState < TankMotionState

# ...

def required_powerups

required = []

health = @object.health.health

if @object.fire_rate_modifier < 2 && health > 50

required << FireRatePowerup

end

if @object.speed_modifier < 1.5 && health > 50

required << TankSpeedPowerup

end

if health < 100

required << RepairPowerup

end

if health < 190

required << HealthPowerup

end

required

end

def change_direction

closest_powerup = @vision.closest_powerup(

*required_powerups)

if closest_powerup

@seeking_powerup = true

angle = Utils.angle_between(

@object.x, @object.y,

closest_powerup.x, closest_powerup.y)

@object.physics.change_direction(

angle - angle % 45)

else

@seeking_powerup = false

# ... choose random direction

end

@changed_direction_at = Gosu.milliseconds

@will_keep_direction_for = turn_time

end

# ...

def turn_time

if @seeking_powerup

rand(100..300)

else

rand(1000..3000)

end

end

end

It is simple as that, and our AI tanks are now getting buffed on their spare time.

Seeking Health Powerups After Heavy Damage

To seek health when damaged, we need to change TankFleeingState#change_direction:

class TankFleeingState < TankMotionState

# ...

def change_direction

closest_powerup = @vision.closest_powerup(

RepairPowerup, HealthPowerup)

if closest_powerup

angle = Utils.angle_between(

@object.x, @object.y,

closest_powerup.x, closest_powerup.y)

@object.physics.change_direction(

angle - angle % 45)

else

# ... reverse from enemy

end

@changed_direction_at = Gosu.milliseconds

@will_keep_direction_for = turn_time

end

# ...

end

This small change tells AI to pick up health while fleeing. The interesting part is that when tank picks up RepairPowerup, it’s health gets fully restored and AI should switch back to TankFightingState. This simple thing is a major improvement in AI behavior.

Evading Collisions And Getting Unstuck

While observing AI navigation, it was noticeable that tanks often got stuck, even in simple situations, like driving into a tree and hitting it repeatedly for a dozen of seconds. To reduce the number of such occasions, we will introduce TankNavigatingState, which would help avoid collisions, and TankStuckState, which would be responsible for driving out of dead ends as quickly as possible.

To implement these states, we need to have a way to tell if tank can go forward and a way of getting a direction which is not blocked by other objects. Let’s add a couple of methods to AiVision:

class AiVision

# ...

def can_go_forward?

in_front = Utils.point_at_distance(

*@viewer.location, @viewer.direction, 40)

@object_pool.map.can_move_to?(*in_front) &&

@object_pool.nearby_point(*in_front, 40, @viewer)

.reject { |o| o.is_a? Powerup }.empty?

end

def closest_free_path(away_from = nil)

paths = []

5.times do |i|

if paths.any?

return farthest_from(paths, away_from)

end

radius = 55 - i * 5

range_x = range_y = [-radius, 0, radius]

range_x.shuffle.each do |x|

range_y.shuffle.each do |y|

x = @viewer.x + x

y = @viewer.y + y

if @object_pool.map.can_move_to?(x, y) &&

@object_pool.nearby_point(x, y, radius, @viewer)

.reject { |o| o.is_a? Powerup }.empty?

if away_from

paths << [x, y]

else

return [x, y]

end

end

end

end

end

false

end

alias :closest_free_path_away_from :closest_free_path

# ...

private

def farthest_from(paths, away_from)

paths.sort do |p1, p2|

Utils.distance_between(*p1, *away_from) <=>

Utils.distance_between(*p2, *away_from)

end.first

end

# ...

end

AiVision#can_go_forward? tells if tank can move ahead, and AiVision#closest_free_path finds a point where tank can move without obstacles. You can also call AiVision#closest_free_path_away_from and provide coordinates you are trying to get away from.

We will use closest_free_path methods in newly implemented tank motion states, and can_go_forward? in TankMotionFSM, to make a decision when to jump into navigating or stuck state.

Those new states are nothing fancy:

13-advanced-ai/entities/components/ai/tank_navigating_state.rb


1 class TankNavigatingState < TankMotionState

2 def initialize(object, vision)

3 @object = object

4 @vision = vision

5 end

6

7 def update

8 change_direction if should_change_direction?

9 drive

10 end

11

12 def change_direction

13 closest_free_path = @vision.closest_free_path

14 if closest_free_path

15 @object.physics.change_direction(

16 Utils.angle_between(

17 @object.x, @object.y, *closest_free_path))

18 end

19 @changed_direction_at = Gosu.milliseconds

20 @will_keep_direction_for = turn_time

21 end

22

23 def wait_time

24 rand(10..100)

25 end

26

27 def drive_time

28 rand(1000..2000)

29 end

30

31 def turn_time

32 rand(300..1000)

33 end

34 end


TankNavigatingState simply chooses a random free path, changes direction to it and keeps driving.

13-advanced-ai/entities/components/ai/tank_stuck_state.rb


1 class TankNavigatingState < TankMotionState

2 def initialize(object, vision)

3 @object = object

4 @vision = vision

5 end

6

7 def update

8 change_direction if should_change_direction?

9 drive

10 end

11

12 def change_direction

13 closest_free_path = @vision.closest_free_path

14 if closest_free_path

15 @object.physics.change_direction(

16 Utils.angle_between(

17 @object.x, @object.y, *closest_free_path))

18 end

19 @changed_direction_at = Gosu.milliseconds

20 @will_keep_direction_for = turn_time

21 end

22

23 def wait_time

24 rand(10..100)

25 end

26

27 def drive_time

28 rand(1000..2000)

29 end

30

31 def turn_time

32 rand(300..1000)

33 end

34 end


TankStuckState is nearly the same, but it keeps driving away from @stuck_at point, which is set by TankMotionFSM upon transition to this state.

class TankMotionFSM

STATE_CHANGE_DELAY = 500

LOCATION_CHECK_DELAY = 5000

def initialize(object, vision, gun)

# ...

@stuck_state = TankStuckState.new(object, vision, gun)

@navigating_state = TankNavigatingState.new(object, vision)

set_state(@roaming_state)

end

# ...

def choose_state

unless @vision.can_go_forward?

unless @current_state == @stuck_state

set_state(@navigating_state)

end

end

# Keep unstucking itself for a while

change_delay = STATE_CHANGE_DELAY

if @current_state == @stuck_state

change_delay *= 5

end

now = Gosu.milliseconds

return unless now - @last_state_change > change_delay

if @last_location_update.nil?

@last_location_update = now

@last_location = @object.location

end

if now - @last_location_update > LOCATION_CHECK_DELAY

puts "checkin location"

unless @last_location.nil? || @current_state.waiting?

if Utils.distance_between(*@last_location, *@object.location) < 20

set_state(@stuck_state)

@stuck_state.stuck_at = @object.location

return

end

end

@last_location_update = now

@last_location = @object.location

end

# ...

end

# ...

end

What this does is automatically change state to navigating when tank is about to hit an obstacle. It also tracks tank location, and if tank hasn’t moved 20 pixels away from it’s original direction for 5 seconds, it enters TankStuckState, which deliberately tries to navigate away from the stock_at spot.

AI navigation has just got significantly better, and it didn’t take that many changes.