I'm currently working on a program that has to solve a 10x10 char maze, for example this one:
1 2 3 4 5 6 7 8 9 10
___________________________________________
1| + [] + [] + [] + + + []
2| + [] + + [] + + [] [] []
3| + + [] [] [] + [] [] + +
4| [] [] [] [] + + + [] [] +
5| + [] + [] + [] + + + []
6| + + + + + + [] [] + []
7| [] + + + [] [] + + + []
8| + + + [] + + + [] [] +
9| + + + [] [] + + [] [] +
10| + [] + [] + + [] + + +
Ignore the numbers, they are just coordinates. As for []
it's just the way the maze is printed. In actuality wherever there's a +
then that means path, wherever there's []
that means there's an obstacle.
I'm using the backtrack algorithm:
void backtrack(int curX, int curY, char(*char_maze)[10], int position)
{
if (curX < 0 || curY < 0 ||
curX > 9 || curY > 9) {
//out of bounds
return;
}
Node tmp;
tmp.x = curX, tmp.y = curY;
queue(&head, &tmp);
position++;
if (char_maze[curX][curY] == finish) {
//destination found TODO print path
printf("route found");
}
if (char_maze[curX][curY] == path) {
char_maze[curX][curY] = visited;
}
backtrack(curX, curY - 1, char_maze, position);
backtrack(curX - 1, curY, char_maze, position);
backtrack(curX, curY + 1, char_maze, position);
backtrack(curX + 1, curY, char_maze, position);
char_maze[curX][curY] = path;
if (position) {
del_nth(head, position);
}
if (!position) {
del_first(&head);
}
position--;
}
The correct route will consist of a linked list, here's a node of that list:
typedef struct coords {
int x;
int y;
struct coords * next;
}Node;
whenever backtrack(...)
stumbles over a passable cell, it's supposed to mark it as visited and add it to the list. Adding to the list is done by these 2 functions:
void queue(Node ** head, Node * object)
{
Node * tmp = (Node *)malloc(sizeof(Node)); //this is the problematic line
*tmp = *object;
Node * last = get_last(*(head));
if (!last) {
(*head) = tmp;
tmp->next = NULL;
}
else {
last->next = tmp;
tmp->next = NULL;
}
}
and
Node * get_last(Node * head)
{
while (1) {
if (head) {
head = head->next;
}
else {
return NULL;
}
}
return head;
}
and also under the appropriate conditions backtrack(...)
should unmark a cell and delete it from the list. Deletion is done using these 2 functions:
void del_nth(Node * head, int index)
{
Node * previous;
for (int i = 0; i < index - 1; i++) {
head = head->next;
}
previous = head;
head = head->next;
previous->next = head->next;
free(head);
}
and
void del_first(Node ** head)
{
Node * del = (*head);
(*head) = (*head)->next;
free(del);
}
path, visited, finish
and so on are const char
-s, which represent the cells of the maze.
backtrack(...)
is called with 2 coordinates set by the user, the maze itself and position
which is set to 0
.
Now that I explained how the code works, the problem. I've ran this code through the Visual Studio Debugger and I got a Stack overflow (parameters: 0x00000001, 0x00492FFC).
exception on this line
Node * tmp = (Node *) malloc(sizeof(Node));
which is a part of the queue(...)
function. This doesn't make any sense to me, since malloc()
allocates on the heap. I'm stumped, I'm out of explanations, I have no idea why this happens. I included all of the code used in the backtrack(...)
function because the problem may actually be there. It wouldn't be the first time a debugger pointed out a wrong line.
Anyway, many thanks for your help in advance.
User contributions licensed under CC BY-SA 3.0