Saturday, March 16, 2013

User Input and Screens (Level 2)

Up to this point, I've tried to implement what I considered "basic tricky" systems like animation and pathfinding.  I still have some work to do on the animation system (see some of the comments on that post), but I feel the fundamental idea is sound enough to continue until I really need to address it.

Clearly, what we have now does NOT constitute a game, but it's starting to take shape.  For this update, I wanted to add more sophisticated controls, so that the player could select one of the little dudes and tell him where to move, and select other dudes and have them decide where to move.  The idea seemed simple, but really got me thinking heavily about how to keep the code modular and managable.

In this update, we will see that done, but I had to redesign the game structure down to its core to make it happen in a way that didn't seem overly forced, and I'm really happy with how it has turned out.

First, in case you haven't read it, Andrew Steigert has a wonderful set of libgdx tutorials where he walks through creating a simple game (not unlike Spaceship Warrior) called Tyrion.  One of the main focuses of his tutorials is using Screens to manage your code.  The idea is that most games have numerous screens, each of which behave quite differently.  For instance, we may end up with a:
  • Logo splash screen
  • Main menu screen
  • Load screen
  • Overworld screen
  • Battle map screen
  • Game menu screen
    • Inventory
    • Character stats
    • Party stats
  • And who knows what the heck else?
Each of these screens out to run very different code: for instance the touchDrag() we have implemented wouldn't really make sense on a logo splash screen, or main menu screen.  You really don't want your users dragging those screens around.  Similarly, the idea of clicking on a cell and selecting an entity doesn't make sense in most contexts.  On the main menu, we really DON'T want to render the GameMap.

One of the cool things about screens is that each one can contain its own code.  For us, this could be really helpful in deciding which rendering systems to process, and setting custom controllers for each screen.  As of now, our Launcher.java file extends Game, and our GameXYZ.java implements Screen.  libgdx gave us these classes so that a Game can run, and delegate to different screens as needed, but we're not using it that way.

The first major change I made was to make Launcher.java just a regular class, and no longer extend Game.  Instead, I made GameXYZ.java extend Game.  The idea here is that GameXYZ.java will now be able to delegate to different screens.

To clarify the difference between Game and Screen, consider the methods that are part of each:
Game
  • create()
  • setScreen()
  • getScreen()
  • render(), resize(), show(), hide(), pause(), etc...
Screen
  • render(), resize(), show(), hide(), pause(), etc...
When Game "render()"s, it checks to see if it currently has a screen, and if so, calls screen.render().  In essence, Game is really just a manager for Screens.  Each screen ought to have a reference to the Game controlling it so that they can call game.setScreen(some_other_screen) - that is, so you can change screens.

I created an Abstract class called AbstractScreen.java which holds some things that I expect to be common to all the screens I use, such as an OrthographicCamera, a reference to the Artemis World (so the screens can interact with Entities and process systems), and a reference to GameXYZ.  As of now, I just implemented a single Screen called OverworldScreen which extends AbstractScreen.  OverworldScreen is more or less a rough copy of the old GameXYZ, because I want it to represent the main Screen I have as of yet.  There are a few differences we'll get to.

Here is the updated and new code for all this:
package com.blogspot.javagamexyz.gamexyz;

import com.badlogic.gdx.backends.lwjgl.LwjglApplication;
import com.badlogic.gdx.backends.lwjgl.LwjglApplicationConfiguration;
import com.blogspot.javagamexyz.gamexyz.utils.ImagePacker;

public class Launcher {
 
 private static final int WIDTH = 1300;
 private static final int HEIGHT = 720;
 
 public static void main(String[] args) {
  ImagePacker.run();
  
  LwjglApplicationConfiguration cfg = new LwjglApplicationConfiguration();
  cfg.width=WIDTH;
  cfg.height=HEIGHT;
  cfg.useGL20=true;
  cfg.title = "GameXYZ";
  cfg.vSyncEnabled = false;
  cfg.resizable=false;
  new LwjglApplication(new GameXYZ(WIDTH,HEIGHT), cfg);
 }
}

Two major things to discuss here.  First, Launcher no longer extends Game - that's because I'm not using Laucher to control my screens, I'm using GameXYZ to do that.  Consequenty, when I declare a new LwjglApplication I don't pass it "this", I pass it a reference to GameXYZ.java (more like the SimpleApp did).

Second, as a major improvement, I am storing the width and height in the Launcher.java file now.  To let my GameXYZ see this, I have to pass it as an argument, but this is no problem!  This is helpful because if we make an HTML5 or Android launcher, we will want to set their width and height separately from one another.

package com.blogspot.javagamexyz.gamexyz;

import com.artemis.World;
import com.badlogic.gdx.Game;
import com.badlogic.gdx.graphics.g2d.SpriteBatch;
import com.blogspot.javagamexyz.gamexyz.screens.OverworldScreen;
import com.blogspot.javagamexyz.gamexyz.systems.ColorAnimationSystem;
import com.blogspot.javagamexyz.gamexyz.systems.ExpiringSystem;
import com.blogspot.javagamexyz.gamexyz.systems.ScaleAnimationSystem;
import com.blogspot.javagamexyz.gamexyz.systems.SpriteAnimationSystem;

public class GameXYZ extends Game {

 public int WINDOW_WIDTH;
 public int WINDOW_HEIGHT;
 
 public World world;
 private SpriteBatch batch;

 public GameXYZ(int width, int height) {
  WINDOW_WIDTH = width;
  WINDOW_HEIGHT = height;
 }
 
 public void create() {
  
     world = new World();
     batch = new SpriteBatch();
     
     world.setSystem(new SpriteAnimationSystem());
     world.setSystem(new ScaleAnimationSystem());
     world.setSystem(new ExpiringSystem());
     world.setSystem(new ColorAnimationSystem());
     world.initialize(); 
     
     setScreen(new OverworldScreen(this, batch, world));
 }
}

Here we can see we cut out a lot of code.  All we have is a constructor, with which we set the width and height, and a method called create(), which is called automatically upon creation.  I'm no expert, and I don't really understand the difference between that method and the constructor.  But I do know that if you try to jam it all into the constructor, it fails.  So I keep it separted and it works like a charm!

