January 17, 2016

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<>();
        path.add(position);
        while (parent != null) {
            path.add(parent.getPosition());
            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
        openNodes.add(startNode);
        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);
                closedNodes.add(node);
                // 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[0].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
                openNodes.add(node);
            } 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);
                    openNodes.add(node);
                }
            }
        }
    }

    // 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<>();
        Log.d(TAG, "GameMap: Map ready!");
    }

    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 MainThread thread;
    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
        getHolder().addCallback(this);

        // 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)
        thread = new MainThread(getHolder(), this);

        // 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
        if (thread.getState() == Thread.State.NEW) {
            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
            thread.setRunning(true);
            // And we start the Game Loop
            thread.start();
        } else if (thread.getState() == Thread.State.TERMINATED) {
            // Start the thread again after a pause
            thread = new MainThread(getHolder(), this);
            thread.setRunning(true);
            thread.start();
        }
    }

    @Override
    public void surfaceDestroyed(SurfaceHolder surfaceHolder) {
        Log.d(TAG, "surfaceDestroyed: Surface is being destroyed!!!");
        // Clean shutdown
        boolean retry = true;
        while (retry) {
            try {
                thread.join();
                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) {
                thread.setRunning(false);
                ((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() {
        thread.setRunning(false);
    }

    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

You can download the source from this post here.

Hope you guys enjoyed this tut! I'll be organizing them all in a single post called Android 2D RPG with links to each one, for ease of finding information. Which means I will also update all previous posts hotlinking the index one. So, what I'm trying to say is, next post in the series (which will be about making the map movement smooth(er) than it is right now) might take a bit to come together, but it's definitely coming, hang in there!

Thanks for reading, please share and follow me! :) Take care!

No comments: