You can find data files in "resources" directory.
First line of each file contains angle of sector and view distance.
Other lines contain position and view vectors.
There is 2D field. It contains many units. Each unit have position and view direction (radius-vector). All units have constant view distance. You should give an answer, how many units can each unit see?
2D battleground is CellList. Side of each cell equals view distance.
This helps to reduce calculations from O(n^2) to O(n) (if units can't see whole map, I hope they don't).
Multithreading is done using async.
We divide all units into batches and let each thread calculate its batch.
Also, there is mutex pool, because neighbours are calculated and used on run (lazy).
If neighbours >= 4, then we can use SIMD to calculate 4 vectors simultaneously (if I did it right).
Other neighbours would be calculated using slow alghorithm.
All units are stored in heap.
Also, I used heap-allocated dynamic arrays to work with SIMD.
TODO
CalculationsUNIT - main unit
NEIGHBOUR - other unit
b - vector from UNIT to NEIGHBOUR
a - unit vector of view
alpha - angle between vectors a and b
How can we know if NEIGHBOUR is in sector of UNIT?
- |b| <= distance view
- alpha <= sector angle / 2
Let's find cos alpha:
cos(alpha) = dot(a, b) / |b|
Now we can compare cos(alpha) and cos(sector angle / 2).
You can find tools in "tools" directory.
data_generator.py
Units generator. You can modify parameters in script.
python3 data_generator.py <FILE_NAME_TO_GENERATE> <NUMBER_OF_ELEMENTS>
Will create file "data.txt" with random 100 units in it.
python3 data_generator.py data.txt 100
data_visualizer.py
Units visualizer. Will visualize your units ¯_(ツ)_/¯
python3 data_visualizer.py <FILE_NAME_TO_READ> <no/yes>
Last optional parameter asks user if they would like to see number of each unit (this info can lead to low performance : c).
Will read and visualize file "data.txt". Number of each unit is also printed.
python3 data_visualizer.py data.txt
Your map will look like this.
Each green point is unit.
Each cell is cell in CellList structure
You can zoom it. Amazing!