0

I am making a snake game in javascript and I need a way to choose a random position for the fruit (a single number on which modulus is applied to get the x and y numbers) but the position should not overlap with positions the snake is already covering. I'm currently using recursion to do this:

function random(min = 0, max = 100, exclude = []) {
  let r = Math.round(Math.random() * (max - min)) + min;

  return exclude.includes(r) ? random(...arguments) : r;
}

When the snake covers a large portion of the board leaving only a few spaces for the fruit, this would take a lot of cycles to return a valid number.

Is there a better method to do this or is this method good enough?

code913
  • 43
  • 6
  • Yes, there is: replace recursion with a `while` loop and convert `exclude` into a `Set`. – InSync Mar 29 '23 at 11:27
  • 2
    Create an array of non-excluded numbers first, then randomly select an index. – Jonathan Hall Mar 29 '23 at 11:27
  • Also you want `Math.floor` not `Math.round` to accurately adhere to your range. – pilchard Mar 29 '23 at 11:33
  • IMO this is an interesting sample of big-O vs. real world performance: your current algorithm is theoretically unbounded (i.e. it could loop infinitely) wheras the one suggested by Jonathan has a definite upper bound. But depending on the specific implementation either one could perform better in real-world examples. – Joachim Sauer Mar 29 '23 at 11:39
  • related: [In Javascript generate a random whole number excluding array of numbers](https://stackoverflow.com/questions/57639315/in-javascript-generate-a-random-whole-number-excluding-array-of-numbers) – pilchard Mar 29 '23 at 11:39

1 Answers1

0

Create an array of "valid" numbers and select a random member of it:

function random(min = 0, max = 100, exclude = []) {
    let free = []
    for (let r = min; r <= max; r++) {
        if (!exclude.includes(r))
            free.push(r)
    }
    return free[Math.floor(Math.random() * free.length)]
}

This way there will be no need for trial and error loops.

gog
  • 10,367
  • 2
  • 24
  • 38
  • This creates a full array every call, surely a `while` loop with an `includes` check is faster, since it exits early. – pilchard Mar 29 '23 at 11:35
  • If `min` and `max` are far apart and `exclude` is very small (or even empty) I doubt this will perform better than OP's original approach – Mureinik Mar 29 '23 at 11:37
  • @Mureinik: the OP provided the context, `max-min` is guaranteed to be very small. – gog Mar 29 '23 at 12:06