Too many IFs

[rogster001]

This problem is from an a* pathfinding routine i am trying to write, i am reluctant to look at sample working versions so far because i want to learn from mistakes, though i realise its best not to reinvent the wheel!

Any thoughts are appreciated.

the problem is as follows

from a given current square on the search area i need to check the surrounding
adjacent squares for walkable or not walkable,, e.g.

0 = Not Walkable, 1 = walkable, 2 = current square (now on the closed list)

so my array 'area[3][3]' that contains the portion i want to test may look like this

111
121
101

The current square (2) is always in the centre.

My problem is that is if any of the four central squares surrounding the current square are unwalkable the diagonal moves to the corners either side of the unwalkable node cannot be considered for the next current square as i am not allowing 'diagonal' moves around obstructions.
In the example this would be the 101 row, although they are walkable squares i cannot move to them from the current square without cutting across the corner of the unwalkable one.

So basically each time i need to check if any of these positions (x)are notwalkable x
x x
x

and if so, ensure that the scores assigned to the nodes either side are not altered or are reset back to their previous state.
This is easy enough i suppose but when the current square is at the edge of the total search area it is giving me a headache because part of the area i would normally test is out of scope of the array.

so if it looked like this

111
021
***
with the final three positions i would like to check (***) being off the lower edge of the searcharea..... i am finding it hard to think how to 'ask' about the array position bottom left below the unwalkable node, without asking to look at contents of invalid and incorrect array elements,

It seems to be leading me to lots of messy IF statements is this just to be accepted in these cases?
the switch statement does not to really serve any better so any thoughts appreciated.
And i totally understand if this thread gets binned! i can't get a concise way of asking this question, and maybe thats also why i haven't yet come up with satisfactory answer!

the word processing knocked over my example with 'x's
i mean the top middle, left middle, right middle, and lower middle nodes.

[Adak]

In chess we frequently work with a chessboard that includes an extra row or column (sometimes more than one), to help us with edge detection.

When the board is initialized, those "off the playing board" rows and columns are given a sentinel value, like -99 or whatever, so we can know for sure, that if we're considering a move to that square, it's off the board, pretty easy.

If board[square] < 0
   you're off the board

I knew what you meant.

Cheers.

[rogster001]

haha cheers, i did consider that approach, having an extra areaaround the 'board' will probably end up doing it, but then i became stubborn about doing it the other way!more because i was annoyed because i did not seem to be finding a neat solution i was sure was there.

the thing that put me off with the sentinel values was the idea that i might get bugs when valid squares contain the same value by coincidence, but yea, will be a value of 21 in my case that should be impossible to get, and if i zero the array first there will not be any wacky numbers floating around.

[Salem]

111
120
111

So the bottom-right of this example is also unreachable by the rules you've posted?

[anon]

Interesting problem. May-be you could post your code?

I second the extra edges too. Simply surround the board with unwalkable tiles and there will be a lot less special cases.

So you want to consider (x-1, y), (x+1, y), (x, y-1) and (x, y+1). In addition consider (x-1, y-1) if both (x-1, y) and (x, y-1) are walkable and similarly for other corner tiles.

I believe it should be possible to generalise (let a loop handle) corners.

[tabstop]

Perhaps I'm misunderstanding the rules of your game, but if you don't allow diagonal moves, why even consider them in your pathfinding? Why not set up your algorithm so it only ever considers north, east, south, and west?

[rogster001]

is see your point but the rule is part of the Astar algorithm i am following, you still have to look at diagonals because there are plenty of times when the current node will be in the middle of walkable nodes, and in this case diagonal is fine, its just you can't 'cut across' the corner of a nonwalkable node, you have to go around

[rogster001]

in answer to Salem, yes in the example you posted the bottom right is unreachable, from the current square at that time. because you would cut across the unwalkable square.

you could have this situation..

101
020
101
where under these rules there is no move available!

[rogster001]

in reply for Anon, yep i did use a loop, goes round 9 times for each of the tiles in the area i test, it adds (or will add) all the values and scores for the tiles that i need in this stage, but in the code below i have just added comments for those bits so you can see the working parts in this problem better.

