top mobile game developers forum
Mobile Game Developer Forums

A-Star Pathfinding Algorithm (Android)

A-Star Pathfinding Algorithm (Android)
cstcoder
Posted : Sat, 18 Mar 2017 19:46:19 - [#1]


Group:  Moderator  
Rank:   Bronze Member
Joined:  6/29/2016
Posts:   23
Rubies:  993 
Location:  Vancouver
By cstcoder 2017-03-18

This article explores the basics of implementing A-star (A*) pathfinding algorithm within Android games.

Introduction
A-star (A*) is probably the most commonly used algorithm in games pathfinding and graph traversal. With the A-star search algorithm it’s possible to find the shortest path from one node to another on a tile map, and this really make sense in scenarios when there’re chasms, rocks or other obstacles on the way.
A* uses a best-first search and finds a least-cost path from a given initial node to one goal node by maintaining a pair of lists: open list and closed list. open list is a list of all the nodes that have been examined and assigned cost in an iteration of the search, while closed list is a list of nodes whose neighbors have been examined. For every iteration, A* always picks the neighbor with a least actual cost to proceed to. To make it clear, we’ll go through a few basic concepts below.



Basic Concepts
The classic cost representation in A* algorithm is

Code:
f(n) = g(n) + h(n)


g(n) represents the total cost from the starting node to the current node.

h(n) is the estimated cost from the current node to the destination. A heuristic function is used to create this estimate on how far away it will take to reach the goal state.

f(n) is the sum of g(n) and h(n). This is the cost of the current estimated shortest path.

Here are a few more concepts need to be considered:
o Node: It can be a tile (square) in a tile-based environment or a point along a path. An A* path contains at least 2 nodes: a starting node and an ending node. A* will calculate all the nodes to get from the start to the end.
o Parent Node: When a node is examined, its neighbors (directly connected nodes) are assigned that node as their parent.
o Open list: This is a list of all the nodes that have been examined and assigned cost in an iteration of the search. The node that has the lowest cost will be used to perform the next iteration of the search.
o Closed list: This is the list of nodes whose neighbors have been examined.
o Cost: Cost is the distance travelled. In pathfinding, nodes with a lower cost are preferably used over nodes with a higher cost.
o Heuristic: The heuristic function tells A* an estimate of the minimum cost from a particular node to the destination. It’s important to choose a good heuristic function in searching for a path.
o Euclidean Distance: The shortest distance from a particular node to the goal. If your objects can move at any angle instead of grid directions, then you should probably use a straight line distance:
Code:
function heuristic(node) {
    dx = goal.x – node.x;
    dy = goal.y – node.y;
    return COST * sqrt((dx*dx)+(dy*dy));
}


o Manhattan Distance: The standard heuristic for a square grid is the Manhattan distance. This is an approximation of the distance between two points based on adding the horizontal distance and vertical distances rather than computing the exact difference. That would look like this:
Code:
function heuristic(node) {
    dx = abs(goal.x – node.x);
    dy = abs(goal.y – node.y);
    return COST * (dx+dy);
}




How A* actually works
Now that you understand the basic concepts, before we actually begin coding, let’s just take a look at how A* actually works.
1) Provide a starting node (or square) and an ending node (or square).
2) Add the starting node to the open list.
3) Start the search loop.
a). Look for the lowest f(n) cost on the open list– we refer to this as the current node. When we first run the loop this will obviously be our starting node.
b). If the current node is the same as the destination then we are done and we can move on to step 4 to build the path.
c). For each of the 8 neighbor nodes adjacent to the current node:
 If the node is not traversable or if it’s on the closed list, skip it. Otherwise do the following.
 If it isn’t on the open list, add it to the open list. Calculate the cost of that node and set the current node as the parent.
 If it’s already on the open list, see if this path to that node has a lower G cost. If so, switch the parent of the node to the current node, and recalculate the G and F scores of the square.
d) Quit the loop when:
 The target node is added onto the closed list, which means the path has been found. Or
 Fail to find the target node, and the open list is empty. In this case, there is no path.
4) Construct the path. Working backwards from the target node, go from each node to its parent until it reaches the starting node.

We should now have a list of all the nodes that make up the best path from the starting node to the destination.




Implementation
First we will start with our Node class.
Code:
public class Node implements Comparable<Object> {
    public Point _pos; //node position
    public int _costG;// the cost to get to that node from the starting node
    public int _costH;// the estimated cost to get from that node to the end node
    public Node _parentNode; //parent node
 
    private Node() {//Constructor
    }

    public Node(Point _pos) {
        this._pos = _pos;
    }

    public int getCost(Node node) {//cost estimating based on Euclidean Distance.
        int m = node._pos.x - _pos.x;
        int n = node._pos.y - _pos.y;
        return (int) Math.sqrt(m * m + n * n);
    }
 
    public boolean addNode(Object node) {//Add the node with lower cost to the open list
        int node1 = _costG + _costH;
        int node2 = ((Node) node)._costG + ((Node) node)._costH;
        if (node1 <= node2)  return true;
        else false;
    } 
}




