Thread: Having trouble solving maze.

  1. #1
    Registered User
    Join Date
    Jan 2006
    Posts
    23

    Having trouble solving maze.

    Hello, I have a task of solving a 20 by 20 maze. The problem im facing is that currently, I take a .txt file in and have to solve a maze for J amount of mazes.

    Im having problems getting my if and elses arranged in my solveMaze function to solve each maze one by one using non AI methods, always check spot above then to the left then below then to the right etc.

    Was wondering if any of you would like to give me some assistance on starting my solveMaze function. Because the arrays first element starts at 0 having some trouble skipping to next mazes etc in the for loops.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    struct stackNode{
    	
    	int data;
    	struct stackNode *nextptr;
    };
    
    
    
    void push(struct stackNode **topptr, int info);
    int pop(struct stackNode **topptr);
    void readFile(char *file);
    int num_of_mazes;
    void solveMaze(char *** maze);
    
    
    int main()
    {
    	char fname[30];
    	int i,j;
    	
    	
    	printf("What is the file name of the maze you wish to solve?");
    	scanf("%s", &fname);
    	
    	readFile(fname);
    	
    	return 0;
    }
    
    
    
    void readFile(char *file)
    	{
    	int i,j;
    	
    	int num_of_mazes;
    	
    	
    	
    	
    	FILE *infile; // file 
    	
    		// If statement for opening file and error for fail.
    		if((infile = fopen(file, "r")) == NULL)
    		{
    			printf("Error Opening File. \n");
    			exit(1);
    		}
    
    	fscanf(infile, "%d", &num_of_mazes);
    	
    	char ***maze;
    	maze = (char ***) malloc((20 * num_of_mazes) * sizeof(char **));
    		for(i = 0; i < (20 * num_of_mazes); i++)
    		{
    		maze[i] =(char **) malloc(20 * sizeof(char *));
    			for(j = 0; j < 20; j++)
    			{
    				maze[i][j] = (char *) malloc(sizeof(char));
    			}
    		}
    	
    	for(i = 0; i < (20 * num_of_mazes); i++)
    	{
    		for(j = 0; j < 20; j++)
    		{
    			fscanf(infile, "%c", &maze[i][j]);
    			printf("%c", maze[i][j]);
    		}
    	
    	}
    	
    	solveMaze(maze);
    	
    	}
    	
    	
    	void solveMaze(char ***maze)
    	{
    		int i,j,k;
    		
    				
    		struct stackNode **xstack;
    		struct stackNode **ystack;
    		
    		int currentx, currenty;
    		
    		
    		
    		for(k = 1; k <= num_of_mazes; k++)
    		{
    		
    			for(i = 0; i < (20 * k); i++)
    			{
    				for(j = 0; j < 20; j++)
    				{
    					
    					
    					
    					
    				}
    			
    			}
    		}
    		
    		
    		
    				
    		}
    	
    	int pop(struct stackNode **topptr)
    	{
    		
    		struct stackNode *tmp;
    		
    		if( *topptr != NULL)
    		{
    			tmp = *topptr;
    			*topptr = (struct stackNode *) tmp->nextptr;
    			int temp2;
    			temp2 = tmp->data;
    			free(tmp);
    			return temp2;
    		}
    		else{
    			printf("Pop function error.");
    			exit(0);
    		
    		}
    		
    	
    	}
    	
    	void push(struct stackNode **topptr, int info)
    	{
    		
    		struct stackNode *temp;
    		
    		temp = (struct stackNode *)malloc(sizeof(struct stackNode));
    		
    			temp->data = info;
    			temp->nextptr = *topptr;
    			*topptr = temp;
    			
    	}

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You should simplify this. Instead of making a solve function that solves every single function at once, make one that just solves one. Since you just have 20x20 mazes, why don't you just use that? Make a structure or what not, wrap your maze up in it, and send it off to be solved. Perhaps:
    Code:
    #define ROWS 20
    #define COLS 20
    struct maze
    {
        char rooms[ ROWS ][ COLS ];
    };
    
    ...
    
    struct maze *load( FILE *fp )
    {
        ...load a maze from the file...
        ...stick it in a 'struct maze'...
        ...return the maze...
    }
    
    int solve( struct maze *m )
    {
        ...solve this maze...
        ...return success or failure...
    }
    I'm not sure why you're making a stack. I suppose you can. You don't really need one though. Just take a maze structure, set all its cells to "unused", set the "start" to "used", and the exit to "exit".

    Now there are many ways to solve. You can simply walk one way around until you can't move any more, at which point you back up until there is another way to go. You can flood fill every unused square around you, then move to those, and repeat, until you hit the exit, incrementing each flood count as you go. The path is simply following the lowest value in any neighboring square, until you hit the start.

    Lots of ways to solve mazes. You can do the "left hand on the wall" route. Etc...

    I'd skip the whole bit about solving J number of mazes, and simply work on getting one solved. Load one up, solve it. The rest will be a snap.


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

  3. #3
    Registered User
    Join Date
    Feb 2006
    Posts
    155
    use backtrace (coloring),and no need for the nested loops,use tree.

  4. #4
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    1. Pick an empty cell and place on stack.
    2. Pick random direction.
    3. If cell is empty, place on stack, set this as current cell and goto 2, else 4.
    4. Pop cell off stack, set as current cell and goto 2.

    The stack contains the solution.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Shortest Path Maze Solver (Breadth Search Help)
    By Raskalnikov in forum C Programming
    Replies: 5
    Last Post: 04-07-2009, 07:41 PM
  2. Solving maze using rec'
    By gavra in forum C Programming
    Replies: 14
    Last Post: 07-13-2008, 09:20 AM
  3. Maze Solving Cont....PLZ
    By jonnybgood in forum C Programming
    Replies: 30
    Last Post: 11-11-2005, 04:00 AM
  4. Solving A Maze Using C Language!!!!
    By jonnybgood in forum C Programming
    Replies: 6
    Last Post: 11-08-2005, 12:15 PM
  5. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 09:28 AM