Dynamic Clustering
Dynamic clustering is a technique to find similar item in your log. The ideas is to put a "state" for each item in your log. The state can contain any data that you seem valuable, such as lateral velocity or distance. Save this along with your data. When you need a data, consider "cluster" them. The easiest way doing this to to find a "distance" between current state and past states. Distance can be Euclidian (sqrt(sqr(dist1 - dist2) + sqr(lat1 - lat2))) or another way, such as Manhatton distance. Took N states with the lower distance, that's your data.
Earlier method doing this linearly by iterate through the log and calculate distance for each one respectively. If you have more than 100,000 states in your log, it will heavily slow. The new approach is K-d Tree. Corbos was the first one who mentioning this on the wiki, and get catch in interest by Chase-san and Simonton. As of now, Simonton's K-d Tree is one of fastest tree.
Bot using this technique
- Tron & Shadow: First tow bots using this technique. This technique used to called "Trons Gun", but later renamed.
- Chalk: First dynamic clustering bot that released with source code.
- DCBot: A simplified version of gun using by earlier version of Tron and Shadow.
- Lukious & Firebird & Hydra: Dynamic Clustering version of Dookious, Phoenix, WaveSerpent respectively.
- Horizon & RougeDC & YersiniaPestis: Newer dynamic clustering bots.
- X2 & Ali & DrussGT: These bots use Dynamic Clustering only for their gun.