Notice I've set the basic processing systems, but none of the rendering systems.  I'm not sure if I want to stick with it this way, but right now each screen will be responsible for its own rendering systems.  One reason for this is that everything used to statically reference GameXYZ.gameMap, but that no longer exists.  Primarily because different screens may want different maps.

Note however that GameXYZ has its own SpriteBatch, even though its not doing any of the rendering.  All the best practices seem to indicate that it's best to have only one instance of SpriteBatch in your whole game because it's a resource hog.  All rendering systems that need it will have it passed to them.

Line 36 calls the setScreen method, which for now just goes to OverworldScreen.  Notice I pass OverworldScreen a reference to this instance of GameXYZ, a reference to the SpriteBatch, and a reference to the World.

All screens I paln on implementing will extend AbstractScreen.java

package com.blogspot.javagamexyz.gamexyz.screens;

import com.artemis.World;
import com.badlogic.gdx.Gdx;
import com.badlogic.gdx.Screen;
import com.badlogic.gdx.graphics.GL10;
import com.badlogic.gdx.graphics.OrthographicCamera;
import com.blogspot.javagamexyz.gamexyz.GameXYZ;

public abstract class AbstractScreen implements Screen {
 
 protected final GameXYZ game;
 protected final World world;
 protected final OrthographicCamera camera;
 
 public AbstractScreen(GameXYZ game, World world) {
  this.game = game;
  this.world = world;
  camera = new OrthographicCamera();
 }
 
 @Override
 public void render(float delta) {
  Gdx.gl.glClearColor(0,0,0,1);
     Gdx.gl.glClear(GL10.GL_COLOR_BUFFER_BIT);
     
     camera.update();
     
     world.setDelta(delta);
     world.process();
 }
 
 @Override
 public void show() {
 }
 
 @Override
 public void hide() {
 }
 
 @Override
 public void pause() {
 }
 
 @Override
 public void resume() {
 }
 
 @Override
 public void resize(int width, int height) {
     game.WINDOW_WIDTH = width;
     game.WINDOW_HEIGHT = height;
     
     camera.setToOrtho(false, width,height);
 }
 
 @Override
 public void dispose() {
 }
}

Notice it has fields to hold the Game and World passed into it, but it doesn't hold the SpriteBatch.  Each screen will also have its own OrthographicCamera (you don't erally want them all sharing the same camera, or zooming out in one screen could influence the way another screen renders).

The render() method calls some of the basic methods that GameXYZ.java used to.  These are things that I could see being generally useful, though I may change my mind about that later and lose the world.process().  Resize changes WINDOW_WIDTH and WINDOW_HEIGHT back in the Game, so all screens should see the updated value.

package com.blogspot.javagamexyz.gamexyz.screens;

import com.artemis.World;
import com.badlogic.gdx.Gdx;
import com.badlogic.gdx.graphics.OrthographicCamera;
import com.badlogic.gdx.graphics.g2d.SpriteBatch;
import com.badlogic.gdx.math.MathUtils;
import com.blogspot.javagamexyz.gamexyz.EntityFactory;
import com.blogspot.javagamexyz.gamexyz.GameXYZ;
import com.blogspot.javagamexyz.gamexyz.input.OverworldControlSystem;
import com.blogspot.javagamexyz.gamexyz.maps.GameMap;
import com.blogspot.javagamexyz.gamexyz.maps.MapTools;
import com.blogspot.javagamexyz.gamexyz.systems.HudRenderSystem;
import com.blogspot.javagamexyz.gamexyz.systems.MapRenderSystem;
import com.blogspot.javagamexyz.gamexyz.systems.PathRenderingSystem;
import com.blogspot.javagamexyz.gamexyz.systems.SpriteRenderSystem;

public class OverworldScreen extends AbstractScreen {
 
 public static GameMap gameMap;
 private OrthographicCamera hudCam;
 
 
 public SpriteRenderSystem spriteRenderSystem;
 public HudRenderSystem hudRenderSystem;
 public MapRenderSystem mapRenderSystem;
 public PathRenderingSystem pathRenderSystem;
 
 private OverworldControlSystem overworldControlSystem;
 
 public OverworldScreen(GameXYZ game, SpriteBatch batch, World world) {
  super(game,world);

     gameMap  = new GameMap();
     hudCam = new OrthographicCamera();
     
     spriteRenderSystem = world.setSystem(new SpriteRenderSystem(camera,batch), true);
     mapRenderSystem = world.setSystem(new MapRenderSystem(camera,batch,gameMap),true);
     hudRenderSystem = world.setSystem(new HudRenderSystem(hudCam, batch),true);
     pathRenderSystem = world.setSystem(new PathRenderingSystem(camera,batch),true);
     
     overworldControlSystem = world.setSystem(new OverworldControlSystem(camera,world,gameMap,game));
     Gdx.input.setInputProcessor(overworldControlSystem);
     
     world.initialize();
     
     int x, y;
     for (int i=0; i<100; i++) {
      do {
       x = MathUtils.random(MapTools.width()-1);
       y = MathUtils.random(MapTools.height()-1);
      } while (gameMap.cellOccupied(x, y));
      EntityFactory.createNPC(world,x,y,gameMap).addToWorld();
     }
 }
 
 @Override
 public void render(float delta) {
  super.render(delta);
  
  mapRenderSystem.process();
  pathRenderSystem.process();
  spriteRenderSystem.process();
  hudRenderSystem.process();
 }

 @Override
 public void show() {
  // TODO Auto-generated method stub
  
 }
 
 @Override
 public void resize(int width, int height) {
  super.resize(width, height);
  hudCam.setToOrtho(false, width, height);
 }

 @Override
 public void hide() {
  // TODO Auto-generated method stub
  
 }

 @Override
 public void pause() {
  // TODO Auto-generated method stub
  
 }

 @Override
 public void resume() {
  // TODO Auto-generated method stub
  
 }

 @Override
 public void dispose() {
  // TODO Auto-generated method stub
  game.world.deleteSystem(hudRenderSystem);
  game.world.deleteSystem(mapRenderSystem);
  game.world.deleteSystem(pathRenderSystem);
  game.world.deleteSystem(spriteRenderSystem); 
 }
}

