Searching for all ghosts

4 files changed, 215 insertions, 35 deletions

diff --git a/Makefile b/Makefile
index 15ebcde..796dbbb 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 CC=gcc
 CFLAGS=-Wall -g -c
 
-LIBS = -lncurses
+LIBS = -lncurses -lm
 
 all: pacman
 
diff --git a/ghosts.c b/ghosts.c
index 0029702..61c1bb1 100644
--- a/ghosts.c
+++ b/ghosts.c
@@ -3,6 +3,10 @@
 #include "pac.h"
 #include "queue.h"
 #include <ncurses.h>
+#include <math.h>
+#include <stdlib.h>
+
+enum search_flag { viewed, not_viewed };
 
 void initialize_ghost(struct ghost_type *ghost, enum ghost_color color)
 {
@@ -110,29 +114,68 @@ void make_ghost_moves(game_space field,
 
 static void pave_only_way(game_space field, struct ghost_type *ghost)
 {
-   struct free_directions path = find_free_directions(field, ghost->position.y,
-                                                      ghost->position.x);
-   enum movement_direction reverse_direction = ghost->direction;
-   reverse_direction ^= 1;
-   if(path.left && left != reverse_direction)
-       ghost->direction = left;
-   else if(path.right && right != reverse_direction)
-       ghost->direction = right;
-   else if(path.up && up != reverse_direction)
-       ghost->direction = up;
-   else if(path.down && down != reverse_direction)
-       ghost->direction = down;
+    struct free_directions path = find_free_directions(field, ghost->position.y,
+                                                       ghost->position.x);
+    enum movement_direction reverse_direction = ghost->direction;
+    reverse_direction ^= 1;
+    if(path.left && left != reverse_direction)
+        ghost->direction = left;
+    else if(path.right && right != reverse_direction)
+        ghost->direction = right;
+    else if(path.up && up != reverse_direction)
+        ghost->direction = up;
+    else if(path.down && down != reverse_direction)
+        ghost->direction = down;
+}
+
+struct coordinates identify_blue_target(struct pacman pac,
+                                        const struct ghost_type *red_ghost)
+{
+    struct coordinates difference, middle_point, result_point;
+    middle_point = identify_target_in_front(pac, blue_shift);
+    difference.x = middle_point.x - red_ghost->position.x;
+    difference.y = middle_point.y - red_ghost->position.y;
+    result_point.x = middle_point.x + difference.x;
+    result_point.y = middle_point.y + difference.y;
+    return result_point;
+}
+
+struct coordinates identify_target_in_front(struct pacman pac, int shift)
+{
+    int x, y;
+    struct coordinates target;
+    x = pac.position.x;
+    y = pac.position.y;
+    switch(pac.direction) {
+    case left:
+        x -= shift;
+        break;
+    case right:
+        x += shift;
+        break;
+    case up:
+        y -= shift;
+        break;
+    case down:
+        y += shift;
+        break;
+    default:
+        ;
+    }
+    target.x = x;
+    target.y = y;
+    return target;
 }
 
 void redirect(game_space field, enum intersection_type paths,
-              struct ghost_type *ghost, struct pacman pac,
+              struct ghost_type *ghost, struct coordinates target_point,
               void (*pathfinder)(game_space, struct ghost_type*,
-                    struct pacman pac))
+                    struct coordinates target_point))
 {
     if(paths == one_path)
         pave_only_way(field, ghost);
     else
-        pathfinder(field, ghost, pac);
+        pathfinder(field, ghost, target_point);
 }
 
 static struct coordinates get_near_point(struct coordinates consider_point,
@@ -144,7 +187,6 @@ static struct coordinates get_near_point(struct coordinates consider_point,
     return found_point;
 }
 
-
 static enum movement_direction find_direction(struct coordinates found_point,
                                               struct coordinates ghost_position)
 {
@@ -166,13 +208,30 @@ static enum movement_direction find_direction(struct coordinates found_point,
     return new_direction;
 }
 
+static void clear_both_queues(struct queue *next_points,
+                              struct queue *reviewed_points)
+{
+    queue_clear(next_points);
+    queue_clear(reviewed_points);
+}
+
+static int is_bfs_search_for_orange(enum search_flag current_width,
+                                    int move_count)
+{
+    if(current_width == not_viewed)
+        ++move_count;
+    return move_count > orange_search_limit;
+}
+
 void breadth_first_search(game_space field, struct ghost_type *ghost,
-                          struct pacman pac)
+                          struct coordinates target_point)
 {
+    int move_count;
+    enum search_flag current_width = not_viewed;
     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;
+    move_count = 0;
     queue_init(&next_points);
     queue_init(&reviewed_points);
     queue_push(&next_points, &target_point);
@@ -189,24 +248,106 @@ void breadth_first_search(game_space field, struct ghost_type *ghost,
                 near_point = get_near_point(consider_point, dx, dy);
                 if(is_obstacle(field, near_point.x, near_point.y))
                     continue;
-                if(queue_consists_point(&next_points, near_point))
+                if(queue_consists_point(&reviewed_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)) {
+                    if(ghost->color == orange)
+                        if(!is_bfs_search_for_orange(current_width,
+                                                     move_count)) {
+                            redirect(field, two_paths, ghost,
+                                     ghost->home_position,
+                                     compute_distance_between_points);
+                            clear_both_queues(&next_points, &reviewed_points);
+                            return;
+                        }
                     ghost->direction =
                         find_direction(consider_point, start_point);
-                    queue_clear(&next_points);
+                    clear_both_queues(&next_points, &reviewed_points);
                     return;
                 }
+                if(ghost->color == orange && current_width == not_viewed) {
+                    current_width = viewed;
+                    ++move_count;
+                }
                 queue_push(&next_points, &near_point);
+                queue_push(&reviewed_points, &near_point);
             }
         }
+        current_width = not_viewed;
+    }
+}
+
+static int standard_distance(int x1, int y1, int x2, int y2)
+{
+    int dx, dy;
+    dx = abs(x1 - x2);
+    dx = dx > field_width ? field_width - dx : dx;
+    dy = abs(y1 - y2);
+    return sqrt(dx*dx + dy*dy);
+ }
+
+static int is_minimal_distance(int min_distance, int tmp_distance,
+                               enum movement_direction cur_direction)
+{
+    return min_distance == 0 || tmp_distance < min_distance ||
+           (tmp_distance == min_distance && cur_direction != right);
+}
+
+static void set_final_direction(int *min_distance,
+                                enum movement_direction cur_direction,
+                                enum movement_direction *final_direction,
+                                struct coordinates initial_point,
+                                struct coordinates target_point)
+{
+    int x1, y1, x2, y2;
+    int tmp_distance;
+    x1 = initial_point.x;
+    y1 = initial_point.y;
+    x2 = target_point.x;
+    y2 = target_point.y;
+    tmp_distance = standard_distance(x1, y1, x2, y2);
+    if(is_minimal_distance(*min_distance, tmp_distance, cur_direction)) {
+        *min_distance = tmp_distance;
+        *final_direction = cur_direction;
+    }
+}
+
+void compute_distance_between_points(game_space field,
+                                     struct ghost_type *ghost,
+                                     struct coordinates target_point)
+{
+    enum movement_direction final_direction, ghost_direction;
+    struct coordinates initial_point, changed_initial_point;
+    int min_distance;
+    final_direction = none;
+    ghost_direction = ghost->direction;
+    initial_point = ghost->position;
+    min_distance = 0;
+    struct free_directions consider_paths =
+        find_free_directions(field, initial_point.y, initial_point.x);
+    if(consider_paths.right && ghost_direction != left) {
+        changed_initial_point.x = initial_point.x + 1;
+        changed_initial_point.y = initial_point.y;
+        set_final_direction(&min_distance, right, &final_direction,
+                            changed_initial_point, target_point);
+    }
+    if(consider_paths.down && ghost_direction != up) {
+        changed_initial_point.x = initial_point.x;
+        changed_initial_point.y = initial_point.y + 1;
+        set_final_direction(&min_distance, down, &final_direction,
+                            changed_initial_point, target_point);
+    }
+    if(consider_paths.left && ghost_direction != right) {
+        changed_initial_point.x = initial_point.x - 1;
+        changed_initial_point.y = initial_point.y;
+        set_final_direction(&min_distance, left, &final_direction,
+                            changed_initial_point, target_point);
+    }
+    if(consider_paths.up && ghost_direction != down) {
+        changed_initial_point.x = initial_point.x;
+        changed_initial_point.y = initial_point.y - 1;
+        set_final_direction(&min_distance, up, &final_direction,
+                            changed_initial_point, target_point);
     }
+    ghost->direction = final_direction;
 }
