Placeholder Image

Subtitles section Play video

  • Yo, I'm just so this is so cool.

  • To see other people like this is the program I wrote and easily It's so cool to see other people actually using it.

  • And it was just a simple visual ization.

  • Today I want to show you a program that I wrote two years ago.

  • Or two or three years ago.

  • I wanted to make, like, my first little game.

  • I even made a video about this thing.

  • It's like the stupid game, which has no point.

  • But I wanted to make the zombies follow the person, so I wanted to have path finding.

  • I remember I actually failed trying to implement this algorithm the first time.

  • Anyways, we'll explain how the algorithm works later.

  • I just want to show you what it is.

  • I haven't run this in a few years.

  • This grid, it's actually not really agreed.

  • I just drew squares on the screen in a four loop.

  • If you left click and drag, you can create walls.

  • Oh, this is so sexy.

  • If you right click, you can remove walls.

  • You hold down the S keys, you create a start.

  • Wait.

  • Is that right?

  • Yeah.

  • You create a start and you hold down the D and you created end.

  • And now if you hit the run, dude, I still love it to this day you can actually like zoo Mel and zoom in, but it's super broken because only zooms out, zooms into the left corner.

  • You can, uh, your egg around these guys.

  • You can change the speed down to slower speed, increase the speed here.

  • If you zoom in far enough, you start to see, like, the numbers on how the algorithm is actually calculating everything, which I find really interesting.

  • It's gonna take you here.

  • Yeah, Let's Let's make it right.

  • So there is no path, but you can see the algorithm is checking.

  • You can kind of see, like how the algorithm is thinking issues.

  • Somebody make issues two hours ago.

  • Somebody is using it two hours ago.

  • What steps seem to show the Pathfinder coming across the note?

  • And I know where you got an email.

  • I'm messaging you because of the A star path finding project.

  • It's awesome.

  • But I found a configuration that doesn't find the final path, and I don't know why.

  • You know, I got him to send me a screen shot and he goes, Please ignore the shape of the walls.

  • So we've got an interesting bug report here.

  • It Ah, it didn't find the final path.

  • Somehow you know what I think might have happened.

  • Stack Overflow error.

  • The only way to know for sure is to recreate the issue.

  • Okay, you two, please do not be monetized me.

  • This is just for education, not work for me.

  • Let's try to do this.

  • Oh, stack overflow.

  • Error.

  • Like if I do this, it's gonna It's gonna crash guaranteed.

  • See, it only got that far.

  • So how does this algorithm actually work?

  • This is our start node.

  • This is our end node have to calculate to numbers.

  • It's calculates something called a G cost.

  • We have to calculate in each costs.

  • And Aggie cost is just the distance from start node and R H costs is just the distance from and knowed if we're looking at this square, the G one picks over one square to the right.

  • And now, when we look at our each kind of a mess of graph here, but we're just going to say that h cost is 12345 So we were marked down five.

  • And then the F is just some.

  • So we have a six.

  • So we want to choose the node with the lowest after trough.

  • This note right here has the lowest Want.

  • It has six.

  • So we would choose this node.

  • Now you're wondering, Devon, you just explain how to choose this node?

  • Yes.

  • So we just repeat the exact same algorithm, I shows you we would re calculate all of these values for the surrounding nodes around this one, and then we would choose the lowest cost, and then we would just repeat that process until we would, uh there is one problem with this that you have solved, but that's the basics outfit.

  • So at the top left, we get our are folded f cost.

  • All of these nodes were on the open list.

  • We sorted it and we chose the lowest value, and the lowest value was for 20.

  • So if we hit start C, it's gonna make its way over top.

  • Just think about all those calculations that are happening inside of the computer, and you can solve that in zero millisecond.

  • So how did you code this, Devon?

  • So all I did was I made a four loop that goes from 0 to 3 and another four loop that goes from 0 to 3.

  • When you have the middle node, we go.

  • 123123123 Scan all surrounding nodes and we calculate the X in the UAE value of that note.

  • We just calculate the G cost and then we calculate the h cost you can see.

  • Then the F cost is just the G cost, plus the H cost set the new parent note.

  • So the parent is the lowest f coughed.

  • So what is lowest F cost function sorts.

  • Interesting.

  • I could have made this much more efficient, so it returns the lowest F cost node.

  • If the parent equals null, then we're at the end.

  • So there's no path.

  • If the parent, if the node that we just chose is the end, then we're done, right?

  • So and then there's a bunch of other logic in here, which I didn't Don't worry, I didn't explain this to you, but it basically checks all adjacent open nodes and checks.

  • If the G score of the parent, plus the open node, is less than the current G score of the open note.

  • If it's true, it's just a parent of the open, notas new barrette and re calculates G and F values.

  • But don't worry about that.

  • It says If then what we do is recall that entire function again, except we call it with our new parent.

  • So, yeah, you guys can Ah, you guys can play around with my algorithm.

  • You can You can break it.

  • I'm sure it's gonna break a 1,000,000 other ways.

  • You can send me pictures.

  • Follow me on the social Media's Twitter and Instagram stuff.

  • I got some bigger and better projects coming in the future.

  • I'm excited.

  • I'm excited for what's next, man.

Yo, I'm just so this is so cool.

Subtitles and vocabulary

Operation of videos Adjust the video here to display the subtitles

B1 node cost lowest algorithm parent calculate

Coding an A* Pathfinding Visualization

  • 0 0
    林宜悉 posted on 2020/04/04
Video vocabulary