Thursday, March 14, 2013

A Star (A*) Pathfinding

I decided the next thing I wanted to implement was a path finder.  It appears to be a universal standard in game development to use the A* algorithm, so I decided to implement that for my hex map.  The good news is that most of the work was already done for me by Kevin Glass over at Coke And Code who has written an excellent article with sample code in Java.  His code is way more general than I was prepared to implement just yet, so I commented out a bunch of stuff I haven't even started thinking about yet, and changed a few things to work on a hex map, and voila!  In the process, I also read a lot about heuristics here, and found some insights to be quite interesting (e.g. not square-rooting Euclidean distance being a bad idea, adding tie-breakers to get more attractive paths, searching for multiple goals and more).  I'm sure that if I ever need to make a more sophisticated pathfinder, this website will prove invaluable!

I'll let you read Kevin Glass' article for an understanding of how the algorithm works, which is a good idea especially considering how I gutted it to get only the essential features to make it work.  When I cut the "fluff" (AKA, the stuff that makes it powerful and general) out of his algorithm, I was left with two class:
  1. Path.java
  2. AStarPathFinder.java
There were two noteworthy changes I had to make to my code, one little, one huge.  I'll start with the little one:

One of the steps in the algorithm is to find all the neighbors of a node, which was nice because I had already created a getNeighbors() method in MapTools to do exactly that.  Alas, I had to fix a major bug in mine: it had no problem returning negative coordinates for the neighbors.  That's because it was stupid and had no idea where the boundary of the world was, and when asked to find neighbors of cell (0,0), it had no problem going outside the world.  My updated algorithm changes it from a fixed size Pair[] array into the libgdx built in class Array.  This is nicer because it permits a variable length of array members (a tile at the border has fewer neighbors than a tile at the center).

Here's what the updated code looks like:
public static Array<Pair> getNeighbors(int x, int y, int n) {
  Array<Pair> coordinates = new Array<Pair>();
  int min;
  int myrow;
  for (int row = y-n; row<y+n+1; row++) {
   min = MyMath.min(2*(row-y+n), n, -2*(row-y-n)+1);
   for (int col = x-min; col < x+min+1; col++) {
    if ((col < 0) || (col >= width())) continue;
    if (x==col && y==row) continue;
    else if (x % 2 == 0) myrow = 2*y-row;
    else myrow = row;
    if ((myrow < 0) || (myrow >= height())) continue;
    coordinates.add(new Pair(col,myrow));
   }
  }
  return coordinates;
 }


One lines 8 and 12 I check to make sure the coordinates are within the boundary of the world.

The more major change is that I used to store the GameMap as its own Entity, which was nice because I could make a RenderingSystem which would catch it every cycle, and I was excited about the possibility of making the map dynamic and interact with other entities.

Unfortunately, any time I want an Entity to find a path from one point to another, that entity has to be able to see the map.  In fact, that's a pretty basic requirement for a game... things have to be able to see the things around them.  Duh, right?!  Well, that wasn't very clean when the GameMap was an Entity.

Instead, I remembered the old VoidEntitySystem which was a system which will run every time, but doesn't do so for a list of entities.  In SpaceshipWarrior we used one to spawn enemy ships.  In my game here, I'm going to use one to draw a map.

So I created a new package called com.blogspot.javagamexyz.gamexyz.maps and added a class GameMap.java into com.blogspot.javagamexyz.gamexyz.maps which looks a lot like the component did (with the addition of a pathFinder field), but now is a stand alone class.
package com.blogspot.javagamexyz.gamexyz.maps;

import com.badlogic.gdx.graphics.Color;
import com.badlogic.gdx.graphics.Pixmap;
import com.badlogic.gdx.graphics.Texture;
import com.blogspot.javagamexyz.gamexyz.pathfinding.AStarPathFinder;
import com.blogspot.javagamexyz.gamexyz.utils.HexMapGenerator;

public class GameMap {
 public int[][] map;
 public int width, height;
 public Pixmap pixmap;
 public Texture texture;
 public AStarPathFinder pathFinder;
 
