Traceline

From HIVE
Jump to: navigation, search


Traceline is an algorithm that finds closest unit in a line. It is used for FPS, to determine whether a fired bullet has hit any units. The algorith is HORRIBLY INEFFICIENT and should NEVER BE USED under any circumstances.

Short overview

Traceline algorithm is very simple. It establishes a small round region and direction, and then periodically shifts the region in given direction and searches it's area for any units.

Why is it so inefficient

The problem lies in the fact that searching for units in region is slow. This action has to go through all units on the map, and test their position against the region bounds. This is done usually ~50 times (50 region positions), each time going through all units.

What should be used

Much more efficient algorithm uses a single unit seach, and then compares all the units found against a line (using [[1]] calculation). See tutorial above.