Improve performance Javascript function

Question

I'm doing a BattleShip game in javascript with iio engine.

I'm trying to play against a computer so I have to put a random position for the ships (I hope you know the game :) ).

I have 5 ships that have to be placed in a grid (10x10). The problem is that the function is pretty slow, and sometimes the page don't get load at all.

I want to know if there are some emprovement for the speed of these function, I'm a little bit newbie :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;
 }
 }
}

• Corbin: The problem is the algorithm: you need something better than while (!allPlaced) { do { pos = randPos(); } while (shipAt(pos)); positions.add(pos); }. 5 ships on a 100 point grid are going to take up quite a bit of the possible placements, meaning lots of wasted guesses. Unfortunately though, I have no idea what algorithm to use here. I suspect it's going to have to be heuristic, but other than that I have no help to offer. I just think your question is very interesting :).
• julesanchez: Some pure javascript technicals stuff : Declare your 'a' and 'k' variable (use in for) outside of your while (you will redeclare your variable each time), and change if(isOk2) isOk = true , by isOk = isOk2;testing variable is slower that setting it : jsperf.com/test-vs-set
• Corbin: @julesanchez Because of variable hoisting, a and k are actually declared outside of the while loop. For that very reason though, he should still declare them at the scope where they're actually declared.
• Stuart: @Corbin The algorithm is actually fast enough for this scale of problem; there are typically under 10 wasted guesses.
• Corbin: @Stuart Ah, teaches me to make assumptions :). Had assumed the implementation was fairly quickly done :).

Answer 1

This is not really a speed issue; there are a couple of problems with your code that prevent it from working properly.

The most serious problem is that, if the position is not good you set isok2 = false. The while loop then picks another position. But nothing resets isok2 to true. So in fact, if the function does not find a good position on the first attempt, it will continue to loop indefinitely, which is why the page does not load.

A second problem is that when the position is not good you set all of the cells to empty.

for (var a = 0; a < size; a++) { // Reset cell
 gridHit[i][j+a].stat = "empty";
}

but this overwrites other ships that might have been in that space. A better approach would be to find an appropriate space first, and only once the whole space has been checked, start filling that space with 'ship' cells. Then you don't have to worry about resetting cells you have started filling before realising the space was blocked.

Some other comments:

(1) Instead of using the condition if((side ? j : i)+size-1 < 11) to check if the position is within the grid, it would be better to make sure that the random numbers chosen are within the grid in the first place:

i = iio.getRandomInt(1, side ? 11 : 11 - size);
j = iio.getRandomInt(1, side ? 11 - size : 11);

(2) Instead of setting k = 10 to break out of the loop, simply use break.

(3) Debug what is happening in your code by strategically placing console.log commands.

(4) It's often cleaner to use functions and return statements rather than flags. For instance, you could have a function like this within your main function:

function blocked() {
 for (var k = 0; k < size; k++) {
 if (side ? grid[i][j + k] : grid[i + k][j]) {
 return true;
 }
 }
}

Here is a jsfiddle demonstrating these points (in the function makeEnemyShip). It uses the same basic algorithm that you do and there is no speed problem.