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.pyfrom 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.pyfrom 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)