# Targeting logic for 100.000 units army

I am making an army fight for my website armyfight. There can be fights of hundreds of thousands units. I am looking for better unit targeting. in jsfiddle is an example.

var enemy = {
2: {
3: {}  // object inside with unit data
},
5: {
6: {}
}
}

var ally = {
4: {
3: {}
}
}

function unit_searches_for_target(y, x) {
var closest_y   = iterate_Y(y);
var unit_target = iterate_X(closest_y, x);
return unit_target;
}

// Searches for closest target at Y axis
function iterate_Y(y) {
if (_.has(target, y)) {
return y;
} else {
var y = parseInt(y);
for (var i = 1; i < 300; i++) {
// If y == 4, it checks 4+1=5 (positive side)
if (_.has(target, String(y + i))) {
return (y+i);
// Else if y == 4, it checks 4-1=3 (negative side)
} else if (_.has(target, String(y - i))) {
return (y-i);
}
}
}
// if didn't find anything, just returns same y as given
return y;
};

// Searches for closest target at X axis
function iterate_X(y, x) {
if (_.has(target[y], x)) {
return {y: y, x: x};
} else {
var x = parseInt(x);
for (var i = 1; i < 300; i++) {
// If x == 4, it checks 4+1=5 (positive side)
if (_.has(target[y], String(x + i))) {
return {y: y, x: x + i};
// Else if x == 4, it checks 4-1=3 (negative side)
} else if (_.has(target[y], String(x - i))) {
return {y: y, x: x - i};
}
}
}
// if didn't find anything, just returns same x as given
return {y: y, x: x};
};


Here first i iterate on Y axis, later on X axis. But on different army positions it gives wrong results.

In this example, units are looking for targets by simply iterating. It is not very good for a huge army fight of hundred thousands units.
Best would be to iterate like here, when iteration process is much faster leading to first-hit success:

function iterate_X(y, x) {
return _.find(enemy[y], function (value, key) { return parseInt(key) >= x });
}


But this iteration works only 0..100, or 99..100, but not 100..0, so i can't iterate objects in reverse mode.
So if ally is {5: {10: {}, 99: {}} and enemy is at {5: {100: {}}}, enemy unit would find closest ally as [5, 10] instead of [5, 99]. If it would be an array iterating backwards from 100 to 0, so it would be first-hit success. But can asotiative array be reverse-iterated?

Any suggestions please on structure? Maybe change units structure from objects to arrays or mix? But then I have problems with associative arrays. I am looking for an explanation or example about the structure and for a faster iteration for units targeting.

And i am also looking for websites, where i could ask these heavy logic questions? I have more of them.

• You forgot to mention how you actually do want the targeting to work. Do you want them to just move towards the closest enemy or is there more to consider? Do you want them to move orthogonally, also diagonally or in any angle? And are there obstacles they need to move around? – Philipp May 22 '16 at 12:16
• thanks for a good question. i need targeting just to move towards enemies. they can move at any axis at any side. just like in my current project. i just need to find closest enemy to move towards it. yet there is no obstacles, so without them. – mansim May 22 '16 at 15:00

## 1 Answer

Organise your units in areas. An area can be a section in your grid (1

There are various implementations of quadtrees (Google is your friend).

This way a unit only has to iterate through the enemy units that are in neighboring quadtree spaces (or quadtree spaces within range of said unit).

This greatly speeds up the targetting/moving scenario's as each unit only has a subsection of the total number of units.

Once a unit moves, reorganise its position in the quadtree.