A* (A star) is one of the most popular algorithms for the path finding in the computer science. It looks for the optimal way with mixing DFS(Depth First Search)and BFS(Breadth First Search) while as it uses the Heuristic method.
Here I introduce this algorithm with one RPG prototype which I implemented many years back (actually, back in my university school-days).
Let's take a look at the two screenshots.
The actual game screen is on the left side whereas right one additionally visualizes the structure of the game map. As you can see them, this game was implemented with 2d style map data which is constructed with 2 dimensional grids. All grid has proper information including position, size, graphical data and one Boolean whether are any obstacles there or not. Actually, the grids in the screenshot are displayed larger than actual size in the game for your easier understanding. If the grid is filled with red color, then it's obstacle space where the player character can't go to. So, we can understand as it's blocked space. You may think some grids looks having obstacles even though they don't fill with the red color. Considering perspective, those obstacles are over the player character so it's available space. Let's suppose the player character moves to one arbitrary position(grid) then let's see how A* algorithm works for the path finding.
Before starting, we can implement a grid with a Node. A node is a data structure normally used in Linked List.
Suppose the yellow node is the destination. It looks for the available nodes from the player character's (It tries the BFS). After investigated the available 8 directions nodes, It selects one which is the closest to the destination. In this case, green arrow node.
In the meantime, it handles the internal data structure. Mainly, it constructs two linked lists (exactly, Stack) which are Open Node and Close Node. The Open Node is a candidate list which needs to investigate the list nodes further. That is, we must visit 8 directions nodes (near 8 grids) from one node. If we don't perform this yet, then this node goes appending in the Open Node. The Close Node, on the other hand, is a list that consisted of the nodes which we don't need to investigate further. And notice this, every time we append one node in the Open Node, it can sort the nodes by distance between a node and the destination.
So far, the Open Node has a green arrow node plus the yellow arrow nodes and the Close Node has only the starting point node.
Let's move on to the next. This time, It visits 8 directions nodes from the green arrow node. (It tries the DFS. A* goes through the best nodes first)
Now, the Open Node has new yellow and green arrow nodes additionally and the Close Node has the starting point node and the light green arrow node.
Annotation
Yellow arrow: New nodes appended in the Open Node.
Light yellow arrow: The nodes appended in the Open Node previously.
Green arrow: A new node appended in the Close Node.
Light green arrow: the node appended in the Close node in the previous step.
Soon it reaches to a cul-de-sac, it tries to navigate with a candidate node from the Open Node. In this case, the available way is only the lower node.
Since the next candidate node in the Open Node would be the closest to the destination, it would be just right of the starting point. But we can find out soon that the around 8 nodes of it were already visited before, so it will be moved to the Close Node immediately. Now, the next candidate node would be just above the starting point. However, it should be moved to the Close Node also by the same reason. So the next candidate would be the upper side node in the below picture.
But in this case if we figure out the next candidates around it, they all are more apart from the destination compared to a candidate node in the Open Node. So the next candidate will be the right bottom node from the starting point.
If we keep going through this sequence, we can finally reach to the destination.
Lastly, we can get a path if we track back the white arrows. Those white arrow nodes would be in the Close Node, so just iterate nodes from the last to the first reversely.
If you can understand the A* theory then let's take a look at the code now.
Obviously, we can get the evaluated value (a sum of degree and distance) but you can modify the units of the degree and distance properly for your case. For your reference, If the minimum value of the degree is 1, then 1 is good to the distance between adjacent 2 nodes.
Now, let's declare global Open Node, Close Node and one stack.
Let's see the pseudo code of next functions because it's not much importance. But pretty enough just with commentary.
Please refer the attached file if you wanna see the actual source code of above functions.
Now, it's a little more serious. Next is the path finding function.
Continue to make_child() function.
I hope you understood so far. But actually in this game, it would be more realistic that if we allow diagonal moving only if two adjacent grids are available so. The change won't be difficult at all. I believe you can make it yourself.
Next function is extend_child_node(). This function is designed to extend a node and sort it if necessary.
It's getting more complex and complex!! If you cannot understand the source code, please draw a temporary path and follow step with this logic. It's going over!
Here, it handles an exceptional case which hasn't been mentioned in the above example. It just re-evaluate the nodes when the Close Node needs update.
Lastly, append a node to the Open Node. Point is, it keeps the order in distance when it push a node.
Somewhat difficult to describe the complex logic by me. But you could hopefully understand what I am talking here. Otherwise, please read the source code considerably.
Anyhow, A* is done here. This logic is for a standard case so definitely you could optimize it further. For instance, we can skip the list of nodes if they just construct a straight way. Or probably we can add a way point in the map in such cases doors and gates. Definitely it would be much better for the path finding. In case of 3D map, I believe it's not much different even though. But you need to google for more information.
astar.cpp
Here I introduce this algorithm with one RPG prototype which I implemented many years back (actually, back in my university school-days).
Let's take a look at the two screenshots.
The actual game screen is on the left side whereas right one additionally visualizes the structure of the game map. As you can see them, this game was implemented with 2d style map data which is constructed with 2 dimensional grids. All grid has proper information including position, size, graphical data and one Boolean whether are any obstacles there or not. Actually, the grids in the screenshot are displayed larger than actual size in the game for your easier understanding. If the grid is filled with red color, then it's obstacle space where the player character can't go to. So, we can understand as it's blocked space. You may think some grids looks having obstacles even though they don't fill with the red color. Considering perspective, those obstacles are over the player character so it's available space. Let's suppose the player character moves to one arbitrary position(grid) then let's see how A* algorithm works for the path finding.
Before starting, we can implement a grid with a Node. A node is a data structure normally used in Linked List.
Suppose the yellow node is the destination. It looks for the available nodes from the player character's (It tries the BFS). After investigated the available 8 directions nodes, It selects one which is the closest to the destination. In this case, green arrow node.
In the meantime, it handles the internal data structure. Mainly, it constructs two linked lists (exactly, Stack) which are Open Node and Close Node. The Open Node is a candidate list which needs to investigate the list nodes further. That is, we must visit 8 directions nodes (near 8 grids) from one node. If we don't perform this yet, then this node goes appending in the Open Node. The Close Node, on the other hand, is a list that consisted of the nodes which we don't need to investigate further. And notice this, every time we append one node in the Open Node, it can sort the nodes by distance between a node and the destination.
So far, the Open Node has a green arrow node plus the yellow arrow nodes and the Close Node has only the starting point node.
Let's move on to the next. This time, It visits 8 directions nodes from the green arrow node. (It tries the DFS. A* goes through the best nodes first)
Now, the Open Node has new yellow and green arrow nodes additionally and the Close Node has the starting point node and the light green arrow node.
Annotation
Yellow arrow: New nodes appended in the Open Node.
Light yellow arrow: The nodes appended in the Open Node previously.
Green arrow: A new node appended in the Close Node.
Light green arrow: the node appended in the Close node in the previous step.
Soon it reaches to a cul-de-sac, it tries to navigate with a candidate node from the Open Node. In this case, the available way is only the lower node.
Again, it tries to navigate a candidate node from the Open Node because all directions are unavailable. They are blocked or already visited. So the result will be the above picture.
Since the next candidate node in the Open Node would be the closest to the destination, it would be just right of the starting point. But we can find out soon that the around 8 nodes of it were already visited before, so it will be moved to the Close Node immediately. Now, the next candidate node would be just above the starting point. However, it should be moved to the Close Node also by the same reason. So the next candidate would be the upper side node in the below picture.
But in this case if we figure out the next candidates around it, they all are more apart from the destination compared to a candidate node in the Open Node. So the next candidate will be the right bottom node from the starting point.
If we keep going through this sequence, we can finally reach to the destination.
Lastly, we can get a path if we track back the white arrows. Those white arrow nodes would be in the Close Node, so just iterate nodes from the last to the first reversely.
If you can understand the A* theory then let's take a look at the code now.
//A node structure
typedef struct node_s {
int degree; //Depth info. Same with the depth in the tree data structure
int distance; //Distance between this node and the destination
int value_factor; //Evaluated value (degree + distance)
int x, y; //Grid position
struct node_s* direct[8]; //Neighbor nodes around this
struct node_s* prev_node; //Previous node in the linked list
struct node_s* next_node; //Next node in the linked list.
} node_t;
//A stack for node sorting
typedef struct node_stack_s {
node_t* node; //A node in this stack position
struct node_stack_s* next_node; //Next node stack
} node_stack_t;
Obviously, we can get the evaluated value (a sum of degree and distance) but you can modify the units of the degree and distance properly for your case. For your reference, If the minimum value of the degree is 1, then 1 is good to the distance between adjacent 2 nodes.
Now, let's declare global Open Node, Close Node and one stack.
node_t *OPEN = NULL, *CLOSED = NULL;
node_stack_t* STACK = NULL;
Let's see the pseudo code of next functions because it's not much importance. But pretty enough just with commentary.
//Initialize list and stack (also clean up resources)
void init_astar()
{
//Remove all nodes while iterating Open Node
//Remove all nodes while iterating Close Node
//Remove all stack resources while iterating the stack.
}
//Check whether the node in the given position is blocked or not.
bool is_available_grid(int x, int y)
{
//Implement whether the player character can move to this node or not.
//...
//If it's available, return TRUE.
//otherwise (in case of blocked?), return FALSE.
}
//Check whether the node in the given position is existed in Open Node.
node_t* is_open(int x, int y)
{
//Iterate Open Node to find the node in the position.
//If it does, return the node.
}
//Check whether the node in the given position is existed in CLOSE NODE.
node_t* is_closed(int x, int y)
{
//Iterate CLOSE NODE to find the node in the position.
//If it does, return the node.
}
//Insert a given node in the stack.
void push_into_stack(node_t* node)
{
//Allocate one stack node.
//Set the input node to the stack node.
//Push the stack node into the stack.
}
//Remove a node from the stack.
node_t* pop_from_stack()
{
//Get the last stack node from the stack.
//Remove stack node.
//Return the node of the stack node
}
Please refer the attached file if you wanna see the actual source code of above functions.
Now, it's a little more serious. Next is the path finding function.
//Starting point: start_x, start_y, and destination: dest_x, dest_y
node_t* find_path( int start_x, int start_y, int dest_x, int dest_y ) {
node_t* present=NULL; //Starting point node
//Add the starting point node. Reversely, starting point is the destination here.
//That means, navigate from the destination to the starting point.
//Destination to Starting point as I mentioned above. We can rewind the completed list to figure out the path.
present = (node_t*) calloc(1, sizeof(node_t));
present->degree = 0;
present->distance= pow((dest_x- start_x), 2) + pow((dest_y - start_y), 2); //Originally, it requires a square root but not necessary.
present->value_factor = present->distance; // distance + degree
present->x= dest_x;
present->y= dest_y;
OPEN=present;
node_t* best=NULL; //best keeps the best path list.
int count=0; //Count a iteration to prevent the infinite loop.
//Begin the investigation. But limit the loop count, just in case.
while(count< FINDPATH_LIMIT) {
//No more candidates. Probably, we found the path?
if (OPEN == NULL) {
return best;
}
best = OPEN; //Begin with investigating a candidate in the Open Node.
OPEN = best->next_node; //The next node should be set to a next candidate for next step.
best->next_node = CLOSED; //Appends the Closed Nodes to a current best one so that we can keep a constructed path properly.
CLOSED=best; //Move to the Closed Node because this best node will be visited in this time.
//Failed at path finding.
if(best == NULL) {
return NULL;
}
//Succeed!
if (best->x == start_x && best->y == start_y)
return best;
//Extends neighbor nodes from a current node.
if (make_child(best, start_x, start_y) == 0 && count == 0)
return NULL;
count++;
}
return best;
}
Continue to make_child() function.
//the node to extends, and destination x, y. it also returns a value of extension fact.
bool make_child(node_t* node, int dest_x, int dest_y) {
bool extended = false; //Return true if it extended any childs.
int x = node->x;
int y = node->y;
//Create children nodes if they were available space.
//Left
if( is_available_grid(x - 1, y) ) {
extend_child_node(node, x-1, y, dest_x, dest_y, LEFT_IDX);
extended=1;
}
//Implement last 7 directions in the same manner. Differences are just x, y positions.
//Right: x + 1, y
//Top: x, y - 1
//Bottom: x, y + 1
//Top Left: x - 1, y - 1
//Top Right: x + 1, y - 1
//Bottom Left: x - 1, y + 1
//Bottom Right: x + 1, y + 1
return extened;
}
I hope you understood so far. But actually in this game, it would be more realistic that if we allow diagonal moving only if two adjacent grids are available so. The change won't be difficult at all. I believe you can make it yourself.
Don't allow diagonal moving if two adjacent grids are blocked
Next function is extend_child_node(). This function is designed to extend a node and sort it if necessary.
//A node to extend, a current node position, the destination position, a direction to extend
void extend_child_node(node_t* node, int cur_x, int cur_y, int dest_x, int dest_y, int cur_direct) {
node_t *old = NULL, *child = NULL;
int i;
int degree= node->degree + 1;
//If a extending node is existed in Open Node, pick it up.
if (old = Is_open(cur_x, cur_y)) {
node->direct[cur_direct] = old;
//Reset the node. Notice that node order is reversed.
if (degree < old->degree) {
old->prev_node = node;
old->degree = degree;
old->value_factor = old->distance + old->degree;
}
//If a extending node is existed in Close Node.
} else if (old = is_close(cur_x, cur_y)) {
node->direct[cur_direct] = old;
//In some cases, degree won't be valid. Sort it again.
if (degree < old->degree) {
old->prev_node = node;
old->degree = degree;
old->value_factor = old->distance + old->degree;
make_sort(old);
}
//Create a child node and push it into Open Node.
} else {
if ((child = (node_t*) calloc(1, sizeof(node_t))) == NULL)
return; //Lack of memory?
child->prev_node = node;
child->degree = degree;
child->distance = (cur_x - dest_x) * (cur_x - dest_x) + (cur_y - dest_y) * (cur_y - dest_y);
child->value_factor = child->distance + child->degree;
child->x = cur_x;
child->y = cur_y;
insert_node(child);
node->direct[cur_direct] = child;
}
}
It's getting more complex and complex!! If you cannot understand the source code, please draw a temporary path and follow step with this logic. It's going over!
//old: A new node for re-evaluation
void make_sort(node_t* old) {
node_t *direct, *previous;
int i;
int degree = old->degree + 1;
for (i=0; i<8; i++) {
if ((direct = old->direct[i]) == NULL) continue;
//Updates nodes. Use a stack for children
if (direct->degree > degree) {
direct->prev_node = old;
direct->degree = degree;
direct->value_factor = direct->distance + direct->degree;
push_into_stack(direct);
}
}
//Updates nodes using a stack.
while (STACK) {
previous = pop_from_stack();
for (i=0; i<8; i++) {
if ((direct = previous->direct[i]) == NULL) break;
if (direct->degree > previous->degree + 1) {
direct->prev_node = previous;
direct->degree = previous->degree + 1;
direct->value_factor = direct->distance + direct->degree;
push_into_stack(direct);
}
}
}
}
Here, it handles an exceptional case which hasn't been mentioned in the above example. It just re-evaluate the nodes when the Close Node needs update.
Lastly, append a node to the Open Node. Point is, it keeps the order in distance when it push a node.
//new node
void insert_node(node_t* present) {
node_t* old = NULL, *temp = NULL;
if (OPEN == NULL) {
OPEN = present;
return;
}
temp = OPEN;
//Find a node which has a higher value factor than the present.
while (temp && (temp->value_factor < present->value_factor)) {
old = temp;
temp = temp->next_node;
}
//Reconstruct the list. Now these list are sorted by distance.
if (old) {
present->next_node = temp;
old->next_node = present;
} else {
present->next_node = temp;
OPEN = present;
}
}
Somewhat difficult to describe the complex logic by me. But you could hopefully understand what I am talking here. Otherwise, please read the source code considerably.
Anyhow, A* is done here. This logic is for a standard case so definitely you could optimize it further. For instance, we can skip the list of nodes if they just construct a straight way. Or probably we can add a way point in the map in such cases doors and gates. Definitely it would be much better for the path finding. In case of 3D map, I believe it's not much different even though. But you need to google for more information.
astar.cpp