### Android 2D RPG - Part 9: Pathfinding

Hello readers! How's everything? I hope all good! Today we're going to implement pathfinding in our game! We've been looking forward for this for a while now, huh? xD After this post we will essentially be able to move our character through a path from its starting position to one we select, provided that is a reachable one, of course.

For pathfinding we're going to be using the A* (AStar) algorithm, which is pretty much the algorithm-to-go for games' pathfinding. I'm not going to go into detail on the algorithm itself, you can read about it on it's wikipedia site, and I recommend everyone to do so!

So, we basically will need to have a start and end position (duh!) with x and y coordinates of each one (for ease of use, we'll be using java's Point class, which is essentially that, x and y coordinates accessed as Point.x and Point.y). We'll also need a boolean array of arrays (boolean[][]) which will represent our movement map. With all this, we'll build an array of points which will be our movement path. I.e. if hero is at position (0,0) and we want to move it to (1,1), our path could be {(0,0), (0,1) , (1,1)}.

Note: In our boolean map, false will represent the coordinates where we cannot move to. For now, this means the object layer of our map, in the future, we'll add NPCs to this list, and maybe other map layers or game elements.

In order to implement this, we'll add 2 more classes (Node.java and AStar.java), the code is below.

Node.java
```package com.example.mygame;

import android.graphics.Point;
import android.support.annotation.NonNull;

import java.util.ArrayList;

// We need to implement Comparable in order to sort (by cost in this case) an array of Nodes
public class Node implements Comparable<Node> {

private Point position;     // Coordinates of the node (map square)
private Node parent;        /* Node that was visited previous to this one
*  null if it's the starting node. (Named parent Node) */
private int costFromStart;  // Number of nodes visited in order to get to this one
private int cost;           /* costFromStart + Manhattan distance from this node
*  to the end one */

// Node constructor
public Node(Point position, Point target, Node parent) {
this.position = position;
this.parent = parent;
if (parent != null) costFromStart = parent.getCostFromStart() + 1;
else costFromStart = 1;
// Calculate cost using Manhattan distance
cost = costFromStart + Math.abs(target.x - position.x) + Math.abs(target.y - position.y);
}

// Used to get a Node's map coordinates
public Point getPosition() {
return position;
}

// Used to get a Node's parent Node
public Node getParent() {
return parent;
}

// Used to get a Node's cost to reach, used to set cost to next visited nodes
public int getCostFromStart() {
return costFromStart;
}

// Used to get the total (estimated) cost of a Node
public int getCost() {
return cost;
}

// Used to compare Nodes (uses cost for comparison). Important to sort an array of Nodes
public int compareTo(@NonNull Node node) {
if (cost > node.getCost()) return 1;
else if (cost == node.getCost()) return 0;
else return -1;
}

/* Used to verify if 2 Nodes are the same, for our purposes,
*  2 Nodes are the same by simply having the same coordinates */
@Override
public boolean equals(Object object) {
return ((object != null) && (object instanceof Node) &&
((Node) object).getPosition().x == position.x &&
((Node) object).getPosition().y == position.y);
}

// Builds the array of Points (path) after AStar is over
public ArrayList<Point> buildPath() {
ArrayList<Point> path = new ArrayList<>();
while (parent != null) {
this.parent = parent.getParent();
}
return path;
}
}
```

