Godot 3: AStar and Navigation2D pathfinding examples overview

[@nailbomb420]

Just a heads up, but the diagonal implementation allows pathing between two obstacles with touching corners.

[@Gdquest]

Good morning! It's 6:45 AM here. This video should've come out a few hours ago, but there was a little accident now the timezone is so different. The channel is back to weekly video releases. One per week, every Wednesday. Okay well, it's still Wedsnesday in some places around the world (and I could use some coffee) Question ► Do you like this type of intermediate-level content? Having an open source demo (with comments) and an overview video? These project examples are for the official Godot demos so eventually you'll find the AStar one on godotengine.org too. But it's not been reviewed yet so for no you have to download it here: bit.ly/godot-3-astar-demo If you want to jump ahead in the video: 1. 0:23 Navigation2D demo 2. 6:15 AStar demo

[@Gdquest]

My take on the question above -> Making this type of content means I can spend more time working on the demo so: 1. It can mean new demos/improving existing demos as part of the official Godot demos 2. I can produce better code templates that you can reuse in your projects 3. It's learning material for people who prefer text and/or reading code too Although it's not a step-by-step tutorial I hope it'll still help you understand how AStar works in Godot.

[@gakkiwoo5452]

@@Gdquest i got same question, why and waht your code got a update(),how can i change your start & end icon?please

[@valentinorossi5328]

Would love to see a Navigation2D *with* Tileset navigation video. What are the advantages of using AStar in your Tilemap demo over Navigation2D?

[@Gdquest]

Navigation2d requires a mesh, you have to make it by hand at the moment. It doesn't support a grid or graph-based movement: it always gives you the shortest geometric path to the target, cutting every corner and moving only in straight lines.

[@BartoszBielecki]

So you are basically grid-sampling a mesh in order to determine if the sampled point is inside the map. I can see two issues here (or I am missing something): * what about nearby positions that cannot be connected as there is a ridge/unwalkable wall between them? you would need kind of ray cast to make sure those can be used; * what about when wider paths need to be used, i.e. a straight line will not suffice?

[@SamFX]

How about avoiding animated obstacles on a non-tiled map, using for example the navigation map from the first example? How would you update the navigation map to take in consideration any dynamic obstacles?

[@Gdquest]

It's a tricky issue with several possible solutions but first that's why you often see AStar and other algorithms rely on grids, even if the map is not tile-based. You can slice your game world using a grid and have all the points where there's some collision shape as obstacles, excluded from the AStar node in this case. Then as you add/remove obstacles you scan all the cells your object is in using its bounding box as a guide and you add/remove the corresponding points in the AStar's database. Now a much simpler option is to still use Navigation2D with a fixed navmesh and have some extra simple code for local avoidance. Casting rays in a cone in the direction the AI is moving and using them to have it stray away from the path temporarily. Dynamic navmeshes are planned. Dunno if it'll be available in 2d but this may be the easiest option in the future.

[@SamFX]

Thanks for the reply, I will give a try to your suggestions.

[@nathanwfranke]

6:54 That's awkward

[@spooki-2451]

really? i don't see how

[@nathanwfranke]

@@spooki-2451 The character went straight through a corner of blocks.

[@Kontrachon]

Hey! nice tut. is there a way to make the Player move smoother? Like a person not on the grid edges?

[@auxencefromont1989]

i would recommend lerp()

[@valentinorossi5328]

Bit confusing calling it Navmesh as it's NavigationPolygonInstance, and there is a NavigationMeshInstance node type. Also we don't see you adding it. Just for those who might be confused.

[@horaciomagliacano5452]

This video is old buthopefully you'll see my question still.... I implemented this into my 2d isometric RTS game, however some of the Y axis tiles hold a negative value and I can't figure out how to get the script to calculate paths for any negative coordinates. I think the problem I am having is the way "map_size = Vector2.ONE * 120" is integrated for looping through each tile. I've tried hard coding the map bounds, and overriding other things but it just will not even begin pathfindind to any Vector2 that has a negative value for one of the axis. Please help, thanks!

[@puddingface1902]

Hello GDQuest. I would like to request a proper AStar2d tutorial with dynamic obstacle avoidance. It's something I am having a little trouble with. In your experience is it really hard to set up?

[@thomashalsted1888]

Odd thing that's happening with my AStar code is that the entity I want to move, a KinematicBody2D referred to as "Tank", goes flying off in a positive X and Y when I set the desired destination, unless I choose the destination as the same tile as an barrier/obstacle tile, or a traversable tile at negative global position.

[@jordanferrazza8700]