diff --git a/ghosts.h b/ghosts.h
index 7830a97..f407839 100644
--- a/ghosts.h
+++ b/ghosts.h
@@ -20,6 +20,9 @@ enum {
     orange_x = red_x - 3,
     orange_home_y = blue_home_y,
     orange_home_x = 0,
+    pink_shift = 4,
+    blue_shift = 2,
+    orange_search_limit = 8
 };
 
 enum ghost_color { red, pink, blue, orange };
@@ -57,11 +60,18 @@ void make_ghost_moves(game_space field,
 
 struct pacman;
 void redirect(game_space field, enum intersection_type paths,
-              struct ghost_type *ghost, struct pacman pac,
+              struct ghost_type *ghost, struct coordinates target_point,
               void (*pathfinder)(game_space, struct ghost_type*,
-                    struct pacman pac));
+                    struct coordinates target_point));
 
 void breadth_first_search(game_space field, struct ghost_type *ghost,
-                          struct pacman pac);
+                          struct coordinates target_point);
+
+void compute_distance_between_points(game_space field, struct ghost_type *ghost,
+                                     struct coordinates target_point);
+
+struct coordinates identify_target_in_front(struct pacman pac, int shift);
+struct coordinates identify_blue_target(struct pacman pac,
+                                        const struct ghost_type *red_ghost);
 
 #endif
