Traceline

From HIVE
Revision as of 21:43, 8 May 2011 by M0rt (talk | contribs) (Created page with "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'''...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to 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)