CODEWITHSUNDEEP
javascriptalgorithm
Suck At Coding
Suck At Coding

Reputation: 27

Algorithm to find an empty space on a grid

So I'm creating a snake game, which you can see here: http://jaminweb.com/snake_TEST_PHP.php

When the snake's head hits a piece of food, the piece of food reappears somewhere else on the board, somewhere that is not on the snake. My function for handling this is simply to try random locations on the board until . But I realize this could involve a lot of computations when the snake has nearly taken up the entire board.

Here's my function, which should be self-explanatory:

this.moveFood = function(bbf) {
    /*
        bbf: bounding box for the food
    */
    var tx = randInt(0, C_w / this.linkSize - 1) * this.linkSize - bbf.x;
    var ty = randInt(0, C_h / this.linkSize - 1) * this.linkSize - bbf.y;
    var fcopy = this.food;
    fcopy.translate(tx, ty);
    if (!this.hitSnake(fcopy)) {
        this.food.translate(tx, ty);
    } else {
        this.moveFood(bbf);
    }
}

Does anyone have a better idea, or can anyone direct me to a resource where I can learn about whatever types of algorithms I'm going to need to improve on this?

Upvotes: 1

Views: 3685

Answers (4)

Sathania
Sathania

Reputation: 89

You could add a property to each tile called "occupied" and set it to true when the snake is in there, or make an array of the empty tiles and only select randomly from there, but that might take even more computation since it needs to be constantly checking where the snake is.

Upvotes: 0

jimm101
jimm101

Reputation: 998

If you're not committed to something that's completely random, but has a slight bias, you can do something like the following:

  1. Generate a random row, and save row as init_row.
  2. Loop through all columns, pushing any empty cells into an array.
  3. If array.length, pick a random element of that array, return (row,col).
  4. Else, increment row with wrapping (row = (row+1) % C_w)
  5. If row!=init_row go to step 2.

  6. Else, don't replace the food--there's no empty squares, snake will die on next move, or should win, etc.

    var empty_y;
var max_x = C_w / this.linkSize - 1) * this.linkSize - bbf.x;
var max_y = C_h / this.linkSize - 1) * this.linkSize - bbf.y;
init_tx = randInt(0, C_w / this.linkSize - 1) * this.linkSize - bbf.x;
tx = init_tx;
do {
    empty_y = [];
    for( y=0; y<max_y; y++) {
        var fcopy = this.food;
        fcopy.translate(tx, y);
        if(!this.hitSnake(fcopy)) {
            empty_y.push(y);
        }
    }
    if( empty_y.length > 0 ) {
        int r = randInt(0,empty_y.length);
        this.food.translate(tx,empty_y(r));
        return;
    }
    tx = (tx+1) % max_x;
} while( tx != init_tx );
// handle case where there is no open spots left

The algorithm is more likely to pick an empty spot in a row with few empty spots, but it will "look" random. (If you loop over all the tx before checking the empty_y array, it will be truly random, but it's not necessary.)

It also looks like the .translate() and .copy() routines are heavy lifting ... you might want to create a [max_y, max_x] array and mark/unmark occupied squares, so you can check more quickly.

Upvotes: 0

Vikram Bhat
Vikram Bhat

Reputation: 6246

easy way to do this is find all occupied tiles and put all unoccupied tiles and put them in a list and select and index in the list as the next tile to place the food.

Upvotes: 0

Sinkingpoint
Sinkingpoint

Reputation: 7624

Unless you have some easy method of getting all the empty tiles, your method is the only real way to do it. I would recommend wrapping it in a do while loop however, to avoid recursion:

this.moveFood = function(bbf) {
/*
    bbf: bounding box for the food
*/
    do{
        var tx = randInt(0, C_w / this.linkSize - 1) * this.linkSize - bbf.x;
        var ty = randInt(0, C_h / this.linkSize - 1) * this.linkSize - bbf.y;
        var fcopy = this.food;
        fcopy.translate(tx, ty);
        if (!this.hitSnake(fcopy)) {
            this.food.translate(tx, ty);
        }
   }while(this.hitSnake(this.food);
}

A better solution would be to either keep or generate a list of all the empty cells and then simply select a random cell from that list which would avoid a potential infinite loop if there isn't a free space.

Upvotes: 1

Related Questions