Оптимизация сокращения вложенных объектов и массивов в Javascript - PullRequest
Новая
       17

Оптимизация сокращения вложенных объектов и массивов в Javascript

0 голосов
/ 01 мая 2020

Я пишу алгоритм движения армии для игры. У меня есть рабочий код, однако он имеет три вложенных оператора for для итерации по довольно большим коллекциям объектов. Это приведет к анимации и будет работать со скоростью примерно 60 кадров в секунду. Я хочу оптимизировать это для производительности.

Исходная позиция - это массив ( армия ) объектов ( единиц) ). Каждый объект объекта имеет два атрибута:

( unit.pathChain ) - массив массивов, обозначающих полную цепочку пути между двумя узлами (например, перемещение от узла A к узлу C через узел B будет выглядеть так [[A, B], [B, C]]).

( unit.distance ) - целое число, описывающее это расстояние, пройденное только по первому пути цепочки путей.

Задача алгоритма состоит в том, чтобы уменьшить все возможные пути с их минимальным пройденным расстоянием (расстояния считаются 0 для всех путей за пределами первого. Для первого пути в цепочке расстояние наследуется от единицы.

Я написал следующее, и это работает однако это интуитивно кажется неуклюжим и медленным, и я изо всех сил пытаюсь оптимизировать его (для производительности - не специально для длины кода / стиля и т. д. c). 

//set up test units with distances and pathchains
let unit1 = {distance: 5, pathChain: [["a", "b"]]};
let unit2 = {distance: 2, pathChain: [["c", "d"],["d", "e"]]};
let unit3 = {distance: 1, pathChain: [["c", "d"],["d", "a"],["a","b"]]};
let unit4 = {distance: 6, pathChain: [["a", "b"]]};
let unit5 = {distance: 3, pathChain: [["e", "f"]]};
let unit6 = {distance: 4, pathChain: [["e", "f"]]};

//assign test units to an army
let army = [unit1, unit2, unit3, unit4, unit5, unit6];

//container for results
let resultObjects = [];

//iterate over all units
for (let i = 0; i < army.length; i++){
  let unit = army[i];

  //for each unit iterate over each path chain
  for (let i2 = 0; i2 < unit.pathChain.length; i2++){
     let testingPath = unit.pathChain[i2];
     let pathFound = false;

     //testing distance is 0 unless it is the first path in the chain in which case distance is inherited from unit
     testingDistance = 0;
     if(i2 == 0){
       testingDistance = unit.distance;
     }

     //iterate over all previously seen paths
     for (let i3 = 0; i3 < resultObjects.length ; i3++){
       let resultObject = resultObjects[i3];
       let resultPath = resultObject.path;
        //test to see if we have already seen this path before
        if (testingPath[0] == resultPath[0] && testingPath[1] == resultPath[1]){
          pathFound = true;
          //if we have seen this path before but this path has a lower distance update the result record to denote a lower distance
          if (testingDistance < resultObject.minimumDistance){
            resultObject.minimumDistance = testingDistance;
          } 
        }
     }

     //if we have not seen this path before add it to the results array
     if (pathFound == false){
       let newResultObject = {path:[testingPath[0], testingPath[1]], minimumDistance: testingDistance};
       resultObjects.push(newResultObject);
     }
  }
}
console.log(resultObjects);

Ожидаемый результат: 

//results should be:
//[
//   {'path':['a','b'],'minimumDistance':0}
//  ,{'path':['c','d'],'minimumDistance':1}
//  ,{'path':['d','e'],'minimumDistance':0}
//  ,{'path':['d','a'],'minimumDistance':0}
//  ,{'path':['e','f'],'minimumDistance':3}
//]
...