Easy pathfinding in python [almost without math]

[@yucelonal9386]

library has changed. So use for point in self.path: x = (point.x * 32) + 16 y = (point.y * 32) + 16 in those 2 places.

[@housecaldwell]

Thank you for providing this!

[@adventuresoftext]

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.

[@ammarshahzad9627]

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.

[@ClearCode]

Check out this video: kzbin.info/www/bejne/qIjXl3aipbyGmJo I talk much more about delta time and floating point numbers in pygame :)

[@patrinho915]

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

[@0rd3r]

o kurde Polak

[@dumbhusk94]

This was so useful thank you I was writing out my own pathfinders which all had terrible performance

[@HaKaNOGUZ]

After watching your tutorial, I understand that I am not a good instructor. Keep up the good work!!!

[@housecaldwell]

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.

[@gulrukh1386]

Excellent Video for Path planning and excellent game formation

[@sylvanfranklin6904]

wow... I built a pathfinder myself. Why did I not just wait for a clear code tutorial?

[@HappyHuz]

whose tutorial did you followed. can you give me the link

[@CrusherKingZ]

That's good, it is a good excercise

[@cybern9ne]

Likewise, I wrote my own code based on tutorials from redblog games. Pathfinder was not a library in python 2.7

[@joezheng1364]

Love ur tutorials. It’s very detailed and it made me do something😆

[@R3qUi3M123]

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

[@thangphu6044]

Very useful

[@xtremegamemaker]

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.

[@lucasblomgren1975]

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?

[@coachpribble3552]

Glad to see you back buddy

[@housecaldwell]

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.

[@housecaldwell]

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

[@HoRRoRlets]

Dude you're a legend

[@benedekvass2812]

I am Benedek Vass and I love your content!

[@patrickslomian7423]

Hey Dude ! You have the best Pygame tutorials on YT !!

[@sanjaygokul7903]

he is the best but also watch from da fluffy potato and coding with Russ

[@gulrukh1386]

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

[@passion002]

Sir you helped me a lot

[@sarahbahgat8052]

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

[@ethankhamis8730]

100% the best python channel on yt, please do c++ soon

[@ruudcools2866]

lol

[@user-ij4ov7re8g]

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

[@diegomoncada8637]

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

[@Raulxz]

@@diegomoncada8637 thanks this made me rock hard

[@housecaldwell]

@@diegomoncada8637 Thanks for this!

[@3030shizon]

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.

[@testdrive123]

this.

[@maikelvangrootel3843]

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

[@gulrukh1386]

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

[@f4be1]

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

[@magickaito]

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()

[@AljunClark]

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

[@AljunClark]

​@@magickaitobro please reply to me

[@keithschaub7863]

keep up the good work

[@jimmyslaughter6262]

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 KZbinr'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?

[@ClearCode]

Hey, did you check out my ultimate introduction to pygame video? I start that one with functions and later on convert it to OOP.

[@fabuuuan]

Great Job thank you!

[@tcgvsocg1458]

Can you do a video of entire first stage of street of rage but with box ,weapon,text box , final boss

[@user-ij4ov7re8g]

on version 1 0 4, it does not display coordinates quite correctly

[@enzofuentes939]

Yeah, I am trying to workaround that. How did you resolve that issue?

[@diegomoncada8637]

@@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

[@Akosiyawin]

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.

[@passion002]

Sir please make a video on seajam

[@dominiknowec9837]

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?

[@housecaldwell]

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.

[@housecaldwell]

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.

[@thesanketdas]

how do i make a matrix for a custom image

[@qwerty3805]

Amazing Video, ur video is useful

[@andersonnguyen2571]

Why does my output get so cluttered with other information like” (Gridnode(x=0, y=0, walkable=True, weight = 1…”

[@diegomoncada8637]

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

[@andersonnguyen2571]

@@diegomoncada8637I figured it out… GridNode is a named tuple. You can access each attribute like object.x and object.y

[@katzenkontor_de]

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"?

[@magickaito]

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 ;))

[@justanintrovert7833]

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

[@YouTubech11]

What are you doing now ❤❤❤

[@swastiksarkar]

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.

[@ClearCode]

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.

[@artorias7750]

what kind of optimization technique did you use?

[@shaderavng7597]

Do a lesson on NavMesh Pathfinding (Polygons) For 2D

[@paumoramolar8952]

How can I get the matrix of the image?

[@buredabby]

What a legend. Unless I missed it, could this also be applied go 3d space?

[@buredabby]

To*

[@ClearCode]

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.

[@markserafin2130]

@@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?

[@XxtheonexX10111]

i am not that good with pygame but i think the rect doesnt follow path it stays on 10,10

[@jpz-og3ki]

How to create a 1:1 code map

[@oscarisorez7829]

How have you made your matrix ??

[@danielzhu7516]

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

[@delloff9866]

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

[@danielzhu7516]

@@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

[@TasteDaRDX]

Thanks for sharing your knowledge, great content. With this, can you do a PacMan game?

[@wubwub3859]

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

[@ClearCode]

It's called epicpen epic-pen.com

[@cameronhanna367]

where do you get the pip file

[@rysyazamirbekuulu8249]

where i can find link to this project?

[@kahwigulum]

Does this pathfinding module work in three dimensions or just two?

[@fizagulzar8813]

How to make map of image?

[@rohitranaware2116]

Where do I get image of room,and other stuff needed for game

[@ClearCode]

check video description

[@msbranin]

@@ClearCode the link for the assets loops back to this youtube video

[@suzanne4300]

Great 👍🏻

[@SkyFly19853]

So, can it be used for making a rts game in Python? I really wanna make one.

[@pikabomb8549]

how did you make the map? in what software?

[@magickaito]

He made it with tile map with the pre-specified tileset

[@ancientscarab4361]

What IDE do you use

[@bishnupahari3353]

he don't use an ide he use a text editior ( sublime text)

[@sufianahmat5334]

Why don't you just build an AI that aware hit boxes that make a path. That would be easier and less complicated

[@jeanrodrigues6249]

France

[@ThatRandomError]

lol it 1:11:11 long all ones

[@dapladoc]

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.

[@saisavit2926]

The vid is 1 hr, 11 min, 11 secs... coincidence?

[@Milk-yi9hg]

I think not!

[@bxstiii]

Can you speak german?

[@thepaulcraft957]

Bezweifle ich, ich weiß es aber nicht

[@bxstiii]

@@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 😂

[@elindur1801]

machen wir so :)

[@thepaulcraft957]

@@bxstiii OK, der Akzent ist mir nie aufgefallen, aber kann ja sein :p

[@bxstiii]

@@elindur1801 Was machen wir so?

[@BackstreetBorz]

My working version (0 is walkable, 1 is wall): matrix = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 1, 0, 1, 0, 1, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 1, 0, 1, 0, 1, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 1, 0, 1, 0, 1, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ] grid = Grid(matrix=matrix, inverse=True) start = grid.node(1, 1) end = grid.node(8, 8) finder = AStarFinder() path = finder.find_path(start, end, grid)[0] coords = [(node.x, node.y) for node in path] print(coords)