This has a GameMap which is initialized in the constructor.  That means that as long as we have THIS screen running around, we'll have that same GameMap.  It also has a "hudCam" in addition to the camera defined in AbstractScreen.  Because all RenderingSystems now have to share the same SpriteBatch, you get problems if in one rendering system you call batch.setProjectionMatrix(camera.combined), but you don't want to do that for the next rendering system in line.  Once it's set for the batch once, it holds for the rest.  This runs in to that old problem of zooming out from out hud, and scrolling it away off the screen.  This would be silly, so we need a camera which WON'T be changed so the hud can always render from the perspective of that camera.

All of the RenderingSystems live here, and are initialized in the constructor.  Notice they are all given the camera and SpriteBatch we want them to use.  Furthermore, mapRenderSystem is given a reference to the gameMap (remember, it can no longer statically get GameXYZ.gameMap).

We'll skip lines 42-43 for now, but below that we just add a bunch of characters to the world.  createNPC() is a lot like createWarrior() from before.  Remember, I want to be able to SELECT the character I'm controlling at that moment, so I don't want to automatically assign ONE character to be the player.  The render() method isn't too shocking - first we call render() from AbstractScreen, then draw each of our systems in turn.  resize() not only calls super.resize(), but also deals with the hudCam.

Now for lines 42-43.  Each Screen can be controlled in its own unique way, so I created a class called OverworldControlSystem.  It gets a camera, because it needs to be able to zoom, etc..., it gets a copy of the World because it needs to be able to influence entities, the GameMap because it also had to be able to read what was going on in that.  It also has a reference to GameXYZ so that this control system has the power to change screens.

package com.blogspot.javagamexyz.gamexyz.input;

import com.artemis.Aspect;
import com.artemis.ComponentMapper;
import com.artemis.Entity;
import com.artemis.World;
import com.artemis.annotations.Mapper;
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.Vector2;
import com.blogspot.javagamexyz.gamexyz.EntityFactory;
import com.blogspot.javagamexyz.gamexyz.GameXYZ;
import com.blogspot.javagamexyz.gamexyz.components.MapPosition;
import com.blogspot.javagamexyz.gamexyz.components.Movement;
import com.blogspot.javagamexyz.gamexyz.components.PlayerSelected;
import com.blogspot.javagamexyz.gamexyz.custom.Pair;
import com.blogspot.javagamexyz.gamexyz.maps.GameMap;
import com.blogspot.javagamexyz.gamexyz.maps.MapTools;

public class OverworldControlSystem extends EntityProcessingSystem implements InputProcessor {
 @Mapper ComponentMapper<MapPosition> pm;
 
 private OrthographicCamera camera;
 private World world;
 private GameMap gameMap;
 
 // We need a copy of the screen implementing this controller (which has a copy of
 // the Game delegating to it) so we can change screens based on users making selections
 private GameXYZ game;
 
 private int selectedEntity;
 private Pair pathTarget;
 private State state, lastState;
 

 @SuppressWarnings("unchecked")
 public OverworldControlSystem(OrthographicCamera camera, World world, GameMap gameMap, GameXYZ game) {
  super(Aspect.getAspectForAll(PlayerSelected.class, MapPosition.class));
  
  this.camera = camera;
  this.world = world;
  this.gameMap = gameMap;
  this.game = game;
  
  state = State.DEFAULT;
  lastState = State.DEFAULT;
  selectedEntity = -1;
 }
 
 @Override
 protected void process(Entity e) {
  
  // We should only get here if the player has selected an entity and asked for a path
  if (state == State.FIND_PATH) {
   state = State.ENTITY_SELECTED;
   lastState = State.FIND_PATH;
   
   // Get the entity's position
   MapPosition pos = pm.getSafe(e);
   
   // Add a Movement component to the entity
   Movement movement = new Movement(pos.x,pos.y,pathTarget.x,pathTarget.y, gameMap);
   e.addComponent(movement);
   e.changedInWorld();
  }
  
 }

 @Override
 public boolean keyDown(int keycode) {
  // TODO Auto-generated method stub
  return false;
 }

 @Override
 public boolean keyUp(int keycode) {
  // TODO Auto-generated method stub
  return false;
 }

 @Override
 public boolean keyTyped(char character) {
  // TODO Auto-generated method stub
  return false;
 }

 @Override
 public boolean touchDown(int screenX, int screenY, int pointer, int button) {
  // TODO Auto-generated method stub
  return false;
 }

 @Override
 public boolean touchUp(int screenX, int screenY, int pointer, int button) {
  
  // Are they releasing from dragging?
  if (state == State.DRAGGING) {
   state = lastState;
   lastState = State.DRAGGING;
   return true;
  }
  
  // Otherwise, get the coordinates they clicked on
  Pair coords = MapTools.window2world(Gdx.input.getX(), Gdx.input.getY(), camera);
   
  // Check the entityID of the cell they click on
  int entityId = gameMap.getEntityAt(coords.x, coords.y);
  
  // If it's an actual entity (not empty) then "select" it (unless it's already selected)  
  if ((entityId > -1) && (entityId != selectedEntity)){
   
   // If there was previously another entity selected, "deselect" it
   if (selectedEntity > -1) {
    Entity old = world.getEntity(selectedEntity);
    old.removeComponent(PlayerSelected.class);
    old.removeComponent(Movement.class);
    old.changedInWorld();
   }
   
   // Now select the current entity
   selectedEntity = entityId;
   Entity e = world.getEntity(selectedEntity);
   e.addComponent(new PlayerSelected());
   e.changedInWorld();
   System.out.println(e.getId());
   
   EntityFactory.createClick(world, coords.x, coords.y, 0.1f, 4f).addToWorld();
   
   lastState = state;
   state = State.ENTITY_SELECTED;
   
   return true;
  }
  
  // Are they clicking to find a new path?
  else if (state == State.ENTITY_SELECTED) {
   lastState = state;
   state = State.FIND_PATH;
   pathTarget = coords;
   return true;
  }
  
  return false;
 }

