Difference between revisions of "Waves/Precise Intersection"

From Robowiki
Jump to navigation Jump to search
(Seraphim 2 uses this too.)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
{{stub}}
 
 
[[Image:Precise Intersection Wave 1.png|thumb|right|252px|Plain wave intersection]]
 
[[Image:Precise Intersection Wave 1.png|thumb|right|252px|Plain wave intersection]]
 
[[Image:Precise Intersection Wave 2.png|thumb|right|252px|First intersection range]]
 
[[Image:Precise Intersection Wave 2.png|thumb|right|252px|First intersection range]]
Line 5: Line 4:
 
[[Image:Precise Intersection Wave 4.png|thumb|right|252px|The steps repeated]]
 
[[Image:Precise Intersection Wave 4.png|thumb|right|252px|The steps repeated]]
  
−
'''Precise Intersection''' of [[waves]] are to calculate every hittable angle/[[Guess Factor|guess factor]]. Normally, people only calculate [[angular bot width]] (<code>Math.atan(18/distance) * 2</code>), which is  perfectly accurate and fine when the enemy bot isn't moving. Anyway, enemy robot have depth and can move.
+
The '''Precise Intersection''' of a robot and a [[Waves|wave]] can be analyzed to find the exact range of firing angles that would hit the robot. The calculation involves simulating the movement of both the bot and the wave on every tick that a bullet collision could take place and deducing the minimum and maximum firing angles that would hit the bot.
−
In order to make it more accurate, you need to check the intersection range for every tick the wave intersects the bounding box of the robot. The intersection range can be calculated by the highest and lowest angles represented by:
 
−
* Intersections between the robot bounding box and the bullet wave.
 
−
* Intersections between the robot bounding box and where the bullet wave was last tick.
 
−
* Any corners of the robot bounding box that lie between the wave last tick and the wave this tick.
 
  
−
In next tick, the enemy robot had moved, therefore you need to calculate the new intersection range. You overlay the ranges calculated each tick, to come up with an 'augmented range'.
+
An estimation of this range is used in many bots. An angular range of <code>Math.atan(18/distance) * 2</code> assumes a stationary bot with a bot width of 18. Simply <code>(18/distance) * 2</code> is accurate at most distances, as well, without any trig operations.
  
−
These steps repeated until the wave passed the robot. The final, augmented intersection range will be the full range that can hit the robot in way more accurate than plain bot width.
+
== Calculation ==
 +
Note that in [[Robocode/Game Physics|Robocode physics]], bullets act as a line segment. Between ticks:
 +
* Bullets advance, forming a line segment.
 +
* Robocode checks for collisions - any intersection of a bullet line segment and a robot bounding box.
 +
* Robots move.
 +
So you need to examine the area covered by the advancing wave and the initial position of the target bot. Specifically, you need to account for:
 +
* Points of intersection between the robot bounding box and the wave's initial position.
 +
* Points of intersection between the robot bounding box and the wave's final position.
 +
* Any corners of the robot bounding box that lie between the two wave circles.
 +
The minimum and maximum angles from the wave source to any of these points form the precise intersection range for this tick. Combine the ranges from every tick to get the entire range of firing angles that would hit the target bot.
  
 
== Bot using this technique ==
 
== Bot using this technique ==
−
There are only 6 known robots using this technique, which are
 
 
* [[Garm]]: The first implementation.
 
* [[Garm]]: The first implementation.
 
* [[RougeDC]]: The original ideas was posted under the name of "Super Bot Width", used in both gun and movement.
 
* [[RougeDC]]: The original ideas was posted under the name of "Super Bot Width", used in both gun and movement.
−
* [[DrussGT]]: Current rumble king use precise intersection in the his gun.
+
* [[DrussGT]]: Current [[RoboRumble]] King, uses precise intersection in his gun.
 
* [[PolishedRuby]]: Same gun as RougeDC.
 
* [[PolishedRuby]]: Same gun as RougeDC.
 
* [[Polylunar]]: Used to determine when a certain angle is going to hit an enemy no matter how they move (only occurs at close range)
 
* [[Polylunar]]: Used to determine when a certain angle is going to hit an enemy no matter how they move (only occurs at close range)
−
* [[Wintermute]]: Newer robot, using in both gun and movement.
+
* [[Wintermute]]: Newer robot, used in both gun and movement.
−
* [[Seraphim]]: Movement and Gun in version 2.
+
* [[Seraphim]]: Movement and gun in version 2.
 +
* [[Nene]]: Precise Intersection made sense, unlike the traditional intersection methods.
 +
* [[GresSuffurd]]: Gun since 0.2.26.
 +
* [[Diamond]]: Movement since 1.471, gun since 1.5.30.
  
−
<!-- Request for category, I don't know which to put in -->
+
== See also ==
 +
* [[Talk:Waves/Precise Intersection#Smashing it down to bins|Smashing it down to bins]] - An alternative algorithm from [[User:GrubbmGait|GrubbmGait]] for calculating precise intersection in a [[Visit Count Stats]] system.
 +
 
 +
[[Category:Terminology]]

Latest revision as of 06:04, 26 November 2012

Plain wave intersection
First intersection range
Augmented intersection range
The steps repeated

The Precise Intersection of a robot and a wave can be analyzed to find the exact range of firing angles that would hit the robot. The calculation involves simulating the movement of both the bot and the wave on every tick that a bullet collision could take place and deducing the minimum and maximum firing angles that would hit the bot.

An estimation of this range is used in many bots. An angular range of Math.atan(18/distance) * 2 assumes a stationary bot with a bot width of 18. Simply (18/distance) * 2 is accurate at most distances, as well, without any trig operations.

Calculation

Note that in Robocode physics, bullets act as a line segment. Between ticks:

  • Bullets advance, forming a line segment.
  • Robocode checks for collisions - any intersection of a bullet line segment and a robot bounding box.
  • Robots move.

So you need to examine the area covered by the advancing wave and the initial position of the target bot. Specifically, you need to account for:

  • Points of intersection between the robot bounding box and the wave's initial position.
  • Points of intersection between the robot bounding box and the wave's final position.
  • Any corners of the robot bounding box that lie between the two wave circles.

The minimum and maximum angles from the wave source to any of these points form the precise intersection range for this tick. Combine the ranges from every tick to get the entire range of firing angles that would hit the target bot.

Bot using this technique

  • Garm: The first implementation.
  • RougeDC: The original ideas was posted under the name of "Super Bot Width", used in both gun and movement.
  • DrussGT: Current RoboRumble King, uses precise intersection in his gun.
  • PolishedRuby: Same gun as RougeDC.
  • Polylunar: Used to determine when a certain angle is going to hit an enemy no matter how they move (only occurs at close range)
  • Wintermute: Newer robot, used in both gun and movement.
  • Seraphim: Movement and gun in version 2.
  • Nene: Precise Intersection made sense, unlike the traditional intersection methods.
  • GresSuffurd: Gun since 0.2.26.
  • Diamond: Movement since 1.471, gun since 1.5.30.

See also

Retrieved from "http://robowiki.net/w/index.php?title=Waves/Precise_Intersection&oldid=27538"