diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | ghosts.c | 197 | ||||
| -rw-r--r-- | ghosts.h | 16 | ||||
| -rw-r--r-- | pacman.c | 35 |
4 files changed, 215 insertions, 35 deletions
@@ -1,7 +1,7 @@ CC=gcc CFLAGS=-Wall -g -c -LIBS = -lncurses +LIBS = -lncurses -lm all: pacman @@ -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; } @@ -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 @@ -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, |