 @Override
 public boolean touchDragged(int screenX, int screenY, int pointer) {
  // If it hadn't been dragging, set the current state to dragging 
  if (state != State.DRAGGING) {
   lastState = state;
   state = State.DRAGGING;
  }
  Vector2 delta = new Vector2(-camera.zoom*Gdx.input.getDeltaX(), camera.zoom*Gdx.input.getDeltaY());
  camera.translate(delta);
  
  return true;
 }

 @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 true;
 }
 
 private enum State {
  DEFAULT,
  ENTITY_SELECTED,
  DRAGGING,
  FIND_PATH,
 };
}


This should somewhat resemble our old "PlayerInputSystem", but there are some new, neat changes.  First, I don't store information about what the player has done as booleans (boolean moving, boolean dragging, etc...) instead I defined an enum called State (lines 172-177).  The idea is that the control system will run (roughly) as a Finite State Machine, where the state dictates what it can do.

For now I've thought of a tentative list of states we may care about, starting in default (just show stuff, leave it open for most anything).  Here's how it works:
If you are in DEFAULT you can
  • Select an NPC by clicking on one (ENTITY_SELECTED)
  • Drag the screen by click dragging (DRAGGING)
If you are in DRAGGING you can
  • Return to the previous state you had been in by letting up on the button (lastState)
If you are in ENTITY_SELECTED you can
  • Find a path from that entity to any cell by clicking on it (FIND_PATH)
  • Select another entity by clicking on it (ENTITY_SELECTED)
  • Drag the screen by click draggin (DRAGGING)
If you are in FIND_PATH
  • process() will automatically find the path (if possible) and return you to just (ENTITY_SELECTED)
   
I imagine expanding this to include more things such as action menus (Move, Attack, Ability, etc...)

The OverworldControlSystem constantly keeps track of which (if any) entity is selected, which cell you have clicked on (for pathfinding), the current state, and the previous state.

On line 109 it asks the GameMap for the entity ID of what is in a particular cell.  If it's nothing, it gets -1.  If there's something there, it gets the ID.  Whatever that ID is, it adds a component called PlayerSelected to that entity (I just renamed the old "Player" component to be more appropriate).  If there had previously been a selected Entity, it removes PlayerSelected status from it first (and also any path it may have been looking at).

I updated GameMap to hold a 2D integer array to hold the ID of entities, retrievable by cell coordinates using getEntityAt(x,y).  I fear that this will be a pain in the but to maintain, but for now (since nothing is really moving) it's simple enough and works.  To keep it up to date, I pass the GameMap into EntityFactory.createNPC() so that it can store the ID into the correct cell of the array upon creation.  When things start moving, I'll have to be careful to force that to update the array.

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;

public class GameMap {
 public int[][] map;
 public int[][] entityLocations;
 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;
  
  entityLocations = new int[width][height];
  
  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);
    
    entityLocations[i][j] = -1;
    
   }
  }
  
  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);
 }
 
 public int getEntityAt(int x, int y) {
  return entityLocations[x][y];
 }
 
 public boolean cellOccupied(int x, int y) {
  return (entityLocations[x][y] > -1);
 }
 
}


Other than that the changes were fairly minor.  On line 129 of OverworldControlSystem I add a cute click effect for when players select a new character to control.  One thing frustrating me about project organization is that OverworldControlSystem does extend EntityProcessingSystem, so it is an Artemis system.  But I thought it best to put it in a separate package, com.blogspot.javagamexyz.gamexyz.input.

That's a heck of an update!  I went ahead and posted the full code to the repository, including images.  Check it out using SVN from https://code.google.com/p/javagamexyz/source/browse/#svn%2Ftags%2F2013-03-16, or just browse the code.

You have gained 150 XP.  Progress to Level 3: 600/600
DING!  You have advanced to Level 3, congratulations!
As a Level 3 PC, you have mastered
  • Using animations in a libgdx/Artemis framework
  • Creating, handling, and drawing 2D tile based maps, even with Hex cells.  You can deal with helper functions like getNeighbors() and distance()
You have also gained some proficiency at
  • Basic pathfinding using the A* algorithm
  • Managing Screens using Game to split your code up into manageable chunks
Your game is now on the path to becoming something that can actually be played!



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

Friday, March 8, 2013

Google Code Repository

I have opened up a Google Code repository where you can go and checkout the source code as we work through it. Check it out at http://code.google.com/p/javagamexyz/.

The code is licensed under the New BSD (BSD 3-clause) which more or less says you may do whatever you want with the code, but I won't assume any liability for anything about it.  The code is hosted using Subversion, for which you can download an eclipse plugin.

