30.0 Maze: DFS generation

___# define S 4 // define 4 possible directions to move

___struct position // define data type for 2D coordinates

___{ int x, y;

___}; // offset tables are with type "cood"

___struct cood // define data type for 2D offsets

___{ int dx, dy;

___}; // offset tables are with type "cood"

___struct position step, next, stack[200];

___struct cood f1[S]; struct cood f2[S];

___int ** w; int top = -1, d;

___void initiation() // initialize offset tables

___{ f1[0].dx=0; f1[0].dy= 1; f1[1].dx=-1; f1[1].dy=0;

______f1[2].dx=0; f1[2].dy=-1; f1[3].dx= 1; f1[3].dy=0;

______f2[0].dx=0; f2[0].dy= 2; f2[1].dx=-2; f2[1].dy=0;

______f2[2].dx=0; f2[2].dy=-2; f2[3].dx= 2; f2[3].dy=0;

______for (int i=0; i<S; i++)

_________for (int j=0; j<S; j++)

____________w[i][j] = 1; // 2D space full of walls

___}

___int NextMove(struct position step)

___{ for (int i=0; i<S; i++)

_________if (w[step.x+f2[i].dx][step.y+f2[i].dy]==1) return 1;

______return 0;

___}

___int ** MazeDFS(struct position step)

___{ push(step); w[step.x][step.y] = 0;

______while (top != -1)

______{ step = pop();

_________while (NextMove(step))

_________{ d = rand()%S;

____________next.x = step.x+f2[d].dx;

____________next.y = step.y+f2[d].dy;

____________if (w[next.x][next.y]==1)

____________{ w[step.x+f1[d].dx][step.y+f1[d].dy] = 0;

__________________push(next);

__________________w[next.x][next.y] = 0;

__________________step = next;

____________}

_________}

______}

______return w;

___}