Finding stuff within a grid - aproaches

[JackBauer]

Hello,

if we have a grid that has some stuff and we need to search it in several directions, what's the best approach ?

Loop each direction?

Or have a single loop like:

Code: Select all

interation  = 0;
while (condition)
   iteration++;
   x = i+iteration;
   y = j+iterarion;

   /* check direction 1 */
   if ( first ) {
     if ( matrix[x][y] is not empty ) {
        if ( other condition ) { 
           return found; /* break the loop */
        }
        else {
            first = 0; /* so it doesnt keep checking this direction if theres a block or no capture */
        }
     }
   }


   x = i-iteration;
   y = y-iteration;

   /* check direction 2 */
   if ( second ) {
        if ( matrix[x][y] is not empty ) {
             if () {

              }
              else {
                  second = 0;
              }
       }
   }

   /* check other directions changing x and y */


}

Or something else?

Example:

Given this matrix,

00000
00010
00000
02002
00000

Check if piece called '1' can capture some piece (as in chess bishops), like pieces numbered 2, if it can move in any diagonal any number of steps. The problem could also be, "if it can move in any direction".

some additional info:

* function only needs to check if theres a "capture" (so it can return as soon as it finds one, not needing to continue the other checks).

* if there's a block in either direction (like a piece of the same color), that direction should/must not be checked anymore.

Thanks.

[cypressx]

Read something about a dfs or bfs ( for example search for them in google.com they are really a must algorithms for every programmer )
here is a simple dfs code , which returns true if you can reach x,y when you move with all 8 directions ..
int dx[somenumberofmoves] = { }; // the moves by x coordinate
int dy[somenumberofmoves] = { }; // the moves by y coordinate
// in you example it will look like this :
dx[4] = { -1, -1, 1, 1 };
dy[4] = { -1, 1, -1, 1 };
// this way x + dx , y + dy ( where i is from 0 to 4 ) you go only the diagonals

bool dfs(int x,int y) {
if(x==wantedX && y==wantedY) return 1;
used[x][y] = 1; // we can`t come back
for(int i=0;i<dx.size();i++) {
if(!used[x+dx][y+dy]) { // ako ne sme go obhodili
dfs(x+dx,y+dy);
}
}
}

... Hope this is what you asked and you find my post helpful .

[eleusive]

Be careful that you check for out-of bounds when you implement a dfs or bfs. Also, this problem can actually be implemented without a complicated algorithm (and is easier to code). Here is the explanation for only diagonal checks. Say there are two pieces named a and b, and you are trying to see what pieces a can reach. Check for each piece b, if abs(a.column/column_size-b.column/column_size)==abs(a.row/row_size-b.row/row_size). If this condition is true, then piece a can reach piece b diagonally. However, you also need to check to see if that path is blocked. One way(not the fastest but still works) to do this is to search each piece besides a and b, and see if that piece can be diagonally reached from both pieces a and b using the same technique described above.

[JackBauer]

Thanks for the input so far. I'll check the "dx dy" example given previously.

Check for each piece b, if abs(a.column/column_size-b.column/column_size)==abs(a.row/row_size-b.row/row_size). If this condition is true, then piece a can reach piece b diagonally. However, you also need to check to see if that path is blocked. One way(not the fastest but still works) to do this is to search each piece besides a and b, and see if that piece can be diagonally reached from both pieces a and b using the same technique described above.

Yes, I did the x/y start/end difference to implement a previous thing in the code (check if piece 1 can capture piece N).

In this new situation the code only needs to know if a piece can capture (any piece, not known in advance). So basicly I can start at x,y and just loop all the ways

00000
01000
00010
00020
00000

lets says the piece is 1,1 (zero based, value=1).

it needs to go to (0,0) and then stop (this direction) because of the bounds.
it needs to go to (0,2) and then stop (this direction) because of the bounds.
it needs to go to (2,2) and continue (empty).
it needs to go to (2,0) and then stop (this direction)
it needs to go to (3,3) and check there's a different piece there (it captures, checking is over)

So basicly there could be a function that checks "Up, Right", another that checks "Up, Left", another that checks "Down, Left"...

Something like this could be used to avoid checking after capture is found.

Code: Select all

int capture = 0;

if ( checkUR ( x,y ) == 1 ) {
  capture = 1;
}
else if ( checkUL ( x,y) ) {
      capture = 1;
}

But that could also be put into a single loop. The advantage of the single loop (as implemented above) is that the checker doesn't keep checking a direction after it found a capture in another direction.

With a function for each, let's say it only finds a capture in the last (or doesn't find a capture) checking fucntion (last direction it checks) --- all other directions were checked until they hit the bounds.

What do you think?

Thanks.