AStar.java
```package com.example.mygame;

import android.graphics.Point;
import android.util.Log;

import java.util.ArrayList;
import java.util.Collections;

public class AStar {

private static final String TAG = AStar.class.getSimpleName();

private ArrayList<Node> openNodes = new ArrayList<>();    // List of closed Nodes (visited)
private ArrayList<Node> closedNodes = new ArrayList<>();  /* List of open Nodes
*  (can be visited) */
private boolean[][] map;                                  // Movement map
private Point target;                                     // End position
private boolean pathFound = false;                        /* Flag to indicate if finding a path
*  was possible */
private ArrayList<Point> path;                            // Movement path to reach end position

// AStar constructor
public AStar(boolean[][] map, Point start, Point target) {
this.map = map;
this.target = target;
Node startNode = new Node(start, target, null);
// Add starting to Node to open list
findPath();
}

// Main search algorithm
private void findPath() {
// Check if there are Nodes available to be visited
if (openNodes.size() > 0) {
// Order Nodes by cost (lowest to highest)
Collections.sort(openNodes);
// Get lowest cost Node
Node node = openNodes.get(0);
// Verify if the Node is the end one
if (node.getPosition().x != target.x ||
node.getPosition().y != target.y) {
// Move Node from open to closed list
openNodes.remove(0);
// Try to add neighbor Nodes to the open list
checkNode(new Node(new Point(node.getPosition().x, node.getPosition().y + 1),
target, node));
checkNode(new Node(new Point(node.getPosition().x + 1, node.getPosition().y),
target, node));
checkNode(new Node(new Point(node.getPosition().x, node.getPosition().y - 1),
target, node));
checkNode(new Node(new Point(node.getPosition().x - 1, node.getPosition().y),
target, node));
// Repeat
findPath();
} else {
// If got to the end Node, we end the search
pathFound = true;
path = node.buildPath();
}
} else Log.d(TAG, "findPath: No path found!");
}

// Function to check if a neighbor Node can be added to the open Nodes list
private void checkNode(Node node) {
// Verify the Node's position is between the map's borders
// Verify the Node's position is a valid movement one (using the boolean map)
// Verify the Node is not already in the closed Nodes list
if (node.getPosition().x >= 0 && node.getPosition().y >= 0 &&
node.getPosition().x < map.length && node.getPosition().y < map.length &&
map[node.getPosition().y][node.getPosition().x] && !closedNodes.contains(node)) {
// If those 3 conditions are met, check if the Node is already on the open list
if (!openNodes.contains(node)) {
// If it's not, we add it to the open list
} else {
// If it is, we pick the one with the lowest cost and discard the other
int nodeIndex = openNodes.indexOf(node);
if (node.getCostFromStart() < openNodes.get(nodeIndex).getCostFromStart()) {
openNodes.remove(nodeIndex);
}
}
}
}

// Check if a path was found or not
public boolean getPathFound() {
return pathFound;
}

// Returns the array of Points (movement path)
public ArrayList<Point> getPath() {
if (pathFound) {
return path;
} else return new ArrayList<>();
}
}
```

Note: this implementation was made by me, using general knowledge of the algorithm. And it's a slightly modified version of the pseudo-code in order to better suit our game needs. For instance, the original algorithm includes diagonal movements, since that's not an option in our game, they're not present in this code, although they can be easily added if we introduce diagonal movement in the future...

Now, let's see the changes we did to previous classes in order to implement the walking movement.

