2
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ 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 :). \$\endgroup\$ – Corbin Jul 26 '13 at 9:43
  • \$\begingroup\$ 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 \$\endgroup\$ – julesanchez Jul 26 '13 at 9:45
  • \$\begingroup\$ @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. \$\endgroup\$ – Corbin Jul 26 '13 at 10:00
  • \$\begingroup\$ @Corbin The algorithm is actually fast enough for this scale of problem; there are typically under 10 wasted guesses. \$\endgroup\$ – Stuart Jul 27 '13 at 12:58
  • \$\begingroup\$ @Stuart Ah, teaches me to make assumptions :). Had assumed the implementation was fairly quickly done :). \$\endgroup\$ – Corbin Jul 28 '13 at 9:49
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.