Thread: 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.

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.

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.

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.

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.

Originally Posted by Adak

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.