Thread: Navigation in a maze towards a preferred location inside the maze

  1. #1
    Registered User
    Join Date
    Dec 2010
    Posts
    12

    Lightbulb Navigation in a maze towards a preferred location inside the maze

    I am trying to create a simple program in which a so called rat is trying to navigate towards its food by itself without any input from the user.
    The following is the simple code of the program i have written:

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<string.h>
    #include<Windows.h>
    
    
    void main()
    {
    
    	int rati=7,ratj=1;
    	
    char maze [9][16] = {
    	{'S','S','S','S','S','S','S','S','S','S','S','S','S','S','S','S'},
    	{'S',' ',' ',' ','X',' ',' ',' ','X',' ','X',' ',' ',' ',' ','S'},
    	{'S','X','X',' ','X','X','X',' ','X',' ','X',' ','X','X','X','S'},
    	{'S',' ',' ',' ',' ',' ','X',' ',' ',' ','X',' ',' ',' ',' ','S'},
    	{'S',' ','X','X','X',' ','X',' ','X',' ','X',' ','X','X',' ','S'},
    	{'S',' ','X','X','X',' ','X',' ','X',' ','X',' ','X','X',' ','S'},
    	{'S',' ','X',' ',' ',' ',' ',' ','X',' ',' ',' ','X','X',' ','S'},
    	{'S',' ','X',' ',' ',' ',' ',' ','X',' ',' ',' ','X','X',' ','S'},
    	{'S','S','S','S','S','S','S','S','S','S','S','S','S','S','S','S'}};
    
    	char rat = 1;
    	char cheese = 3;
    	
    	maze[7][14] = cheese;
    	maze[rati][ratj] = rat;
    	
    
    	while (rati!=7 || ratj!=14)
    	{
    		for (int i=0;i<=8;i++)
    		{
    			for(int j=0;j<=15;j++)
    			{
    				printf("%c",maze[i][j]);
    			}
    		printf("\n");
    		}
    
    		char dirhold;
    		
    		maze[rati][ratj] = ' ';
    
    		if (maze[rati-1][ratj] == ' ' && dirhold != 'd')
    		
    		{
    			rati--;//Towards Up
    			dirhold = 'u';
    		}
    			
    		else if (maze[rati][ratj+1]==' ' && dirhold != 'l')
    			{
    				ratj++;//Right
    				dirhold='r';
    			}
    		else if (maze[rati+1][ratj] == ' ' && dirhold !='u')
    			{
    				rati++;//Down
    				dirhold = 'd';
    			}
    		else if (maze[rati][ratj-1]==' ' && dirhold != 'r')
    			{	
    				ratj--;//Left
    				dirhold = 'l';
    			}
    		
    		/*else if (maze[rati-1][ratj] != 'X')
    			rati--;
    		else if (maze[rati+1][ratj] != 'X')
    			rati++;
    		else if (maze[rati][ratj-1]!='X')
    			ratj--;
    		else if (maze[rati][ratj+1]!='X')
    			ratj++;*/
    	
    		maze[rati][ratj] = rat;
    		
    		
    
    		system ("cls");
    		Sleep(50);
    	}
    		
    
    	getch();
    	}
    The problem is that it is getting stuck at some point in the maze. The food is located at bottom right so obviously the preferred direction of the rat should be towards right and bottom. Please help me to implement this logic so the rat doesn't get stuck.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    If you're stuck at a dead-end (i.e. three walls around where you are) you need to back up regardless of the value of dirhold.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Your commented out code should almost fix it I think, except that you forgot to change dirhold as well in each case.
    However, currently you are both adjusting the position inside each case and setting the direction variable. I would advise you to only set the direction variable inside each case, and then as a separate step just prior to placing the rat in the maze again, you move according to how you set dirhold in the statements above.

    So some pseudocode for the main loop:
    1. Draw maze
    2. Remove old rat location
    3. Examine surrounding square(s) and pick new direction
    4. Examine direction and move rat coordinates
    5. Place rat at new location

    Another thing to consider is that not all mazes are solveable by keeping your left hand against the wall. E.g. where the cheese is in the centre and the rat can go all the way around the right outside wall. A better strategy is the "bread crumb" approach, where you separately increment a count of each square visited, and prefer to explore towards cells with fewer crumbs. This all takes me back to the days of learning Pascal by playing with the THINK Pascal GridWalker game tutorial.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Jan 2009
    Location
    Australia
    Posts
    375
    I find that recursion is a pretty fun way to solve maze problems like this.

    However, it's probably less efficient and would get evern worse when the maze was bigger.

    The method of recursion is just checking to see whether adjacent cells are empty, then branch out to them if they are. Repeat until you find the cell with cheese.

  5. #5
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    463
    Quote Originally Posted by DeadPlanet View Post
    I find that recursion is a pretty fun way to solve maze problems like this.

    However, it's probably less efficient and would get evern worse when the maze was bigger.

    The method of recursion is just checking to see whether adjacent cells are empty, then branch out to them if they are. Repeat until you find the cell with cheese.
    doesn't greedy algorithm work well with mazes?
    Last edited by nimitzhunter; 01-07-2011 at 11:10 PM.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by DeadPlanet View Post
    I find that recursion is a pretty fun way to solve maze problems like this.
    Recursion isn't a method of solving mazes. Recursion is just a function that calls iteself.
    Quote Originally Posted by DeadPlanet View Post

    However, it's probably less efficient and would get evern worse when the maze was bigger.

    The method of recursion is just checking to see whether adjacent cells are empty, then branch out to them if they are. Repeat until you find the cell with cheese.
    You're talking about a BFS, which doesn't necessarily have anything to do with recusion.

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    The two algorithms I'd suggest for solving your maze are:

    1) Depth First Search.

    The recursive form of DFS, is easier to understand and code. DFS is also a fast solver, but it won't give the shortest way to the cheese, unless you add the little bit of extra code that makes it use iterative deepening.

    DFS is a "bottom feeder", and backtracking is literally a return away. Crazy if you haven't seen it before.

    2) A*

    I know this is commonly recommended for solving mazes, but not much else about it.

    Check out the Wikipedia article on these algo's, or just Google away - lots of info out there, on both the above.

    Sounds like you're trying to set up your rat with some intelligence. Since he's in a maze, that can be frustrating. I'd suggest that you leave the rat dumb as a brick, but have him run fast as lightning, to exhaustively search for the cheese. Once you start programming him to prefer heading in the general direction of the cheese, you've got trouble - he is, after all in a maze, and the fastest way to get to the cheese is frequently going to be run away from the direction of the cheese.
    Last edited by Adak; 01-08-2011 at 03:34 AM.

  8. #8
    Registered User
    Join Date
    Jan 2009
    Location
    Australia
    Posts
    375
    You're talking about a BFS, which doesn't necessarily have anything to do with recusion.
    Cool. I find that the self contained function (that calls itself) has a certain elegance to it. I'm not forcing my views or opinions on mrafray, just stating that I like to use recursion (i.e a function that calls itself) to implement a 'BFS', and he/she can if he/she so desires.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is a better rat, but far from perfect:

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<string.h>
    #include<Windows.h>
    
    #define ROWS 9
    #define COLS 16
    
    void show(char maze[ROWS][COLS]);
    
    int main(void)
    {
    
      int ratr=7,ratc=1, r, c, goal=0;
    	
      char maze [ROWS][COLS] = {
        {'S','S','S','S','S','S','S','S','S','S','S','S','S','S','S','S'},
        {'S',' ',' ',' ',' ',' ',' ',' ','X',' ','X',' ',' ',' ',' ','S'},
        {'S','X','X',' ','X','X','X',' ','X',' ','X',' ','X','X','X','S'},
        {'S',' ',' ',' ',' ',' ','X',' ',' ',' ','X',' ',' ',' ',' ','S'},
        {'S',' ','X','X','X',' ','X',' ','X',' ','X',' ','X','X',' ','S'},
        {'S',' ','X','X','X',' ','X',' ','X',' ','X',' ','X','X',' ','S'},
        {'S',' ','X',' ',' ',' ',' ',' ','X',' ','X',' ','X','X',' ','S'},
        {'S',' ','X',' ',' ',' ',' ',' ','X',' ',' ',' ','X','X',' ','S'},
        {'S','S','S','S','S','S','S','S','S','S','S','S','S','S','S','S'}
      };
      char rat, cheese, vector;
      rat = '*';
      cheese = 178; //
    	
      maze[7][14] = cheese;
      maze[ratr][ratc] = rat;
    	
      while (!goal) {
        show(maze);
        getch();
        
        maze[ratr][ratc] = ' ';
        if(maze[ratr-1][ratc]==cheese) 
          ratr--;
        else if(maze[ratr+1][ratc]==cheese) 
          ratr++;
        else if(maze[ratr][ratc-1]==cheese) 
          ratc--;
        else if(maze[ratr][ratc+1]==cheese) 
          ratc++;
    
        if (maze[ratr-1][ratc] == ' ' && vector != 'd') {
          ratr--;//Towards Up
          vector = 'u';
        }
        else if(maze[ratr-1][ratc] != ' ' && vector == 'u') {
          vector = 'd';
        }
        else if (maze[ratr][ratc+1] == ' ' && vector != 'l') {
          ratc++;//Right
          vector='r';
        }
        else if(maze[ratr][ratc+1] != ' ' && vector == 'r') {
          vector = 'l';
        }
        else if (maze[ratr+1][ratc] == ' ' && vector !='u') {
          ratr++;//Down
          vector = 'd';
        }
        else if (maze[ratr][ratc-1] == ' ' && vector != 'r') {	
          ratc--;//Left
          vector = 'l';
        }
        /*else if (maze[ratr-1][ratc] != 'X')
          ratr--;
        else if (maze[ratr+1][ratc] != 'X')
          ratr++;
        else if (maze[ratr][ratc-1]!='X')
          ratc--;
        else if (maze[ratr][ratc+1]!='X')
          ratc++;*/
    	
        if(maze[ratr][ratc]==cheese) {
          goal=1;
          printf("\n\nI LOVE this cheese!\n");
          maze[ratr][ratc] = rat;
          show(maze);
        }
        maze[ratr][ratc] = rat;
      }
      printf("\n\n\t\t\t    press enter when ready");
      (void) getchar();
      return 0;
    }
    void show(char maze[ROWS][COLS]) {
      int r, c;
    
      putchar('\n');
      for (r=0;r<ROWS;r++) {
        for(c=0;c<COLS;c++) {
        	printf("%c",maze[r][c]);
        }
        printf("\n");
      }
    }
    It finds the cheese in this case, but wouldn't find it in other maze configurations.

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I was under the impression that the OP just wanted a sort of weighted pathing - head towards the cheese whenever possible, as a first choice. They just need to keep track of if a path is a dead end, and not go there anymore, and decide if they go this way or that way, depending on if this way is less steps to the right X (or Y) coord, than that way. Consider:

    abxx
    cxxx
    xxxd

    If we are a and we want to go to d and our two choices are currently b or c, then c is the "better" choice, because it is only 2 steps from the correct row, where as going to b is still 3 steps from the right column.

    Anyway, that's what I thought they were trying to do. They just need to stop going a direction if it ended up a dead end.


    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,907
    Quote Originally Posted by Adak View Post
    2) A*

    I know this is commonly recommended for solving mazes, but not much else about it.
    So I haven't seen the OP on here since the OP, but the way I understood his question is that the rat (program) doesn't know where the cheese is. A* is more designed for finding the best (lowest cost) route to a known goal, not finding an object whose location is unknown. A* requires knowledge of the search space, i.e. cost of movements in each direction (a constant for all moves in this case), as well as the goal location. This is because A* requires a heuristic function that gives a cost-to-goal for a node that is equal to or better than all actual routes to the goal. For graph traversal (of which maze solving is a specific case), people often use straight line distance (shortest distance between two points). As awesome as this algo is, I don't think it will work in this case.

    I would stick with something like BFS or DFS for the simpler solution.

    As an interesting aside, I thought it would be cool if you could work in a smell factor (since rats in a maze would normally smell out the cheese). You basically give the cheese square a smell of one, then every adjacent square gets a smell of something like .9. Keep multiplying by some factor like .9 every step you radiate away from the cheese, then you can let the rat make smart decisions once he's close enough to smell the cheese. Similar techniques are used in path finding algorithms for robots.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by anduril462 View Post
    So I haven't seen the OP on here since the OP, but the way I understood his question is that the rat (program) doesn't know where the cheese is. A* is more designed for finding the best (lowest cost) route to a known goal, not finding an object whose location is unknown. A* requires knowledge of the search space, i.e. cost of movements in each direction (a constant for all moves in this case), as well as the goal location. This is because A* requires a heuristic function that gives a cost-to-goal for a node that is equal to or better than all actual routes to the goal. For graph traversal (of which maze solving is a specific case), people often use straight line distance (shortest distance between two points). As awesome as this algo is, I don't think it will work in this case.
    My thoughts exactly. Using A* would give you the optimal route right from the start, i.e. it would be cheating. Even if the rat were to follow its nose, it would surely wander down a few dead ends, whereas if it were solved with A* then it would basically know exactly where to go. Best case you could solve it while the rat moves through the maze and have the rat always head down the currently most promising path, but that would vastly complicate things for what is already quite a bit harder than this poster is up to at this point, and it's still cheating. Also, what if there is more than one piece of cheese in the maze later?

    So perhaps stop viewing this as a classical maze-solving problem, which clearly it is not. Assume that the rat can only see what is in the cells immediately adjacent to it, and can't smell anything. You either move randomly, or follow one hand along the wall, or you simulate the rat building up its memory of the maze by doing the breadcrumb dropping thing.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 04-13-2010, 03:14 PM
  2. Still battling with Copy Control
    By Mario F. in forum C++ Programming
    Replies: 9
    Last Post: 06-23-2006, 08:04 AM
  3. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM
  4. Im so lost at . .
    By hermit in forum C Programming
    Replies: 18
    Last Post: 05-15-2002, 01:26 AM

Tags for this Thread