Jump to content
  • Advertisement
Sign in to follow this  
Thomo

A simple but puzzling algorithm

This topic is 4426 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

I have a 10 * 10 grid labelled like this: 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21......etc. Later on I want to travers the grid square by square. However, instead of going in the traditional way: --------> --------> --------> --------> I want to go like this: -------> <------- -------> <------- Basically, I'm having trouble with the algorithm to do it, but it's giving me a headache. I was hoping someone might help. So far I have this....
gridPosition = 0;
	
	while (gridPosition < 100) {
		
		if (gridPosition != 0 && gridPosition % 10 == 0) { 
			
			gridPosition += 10;
			
		}
		
		else if ((gridPosition+1) % 10 == 0) {
		
			gridPosition += 10;
			
			
		}
		
		row = int(gridPosition / ROWS);
		col = gridPosition - row * COLUMNS;

                if (row % 2 == 0) {
				
			gridPosition++;
		}
			
		else if (row % 2 != 0){
			
			gridPosition--;
		}
		
		printf(gridPosition);

         }

Essentially, what it does is.....starts at n = 0. If the row is odd n is increased by 1. If the row is even n is decremented. if n is on the left/right edges it jumps to the next line immediately beneath it (i.e. n += 10). However, the edges are not printed since n jumps befre being printed. I've spent the last hour or so fiddling with it. Now, forgive me for being thick, but am I missing something completely obvious here.....it seems so to me :-) Can some advise me please...I have a bad ear :'-(

Share this post


Link to post
Share on other sites
Advertisement
In my opinion, it would be easier to think about it in terms of X and Y in 2D space. You can then convert the X and Y coordinate into an index by using:
idx = (y * width) + x;

where width in your case would be 10.

You could then iterate through the grid like so:
flip = false;

for (y = 0; y < 10; y++)
{
if (flip == false)
{
for (x = 0; x < 10; x++)
{
gridPosition = (y * 10) + x;

// ...do something with gridPosition...
}
}
else
{
for (x = 9; x >= 0; x--)
{
gridPosition = (y * 10) + x;

// ...do something with gridPosition...
}
}

flip = !flip;
}


Obviously there are better ways of traversing through the grid, but hopefully this should give you an idea as to how to start.

Share this post


Link to post
Share on other sites

//Here is how you compute row and column for your grid based on cell number:

row = cell / columns
col = row % 2 ? columns - cell % columns - 1 : cell % columns

//So you can traverse the cells like this:

int rows = 10;
int cols = 10;
for(int cell = 0; cell < rows * cols; ++cell) {
int row = cell / cols;
int col = row % 2 ? cols - cell % cols - 1 : cell % cols;
}

//You can also make a function:

void get_grid_coords(int cell int rows, int cols, int &row, int &col) {
row = cell / cols;
col = row % 2 ? cols - cell % cols - 1 : cell % cols;
}

//And use it like this:

int rows = 10;
int cols = 10;
for(int cell = 0; cell < rows * cols; ++cell) {
int row, col;
get_grid_coords(cell, rows, cols, row, col);
}




Simple isnt it.

Share this post


Link to post
Share on other sites
Your basic problem seems to be that, when you reach an edge, you update twice - once to get to the next row, and then once to begin traversing that row. Your numbers are actually going through the square in the right order, but the nines and zeroes are not getting printed because you update again before you reach the print statement. Try printing every time you change your position, and see if that doesn't help.

Share this post


Link to post
Share on other sites

int dir = 1;
for (int y = 0; y < 10; y++) {

for (int x = ((dir == 1) ? 0 : 9); x >= 0 && x <= 9; x += dir) {
// Whatver you want to do at x, y
}

// Swap the x traverse direction
dir = -dir;
}




That's nice and clean I think.

Share this post


Link to post
Share on other sites
In a similar vein (because I feel clever today):


for (int y = 0; y < rows; ++y) {
int start = 0, limit = columns, dir = 1;
for (int x = start; x != limit; x += dir) {
// do whatever
}
dir = -dir;
std::swap(start, limit);
start += dir; limit += dir;
}

Share this post


Link to post
Share on other sites
It is said that you are trying to traverse the grid boustrophedonically. If you check the dictionary, chances are you won't find this particular adverb, but you will find the base word "boustrophedon" which is an ancient form of writing wherein every second line is written backwards. It should be noted, however, that this term in not limited to writing. It is suitable for describing any occurance of this pattern.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
In a similar vein (because I feel clever today):


for (int y = 0; y < rows; ++y) {
int start = 0, limit = columns, dir = 1;
for (int x = start; x != limit; x += dir) {
// do whatever
}
dir = -dir;
std::swap(start, limit);
start += dir; limit += dir;
}


Your code does not do what you think it does.

You will always iterate forward under your code.

Better:

int sgn( int v ) { return v<0?-1:1; }

// ...

// intial open bounds for the interval in "x":
int x_left = -1, x_right = columns;

// start looping:
for (int y = 0; y < rows; ++y) {

// loop between the ordered open bounds x_left and x_right:
int dir = sgn( x_right - x_left );
for (int x = (x_left+dir); (x*dir)<(x_right*dir); x += dir) {
// do whatever
}

// change the order:
std::swap(x_left, x_right);
}

Share this post


Link to post
Share on other sites
Quote:
Original post by NotAYakk
Your code does not do what you think it does.


Should've posted why :-).

Instead of rewriting the whole durn thing, just bump the variable declarations outside the y loop so they persist :-).

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
Quote:
Original post by NotAYakk
Your code does not do what you think it does.


Should've posted why :-).

Instead of rewriting the whole durn thing, just bump the variable declarations outside the y loop so they persist :-).


I led the horse to water. Drinking is up to the horse.

Plus, Zahlman's implementation fails catastrophically when the width of a column is negative.

Mine fails less catetrophically! (I mean, if the client says the width of the column is -4, they do want you to iterate over -2 then -3, right? Right? ...)

To improve mine and make it extra robust:

  // intial open bounds for the interval in "x":
int x_left = -1, x_right = columns;
int dir = 1;

// start looping:
for (int y = 0; y < rows; ++y) {
// loop between the ordered open bounds x_left and x_right:
for (int x = (x_left+dir); (x*dir)<(x_right*dir); x += dir) {
// do whatever
}

// change the order:
std::swap(x_left, x_right);
dir*=-1;
}

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!