Kd-tree

This article is a stub. You can help RoboWiki by expanding it.

In computer science, a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. kd-trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbour searches). kd-trees are a special case of BSP trees.

In Robocode, a kd-tree is a data structure use for k-nearest neighbours searching in Dynamic Clustering data logging algorithms. Currently, the most popular type of kd-tree in Robocode is the Bucket PR kd-tree.

How it works?

Any state can be represented as a point in a n-dimensional space. A simple representation of an enemy robot's state might consist of 2 dimensions: velocity and distance to the nearest wall. Each time you scan a robot, you add that robot's state, represented as a point, to a list. For example, your list of robot states might consist of (8, 50), (7, 46), (6, 43), and (5, 40). Each point also has a value associated with it, which is usually an entry in a linked list that describes the enemy robot's movements over time.

When our gunheat reaches zero, it's firing time. First, we calculate the point that describes the enemy's current state. Then, we loop through our list of points, for each one calculating the distance from the current point. We take the closest point, retrieve the linked list entry associated with it, and use play-it-forward targeting to aim our gun at the predicted position of the enemy.

Everything works perfectly until about 10 rounds. Our robot begins to slow down, starts skipping turns, and eventually becomes disabled. Why? Because as the number of points increases, the time it takes to search them through increases proportionally. The solution is a kd-tree. A kd-tree stores points in an efficient tree-based data structure that takes O(log(n)) time to search through. The result is a fast robot that is able to handle many more dimensions that describe a state far more accurately than just 2 could. You could also find more than one point, predict more than one target, and shoot at clumps of targets (see Shadow's melee gun) for increased accuracy.

Bucket PR kd-tree

Bucket PR kd-trees have two characteristics:

• Bucket means points are collected in leaves until they overflow. Only then are they split. This makes the tree more likely to be balanced since we can choose a smarter splitting point than whatever we receive first.
• PR stands for Point-Region. The tree recursively splits its region into two equally-sized areas, regardless of the position of the actual data, until buckets no longer overflow. This is more likely to retain balance if the data is evenly distributed since the final tree does not depend on the order of the data. If the data is closely clustered, however, this can result in an excessively deep tree.

For an applet demo, see Spatial Index Demos. The example there cycles partitioning axes in a fixed order, while most authors use a more intelligent algorithm. Rednaxela's kd-tree, for example, splits on the widest dimension.

Implementations

There are several implementations of kd-tree around Robocode's community, and most if not all of them are bucket PR kd-trees:

• Rednaxela's kd-tree: Tied for the fastest and most efficient kd-tree around today.
• Skilgannon's kd-tree: On par with Rednaxela's tree, possibly faster in cache-intensive conditions.
• Duyn's kd-tree: Another highly optimized kd-tree implementation. See also Duyn's kd-tree tutorial.
• Chase's KD-TreeC: A fair tree and the only one that includes range searching.
• Simonton's kd-tree: The first bucket PR kd-tree in Robocode community.

See also

• Dynamic Clustering