BFS, queue files

Fixed remaining direction check for pacman (old version was commented out).
Breadth First Search for red ghost.
Changed switch style.

1 files changed, 138 insertions, 66 deletions

diff --git a/ghosts.c b/ghosts.c
index 2559740..7a320ec 100644
--- a/ghosts.c
+++ b/ghosts.c
@@ -1,52 +1,55 @@
 #include "ghosts.h"
 #include "field.h"
+#include "pac.h"
+#include "queue.h"
+#include <ncurses.h>
 
 void initialize_ghost(struct ghost_type *ghost, enum ghost_color color)
 {
     switch(color) {
-        case red:
-            ghost->position.y = red_y;
-            ghost->position.x = red_x;
-            ghost->home_position.y = red_home_y;
-            ghost->home_position.x = red_home_x;
-            ghost->color = red;
-            ghost->mode = scatter;
-            ghost->direction = none;
-            break;
-        case pink:
-            ghost->position.y = pink_y;
-            ghost->position.x = pink_x;
-            ghost->home_position.y = pink_home_y;
-            ghost->home_position.x = pink_home_x;
-            ghost->color = pink;
-            ghost->mode = scatter;
-            ghost->direction = none;
-            break;
-        case blue:
-            ghost->position.y = blue_y;
-            ghost->position.x = blue_x;
-            ghost->home_position.y = blue_home_y;
-            ghost->home_position.x = blue_home_x;
-            ghost->color = blue;
-            ghost->mode = scatter;
-            ghost->direction = none;
-            break;
-        case orange:
-            ghost->position.y = orange_y;
-            ghost->position.x = orange_x;
-            ghost->home_position.y = orange_home_y;
-            ghost->home_position.x = orange_home_x;
-            ghost->color = orange;
-            ghost->mode = scatter;
-            ghost->direction = none;
-            break;
+    case red:
+        ghost->position.y = red_y;
+        ghost->position.x = red_x;
+        ghost->home_position.y = red_home_y;
+        ghost->home_position.x = red_home_x;
+        ghost->color = red;
+        ghost->mode = scatter;
+        ghost->direction = none;
+        break;
+    case pink:
+        ghost->position.y = pink_y;
+        ghost->position.x = pink_x;
+        ghost->home_position.y = pink_home_y;
+        ghost->home_position.x = pink_home_x;
+        ghost->color = pink;
+        ghost->mode = scatter;
+        ghost->direction = none;
+        break;
+    case blue:
+        ghost->position.y = blue_y;
+        ghost->position.x = blue_x;
+        ghost->home_position.y = blue_home_y;
+        ghost->home_position.x = blue_home_x;
+        ghost->color = blue;
+        ghost->mode = scatter;
+        ghost->direction = none;
+        break;
+    case orange:
+        ghost->position.y = orange_y;
+        ghost->position.x = orange_x;
+        ghost->home_position.y = orange_home_y;
+        ghost->home_position.x = orange_home_x;
+        ghost->color = orange;
+        ghost->mode = scatter;
+        ghost->direction = none;
+        break;
     }
 }
 
 void pull_out_ghosts(int *get_out_stage,
-                     struct ghost_type *red_ghost, 
+                     struct ghost_type *red_ghost,
                      struct ghost_type *pink_ghost,
-                     struct ghost_type *blue_ghost, 
+                     struct ghost_type *blue_ghost,
                      struct ghost_type *orange_ghost)
 {
     enum { final_stage = 1 };
@@ -64,24 +67,24 @@ void pull_out_ghosts(int *get_out_stage,
     --*get_out_stage;
 }
 
-static void change_position(struct ghost_type *ghost, 
+static void change_position(struct ghost_type *ghost,
                             enum movement_direction direction)
 {
     switch(direction) {
-        case left:
-            --ghost->position.x;
-            return;
-        case right:
-            ++ghost->position.x;
-            return;
-        case up:
-            --ghost->position.y;
-            return;
-        case down:
-            ++ghost->position.y;
-            return;
-        default:
-            return;
+    case left:
+        --ghost->position.x;
+        return;
+    case right:
+        ++ghost->position.x;
+        return;
+    case up:
+        --ghost->position.y;
+        return;
+    case down:
+        ++ghost->position.y;
+        return;
+    default:
+        return;
     }
 }
 
@@ -91,14 +94,14 @@ void make_ghost_moves(game_space field,
                       struct ghost_type *blue_ghost,
                       struct ghost_type *orange_ghost)
 {
-    clear_symbol(field, red_ghost->position.y, red_ghost->position.x, 
+    eat_or_revert_symbol(field, red_ghost->position.y, red_ghost->position.x,
                  ghost_char);
-    clear_symbol(field, pink_ghost->position.y, pink_ghost->position.x, 
+    eat_or_revert_symbol(field, pink_ghost->position.y, pink_ghost->position.x,
                  ghost_char);
-    clear_symbol(field, blue_ghost->position.y, blue_ghost->position.x, 
-                 ghost_char);
-    clear_symbol(field, orange_ghost->position.y, orange_ghost->position.x, 
+    eat_or_revert_symbol(field, blue_ghost->position.y, blue_ghost->position.x,
                  ghost_char);
+    eat_or_revert_symbol(field, orange_ghost->position.y,
+                         orange_ghost->position.x, ghost_char);
     change_position(red_ghost, red_ghost->direction);
     change_position(pink_ghost, pink_ghost->direction);
     change_position(blue_ghost, blue_ghost->direction);
@@ -121,20 +124,89 @@ static void pave_only_way(game_space field, struct ghost_type *ghost)
        ghost->direction = down;
 }
 
-void redirect(game_space field, enum intersection_type paths, 
-              struct ghost_type *ghost, 
-              void (*pathfinder)(game_space field, enum intersection_type paths,
-                                 struct ghost_type *ghost))
+void redirect(game_space field, enum intersection_type paths,
+              struct ghost_type *ghost, struct pacman pac,
+              void (*pathfinder)(game_space, struct ghost_type*,
+                    struct pacman pac))
 {
     if(paths == one_path)
         pave_only_way(field, ghost);
-    else if(paths == two_paths || paths == three_paths)
-        pathfinder(field, paths, ghost);
+    else
+        pathfinder(field, ghost, pac);
+}
+
+static struct coordinates get_near_point(struct coordinates consider_point,
+                                         int dx, int dy)
+{
+    struct coordinates found_point;
+    found_point.x = consider_point.x + dx;
+    found_point.y = consider_point.y + dy;
+    return found_point;
 }
 
 
-void breadth_first_search(game_space field, enum intersection_type paths,
-                          struct ghost_type *ghost)
+static enum movement_direction find_direction(struct coordinates found_point,
+                                              struct coordinates ghost_position)
 {
+    int dx, dy;
+    enum movement_direction new_direction;
+    dx = found_point.x - ghost_position.x;
+    dy = found_point.y - ghost_position.y;
+    switch(dx) {
+    case 1:
+        new_direction = dy == 0 ? right : none;
+        break;
+    case 0:
+        new_direction = dy == -1 ? up : down;
+        break;
+    case -1:
+        new_direction = dy == 0 ? left : none;
+        break;
+    }
+    return new_direction;
+}
 
+void breadth_first_search(game_space field, struct ghost_type *ghost,
+                          struct pacman pac)
+{
+    struct coordinates consider_point, near_point;
+    struct coordinates start_point = { ghost->position.y, ghost->position.x };
+    struct coordinates target_point = { pac.position.y, pac.position.x };
+    struct queue next_points, reviewed_points;
+    queue_init(&next_points);
+    queue_init(&reviewed_points);
+    queue_push(&next_points, &target_point);
+    queue_push(&reviewed_points, &target_point);
+    while(!empty(&next_points)) {
+        consider_point = queue_front(&next_points);
+        pop(&next_points);
+        int dx;
+        for(dx = -1; dx <= 1; ++dx) {
+            int dy;
+            for(dy = -1; dy <= 1; ++dy) {
+                if(dx != 0 && dy != 0)
+                    continue;
+                near_point = get_near_point(consider_point, dx, dy);
+                if(is_obstacle(field, near_point.x, near_point.y))
+                    continue;
+                if(is_consist_point(&next_points, near_point))
+                    continue;
+#if 0
+                init_pair(1, COLOR_RED, COLOR_BLACK);
+                attron(COLOR_PAIR(1));
+                move(near_point.y, near_point.x);
+                addch('X');
+                attron(COLOR_PAIR(1));
+                refresh();
+#endif
+                if(equal_points(start_point, near_point)) {
+                    ghost->direction =
+                        find_direction(consider_point, start_point);
+                    queue_clear(&next_points);
+                    return;
+                }
+                queue_push(&next_points, &near_point);
+            }
+        }
+    }
 }