To check out a particular version of the code
  1. Install the plugin
  2. In Eclipse say File->Import
  3. Find the option "Project from SVN" and click it
  4. Say "Create a new repository location"
  5. Under URL, say "http://javagamexyz.googlecode.com/svn/tags/2013-03-08/GameXYZ"
    • Or replace the date with whichever version you want
  6. Go with the Head Revision (I don't really know what this means...)
  7. Check out as a project configured using the New Project Wizard
  8. Give the project whatever name
  9. Do the same for /GameXYZ-desktop
  10. You still have to put the .jars in the buildpath and set project dependencies, but then it should work!

To check out the most recent
Use this URL: "http://javagamexyz.googlecode.com/svn/trunk/GameXYZ"

As time goes on, that most recent version may become outdated.  When that happens, right click on the project, go to Team->Update.

There are a few changes to this code from my last blog update that need to be mentioned:
  • MapTools can calculate the "raw" distance between two cells, that is, how many cells they are apart from each other.  This was confusing to do for a hex map, and probably isn't very optimal, but it works!
  • The resource "images" file structure is a little updated
  • I created my own sprite character animation that fits well into a grid cell (32x32 image) - it was fun to do, and I may post a tutorial on how I did it later (note - I suck as an artist, so even if you have no artistic talent you may be able to do something like these)
  • n, wmult, and hmult have been moved to from MidpointDisplacement to HexMapGenerator.  I will probably someday move smoothness and all the thresholds there as well
  • The GameMap component now has a Texture which builds itself upon instantiation, holding an image of the overall map where each cell takes up a single pixel.  This was done using Pixmap from libgdx.  The code is pretty straightforward except for using Pixmap.Format.RBGA8888 - I'm not totally sure what this format means and why I had to use it.  But when I used the other formats, it looked terrible.  My getColor() method hardcodes which color to use for each terrain type.  MapRenderSystem has a line commented out which draws this map at (0,0).
  • I added a FloatPair class, so I can have a Pair not just with ints.  I wanted to redo Pair as a generic class (i.e. Pair<Class1,Class2>) but when I did that  Java wouldn't let me make an array of Pair<Integer,Integer>, which I use to return a list coordinates of neighbors.  It's supposedly possible to do it by using raw types, and not telling the compiler that they are supposed to be Integers, but that seems dirty and may not be available forever.  So I just made a separate class for floats.
  • MapTools has a method which window2world() can figure out what hex cell you're clicking on, depending on where the cursor is in the window.  This replaced the hardcode in PlayerInputSystem which did the same thing.  I want to implement the reverse, world2window(), but haven't gotten around to it yet.
Here's a screenshot of its current incarnation:

You have gained 50 XP.  Progress to Level 3: 350/600

Wednesday, March 6, 2013

Terrain Generation

Okay, time to talk about the random terrain generation algorithm, so that you too can have some cool maps!

A little research brought me to two common random terrain algorithms, Perlin Noise and Diamond-Square.  I liked the look of Diamond-Square a little more, and it seemed easier to implement than Perlin Noise anyway.  My guiding light in this part was an article from Gameprogrammer.com on fractal terrain generation.  It breaks the algorithm down into tiny bitsized steps, and is awesome!

It does, however, have some unfortunate limitations.  First and foremost, it can only build maps which have dimenions 2^n+1.  I don't like the idea of going from n=9 (513 cells) to n=10 (1025 cells) with no middle ground!  I didn't like it one bit.

Also, and perhaps even worse, while setting n to a larger number creates a larger map, it's not really that it builds a larger world... it just builds the same world at a finer and finer scale.  To get an idea of what I mean, consider a few iterations of the diamond square algorithm from the gameprogrammer article:
You don't really get any new features, you just get refinements on features already there.  Thus, whereas a grid cell in the top image may cover 10 square miles, a grid cell in the bottom image may only by 10 feet by 10 feet.  In game, then, you will have to walk over a LOT of tiles to cover much distance, which kind of sucks.  There is room for finer and finer details, but ultimately your map is limited to the features the first few steps came up with.  Especially when you are transforming it to a 2D map anyway, you will lost most of the fine details later iterations created, and you just get a HUGE boring map.

This really limits the diversity of maps you can generate, and just won't do.

To get around this, I modified the initialization step a bit.  Whereas in the original algorithm you just initialize the four corners, either all to the same value (boring) or to some random value (a little less boring), I modified it to allow you to initialize an arbitrary sized grid.
The standard algorithm lets you initialize 4 corners, then works its way inward.

Modified algorithm lets you initialize a grid, and works its way in through each of the regions, which all share borders and can see into their neighbors when appropriate.


Now there is a tradeoff here!  If you initialize too many points in your gird, you end up with maps which don't have much coherent structure:

The tectonic forces that gave rise to this geography were a little drunk at the time...
If you have too few grid points, and rely on making decent size maps by increasing n, you get too boring of maps
I know it's more realistic... but WHYYYYY do I have to cross 12,000 tiles just to make it across the mountain range on the bottom right?
You need to tweak things to strike a balance you like.  Many things about this algorithm are customizable.
Boy, doesn't that look fun!  I can't wait to spend my money to support the people who made this game!
Here's the rough idea of how to use the Diamond Square (also known as midpoint displacement) algorithm to make our 2D map:
  • Generate the fractal terrain (note, this is really a 3D terrain being created)
  • Normalize all the heights to lie between 0 and 1 (inclusive)
  • Have a set of threshold parameters such that all points below the DeepWaterThreshold become deep water, otherwise if they are between that threshold and the ShalowWaterThreshold, they become shallow water, etc...
  • Smile at your pretty map
It's not the best, there are lots of ways it could be improved.  For instance, instead of having strict thresholds, perhaps the height generated by the algorithm sets the probability that certain terrains might be picked.  That way, instead of going from solid grassland to solid darker green grassland to solid forest, there could be smoother transitions and more engaging maps.  But this is a start.

Without further adieu, here is my MidpointDisplacement.java (you could call it DiamondSquare.java):
package com.gamexyz.utils;

import com.badlogic.gdx.math.MathUtils;

public class MidpointDisplacement {
 public float deepWaterThreshold, 
     shallowWaterThreshold,
     desertThreshold,
     plainsThreshold,
     grasslandThreshold,
     forestThreshold,
     hillsThreshold,
     mountainsThreshold;

 public int n;
 public int wmult, hmult;
 
 public float smoothness;

 public MidpointDisplacement() {
  
  // the thresholds which determine cutoffs for different terrain types
  deepWaterThreshold = 0.5f;
  shallowWaterThreshold = 0.55f;
  desertThreshold = 0.58f;
  plainsThreshold = 0.62f;
  grasslandThreshold = 0.7f;
  forestThreshold = 0.8f;
  hillsThreshold = 0.88f;
  mountainsThreshold = 0.95f;
  
  // n partly controls the size of the map, but mostly controls the level of detail available
  n = 7;
  
  // wmult and hmult are the width and height multipliers.  They set how separate regions there are
  wmult=6;
  hmult=4;
  
  // Smoothness controls how smooth the resultant terain is.  Higher = more smooth
  smoothness = 2f;
 }
 
 public int[][] getMap() {
  
  // get the dimensions of the map
  int power = MyMath.pow(2,n);
  int width = wmult*power + 1;
  int height = hmult*power + 1;
  
  // initialize arrays to hold values 
  float[][] map = new float[width][height];
  int[][] returnMap = new int[width][height];
  
  
  int step = power/2;
  float sum;
  int count;
  
  // h determines the fineness of the scale it is working on.  After every step, h
  // is decreased by a factor of "smoothness"
  float h = 1;
  
  // Initialize the grid points
  for (int i=0; i<width; i+=2*step) {
   for (int j=0; j<height; j+=2*step) {
    map[i][j] = MathUtils.random(2*h);
   }
  }

  // Do the rest of the magic
  while (step > 0) {   
   // Diamond step
   for (int x = step; x < width; x+=2*step) {
    for (int y = step; y < height; y+=2*step) {
     sum = map[x-step][y-step] + //down-left
        map[x-step][y+step] + //up-left
        map[x+step][y-step] + //down-right
        map[x+step][y+step];  //up-right
     map[x][y] = sum/4 + MathUtils.random(-h,h);
    }
   }
   
   // Square step
   for (int x = 0; x < width; x+=step) {
    for (int y = step*(1-(x/step)%2); y<height; y+=2*step) {
     sum = 0;
     count = 0;
     if (x-step >= 0) {
      sum+=map[x-step][y];
      count++;
     }
     if (x+step < width) {
      sum+=map[x+step][y];
      count++;
     }
     if (y-step >= 0) {
      sum+=map[x][y-step];
      count++;
     }
     if (y+step < height) {
      sum+=map[x][y+step];
      count++;
     }
     if (count > 0) map[x][y] = sum/count + MathUtils.random(-h,h);
     else map[x][y] = 0;
    }
    
   }
   h /= smoothness;
   step /= 2;
  }
  
  // Normalize the map
  float max = Float.MIN_VALUE;
  float min = Float.MAX_VALUE;
  for (float[] row : map) {
   for (float d : row) {
    if (d > max) max = d;
    if (d < min) min = d;
   }
  }
  
  // Use the thresholds to fill in the return map
  for(int row = 0; row < map.length; row++){
   for(int col = 0; col < map[row].length; col++){
    map[row][col] = (map[row][col]-min)/(max-min);
    if (map[row][col] < deepWaterThreshold) returnMap[row][col] = 0;
    else if (map[row][col] < shallowWaterThreshold) returnMap[row][col] = 1;
    else if (map[row][col] < desertThreshold) returnMap[row][col] = 2;
    else if (map[row][col] < plainsThreshold) returnMap[row][col] = 3;
    else if (map[row][col] < grasslandThreshold) returnMap[row][col] = 4;
    else if (map[row][col] < forestThreshold) returnMap[row][col] = 5;
    else if (map[row][col] < hillsThreshold) returnMap[row][col] = 6;
    else if (map[row][col] < mountainsThreshold) returnMap[row][col] = 7;
    else returnMap[row][col] = 8;
   }
  }

  return returnMap;
 }
}
int n controls the level of detail (and hence the size of your map).  int wmult and int hmult kind of control how many (mostly) independent regions there are (and hence also control the size of your map).  The thresholds all control cutoff points for the different terrain types.  I don't want to explain how the actual algorithm itself works, check out the Gameprogrammer article if you are more curious.

I also created a class HexMapGenerator.java which calls my MidpointDisplacement algorithm (and for now that's all it does, but I hope to expand to make cooler maps, maybe place towns or resources, who knows?)
package com.gamexyz.utils;

public class HexMapGenerator {
 
 public HexMapGenerator() {
 }

 public int[][] getDiamondSquare() {
  MidpointDisplacement md = new MidpointDisplacement();
  return md.getMap();
 }
}

I also updated my GameMap component to load a random map (which is remarkably fast) from the HexMapGenerator
HexMapGenerator hmg = new HexMapGenerator();
  map = hmg.getDiamondSquare();
  width = map.length;
  height = map[0].length;
With that, you can now make some awesome, playable looking maps!  We already know how to scroll around, zoom in and out, etc.  Notice as you scroll out that FPS goes down, that's because we already implemented the frustum culling, but when we zoom out more and more tiles are in the frustum, so it runs slower.  Play around and have some fun!

You have gained 50 XP.  Progress to Level 3: 300/600

The Game Map Pt 2 (Level 2)

This will be a pretty short update, but kind of fun.  The goal is to be able to click-drag to move around the world, tell which cell is being clicked on, scroll to zoom in/out, and draw only the map tiles within our camera's view.

I'm going to implement the first three pieces in PlayerInputSystem.java, and the last part in MapRenderSystem.java.

First let's look at PlayerInputSystem.java
package com.gamexyz.systems;

import com.artemis.Aspect;
import com.artemis.ComponentMapper;
import com.artemis.Entity;
import com.artemis.annotations.Mapper;
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.gamexyz.components.Player;
import com.gamexyz.components.Position;
import com.gamexyz.utils.MapTools;

public class PlayerInputSystem extends EntityProcessingSystem implements InputProcessor {
 @Mapper ComponentMapper<Position> pm;
 
 private OrthographicCamera camera;
 private Vector3 mouseVector;
 
 @SuppressWarnings("unchecked")
 public PlayerInputSystem(OrthographicCamera camera) {
  super(Aspect.getAspectForAll(Player.class));
  this.camera=camera;
 }
 
 @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);
  
 }

 @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) {
  int x = (int)((mouseVector.x - 6f) / (float)MapTools.col_multiple);
  int y = (int)((mouseVector.y - (float)MapTools.row_multiple*(x%2)/2) / (float)MapTools.row_multiple);
  return false;
 }

 @Override
 public boolean touchUp(int screenX, int screenY, int pointer, int button) {
  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;
 } 
}
The touchDown() method computes which cell is being clicked, and stores the coordinates in x,y.  It looks a little hideous because you have to be careful whether you are in an even or odd column.  Remember, because it's a hex map, if you are in an odd column all the cells are drawn down a little lower.

