Instantly share code, notes, and snippets.

Embed
What would you like to do?
Breadth First Search Maze Program
/* Breadth First Search Maze. */
#include "stdlib.h"
#include <iostream>
#include <windows.h>
#define NORTH 0
#define EAST 1
#define SOUTH 2
#define WEST 3
#define MAX_WIDTH 10
#define MAX_HEIGHT 10
#define QUE_SIZE 200
HANDLE console = GetStdHandle(STD_OUTPUT_HANDLE); // For use of SetConsoleTextAttribute()
void print_maze(struct Tile *maze, struct AI *ai);
bool bfs_move(bool goToStart, struct Tile *maze, struct Tile *aiMem, int *memPos, int *parents, int *moveMem, int *moveMaze, struct AI *ai);
int bfs(bool goToStart, int *parents, struct Tile *aiMem, int *memPos, int *moveMem, int *moveMaze, struct AI con);
void generate_maze(struct Tile *m);
void resetque(void);
bool enque(int num);
int deque(void);
struct Tile
{
unsigned char N : 1;
unsigned char E : 1;
unsigned char S : 1;
unsigned char W : 1;
unsigned char V : 1;
unsigned char END : 1;
unsigned char START : 1;
unsigned char filler : 1;
};
struct AI
{
int position;
unsigned char direction;
};
struct que_node {
int number;
struct que_node *next;
};
struct que_node *que = (struct que_node *)malloc(QUE_SIZE * sizeof(struct que_node));
struct que_node *head, *tail;
struct Tile t[15];
int width, height;
/* main.
====================================================================================================================================================================================================================================
====================================================================================================================================================================================================================================*/
int main(void)
{
int memPos = 0, moveMem[4] = { -MAX_WIDTH, 1, MAX_WIDTH, -1 }, moveMaze[4] = { -width, 1, width, -1 };
struct AI ai = { 0 };
bool moreOpenTiles = true;
int *parents = (int *)malloc((MAX_WIDTH * MAX_HEIGHT) * sizeof(int));
struct Tile *maze = (struct Tile *)malloc(MAX_WIDTH * MAX_HEIGHT), *aiMem = (struct Tile *)malloc(MAX_WIDTH * MAX_HEIGHT);
unsigned char *mazeP = (unsigned char*)maze, *memP = (unsigned char*)aiMem;
for (int i = 0; i < MAX_WIDTH * MAX_HEIGHT; i++)
memP[i] = 0;
generate_maze(maze);
moveMaze[0] = -width;
moveMaze[2] = width;
for (int e; moreOpenTiles;)
{
maze[ai.position].V = true;
aiMem[memPos] = maze[ai.position];
for (e = 0; e < 4; e++)
{
print_maze(maze, &ai);
getchar();
if (mazeP[ai.position] & (1 << ai.direction) || memP[memPos + moveMem[ai.direction]] != 0)
{
ai.direction++;
if (ai.direction == 4)
ai.direction = NORTH;
}
else
{
ai.position += moveMaze[ai.direction];
memPos += moveMem[ai.direction];
break;
}
}
if (e == 4)
moreOpenTiles = bfs_move(false, maze, aiMem, &memPos, parents, moveMem, moveMaze, &ai);
print_maze(maze, &ai);
getchar();
}
moreOpenTiles = bfs_move(true, maze, aiMem, &memPos, parents, moveMem, moveMaze, &ai);
system("pause");
}
/* bfs_move.
====================================================================================================================================================================================================================================
====================================================================================================================================================================================================================================*/
bool bfs_move(bool goToStart, struct Tile *maze, struct Tile *aiMem, int *memPos, int *parents, int *moveMem, int *moveMaze, struct AI *ai)
{
int numberOfMoves, lastMove, i, moves[MAX_WIDTH * MAX_HEIGHT];
unsigned char direction;
for (int i = 0; i < MAX_WIDTH * MAX_HEIGHT; i++)
parents[i] = -1;
lastMove = bfs(goToStart, parents, aiMem, memPos, moveMem, moveMaze, *ai);
if (lastMove == -1)
return false;
i = lastMove;
for (numberOfMoves = 0; parents[i] != i;) /* Count the number of moves, and place all the moves in moves[].*/
{
moves[numberOfMoves] = i;
i = parents[i];
numberOfMoves++;
}
for (numberOfMoves--, direction = NORTH; numberOfMoves >= 0; numberOfMoves--)
{
for (int e = 0; e < 4; e++)
{
if (moves[numberOfMoves] == *memPos + moveMem[direction])
{
ai->direction = direction;
print_maze(maze, ai);
getchar();
ai->position += moveMaze[direction];
*memPos += moveMem[direction];
print_maze(maze, ai);
getchar();
break;
}
else
{
direction++;
if (direction == 4)
direction = NORTH;
}
}
}
return true;
}
/* bfs.
====================================================================================================================================================================================================================================
====================================================================================================================================================================================================================================*/
int bfs(bool goToStart, int *parents, struct Tile *aiMem, int *memPos, int *moveMem, int *moveMaze, struct AI con)
{
unsigned char *memP = (unsigned char*)aiMem;
int t;
resetque();
con.position = *memPos;
parents[con.position] = con.position;
for (; con.position != -1; con.position = deque())
{
for (int e = 0; e < 4; e++)
{
t = con.position + moveMem[con.direction];
if ((memP[con.position] & (1 << con.direction)) == 0 && parents[t] == -1)
{
enque(t);
parents[t] = con.position;
if (goToStart)
{
if (aiMem[t].START)
return t;
}
else if (memP[t] == 0)
return t;
}
con.direction++;
if (con.direction == 4)
con.direction = NORTH;
}
}
return -1;
}
/* print_maze.
====================================================================================================================================================================================================================================
====================================================================================================================================================================================================================================*/
void print_maze(struct Tile *maze, struct AI *ai)
{
int hi, wi;
unsigned char lines[2] = { ' ', '-' }, walls[2] = { ' ','|' }, aiSprites[4] = { 202, 204, 203, 185 }, nv[2] = { 'n', 'v' };
system("cls");
for (hi = 0; hi < height; hi++)
{
for (wi = 0; wi < width; wi++)
printf(" %c ", lines[maze[wi + (hi*width)].N]);
printf("\n");
for (wi = 0; wi < width; wi++)
{
if (ai->position == (wi + (hi*width)))
{
printf("%c", walls[maze[wi + (hi*width)].W]);
SetConsoleTextAttribute(console, 10);
printf("%c", aiSprites[ai->direction]);
SetConsoleTextAttribute(console, 15);
printf("%c", walls[maze[wi + (hi*width)].E]);
}
else
printf("%c%c%c", walls[maze[wi + (hi*width)].W], nv[maze[wi + (hi*width)].V], walls[maze[wi + (hi*width)].E]);
}
printf("\n");
for (wi = 0; wi < width; wi++)
printf(" %c ", lines[maze[wi + (hi*width)].S]);
printf("\n");
}
printf("\n");
}
/* generate_maze.
====================================================================================================================================================================================================================================
====================================================================================================================================================================================================================================*/
void generate_maze(struct Tile *m)
{
// - - - - - - -
// 0 n 1 |n 2 n 3 n| 4 n 5 |n 6 n| 7 n| 8 |n 9 |n| 10 n 11 |n 12 |n| 13 n| 14 |n|
// - - - - - - -
t[1].W = 1,
t[2].N = 1,
t[3].E = 1,
t[4].S = 1,
t[5].N = 1,
t[5].W = 1,
t[6].N = 1,
t[6].E = 1,
t[7].E = 1,
t[7].S = 1,
t[8].S = 1,
t[8].W = 1,
t[9].E = 1,
t[9].W = 1,
t[10].N = 1,
t[10].S = 1,
t[11].N = 1,
t[11].S = 1,
t[11].W = 1,
t[12].N = 1,
t[12].E = 1,
t[12].W = 1,
t[13].N = 1,
t[13].E = 1,
t[13].S = 1,
t[14].E = 1,
t[14].S = 1,
t[14].W = 1;
/*
width = 3, height = 3;
m[0] = t[11];
m[1] = t[2];
m[2] = t[6];
m[3] = t[5];
m[4] = t[7];
m[5] = t[9];
m[6] = t[8];
m[7] = t[13];
m[8] = t[14];
*/
width = 6, height = 4;
m[0] = t[12];
m[1] = t[11];
m[2] = t[2];
m[3] = t[2];
m[4] = t[2];
m[5] = t[6];
m[6] = t[1];
m[7] = t[10];
m[8] = t[0];
m[9] = t[0];
m[10] = t[0];
m[11] = t[3];
m[12] = t[1];
m[13] = t[6];
m[14] = t[1];
m[15] = t[0];
m[16] = t[0];
m[17] = t[3];
m[18] = t[8];
m[19] = t[7];
m[20] = t[8];
m[21] = t[4];
m[22] = t[4];
m[23] = t[7];
m[0].START = true;
}
void resetque(void)
{
head = que;
tail = que;
for (int i = 0; i < QUE_SIZE; i++)
{
que[i].number = -1;
que[i].next = 0;
}
}
bool enque(int num)
{
int i;
struct que_node *newNode;
for (i = 0; i < QUE_SIZE && que[i].number != -1; i++);
if (i == QUE_SIZE)
return false;
tail->number = num;
tail->next = que + i;
tail = tail->next;
return true;
}
int deque(void)
{
struct que_node *oldNode = head;
int num = head->number;
head = head->next;
oldNode->number = -1;
oldNode->next = 0;
return num;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment