From: Edward Faulkner <ef@...>
Date: 2005-12-20T16:49:44+09:00
Subject: [SOLUTION] Robot

--OgqxwSJOaUobr8KG
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

Here's my robot.  The coolest part is the predictive tracker, which
makes him a pretty good shot.

Kinda long for a quiz submission, I know.  But it's a tough problem.

regards,
Ed

require 'robot'
require 'matrix'

BOT_MAX_SPEED =3D 8
BULLET_SPEED =3D 30

class NotEnoughData < RuntimeError; end

class PredictiveTracker
  def initialize(size =3D 4)
    @size =3D size || 4

    @x =3D Array.new(@size,0)=20
    @y =3D Array.new(@size,0)
    @t =3D Array.new(@size,0)

    @most_recent =3D 0
    @solution =3D nil
  end

  def mark(x,y,time)
    @most_recent =3D (@most_recent + 1) % @size
    @x[@most_recent] =3D x
    @y[@most_recent] =3D y
    @t[@most_recent] =3D time

    # Update solution, if possible
    @solution =3D solve
  rescue
  end
 =20
  def solve
    xoff, vx =3D linfit(@t, @x)
    yoff, vy =3D linfit(@t, @y)
    [vx,vy,xoff,yoff]
  end

  # predicts target location at the given time
  def predict(time)
    raise NotEnoughData unless @solution
    vx, vy, xoff, yoff =3D @solution
    [xoff + vx*time, yoff + vy*time]
  end


  def aim_point(my_x, my_y, time)
    raise NotEnoughData unless @solution
    t =3D 0
    loop do
      x,y =3D predict(time+t)
      break if vs(vd([x,y],[my_x,my_y])) < BULLET_SPEED*BULLET_SPEED*t*t
      t +=3D 1
      raise NotEnoughData if t > 100
    end
    predict(time+t)
  end

  def firing_angle(my_x,my_y,time)
    x,y =3D aim_point(my_x,my_y,time)
    Math.atan2(my_y-y,x-my_x).to_deg
  end


  # returns [a,b] such that a + bx =3D y is least squares linear fit
  def linfit(x,y)
    sum_x =3D 0.0
    sum_y =3D 0.0
    sum_prod =3D 0.0
    sum_x2 =3D 0.0
    n =3D x.size
    n.times {|i|=20
      sum_x +=3D x[i]
      sum_y +=3D y[i]
      sum_prod +=3D x[i]*y[i]
      sum_x2 +=3D x[i]*x[i]
    }
    b =3D (n*sum_prod - sum_x*sum_y) / (n*sum_x2 - sum_x*sum_x)
    a =3D (sum_y - b*sum_x) / n
    raise NotEnoughData if a.nan? or b.nan?
    [a,b]
  end

  # Vector difference
  def vd(a,b)
    a.zip(b).map{|a,b| a - b}
  end

  # Vector square
  def vs(a)
    dp(a,a)
  end

  # Dot product
  def dp(a,b)
    a.zip(b).map{|a,b| a*b}.inject(0){|a,b| a+b}
  end

end


