BFS, queue files

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

10 files changed, 428 insertions, 221 deletions

diff --git a/Makefile b/Makefile
index 8754c3c..15ebcde 100644
--- a/Makefile
+++ b/Makefile
@@ -1,19 +1,14 @@
 CC=gcc
 CFLAGS=-Wall -g -c
 
-all: pacman
-
-pacman: ghosts.o field.o pac.o  pacman.o
-	$(CC) ghosts.o field.o pac.o pacman.o -lncurses -o pacman
+LIBS = -lncurses
 
-field.o: field.c
-	$(CC) $(CFLAGS) field.c
+all: pacman
 
-ghosts.o: ghosts.c
-	$(CC) $(CFLAGS) ghosts.c
+%.o: %.с %.h
+	$(CC) $(CFLAGS) $< -o $@
 
-pacman.o: pacman.c
-	$(CC) $(CFLAGS) pacman.c
+OBJMODULES=field.o ghosts.o pac.o queue.o pacman.o
 
-pac.o: pac.c
-	$(CC) $(CFLAGS) pac.c 
+pacman: $(OBJMODULES)
+	$(CC) $(LIBS) $^ -o $@
diff --git a/field.c b/field.c
index df61097..5bcb813 100644
--- a/field.c
+++ b/field.c
@@ -54,7 +54,7 @@ game_space get_new_field()
 
 static int is_has_point(int i, int j)
 {
-    return !((i == 12 && j == 9) || (i == 12 && j == 18) || 
+    return !((i == 12 && j == 9) || (i == 12 && j == 18) ||
              (i == 14 && j == 18) || (i == 15 && j == 9) ||
              (i == 17 && j == 9) || (i == 17 && j == 18));
 }
@@ -69,30 +69,30 @@ void print_field(game_space field)
             symbol = field[i][j];
             move(i, j);
             switch(symbol) {
-                case '1':
-                case '2':
-                case '3':
-                    if(is_has_point(i, j))
-                        addch('.');
-                    else
-                        addch(' ');
-                    break;
-                case '/':
-                    addch('/');
-                    break;
-                case '.':
+            case '1':
+            case '2':
+            case '3':
+                if(is_has_point(i, j))
                     addch('.');
-                    break;
-                case '#':
-                    addch('#');
-                    break;
+                else
+                    addch(' ');
+                break;
+            case '/':
+                addch('/');
+                break;
+            case '.':
+                addch('.');
+                break;
+            case '#':
+                addch('#');
+                break;
             }
             refresh();
         }
     }
 }
 
