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:
Post a Comment
Got something to say? Speak your mind!