在网格上寻找空白空间的算法

Algorithm to find an empty space on a grid

本文关键字：空间 算法 空白 寻找 网格      更新时间：2023-09-26

我要创建一个蛇类游戏，你可以在这里看到:http://jaminweb.com/snake_TEST_PHP.php

当蛇的头碰到一块食物时，这块食物会重新出现在黑板上的其他地方，而不是蛇身上的地方。我处理这个问题的功能是简单地尝试板上的随机位置，直到。但我意识到，当蛇几乎占据了整个棋盘时，这可能需要进行大量的计算。

这是我的函数，它应该是不言自明的:

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);
    }
}

有没有人有更好的主意，或者有人能告诉我一个资源，在那里我可以了解我需要改进的任何类型的算法?

除非您有一些简单的方法来获取所有的空tile，否则您的方法是唯一真正的方法。但是，我建议将它包装在do while循环中，以避免递归:

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);
}

一个更好的解决方案是保留或生成一个包含所有空单元格的列表，然后简单地从该列表中随机选择一个单元格，这将避免在没有空闲空间时可能出现的无限循环。

简单的方法是找到所有占用的瓷砖，并将所有未占用的瓷砖放入列表中，然后选择并在列表中索引作为下一个放置食物的瓷砖。

如果你不是完全随机的，但有一点偏见，你可以做下面的事情:

  1. 生成一个随机行，保存为init_row
    2. 循环遍历所有列，将所有空单元格压入数组。
  2. 如果数组。长度，选择该数组的随机元素，返回(row,col)。
  4. 如果行!=init_row转到步骤2

  5. 否则，不要替换食物——没有空的方块，蛇会在下一步行动中死亡，或者应该赢，等等。

    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

该算法更有可能在空点很少的一行中选择一个空点，但它会"看起来"是随机的。(如果在检查empty_y数组之前循环遍历所有tx，它将是真正随机的，但这不是必要的。)

看起来。translate()和。copy()例程也很繁重…您可能想要创建一个[max_y, max_x]数组并标记/取消标记已占用的正方形，以便您可以更快速地进行检查。

你可以为每个贴图添加一个名为"occupied"的属性，并在蛇出现时将其设置为true，或者创建一个空贴图数组，只从那里随机选择，但这可能需要更多的计算，因为它需要不断检查蛇的位置。

相关文章：