Now we will define a class called Pathfinder:
Code:
public class PathFinder {
    private OpenList _openList; //open list
    private LinkedList<Node> _closedList; //closed list
    private int[][] _map; //map array
    private int[] _block; //block array

    public PathFinder(int[][] map, int[] block) {//Constructor
        _map = map;
        _block = block;
        _openList = new OpenList();
        _closedList = new LinkedList<Node>();
    }

    public List<Node> searchPath(Point startPos, Point endPos) {
        Node startNode = new Node(startPos);//Initialize the start node & end node
        Node endNode = new Node(endPos);
        startNode._costG = 0;
        startNode._costH = startNode.getCost(endNode);
        startNode._parentNode = null;
        _openList.add(startNode); //put the current node into open list

        // Start our loop until the open list is empty, then we are done and we can build the path.
        while (!_openList.isEmpty()) {
            Node firstNode = (Node) _openList.removeFirst();

            // Check If the current node is the same as our destination
            if (firstNode.equals(endNode)) {
                // //build the path if the current node is the same as our destination
                return buildPath(firstNode);
            } else { // if not, add the node to the closed list
                _closedList.add(firstNode);
                LinkedList<Node> _block = firstNode.getBlock();//get the block array

                // Test each node out of the connected nodes. If the node is the same as our
                // current node or it is not traversable, move on to the next connected node.
                for (int i = 0; i < _block.size(); i++) {
                    Node connectedNode = (Node) _block.get(i);
                    connectedNode._costG = firstNode._costG+1;
                    connectedNode._costH = connectedNode.getCost(endNode);
                    connectedNode._parentNode = firstNode;
                    _openList.add(neighborNode);
                }
            }
        }
   
        _openList.clear(); //empty open/closed lists when the loop finished
        _closedList.clear();
        return null;
    }
……
}




Finally, we move forward to explain how to invoke the path finder within the main thread. We need to provide a starting and ending node for the path each time and the information of all the moving entities as well.
private PathFinder astar;
astar = new PathFinder(BlockMatrix, BlockCondition);
path = astar.searchPath(new Point(hero.col, hero.row), new Point(clickCol, clickRow));
Code:
if(path != null && path.size()>1) {
    hero.step = 0;
    hero.setHeroStatus(HERO_TRACE);
    //Do further things…
}




Summary
This article explored the basics of implementing A-star (A*) pathfinding algorithm within Android games.
As a powerful and useful algorithm, A-star (A*) is widely used in games pathfinding and graph traversal. With the A-star search algorithm it’s possible to find the shortest path from one node to another on a tile map, especially in scenarios when there’re chasms, rocks or other obstacles on the way.

References
1. Tower defense A* pathfinding
2. Searching using A* (A-Star)

You never know till you have tried
Zambie
Posted : Sun, 19 Mar 2017 19:52:20 - [#2]


Rank:    New Member
Joined:  11/5/2016
Posts:   19
Rubies:  30 
Nice article, :p
epalm
Posted : Mon, 10 Apr 2017 20:00:57 - [#3]


Rank:    New Member
Joined:  11/5/2016
Posts:   1
Rubies:  5 
Thanks for sharing, :)
duke
Posted : Thu, 13 Apr 2017 20:02:41 - [#4]


Group:  Moderator  
Rank:   Bronze Member
Joined:  7/16/2016
Posts:   14
Rubies:  107 
That's what im looking for, thx man!

Being on sea, sail; being on land, settle ½ ¾
b3DMax
Posted : Fri, 14 Apr 2017 10:10:27 - [#5]


Rank:    Bronze Member
Joined:  8/24/2016
Posts:   13
Rubies:  20 
Really appreciated. :D Applause
b3DMax
Posted : Fri, 14 Apr 2017 10:11:54 - [#6]


Rank:    Bronze Member
Joined:  8/24/2016
Posts:   13
Rubies:  20 
Bookmarked. Angel
siley
Posted : Fri, 11 Aug 2017 19:16:48 - [#7]


Rank:    New Member
Joined:  8/24/2016
Posts:   13
Rubies:  17 
Location:  Toronto
Thanks for sharing, reserved
doid
Posted : Fri, 11 Aug 2017 19:29:41 - [#8]


Rank:    New Member
Joined:  9/7/2016
Posts:   12
Rubies:  16 
Pray Thanks for sharing. Applause Speak to the hand
rstella
Posted : Fri, 11 Aug 2017 19:44:31 - [#9]


Rank:    New Member
Joined:  8/24/2016
Posts:   7
Rubies:  11 
Location:  Seattle
Lovely, Bookmarked :O


Forum Jump
You may not post new threads in this forum.
You may not reply to threads in this forum.
You may not delete your posts in this forum.
You may not edit your posts in this forum.
You may not create polls in this forum.
You may not vote in polls in this forum.
Main Forum RSS : RSS
This page was generated in 0.832 seconds
Home | Top Mobile Games | Developer Resource | Forum Rules | Sitemap | Downloads | Contact Us | About Us
Copyright ©2017 - Apphex Forums  Powered by: cstcode v1.0.5