 public GameMap() {
  HexMapGenerator hmg = new HexMapGenerator();
  map = hmg.getDiamondSquare();
  width = map.length;
  height = map[0].length;
  pixmap = new Pixmap(width,height,Pixmap.Format.RGBA8888);
  
  for (int i=0; i<width;i++) {
   for (int j=0;j<height;j++) {
    pixmap.setColor(getColor(map[i][j]));
    pixmap.drawPixel(i, j);
   }
  }
  
  texture = new Texture(pixmap);
  pixmap.dispose();
  
  pathFinder = new AStarPathFinder(map, 100);
  
 }
 
 private Color getColor(int color) { //  r    g    b
  if (color == 0)      return myColor(34  ,53  ,230);
  else if (color == 1) return myColor(105 ,179 ,239);
  else if (color == 2) return myColor(216 ,209 ,129);
  else if (color == 3) return myColor(183 ,245 ,99);
  else if (color == 4) return myColor(109 ,194 ,46);
  else if (color == 5) return myColor(87  ,155 ,36);
  else if (color == 6) return myColor(156 ,114 ,35);
  else if (color == 7) return myColor(135 ,48  ,5);
  else return new Color(1,1,1,1);
 }
 
 private static Color myColor(int r, int g, int b) {
  return new Color(r/255f, g/255f, b/255f,1);
 }
 
}

I also changed MapRenderSystem.java to the VoidEntitySystem, and it looks like this:
package com.blogspot.javagamexyz.gamexyz.systems;

import com.artemis.systems.VoidEntitySystem;
import com.badlogic.gdx.Gdx;
import com.badlogic.gdx.graphics.OrthographicCamera;
import com.badlogic.gdx.graphics.g2d.SpriteBatch;
import com.badlogic.gdx.graphics.g2d.TextureAtlas;
import com.badlogic.gdx.graphics.g2d.TextureAtlas.AtlasRegion;
import com.badlogic.gdx.graphics.g2d.TextureRegion;
import com.badlogic.gdx.math.MathUtils;
import com.badlogic.gdx.utils.Array;
import com.blogspot.javagamexyz.gamexyz.maps.GameMap;
import com.blogspot.javagamexyz.gamexyz.utils.MapTools;

public class MapRenderSystem extends VoidEntitySystem {
 private SpriteBatch batch;
 private TextureAtlas atlas;
 private Array textures;
 private OrthographicCamera camera;
 private GameMap gameMap;
 
 public MapRenderSystem(OrthographicCamera camera, GameMap gameMap) {
  this.camera = camera;
  this.gameMap = gameMap;
 }
 
 @Override
 protected void initialize() {
  batch = new SpriteBatch();
  // Load the map tiles into an Array
  atlas = new TextureAtlas(Gdx.files.internal("textures/maptiles.atlas"),Gdx.files.internal("textures"));
  textures = atlas.findRegions(MapTools.name);
 }

 @Override
 protected boolean checkProcessing() {
  return true;
 }
 
 protected void processSystem() {
  
  TextureRegion reg;
  int x, y;

  
  // Get bottom left and top right coordinates of camera viewport and convert
  // into grid coordinates for the map
  int x0 = MathUtils.floor(camera.frustum.planePoints[0].x / (float)MapTools.col_multiple) - 1;
  int y0 = MathUtils.floor(camera.frustum.planePoints[0].y / (float)MapTools.row_multiple) - 1;
  int x1 = MathUtils.floor(camera.frustum.planePoints[2].x / (float)MapTools.col_multiple) + 2;
  int y1 = MathUtils.floor(camera.frustum.planePoints[2].y / (float)MapTools.row_multiple) + 1;
  
  // Restrict the grid coordinates to realistic values
  if (x0 % 2 == 1) x0 -= 1;
  if (x0 < 0) x0 = 0;
  if (x1 > gameMap.width) x1 = gameMap.width;
  if (y0 < 0) y0 = 0;
  if (y1 > gameMap.height) y1 = gameMap.height; 
  
  // Loop over everything in the window to draw.  Draw 2 columns at once
  for (int row = y0; row < y1; row++) {
   for (int col = x0; col < x1-1; col+=2) {
    x = col*MapTools.col_multiple;
    y = row*MapTools.row_multiple;
    reg = textures.get(gameMap.map[col][row]);
    batch.draw(reg, x, y, 0, 0, reg.getRegionWidth(), reg.getRegionHeight(), 1, 1, 0);
    x += MapTools.col_multiple;
    y += MapTools.row_multiple/2;
    reg = textures.get(gameMap.map[col+1][row]);
    batch.draw(reg, x, y, 0, 0, reg.getRegionWidth(), reg.getRegionHeight(), 1, 1, 0);
   }
  // Due to the map generation algorithm I use, there is guaranteed to be an odd number of columns.
  // Since I drew 2 columns at once above, the far right one won't be touched.  This bit is a little
  // silly because it draws the far right column, whether it is in the frustum or not.  Oh well...
   if (x1 >= gameMap.width) {
    int col = gameMap.width-1;
    x = col*MapTools.col_multiple;
    y = row*MapTools.row_multiple;
    reg = textures.get(gameMap.map[col][row]);
    batch.draw(reg, x, y, 0, 0, reg.getRegionWidth(), reg.getRegionHeight(), 1, 1, 0);
   }
   
  }
  
  // This line can draw a small image of the whole map
  //batch.draw(gameMap.texture,0,0);
 }
 
