Insight into programming algorithms

Home » Graph Theory » A-star(A*) in general » Implementing A-star(A*) for Pathfinding

Implementing A-star(A*) for Pathfinding


This is an extension to the A* in general where I had explained about the basics of A* and the skeletal algorithm which is common for all implementations.

Introduction

Here we’ll be learning about the implementation of the A* algorithm that we have learnt so far on pathfinding on a 2D grid. I’ll be explaining with 4 way movement i.e. the object can move 4 ways, up, down, left and right as it’s exactly same as the 8 way movement i.e. 4 way movement plus the diagonal movement.

Prerequisites 

The basic knowledge of A* algorithm is required which can be found in my earlier tutorial here as I’m not going to explain all the variables F score, G score, H score etc here.

Working

Let’s work on this in the order of the previous article. So first of all we need to decide what all information is needed to be kept in the node.

  • We need the x,y coordinates as column and row information within the nodes.
  • We need the individual f,g and h scores to be stored in the nodes.
  • We need a pointer that points to the parent.

This is the basic information required to be stored in the node, of course more stuff can be added as per the requirements of the pathfinding problem.

Structure of a Node

Structure Node
{

variable x , variable y, variable f, variable g, variable h;
pointer parent;

}

Making a graph

Now as we discussed earlier, we need to realize the search space as a graph.
Each tile is represented with it’s coordinates x/column and y/row these coordinates make them unique. Let’s take the following case:

Block S

Starting block

S is the starting block with the coordinates (4,6). Since we can move in four directions, we can move to (5,6),(4,7),(3,6) and (4,5) as we don’t have any obstacles blocking the path. This is how the initial cycle of the database looks after the neighbor function runs once.

Untitled-1-Recovered.jpg

Graph

Each node can have maximum of 4 children, the graph fill further expand in a similar fashion with each child pointing to the parent using pointer.

The g score here, which is the cost of travelling to that node will increase by 1 at each depth, which basically mean that we have to add 1 to the g score of the parent before storing it in the child nodes.

Let’s discuss on the various Heuristics that we can use:

  • Manhattan Distance/Taxicab geometry

This is most easy to implement heuristics and works best on 4 way movement grid i.e when combined with A* it works fastest for 4 way movement. So what is Manhattan heuristic? It is nothing but the Manhattan distance between two points, essentially it is the distance between two points measured along axes at right angles.It is also known as taxicab distance.

Manhattan

Mathematically we calculate Manhattan distance as:

Manhattan distance =|start.x-goal.x|+|start.y-goal.y|

where start and goal are the two points for which we have to calculate the Manhattan. Thus for the above figure the Manhattan distance will be 11.

  • Euclidean Heuristics 

This content will be updated soon…

  • Octile Heuristics

This content will be updated soon…

  • Chebyshev Heuristics

This content will be updated soon…

 

Let’s now try to understand how pathfinding will work according to the algorithm and using Manhattan heuristics, taking the following instance and watching the progression.

G-S

The grey blocks are the obstacles where the object cannot go. So with our first cycle we get the following 

1st step

F score = Top right
H score= Top left
G score= Bottom Left

Now in the next step we have to take the minimum F score according to the algorithm as we learnt

1st choice

 

Green block marks the node that can be used for the next iteration. Let’s take the tile on the right and move forward with our algorithm.Start is inserted to the closed list and this marked as red.

 

For the third step we have the following choices

2nd choice

This time let’s take the tile on top

3rd

 

Now we see that here the tile which is circle is generated again, when this happens the algorithm checks if the g-score of current tile/node is less than the previous, if it is then the orignal tile’s g-score and f-score is replaced with the new one, since here the g-score is equal the algorithm does nothing, it doesn’t insert this node to any of the lists.
The Red tile represents that it has been checked and represents being in the closed list while all others are open.

The algorithm progresses in a similar fashion taking the least F score node and expanding it while checking for any duplicates or already explored nodes. The following expansion shows the detailed step wise choices till it reaches the goal, the tiles marked with arrows are the prudent tiles that the algorithms detects to further expand in the next epoch.

1.jpg

2.jpg

 

3.jpg

4.jpg

5.jpg

6.jpg

7.jpg

8.jpg

9.jpg

10

11.jpg

12

13.jpg

14.jpg

Now as we see as the goal is found, it is the shortest path that is found between start and goal and thus we trace back to the initial node through the parent pointer making the entire path and choices visible obtaining the final state as shown.

15.jpg

 

Make sure you read my previous post about A* in general as it explains the basic algorithm and make sure to implement it in any language as it will help in understanding it much better.


 

If you see anything wrong with the post or if you have any queries regarding the algorithm. Post them in the comment section. There can be things wrong with this as I am still a beginner on the path of learning and this is based on what I have learnt so far with examples from external sources as well. So experts, please let me know through the comments section.


2 Comments

  1. Mukesh says:

    Great explanation.Thanks!

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: