Улучшить скорость функции

Question

Я играю в BattleShip в javascript с двигателем iio.

Я пытаюсь играть против компьютера, поэтому я должен поставить случайную позицию для кораблей (надеюсь, вы знаете игру :)).

У меня есть 5 кораблей, которые должны быть размещены в сетке (10x10). Проблема в том, что функция довольно медленная, и иногда страница вообще не загружается.

Я хочу знать, если есть некоторые улечшения для скорости этих функций, я немного новичок: D

function posShips(size){ 
    // var size -> size of the ship 
    var isOk = false; // flag var to check if the ship is in a right position 
    var isOk2 = true; // flag var, become false if the cell is already fill with another ship 
    var i; 
    var j; 
    var side; // horizontal or vertical 
    while(!isOk){ 
     i = iio.getRandomInt(1,11); 
     j = iio.getRandomInt(1,11); 
     side = iio.getRandomInt(0,2); 
     if((side ? j : i)+size-1 < 11){ // Not out of the array 
      for (var k = 0; k < size; k++) { // Size of the ship 
       if(side){ 
        if(gridHit[i][j+k].stat == "empty"){ //If is empty put the ship 
         gridHit[i][j+k].stat = "ship"; 
         gridHit[i][j+k].setFillStyle("red") 
        }else{ // If not empty 
         isOk2 = false; //Position is not good, do all the thing again. 
         for (var a = 0; a < size; a++) { // Reset cell 
          gridHit[i][j+a].stat = "empty"; 
         } 
         k = 10; 
        } 
       }else{ 
        if(gridHit[i+k][j].stat == "empty"){ //If is empty put the ship 
         gridHit[i+k][j].stat = "ship"; 
         gridHit[i+k][j].setFillStyle("red") 
        }else{ // If not empty 
         isOk2 = false; //Position is not good, do all the thing again. 
         for (var a = 0; a < size; a++) { // Reset cell 
          gridHit[i+a][j].stat = "empty"; 
         } 
         k = 10; 
        } 
       } 
      }; 
      if(isOk2) 
       isOk = true; 
     } 
    } 
} 

Answer 1

1. Не поднимайте корабельных позиции, которые будут выходить за пределы сетка. Сначала выберите направление, а затем ограничьте начальные позиции x и y на основании size. например если размер равен 3, для начального значения изменяющейся координаты нет точки выше 7.

2. Не изменяйте массив во время поиска. Сначала выполните поиск и только после этого обновите массив. Это позволяет избежать любой операции «очистки».

3. По возможности устраните повторяющиеся ссылки на глубокие объекты. Если вы повторно обращаетесь к grid[y][x] для разных x, сначала сделайте ссылку на grid[y], а затем используйте это для последующих обращений.

4. Прерывать петли рано, нет смысла продолжать проверку позиции, если предыдущая уже не выполнена.

5. Сначала разместите свои большие корабли - легче вместить небольшие корабли в промежутки, оставшиеся между большими.

См http://jsfiddle.net/alnitak/Rp9Ke/ для моей реализации, с эквивалентом вашей функции является следующее:

this.place = function(size) { 

    // faster array access 
    var g = this.grid; 

    // initial direction, and vector 
    var dir = rand(2); // 0 - y, 1 - x 
    var dx = dir ? 1 : 0; 
    var dy = dir ? 0 : 1; // or 1 - dx 

    LOOP: while (true) { 
     // initial position 
     var x = dir ? rand(10 - size) : rand(10); 
     var y = dir ? rand(10) : rand(10 - size); 

     // test points 
     var n = size, tx = x, ty = y; 
     while (n--) { 
      if (g[ty][tx]) continue LOOP; 
      tx += dx; 
      ty += dy; 
     } 

     // fill points 
     n = size; 
     while (n--) { 
      g[y][x] = size; 
      x += dx; 
      y += dy; 
     } 

     break; 
    } 
};