 @Override
 protected void begin() {
  batch.setProjectionMatrix(camera.combined);
  batch.begin();
 }
 
 @Override
 protected void end() {
  batch.end();
 }
}

In my main screen class, GameXYZ.java, I simply added a field for the GameMap:
public class GameXYZ implements Screen {

 public static int WINDOW_WIDTH = 1300;
 public static int WINDOW_HEIGHT = 720;
 
 OrthographicCamera camera;
 SpriteBatch batch;
 World world;
 Game game;
 
 public static GameMap gameMap;
 
 private SpriteRenderSystem spriteRenderSystem;
 private HudRenderSystem hudRenderSystem;
 private MapRenderSystem mapRenderSystem;

 public GameXYZ(Game game) {
  this.game = game;
  
     batch = new SpriteBatch();
     camera = new OrthographicCamera();
     gameMap  = new GameMap();
     world = new World();
.
.
.

Now whenever anything needs to see the GameMap, it can easily by checking GameXYZ.gameMap.  With these fairly important updates, I was able to make my new pathfinding system.  I make no guarantee that it is a smart way, not the way it will end up, but here goes.

Here is the code I ended up with from Kevin's tutorial.  I put it in a new package com.blogspot.javagamexyz.gamexyz.pathfinding:

AStarPathFinder.java
package com.blogspot.javagamexyz.gamexyz.pathfinding;

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

import com.badlogic.gdx.utils.Array;
import com.blogspot.javagamexyz.gamexyz.custom.Pair;
import com.blogspot.javagamexyz.gamexyz.utils.MapTools;


/**
 * A path finder implementation that uses the AStar heuristic based algorithm
 * to determine a path. 
 * 
 * @author Kevin Glass
 */
public class AStarPathFinder {
 /** The set of nodes that have been searched through */
 private Array<Node> closed = new Array<Node>();
 /** The set of nodes that we do not yet consider fully searched */
 private SortedList open = new SortedList();
 
 /** The map being searched */
 private int[][] map;
 /** The maximum depth of search we're willing to accept before giving up */
 private int maxSearchDistance;
 
 /** The complete set of nodes across the map */
 private Node[][] nodes;

 /**
  * Create a path finder 
  * 
  * @param heuristic The heuristic used to determine the search order of the map
  * @param map The map to be searched
  * @param maxSearchDistance The maximum depth we'll search before giving up
  * @param allowDiagMovement True if the search should try diaganol movement
  */
 public AStarPathFinder(int[][] map, int maxSearchDistance) {
  this.map = map;
  this.maxSearchDistance = maxSearchDistance;
  
  nodes = new Node[map.length][map[0].length];
  for (int x=0;x<map.length;x++) {
   for (int y=0;y<map[0].length;y++) {
    nodes[x][y] = new Node(x,y);
   }
  }
 }
 
 /**
  * @see PathFinder#findPath(Mover, int, int, int, int)
  */
 public Path findPath(int sx, int sy, int tx, int ty) {
  // easy first check, if the destination is blocked, we can't get there
//  if (map.blocked(mover, tx, ty)) {
//   return null;
//  }
  
  // initial state for A*. The closed group is empty. Only the starting
  // tile is in the open list and it's cost is zero, i.e. we're already there
  nodes[sx][sy].cost = 0;
  nodes[sx][sy].depth = 0;
  closed.clear();
  open.clear();
  open.add(nodes[sx][sy]);
  
  nodes[tx][ty].parent = null;
  
  // while we haven't found the goal and haven't exceeded our max search depth
  int maxDepth = 0;
  while ((maxDepth < maxSearchDistance) && (open.size() != 0)) {
   // pull out the first node in our open list, this is determined to 
   // be the most likely to be the next step based on our heuristic
   Node current = getFirstInOpen();
   if (current == nodes[tx][ty]) {
    break;
   }
   
   removeFromOpen(current);
   addToClosed(current);
   
   Array<Pair> neighbors = MapTools.getNeighbors(current.x, current.y);
   // search through all the neighbours of the current node evaluating
   // them as next steps
   for (Pair n : neighbors) {
    int xp = n.x;
    int yp = n.y;
    float nextStepCost = current.cost + getMovementCost(current.x,current.y,xp,yp);
    Node neighbor = nodes[xp][yp];
    if (nextStepCost < neighbor.cost) {
     if (inOpenList(neighbor)) removeFromOpen(neighbor);
     if (inClosedList(neighbor)) removeFromClosed(neighbor);
    }
    if (!inOpenList(neighbor) && !inClosedList(neighbor)) {
     neighbor.cost = nextStepCost;
     neighbor.heuristic = (float)MapTools.distance(xp,yp,tx,ty);
     maxDepth = Math.max(maxDepth, neighbor.setParent(current));
     addToOpen(neighbor);
    }
   }
  }

  // since we've got an empty open list or we've run out of search 
  // there was no path. Just return null
  if (nodes[tx][ty].parent == null) {
   return null;
  }
  
  // At this point we've definitely found a path so we can uses the parent
  // references of the nodes to find out way from the target location back
  // to the start recording the nodes on the way.
  Path path = new Path();
  Node target = nodes[tx][ty];
  while (target != nodes[sx][sy]) {
   path.prependStep(target.x, target.y);
   target = target.parent;
  }
  path.prependStep(sx,sy);
  
  // thats it, we have our path 
  return path;
 }

 /**
  * Get the first element from the open list. This is the next
  * one to be searched.
  * 
  * @return The first element in the open list
  */
 protected Node getFirstInOpen() {
  return (Node) open.first();
 }
 
 /**
  * Add a node to the open list
  * 
  * @param node The node to be added to the open list
  */
 protected void addToOpen(Node node) {
  open.add(node);
 }
 
 /**
  * Check if a node is in the open list
  * 
  * @param node The node to check for
  * @return True if the node given is in the open list
  */
 protected boolean inOpenList(Node node) {
  return open.contains(node);
 }
 
 /**
  * Remove a node from the open list
  * 
  * @param node The node to remove from the open list
  */
 protected void removeFromOpen(Node node) {
  open.remove(node);
 }
 
 /**
  * Add a node to the closed list
  * 
  * @param node The node to add to the closed list
  */
 protected void addToClosed(Node node) {
  closed.add(node);
 }
 
 /**
  * Check if the node supplied is in the closed list
  * 
  * @param node The node to search for
  * @return True if the node specified is in the closed list
  */
 protected boolean inClosedList(Node node) {
  return closed.contains(node,false);
 }
 
 /**
  * Remove a node from the closed list
  * 
  * @param node The node to remove from the closed list
  */
 protected void removeFromClosed(Node node) {
  closed.removeValue(node,false);
 }
 
 /**
  * Check if a given location is valid for the supplied mover
  * 
  * @param mover The mover that would hold a given location
  * @param sx The starting x coordinate
  * @param sy The starting y coordinate
  * @param x The x coordinate of the location to check
  * @param y The y coordinate of the location to check
  * @return True if the location is valid for the given mover
  */
 protected boolean isValidLocation(int sx, int sy, int x, int y) {
  boolean invalid = (x < 0) || (y < 0) || (x >= map.length) || (y >= map[0].length);
  
  if ((!invalid) && ((sx != x) || (sy != y))) {
   //invalid = map.blocked(mover, x, y);
  }
  
  return !invalid;
 }
 
 /**
  * Get the cost to move through a given location
  * 
  * @param mover The entity that is being moved
  * @param sx The x coordinate of the tile whose cost is being determined
  * @param sy The y coordiante of the tile whose cost is being determined
  * @param tx The x coordinate of the target location
  * @param ty The y coordinate of the target location
  * @return The cost of movement through the given tile
  */
 public float getMovementCost(int sx, int sy, int tx, int ty) {
  return (float)map[tx][ty];
  //return map.getCost(mover, sx, sy, tx, ty);
 }

 /**
  * Get the heuristic cost for the given location. This determines in which 
  * order the locations are processed.
  * 
  * @param mover The entity that is being moved
  * @param x The x coordinate of the tile whose cost is being determined
  * @param y The y coordiante of the tile whose cost is being determined
  * @param tx The x coordinate of the target location
  * @param ty The y coordinate of the target location
  * @return The heuristic cost assigned to the tile
  */
 public float getHeuristicCost(int x, int y, int tx, int ty) {
  return MapTools.distance(x, y, tx, ty);
  //return heuristic.getCost(map, mover, x, y, tx, ty);
 }
 
 /**
  * A simple sorted list
  *
  * @author kevin
  */
 private class SortedList {
  /** The list of elements */
  private ArrayList<Node> list = new ArrayList<Node>();
  
  /**
   * Retrieve the first element from the list
   *  
   * @return The first element from the list
   */
  public Object first() {
   return list.get(0);
  }
  
  /**
   * Empty the list
   */
  public void clear() {
   list.clear();
  }
  
  /**
   * Add an element to the list - causes sorting
   * 
   * @param o The element to add
   */
  public void add(Node o) {
   list.add(o);
   Collections.sort(list);
  }
  
  /**
   * Remove an element from the list
   * 
   * @param o The element to remove
   */
  public void remove(Object o) {
   list.remove(o);
  }
 
  /**
   * Get the number of elements in the list
   * 
   * @return The number of element in the list
    */
  public int size() {
   return list.size();
  }
  
  /**
   * Check if an element is in the list
   * 
   * @param o The element to search for
   * @return True if the element is in the list
   */
  public boolean contains(Object o) {
   return list.contains(o);
  }
 }
 
 /**
  * A single node in the search graph
  */
 private class Node implements Comparable {
  /** The x coordinate of the node */
  private int x;
  /** The y coordinate of the node */
  private int y;
  /** The path cost for this node */
  private float cost;
  /** The parent of this node, how we reached it in the search */
  private Node parent;
  /** The heuristic cost of this node */
  private float heuristic;
  /** The search depth of this node */
  private int depth;
  
  /**
   * Create a new node
   * 
   * @param x The x coordinate of the node
   * @param y The y coordinate of the node
   */
  public Node(int x, int y) {
   this.x = x;
   this.y = y;
  }
  
  /**
   * Set the parent of this node
   * 
   * @param parent The parent node which lead us to this node
   * @return The depth we have no reached in searching
   */
  public int setParent(Node parent) {
   depth = parent.depth + 1;
   this.parent = parent;
   
   return depth;
  }
  
  /**
   * @see Comparable#compareTo(Object)
   */
  public int compareTo(Object other) {
   Node o = (Node) other;
   
   float f = heuristic + cost;
   float of = o.heuristic + o.cost;
   
   if (f < of) {
    return -1;
   } else if (f > of) {
    return 1;
   } else {
    return 0;
   }
  }
  
  /**
   * @see Object#equals(Object)
   */
  public boolean equals(Object other) {
   if (other instanceof Node) {
    Node o = (Node) other;
    
    return (o.x == x) && (o.y == y);
   }
   
   return false;
  }
 }
}

One thing to note is that Kevin used ArrayList to hold the list of nodes, whereas I changed it to the libgdx class Array.  If you've built the SimpleApp bucket drop game you may remember them saying this:
The Array class is a libgdx utility class to be used instead of standard Java collections like ArrayList. The problem with the later is that they produce garbage in various ways. The Array class tries to minimize garbage as much as possible. Libgdx offers other garbage collector aware collections such as hashmaps or sets as well.
To do that, I had to add a .equals() method to the private class Node.

Note on lines 39-49 I load the map and initialize the node array in the constructor.  Next, the method findPath() is the main piece of the puzzle.  It starts commented out because I'm assuming my unit can move anywhere, but someday I'd like to include information about the mover.  Lines 62-68 initialize everything (again, you can read the details in Kevin's article).  Then we begin our search.

Line 75 gets the current node we will work on.  Line 83 gets an Array of coordinates of its neighbors using my getNeighbors() method.  It loops over those neighbors, checks them out, updates their cost if it has found a shorter path to get there, etc...  On line 89 it updates the cost of the path it's currently searching using getMovementCost().  If we look down at lines 221-224 we see I was just lazy and made each cell's cost equal to its value: deep ocean = 0, shallow water = 1, desert = 2, etc...  This means that for now, paths will really like to go through deep ocean, and will really hate going through mountains.  Clearly this will be something to update when the game becomes more involved.

After searching as long as it can/needs to, if it never finds a path it returns null.  Otherwise it returns our path!

On line 228 in the getHeuristicCost() method, I got rid of the Heuristic classes Kevin wrote.  As of now I can't imagine using another heuristic than the straight up distance method in MapTools, so I just use that.  Everything else is pretty much just helper methods, I didn't change too much from Kevin.  The code refers to a class called Path, which is a separate file which looks like this:

Path.java
package com.blogspot.javagamexyz.gamexyz.pathfinding;

import com.badlogic.gdx.utils.Array;

/**
 * A path determined by some path finding algorithm. A series of steps from
 * the starting location to the target location. This includes a step for the
 * initial location.
 * 
 * @author Kevin Glass
 */
public class Path {
 /** The list of steps building up this path */
 private Array<Step> steps = new Array<Step>();
 
 /**
  * Create an empty path
  */
 public Path() {
  
 }

 /**
  * Get the length of the path, i.e. the number of steps
  * 
  * @return The number of steps in this path
  */
 public int getLength() {
  return steps.size;
 }
 
 /**
  * Get the step at a given index in the path
  * 
  * @param index The index of the step to retrieve. Note this should
  * be >= 0 and < getLength();
  * @return The step information, the position on the map.
  */
 public Step getStep(int index) {
  return (Step) steps.get(index);
 }
 
 /**
  * Get the x coordinate for the step at the given index
  * 
  * @param index The index of the step whose x coordinate should be retrieved
  * @return The x coordinate at the step
  */
 public int getX(int index) {
  return getStep(index).x;
 }

 /**
  * Get the y coordinate for the step at the given index
  * 
  * @param index The index of the step whose y coordinate should be retrieved
  * @return The y coordinate at the step
  */
 public int getY(int index) {
  return getStep(index).y;
 }
 
 /**
  * Append a step to the path.  
  * 
  * @param x The x coordinate of the new step
  * @param y The y coordinate of the new step
  */
 public void appendStep(int x, int y) {
  steps.add(new Step(x,y));
 }

 /**
  * Prepend a step to the path.  
  * 
  * @param x The x coordinate of the new step
  * @param y The y coordinate of the new step
  */
 public void prependStep(int x, int y) {
  steps.add(new Step(x, y));
 }
 
 /**
  * Check if this path contains the given step
  * 
  * @param x The x coordinate of the step to check for
  * @param y The y coordinate of the step to check for
  * @return True if the path contains the given step
  */
 public boolean contains(int x, int y) {
  return steps.contains(new Step(x,y),false);
 }
 
 /**
  * A single step within the path
  * 
  * @author Kevin Glass
  */
 public class Step {
  /** The x coordinate at the given step */
  private int x;
  /** The y coordinate at the given step */
  private int y;
  
  /**
   * Create a new step
   * 
   * @param x The x coordinate of the new step
   * @param y The y coordinate of the new step
   */
  public Step(int x, int y) {
   this.x = x;
   this.y = y;
  }
  
  /**
   * Get the x coordinate of the new step
   * 
   * @return The x coodindate of the new step
   */
  public int getX() {
   return x;
  }

  /**
   * Get the y coordinate of the new step
   * 
   * @return The y coodindate of the new step
   */
  public int getY() {
   return y;
  }
  
  /**
   * @see Object#hashCode()
   */
  public int hashCode() {
   return x*y;
  }

  /**
   * @see Object#equals(Object)
   */
  public boolean equals(Object other) {
   if (other instanceof Step) {
    Step o = (Step) other;
    
    return (o.x == x) && (o.y == y);
   }
   
   return false;
  }
 }
}

The included private class Step makes me feel a little guilty because it's so similar to Node from AStarPathFinder, and also to my class Pair, and I don't want to have 3 classes where one will do, so maybe at some point I'll combine them into a single class.

To integrate it all into our code, I created a Component called Movement which just stores a Path:
package com.blogspot.javagamexyz.gamexyz.components;

import com.artemis.Component;
import com.blogspot.javagamexyz.gamexyz.GameXYZ;
import com.blogspot.javagamexyz.gamexyz.pathfinding.Path;

public class Movement extends Component {
 
 public Path path;
 
 public Movement(int x0, int y0, int tx, int ty) {
  path = GameXYZ.gameMap.pathFinder.findPath(x0, y0, tx, ty);
 }

}


Notice on line 12 where it gets the GameMap by referencing GameXYZ.gameMap, and then references its pathFinder to findPath().  If the pathfinder is unable to find a path, it will return Null.  Clearly this will be extended/changed in the future to include stuff like what kind of unit is moving, how far can it move, how well does it move over mountains, ocean, etc.

To test it out I wanted to make it so whenever you click a cell, it tries to come up with a path from my main dude to that cell.  The place to do this seemed like PlayerInputSystem touchDown() (or touchUp()), but there's a little problem.  Those listener methods can't actually see the Entity being processed, so they can't add a new Movement component to it.

Instead, I created a boolean flag: moving, along with a Pair moveTarget.  In the touchDown/Up() method I set the moving flag to be true, and set moveTarget to the cell that was clicked on.  Then, in the process() method I check to see if moving is true, and if so, I add the Movement component to the Entity (and set moving to false, so I'm not adding this same component every cycle).  Here's what it looks like:

PlayerInputSystem.java
package com.blogspot.javagamexyz.gamexyz.systems;

import com.artemis.Aspect;
import com.artemis.Entity;
import com.artemis.systems.EntityProcessingSystem;
import com.badlogic.gdx.Gdx;
import com.badlogic.gdx.InputProcessor;
import com.badlogic.gdx.graphics.OrthographicCamera;
import com.badlogic.gdx.math.Vector3;
import com.blogspot.javagamexyz.gamexyz.EntityFactory;
import com.blogspot.javagamexyz.gamexyz.components.Movement;
import com.blogspot.javagamexyz.gamexyz.components.Player;
import com.blogspot.javagamexyz.gamexyz.custom.Pair;
import com.blogspot.javagamexyz.gamexyz.utils.MapTools;

public class PlayerInputSystem extends EntityProcessingSystem implements InputProcessor {
 
 private OrthographicCamera camera;
 private Vector3 mouseVector;
 
 private boolean moving;
 private Pair moveTarget;
 
 @SuppressWarnings("unchecked")
 public PlayerInputSystem(OrthographicCamera camera) {
  super(Aspect.getAspectForAll(Player.class));
  this.camera=camera;
  moving=false;
  moveTarget = new Pair(0,0);
 }
 
 @Override
 protected void initialize() {
  Gdx.input.setInputProcessor(this);
 }

 @Override
 protected void process(Entity e) {
  mouseVector = new Vector3(Gdx.input.getX(),Gdx.input.getY(),0);
  camera.unproject(mouseVector);
  
  if (moving) {
   moving = false;
   Movement movement = new Movement(11,14,moveTarget.x,moveTarget.y);
   e.addComponent(movement);
   e.changedInWorld();
   
  }
 }

 @Override
 public boolean keyDown(int keycode) {
  return false;
 }

 @Override
 public boolean keyUp(int keycode) { 
  return false;
 }

 @Override
 public boolean keyTyped(char character) {
  return false;
 }

 @Override
 public boolean touchDown(int screenX, int screenY, int pointer, int button) {
  return false;
 }

 @Override
 public boolean touchUp(int screenX, int screenY, int pointer, int button) {
  // Get the hex cell being clicked
  Pair coords = MapTools.window2world(Gdx.input.getX(), Gdx.input.getY(), camera);
  moving = true;
  moveTarget = coords;
  if (button == 1) camera.zoom = 1;
  EntityFactory.createClick(world, coords.x, coords.y, 0.2f, 4f).addToWorld();
  return false;
 }

 @Override
 public boolean touchDragged(int screenX, int screenY, int pointer) {
  Vector3 delta = new Vector3(-camera.zoom*Gdx.input.getDeltaX(), camera.zoom*Gdx.input.getDeltaY(),0);
  camera.translate(delta);
  
  return false;
 }

 @Override
 public boolean mouseMoved(int screenX, int screenY) {
  return false;
 }

 @Override
 public boolean scrolled(int amount) {
  if ((camera.zoom > 0.2f || amount == 1) && (camera.zoom < 8 || amount == -1)) camera.zoom += amount*0.1;
  return false;
 }
 
}

Also in the PlayerInputSystem, note line 46.  Because I added a new Movement component, it overrides the old one, but this doesn't register until you call e.changedInWorld().

Now, this is cute... maybe it works, maybe it doesn't?  How would I know?  I click, and supposedly it makes a path?  Well, let's visualize that path.  I did a quick Google search and came up with this cute little feet.png
I put it in its own new folder, "textures/misc".  Then I made a new RenderingSystem just to draw the path, called PathRenderingSystem:
package com.blogspot.javagamexyz.gamexyz.systems;

import com.artemis.Aspect;
import com.artemis.ComponentMapper;
import com.artemis.Entity;
import com.artemis.EntitySystem;
import com.artemis.annotations.Mapper;
import com.artemis.utils.ImmutableBag;
import com.badlogic.gdx.Gdx;
import com.badlogic.gdx.graphics.OrthographicCamera;
import com.badlogic.gdx.graphics.Texture;
import com.badlogic.gdx.graphics.g2d.SpriteBatch;
import com.blogspot.javagamexyz.gamexyz.components.Movement;
import com.blogspot.javagamexyz.gamexyz.custom.FloatPair;
import com.blogspot.javagamexyz.gamexyz.utils.MapTools;

public class PathRenderingSystem extends EntitySystem {
 @Mapper ComponentMapper<Movement> mm;
 
 private OrthographicCamera camera;
 private SpriteBatch batch;
 private Texture feet;
 
 @SuppressWarnings("unchecked")
 public PathRenderingSystem(OrthographicCamera camera) {
  super(Aspect.getAspectForAll(Movement.class));
  this.camera = camera;
 }

 @Override
 protected void initialize() {
  batch = new SpriteBatch();
  feet = new Texture(Gdx.files.internal("textures/misc/feet.png"));
 }
 
 @Override
 protected boolean checkProcessing() {
  // TODO Auto-generated method stub
  return true;
 }

 @Override
 protected void processEntities(ImmutableBag<Entity> entities) {
  for (int i=0; i<entities.size(); i++) {
   process(entities.get(i));
  }
 }
 
 @Override
 protected void begin() {
  batch.setProjectionMatrix(camera.combined);
  batch.begin();
 }
 
 private void process(Entity e) {
  Movement move = mm.get(e);
  if (move.path != null) {
   for (int i=0; i<move.path.getLength(); i++) {
    FloatPair coords = MapTools.world2window(move.path.getX(i), move.path.getY(i));
    batch.draw(feet, coords.x-feet.getWidth()/2, coords.y-feet.getHeight()/2);
   }
  }
 }
 
 @Override
 protected void end() {
  batch.end();
 }
}

On line 26 I grab all entities with the "Movement" component.  On line 33 I just go ahead and hardcode loading feet.png - every path cell will just be rendered with that image, so I don't have to get fancy.

For processing, first on line 57 I make sure that the path isn't null.  On lines 58-61 I loop over the path, getting all the steps, change those to coordinates for where to draw the feet in window space, then draw them.  That's just enough to actually see the path it's finding.

Pretty awesome!  Next I plan on working on the user interface a little bit.  For instance, I want to be able to click on a character to select them, then click on a map tile to move them.  I also want to be able to scroll the camera without counting as a movement click.  I'll probably also add some code to literally move the entities you click to their new location.  This part will have me think a lot more about how I want the game to feel.  I'll be shooting towards a Final Fantasy Tactics, Battle for Wesnoth, Fire Emblem -esque SRPG experience.  Because this is written with libgdx it has the potential to be deployed to desktop, HTML5, or Android, which may be too much to think about right now.  I'll probably start just focusing on desktop, but we'll see!

You have gained 100 XP.  Progress to level 3: 450/600

1 comment: