Question about C++ recusive pathfinding - Overclock.net

icyblizard · 12-06-07

Mods delete if you see this

stargate125645 · 12-06-07

Quote:

Originally Posted by icyblizard

Does anyone know how to do a pathfinding function than has less than 10 lines of code? We have to do something like a mouse looking for a cheese
****************
*C *
************ *
* * *
*M ********* *
* *
****************
This is just an example, we actually have to load a txt file and save it into an array (16 length by 8height).
C - cheese
M - mouse
* - wall
The thing is, i have done it using recursions and my code is like 80 lines

and yet the lecturer said it was possible to do it with just 8-9 lines of actual code

I think im going to be like *** when he shows us his code

Don't use any spaces, and it will be 1 line of code.

That will show your teacher!

icyblizard · 12-06-07

sorry, actual maze looks like this, just replace the . with blank spaces. The brower sees many spacings as just 1 spacing
****************
*C .........................*
************......*
* ..*.......................*
*M *********......*
*............................*
****************
Actual maze is 16*8, just too troublesome to draw it here.
And of course, i believe that his 10 lines are indented properly

kdbolt70 · 12-06-07

Oh man, I wrote this exact program a couple of years ago. There's no way in hell you could get a shortest path algorithm (thats what the name of this problem is) in 10 lines, especially if you have to load the maze from file!

icyblizard · 12-06-07

Not the whole code, just the pathfinding part

dante020 · 12-06-07

Well, does it have to be the shortest path, or just any path? And how do you display the path that you traveled?

icyblizard · 12-07-07

It does not have to be the shortest path. When the function is returned, the current coordinates of the maze[x][y]='+' to mark the path which u travelled.

dante020 · 12-07-07

I'll see what I can do.

EDIT: Can you move diagonally?

EDIT: This works fine (I think). It returns a path, not necessarily the shortest. I tested it with:

"maze.txt"

Code:

****************
*m             *
************** *
*              *
***** **********
*     *   *    *
*       *   * c*
****************

Code:

#include <iostream>
#include <fstream>

using namespace std;

const int ROWS = 8, COLS = 16;

void findStart(char maze[ROWS][COLS], char start[]);
bool path(char maze[ROWS][COLS], int x, int y);
void loadFile(string target, char maze[ROWS][COLS]);
void print(char maze[ROWS][COLS]);

int main()
{
	char maze[ROWS][COLS], start[2];
	
	loadFile("maze.txt", maze);
	print(maze);
	
	findStart(maze, start);
	
	path(maze, start[0], start[1]);
	
	cout << "Path: " << endl;
	
	print(maze);
	
	system("pause");
	return 0;
}

void print(char maze[ROWS][COLS])
{
	for(int row=0; row<ROWS; row++)
	{
		for(int col=0; col<COLS; col++)
			cout << maze[row][col] << " ";
			
		cout << endl;
	}
}

void loadFile(string target, char maze[ROWS][COLS])
{
	ifstream file;
	file.open(target.c_str());
	for(int row=0; row<ROWS; row++)
	{
		for(int col=0; col<COLS; col++)
			maze[row][col] = file.get();
			
		file.get();
	}
	file.close();
}

void findStart(char maze[ROWS][COLS], char start[])
{
	for(int row=0; row<ROWS; row++)
		for(int col=0; col<COLS; col++)
			if(maze[row][col] == 'm')
			{
				start[0] = row;
				start[1] = col;
			}
}

bool path(char maze[ROWS][COLS], int x, int y)
{
	if(maze[x][y] == ' ') maze[x][y] = '+';
	for(int val=-2; val<=2; val++)
	{
		if(maze[x+val/2][y+val%2] == 'c') // found cheese
		{
			return true;
			system("pause");
		}
			
		if(maze[x+val/2][y+val%2] == ' ')
		{
			if(path(maze, x+val/2, y+val%2)) 
				return true;
		}
	}
	if(maze[x][y] == '+') maze[x][y] = ' ';
	return false;
}

kdbolt70 · 12-07-07

Quote:

Originally Posted by icyblizard

It does not have to be the shortest path. When the function is returned, the current coordinates of the maze[x][y]='+' to mark the path which u travelled.

ahh, well making it not the shortest path might be quite a bit easier. If I had some time I'd attempt it, though it looks like dante has a good solution

dante020 · 12-07-07

Well I could make it the shortest path without too much effort but if its not required...

EDIT: This one should find the shortest path

Code:

#include <iostream>
#include <fstream>

using namespace std;

const int ROWS = 8, COLS = 16;

void findStart(char maze[ROWS][COLS], char start[]);
void path(char maze[ROWS][COLS], int x, int y, char shortest[ROWS][COLS], int & length, int & shortPath);
void loadFile(string target, char maze[ROWS][COLS]);
void print(char maze[ROWS][COLS]);

int main()
{
	char maze[ROWS][COLS], shortest[ROWS][COLS], start[2];
	int length = 0, shortPath = 0;
	
	loadFile("maze.txt", maze);
	print(maze);
	
	findStart(maze, start);
	
	path(maze, start[0], start[1], shortest, length, shortPath);
	
	cout << "Path: " << endl;
	
	print(shortest);
	
	cout << "Length: " << shortPath << endl;
	
	system("pause");
	return 0;
}

void print(char maze[ROWS][COLS])
{
	for(int row=0; row<ROWS; row++)
	{
		for(int col=0; col<COLS; col++)
			cout << maze[row][col] << " ";
			
		cout << endl;
	}
}

void loadFile(string target, char maze[ROWS][COLS])
{
	ifstream file;
	file.open(target.c_str());
	for(int row=0; row<ROWS; row++)
	{
		for(int col=0; col<COLS; col++)
			maze[row][col] = file.get();
			
		file.get();
	}
	file.close();
}

void findStart(char maze[ROWS][COLS], char start[])
{
	for(int row=0; row<ROWS; row++)
		for(int col=0; col<COLS; col++)
			if(maze[row][col] == 'm')
			{
				start[0] = row;
				start[1] = col;
			}
}

void path(char maze[ROWS][COLS], int x, int y, char shortest[ROWS][COLS], int & length, int & shortPath)
{
	if(maze[x][y] == ' ')
	{
		maze[x][y] = '+';
		length++;
	}
	for(int val=-2; val<=2; val++)
	{
		if(maze[x+val/2][y+val%2] == 'c') // found cheese
		{
			if(length < shortPath || shortPath == 0)
			{
				for(int row=0; row<ROWS; row++)
					for(int col=0; col<COLS; col++)
						shortest[row][col] = maze[row][col];
				shortPath = length;
			}
		}
			
		if(maze[x+val/2][y+val%2] == ' ')
		{
			path(maze, x+val/2, y+val%2, shortest, length, shortPath);
		}
	}
	if(maze[x][y] == '+')
	{
		maze[x][y] = ' ';
		length--;
	}
}

		Overclock.net - Overclocking.net > Software, Programming and Coding > Coding and Programming > Application Programming
Question about C++ recusive pathfinding

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)