I am making a game in elm and trying to randomly place N evil robots on a grid with ROWS x COLS cells.
What I would like is a List (Int, Int) pairs that specifies where to place the N robots.
I can make a List of coordinate pairs with
makeGrid : Seed -> List (Int, Int)
makeGrid seed =
let gen = list n <| pair (int 0 rows) (int 0 cols)
in
fst (generate gen seed)
That's fine. But if I want to generate a list of unique pairs?
Should I do the imperative solution where I keep a Set of my things and loop through adding until I have enough?
Maybe something like this (probably wrong, didn't check it in the REPL):
makeN : Int -> Seed -> (List (Int, Int), Seed)
makeN n seed =
let gen = list n <| pair (int 0 rows) (int 0 cols)
in
generate gen seed
makeGrid : List(Int, Int) -> Seed -> Int -> List (Int, Int)
makeGrid partial seed n =
case of List.length partial
n -> partial
current ->
let (new_elems, new_seed) = makeN (n - current) seed
makeGrid Set.toList (Set.fromList <| append partial new_elems) new_seed n
This feels off. I've thought of 3 alternatives:
-
Make my grid a list of ROWS * COLS coordinate pairs with type List (Int, Int), then shuffle it, and take the first N pairs in the list to place my robots on. This seems very concise and clean, but inefficient/bad if the number of unique points I need is much smaller than my grid, and if my grid is big (as Fisher-Yates is O(n log(n)) I think).
-
Use something like this package to sample from my grid without replacement, but I need to change my grid into an Array and it looks like it does a lot of splitting and splicing Array operations, which look costly.
-
Use the JS FFI to implement this in a 4 line JS loop.
None of these solutions feel good, is there something I'm missing? I'm probably going to just change the game mechanics to that each cell has a probability P of having a robot on it, so that it's simpler to implement.
Aucun commentaire:
Enregistrer un commentaire