GameMap.java
```package com.example.mygame;

import android.graphics.Bitmap;
import android.graphics.Canvas;
import android.graphics.Point;
import android.graphics.Rect;
import android.util.Log;

import java.util.ArrayList;

public class GameMap {

// Constant for logging
private static final String TAG = GameMap.class.getSimpleName();

// Number of sprites per row of our bitmap
// Depends on the tileset you're using
private static final int TILESET_COLS = 8;

private Bitmap bitmap;          // The image of our map's tiles
private int[] terrain;          // Array of terrain for background buffer
private int[] object;           /* Array of objects for background buffer
* (hero can't move through this) */
private int[] roof;             // Array of elements for the top buffer
private int width;              // Numbers of squares in a map row
private int square;             // Screen square size
private Bitmap buffer;          // Buffer for background elements
private Bitmap roofBuffer;      // Buffer for top elements (covers bottom, hero, NPCs, etc)
private int x;                  // Hero's x coordinate
private int y;                  // Hero's y coordinate
private int drawX;              // x coordinate to draw map
private int drawY;              // y coordinate to draw map
private boolean[][] map;        // Movement map
private Hero hero;              // Hero
private ArrayList<Point> path;  // Movement path

// GameMap constructor
public GameMap(Bitmap bitmap, int[] terrain, int[] object, int[] roof, int width, int square,
int x, int y, Hero hero) {
this.bitmap = bitmap;
this.terrain = terrain;
this.object = object;
this.roof = roof;
this.width = width;
this.square = square;
this.x = x;
this.y = y;
this.hero = hero;
// Fill drawing buffers
fillBuffers();
// Fill movement map
fillMap();
path = new ArrayList<>();
}

private void fillBuffers() {
// We create 2 image buffers to be drawn on each render
// One for background elements (buffer)
// Another for top elements (roofBuffer)
buffer = Bitmap.createBitmap(width * square, (terrain.length / width) * square, Bitmap.Config.ARGB_8888);
roofBuffer = Bitmap.createBitmap(width * square, (terrain.length / width) * square, Bitmap.Config.ARGB_8888);
Canvas canvas = new Canvas(buffer);
Canvas roofCanvas = new Canvas(roofBuffer);
// Draw each array on the corresponding buffer
// Easy to expand if there's need to add more layers
draw(terrain, canvas);
draw(object, canvas);
draw(roof, roofCanvas);
}

// Draws a map layer on a buffer's canvas
private void draw(int[] ints, Canvas canvas) {
// Draw an array of sprite ids into a canvas
int spriteSize = (bitmap.getWidth() / TILESET_COLS);
for (int i = 0; i < (ints.length / width); i++) {
for (int j = 0; j < width; j++) {
int sprite = ints[(i * width) + j] - 1;
if (sprite >= 0) {
Rect src = new Rect((sprite % TILESET_COLS) * spriteSize,
(int) Math.floor(sprite / TILESET_COLS) * spriteSize,
(sprite % TILESET_COLS) * spriteSize + spriteSize,
(int) Math.floor(sprite / TILESET_COLS) * spriteSize + spriteSize);
Rect dst = new Rect(j * square, i * square, (j + 1) * square, (i + 1) * square);
canvas.drawBitmap(bitmap, src, dst, null);
}
}
}
}

// Draws the background buffer onto the screen
public void renderBottom(Canvas canvas) {
canvas.drawBitmap(buffer, drawX, drawY, null);
}

// Draws the top buffer onto the screen
public void renderTop(Canvas canvas) {
canvas.drawBitmap(roofBuffer, drawX, drawY, null);
}

// Update map state on each game loop
public void update() {
// Verify if the movement path is empty
int size = path.size();
if (size > 0) {
// If it's not empty we move to the next coordinates
size--;
// Change the direction our hero is facing as needed
if (x < path.get(size).x) hero.setDirection(2);
else if (x > path.get(size).x) hero.setDirection(1);
else if (y < path.get(size).y) hero.setDirection(0);
else if (y > path.get(size).y) hero.setDirection(3);
// Modify drawing parameters
drawX += (square * (x - path.get(size).x));
drawY += (square * (y - path.get(size).y));
// Modify hero's position
x = path.get(size).x;
y = path.get(size).y;
// Remove the used coordinates from movement path
path.remove(size);
}
}

// Sets the initial coordinates to draw our map at
// Needs to be called after our GamePanel is created
public void setDrawCoordinates(int drawX, int drawY) {
this.drawX = (drawX / 2) - (square / 2) - (x * square);
this.drawY = (drawY / 2) - (square / 2) - (y * square);
}

// Lets map handle touch actions
public void handleActionDown(int eventX, int eventY) {
/*
* At the moment, this moves our hero
* to the touched map square (if possible)
*/
eventX = (int) Math.floor((eventX - drawX) / square);
eventY = (int) Math.floor((eventY - drawY) / square);
Log.d(TAG, "handleActionDown: Square: x=" + eventX + ", y=" + eventY);
if ((eventX >= 0) && (eventY >= 0) && (eventX < width) &&
(eventY < terrain.length / width) && map[eventY][eventX]) {
// Try to find a movement path to touched square
AStar aStar = new AStar(map, new Point(x, y), new Point(eventX, eventY));
if (aStar.getPathFound()) {
path = aStar.getPath();
Log.d(TAG, "handleActionDown: " + path);
}
} else {
Log.d(TAG, "handleActionDown: Impossible to move there!");
}
}

// Fill movement map
private void fillMap() {
map = new boolean[object.length / width][width];
for (int i = 0; i < (object.length / width); i++) {
for (int j = 0; j < width; j++) {
int data = object[(i * width) + j];
map[i][j] = (data <= 0);
}
}
}
}
```

Hero.java

