Jul-03-2023, 05:27 PM
GitHub URL: https://github.com/ProarchwasTaken/path_test/tree/main
I figured out how to write a basic pathfinding algorithm in pygame, and I'm pretty proud of it. So I was wondering if there's anything I could've done better.
main.py
I figured out how to write a basic pathfinding algorithm in pygame, and I'm pretty proud of it. So I was wondering if there's anything I could've done better.
main.py
from constants import * import sys import pygame import time """==================================================================================================================== Pathfinding Algorithm written by: Tyler I managed to write a pathfinding system without watching any direct coding tutorials on how to do it. All I've really done before codeing this, is watch a video on how pathfinding algorithms generally work and figured out the rest. It wasn't easy though, this is probably the most lines of code I've written into a project so far. I've also went about doing a different script structure than normal. Personally I think it looks better. CONTROLS: - Click a tile to add/remove a wall. - Right click to place/move the target tile - Press the Space key and watch the magic happen! The reason I went ahead to do this is because I figured that knowing how to do pathfinding is one of those things that are necessary to making most games. Along with animations, spritesheets, serialization, and the works. Hopefully I can write a more efficient system in the future, so what do you think? Thanks for checking this out! =====================================================================================================================""" # Main program function def Program(): pygame.init() # General Imports from pathfinding import Agent, Target from grid import Grid # Window setup screen = pygame.display.set_mode((WINDOW_WIDTH, WINDOW_HEIGHT)) viewport = pygame.Surface((WINDOW_WIDTH, WINDOW_HEIGHT)) # Game Clock setup Clock = pygame.time.Clock() prevTime = time.time() # Class Instances Grid.obj = Grid(0, 0, 1) Agent.obj = Agent(10, 10, prevTime) # (Tile X, Tile Y, prevTime) # Main game loop while True: # Ticks the clock, making the program only run at a maximum set FPS Clock.tick(FPS) # FPS Counter pygame.display.set_caption(f"Pathfinding | FPS: {round(Clock.get_fps())}") # Gets the current time. curTime = time.time() # Gets deltatime value. deltaTime = curTime - prevTime # Resets prevTime to curTime prevTime = curTime # Clears the screen. viewport.fill(COLOR["white"]) # Event interpreter which checks for program events and handles what to do when said events occur. # This function is starting to get a bit long, maybe I could have a seperate script for it... for event in pygame.event.get(): # Allows the player to quit the game. if event.type == pygame.QUIT: pygame.quit() sys.exit() # Detect for any kind of mouse press. if event.type == pygame.MOUSEBUTTONDOWN: # This would only run if the current game state is 'standby' if GET_GAMESTATE() == 'standby': Grid.obj.mouseButtonDown(event.pos, event.button) # Checks for when a key is pressed if event.type == pygame.KEYDOWN: # DEBUG: Manually scans the layout and prints which tiles are adjacent to Agent. if event.key == pygame.K_e: layout = Grid.obj.scanLayout() for line in layout: print(line) Agent.obj.debug_adjacent(layout) # Triggers when the Space key is pressed and if the gamestate is at a specific value. if event.key == pygame.K_SPACE and GET_GAMESTATE() == 'standby': # Tells the Agent to search for the Target. Not before checking if the Target exists at all. if Agent.obj.startSearch(Grid.obj, curTime) is not False: # Change the gamestate. CHANGE_GAMESTATE("searching") # Updates class instances Grid.obj.draw(viewport) if Target.obj is not None: Target.obj.draw(viewport) Agent.obj.update(viewport, Grid.obj, curTime, deltaTime) # Updates screen to reflect changes screen.blit(viewport, (0, 0)) pygame.display.flip() # This is the main script! Run this first! # Starting to realize the real importantance of this simple line of code. When I was new, I used to have problems with # circular imports to the point where I was reluctant to try multi file projects for a while. if __name__ == '__main__': Program()constants.py
# =======GAME STATES========== # 'standby' = Nothing is happening, you can place down walls and change the target position # 'searching' = The Agent searchs the layout until it finds the Target # 'pathing' = Generates a path starting from the target to the Agent # 'moving' = The pathfinding agent traverses down the path generated until it reaches the target. # The beginning state of the program. GAME_STATE = 'standby' # At first, I thought changing and checking the current game_state was as easy as just changing the value or using an # if statment, but do to how importing from other python files works, it's not that simple, you could probably figure # out why on Google. I did come up of a solution though, and it seems to work fine. # When called, it returns the current game state. Allows other files to get info on what the current game state is. def GET_GAMESTATE(): return GAME_STATE # Important function, when called, it will change the gamestate of the game, affecting lots of different things. def CHANGE_GAMESTATE(newState): global GAME_STATE GAME_STATE = newState print(f"Switching gamestate to '{GAME_STATE}'") # The size of the window WINDOW_WIDTH, WINDOW_HEIGHT = 600, 600 # Frames per second FPS = 60 TARGET_FPS = 60 # The size of each tile. TILE_SIZE = 40 # Calculates how many tiles can fit on the X and Y axis depending on the Window and Tile size GRID_COLS = 15 GRID_ROWS = 15 # Color Dictionary COLOR = { "black": (0, 0, 0), "white": (255, 255, 255), "grey": (128, 128, 128), "blue": (0, 0, 255), "red": (255, 0, 0), "yellow": (255, 255, 0), "orange": (255, 128, 0) }grid.py
from main import * from pathfinding import Agent, Target # The more I go on, I keep finding better ways of doing certain things. Before, I just create multiple instance of # tiles, instead, I just have to make a list of multiple rects and I think it works much better. # Well nevermind then... recently I've gone back to using class instances. The reason for this because I could properly # use if statments to check which tile it actually is. Also, I think this will improve code readability for me and # others later on. # The Base grid class. # Resposible for rendering the grid and generating the layout for the path finding agent. class Grid: obj = None # Runs on instance initilization. def __init__(self, offX, offY, spacing): # Declares list of to store all tile rects and wall instances. self.tilelist = [] # Stores all tile positions self.tileRects = [] # The offset position of the grid. self.offset = (offX, offY) # The amount of pixels between each tile. self.spacing = spacing # Prepare a list of tiles based of col and row index for row_index in range(GRID_ROWS): for col_index in range(GRID_COLS): x = col_index * TILE_SIZE y = row_index * TILE_SIZE # With said information, adds the rect to the list. self.tilelist.append(Tile(x, y, TILE_SIZE - spacing)) self.tileRects.append(pygame.Rect(x, y, TILE_SIZE, TILE_SIZE)) # The most primal form of the layout, will soon to used later self.rawList = [] # Holds the full layout with the correct listing. self.layout = list() # When called it will check for mouse inputs and save the position the mouse was at when pressed def mouseButtonDown(self, pos, key): # Swap tile if key == 1: # Left Mouse Button # For each tile of the instance, check if the mouse position is inside any given rect. for tile in self.tilelist: if tile.rect.collidepoint(pos): # Swaps the tile self.swapTile(tile) if key == 3: # Right Mouse Button # For each tile, check of the mouse position is inside any of them. for tile in self.tilelist: if tile.rect.collidepoint(pos): # Create/Change the position of Target at the position of tile. Target.obj = Target(tile.rect.x, tile.rect.y) # Swap tile function, this still works whether if it's a tile or a wall. # This function also ensures that the new tile will retain the list index the old tile used to have thanks to # insert() def swapTile(self, tile): print(f"Removed tile ID: {self.tilelist.index(tile)}") # Retrieves some information about the tile targetedIndex = self.tilelist.index(tile) oldRectX = tile.rect.x oldrectY = tile.rect.y # Deletes the rect self.tilelist.remove(tile) # A class check which determines what happens next. if tile.__class__ == Tile: # Creates a regular tile at the old rect's position and with its old index. self.tilelist.insert(targetedIndex, Wall(oldRectX, oldrectY, TILE_SIZE)) elif tile.__class__ == Wall: # Creates a wall tile at the old rect's position and with its old index. self.tilelist.insert(targetedIndex, Tile(oldRectX, oldrectY, TILE_SIZE - self.spacing)) # Will called, it will return a layout of the map in the form of a nested list. def scanLayout(self): # Clears the list to prevent unexpected layout duplication self.rawList.clear() self.layout.clear() # For every tile in the grid, it will check to see of it collides with the windowRect for tile in self.tilelist: # Appends a certain number to the raw list depending on the class of the tile. if tile.__class__ == Tile: self.rawList.append(0) if tile.__class__ == Wall: self.rawList.append(1) # Converts the long list into a clean, nested list. Thus saving the structual layout of the level for i in range(0, len(self.rawList), GRID_ROWS): self.layout.append(self.rawList[i:i + GRID_COLS]) # Gets the agent's center position agentCenter = Agent.obj.rect.center # Sets targetCenter to None targetCenter = None # Checks if a Target exists. if Target.obj is not None: targetCenter = Target.obj.rect.center # Each tile checks to see if the agent's center position is inside their rect. for tile in self.tilelist: # Checks if the tile detects Agent. if tile.rect.collidepoint(agentCenter): self.tileIntegration(tile, 2) # Checks if the tile detects a path tile elif tile.rect.collideobjects(Agent.obj.pathList): self.tileIntegration(tile, 3) # Check if the tile detects Target elif targetCenter is not None: if tile.rect.collidepoint(targetCenter): self.tileIntegration(tile, 9) # Returns the layout to the thing that called it. # Empty Tiles = 0, Walls = 1, Agent = 2, Path Tile = 3, Target = 9 return self.layout # Function for replacing values in self.layout # Funny How I realize a better way of doing this, days after I wrote it def tileIntegration(self, tile, newID): # Splits the tile's position into two seperate variables objX, objY = tile.rect.topleft # Divides each value by the tilesizes to get true tile positions objTileX = int(objX / TILE_SIZE) objTileY = int(objY / TILE_SIZE) # Sets a specific nested list value using the two position variable to new ID self.layout[objTileY][objTileX] = newID # Draws every tile on the screen def draw(self, viewport): # Draws each rect in the list for tile in self.tilelist: # Checks if the class of the tile and will act accordingly if tile.__class__ == Tile: pygame.draw.rect(viewport, COLOR["black"], tile) elif tile.__class__ == Wall: pygame.draw.rect(viewport, COLOR["grey"], tile) # Tile Sub-Class class Tile: def __init__(self, x, y, tilesize): self.rect = pygame.Rect(x, y, tilesize, tilesize) # Wall Sub-Class class Wall: def __init__(self, x, y, tilesize): self.rect = pygame.Rect(x, y, tilesize, tilesize)pathfinding.py
from main import * # Basic font font = pygame.font.Font(None, 28) # Out of Bounds Check # Checks if the specified adjacent tile is out of bounds (outside the screen). Returns None if so. def oobCheck(layout, x, y, offsetX, offsetY): # Checks if Y + offsetY would be greater than GRID_ROWS or lower than 0. if y + offsetY >= GRID_ROWS or y + offsetY < 0: return None # Checks if X + offsetX would be greater than GRID_COLS or lower than 0. if x + offsetX >= GRID_COLS or x + offsetX < 0: return None # If above statements are false. direction = layout[y + offsetY][x + offsetX] # Returns the direction, and the offset in a neat little list! :) return [direction, (offsetX, offsetY)] # Used for checking what tiles are adjcent to a tile. Then returning the results def getAdjacents(layout, objX, objY): adjacent = { # HINT: oobCheck(layout, X, Y, offsetX, offsetY) "right": oobCheck(layout, objX, objY, 1, 0), "down": oobCheck(layout, objX, objY, 0, 1), "left": oobCheck(layout, objX, objY, -1, 0), "up": oobCheck(layout, objX, objY, 0, -1) } return adjacent # Master parent class. All child classes will inherit and go through the code of init. I did this to lower the amount # of repeating code. Every developer hates that for some reason. class Common: def __init__(self, tileX, tileY, pathID): self.rect = pygame.Rect(tileX * TILE_SIZE, tileY * TILE_SIZE, TILE_SIZE, TILE_SIZE) # Saves the pathID for pathfinding. self.pathID = pathID # The text that will display the path ID of the child instance self.text = font.render(f"{self.pathID}", False, COLOR["white"], COLOR["black"]) # Saves the tile position the instance started on. self.tileX = tileX self.tileY = tileY # The Pathfinding agent who will pathfind their way to the next target. # Man, and I thought making the grid script was complicated. I guess it makes sense. class Agent(Common): obj = None # Runs on instance initilization. def __init__(self, tileX, tileY, prevTime): super().__init__(tileX, tileY, 0) # How much delay between each time the createPath function is called. self.searchDelay = 0.01 # Becomes important when searching for the target is impossible. self.stall = 0 # Time variable self.prevTime = prevTime # How fast the agent will move during the movement phase. self.speed = 5 # List to hold all spread tiles for searching for the exit. self.pathList = list() # List of positions, generated during the pathing phase that the agent moves through self.route = list() # Runs once every frame def update(self, viewport, grid, curTime, deltaTime): # Runs a function depending on the game state. if GET_GAMESTATE() == 'searching': self.targetSearch(curTime, grid) elif GET_GAMESTATE() == 'pathing': self.routeCreation(grid) elif GET_GAMESTATE() == 'moving': self.movementPhase(deltaTime) # Draws everything associated with the Agent self.draw(viewport) # Searches for the target def targetSearch(self, curTime, grid): # Only runs after a specified amount of time has passed if curTime - self.prevTime >= self.searchDelay: # Gets the old length of the list to compare later. oldPathCount = len(self.pathList) for path in self.pathList: # Checks if path has found the target. if path.targetFound(): # Deletes the path that collided with target self.pathList.remove(path) # Deletes any extra path tiles self.pathCleanup() # Generates and prints the layout. layout = grid.scanLayout() for line in layout: print(line) # Change the game state to the pathing phase. CHANGE_GAMESTATE("pathing") print(f"Path Count: {len(self.pathList)}") break # Runs if the path tile is active elif path.active is True: # Scan the layout layout = grid.scanLayout() # Get the adjacent tile information adjacent = getAdjacents(layout, path.tileX, path.tileY) # Create more path tiles based of said info self.createPathTile(path.tileX, path.tileY, adjacent, path.pathID) # Make the path tile unactive path.active = False # Resets the stall counter. self.stall = 0 # Ends the loop break # If the length of the new path list is the same as the old one, then increase stall by one. if len(self.pathList) == oldPathCount: self.stall += 1 # Ends the search prematurely if stall is over 5 if self.stall > 5: # Deletes all path tiles. self.pathList.clear() # Display error message print("[SEARCH FAILED] The target was impossible to get to!") # Change the gamestate back to standby. CHANGE_GAMESTATE("standby") # Resets the timer self.prevTime = curTime # Deletes any extra path tiles def pathCleanup(self): for path in self.pathList: if path.agentCollide(): self.pathList.remove(path) if path.selfCollide(): self.pathList.remove(path) # Sets up the route to the target # Probably the most complicated part of this program. # There's a lot of complicated things I write in this script def routeCreation(self, grid): # Gets selection rect selection = Target.selectionRect # Gets the tile position of selection tileX = int(selection.x / TILE_SIZE) tileY = int(selection.y / TILE_SIZE) # Gets the layout of the level. layout = grid.scanLayout() # Gets tiles adjacent to selection adjacent = getAdjacents(layout, tileX, tileY) # Declare list for get the index of adjacent path tiles adjPaths = list() # For each direction in adjacent for direction in adjacent: # Shortens the path for convenience dirInfo = adjacent[direction] # If the contents of dirInfo is not None if dirInfo is not None: # The tile found in that direction tile = dirInfo[0] # If tile is the agent tile if tile == 2: print("The route has been completed!") # Pauses the program for two seconds time.sleep(2) # Deletes all path tiles self.pathList.clear() # Reverse the order of every position in route. self.route.reverse() # Change the game state and end the function CHANGE_GAMESTATE("moving") return # If the tile is a path tile elif tile == 3: # The offset to get that direction. offsetX, offsetY = dirInfo[1] # Gets the adjacent tile's position. adjPos = (tileX + offsetX) * TILE_SIZE, (tileY + offsetY) * TILE_SIZE # Every path checks if the following conditions are true for path in self.pathList: # Checks if the adjPos is inside path if path.rect.collidepoint(adjPos): # Appends data about the path to adjPaths adjPaths.append( { "pathID": path.pathID, "index": self.pathList.index(path), "pos": path.rect.topleft } ) # This next part involves finding the adjacent tile with the lowest path id and setting up the other values # associated with it. For some reason I can't use min() with dictionaries so this is the solution I came up # with. It's probably terrible. # List of adjacent path IDs idList = list() # List of adjacent path indexs indexList = list() # List of avalible adjacent path positions posList = list() # Each dictionary in adjPaths for item in adjPaths: # Add each key is appended to their own seperate lists # Since each key is added at the same time, hopefully they will have the same indexes, so it will be easy to # get them when needed. idList.append(item["pathID"]) indexList.append(item["index"]) posList.append(item["pos"]) # Gets the index of the lowest path id. Hopefully, this will allow the program to get the other keys that are # associated with the id. lowPathIndex = idList.index(min(idList)) # Finally, using lowPathIndex, puts the right values right back into a dictionary that is the key to making # this work. Man, this took a bit to figure out :( tileData = { "pathID": idList[lowPathIndex], "index": indexList[lowPathIndex], "pos": posList[lowPathIndex] } print(f"Current Path Data: {tileData}") # Now that the program has the information needed. Here's the easy/fun part! # Adds the position to the route. self.route.append(tileData["pos"]) # Shortens the path to the next tile. nextTile = self.pathList[tileData["index"]] # Change the color of the next tile. nextTile.color = COLOR["orange"] # Move the selection to the next tile's position Target.selectionRect.topleft = tileData["pos"] # TODO: Make it so the agent moves along a route. def movementPhase(self, deltatime): # If the route list is empty. if len(self.route) == 0: print("The agent has made it to their destination!") # Updates the agent's tile position self.tileX = int(self.rect.x / TILE_SIZE) self.tileY = int(self.rect.y / TILE_SIZE) # Change the gamestate and ends the function. CHANGE_GAMESTATE("standby") return # Gets the first position in the route. nextPos = self.route[0] # Checks if the agent's position is equal to nextPos if self.rect.topleft == nextPos: # Remove nextPos from the route self.route.remove(nextPos) else: # Splits the agent's position and nextPos into seperate variables x, y = self.rect.topleft nx, ny = nextPos if x < nx: # If nextPos is to the right of Agent # Move Right self.movement(1, 0, deltatime) elif x > nx: # If nextPos is to the left of Agent # Move left self.movement(-1, 0, deltatime) elif y < ny: # If nextPos is below Agent # Move Down self.movement(0, 1, deltatime) elif y > ny: # If nextPos is above Agent # Move Up self.movement(0, -1, deltatime) # When called, moves the agent in a certain direction depending on the offset. def movement(self, offsetX, offsetY, dt): # The offset has to range from 1 to 0 to -1. With 0 not moving the agent at all self.rect.x += (self.speed * offsetX) self.rect.y += (self.speed * offsetY) # When called, begins the search for the target instance. def startSearch(self, grid, curTime): # Checks if a Target even exists in the first place, return False if not. if Target.obj is None: print("There is no target tile!") return False # Checks if Target is inside the agent. elif self.rect.colliderect(Target.obj.rect): print("The agent is already inside the target! Try moving it.") return False # Deletes all path tiles before proceeding self.pathList.clear() # First it asked the grid to generate a layout. layout = grid.scanLayout() # Then uses the layout to get what tiles are adjacent to him. adjacent = getAdjacents(layout, self.tileX, self.tileY) self.createPathTile(self.tileX, self.tileY, adjacent, self.pathID) self.prevTime = curTime # This functions creates path tiles on avalible adjacent tiles def createPathTile(self, tileX, tileY, adjacent, oldPathID): # For each direction in adjacent for direction in adjacent: # Shortens the path to the directions items for convenience. dirInfo = adjacent[direction] # Checks if the contents of dirInfo is not None if dirInfo is not None: # Gets the tile found from that direction. tile = dirInfo[0] # Gets the offset used to find the tile. offsetX, offsetY = dirInfo[1] # Checks if the tile is an empty tile or the target tile if tile == 0 or tile == 9: # Creates a path tower at a chosen position + the offset and Path ID self.pathList.append(Agent.Path(tileX + offsetX, tileY + offsetY, oldPathID + 1)) # Debug function which prints out tiles adjcent to Agent def debug_adjacent(self, layout): adjacent = getAdjacents(layout, self.tileX, self.tileY) for direction in adjacent: print(f"{direction}: {adjacent[direction]}") # Draws the instance and all path tiles def draw(self, viewport): # Draw the path tiles for path in self.pathList: pygame.draw.rect(viewport, path.color, path.rect) viewport.blit(path.text, path.rect) # Then draw the agent pygame.draw.rect(viewport, COLOR["blue"], self.rect) viewport.blit(self.text, self.rect) # Path child class, this will be helpful in searching the Target and making a path to it. class Path(Common): def __init__(self, tileX, tileY, pathID): super().__init__(tileX, tileY, pathID) # Basic tile data self.color = COLOR["yellow"] # Determine whether the Path should create more Path instances self.active = True # Appends itself to agent's spread list Agent.obj.pathList.append(self) # Returns true if path tile has collided with Target object def targetFound(self): if self.rect.colliderect(Target.obj): return True # Returns true if path tile is inside another path tile def selfCollide(self): if self.rect.collideobjects(Agent.obj.pathList): return True # Returns the if path tile is inside the agent def agentCollide(self): if self.rect.colliderect(Agent.obj): return True # Target child class, used as a finish line for the agent. class Target: obj = None # Stores a copy of Target's Rect for later selectionRect = None # Runs on instance initilization. def __init__(self, x, y): self.rect = pygame.Rect(x, y, TILE_SIZE, TILE_SIZE) # Clears and adds the Target's position to the Agent's route. # This will be important later. Agent.obj.route.clear() Agent.obj.route.append(self.rect.topleft) # Copy the instance's rect to a class variable Target.selectionRect = pygame.Rect.copy(self.rect) # Draws the instance def draw(self, viewport): pygame.draw.rect(viewport, COLOR["red"], self.rect)