Hi, found a small bug in the repo. While implementing the ability to draw the maps plus a Sims-style "I CAN'T GO ANYWHERE" warning, I found that the start and end title is drawn one too many times, causing the tile to redraw illegally on error then just permanently sit there littering the map even after clearing.

[@NuroKnight]

This is going to be a long shot but I just checked out this video and thanks for doing it but I was wondering where the script is with the comments?

[@CrynusWo]

i looked at your astar2D project. But I have a question, if I want to add some more obstacles, how do I edit the code? Because in your tutorial example there is only 1 type of obstacle.

[@Produno]

Will you be updating this at any point in the future to include visual aids for debugging? ie, showing the grids that the Astar selects like in the examples shown in the redblobgames blog you posted, or are you done with this for now?

[@Gdquest]

Got a lot of work so no. But it's open source, other people are welcome to contribute.

[@fullanalysis93]

The A* demo is beautiful, thank you.

[@vanilmirth5342]

i must help! get_simple_path return nothing..what to do?? =(

[@melvomen4078]

How can i make it that it dont Look at a tilemap and Look for obstacles instead?

[@spooki-2451]

you can map the obstacles to the tilemap, otherwise, if you aren't using any sort of grid or map of a few fixed points, you may want to just use the navmesh instead.

[@JayComedyDirector]

Thank you for your tutorial ! I'm working on a tower defense where the tower themself make the maze. I have coded my path finding script (thx for your help) All good. But i'm hitting. a wall now on how to "place" those towers on the gridded map and make them re calculate the path. (I'm assuming a signal that would update when placed) My problem is that i have no clue on how to place a tower on the map in game. Do you have any advice ? tutorial ? link ? you could send over ? Thanks !

[@jointloic2260]

Waou ! Realy cool, this is usable too for a 3D project ? Thanks ! :)

[@Gdquest]

Sure! You build the graph manually so it works for any type of game

[@kennyjaeger8847]

For the first example I couldn't quite understand the purpose of "elif distance < 0.0" block. It seems like that part of the code will never be executed, and "set_process(false)" will never be called. I removed that elif block and the app still works as per normal. So ... what is it supposed to be doing?

[@Gdquest]

A mistake on my end, the condition before that block should be if distance 0.0:. It's hard to see as the character moves in small steps every frame but without that last block the character will always overshoot the path (maybe by 1 or less than 1 pixel)

[@kennyjaeger8847]

Ah, alright I'm beginning to understand it's purpose. Thank you. Anyways, changing to "distance > 0.0" seems to cause the character to stop moving prematurely. I was playing around and it seems that checking that for the last point seems to work well: "elif path.size()

[@hamster_games9379]

Awesome!!!

[@OBalduriano]

How do I find out which side the character is looking at? (To use the correct animation or rotation)?

[@lordofudead]

You have probably figured it out by now but if not, I imagine that code would look a little like this. Get character X, Y position (most movement scripts have this step). Check where new X and Y will be - if NewX is greater than OldX, character moved right - if NewX is less than OldX character moved left Ect... If character is moving left, rotate character left. Or something like that, I’m on mobile so I do apologise for the funky formatting.

[@user-mg2wj3cb8q]

where can i download your example?

[@Produno]

Hello Nathan. What would be the best way to store the direction of the node if we wanted to change this via animation rather than using rotation? Thanks! Also while I'm here, I want to store more than one object as an obstruction, would I be best using groups for this?

[@Gdquest]

For the direction you have the coordinates of the last and next point the character is moving to, you can calculate a direction vector with that: var direction = (move_target - last_move_target).normalized() And yes you can use a group for obstacles.

[@Produno]

Awesome, thanks.

[@antanaspaskauskas9432]

I have a question, why do you use _input(event)? I thought that an easier method of if Input.is_action_pressed(".....") in the _process(delta) function is used nowadays :) Is there an advantage of the former method?

[@Gdquest]

No you need both, they don't have the same effect. You query the Input class in _process for movement etc. because you need to update the character's direction on every frame, but for trigger actions (like clicking in the video) _input(event) is your friend: it gets called when the user presses a key so you can process it ASAP and change the character's state. You can kind of do that in _process but you'll need more code to do the same thing. Input and _input() were both in Godot 2, little changed in this regard

[@antanaspaskauskas9432]

Thanks, learning something new!

[@somarandtheastronautape6518]

At 08:01 there is a map_size variable with value Vector2(16, 16) does it means that the maps has 17x17 tiles or Vector2(0, 0) doesn't count?

[@KurttBlissZ]