```package com.example.mygame;

import android.graphics.Bitmap;
import android.graphics.Canvas;
import android.graphics.Rect;
import android.util.Log;

public class Hero {

// Constant for logging
private static String TAG = Hero.class.getSimpleName();

private Bitmap bitmap;     // The image of our character sprites
private int square;        // Size of screen square
private int x;             // The x coordinate of our character
private int y;             // The y coordinate of our character
private int direction;     // The direction the character is facing
// (0 down, 1 left, 2 right, 3 up. The order of our sprite image)
private int sprite;        // The animation sprite, since our characters have 3 sprites per
// animation, this ranges from 0 to 2
private int spriteHeight;  // Size (in pixels) of a single sprite height
private int spriteWidth;   // Size (in pixels) of a single sprite width
private Rect src;          // Square of the image to be drawn
private Rect dst;          // Square of the screen to draw unto

// Hero constructor
public Hero(Bitmap bitmap, int square) {
this.bitmap = bitmap;
this.square = square;
this.direction = 0;
this.sprite = 0;
this.spriteHeight = bitmap.getHeight() / 4; // 4 directions
this.spriteWidth = bitmap.getWidth() / 3;   // 3 sprites per direction
this.src = new Rect(0, 0, spriteWidth, spriteHeight);
Log.d(TAG, "Hero: Hero created!");
}

// Used to get the image our hero is using to draw itself (currently unused)
public Bitmap getBitmap() {
return bitmap;
}

// Used to change the image our hero is using to draw itself (currently unused)
public void setBitmap(Bitmap bitmap) {
this.bitmap = bitmap;
}

// Used to get hero's y coordinate for drawing (currently unused)
public int getX() {
return x;
}

// Used to change hero's x coordinate for drawing
public void setX(int x) {
this.x = (x - square) / 2;
}

// Used to get hero's y coordinate for drawing (currently unused)
public int getY() {
return y;
}

// Used to change hero's y coordinate for drawing
public void setY(int y) {
this.y = (y - square) / 2;
}

// Used to get hero's facing direction (currently unused)
public int getDirection() {
return direction;
}

// Used to change hero's facing direction
public void setDirection(int direction) {
this.direction = direction;
src.top = spriteHeight * direction;
src.bottom = src.top + spriteHeight;
}

// Sets the coordinates to draw our hero at
// Needs to be called after our GamePanel is created
public void setDrawSquare() {
this.dst = new Rect(this.x, this.y, this.x + square, this.y + square);
}

// Draws the hero on screen
public void draw(Canvas canvas) {
canvas.drawBitmap(bitmap, src, dst, null);
}

// Update hero state on each game loop
public void update() {
/*
* At the moment, this changes the hero's sprite to be drawn
*/
sprite++;
src.left += spriteWidth;
src.right += spriteWidth;
if (sprite > 2) {
sprite = 0;
src.left = 0;
src.right = spriteWidth;
}
}

}
```

GameMap.java

