Coding An A* Pathfinding Visualization

Yo I’m just so this is so cool to see other people like this is the program I wrote and he’s like it’s so cool to see other people actually using it and it was just a simple visualization 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 pathfinding 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.

It is I haven’t run this in a few years this grid it’s actually not really grid I just drew squares on the screen in a for loop if you left-click and drag you can create walls ah this is so sexy if you right-click you can remove walls you.

Hold down the s key you create a start wait no is that right yeah you create.

A start and you can hold down the e and you create an N and now if you hit the run dude I still love it to this day you can actually like zoom out and zoom in but it’s.

Super broken because the only zooms out and zooms into the left corner you can drag around these guys you can change the speed down to a slower speed you.

Actually let’s increase the speed here if you zoom in far enough you’ll 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.

Is checking you can kind of see like how the.

Algorithm is thinking issues did somebody make issues two hours ago somebody’s using it two hours ago what the steps see me to show the Pathfinder coming across the end.

Node and ignore you I got an email I’m messaging.

You because of the a-star pathfinding 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 screenshot and he goes please ignore the shape of the walls hmm so we’ve got an interesting bug report here it it didn’t find the final path somehow mmm you know what I think might have happened Stack Overflow error the.

Only way to know for sure is to recreate the the issue okay YouTube please do not do monetize me.

This is just for education now it worked for me let’s try to do this oh 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 we have to calculate two numbers we’ve to calculate something called a G cost and we have to calculate an H.

Just the distance from start node and our H cost is just the distance from end node if we’re looking at this square the G 1 pixel were 1 square.
To the right and now when we look at our H kind.

Of a messed up graph here but we’re just gonna say that.

H cost is 1 2 3 4 5 so we would mark down 5 and then the F is just the sum so we.

Have a 6 so we want to choose the node with the lowest F Fox this node right here has the lowest one it has 6 so we would choose this node now you’re wondering Devon you just explained how to choose this node yes so we just repeat the exact same algorithm I showed you.

We would recalculate all of these values for the surrounding.

Nodes around this one and then we would choose the lowest F cost and then we would just repeat that process until we would there is one problem with this that you do have to solve but that’s the basics of it.

So at the top left we get our our bolded f costs all of these nodes were on the open list we sorted it and we chose the lowest value and the lowest value was 420.

So if we hit start and see it’s gonna make its way over top just think about all those calculations that are happening inside of the computer and it can solve.

That in zero milliseconds so how did you code this Devon so all I did was I made a for loop that goes from zero to three and another for loop that goes from zero to three when you have the middle node we go one.

Two three one two three one two three scan all surrounding nodes and we calculate the x and the y value of that node we just calculate the the G cost and then we calculate the H cost so you can see then the F cost is just the G cost.

Plus the H cost set the new parent node 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 it 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 node if it’s true it’s just the parent of the open node as a new parent and recalculates G and F.

Values but don’t worry about that it’s it’s a then what we do is we call that entire function again except we call it with our new parent so yeah you guys can you guys can play around with my algorithm you can you can break it I’m sure it’s gonna break a million other ways you can send me pictures follow.

Me on the social medias Twitter and Instagram and stuff I got some bigger and better projects coming in the future I’m excited I’m excited for what’s next man.

Posted in Programming<a href="" rel="tag">A* Pathfinding algorithm</a> <a href="" rel="tag">C programming</a> <a href="" rel="tag">Coding</a> <a href="" rel="tag">Coding an A* Pathfinding Visualization</a> <a href="" rel="tag">Computer Science</a> <a href="" rel="tag">Devon Crawford</a> <a href="" rel="tag">dijkstra</a> <a href="" rel="tag">engineering</a> <a href="" rel="tag">Game loop</a> <a href="" rel="tag">Game programming</a> <a href="" rel="tag">Graphs</a> <a href="" rel="tag">Java programming</a> <a href="" rel="tag">Object oriented Java</a> <a href="" rel="tag">Stack overflow</a> <a href="" rel="tag">University student</a>