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/Ghost.py | 164 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 161 insertions(+), 3 deletions(-) (limited to 'src/Ghost.py') 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): -- 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/Ghost.py | 139 +++++++++++++++++------------------------------------------ 1 file changed, 39 insertions(+), 100 deletions(-) (limited to 'src/Ghost.py') 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/Ghost.py | 10 ---------- 1 file changed, 10 deletions(-) (limited to 'src/Ghost.py') 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 -- cgit v1.2.3