Its how many tiles you can have... anything out size the map size you can't walk in...

[@KurttBlissZ]

I didn't like how you had to manually change the size so I added a sprite to scale that defines the map size drive.google.com/file/d/1Z-MKewwy8V_g6GvgUxhsV-8vSfJuIyp6/view?usp=sharing

[@leejohnh22]

Hi thanks for the video, very helpful so far! I am currently trying to integrate this with one of your earlier projects with Isometric Grid but trying to replace the arrow key movement with mouse click. I'm currently having trouble where when I click a place on the grid, the cell that is selected is not accurate. Any pointers on how to accurately have the correct cell selected?

[@leejohnh22]

On this video kzbin.info/www/bejne/gae2m31joMl6n9E , Gilles Roudiere commented saying "The isometric_to_cartesian function is useful when creating a mouse-based gameplay, which is usually the case with isometric games (moving with not axis-aligned directions is difficult with a gamepad). In this case you would have to convert the mouse screen position to the isometric world." So in the player.gd script, on the func _input(event), I passed the global_position and target_position through the isometric_to_cartesian functions but it ends up being more innacurate

[@Gdquest]

How about using an isometric tilemap and its map to world methods?

[@Gdquest]

If you have precision issues or your game has specific needs you can always write the conversion functions yourself.

[@leejohnh22]

I will give that a try, thanks for input!

[@antanaspaskauskas9432]

Navigation2D has a lot of problems. Just another issue I have noticed recently... What happens if there are two routes - Route A and Route B - to get from Point A to Point B, where they have same distance? The object gets stuck as it can not decide which way to go.

[@Gdquest]

Sounds strange, it should be extremely rare and barely possible to have the exact same distance in practice. Did you report the bug, maybe with an example? I'm sure it'd get fixed

[@antanaspaskauskas9432]

Hmm, not sure if it is bug or not, but I have uploaded the video on Facebook :) facebook.com/alastor192/videos/1390632927708174/ I actually can reproduce it each time I reach a NavigationPolygon angle - the character gets stuck

[@Gdquest]

Looked at it, it looks like your movement code causes the bug.

[@antanaspaskauskas9432]

What I don't understand is where exactly :(

[@antanaspaskauskas9432]

Thanks, I solved the problem

[@antanaspaskauskas9432]

Sorry for asking again, but do you know if you can change NavigationPolygon through code? I know there is navpoly_set_transform, but there is no documentation for some reason...

[@Gdquest]

I don't think you can do it conveniently. There's realtime navmeshes on the godot roadmap too I think

[@antanaspaskauskas9432]

That would be very cool!

[@winegumification]

Hey, great tutorial! The astar_node.get_point_path(start_point_index, end_point_index) is causing several errors to show up in the debugger, which causes a bit of stutter (error: Condition ' p_elem->_root ' is true). Any idea what might be causing this?

[@Gdquest]

I asked around and couldn't get an answer. I don't know where it comes from unfortunately. Here it doesn't cause slowdowns though.

[@winegumification]

I figured it out! Because you're adding all the neighbour points when connecting, you don't need to flag bi-directional as true. This is adding redundant connections which throws the error. You could just connect the right and bottom neighbours and flag as true, or just set bidirectional as false. This fixes it. (also thanks to /u/MortimerMcMire on reddit)

[@Gdquest]

Thanks much :) forgot about that

[@ZoidbergForPresident]

Wait, move_along_path is called each frame when the mouse is clicked?

[@Gdquest]

You calculate the path once and then the character moves every frame until it reaches its destination, yes

[@ZoidbergForPresident]

Oooh, ok. But what if the path changes in between, like dynamic moving levels or if a movable unit gets in the way?

[@Gdquest]

Then you'll have to recalculate at that very moment. If it's only from time to time it's okay. If you're making an RTS game with hundreds of units you'll need to look into special algorithms, but you could also calculate the path on a moderately-sized map 100 times per frame with AStar without seeing frame drops (NB: it's not the best idea though ;) )

[@ZoidbergForPresident]

OK, thanks. :)

[@daddydeadcity772]

This is good. Godot's current navigation2d node is terrible.

[@nohhem]

,it would be great if you have like this tutorial or code for python ,many thanks in advance for this great work

[@Gdquest]

I won't cover Python in Godot as too few people would use it. It's great to have it for tool development etc. But I think the people who would need it instead of gdscript shouldn't need tutorials.

[@snarkmultimedia]

this explanation is confusing to me, I sugest you try first to explain how to click and make the caracter move from one cell to another and them explain how the caracter avoid obstacles, start simpler and end with the more complex stuff