(the 'area[n][n] array is filled at random with the walkable and unwalkable values)

 for(count = 0; count < 9; count++)
{

    switch(count)              /*tests the coordinates will be within the search area */
   {
    case 0: cX -= 1; cY -= 1; 
    break;
    case 1: cX++; 
    break;
    case 2: cX++; 
    break;
    case 3: cX -= 2; cY++; 
    break;
    case 4: cX++; 
    break;
    case 5: cX += 1; 
    break;
    case 6: cX -= 2; cY++; gscore = 14;
    break;
    case 7: cX++; gscore = 10;
    break;
    case 8: cX++; gscore = 14;
    break;
   }
                  /*this IF allows the array to be filled where it is within the 'board' */

	if((cY >= 0 && cY <= MXDWN) && (cX >= 0 && cX <= MXACR))
	{
	grid[cY][cX] = area[cY][cX];    /*fill the test area with walk/unwalk and current square values*/
	 

            /*maybe.........but this is the stuff i don't like, below is where i check as in the problem*/

                 if((count ==1 || count == 3 || count == 5 || count == 7) && grid[dwn][acr] == UNWALK)

                   /*now i need some more code to check the nodes next to the unwalkable one!! */

	}
}                                                           /* End of count FOR Loop */

[anon]

The "problem" with that loop is that the value of count is completely irrelevant to what you are doing inside the loop. That's why you need the switch and extremely complicated logic of incrementing/decrementing variables.

I had something like this in mind (assuming extra borders, but check_node might check whether the node is in range or not too). The side cases could be put in a loop too, but it seems simpler to simply call a function separately for each case.

#include <stdio.h>

void check_node(int x, int y)
{
    printf("Checking node [&#37;d, %d]\n", x, y);
}

int is_walkable(int x, int y)
{
     return 1;
}

int main()
{    
    int x = 3, y = 6, i, j;
    check_node(x-1, y);
    check_node(x, y-1);
    check_node(x+1, y);
    check_node(x, y+1);
    
    //all combinations of -1 and 1 for i and j
    for (i = -1; i <= 1; i += 2) { 
        for (j = -1; j <= 1; j += 2) {
            if (is_walkable(x + i, y) && is_walkable(x, y + j)) {
                check_node(x + i, y + j);
            }
        }
    }
    return 0;
}

(Not tested properly, may not work quite right.)

[Salem]

4 simple tests, to check for N,S,E,W movement, make this one function with this interface.
bool isValidCardinalMove( int x, int y );

4 slightly more complex tests for the diagonals, make this another function with this interface.
bool isValidDiagonalMove( int x, int y );

Then a valid move test looks really simple

bool isValidMove ( int x, int y ) {
    return isValidCardinalMove( x, y ) && isValidDiagonalMove( x, y );
}

Breaking the problem down into easily solvable parts is one of those skills which is rather harder to teach (except by practice).

If you're getting confused with any single function, that's a hint you need to step back and think about how you might simplify into more specific tasks.

[rogster001]

Yes, i actually did some work last night and broke down other parts of program into functions where they had previously been in main() There are some other parts i would like to make into functions too but they bug me because i thought you could only return one value, and sometimes i think i need to pass a whole array back, or would like to return more than one variable.
Which brings me to your suggestion above are you returning two values?

i came up with a working version that does the job for now, i decided to check the squares on the corners first, because if they have got through my first conditonal check they are one the board anyway, and so are the relevant adjacent squares because there can only ever be one row off the board.
This is also why i haven't added an extra sentinel row + column, though i should because is better solution in long term methinks.

here is what i put together...
cY , cX is current square Y, X), BLANK is available square not yet closed, the other olistNscore variables irrelevant in this discussion.

                if((cY >= 0 && cY < MAXDWN) && (cX >= 0 && cX < MAXACR))
		{
		   grid[cY][cX] = area[cY][cX];

		  if(grid[cY][cX] == WALK && olistFscore[cY][cX] == BLANK)
		  {

		    AddSquare = CheckDiagonalMove(grid, cY,cX,count);

		    if(AddSquare == 1)
		    {
		    olistGscore[cY][cX] = olistGscore[cY][cX] + gscore;
		    olistFscore[cY][cX] = olistGscore[cY][cX] + olistHscore[cY][cX];
		    }

		  }

And here's the function that is called to check the diagonal move and returns if the square can be added to valid open nodelist

CheckDiagonalMove(int grid[MXDWN][MXACR],int cY, int cX, int count)
{

int AddSq = 1;
		  switch(count)   /*These counts are the corners */
		  {
		   case 0:
			if(grid[cY][cX+1] == NWALK || grid[cY+1][cX] == NWALK)
			AddSq = 0; break;
		   case 2:
			if(grid[cY][cX-1] == NWALK || grid[cY+1][cX] == NWALK)
			AddSq = 0; break;
		   case 6:
			if(grid[cY-1][cX] == NWALK || grid[cY][cX+1] == NWALK)
			AddSq = 0; break;
		   case 8:
			if(grid[cY][cX-1] == NWALK || grid[cY-1][cX] == NWALK)
			AddSq = 0; break;

		   default: AddSq = 1;
		  }
return(AddSq);
}

thanks for the feedback on this post!

i am posting another thread related to this pathfinding program also, i am presently using four loops to do the task in the thread but i am sure there is an easy little maths equation that will do the job with one loop....i just knows it!