javascript - 1.000.000 单位军队的目标逻辑

Question

我正在为我的网站而战armyfight .可以有百万单位的战斗。我正在寻找更好的单位目标。在 jsfiddle是一个例子。

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};
};

我首先在 Y 轴上迭代，然后在 X 轴上迭代。但是在不同的军队阵地上，它给出了错误的结果。

在这个例子中，单位通过简单的迭代来寻找目标。对于百万级的大军战斗来说不是很好。
最好是像这里一样迭代，当迭代过程更快导致第一次成功时:

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

但此迭代仅适用于 0..100 或 99..100，但不适用于 100..0，因此我无法在反向模式下迭代对象。
所以如果 ally 是 {5 : {10: {}, 99: {}} 并且敌人在 {5: {100: {}}}，敌方单位会找到最近的盟友 [5, 10]而不是 [5, 99]。如果它是一个从 100 到 0 向后迭代的数组，那么它将是第一次成功。但是后来我遇到了关联数组的问题，它可以反向迭代吗？

请对结构有什么建议吗？也许将单位结构从对象更改为数组或混合？但是后来我遇到了关联数组的问题。我正在寻找有关结构的解释或示例，并寻找单位定位的更快迭代。

我也在寻找网站，在那里我可以问这些沉重的逻辑问题？我有更多。

Answer 1

出于性能原因，我会避免使用“find”之类的函数，而是使用某种索引访问。

例如，可以把你的单位放到hash中:

这个散列的键可以是一个字符串 xcoord+":"+ycord

此散列的值可以是您的对象的散列，由一些唯一的单元 ID 键控。所以，然后你可以通过检查当前单元格和周围 8 个单元格中的内容来搜索单元的邻居

我尝试了下面的代码，它在 1 秒内找到了所有 1M 单元的所有邻居。

    var units = {}

for(var i=0; i<1000000; i++) {
    var x = Math.floor(Math.random()*400);
    var y = Math.floor(Math.random()*400);
    var idx = x+":"+y;
    if(!units[idx])
        units[idx] = {};

    units[idx][i] = {
        id: i,
        x: x,
        y: y,
        //... other attributes of your unit
    };
};

// find neighbours for each unit;

console.log('Started lookups');
var start = new Date().getTime();

var keys = Object.keys(units);
for(var i=0; i<keys.length; i++) {
    var neighbours = findNeighbours(units[keys[i]]);
}

var finish = new Date().getTime();
console.log('Finished lookups in '+(finish-start));

function findNeighbours(unit) {
    var res = [];
    // check who is in all 9 cells
    // x     x     x
    // x    unit   x
    // x     x     x
    for(var i=0; i<3; i++) {
        for(var j=0; j<3; j++) {
            var idx = (unit.x+i-1)+":"+(unit.y+j-1);
            var unitsInCell = units[idx];
            if(unitsInCell) {
                var keys = Object.keys(unitsInCell);
                for(var j = 0; j<keys.length; j++)
                    res.push(unitsInCell[keys[j]]);
            }
        }
    }
}