touchDragged() handles clicking and dragging.  It's kind of awesome that libgdx just comes with built in methods for Gdx.input.getDeltaX() and Y.  I multiply them both by camera.zoom, because when we are zoomed very far in or very far out, the distance the camera moves should change accordingly.  camera.translate() just moves the x,y, and z coordinate of the camera, but we're not touching z, so that component is 0.

scrolled() handles scrolling, and if you scroll up it zooms in (up to 0.2) whereas if you scroll down it scrolls out (up to 8).  You can adjust those points, but be wary of what can happen if you get a negative zoom!  Also, the fact that zoom changes by amount*0.1 sets how fine tuned you can adjust the zoom.  If it were 0.01, you would have finer control.

If you implement these straight away, you might notice something funny... I sure did!  The HUD which displays FPS and so on stays at a fixed point on the MAP, not on the screen.  As you zoom out, it gets smaller and smaller.  As you zoom in it does the same.  That is silly, so let's fix it!

The problem in HudRenderSystem.java is that we run batch.setProjectionMatrix(camera.combined).  This lets things move as you move your camera, exactly what we want to avoid.  Get rid of this line.  In fact, you don't really need anything to do with a camera, so this is what my new HudRenderSystem looks like (I know I left the camera as an argument, but I was just too lazy to change the main code where I initialize it).
package com.gamexyz.systems;

