Mobile Game Developer Forums
Welcome, Guest
Apphex Forums
>
Mobile Game Development
>
Android Game Programming
AStar Pathfinding Algorithm (Android)
AStar Pathfinding Algorithm (Android)
Previous Thread
·
Next Thread
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 20170318
This article explores the basics of implementing Astar (A*) pathfinding algorithm within Android games.
Introduction
Astar (A*) is probably the most commonly used algorithm in games pathfinding and graph traversal. With the Astar 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 bestfirst search and finds a leastcost 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 tilebased 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 Astar (A*) pathfinding algorithm within Android games.
As a powerful and useful algorithm, Astar (A*) is widely used in games pathfinding and graph traversal. With the Astar 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* (AStar)
You never know till you have tried
Back to top
Zambie
Posted :
Sun, 19 Mar 2017 19:52:20 
[#2]
Rank:
New Member
Joined: 11/5/2016
Posts: 19
Rubies: 30
Nice article, :p
Back to top
epalm
Posted :
Mon, 10 Apr 2017 20:00:57 
[#3]
Rank:
New Member
Joined: 11/5/2016
Posts: 1
Rubies: 5
Thanks for sharing, :)
Back to top
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 ½ ¾
Back to top
b3DMax
Posted :
Fri, 14 Apr 2017 10:10:27 
[#5]
Rank:
Bronze Member
Joined: 8/24/2016
Posts: 13
Rubies: 20
Really appreciated. :D
Back to top
b3DMax
Posted :
Fri, 14 Apr 2017 10:11:54 
[#6]
Rank:
Bronze Member
Joined: 8/24/2016
Posts: 13
Rubies: 20
Bookmarked.
Back to top
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
Back to top
doid
Posted :
Fri, 11 Aug 2017 19:29:41 
[#8]
Rank:
New Member
Joined: 9/7/2016
Posts: 12
Rubies: 16
Thanks for sharing.
Back to top
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
Back to top
Forum Jump
Announcements
 Releases, Events & Offerings
Mobile Game Development
 Android Game Programming
 iOS Game Programming
 Programming Tutorials & Free Downloads
New IT Techniques
 Breaking into the Game Industry
 Java Development
 Programming Languages & Tools
 Database Development
 Everything Linux/Unix
News and Talk
 Hot Games, Apps & More
 Everything Mobile
 Walkthroughs & Guides
 Ringtone & Wallpaper Downloads
Community Interaction
 Comments, Suggestions & Ideas
 Lounge
 Help Wanted
 Support & Feedback
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 :
This page was generated in 0.829 seconds
Watch this thread
RSS Feed
Email this thread
Print this thread
Threaded
Normal
Home

Top Mobile Games

Developer Resource

Forum Rules

Sitemap

Downloads

Contact Us

About Us
Copyright ©2017 
Apphex Forums
Powered by:
cstcode
v1.0.5