Too many IFs

This is a discussion on Too many IFs within the C Programming forums, part of the General Programming Boards category; This problem is from an a* pathfinding routine i am trying to write, i am reluctant to look at sample ...

  1. #1
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438

    Too many IFs

    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.
    Last edited by rogster001; 01-22-2008 at 06:00 AM. Reason: tidy up example

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.
    Code:
    If board[square] < 0
       you're off the board
    I knew what you meant.

    Cheers.

  3. #3
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    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.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,592
    111
    120
    111

    So the bottom-right of this example is also unreachable by the rules you've posted?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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?

  7. #7
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    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

  8. #8
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    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!

  9. #9
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    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)

    Code:
     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 */
    Last edited by rogster001; 01-22-2008 at 09:40 AM.

  10. #10
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.

    Code:
    #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.)
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  11. #11
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,592
    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
    Code:
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  12. #12
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    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.

    Code:
                    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
    Code:
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. multiple ifs...
    By halfpint101 in forum C++ Programming
    Replies: 4
    Last Post: 01-17-2008, 12:56 PM
  2. Question With Nested If's
    By jarvis in forum C Programming
    Replies: 7
    Last Post: 07-26-2006, 08:06 AM
  3. Try...catch...throw or ifs?
    By Kylecito in forum C++ Programming
    Replies: 9
    Last Post: 03-02-2006, 09:41 PM
  4. Very new to C++ or other programming, stuck on IF's
    By ivanlucrazy in forum C++ Programming
    Replies: 13
    Last Post: 10-16-2003, 08:59 PM
  5. Single else for two ifs.
    By Juganoo in forum C Programming
    Replies: 6
    Last Post: 12-23-2002, 02:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21