video thumbnail 25:40
A* Pathfinding (E04: heap optimization)

2014-12-24

[public] 160K views, 3.11K likes, 25.0 dislikes audio only

channel thumbSebastian Lague

Welcome to part 4! In this episode we make our algorithm run much faster by creating a data structure called a heap.

Source code: https://github.com/SebLague/Pathfinding

If you'd like to support these videos, you can do so with a recurring pledge on Patreon, or a one-time donation through PayPal. https://www.patreon.com/SebastianLague

https://www.paypal.me/SebastianLague


remove the node from the heap with the lowest f cost
/youtube/video/3Dw5d7PlcTM?t=125.32
finding the parent of any node in this heap
/youtube/video/3Dw5d7PlcTM?t=221.44
getting the two children of any given node in the heap
/youtube/video/3Dw5d7PlcTM?t=243.25
adding new items
/youtube/video/3Dw5d7PlcTM?t=337.66
create an integer for the parent index
/youtube/video/3Dw5d7PlcTM?t=472.66
create a little variable t for the parent item
/youtube/video/3Dw5d7PlcTM?t=494.159
add items to the heap
/youtube/video/3Dw5d7PlcTM?t=653.49902
removing the first item from the heap
/youtube/video/3Dw5d7PlcTM?t=659.70898
take the item at the end of the heap
/youtube/video/3Dw5d7PlcTM?t=683.97998
set the heap index of that item to zero
/youtube/video/3Dw5d7PlcTM?t=698.97998
get the indices of the items
/youtube/video/3Dw5d7PlcTM?t=735.21997
set the swap index to that child
/youtube/video/3Dw5d7PlcTM?t=814.98999
compare the f costs of the two nodes
/youtube/video/3Dw5d7PlcTM?t=1134.5291
create a new stopwatch
/youtube/video/3Dw5d7PlcTM?t=1220.149
adjust our grid world size to 100 by a hundred
/youtube/video/3Dw5d7PlcTM?t=1308.73
display path gizmos
/youtube/video/3Dw5d7PlcTM?t=1340.86
turn on only display path gizmos
/youtube/video/3Dw5d7PlcTM?t=1412.65