Enhancement: Better location lookup algorithm for food and power-ups

[jjteoh-thewebdev]

Problem

function generateFood() {
  let newFoodX, newFoodY;
  do {
    newFoodX = Math.floor(Math.random() * GRID_SIZE);
    newFoodY = Math.floor(Math.random() * GRID_SIZE);
  } while (snake.some((part) => part.x === newFoodX && part.y === newFoodY));

  food = { x: newFoodX, y: newFoodY };
}

Current location lookup for food and power-up use a brute force approach(while not found, random select a cell). In late game, snake body may take up more cells. It may take longer time to resolve unoccupied cell.

Although this approach may not be a problem in a 20x20 grid size. I would like to lookup for any better alternative.

Suggestion

Requirements:

• 2D grid of size m x n
• Need to randomly select an available cell, one that hasn’t been used yet.
• Each cell can only be selected once
• Must be fast, ideally constant time

Lookup unoccupied location with Fisher-Yates shuffling.