import com.artemis.systems.VoidEntitySystem;
import com.badlogic.gdx.Gdx;
import com.badlogic.gdx.graphics.OrthographicCamera;
import com.badlogic.gdx.graphics.Texture;
import com.badlogic.gdx.graphics.Texture.TextureFilter;
import com.badlogic.gdx.graphics.g2d.BitmapFont;
import com.badlogic.gdx.graphics.g2d.SpriteBatch;
import com.badlogic.gdx.graphics.g2d.TextureRegion;
import com.gamexyz.GameXYZ;

public class HudRenderSystem extends VoidEntitySystem {

 private SpriteBatch batch;
 private BitmapFont font;

 public HudRenderSystem(OrthographicCamera camera) {
 }

 @Override
 protected void initialize() {

  batch = new SpriteBatch();

  Texture fontTexture = new Texture(Gdx.files.internal("fonts/normal_0.png"));
  fontTexture.setFilter(TextureFilter.Linear, TextureFilter.MipMapLinearLinear);
  TextureRegion fontRegion = new TextureRegion(fontTexture);
  font = new BitmapFont(Gdx.files.internal("fonts/normal.fnt"), fontRegion, false);
  font.setUseIntegerPositions(false);
 }

 @Override
 protected void begin() {
  batch.begin();
 }

 @Override
 protected void processSystem() {
  batch.setColor(1, 1, 1, 1);
  font.draw(batch, "FPS: " + Gdx.graphics.getFramesPerSecond(), 20, GameXYZ.WINDOW_HEIGHT - 20);
  font.draw(batch, "Active entities: " + world.getEntityManager().getActiveEntityCount(), 20, GameXYZ.WINDOW_HEIGHT - 40);
  font.draw(batch, "Total created: " + world.getEntityManager().getTotalCreated(), 20, GameXYZ.WINDOW_HEIGHT - 60);
  font.draw(batch, "Total deleted: " + world.getEntityManager().getTotalDeleted(), 20, GameXYZ.WINDOW_HEIGHT - 80);
 }
 
 @Override
 protected void end() {
  batch.end();
 }
}

With that, our HUD should stay up where it belongs... silly HUD...

The last bit we want right now is frustum culling: to only draw the tiles in our camera's view.  Libgdx makes this pretty easy too, but to give you super clear idea of what a frustum is, here's wikipedia.
What we're going to do is get the coordinates of the corners of the far plane, and use them to limit what we render.  In MapRenderSystem, where we defined int x0, x1, y0, and y1, change the code to look like this:
  // 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; 
And voila!  We probably don't notice a huge difference yet, but when we start playing with HUGE maps later on, this will mean a world of difference.  It handles zooming in and out as well.

This is almost starting to look like it could become a game.  Almost...

You have gained 50 XP.  Progress to Level 3: 250/600

The Game Map (Level 2)

While what we have so far is kind of cute, it doesn't look like much of a game just yet.  As with any decent top down, tile based, 2D RPG, we need some awesome looking maps.  For right now, I don't have a perfect idea of what it should look like, but I've decided to expand myself a bit and make it a hex based grid, instead of square tiles.

The first thing I wanted was a set of terrain tile sprites, which I threw together in Paint.NET.  I based my tiles on a 46 x 39 pixel square, because I wanted my hexagons to be as close to regular hexagons as possible, which requires some rounding on a computer (pesky sqrt(3))!

Anyway, I chose to make tiles for deep water, shallow water, beach/desert, plains, light forest, forest, hills, mountains, and tall mountain peaks.  I named the files hex_0.png through hex_8.png to make them load into a single object with the ImagePacker.  Because I actually drew these, I suppose I should mention something about a license.  I like the creative commons attribution license, so use them however you like as long as you give me credit!  As for my code, use it however you like too.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 Unported License.


I put these images in a folder textures/maptiles in GameXYZ-desktop.  They were designed with partially transparent edges so they could overlap and show some natural looking grid lines.  Here's an example of a random map I generated and rendered with these tiles (click for full size):

Actually, that's just a small portion of the whole, which looks like:

This is really just a first stab at the terrain generation, but I think it's okay for now.  We'll talk about how to make it in a later terrain generation post.  For now though let's focus on how we store and render it.

The data for the map is stored in a 2D array of ints, where each int corresponds to a terrain type (0=deep water, 1=shallow water, etc...).  Unlike a typical 2D tile map, which is just about perfectly represented by a 2D array, the hexmap needs a little tweaking.  Whereas a typical square tile map might look like this:

To turn it into a hexmap, we can shift every other column up by half a cell to look like this:

Of course we won't want to render our tiles to look like squares, but as far as the 2D int array is concerned, this is how it will be rendered.

Notice a frustrating problem with this though, whereas in the square array it's very easy to find a cells neighbors, it is less trivial in the hex map.  Consider cell (1,1).  It has a neighbor of (2,2), or (1+1, 1+1).  However, (4,3) does NOT have a neighbor at (4+1,3+1)=(5,4).  The problem comes with the upward shift of every other column.  So when we are navigating the map, or getting cell neighbors, we'll have to be very careful how we do it.

UPDATE:
The following no longer reflects how I implemented it.  Very shortly after writing this, I realized it stunk as I tried to implement pathfinding.  The general concept is the same, but it is not a Component and Entity thing, it is just a stand alone class called GameMap.java which has a field declared in GameXYZ.java.  To see how it is done more recently, check out the pathfinding post here.
 
