贪吃蛇游戏：寻求高效生成非蛇身区域苹果坐标的优化算法

我正在开发一款贪吃蛇游戏，需要在每次循环时将苹果放置在x*y规格的地图中，且苹果不能位于蛇身位置。

初始实现代码 #

// snake_body 是存储蛇身所有坐标的数组
snake_body := []

// 循环寻找不在蛇身里的坐标
function setApple()
    loop
        apple_x := random(map_x)
        apple_y := random(map_y)
        if (apple_x, apple_y) not in snake_body
            return apple_x, apple_y

这个设计在蛇身较短时效率尚可，但到游戏后期蛇身占据大部分坐标时，循环需要执行多次才能找到有效位置，效率低下。

当前尝试的解决方案 #

我目前的办法是创建并维护一个记录蛇未占用区域的坐标数组：

empty_ground := []

function refresh()
    // 每次循环用这个方法更新 empty_ground 里的元素

function setApple()
    return random(empty_ground)

但这种方式需要维护大型坐标表，更新时也会消耗算力，请问是否存在更优的算法可以快速解决该问题？

优化方案推荐 #

1. 二维转一维映射法

把地图的二维坐标(x,y)转换成一维索引idx = y * map_x + x，将整个地图转化为0到map_x*map_y-1的连续整数范围：

• 维护一个已占用索引集合（比如哈希集合），存储蛇身对应的一维索引，蛇身更新时只需添加/删除对应索引；
• 计算剩余可用位置数量available = map_x*map_y - 蛇身长度；
• 生成0到available-1之间的随机数r；
• 从0开始遍历整数，跳过已占用索引，找到第r+1个未占用索引，再转回二维坐标。

示例伪代码：

occupied := new HashSet()

// 蛇身更新时同步维护occupied集合
function updateSnakeBody(new_body)
    // 移除蛇身离开部分的索引
    // ...
    // 添加新进入蛇身部分的索引
    for (x,y) in new_body:
        idx = y * map_x + x
        occupied.add(idx)

function setApple()
    total = map_x * map_y
    available = total - occupied.size()
    r = random(0, available-1)
    count = 0
    for idx from 0 to total-1:
        if not occupied.contains(idx):
            if count == r:
                x = idx % map_x
                y = idx // map_x
                return (x,y)
            count += 1

2. 洗牌法（适合中小地图）

初始化时生成所有坐标的一维索引数组并打乱，通过指针快速取位：

• 游戏启动时，生成0到map_x*map_y-1的数组，随机洗牌；
• 维护一个指针ptr，初始指向数组开头；
• 每次放苹果时，取shuffled[ptr]转回二维坐标，然后ptr++；
• 当蛇移动导致尾部离开地图时，将尾部对应的索引插回数组的ptr位置，后续继续取用即可；地图快占满时重新洗牌一次。

这种方法生成苹果仅需O(1)时间，更新操作也极简。

3. 优化版拒绝采样

如果地图剩余空间还不算极小（比如剩余10%以上），可以优化初始采样逻辑：

• 将蛇身坐标存入哈希集合，让坐标判断变为O(1)时间；
• 设定最大尝试次数（比如5次），若多次采样都命中蛇身，直接切换到映射遍历法取位。

这种方法兼顾蛇身较短时的高效性，同时避免后期无限循环的问题。

内容的提问来源于stack exchange，提问作者bread