class EdBot
   include Robot

  def tick events
    startup if time =3D=3D 0
    update_radar(events)
    update_gun
    update_heading

    accelerate 1

    turn_radar(radar_velocity - @gun_velocity - @angular_velocity)
    turn_gun(@gun_velocity - @angular_velocity)
    turn(@angular_velocity)
  end

  def update_radar(events)
    if events['robot_scanned'].empty?
      if @saw_target
        high_low
      else
        low_low
      end
      @saw_target =3D false
    else
      td =3D events['robot_scanned'].min.first
      if @saw_target
        high_high(td)
      else
        low_high(td)
      end
      @saw_target =3D true
    end
    @older_radar_heading =3D @old_radar_heading
    @old_radar_heading =3D radar_heading
  end

  def low_low
    @radar_speed =3D clamp(@radar_speed + target_angular_speed, 0, 60)

    if @downticks > 0
      @downticks -=3D 1
      if @downticks =3D=3D 0
        @radar_direction *=3D -1
      end
    end
  end

  def low_high(dist)
    @uptick_heading =3D beam_center
    @uptick_dist =3D dist
  end

  def high_high(dist)
    @uptick_dist =3D dist
  end

  def high_low
    @radar_direction *=3D -1
    @radar_speed =3D clamp(@radar_speed * 0.5, target_angular_speed, 60)
    plot_target(angle_average(angle_average(@old_radar_heading,@older_radar=
_heading),@uptick_heading),@uptick_dist)
    @downticks =3D 8
  end

  def beam_center
    angle_average(radar_heading, @old_radar_heading)
  end

  def trigger(spread)
    if spread < 1
      fire 3
    end
  end

  def update_gun
    diff =3D angle_direction(gun_heading, @tracker.firing_angle(x,y,time))
    @gun_velocity =3D clamp(diff,-30,30)
    trigger(diff)
  rescue NotEnoughData
  end

  def wall_force(range)
    (2**((battlefield_width - range)/50.0))/(2**(battlefield_width/50.0))
  end

  def update_heading
    ranges =3D [x-size, battlefield_height-size-y, battlefield_width-size-x=
, y-size]
    normals =3D [0, 90, 180, 270]
    forces =3D ranges.map {|r| wall_force(r)}

    @xforce =3D forces[0] - forces[2]
    @yforce =3D forces[3] - forces[1]
    fa =3D Math.atan2(-@yforce,@xforce).to_deg

    goal =3D target_heading + 90
    unless angle_difference(heading, goal) < 90
      goal =3D (goal + 180) % 360
    end

    diff =3D angle_direction(goal, fa)
    goal +=3D diff*(forces.max)
    @angular_velocity =3D clamp(angle_direction(heading, goal),-10,10)
  end


  def startup
    @saw_target =3D false
    @uptick_heading =3D 0

    @target_x =3D @target_y =3D 0

    @radar_speed =3D 60
    @radar_direction =3D 1
    @old_radar_heading =3D 0
    @older_radar_heading =3D 0
    @downticks =3D 0

    @gun_velocity =3D 0
    @angular_velocity =3D 0
   =20
    @tracker =3D PredictiveTracker.new

    @log =3D File.open("edbot.log","a")
    @log.write "Starting up!\n"

  end

  def angle_difference(a,b)
    d =3D (a % 360 - b % 360).abs
    d > 180 ? 360 - d : d
  end

  # To turn from a toward b, how should you turn?
  def angle_direction(a,b)
    magnitude =3D angle_difference(a,b)
    if angle_difference(a + 1, b) < magnitude
      magnitude
    else
      -magnitude
    end
  end

  def radar_velocity
    @radar_speed * @radar_direction
  end

  def angle_average(a,b)
    (angle_direction(a,b) / 2 + a) % 360
  end

  # How much can the angle to the target change in one tick?
  def target_angular_speed
    360 * BOT_MAX_SPEED / (2 * Math::PI * target_distance)
  end

  def target_heading
    Math.atan2(y- @target_y, @target_x - x).to_deg
  end

  def target_distance
    Math.sqrt((@target_x - x)**2 + (@target_y - y)**2)
  end

  def plot_target(heading, distance)
    rads =3D heading.to_rad
    @target_y =3D y - distance * Math.sin(rads)
    @target_x =3D x + distance * Math.cos(rads)
    @tracker.mark(@target_x,@target_y,time)
    @log.write("#{@target_x}\t#{@target_y}\t#{time}\n")
  end

  def clamp(var, min, max)
    val =3D 0 + var # to guard against poisoned vars
    if val > max
      max
    elsif val < min
      min
    else
      val
    end
  end

end



--OgqxwSJOaUobr8KG
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDp7eCnhUz11p9MSARAr89AKCSn22IMlqPl0ZTkmjtokUckVtsvwCePvM2
MSzKExS29iOKWfrkIfp7LcM=
=yWrR
-----END PGP SIGNATURE-----

--OgqxwSJOaUobr8KG--