```package com.example.mygame;

import android.app.Activity;
import android.content.Context;
import android.graphics.BitmapFactory;
import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import android.util.Log;
import android.view.MotionEvent;
import android.view.SurfaceHolder;
import android.view.SurfaceView;

public class GamePanel extends SurfaceView implements SurfaceHolder.Callback {

// Constant for logging
private static final String TAG = GamePanel.class.getSimpleName();

// Size of the sprites to be drawn on screen
private static final int SPRITE_SIZE = 64;

private Hero hero;
private GameMap gameMap;

// Paint used to paint bottom of screen red
private Paint paint = new Paint();

public GamePanel(Context context) {
super(context);
// Adding callback (this) to surface holder to catch events

// Create our hero and load it's bitmap
hero = new Hero(BitmapFactory.decodeResource(getResources(), R.drawable.alex), SPRITE_SIZE);

// Create our game map, load bitmap, fill buffers
gameMap = new GameMap(BitmapFactory.decodeResource(getResources(), R.drawable.tileset),
new int[] {1,1,1,1,1,1,1,1,1,1,1,1,
16,16,1,16,1,1,1,1,8,8,1,1,
1,1,1,16,1,1,1,16,16,16,8,16,
1,8,8,8,8,8,8,1,1,1,1,1,
1,16,1,1,1,1,8,1,1,1,1,1,
1,1,1,1,8,8,8,8,8,8,8,1,
1,1,8,8,8,1,8,1,1,1,1,1,
8,8,1,1,1,1,8,1,1,1,1,1,
1,1,1,1,1,1,8,1,1,1,1,8,
1,8,8,8,8,1,8,1,1,1,8,1,
16,16,16,1,1,1,8,8,8,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1}, new int[] {55,55,55,55,55,55,55,55,55,55,55,55,
55,0,72,0,0,0,0,0,0,71,0,55,
55,68,0,0,0,0,0,71,0,0,0,55,
55,0,0,0,65,66,0,0,0,0,68,55,
55,0,0,0,0,0,0,0,0,0,0,55,
55,39,40,0,0,0,0,39,40,0,0,55,
55,0,0,0,0,68,0,0,0,0,0,55,
55,0,0,0,0,0,0,0,65,66,0,55,
55,0,0,0,72,0,0,0,0,0,0,55,
55,65,66,0,0,0,0,39,40,0,72,55,
55,0,0,0,0,68,0,0,0,0,0,55,
55,55,55,55,55,55,55,55,55,55,55,55}, new int[] {47,0,0,0,0,0,0,0,0,0,0,47,
47,60,61,0,0,0,0,0,0,0,0,47,
47,0,69,0,57,58,0,0,0,59,60,47,
47,0,0,0,0,0,0,0,0,67,0,47,
47,0,0,0,0,0,0,0,0,0,0,47,
47,0,0,0,59,60,61,0,0,0,0,47,
47,0,0,0,67,0,69,0,57,58,0,47,
47,0,0,0,0,0,0,0,0,0,0,47,
47,57,58,0,0,0,0,0,0,0,0,47,
47,0,0,0,59,60,61,0,0,0,0,47,
47,47,47,47,47,47,47,47,47,47,47,47,
0,0,0,0,0,0,0,0,0,0,0,0}, 12, SPRITE_SIZE, 2, 2, hero);

// Create the Game Loop (the thread)

// Make GamePanel able to focus so it can handle events
setFocusable(true);
}

@Override
public void surfaceChanged(SurfaceHolder surfaceHolder, int format, int width, int height) {

}

@Override
public void surfaceCreated(SurfaceHolder surfaceHolder) {
// Check if its the first time the thread starts
paint.setColor(Color.RED);
hero.setX(getWidth());
hero.setY(getHeight());
hero.setDrawSquare();
gameMap.setDrawCoordinates(getWidth(), getHeight());
// When the surface is created we set the running flag to true
// And we start the Game Loop
// Start the thread again after a pause
}
}

@Override
public void surfaceDestroyed(SurfaceHolder surfaceHolder) {
Log.d(TAG, "surfaceDestroyed: Surface is being destroyed!!!");
// Clean shutdown
boolean retry = true;
while (retry) {
try {
retry = false;
} catch (InterruptedException e) {
// Try again to shut down the thread
}
}
Log.d(TAG, "surfaceDestroyed: Thread was shut down cleanly.");
}

@Override
public boolean onTouchEvent(MotionEvent event) {
// Detect a touch event
if (event.getAction() == MotionEvent.ACTION_DOWN) {
// End game if lower part of screen (64px) is touched
if (event.getY() > getHeight() - 64) {
((Activity) getContext()).finish();
} else {
// Log touch coordinates
Log.d(TAG, "onTouchEvent: Coordinate: x=" + event.getX() + ", y=" + event.getY());
// Let GameMap handle the touch event
gameMap.handleActionDown((int) event.getX(), (int) event.getY());
}
}
return super.onTouchEvent(event);
}

@Override
protected void onDraw(Canvas canvas) {

}

public void render(Canvas canvas) {
// Fill screen with black
canvas.drawColor(Color.BLACK);
// Draw background buffer
gameMap.renderBottom(canvas);
// Draw hero
hero.draw(canvas);
// Draw top buffer
gameMap.renderTop(canvas);
// Fill bottom 64px of screen with red (for closing game)
canvas.drawRect(0, canvas.getHeight() - 64, canvas.getWidth(), canvas.getHeight(), paint);
}

public void setRunningFalse() {
}

public void update() {
// Update hero
hero.update();
// Update map
gameMap.update();
}
}
```

That's it! Now our character can move across the maps we create using the shortest path available to it's destination! It looks more like a real game now, doesn't it? :P At this moment, this game can be a lot of things, this is a good base for a lot of games, try it, be creative, go crazy! :P