Jump to content
  • Advertisement
Sign in to follow this  
Trillian

Generate a 2D grid of ascending numbers

This topic is 3676 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
 * 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.

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!