From 2c2448cc94b8f17ac699814a75110411d57f3bea Mon Sep 17 00:00:00 2001 From: scratko Date: Sun, 7 Apr 2024 03:07:42 +0300 Subject: BFS, queue files Fixed remaining direction check for pacman (old version was commented out). Breadth First Search for red ghost. Changed switch style. --- ghosts.c | 204 ++++++++++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 138 insertions(+), 66 deletions(-) (limited to 'ghosts.c') 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 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); + } + } + } } -- cgit v1.2.3