A* Pathfinding - How does it work.

What is pathfinding?

If you don't know, what pathfinding is, it is when you want to calculate the best road from one place to another. 

It is used in lol(Leauge of legends), when you want to move to another place and pressed at a point with your mouse, then lol uses pathfinding to move you to that point. 

So pathfinding is finding the best route, from one point to another point.

Example from our game! 

Here is an example from our game on how pathfinding can be used in a game.

How does pathfinding work?

Pathfinding works in many different ways and there are many differents algorith to use, but I'm going to describe how A* works since it is what we have used in our game.

Nodes

To find the path to a target position,the first thing you do is make a start node. All node need to have a position, a g cost, a cost, a f cost and a parent. More on the cost later. 

Nodes with cost added around the player.

When you have a startnode, you then check all the positon next to the node. Right, left, up, down, diagonal. If the position is not on a unwalkable, meaning a place you should be able to be at, then you can add it to the openlist.

Cost

G cost is the movement cost, how much it cost to move to the node. If you should move vertical or horizontal the g cost would be 10 and if it was diagonal it would be 14. The reason for this is because of mathmatics, but there is a reason.

H cost is the estimated cost from you to the target position. If there is 5 nodes horizontal and 4 nodes vertical, to the target position, then the esitimated cost (H) is 90. You just multiply the distance vertical and horizontal by 10 and then you have the H cost.
F cost is G + H. You just put'em together and you have the F cost.

Open and closed list

Open list is the where you have all the nodes, you can use to get to the target position. You use it to find the nodes you need to use to find the target position.

Closed list is the list, you use to calculate to get to the target postion.

The nodes marked in blueish, is the ones added to closedlist. The rest are added to openlist.

Parent

When you have found the node with the lowest F cost, you want to add to the closed list, then you make the current node the parent, to the node you added to closed list and make the node you added to the new current node.

Parent child in real life. Nodes works the same way, they know about each other and this is used to get the path.

The way to do it!

1. You take you startnode and make it your currentnode. 

2. You start to loop the following things through

• Check all the position next to the current node, if they are not on unwalkable ground, then make them a node, where you calculate and remember G,H, F cost and the parent. 
• You add all the nodes to the openlist.
• You look through the openlist and find the one with the smallest F cost and at it to the closed list, then also remove it from the openlist.
• You make the node, you just found the current node 

3. When you hit the target position, then you go back through the parent and you get your path.

4. BUT

• Stop when you the openlist is openlist is empty, then there is no path.  
• Stop when you have added the target position as a node to your closed list.

Congrats, if you follow these steps, you should be able to make pathfinding in your our game, just like we did.

Any problems or questions, just send me a mail at headlesshoboentertainment@gmail.com