🐍 Snake Solver

Web ページがゲームを進行し、UIAPduino は 次の方向 を返すだけです。

1レベルの通信の流れ:
CMD_RESET → UIAPduino がボードと岩をリセット
CMD_ROCK → 岩の座標を1個ずつ送信（複数回）
CMD_START → UIAPduino が初期化して最初の方向を送信
CMD_TICK → 1マス移動するたびに呼ばれる。次の方向を送信
CMD_DIR → UIAPduino が Web に返す移動方向

SnakeHID クラスのメソッド:
snake.sendDir(dx, dy) — 次の方向を送信（必ず呼ぶ）

方向の表現:
dx=+1, dy= 0 → 右   dx=-1, dy= 0 → 左
dx= 0, dy=+1 → 下   dx= 0, dy=-1 → 上

UIAPduino はボードと岩の状態を自分で管理します:

bool board[16][16]; // スネークが占有 → true
bool rocks[16][16]; // 岩がある    → true
uint8_t headX, headY;

// CMD_RESET 受信時: すべてクリア
void clearAll() {
    for (uint8_t y = 0; y < 16; y++)
        for (uint8_t x = 0; x < 16; x++) {
            board[y][x] = false;
            rocks[y][x] = false;
        }
}

// CMD_ROCK 受信時: 岩を登録
rocks[buf[2]][buf[1]] = true;

// CMD_TICK 受信時: 頭の位置を更新
headX = buf[1]; headY = buf[2];
board[headY][headX] = true;

次の移動先が board[ny][nx] または rocks[ny][nx] なら衝突するので避ける必要があります。

まずは「衝突しない方向を選ぶ」だけの実装から始めてみましょう:

void computeNextDir(int8_t& outDx, int8_t& outDy) {
    const int8_t DDX[] = { 1, 0, -1,  0 };
    const int8_t DDY[] = { 0, 1,  0, -1 };

    for (uint8_t d = 0; d < 4; d++) {
        int16_t nx = (int16_t)headX + DDX[d];
        int16_t ny = (int16_t)headY + DDY[d];
        // 壁チェック
        if (nx < 0 || nx >= 16 || ny < 0 || ny >= 16) continue;
        // 自分・岩チェック
        if (board[ny][nx] || rocks[ny][nx]) continue;
        // 進める！
        outDx = DDX[d];
        outDy = DDY[d];
        return;
    }
    // 逃げ場なし
    outDx = 1; outDy = 0;
}

これだけでも動きますが、行き止まりに入り込みやすいです。ヒント 4 を参照。

4方向それぞれについて BFS で到達可能なセル数を数え、 最も広い空間につながる方向を選びます。 岩がある場合でも有効です:

// BFS用グローバルキュー（スタック節約のため）
uint8_t bfsQx[256], bfsQy[256];

uint16_t countReachable(uint8_t sx, uint8_t sy) {
    bool visited[16][16] = {};
    const int8_t dx[] = { 1, 0, -1, 0 };
    const int8_t dy[] = { 0, 1,  0,-1 };
    uint16_t head = 0, tail = 0;
    bfsQx[tail] = sx; bfsQy[tail] = sy; tail++;
    visited[sy][sx] = true;
    while (head < tail) {
        uint8_t x = bfsQx[head], y = bfsQy[head]; head++;
        for (uint8_t d = 0; d < 4; d++) {
            int16_t nx = (int16_t)x+dx[d], ny = (int16_t)y+dy[d];
            if (nx<0||nx>=16||ny<0||ny>=16) continue;
            if (visited[ny][nx]||board[ny][nx]||rocks[ny][nx]) continue;
            visited[ny][nx] = true;
            bfsQx[tail]=(uint8_t)nx; bfsQy[tail]=(uint8_t)ny; tail++;
        }
    }
    return tail; // 到達できたセル数
}

void computeNextDir(int8_t& outDx, int8_t& outDy) {
    const int8_t DDX[]={1,0,-1,0}, DDY[]={0,1,0,-1};
    uint16_t best = 0; bool found = false;
    for (uint8_t d = 0; d < 4; d++) {
        int16_t nx=(int16_t)headX+DDX[d], ny=(int16_t)headY+DDY[d];
        if (nx<0||nx>=16||ny<0||ny>=16) continue;
        if (board[ny][nx]||rocks[ny][nx]) continue;
        uint16_t cnt = countReachable((uint8_t)nx,(uint8_t)ny);
        if (!found||cnt>best) { best=cnt; outDx=DDX[d]; outDy=DDY[d]; found=true; }
    }
    if (!found) { outDx=1; outDy=0; }
}