Array help needed

fletch

More a mathematical question than programming but I'll try explain as best I can.
So I have an array 16 * 16 in size. Suppose I have two players, at any one time their position in the array is displayed on an 8*8 grid. How can I determine if the two players are or are not in the same 8*8 grid??? Help is much appreciated...
The problem is language independent really....

feylya

If I understand you correctly, all you're really trying to do is find if the distance between the 2 players is less than 8 in both directions. Is that right?

fletch

feylya wrote:

If I understand you correctly, all you're really trying to do is find if the distance between the 2 players is less than 8 in both directions. Is that right?

Hmmm no I don't think that would do the trick.......if one player was in position [8][7] and the other was in [7][8] well then their distances apart is <8, however they are in different squares....

feylya

Ah, so you want to know what quadrant they're in? Why not give them a quadrant property based on their relation to [0] [0]. It's just a few if statements.

Tobias Greeshman

Why not have a function to test each quadrant

Boolean Check1stQuadrant ( array, player ) ;
Boolean Check2ndQuadrant ( array, player ) ;
Boolean Check3rdQuadrant ( array, player ) ;
Boolean Check4thQuadrant ( array, player ) ;

Fairly straightforward really with just tweaking loop guards to search certain parts of the array.

fletch

Right...the above I gave is merely an extract from a much larger grid....didn't want to complicate things....so the Check1stQuadrant method doesn't really apply here since in reality I have many more quadrants than 4.
I was thinking of the Euclidean distance and other such methods but to no avail.

Mutant_Fruit

EDIT: Rather than give you the answer, i'll give you a hint... Send the top left box from each 8x8 square into a function called "CheckIsInSquare" and then it should be a simple matter to see if each "player" is in the same 8x8 square.

To do this just design an algorithm to move through your array to pick the top-left box of each 8x8 square. This should be easy enough to manage. I did this for a sudoku solving program before when i had to check if a number was already in a 3x3 square.

EDIT2: This would be a very wasteful method if your grid is quite big. A better approach would be to take each players 'x' and 'y' coordinate and get the corresponding coordinates for the top-left box in the square they're in. If those coordinates for the top left box are the same for each player then they're in the same square.

fletch

Mutant_Fruit wrote:

EDIT: Rather than give you the answer, i'll give you a hint... Send the top left box from each 8x8 square into a function called "CheckIsInSquare" and then it should be a simple matter to see if each "player" is in the same 8x8 square.

To do this just design an algorithm to move through your array to pick the top-left box of each 8x8 square. This should be easy enough to manage. I did this for a sudoku solving program before when i had to check if a number was already in a 3x3 square.

EDIT2: This would be a very wasteful method if your grid is quite big. A better approach would be to take each players 'x' and 'y' coordinate and get the corresponding coordinates for the top-left box in the square they're in. If those coordinates for the top left box are the same for each player then they're in the same square.

Hmmm definitely given me something to think about! Thanks

fletch

Thanks a lot Mutant_Fruit....got it workin....nice one!

Mutant_Fruit

fletch wrote:

Thanks a lot Mutant_Fruit....got it workin....nice one!

Excellante, i assume you used the second option i mentioned. I think it'd be by far the most efficient method.

Also, could i see the code you used to work out your answer? Just out of interest

Mr.StRiPe

Something like this might be more efficient where P1_Pos and P2_Pos contain the respective players x and y position coordinates.

#define GRID_SIZE	8

bool PlayersInSameGrid(int P1_Pos[], int P2_Pos[])
{
	if((P1_Pos[0]/GRID_SIZE) == (P2_Pos[0]/GRID_SIZE))
	{
		if((P1_Pos[1]/GRID_SIZE) == (P2_Pos[1]/GRID_SIZE))
			return true;
	}

	return false;
}

Mutant_Fruit

Mr.StRiPe wrote:

Something like this might be more efficient where P1_Pos and P2_Pos contain the respective players x and y position coordinates.

Aye, doing that is what i was thinking of. By dividing by 8, you're going to "round down" to the nearest int, and so getting the coordinates for the top left corner of each square. You made it a little more efficient though

fletch

Hmm my code looks a bit different but it still works

function  InSameSquare (p1X, p1Y, p2X, p2Y)
{
          while( (p1X % sizeOfGrid)!=0 )
                 p1X = p1X - 1;
          while( (p1Y % sizeOfGrid)!=0 )
                 p1Y = p1Y - 1;          
          while( (p2X % sizeOfGrid)!=0 )
                 p2X = p2X - 1;
          while( (p2Y % sizeOfGrid)!=0 )
                 p2Y = p2Y - 1;
          if( (p1X == p2X) && (p1Y == p2Y) )
              {
              return true;
              }
          else {
               return false;
          }
}

Yours requires a lot less calculation so I'd say is more efficient....I think I might borrow bits of it :-)

Mutant_Fruit

You have the right idea. You know to check if there's a reminder:

p1X % sizeOfGrid)!=0

But wouldn't it have been a little better to do this:

p1X = p1X - (p1X % sizeOfGrid);

instead of this:

while( (p1X % sizeOfGrid)!=0 )
                 p1X = p1X - 1;

Of course, Stripes one would be most efficient i'd say.

GreeBo

fletch wrote:

Hmmm no I don't think that would do the trick.......if one player was in position [8][7] and the other was in [7][8] well then their distances apart is <8, however they are in different squares....

What does it matter that they are in different squares, I thought you wanted to see if they are in the same 8x8 grid?