Easy pathfinding in python [almost without math]
Vložit
- čas přidán 8. 07. 2024
- A tutorial on creating pathfinding in python & pygame. We will be using the pathfinding module to avoid doing complicated math and instead focus on implementing it in an actual project.
If you want to support me: / clearcode
(You also get lots of perks)
Social stuff:
Twitter - / clear_coder
Discord - / discord
Timestamps:
0:00:00 - Intro + pathfinding theory
0:01:51 - Simple pathfinding project
0:12:14 - Creating the Roomba project
Project files:
github.com/clear-code-project...
![Learning pygame by creating Snake [python tutorial]](http://i.ytimg.com/vi/QFvqStqPCRU/mqdefault.jpg)
library has changed.
So use
for point in self.path:
x = (point.x * 32) + 16
y = (point.y * 32) + 16
in those 2 places.
Thank you for providing this!
Wow, this works amazingly well for my NPC's in my text adventure. I had to translate the given path into their language (1 north, 2 west, 3, east, 4 south) but they work and find their paths respectfully. Thank you for this awesome tutorial, you just boosted my NPC's brains 10 times lol.
This was so useful thank you I was writing out my own pathfinders which all had terrible performance
1:01:15 was what I was looking for. In fb groups and discord and everyone told me to use vectors. I am glad I watched this video since I will be implementing pathfinding in my next game and it also solved my problem of floating point error. Thank you mate you have helped me immensely with your content.
Check out this video: czcams.com/video/rWtfClpWSb8/video.html I talk much more about delta time and floating point numbers in pygame :)
Love ur tutorials. It’s very detailed and it made me do something😆
After watching your tutorial, I understand that I am not a good instructor. Keep up the good work!!!
Man, you're doing great job for beginners. Everything is clearly explained like everytime :) I don't know how this channel is not 1kk+ subs
o kurde Polak
Excellent Video for Path planning and excellent game formation
Glad to see you back buddy
Sir you helped me a lot
Very useful
Great Job thank you!
wow... I built a pathfinder myself. Why did I not just wait for a clear code tutorial?
whose tutorial did you followed.
can you give me the link
That's good, it is a good excercise
Likewise, I wrote my own code based on tutorials from redblog games. Pathfinder was not a library in python 2.7
keep up the good work
Dude you're a legend
Hey Dude ! You have the best Pygame tutorials on YT !!
he is the best but also watch from da fluffy potato and coding with Russ
Amazing Video, ur video is useful
Hey, great tutorial! I noticed that the Roomba does never stop at the exakt middle of the tiles because the collision rects stop the movement before the Roomba is in the exact center. Any thoughts on how to fix this?
1:06:48 "Oh, it's actually working." I think this comment is because in the code provided in github, if you let the roomba get all the way to the final point, then click a new path, it starts moving in the last direction and does not follow the path. As long as you click while a path exists, the code works.
I am Benedek Vass and I love your content!
Very usefull tutorial! I implemented this into my game. I recomend also using this: print(self.grid.grid_str(path, start_grid, end_grid)) for debugging purpose. Shows nicely in console the whole pathfinding matrix and path. Could you also make some tutorial how to make large levels with multiple tiles (ie. 100x100 matrix)? Because the problem Im dealing with is not related to pathfinding. The problem i have with such large levels is that i get performance issues when i want to update every tile position in every frame. That goes to 600000 updates per second and i dont know how to work around this (framerate drops significantly). I tried adding all tiles to one surface and bliting only that surface on screen and it did help a lot but still im not satisfied with framerate. surface.scroll is not really good option in my case because it works on intigers and my movement needs to be float. Please help...
Great 👍🏻
100% the best python channel on yt, please do c++ soon
lol
he doesn't know that much c++ he is only good at python
is there any other way to read the map because i'm doing an indoor navigation system but i've got a really large map
Your tutorials are awesome! I've been able to use some of your stuff in other videos. I have a request... I have followed two other CZcamsr's tutorials on OOP and creating classes and I'm still struggling with the concept. I don't understand how to write one from scratch for my own projects. Your tutorials are so easy to absorb, would you be able to cover it and connect it with pygame?
Hey, did you check out my ultimate introduction to pygame video? I start that one with functions and later on convert it to OOP.
Thanks for sharing your knowledge, great content. With this, can you do a PacMan game?
May I ask, one question, as such type of games may connect with LIDAR as well, and can we connect hardware as well, like car, vehicles etc.???
if yes, can you send me the link of one of your videos, please?
thanks, i am waiting for your response.
Appreciated highly.
best regards
hello,dumb question, what do u use to draw on top of the code, i am a teacher too on java script and i have online classes and i would like to know thename of the app u use for drawing on the code
thanks
It's called epicpen epic-pen.com
what kind of optimization technique did you use?
I am making a flappy bird Game by following your tutorial but there is a problem when I am setting the GameOver bool to False It automatically setting to True how to fix this
Sir please make a video on seajam
Can you do a video of entire first stage of street of rage but with box ,weapon,text box , final boss
where i can find link to this project?
8:01 path now returns a gridnode: instead of (0,0). You can now print an ASCII representation of it with print(grid.grid_str(path=path, start=start, end=end)). And that's cool, but I want to see just the list like you have it here and I can't find a way to do that.
Solution is given here in the comments:
@diegomoncada8637
5 months ago (edited)
path, runs = finder.find_path(start, end, grid)
print(*map(lambda gridnode: (gridnode.x, gridnode.y), path))
Can you start a Ursina series? That is an awesome game engine. I would really want to cover Ursina Basics and create some basic games.
I have a few more big pygame projects and then I will focus on ursina for a bit, gonna at least do Zelda and Doom in pygame first though.
Please consider telling me how to make the pathfinder prefer some nodes over others. I know it has to do something with weighted graphs or something like that, but I am a 15 year old and I don't understand these concepts quite well. Just tell me in brief.
How can I get the matrix of the image?
How have you made your matrix ??
I really like this tutorial, the only thing is that sometimes if you change the direction midway, it has a chance of just flying off in a random direction...
This is because the collision rect is too small for that speed. I fixed it by simply increasing its dimensions. Just make sure that the collision rect is twice as big as the speed. So if self.speed = 3 it should be like: rect = pygame.Rect((x-3,y-3),(6,6))
@@delloff9866 Yep, but the only thing is that if you make the collision rect too big, there will be a noticeable gap, especially at high speeds. Using his method, there's basically no way to pump up the speed of the rectangle without making it look weird
That was a really, really, REALLY great tutorial! I nearly simultaneously converted it to my game i am working on. But i stuck on a problem afterwards. I Want to "spawn" more Roombas, so i need a function like spawnroomba(a,b,c,d,e). But i dont know how to solve this issue because this seems to be written for just one instance of "Roomba" and "pathfinding". Can you or somebody else help me with that? What does I have to change to make the (or better several) Roomba(s) "spawnable"?
Generate the random number within specific grid range first then check if that grid is 0 or not and if it is not (meaning it is not the wall) then convert it to real coordinate and spawn the roomba ;))
Do a lesson on NavMesh Pathfinding (Polygons) For 2D
where do you get the pip file
How to make map of image?
im having a problem where the vectors in get-direction are appearing as zeros, so that they cannot be normalised which stops the code from working
Yep, I got that too! It is because the first element of path list is also the current position of player so the result of that subtraction would be 0 (which throw error) and to fix that you need to add a default parameter with the value only set to True when it is the first time getting direction afterward you dont have to worry about that parameter anymore. Here is my code for reference (you can find it on line 29 when first time setting the path and line 80):
import pygame,sys,time
from pathfinding.core.grid import Grid
from pathfinding.core.diagonal_movement import DiagonalMovement
from pathfinding.finder.a_star import AStarFinder
from settings import *
class PathFinder:
def __init__(self,screen,matrix,player):
self.screen = screen
self.matrix = matrix
self.grid = Grid(matrix=matrix)
self.select_image = pygame.image.load("../graphic/selection.png").convert_alpha()
# Pathfinding
self.path = []
self.player = player
def create_path(self)->None:
# Start
start_x,start_y = self.player.get_coord()
start = self.grid.node(start_x,start_y)
# End
end_x,end_y = self.get_current_cell()[0],self.get_current_cell()[1]
end = self.grid.node(end_x,end_y)
# Path
finder = AStarFinder(diagonal_movement=DiagonalMovement.always)
self.path = finder.find_path(start,end,self.grid)[0]
self.grid.cleanup()
self.player.set_path(self.path,True)
def draw_path(self)->None:
if len(self.path) > 2:
points = []
for index,point in enumerate(self.path):
x = point.x * CELL_SIZE + CELL_SIZE / 2
y = point.y * CELL_SIZE + CELL_SIZE / 2
points.append((x,y))
pygame.draw.circle(self.screen,LINE_COLOR,(x,y),2)
pygame.draw.lines(self.screen,LINE_COLOR,False,points,5)
def draw_active_cell(self)->None:
col,row = self.get_current_cell()[0],self.get_current_cell()[1]
if self.matrix[row][col] == 1:
rect = pygame.Rect((CELL_SIZE * col,CELL_SIZE * row),(32,32))
self.screen.blit(self.select_image,rect)
def get_current_cell(self)->tuple:
mouse_pos = pygame.mouse.get_pos()
col = mouse_pos[0] // CELL_SIZE
row = mouse_pos[1] // CELL_SIZE
return (col,row)
def update(self)->None:
self.draw_active_cell()
self.draw_path()
class Player(pygame.sprite.Sprite):
def __init__(self,group):
super().__init__(group)
self.image = pygame.image.load("../graphic/roomba.png").convert_alpha()
self.rect = self.image.get_rect(topleft=(CELL_SIZE,CELL_SIZE))
# Movement
self.pos = self.rect.center
self.speed = 150
self.direction = pygame.math.Vector2(0,0)
# Path
self.collision_rects = []
def get_coord(self)->tuple:
return self.rect.centerx//CELL_SIZE,self.rect.centery//CELL_SIZE
def create_collision_rects(self,path)->None:
self.collision_rects = []
for point in path:
x = point.x * 32 + 16 - 2
y = point.y * 32 + 16 - 2
rect = pygame.Rect((x,y),(4,4))
self.collision_rects.append(rect)
def get_direction(self,remove_first_point = False)->None:
if remove_first_point: self.collision_rects.remove(self.collision_rects[0])
if len(self.collision_rects) >= 1:
start = pygame.math.Vector2(self.pos)
end = pygame.math.Vector2(self.collision_rects[0].center)
self.direction = (end - start).normalize()
elif len(self.collision_rects) == 0:
self.direction = pygame.math.Vector2(0,0)
def set_path(self,path,remove_first_point)->None:
if path:
self.create_collision_rects(path)
self.get_direction(remove_first_point)
def collision(self)->None:
if self.collision_rects:
for rect in self.collision_rects:
if rect.collidepoint(self.pos):
self.collision_rects.remove(self.collision_rects[0])
self.get_direction()
def update(self,dt)->None:
self.collision()
self.pos += self.direction * self.speed * dt
self.rect.center = self.pos
class Game:
def __init__(self):
pygame.init()
# Defaults
pygame.display.set_caption("Pathfinding")
pygame.mouse.set_visible(False)
self.screen = pygame.display.set_mode((WINDOW_WIDTH,WINDOW_HEIGHT))
self.clock = pygame.Clock()
# Setup
self.bg = pygame.image.load("../graphic/map.png").convert()
self.all_sprites = pygame.sprite.Group()
self.player = Player(self.all_sprites)
self.pathfinder = PathFinder(self.screen,MAP_MATRIX,self.player)
def run(self)->None:
prev_time = time.time()
while True:
dt = time.time() - prev_time
prev_time = time.time()
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
if event.type == pygame.KEYDOWN and event.key == pygame.K_q:
pygame.quit()
sys.exit()
if event.type == pygame.MOUSEBUTTONDOWN:
self.pathfinder.create_path()
# Draw
self.screen.fill("orange")
self.screen.blit(self.bg,(0,0))
self.all_sprites.draw(self.screen)
# Update
self.pathfinder.update()
self.all_sprites.update(dt)
pygame.display.update()
self.clock.tick(60)
if __name__ == "__main__":
game = Game()
game.run()
Traceback (most recent call last):
File "c:\Users\temos\Downloads\Python-Pathfinder-main
oomba project\pathfinding_roomba.py", line 167, in
pathfinder.create_path()
File "c:\Users\temos\Downloads\Python-Pathfinder-main
oomba project\pathfinding_roomba.py", line 47, in create_path
self.roomba.sprite.set_path(self.path)
File "c:\Users\temos\Downloads\Python-Pathfinder-main
oomba project\pathfinding_roomba.py", line 92, in set_path
self.create_collision_rects()
File "c:\Users\temos\Downloads\Python-Pathfinder-main
oomba project\pathfinding_roomba.py", line 99, in create_collision_rects
x = (point[0] * 32) + 16
~~~~~^^^
TypeError: 'GridNode' object is not subscriptable
How did you fix this error ?@@magickaito
@@magickaitobro please reply to me
What a legend. Unless I missed it, could this also be applied go 3d space?
To*
the algorithm only works in 2D but if you have a 3D game you could still use it quite well, just ignore the height axis. Should work for nearly all games.
@@ClearCode How can we implement this for multiple floors? For example if you have staircases or elevators that the roomba could use to get to another level?
Hi, I have one error by typing your same code as below:-
Class pathfinder:
def draw_active_cell(self):
mouse_pos = pygame.mouse.get_pos()
print(mouse_pos)
Error: TypeError: draw_active_cell() missing 1 required positional argument: 'self'
please, resolve my issue, t hanks
on version 1 0 4, it does not display coordinates quite correctly
Yeah, I am trying to workaround that. How did you resolve that issue?
@@enzofuentes939
path, runs = finder.find_path(start, end, grid)
print(*map(lambda gridnode: (gridnode.x, gridnode.y), path))
look, i made this solution, it seems to be returning a GridNode object so you have just to take x and y attributes
24:32 Are you sure creating an rectangle 60 times per second is a good practise? Wouldn't it be better to create rectangle once in the init method and then repositioning it with rect.topleft = (x, y). Simlar for finder here 32:11. Is that necesary to create new finder every time we want to createa a path? I dont know background behind those instructions that's why i'm asking
26:50 Wouldn't it be more intuitive to setup matrix the way that you could refer to it's cells with matrix[col][row] instead of matrix[row][col]? At first glance when creating matrix you create columns first and then cells inside them but if you think about it columns are reprezentation of x axis and rows are reprezentation of y axis and in whole mathematic you first write x and then y.
1:08:56 Wouldn't it be easier to inside roomba's get_direction method in else statement (self.collision_rects is empty) just pathfinder.path = [], or at least pathfinder.empty_path() instead of passing pathfinder's method as an argument into roomba? Are there any benefits of such approach?
Regarding the second question, the representation of the matrix is through a list of lists. So you have to pass the right list first (the row) and then within that list get the value (the col). I agree it would be more intuitive to have col, row but it's limited to what a list of lists can do.
For the first question, I tried your method and it worked well. I think that your way is a better programming practice, but it does introduce some complexity (you have to initialize the rect first) so that's probably why he didn't use it in the tutorial.
how did you make the map? in what software?
He made it with tile map with the pre-specified tileset
Where do I get image of room,and other stuff needed for game
check video description
@@ClearCode the link for the assets loops back to this youtube video
Does this pathfinding module work in three dimensions or just two?
why does this line "path=finder.find_path(start,end,grid)
print(path)"return to me, besides the coordinates, this is"([GridNode(x=0, y=0, walkable=True, weight=1, grid_id=None, connections=None), GridNode(x=0, y=1, walkable=True, weight=1..." also why I can't get the coordinates
path, runs = finder.find_path(start, end, grid)
print(*map(lambda gridnode: (gridnode.x, gridnode.y), path))
look, i made this solution, it seems to be returning a GridNode object so you have just to take x and y attributes
@@diegomoncada8637 thanks this made me rock hard
@@diegomoncada8637 Thanks for this!
I wonder how easy it would be if u use VSCode or any other code editor with intellisense or snippets to aid you in coding.
he use a normal code editor to let you keep up with his script
So, can it be used for making a rts game in Python?
I really wanna make one.
What IDE do you use
he don't use an ide he use a text editior ( sublime text)
i am not that good with pygame but i think the rect doesnt follow path it stays on 10,10
Why does my output get so cluttered with other information like” (Gridnode(x=0, y=0, walkable=True, weight = 1…”
i have the same problem, i think it's because we're using an newer version than him
path, runs = finder.find_path(start, end, grid)
print(*map(lambda gridnode: (gridnode.x, gridnode.y), path))
look, i made this solution, it seems to be returning a GridNode object so you have just to take x and y attributes
@@diegomoncada8637I figured it out… GridNode is a named tuple. You can access each attribute like object.x and object.y
How to create a 1:1 code map
This no longer works. It will not read the GridNode. The docs for this are not readily available do you have any knowledge of where to look for a solution? I was really looking forward to implementing this in my games.
this.
self.path = [*map(lambda gridnode: (gridnode.x, gridnode.y), self.path)]
Paste this under the self.path and before the self.grid.cleanup() this should fix the problem
x = point[0] * 32
TypeError: 'GridNode' object is not subscriptable
self.path = [*map(lambda gridnode: (gridnode.x, gridnode.y), self.path)]
Paste this under the self.path and before the self.grid.cleanup() this should fix the problem
@@maikelvangrootel3843 thank you,everything worked:)
@@maikelvangrootel3843 Thank you very much, your method helped me.
lol it 1:11:11 long all ones
France
Why don't you just build an AI that aware hit boxes that make a path. That would be easier and less complicated
The vid is 1 hr, 11 min, 11 secs... coincidence?
I think not!
The tutorial is great, but the code formatting is awful. The beginners that watch this video could mimic this style and make the world a worse place. Please, use pep8 code style guide.
Can you speak german?
Bezweifle ich, ich weiß es aber nicht
@@thepaulcraft957 haha moin😂 Wollte nur fragen wegen dem Akzent.Der ist ja auch nicht komplett englisch. Vielleicht ist es ja deutsch? 😅 keine Ahnung.
Aber du bist anscheinend deutsch 😂
machen wir so :)
@@bxstiii OK, der Akzent ist mir nie aufgefallen, aber kann ja sein :p
@@elindur1801 Was machen wir so?