From 422ad3b2c2241b423c7767a0d70401eda38a0ffa Mon Sep 17 00:00:00 2001 From: omagdy7 Date: Sun, 16 Apr 2023 04:47:58 +0200 Subject: Implemented an A* but there is a bug that causes a jitter in movement when the manhatten distance is equal --- src/Game.py | 13 +++-- src/Ghost.py | 164 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- src/Player.py | 2 +- 3 files changed, 170 insertions(+), 9 deletions(-) (limited to 'src') diff --git a/src/Game.py b/src/Game.py index 58b8987..a69ad84 100644 --- a/src/Game.py +++ b/src/Game.py @@ -1,5 +1,6 @@ from pygame.mouse import get_pressed import Player +import Ghost from Direction import DIRECTION import settings as Settings import map as Map @@ -24,6 +25,7 @@ class Game(): '../assets/pacman_left_sprite.png').convert_alpha() player = Player.Player(sprite_sheet) + ghost = Ghost.Ghost() # Set the pacman velocity dx = 0 @@ -41,6 +43,8 @@ class Game(): grid_x = Settings.settings.width // len(maze.maze[0]) grid_y = Settings.settings.height // len(maze.maze) + print(grid_x, grid_y) + # Checks collision with walls # checks if the current position of pacman is either a dot, big dot or free @@ -48,6 +52,8 @@ class Game(): is_dot = maze.maze[y][x] == Map.D is_big_dot = maze.maze[y][x] == Map.BD is_free = maze.maze[y][x] == 0 + if is_dot or is_big_dot: + maze.maze[y][x] = 0 return (is_dot or is_free or is_big_dot) @@ -66,11 +72,6 @@ class Game(): return True - - - - - # Main game loop running = True @@ -148,8 +149,10 @@ class Game(): player.y += dy + ghost.move(maze.maze, (player.x, player.y)) maze.draw_map(screen) player.draw(screen, counter) + ghost.draw(screen) # Update the screen pygame.display.flip() diff --git a/src/Ghost.py b/src/Ghost.py index 33086a1..2477bfa 100644 --- a/src/Ghost.py +++ b/src/Ghost.py @@ -1,7 +1,165 @@ +from typing import List +import pygame +import math +from Direction import DIRECTION +import map as Map +import random + class Ghost(): def __init__(self): - self.x = None - self.y = None + self.x = 75 + self.y = 75 + self.tx = 0 + self.ty = 0 + self.speed = 3 + + def heuristic(self, pacman_pos, next_pos): + return abs(next_pos[0] - pacman_pos[0]) + abs(next_pos[1] - pacman_pos[1]) + + + + + # checks if the current position of pacman is either a dot, big dot or free + def is_valid(self, maze, x, y): + is_dot = maze[y][x] == Map.D + is_big_dot = maze[y][x] == Map.BD + is_free = maze[y][x] == 0 + return (is_dot or is_free or is_big_dot) + + + # checks collision with pacman and obstacles returns false if there is a collision and true otherwise + def check_collision(self, nx, ny, gx, gy, maze): + direct_x = [1, 0, -1, 0, 1, 1, -1, -1] + direct_y = [0, 1, 0, -1, -1, 1, -1, 1] + + # print(f"nx: {nx}, ny: {ny}") + # print() + + # print(maze[3][13], self.is_valid(maze, 13, 3)) + print() + if nx == 391 and ny == 79: + print("----------------------") + + for i in range(len(direct_x)): + px = nx + direct_x[i] * 14 + py = ny + direct_y[i] * 14 + print(px, py) + x = px // gx + y = py // gy + # print(f"x: {x}, y: {y} is_valid({x}, {y}) = {self.is_valid(maze, x, y)}") + if not self.is_valid(maze, x, y): + return False + + return True + + def get_possible_moves(self, maze): + possible_directions = {} + + up = (0, -self.speed) + down = (0, self.speed) + right = (self.speed, 0) + left = (-self.speed, 0) + + if self.check_collision(up[0], up[1], 30, 30, maze): + possible_directions[up] = DIRECTION.UP + if self.check_collision(down[0], down[1], 30, 30, maze): + possible_directions[down] = DIRECTION.DOWN + if self.check_collision(right[0], right[1], 30, 30, maze): + possible_directions[right] = DIRECTION.RIGHT + if self.check_collision(left[0], left[1], 30, 30, maze): + possible_directions[left] = DIRECTION.LEFT + + return possible_directions + + + # def get_next_move(self, pacman_pos, maze): + # possible_directions = self.get_possible_moves(maze) + # + # next_move = DIRECTION.RIGHT + # mn = 1000000 # really big number + # + # for pos, dir in possible_directions.items(): + # h = self.heuristic(pacman_pos, pos) + # if h < mn: + # mn = h + # print("dir: ", dir) + # next_move = dir + # + # print("Min h:", mn) + # # print("Left: ", self.heuristic(pacman_pos)) + # print("Best: next_move", next_move) + # return next_move + + + def get_next_move(self, pacman_pos, maze): + dx = [1, 0, -1, 0] + dy = [0, 1, 0, -1] + + + ret = len(dx) * [math.inf] + + for i in range(len(dx)): + nx = self.x + dx[i] * self.speed + ny = self.y + dy[i] * self.speed + if self.check_collision(nx, ny, 30, 30, maze): + ret[i] = self.heuristic((nx, ny), pacman_pos) + + + min_idx = ret.index(min(ret)) + # if min_idx == 1: + # print(f"({self.x}, {self.y})") + # print(self.check_collision(391, 79, 30, 30, maze)) + return (dx[min_idx] * self.speed, dy[min_idx] * self.speed) + + + + + + + + def move(self, maze, player_pos): + next_move = self.get_next_move(player_pos, maze) + + dx = 0 + dy = 0 + + self.x += next_move[0] + self.y += next_move[1] + + # if next_move == DIRECTION.UP: + # self.ty = -self.speed + # self.tx = 0 + # elif next_move == DIRECTION.DOWN: + # self.ty = self.speed + # self.tx = 0 + # elif next_move == DIRECTION.RIGHT: + # self.tx = self.speed + # self.ty = 0 + # elif next_move == DIRECTION.LEFT: + # self.tx = -self.speed + # self.ty = 0 + # + # + # if self.check_collision(self.tx, self.ty, 30, 30, maze): + # dx = self.tx + # dy = self.ty + # + # if dx < 0: + # self.direction = DIRECTION.LEFT + # elif dx > 0: + # self.direction = DIRECTION.RIGHT + # elif dy < 0: + # self.direction = DIRECTION.UP + # elif dy > 0: + # self.direction = DIRECTION.DOWN + # + # if self.check_collision(dx, dy, 30, 30, maze): + # self.x += dx + # self.y += dy + + def draw(self, screen): + radius = 30 // 2 + pos = (self.x , self.y) + pygame.draw.circle(screen, 'green', pos, radius) - # def heuristic(self): diff --git a/src/Player.py b/src/Player.py index eac2d62..430a974 100644 --- a/src/Player.py +++ b/src/Player.py @@ -33,7 +33,7 @@ class Player(): self.x = 30 * 17 - 15 self.y = 30 * 25 - 15 self.sprite = get_sprites(sprite_sheet) - self.speed = 5 + self.speed = 6 self.direction = DIRECTION.LEFT def draw(self, screen, counter): -- cgit v1.2.3 From fd985ac6bc684cdbe89e2c93ea098419977a01f5 Mon Sep 17 00:00:00 2001 From: omagdy7 Date: Sun, 16 Apr 2023 06:02:58 +0200 Subject: Sucssessfully implemented A* algorithm on the ghosts --- src/Game.py | 15 +++++-- src/Ghost.py | 139 +++++++++++++++++------------------------------------------ 2 files changed, 51 insertions(+), 103 deletions(-) (limited to 'src') diff --git a/src/Game.py b/src/Game.py index a69ad84..19901a6 100644 --- a/src/Game.py +++ b/src/Game.py @@ -25,7 +25,10 @@ class Game(): '../assets/pacman_left_sprite.png').convert_alpha() player = Player.Player(sprite_sheet) - ghost = Ghost.Ghost() + inky = Ghost.Ghost("green", 75, 75) + pinky = Ghost.Ghost("cyan", 27 * 30, 30 * 30 + 15) + clyde = Ghost.Ghost("red", 27 * 30 + 15, 75) + winky = Ghost.Ghost("purple", 75, 30 * 30 + 15) # Set the pacman velocity dx = 0 @@ -149,10 +152,16 @@ class Game(): player.y += dy - ghost.move(maze.maze, (player.x, player.y)) + inky.move(maze.maze, (player.x, player.y)) + pinky.move(maze.maze, (player.x, player.y)) + winky.move(maze.maze, (player.x, player.y)) + clyde.move(maze.maze, (player.x, player.y)) maze.draw_map(screen) player.draw(screen, counter) - ghost.draw(screen) + inky.draw(screen) + pinky.draw(screen) + winky.draw(screen) + clyde.draw(screen) # Update the screen pygame.display.flip() diff --git a/src/Ghost.py b/src/Ghost.py index 2477bfa..11c195b 100644 --- a/src/Ghost.py +++ b/src/Ghost.py @@ -6,11 +6,11 @@ import map as Map import random class Ghost(): - def __init__(self): - self.x = 75 - self.y = 75 - self.tx = 0 - self.ty = 0 + def __init__(self, color, x, y): + self.x = x + self.y = y + self.color = color + self.last_move = 3 self.speed = 3 def heuristic(self, pacman_pos, next_pos): @@ -32,84 +32,53 @@ class Ghost(): direct_x = [1, 0, -1, 0, 1, 1, -1, -1] direct_y = [0, 1, 0, -1, -1, 1, -1, 1] - # print(f"nx: {nx}, ny: {ny}") - # print() - - # print(maze[3][13], self.is_valid(maze, 13, 3)) - print() - if nx == 391 and ny == 79: - print("----------------------") for i in range(len(direct_x)): px = nx + direct_x[i] * 14 py = ny + direct_y[i] * 14 - print(px, py) x = px // gx y = py // gy - # print(f"x: {x}, y: {y} is_valid({x}, {y}) = {self.is_valid(maze, x, y)}") if not self.is_valid(maze, x, y): return False return True - def get_possible_moves(self, maze): - possible_directions = {} - - up = (0, -self.speed) - down = (0, self.speed) - right = (self.speed, 0) - left = (-self.speed, 0) - - if self.check_collision(up[0], up[1], 30, 30, maze): - possible_directions[up] = DIRECTION.UP - if self.check_collision(down[0], down[1], 30, 30, maze): - possible_directions[down] = DIRECTION.DOWN - if self.check_collision(right[0], right[1], 30, 30, maze): - possible_directions[right] = DIRECTION.RIGHT - if self.check_collision(left[0], left[1], 30, 30, maze): - possible_directions[left] = DIRECTION.LEFT - - return possible_directions - - - # def get_next_move(self, pacman_pos, maze): - # possible_directions = self.get_possible_moves(maze) - # - # next_move = DIRECTION.RIGHT - # mn = 1000000 # really big number - # - # for pos, dir in possible_directions.items(): - # h = self.heuristic(pacman_pos, pos) - # if h < mn: - # mn = h - # print("dir: ", dir) - # next_move = dir - # - # print("Min h:", mn) - # # print("Left: ", self.heuristic(pacman_pos)) - # print("Best: next_move", next_move) - # return next_move - def get_next_move(self, pacman_pos, maze): dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] - ret = len(dx) * [math.inf] + + forbidden = 0 + + if self.last_move == 0: + forbidden = 2 + if self.last_move == 1: + forbidden = 3 + if self.last_move == 2: + forbidden = 0 + if self.last_move == 3: + forbidden = 1 + for i in range(len(dx)): - nx = self.x + dx[i] * self.speed - ny = self.y + dy[i] * self.speed - if self.check_collision(nx, ny, 30, 30, maze): - ret[i] = self.heuristic((nx, ny), pacman_pos) + if i != forbidden: + nx = self.x + dx[i] * self.speed + ny = self.y + dy[i] * self.speed + if self.check_collision(nx, ny, 30, 30, maze): + ret[i] = self.heuristic((nx, ny), pacman_pos) + print("--------------------") min_idx = ret.index(min(ret)) - # if min_idx == 1: - # print(f"({self.x}, {self.y})") - # print(self.check_collision(391, 79, 30, 30, maze)) - return (dx[min_idx] * self.speed, dy[min_idx] * self.speed) + print(f"last_move: {self.last_move}, current_move: {min_idx}") + x1 = self.x + dx[2] * self.speed + y1 = self.y + dy[2] * self.speed + x2 = self.x + dx[0] * self.speed + y2 = self.y + dy[0] * self.speed + print(f"hl = {self.heuristic((x1, y1), pacman_pos)}, h2 = {self.heuristic((x2, y2), pacman_pos)}") + return min_idx @@ -118,48 +87,18 @@ class Ghost(): def move(self, maze, player_pos): - next_move = self.get_next_move(player_pos, maze) - - dx = 0 - dy = 0 - - self.x += next_move[0] - self.y += next_move[1] - - # if next_move == DIRECTION.UP: - # self.ty = -self.speed - # self.tx = 0 - # elif next_move == DIRECTION.DOWN: - # self.ty = self.speed - # self.tx = 0 - # elif next_move == DIRECTION.RIGHT: - # self.tx = self.speed - # self.ty = 0 - # elif next_move == DIRECTION.LEFT: - # self.tx = -self.speed - # self.ty = 0 - # - # - # if self.check_collision(self.tx, self.ty, 30, 30, maze): - # dx = self.tx - # dy = self.ty - # - # if dx < 0: - # self.direction = DIRECTION.LEFT - # elif dx > 0: - # self.direction = DIRECTION.RIGHT - # elif dy < 0: - # self.direction = DIRECTION.UP - # elif dy > 0: - # self.direction = DIRECTION.DOWN - # - # if self.check_collision(dx, dy, 30, 30, maze): - # self.x += dx - # self.y += dy + min_idx = self.get_next_move(player_pos, maze) + dx = [1, 0, -1, 0] + dy = [0, 1, 0, -1] + new_dx = dx[min_idx] * self.speed + new_dy = dy[min_idx] * self.speed + self.x += new_dx + self.y += new_dy + self.last_move = min_idx def draw(self, screen): radius = 30 // 2 pos = (self.x , self.y) - pygame.draw.circle(screen, 'green', pos, radius) + pygame.draw.circle(screen, self.color, pos, radius) -- cgit v1.2.3 From 3634fcc4f9f62d40ea03ba890a3290e05ed20ed8 Mon Sep 17 00:00:00 2001 From: omagdy7 Date: Sun, 16 Apr 2023 17:49:50 +0200 Subject: Added all ghosts with A* search for now --- src/Game.py | 16 ++++++++-------- src/Ghost.py | 10 ---------- src/map.py | 3 ++- 3 files changed, 10 insertions(+), 19 deletions(-) (limited to 'src') diff --git a/src/Game.py b/src/Game.py index 19901a6..e4784c9 100644 --- a/src/Game.py +++ b/src/Game.py @@ -25,10 +25,10 @@ class Game(): '../assets/pacman_left_sprite.png').convert_alpha() player = Player.Player(sprite_sheet) - inky = Ghost.Ghost("green", 75, 75) - pinky = Ghost.Ghost("cyan", 27 * 30, 30 * 30 + 15) - clyde = Ghost.Ghost("red", 27 * 30 + 15, 75) - winky = Ghost.Ghost("purple", 75, 30 * 30 + 15) + blinky = Ghost.Ghost("red", 75, 75) + pinky = Ghost.Ghost("pink", 27 * 30, 30 * 30 + 15) + inky = Ghost.Ghost("orange", 75, 30 * 30 + 15) + clyde = Ghost.Ghost("cyan", 27 * 30 + 15, 75) # Set the pacman velocity dx = 0 @@ -152,15 +152,15 @@ class Game(): player.y += dy - inky.move(maze.maze, (player.x, player.y)) + blinky.move(maze.maze, (player.x, player.y)) pinky.move(maze.maze, (player.x, player.y)) - winky.move(maze.maze, (player.x, player.y)) + inky.move(maze.maze, (player.x, player.y)) clyde.move(maze.maze, (player.x, player.y)) maze.draw_map(screen) player.draw(screen, counter) - inky.draw(screen) + blinky.draw(screen) pinky.draw(screen) - winky.draw(screen) + inky.draw(screen) clyde.draw(screen) # Update the screen diff --git a/src/Ghost.py b/src/Ghost.py index 11c195b..d4bc683 100644 --- a/src/Ghost.py +++ b/src/Ghost.py @@ -1,9 +1,7 @@ -from typing import List import pygame import math from Direction import DIRECTION import map as Map -import random class Ghost(): def __init__(self, color, x, y): @@ -69,15 +67,7 @@ class Ghost(): if self.check_collision(nx, ny, 30, 30, maze): ret[i] = self.heuristic((nx, ny), pacman_pos) - print("--------------------") - min_idx = ret.index(min(ret)) - print(f"last_move: {self.last_move}, current_move: {min_idx}") - x1 = self.x + dx[2] * self.speed - y1 = self.y + dy[2] * self.speed - x2 = self.x + dx[0] * self.speed - y2 = self.y + dy[0] * self.speed - print(f"hl = {self.heuristic((x1, y1), pacman_pos)}, h2 = {self.heuristic((x2, y2), pacman_pos)}") return min_idx diff --git a/src/map.py b/src/map.py index 9248241..34f066a 100644 --- a/src/map.py +++ b/src/map.py @@ -12,6 +12,7 @@ TL = 32 BL = 64 BR = 128 G = 256 +P = 512 PI = math.pi @@ -34,7 +35,7 @@ class Map(): [V, 0, 0, 0, 0, 0, V, D, V, V, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, V, V, D, V, 0, 0, 0, 0, 0, V], [BR, 0, 0, 0, 0, 0, V, D, V, V, 0, TL, H, H, G, G, H, H, TR, 0, V, V, D, V, 0, 0, 0, 0, 0, BL], [H, H, H, H, H, H, BR, D, BL, BR, 0, V, 0, 0, 0, 0, 0, 0, V, 0, BL, BR, D, BL, H, H, H, H, H, H], - [0, 0, 0, 0, 0, 0, 0, D, 0, 0, 0, V, 0, 0, 0, 0, 0, 0, V, 0, 0, 0, D, 0, 0, 0, 0, 0, 0, 0], + [P, 0, 0, 0, 0, 0, 0, D, 0, 0, 0, V, 0, 0, 0, 0, 0, 0, V, 0, 0, 0, D, 0, 0, 0, 0, 0, 0, P], [H, H, H, H, H, H, TR, D, TL, TR, 0, V, 0, 0, 0, 0, 0, 0, V, 0, TL, TR, D, TL, H, H, H, H, H, H], [TR, 0, 0, 0, 0, 0, V, D, V, V, 0, BL, H, H, H, H, H, H, BR, 0, V, V, D, V, 0, 0, 0, 0, 0, TL], [V, 0, 0, 0, 0, 0, V, D, V, V, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, V, V, D, V, 0, 0, 0, 0, 0, V], -- cgit v1.2.3