# Waves/Precise Intersection

m |
m (→Bot using this technique) |
||

(4 intermediate revisions by 3 users not shown) | |||

Line 1: | Line 1: | ||

− | |||

[[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 [[ | + | 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. |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | 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. | |

− | + | == 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 == | ||

− | |||

* [[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 | + | * [[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, | + | * [[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 == | |

+ | * [[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 05:04, 26 November 2012

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.

## [edit] 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.

## [edit] 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.

## [edit] See also

- Smashing it down to bins - An alternative algorithm from GrubbmGait for calculating precise intersection in a Visit Count Stats system.