In the "bad" exemple, there's no way to go from 1 to 3 or from 1 to 7 without making a "descending" move.
And no, this is not a homework assignment, I want to use this for map generation with unlockable areas.
Thanks!
[Edited by - Trillian on November 22, 2008 1:50:34 PM]
Generate a 2D grid of ascending numbers
Author
Hello,
Does anyone know a good way to generate a 2D grid of numbers that respect the following criterion:
- Each cell contains a number from 1 to the number of cells
- Two different cells cannot have the same value
- There must be at least one way to traverse the grid by moving using adjacent cells (no diagonals moves) from the "1" cell to any other cell with all moves being ascending relative to their value.
- The algorithm should rely on a random number generator to generate numerous different solutions.
Here's an exemple:
In the "bad" exemple, there's no way to go from 1 to 3 or from 1 to 7 without making a "descending" move.
And no, this is not a homework assignment, I want to use this for map generation with unlockable areas.
Thanks!
[Edited by - Trillian on November 22, 2008 1:50:34 PM]
In the "bad" exemple, there's no way to go from 1 to 3 or from 1 to 7 without making a "descending" move.
And no, this is not a homework assignment, I want to use this for map generation with unlockable areas.
Thanks!
[Edited by - Trillian on November 22, 2008 1:50:34 PM]
There's an inconsistency in your example and your requirements.
You said, "There must be a way to traverse the grid," emphasis on "at least one way."
But you denied your "bad" example because there was a way that didn't satisfy your requirements. That doesn't mean there ISN'T another way which does. So it's also a 'good' example according to your rules.
"There exists" and "for all" are very different things, so rethink what you want from this problem.
Btw, you also said "from the '1' cell to the 'max' cell," but neither of your examples go to the 'max' cell.
You said, "There must be a way to traverse the grid," emphasis on "at least one way."
But you denied your "bad" example because there was a way that didn't satisfy your requirements. That doesn't mean there ISN'T another way which does. So it's also a 'good' example according to your rules.
"There exists" and "for all" are very different things, so rethink what you want from this problem.
Btw, you also said "from the '1' cell to the 'max' cell," but neither of your examples go to the 'max' cell.
Author
You're right, I wasn't very clear, and I made a mistake, I meant from the "1" cell to any other cell.
I've edited my original post and changed my illustrations. I hope its clearer now.
I've edited my original post and changed my illustrations. I hope its clearer now.
* Pick a random square and place 1 there. * for i=2 to n * pick a random square that is adjacent to a square that already has a number assigned and place i there.
Author
Quote:Original post by alvaro* Pick a random square and place 1 there. * for i=2 to n * pick a random square that is adjacent to a square that already has a number assigned and place i there.
Yes, but how do you go finding a square that is adjacent to a square that already has a number without brute-forcing something that would be completely inefficient for large grids?
The only way to implement this algorithm that I can currently think of would be something like:
* Pick a random square and place 1 there* Build a list of empty cell coordinates* While that list is not empty * Pick a random empty cell coordinate from the list * If the empty cell at that coordinate is adjacent to a filled cell * Fill the cell with the next number * Remove the cell coordinate from the listBut the big problem with this is the "pick a random value and throw it away if its not OK" thing in a loop, which I'd like not to have. Is there an alternative algorithm that could guarantee that at least new cell is filled at the end of each pass?
Thanks
Quote:Original post by Trillian
Yes, but how do you go finding a square that is adjacent to a square that already has a number without brute-forcing something that would be completely inefficient for large grids?
Manage a list of neighbours to occupied squares.
Author
Quote:Original post by DevFredQuote:Original post by Trillian
Yes, but how do you go finding a square that is adjacent to a square that already has a number without brute-forcing something that would be completely inefficient for large grids?
Manage a list of neighbours to occupied squares.
Wow, its much simpler than I expected, I should have thought about it! I just did a quick implementation and it works as expected, and performs well for 100x100 grids, which should be more than enough. Thanks a lot for your solution!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
