Category Archives: Algortihms and Data Structures

This category contains all posts relating to algorithms and data structures.

KD Tree

KD TreeThe KD Tree belongs to the topic algorithms and data structures. In this demo it is used to split the graphic scene into several parts and the objects, visualized as colored cubes, are stored in the leaves of the tree. With the help of this data structure it is possible to solve the nearest pair problem, which might be useful to find the nearest enemy or player in a computer game. But in the sample application here, the KD-Tree serves for something else, namely for collision detection. By pressing the Enter-Key it is possible to cast a ray (red) and then the nodes of the tree are searched for intersections. Finally only the objects in the leave nodes with intersections have to be checked for collisions with the ray. The hidden triangles are rendered in black. The same principle can be used for determining the visibility of objects.

The demo was developed with C# and XNA. The source code can be found on GitHub.

A* Search

A* SearchThis application shows, how to find the optimal path from one point to another with the help of the A* search. In doing so, the type of territory and the enemies moving on a two dimensional map are taken into consideration by calculating way costs for each field. On the picture you find the white point as start and the violet point as the target position. The big red points are visualizing enemies with their range as small red points. The hexagonal fields of the mapped are colored, for showing different types of territory: light green = grass, dark green = wood, blue = water and brown = mountain. Finally the orange points show the best possible solution for reaching the target and avoiding enemies.

It was developed with C++ and the game SDK ClanLib. The source code can be found on GitHub.