-void display_character(int y, int x, int symbol)
+void display_character(int y, int x, enum select_character symbol)
 {
     move(y, x);
     addch(symbol);
@@ -104,28 +104,31 @@ void display_ghosts_on_field(struct ghost_type *red_ghost,
                              struct ghost_type *blue_ghost,
                              struct ghost_type *orange_ghost)
 {
-    display_character(red_ghost->position.y, red_ghost->position.x, '&');
-    display_character(pink_ghost->position.y, pink_ghost->position.x, '&');
-    display_character(blue_ghost->position.y, blue_ghost->position.x, '&');
-    display_character(orange_ghost->position.y, orange_ghost->position.x, '&');
+    display_character(red_ghost->position.y, red_ghost->position.x, ghost_char);
+    display_character(pink_ghost->position.y, pink_ghost->position.x,
+                      ghost_char);
+    display_character(blue_ghost->position.y, blue_ghost->position.x,
+                      ghost_char);
+    display_character(orange_ghost->position.y, orange_ghost->position.x,
+                      ghost_char);
 }
 
-void clear_symbol(game_space field, int y, int x, 
+void eat_or_revert_symbol(game_space field, int y, int x,
                   enum select_character character)
 {
     int symbol = field[y][x];
     move(y, x);
     if(character == ghost_char) {
         switch(symbol) {
-            case '#':
-                addch('#');
-                break;
-            case '.':
-                addch('.');
-                break;
-            case ' ':
-                addch(' ');
-                break;
+        case '#':
+            addch('#');
+            break;
+        case '.':
+            addch('.');
+            break;
+        case ' ':
+            addch(' ');
+            break;
         }
     }
     else if(character == pac_char)
@@ -133,7 +136,7 @@ void clear_symbol(game_space field, int y, int x,
     refresh();
 }
 
-enum intersection_type get_intersection(const game_space field, 
+enum intersection_type get_intersection(const game_space field,
                                           struct ghost_type *ghost)
 {
     int y, x, symbol;
@@ -141,18 +144,19 @@ enum intersection_type get_intersection(const game_space field,
     x = ghost->position.x;
     symbol = field[y][x];
     switch(symbol) {
-        case one_path:
-            return one_path;
-        case two_paths:
-            return two_paths;
-        case three_paths:
-            return three_paths;
-        default:
-            return direct_path;
+    case one_path:
+        return one_path;
+    case two_paths:
+        return two_paths;
+    case three_paths:
+        return three_paths;
+    default:
+        return direct_path;
     }
 }
 
-struct free_directions find_free_directions(game_space field, int y, int x)
+struct free_directions find_free_directions(const game_space field, int y,
+                                            int x)
 {
     struct free_directions found_paths;
     found_paths.left = field[y][x-1] != '/' && field[y][x-1] != '#' ? 1 : 0;
@@ -161,3 +165,9 @@ struct free_directions find_free_directions(game_space field, int y, int x)
     found_paths.down = field[y+1][x] != '/' && field[y+1][x] != '#' ? 1 : 0;
     return found_paths;
 }
+
+int is_obstacle(const game_space field, int x, int y)
+{
+    int symbol = field[y][x];
+    return symbol == door || symbol == block;
+}
diff --git a/field.h b/field.h
index 42992aa..7ac53e8 100644
--- a/field.h
+++ b/field.h
@@ -1,6 +1,13 @@
 #ifndef FIELD_H_SENTRY
 #define FIELD_H_SENTRY
 
+enum {
+    field_width  = 28,
+    field_height = 29,
+    door = '#',
+    block = '/'
+};
+
 enum intersection_type {
     one_path    = '1',
     two_paths   = '2',
@@ -8,13 +15,11 @@ enum intersection_type {
     direct_path
 };
 
-enum { 
-    field_width = 29,
-    field_height = 29
+enum select_character {
+    ghost_char = '&',
+    pac_char = 'C'
 };
 
-enum select_character { ghost_char, pac_char };
-
 typedef char (*game_space)[field_width];
 game_space get_new_field();
 
@@ -27,7 +32,7 @@ struct free_directions {
 
 void print_field(game_space field);
 
-void display_character(int y, int x, int symbol);
+void display_character(int y, int x, enum select_character symbol);
 
 struct ghost_type;
 void display_ghosts_on_field(struct ghost_type *red_ghost,
@@ -35,12 +40,14 @@ void display_ghosts_on_field(struct ghost_type *red_ghost,
                              struct ghost_type *blue_ghost,
                              struct ghost_type *orange_ghost);
 
-void clear_symbol(game_space field, int y, int x, 
+void eat_or_revert_symbol(game_space field, int y, int x,
                   enum select_character character);
 
-enum intersection_type get_intersection(const game_space field, 
+enum intersection_type get_intersection(const game_space field,
                                           struct ghost_type *ghost);
 
 struct free_directions find_free_directions(game_space field, int y, int x);
 
+int is_obstacle(game_space field, int x, int y);
+
 #endif
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);
+            }
+        }
+    }
 }
diff --git a/ghosts.h b/ghosts.h
index 405a5e2..08c2367 100644
--- a/ghosts.h
+++ b/ghosts.h
@@ -11,7 +11,7 @@ enum {
     pink_y = red_y + 1,
     pink_x = red_x - 2,
     pink_home_y = red_home_y,
-    pink_home_x = 1,
+    pink_home_x = 2,
     blue_y = red_y,
     blue_x = red_x-1,
     blue_home_y = 29,
@@ -20,7 +20,6 @@ enum {
     orange_x = red_x - 3,
     orange_home_y = blue_home_y,
     orange_home_x = 0,
-    field_size = 29
 };
 
 enum ghost_color { red, pink, blue, orange };
@@ -43,9 +42,9 @@ struct ghost_type {
 void initialize_ghost(struct ghost_type *ghost, enum ghost_color color);
 
 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);
 
 void make_ghost_moves(game_space field,
@@ -54,12 +53,13 @@ void make_ghost_moves(game_space field,
                       struct ghost_type *blue_ghost,
                       struct ghost_type *orange_ghost);
 
-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));
+struct pacman;
+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));
 
-void breadth_first_search(game_space field, enum intersection_type paths,
-                          struct ghost_type *ghost);
+void breadth_first_search(game_space field, struct ghost_type *ghost,
+                          struct pacman pac);
 
 #endif
diff --git a/pac.c b/pac.c
index 50256d8..1fd4b73 100644
--- a/pac.c
+++ b/pac.c
@@ -10,34 +10,36 @@ void initialize_pac(struct pacman *pac)
     pac->direction = none;
 }
 
-static enum movement_direction get_correct_path(struct pacman *pac,
-                                                struct free_directions 
-                                                                    free_path,
-                                                enum movement_direction 
+static enum movement_direction get_matching_for_directions(game_space field,
+                                                           struct pacman *pac,
+                                                      enum movement_direction
                                                                     direction)
 {
+    struct free_directions free_paths =
+        find_free_directions(field, pac->position.y, pac->position.x);
     switch(direction) {
-        case left:
-            return free_path.left ? left : none;
-        case right:
-            return free_path.right ? right : none;
-        case up:
-            return free_path.up ? up : none;
-        case down:
-            return free_path.down ? down : none;
-        default:
-            return none;
+    case left:
+        return free_paths.left ? left : none;
+    case right:
+        return free_paths.right ? right : none;
+    case up:
+        return free_paths.up ? up : none;
+    case down:
+        return free_paths.down ? down : none;
+    default:
+        return none;
     }
 
 }
 
-void check_remaining_direction(game_space field, struct pacman *pac, 
+#if 0
+void check_remaining_direction(game_space field, struct pacman *pac,
                                enum movement_direction *stored_direction)
 {
     enum movement_direction temp_direction;
-    struct free_directions free_path = 
+    struct free_directions free_path =
         find_free_directions(field, pac->position.y, pac->position.x);
-    enum movement_direction current_direction = 
+    enum movement_direction current_direction =
         stored_direction ? *stored_direction : pac->direction;
     temp_direction = get_correct_path(pac, free_path, current_direction);
     if(temp_direction != none)
@@ -49,8 +51,35 @@ void check_remaining_direction(game_space field, struct pacman *pac,
     if(stored_direction)
         *stored_direction = none;
 }
+#endif
+
+void check_remaining_direction(game_space field, struct pacman *pac,
+                            enum movement_direction *stored_direction)
+{
+    enum movement_direction matching_result;
+    if(*stored_direction == none)
+        pac->direction =
+            get_matching_for_directions(field, pac, pac->direction);
+    else {
+        matching_result =
+            get_matching_for_directions(field, pac, *stored_direction);
+        if(matching_result != none)
+            pac->direction = matching_result;
+        else
+            pac->direction =
+                get_matching_for_directions(field, pac, pac->direction);
+        *stored_direction = none;
+   }
+}
+
+static void check_remaining_direction_after_pressed_key(game_space field,
+                                                        struct pacman *pac)
+{
+    pac->direction =
+        get_matching_for_directions(field, pac, pac->direction);
+}
 
-void change_pac_direction(game_space field, struct pacman *pac, int key, 
+void change_pac_direction(game_space field, struct pacman *pac, int key,
                           enum movement_direction *stored_direction)
 {
     enum state { no, yes } is_changed_direction;
@@ -58,56 +87,56 @@ void change_pac_direction(game_space field, struct pacman *pac, int key,
     struct free_directions path = find_free_directions(field, pac->position.y,
                                                        pac->position.x);
     switch(key) {
-        case KEY_LEFT:
-            if(path.left) {
-                pac->direction = left;
-                is_changed_direction = yes;
-            } else
-                *stored_direction = left;
-            break;
-        case KEY_RIGHT:
-             if(key == KEY_RIGHT && path.right) {
-                 pac->direction = right;
-                 is_changed_direction = yes;
-             } else
-                 *stored_direction = right;
-             break;
-        case KEY_UP:
-             if(key == KEY_UP && path.up) {
-                 pac->direction = up;
-                 is_changed_direction = yes;
-             } else
-                 *stored_direction = up;
-             break;
-        case KEY_DOWN:
-             if(key == KEY_DOWN && path.down) {
-                 pac->direction = down;
-                 is_changed_direction = yes;
-             } else
-                 *stored_direction = down;
-             break;
+    case KEY_LEFT:
+        if(path.left) {
+            pac->direction = left;
+            is_changed_direction = yes;
+        } else
+            *stored_direction = left;
+        break;
+    case KEY_RIGHT:
+         if(path.right) {
+             pac->direction = right;
+             is_changed_direction = yes;
+         } else
+             *stored_direction = right;
+         break;
+    case KEY_UP:
+         if(path.up) {
+             pac->direction = up;
+             is_changed_direction = yes;
+         } else
+             *stored_direction = up;
+         break;
+    case KEY_DOWN:
+         if(path.down) {
+             pac->direction = down;
+             is_changed_direction = yes;
+         } else
+             *stored_direction = down;
+         break;
     }
     if(is_changed_direction == no)
-        check_remaining_direction(field, pac, NULL);
+        check_remaining_direction_after_pressed_key(field, pac);
 }
 
 void make_pac_move(game_space field, struct pacman *pac)
 {
-    clear_symbol(field, pac->position.y, pac->position.x, pac_char);
+    eat_or_revert_symbol(field, pac->position.y, pac->position.x, pac_char);
     switch(pac->direction) {
-        case left:
-            --pac->position.x;
-            return;
-        case right:
-            ++pac->position.x;
-            return;
-        case up:
-            --pac->position.y;
-            return;
-        case down:
-            ++pac->position.y;
-            return;
-        default:
-            return;
+    case left:
+        --pac->position.x;
+        return;
+    case right:
+        ++pac->position.x;
+        return;
+    case up:
+        --pac->position.y;
+        return;
+    case down:
+        ++pac->position.y;
+        return;
+    default:
+        return;
     }
 }
diff --git a/pac.h b/pac.h
index 1125694..e3c5ffa 100644
--- a/pac.h
+++ b/pac.h
@@ -3,7 +3,7 @@
 
 #include "ghosts.h"
 
-enum { 
+enum {
     max_live = 3,
     pac_y = 22,
     pac_x = 14
@@ -18,10 +18,10 @@ struct pacman {
 
 void initialize_pac(struct pacman *pac);
 
-void change_pac_direction(game_space field, struct pacman *pac, int key, 
+void change_pac_direction(game_space field, struct pacman *pac, int key,
                           enum movement_direction *stored_direction);
 
-void check_remaining_direction(game_space field, struct pacman *pac, 
+void check_remaining_direction(game_space field, struct pacman *pac,
                                enum movement_direction *stored_direction);
 
 void make_pac_move(game_space field, struct pacman *pac);
diff --git a/pacman.c b/pacman.c
index c3225b2..5b5b50a 100644
--- a/pacman.c
+++ b/pacman.c
@@ -1,26 +1,28 @@
 #include "field.h"
 #include "ghosts.h"
 #include "pac.h"
+#include "queue.h"
 #include <ncurses.h>
 #include <stdlib.h>
 #include <unistd.h>
 
-enum { 
+enum {
     timeout_duration    = 0,
     sleep_duration      = 190000,
     key_escape          = 27,
     count_get_out_moves = 5
 };
 
-static void pathfinder_stage(game_space field, struct ghost_type *red_ghost, 
-                             struct ghost_type *pink_ghost, 
+static void pathfinder_stage(game_space field, struct pacman pac,
+                             struct ghost_type *red_ghost,
+                             struct ghost_type *pink_ghost,
                              struct ghost_type *blue_ghost,
                              struct ghost_type *orange_ghost)
 {
     enum intersection_type intersection;
     intersection = get_intersection(field, red_ghost);
     if(intersection != direct_path)
-        redirect(field, intersection, red_ghost, breadth_first_search);
+        redirect(field, intersection, red_ghost, pac, breadth_first_search);
 }
 
 int main()
@@ -33,6 +35,7 @@ int main()
     stored_direction = none;
     get_out_stage = count_get_out_moves;
     initscr();
+    start_color();
     cbreak();
     noecho();
     curs_set(0);
@@ -46,31 +49,27 @@ int main()
     initialize_ghost(&blue_ghost, blue);
     initialize_ghost(&orange_ghost, orange);
     initialize_pac(&pac);
-    display_ghosts_on_field(&red_ghost, &pink_ghost, &blue_ghost, 
+    display_ghosts_on_field(&red_ghost, &pink_ghost, &blue_ghost,
                             &orange_ghost);
-    display_character(pac.position.y, pac.position.x, 'C');
+    display_character(pac.position.y, pac.position.x, pac_char);
     usleep(sleep_duration);
     while((key = getch()) != key_escape) {
         if(get_out_stage)
-            pull_out_ghosts(&get_out_stage, &red_ghost, &pink_ghost, 
+            pull_out_ghosts(&get_out_stage, &red_ghost, &pink_ghost,
                             &blue_ghost, &orange_ghost);
         else
-            pathfinder_stage(field, &red_ghost, &pink_ghost, &blue_ghost, 
+            pathfinder_stage(field, pac, &red_ghost, &pink_ghost, &blue_ghost,
                              &orange_ghost);
-        if(key != ERR) 
+        if(key != ERR)
             change_pac_direction(field, &pac, key, &stored_direction);
-        else {
-            if(stored_direction != none)
-                check_remaining_direction(field, &pac, &stored_direction);
-            else
-                check_remaining_direction(field, &pac, NULL);
-        }
-        make_ghost_moves(field, &red_ghost, &pink_ghost, &blue_ghost, 
+        else
+            check_remaining_direction(field, &pac, &stored_direction);
+        make_ghost_moves(field, &red_ghost, &pink_ghost, &blue_ghost,
                          &orange_ghost);
         make_pac_move(field, &pac);
-        display_ghosts_on_field(&red_ghost, &pink_ghost, &blue_ghost, 
+        display_ghosts_on_field(&red_ghost, &pink_ghost, &blue_ghost,
                                 &orange_ghost);
-        display_character(pac.position.y, pac.position.x, 'C');
+        display_character(pac.position.y, pac.position.x, pac_char);
         usleep(sleep_duration);
     }
     endwin();
diff --git a/queue.c b/queue.c
new file mode 100644
index 0000000..dd3dc1b
--- /dev/null
+++ b/queue.c
@@ -0,0 +1,70 @@
+#include "queue.h"
+#include <stdlib.h>
+
+void queue_init(struct queue *q)
+{
+    q->first = NULL;
+    q->last = NULL;
+}
+
+void queue_push(struct queue *q, const struct coordinates *data)
+{
+    struct item *new_element = malloc(sizeof(struct item));
+    new_element->point = *data;
+    new_element->next = NULL;
+    if(!q->first)
+        q->first = q->last = new_element;
+    else {
+        q->last->next = new_element;
+        q->last = q->last->next;
+    }
+}
+
+int empty(const struct queue *q)
+{
+    return q->first ? 0 : 1;
+}
+
+struct coordinates queue_front(const struct queue *q)
+{
+    return q->first->point;
+}
+
+void pop(struct queue *q)
+{
+    struct item *tmp = q->first;
+    q->first = q->first->next;
+    free(tmp);
+}
+
+int equal_points(struct coordinates first_point,
+                        struct coordinates second_point)
+{
+    return first_point.x == second_point.x && first_point.y == second_point.y;
+}
+
+int is_consist_point(const struct queue *q, struct coordinates target_point)
+{
+    enum { false, true };
+    struct item *tmp_item = q->first;
+    struct coordinates tmp_point;
+    while(tmp_item != NULL) {
+        tmp_point = tmp_item->point;
+        if(equal_points(tmp_point, target_point))
+            return true;
+        tmp_item = tmp_item->next;
+    }
+    return false;
+}
+
+void queue_clear(struct queue *q)
+{
+    struct item *tmp;
+    while(q->first != NULL) {
+       tmp = q->first;
+       q->first = q->first->next;
+       free(tmp);
+    }
+    q->first = NULL;
+    q->last = NULL;
+}
diff --git a/queue.h b/queue.h
new file mode 100644
index 0000000..413b76f
--- /dev/null
+++ b/queue.h
@@ -0,0 +1,25 @@
+#ifndef QUEUE_H_SENTRY
+#define QUEUE_H_SENTRY
+
+#include "ghosts.h"
+
+struct item {
+    struct coordinates point;
+    struct item *next;
+};
+
+struct queue {
+    struct item *first;
+    struct item *last;
+};
+
+void queue_init(struct queue *q);
+void queue_push(struct queue *q, const struct coordinates *data);
+struct coordinates queue_front(const struct queue *q);
+int empty(const struct queue *q);
+void pop(struct queue *q);
+int equal_points(struct coordinates tmp_point, struct coordinates target_point);
+int is_consist_point(const struct queue *q, struct coordinates target_point);
+void queue_clear(struct queue *q);
+
+#endif