In a virtual game world, there exists a multitude of unit objects stored in an array.
These units are positioned on a 2D map with x and y coordinates.
let units = [
{id: 1, x=3450, y = 1456},
{id: 2, x=5560, y = 2423},
{id: 3, x=1321, y = 3451}
]
Every second, the game tasks each unit with compiling a list of other units within a specified distance for potential interactions like combat or evasion.
As the number of units grows into the thousands, the current method of each unit checking distances with every other unit becomes increasingly inefficient due to the exponential increase in tests required.
After researching similar issues online, an attempt was made to group units into row/column cells and only conduct distance tests on potentially relevant units. However, it was discovered that organizing these groups took longer than expected and did not provide significant benefits.
A testable version of the current code is provided below, taking approximately one second to complete on a standard browser. Suggestions for optimizations are welcomed to enhance performance significantly.
//create the world
let mapWidth = 5000;
let mapHeight = 2000;
let releventDistance = 200;
let unitCount = 5000;
//function to create a new unit at a random position on the map
function newUnit(id){
let newUnit = {};
newUnit.id = id;
newUnit.x = Math.floor(Math.random() * mapWidth);
newUnit.y = Math.floor(Math.random() * mapHeight);
//array of 'relevant' neighbors represents other units close enough for interaction
newUnit.neighbours = [];
return newUnit;
}
//simple distance calculation
function distance(unit1, unit2){
let dx = unit1.x - unit2.x;
let dy = unit1.y - unit2.y;
return Math.sqrt(dx * dx + dy * dy);
}
//array to store units
var myUnits = [];
//populate the unit array
for (let i = 0; i < unitCount; i++){
myUnits.push(newUnit(i));
}
console.log(unitCount + " units created");
//perform full scan using nested loops
let timeStamp1 = new Date();
myUnits.forEach(unit => {
myUnits.forEach(unit2 => {
//avoid testing a unit against itself
if(unit.id != unit2.id){
let unitDist = distance(unit, unit2);
if (unitDist <= relevantDistance){
unit.neighbours.push({unit : unit2, distance : unitDist});
}
}
})
})
//print results
console.log((new Date() - timeStamp1) + "ms: to complete bruteforce fullscan");
//calculate average number of neighbors
let totalNeighbourCount = 0;
myUnits.forEach(myUnit => {totalNeighbourCount += myUnit.neighbours.length});
console.log(Math.floor(totalNeighbourCount / myUnits.length) + ": average number of neighbours");