+static int
+already_tried (ghoststruct *g, int x, int y)
+{
+ int i = 0;
+ if (! ( 0 <= g->trace_idx && g->trace_idx < GHOST_TRACE ) ){
+ fprintf(stderr, "FOUND TRACE ERROR. DUMPING TRACE.\n");
+ fprintf(stderr, "%d\n", g->trace_idx );
+ for ( i = 0; i < GHOST_TRACE; i++ ){
+ fprintf(stderr, "( %d, %d )\n", g->trace[i].vx, g->trace[i].vy );
+ }
+ assert ( False );
+ }
+ while (i < g->trace_idx){
+ if ( x == g->trace[i].vx && y == g->trace[i].vy ){
+ /* fprintf ( stderr, "Match FOUND (%d, %d)\n", x, y); */
+ return 1;
+ }
+ i++;
+ }
+ return 0;
+}
+#endif
+
+static void
+store_dir ( ghoststruct *g, pos ps ){
+ int i = g->home_count;
+ assert ( 0 <= i && i < GHOST_TRACE );
+ g->way_home[i].vx = dirvecs[ps].dx;
+ g->way_home[i].vy = dirvecs[ps].dy;
+ g->home_count++;
+}
+
+static void
+clear_dir ( ghoststruct *g ){
+ int i = 0;
+ g->home_count = 0;
+ g->home_idx = 0;
+ while (i < GHOST_TRACE){
+ g->way_home[i].vx = -1;
+ g->way_home[i++].vy = -1;
+ }
+}
+
+static int
+found_jail ( int col, int row ){
+ int cx, cy;
+ pacman_get_jail_opening ( &cx, &cy );
+ cy += 1;
+ if (row == cy && col == cx )
+ return 1;
+ else
+ return 0;
+}
+
+static int
+move_ghost ( pacmangamestruct * pp,
+ int row, int col,
+ pos ps,
+ int *new_row, int *new_col){
+ int idx = (int)ps;
+ int tr = row + dirvecs[idx].dx;
+ int tc = col + dirvecs[idx].dy;
+ if ( pacman_check_pos ( pp, tr, tc, True )){
+ *new_row = tr;
+ *new_col = tc;
+ return True;
+ }
+ else {
+ return False;
+ }
+}
+
+static int
+recur_back_track ( pacmangamestruct * pp, ghoststruct *g, int row, int col ){
+ int new_row, new_col;
+
+ if ( already_tried ( g, col, row ) )
+ return False;
+
+ if ( found_jail ( col, row ) )
+ return True;
+
+ save_position ( g, col, row );
+
+ if ( move_ghost ( pp, row, col, pos_left, &new_row, &new_col ))
+ if ( recur_back_track ( pp, g, new_row, new_col )){
+ store_dir ( g, pos_left );
+ return True;
+ }
+
+ if ( move_ghost ( pp, row, col, pos_up, &new_row, &new_col ))
+ if ( recur_back_track ( pp, g, new_row, new_col )){
+ store_dir ( g, pos_up );
+ return True;
+ }
+
+ if ( move_ghost ( pp, row, col, pos_down, &new_row, &new_col ))
+ if ( recur_back_track ( pp, g, new_row, new_col )){
+ store_dir ( g, pos_down );
+ return True;
+ }
+
+ if ( move_ghost ( pp, row, col, pos_right, &new_row, &new_col ))
+ if ( recur_back_track ( pp, g, new_row, new_col )){
+ store_dir ( g, pos_right );
+ return True;
+ }
+
+ return False;
+}
+
+static void
+find_home ( pacmangamestruct *pp, ghoststruct *g ){
+ int i;
+ int r,c;
+ int cx, cy;
+ ghoststruct *tmp_ghost;
+ tmp_ghost = (ghoststruct*)malloc(sizeof ( ghoststruct ));
+ if ( tmp_ghost == NULL ){
+ fprintf(stderr, "find_home : Could not allocate memory.");
+ exit ( 1 );
+ }
+ tmp_ghost = memmove(tmp_ghost, g, sizeof ( ghoststruct ));
+ if ( tmp_ghost == NULL ){
+ fprintf(stderr, "find_home : Could not copy memory.");
+ exit ( 1 );
+ }
+ clear_trace ( tmp_ghost );
+ clear_dir ( tmp_ghost );
+ r = tmp_ghost->row;
+ c = tmp_ghost->col;
+ if ( ! recur_back_track ( pp, tmp_ghost, r, c ) ){
+ fprintf(stderr, "Could not find way home.#@$?\n");
+ pacman_get_jail_opening ( &cx, &cy);
+ fprintf(stderr, "Jail was at (%d%d)\n", cx,cy);
+ }
+ for ( i = 0; i < GHOST_TRACE; i++ ){
+ g->way_home[i].vx = tmp_ghost->way_home[i].vx;
+ g->way_home[i].vy = tmp_ghost->way_home[i].vy;
+ }
+ g->home_count = tmp_ghost->home_count;
+ g->home_idx = tmp_ghost->home_count;
+ free(tmp_ghost);
+}
+
+/* Make the ghost go back to the inbox */
+static void
+ghost_goingin (pacmangamestruct * pp, ghoststruct * g)
+{
+ g->home_idx--;
+ if (g->home_idx < 0){ g->aistate = goingout; return;}
+ /* row == vx ? wtf... Don't Ask */
+ g->nextrow = g->row + g->way_home[g->home_idx].vx;
+ g->nextcol = g->col + g->way_home[g->home_idx].vy;
+}
+
+