To actually implement this, I made a new Component called GameMap, and a new EntitySystem called MapRenderSystem.  At the start of the game I'll create an entity with the GameMap component, which will store the 2D array, plus whatever other crap I can think of as necessary, and every cycle the MapRenderSystem will render it (much like SpriteRenderSystem).  I'll specifically call MapRenderSystem first, so that sprites get rendered on top of it.  I also create a few other helper classes.  Here's what they look like:
package com.gamexyz.components;

import com.artemis.Component;

public class GameMap extends Component {
 public int[][] map;
 public int width, height;
 
 public GameMap() {
  map = new int[][] {
    { 0, 1, 2, 3, 4, 5, 6, 7, 8 },
    { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 2, 2, 2, 2, 2, 2, 2, 2, 2 },
    { 2, 2, 2, 2, 2, 2, 2, 2, 2 },
    { 3, 3, 3, 3, 3, 3, 3, 3, 3 },
    { 3, 3, 3, 3, 3, 3, 3, 3, 3 }
  };
  width = map.length;
  height = map[0].length;
  
 }
}
Here we just have some crappy predefined map, plus info on the width and height.  The RenderSystem looks like this:
package com.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.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.utils.Array;
import com.gamexyz.components.GameMap;
import com.gamexyz.utils.MapTools;

public class MapRenderSystem extends EntitySystem {
 @Mapper ComponentMapper<GameMap> gm;
 private SpriteBatch batch;
 private TextureAtlas atlas;
 private Array<AtlasRegion> textures;

 private OrthographicCamera camera;
 
 @SuppressWarnings("unchecked")
 public MapRenderSystem(OrthographicCamera camera) {
  super(Aspect.getAspectForAll(GameMap.class));
  this.camera = camera;
 }
 
 @Override
 protected void initialize() {
  batch = new SpriteBatch();
  
  atlas = new TextureAtlas(Gdx.files.internal("textures/maptiles.atlas"),Gdx.files.internal("textures"));
  textures = atlas.findRegions(MapTools.name); 
 }

 @Override
 protected boolean checkProcessing() {
  return true;
 }

 @Override
 protected void processEntities(ImmutableBag<Entity> entities) {
  for (int i = 0; i < entities.size(); i++) process(entities.get(i));
 }
 
 private void process(Entity e) {
  GameMap gameMap = gm.get(e);
  TextureRegion reg;
  int x, y;

  int x0 = 0;
  int x1 = gameMap.width;
  
  int y0 = 0;
  int y1 = gameMap.height;
  
  // Loop over everything in the window to draw
  // Because I am drawing a hexmap tile, I chose to 
  // do 2 columns at once. As such, I had to
  // stop shy of the far right column, because
  // col+1 would break for it.  Thus we do that
  // final column separately.
  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);
   }
   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);
   }
   
  }
 }
 
 @Override
 protected void begin() {
  batch.setProjectionMatrix(camera.combined);
  batch.begin();
 }
 
 @Override
 protected void end() {
  batch.end();
 }
}
Here, when it's initialized, it stores the map textures in an Array called textures (lines 37-38).  Because every 2nd column has to be shifted up by half a cell, I had a choice between rendering two columns at once, and manually putting the 2nd one up a bit, or rendering each column individually and checking to see if we were on an even or odd column every time.  I chose the first option (lines 70-77).  My random map generation method ends up with an odd number of columns overall, however, so I had to render the last one separately (lines 79-85).

I call MapTools.col_multiple and MapTools.row_multiple to get the row and column offsets that each hex cell should be drawn at.  Because they are hex cells, the images have to overlap a bit to line up properly, and those constants store that information.  MapTools.name is just a string "hex", because I wanted to potentially have the flexibility to someday also do square tiles.  The MapTools class went into com.gamexyz.utils
package com.gamexyz.utils;

import com.gamexyz.custom.Pair;

public class MapTools {
 
 public static final int col_multiple = 34;
 public static final int row_multiple = 38;
 public static final String name = "hex";
 
 

 public static Pair[] getNeighbors(int x, int y, int n) {
  Pair[] coordinates = new Pair[3*(n*n + n)];
  int i = 0;
  int min;
  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 (x==col && y==row) continue;
    else if (x % 2 == 0) coordinates[i]=new Pair(col,2*y-row);
    else coordinates[i] = new Pair(col,row);
    i++;
   }
  }
  return coordinates;
 }
 
 public static Pair[] getNeighbors(int x, int y) {
  return getNeighbors(x,y,1);
 }
}
That getNeighbors method was a nightmare to create.  I'm certainly not sure that it's the best way to go about it, but I've tested it and it works.  It returns the neighbors as an array of Pairs, which I had to define in com.gamexyz.custom
package com.gamexyz.custom;

public class Pair {
 public Pair(int x, int y) {
  this.x = x;
  this.y = y;
 }
 public int x, y;
}

Also, a few of these classes reference something called MyMath, which is just a collection of a few math methods I put together in com.gamexyz.utils.  They're not the most general, but they get the job done quickly.
package com.gamexyz.utils;

public class MyMath {
 public static int min(int a, int b) {
  if (a < b) return a;
  return b;
 }
 
 public static int min(int a, int b, int c) {
  if (min(a,b) < c) return min(a,b);
  return c;
 }
 
 public static int pow(int a, int b) {
  if (b > 1) return a*pow(a,b-1);
  else return a;
 }
}

Remember to register the MapRenderSystem and create an Entity with the component for GameMap, and also remember to manually process MapRenderSystem. With that, you are now drawing a game map in hex tiles! These methods should be easy to customize if you want square tiles instead.

There are a couple of crappy things going on here though.  First, this code always renders the ENTIRE map... not just the portion it needs.  That process is called Frustum Culling, and is actually super easy!  For small maps, this isn't so important, but for larger maps it will make a difference.  We'll talk about it in the next article.

Also, it would be super nice to be able to click/drag and move the map, and maybe even use a scroll wheel to zoom in and out.  These are also pretty easy and will be discussed next time.

Also, you can design your own maps by hand, but that is PAINSTAKINGLY slow I think.  I implemented the Diamond-Square fractal terrain generation algorithm, it's super fast, and I'll post that along with its inner workings coming soon.

I will probably also start a Google Code repository soon so people can come and download the code in case something doesn't work so well because I forgot some minor thing I tweaked in another file.

You have gained 100 XP.  Progress to Level 3: 200/600