diff --git a/pacman.c b/pacman.c
index 9346055..f2e0161 100644
--- a/pacman.c
+++ b/pacman.c
@@ -19,10 +19,39 @@ static void pathfinder_stage(game_space field, struct pacman pac,
                              struct ghost_type *blue_ghost,
                              struct ghost_type *orange_ghost)
 {
+    void (*search_method)(game_space, struct ghost_type*, struct coordinates);
     enum intersection_type intersection;
-    intersection = get_intersection(field, red_ghost);
-    if(intersection != direct_path)
-        redirect(field, intersection, red_ghost, pac, breadth_first_search);
+    int color_priority;
+    struct ghost_type *current_ghost;
+    struct coordinates target_point;
+    for(color_priority = 0; color_priority <= orange; ++color_priority) {
+        switch(color_priority) {
+        case red:
+            current_ghost = red_ghost;
+            target_point = pac.position;
+            search_method = breadth_first_search;
+            break;
+        case pink:
+            current_ghost = pink_ghost;
+            target_point = identify_target_in_front(pac, pink_shift);
+            search_method = compute_distance_between_points;
+            break;
+        case blue:
+            current_ghost = blue_ghost;
+            target_point = identify_blue_target(pac, red_ghost);
+            search_method = compute_distance_between_points;
+            break;
+        case orange:
+            current_ghost = orange_ghost;
+            target_point = pac.position;
+            search_method = breadth_first_search;
+            break;
+        }
+        intersection = get_intersection(field, current_ghost);
+        if(intersection != direct_path)
+            redirect(field, intersection, current_ghost, target_point,
+                     search_method);
+    }
 }
 
 static void initialize_ghosts(struct ghost_type *red_ghost,