E
Edward Faulkner
--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
sum_y +=3D y
sum_prod +=3D x*y
sum_x2 +=3D x*x
}
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:
I * 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--
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
sum_y +=3D y
sum_prod +=3D x*y
sum_x2 +=3D x*x
}
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:
I * 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--