Sign in to follow this  
Trillian

Generate a 2D grid of ascending numbers

Recommended Posts

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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 list

But 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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
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.


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!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this