Prettier Maps


Code for this tutorial is on this git branch:

git clone -b better_maps https://dglencross@bitbucket.org/dglencross/zombiegametutorial.git

Have a look here for help setting it up


This is a screenshot from Dinowar, our Android game written with Libgdx. The random map generation is very similar to what we have implemented in this Zombie tutorial.

Compare that to what we have done so far in this tutorial series:

Until now, we haven’t put a lot of effort into making the maps look better. In this tutorial, we will make some changes so that our maps look more like this:

50% water

Notice how the edges are much cleaner, they are have curved corners and nicer edges. There is also a clear, coloured border line.

20% water

Let’s take a look at how we have achieved this. Firstly, we have created a bunch of new images (which you can use in your own projects). These are under the assets_general/tiles folder.

These images might not look obviously related to the screenshots above – but we will see how they form to create the rounded edges that we want.

Terrain transitions

At the moment, the borders of the land are just solid, blocky divisions and look very rough. To make our map look good, we need some way of making the transitions between these different types of tile look more natural.

The solution we have used is taken from this tutorial:

https://www.gamedev.net/resources/_/technical/game-programming/tilemap-based-game-techniques-handling-terrai-r934

I strongly recommend you go read this tutorial – it is not long, and I do not see the point of reproducing the content here.

But, to summarise as quickly as possible – for each tile, we work out if it touches a tile of a different type (in our case, where land and water touch) and work out what bits of the tile we should draw. But seriously, go read that tutorial.

When water meets land, the water ‘overlaps’ the ground to allow for a smoother looking transition.

Our implementation

We calculate the the transition information for each tile when we create the map. We loop through all the tiles and work out which transition images we want to apply to each one, then store that information in the Tile object. Each tile has been assigned a number of sprites which sit on top of one another to achieve the full effect. Then each time we draw, we draw every sprite for each individual tile.

Check out the changes in the following classes:

Tile.java, TileSprite.java, Pair.java and MapTools.java

Tile.java

Firstly, we load in all the sprites that we are going to use in setSprites().

Now, when a Tile is created, we create our corners and edges that will be drawn on each update.

public Tile (Pair pair) {
   makeCorners(pair);
   makeEdges(pair);
}

I’m not going to reproduce all the code here – check out the project and look for yourself. But the makeCorners() and makeEdges() methods set up what the tile is going to look like based on its neighbours (i.e. its surrounding tiles).

TileSprite.java

Now, when we draw our tiles (and TileSprites), we draw the ‘solid’ and ‘line’ sections’ of each tile. The ‘line’ parts are the borders – you can see what I mean with the following screenshot – this has had the lines removed:

Compare that to a previous screenshot. Personally I think it looks much better with the lines – but if you don’t want them, delete the following in TileSprite.java:

if (linePart!=null) {
   linePart.setBounds(pair.x, pair.y, 1, 1);
   linePart.setColor(lineColor);
   linePart.draw(batch);
}

Then delete code around adding the lines – but I don’t think you’ll want to do this.

Conclusion

I haven’t gone into a huge amount of detail about the code in this tutorial, but it is not that complicated – the important thing is to understand the concept, and your best way to do that is to read the tutorial I linked to above (and here) on GameDev.net. The code provided is based on the ideas from the GameDev tutorial.

It transforms a blocky map into a much nicer, smoother looking map. And it is possible for more than just land and water – if you are creating a more detailed map, you can fiddle with the order of precedence of your map details to get them to smoothly transition into one another.



If you like these tutorials, or want to see a game that was written in much the same way, please download Dinowar from the Google Play Store. It costs nothing and is ad-free.

Firing bullets at zombies


Code for this tutorial is on this git branch:

git clone -b zombies https://dglencross@bitbucket.org/dglencross/zombiegametutorial.git

Have a look here for help setting it up


Firing bullets

Also included in the latest code is the ability to fire bullets at zombies. They way the player actually does this is to touch on or close to the zombie.

In the earliest iteration of this, I had the zombies simply die when clicked on. This was very unsatisfying, so I implemented proper bullets. In the current version of the game, I don’t think it’s actually possible to miss – the zombies run directly at you, so when you fire a bullet in their direction, you are guaranteed to hit. However, you could imagine a development of the game where the zombies run from side-to-side, and so bullets could easily miss.

The bullets continue on when they hit a zombie, so they can actually hit multiple zombies on the map if they happen to be aligned.

Aiming

As described, the mechanism for firing is to click on/touch a zombie. In our PlayerInputSystem, we introduce a method for checking if the place we just touched is on a zombie.

private Zombie getTouchedZombie(int x, int y) {
   Vector2 touch = new Vector2(x,y);
   for (Zombie z : screen.getGameController().getZombies()) {
      if (!z.hasBeenShot() && z.getPos().dst(touch) < 2) {
         return z;
      }
   }

   return null;
}

All we do is loop over our zombies and check if they are close to the touch. This is some pretty basic ‘collision detection’. We call this method every time we touch somewhere on the screen. If it returns a zombie, we fire at it.

Zombie shot = getTouchedZombie(x, y);

if (shot != null) {
   getPlayer().shootZombie(shot);
   return false;
}

Note we also return from the touchDown method – we don’t want to walk towards the zombie. Whenever we shoot, the player stops walking.

Bullets

The Bullet class is where all of the logic for an individual bullet resides. It is created and then the fire() method is called, and given its starting point and its destination (i.e. the location of the zombie we have fired at).

public void fire(Vector2 destination, PlayerCharacter character) {
    currentPosition = character.getPos().cpy();
    endPosition = destination.cpy();

    dir = endPosition.cpy();
    dir.sub(currentPosition);
    dir.setLength(BULLET_SPEED);
}

Let’s look at what is going on here. In the first two lines, we assign our currentPosition to be the same as the character’s, and the endPosition to be the vector we have passed in.

We set the dir (direction) variable to be the difference between the start and end points, but at a shorter length. You can vary this length depending on how fast you want your bullets to move.

When we update then, we just keep adding that dir variable to the currentPosition to keep our bullet moving in a constant direction at constant speed:

public void update(float delta) {
    currentPosition.set(currentPosition).add(dir);
    sprite.setPosition(currentPosition.x, currentPosition.y);
}

Bullets colliding with zombies

Finally, we need some collision detection between zombies and bullets. This will work in the same way as the other basic collision detection we use (when checking whether a player has clicked near a zombie, or if a zombie is touching the player). Every time we update the zombies, we check whether they have been hit by a bullet.

This is in the GameController:

// check if a zombie has been hit by a bullet
for(Bullet b : bullets) {
   if (b.isLive() && z.getPos().dst(b.getPos()) < 1.0f) {
      z.shoot();
   }
}

If the bullet is still live, and it is very close to the zombie, we consider that a collision and kill the zombie by triggering its shoot method. (We also keep track of the number of shot zombies, but I’ve removed that from here just for clarity).

At this point of the development of the game, the zombie’s shoot method simply tells it that it has been shot. This means that when zombies come to be updated later, this zombie will not have its update method triggered, and the player can no longer interact with it, for example by dying when walking over it. We also set the zombie’s sprite to be a satisfyingly gory blood splatter.

Conclusion

In this tutorial we have shown how to fire bullets and have them ‘hit’ zombies.

There are still some improvements to be made for this, which I may work on in future (though it’s not a priority). These include:

  • collision detection could probably be more efficient
  • at time of writing, bullets never ‘die’. This would be fairly easy to implement though – just keep count of how far a bullet has travelled and set  ‘live = false’ after a certain distance
  • the bullet does not come out of the player character’s gun, but just starts from his ‘position’ on the map. Again, this could be done fairly easily I think – but it seemed fiddly so I haven’t bothered (particularly as I might change the player sprite in future)

Next up will either be some kind of GUI, or perhaps map improvements – the map still looks a bit crap at the moment. In Dinowar we have logic to work out corners and how edges fit together, something that I may implement in a future tutorial for this.

Dinowar edges made smooth


If you like these tutorials, or want to see a game that was written in much the same way, please download Dinowar from the Google Play Store. It costs nothing and is ad-free.

Zombie splat – creating random zombies


Code for this tutorial is on this git branch:

git clone -b zombies https://dglencross@bitbucket.org/dglencross/zombiegametutorial.git

Have a look here for help setting it up


Zombies

If you have already downloaded and run the game, you will see zombies running towards the main character. In this tutorial, we will describe how these zombies are created and how they choose what to do. It is fairly straightforward – but leaves a lot of room for more complex behaviour, if you wish to adapt it.

Zombie behaviour

  • Stand in a random position
  • If the player comes within a certain radius, run towards him
  • Keep moving towards the player in a straight line, unless the player goes out of range
  • If there is an obstacle in the way, stop
  • If we have reached the player, kill him

If you have followed the tutorial all the way through, you may remember that the player character originally moved in straight lines, just walking towards the clicked point. This is the behaviour that I have implemented for the zombies, with an additional bit of logic to check that the zombie is not about to walk into an obstacle (in our case, water).

Zombie.java

First off, when we create the zombie we stick him in a random start position using the same helper method as we do for the player – however, we make sure the zombie does not spawn close to the player. This is to stop zombies attacking the player as soon as the game launches – it is better to let the player make some movement first.

while(pos.dst(screen.gameController.getPlayer().getPos()) < attackRadius) {
            pos = screen.getWorld().getRandomStartPosition();
        }

As with the player character, the core of the class is in its update method:

public boolean update(Vector2 playerPos) {
    if (hasBeenShot) {
        return false;
    }

    if (withinAttackDistance(playerPos)) {
        updateOrientation(playerPos);
        moveTowardsPlayer(playerPos);
    }
    return touchingPlayer(playerPos);
}

Firstly, we check if the zombie has already been shot – if so, do nothing.

If the zombie is close enough to the player to attack (I have hard-coded the radius – the larger you make it, the harder the game is), it will rotate to look at him, and move towards him.

For an added creep-factor, you can make the zombies update orientation regardless of whether or not the player is in view – it adds a certain level of creepiness to know that they are all pointed at the player, all the time.

private void updateOrientation(Vector2 playerPos) {
    float angle = (float) Math.toDegrees(Math.atan2(playerPos.x - pos.x, playerPos.y - pos.y));
    this.orientation = - angle;
}

The updateOrientation logic should look familiar to you if you have followed the tutorial – it is very similar to the way it works for the player character.

private void moveTowardsPlayer(Vector2 playerPos) {
    diff = playerPos.cpy();
    diff.sub(pos);

    diff.setLength(ZOMBIE_SPEED);

    Vector2 nextPos = pos.cpy().add(diff);

    // attempt to stop zombies crossing water
    Pair nextPair = screen.getWorld().getPair((int)nextPos.x, (int)nextPos.y);
    if (nextPair.isLand) {
        pos.set(pos).add(diff);
    }

}

Again, for moving towards the player we use vector maths to calculate the next step. We only update the zombie’s position if he is moving to a land tile – if not, he gets stuck. This does make the zombie pretty stupid – you can try changing this if you want.

The ZOMBIE_SPEED is hard-coded, and if you want a more challenging game, try increasing it – it definitely makes the game more fun.

private boolean touchingPlayer(Vector2 playerPos) {
    return pos.dst(playerPos) < 0.5;
}

The last step is to check if the zombie is touching the player, and return that value – if it is, we wanted to take some action. In this version, we kill the player (and the zombie). In future, we might allow (for example) three zombies to hit the player before he dies.

Creating the zombies

In GameController, during the creation of a new game, we allocate our zombies.

private void createZombies() {
   zombies = new ArrayList<Zombie>();
   for(int i=0; i < startingZombies; i++) {
      zombies.add(new Zombie(screen));
      zombiesAlive++;
   }
}

Fiddle with the startingZombies variable if you want to try the game out with more or fewer zombies.

No path-finding?

Instead of having the zombies run in a straight line, you can implement Jump Point Search for them. However, just in the interests of running quickly on a mobile phone, I have decided to make my zombies do no path-finding.

Conclusion

We have seen how to create some simple zombies and imbue them with basic behaviour. Next up, we will learn how to shoot them.



If you like these tutorials, or want to see a game that was written in much the same way, please download Dinowar from the Google Play Store. It costs nothing and is ad-free.

Zombie Splat – a playable game


Code for this tutorial is on this git branch:

git clone -b zombies https://dglencross@bitbucket.org/dglencross/zombiegametutorial.git

Have a look here for help setting it up


Zombie Splat

For the first time, the code for this tutorial features the outline of an actual playable game. Its working title is Zombie Splat, due to lack of imagination on my part. Here’s a little sample of it:

What I’ve added since the last tutorial:

  • Zombies who attack when you get close enough to them
  • The ability to shoot the zombies by tapping on them (or clicking, as in the above video)
  • A bit of text to display how many zombies are remaining to shoot
  • A ‘You win/You lose’ message depending on the outcome of the game

These are the key features that we’ve added in this tutorial series so far:

Feel free to download the code for the above video, and in the next few posts I’ll go into some depth explaining the code that has been added to enable these new features.



If you like these tutorials, or want to see a game that was written in much the same way, please download Dinowar from the Google Play Store. It costs nothing and is ad-free.

Making the camera follow the character


Code for this tutorial is on this git branch:

git clone -b sticky_camera https://dglencross@bitbucket.org/dglencross/zombiegametutorial.git

Have a look here for help setting it up


Keeping the camera centred on the player – intelligently

This tutorial can be used independently to the ongoing series, as this is probably a useful bit of code for a lot of top-down 2D games.

In previous tutorials, the camera has been following the player around the screen, always keeping the camera centred over the player. However, when the player moves towards the edge of the game world, the edge of the map and beyond is visible. This looks pretty awful.

What we want is for the camera to follow the player around, but never get to the edge of the map. So when they player gets within a certain distance of the edge of the map, the camera stops following.

Code

float x = getPlayer().getX();
float y = getPlayer().getY();
// We divide the viewPort sizes by 2, because the player
// is always in the middle of the screen - with half of the
// screen above it, half below, half to the left side of it,
// half to the right

// You can extract these out (as they are in the full project)
// These are always the same, so only need to be calculated once
float halfViewPortWidth = camera.viewportWidth / 2;
float halfViewPortHeight = camera.viewportHeight / 2;

if (x < halfViewPortWidth) {
    camera.position.x = halfViewPortWidth;
} else if (x > ZombieGame.getWorldWidth() - halfViewPortWidth) {
    camera.position.x = ZombieGame.getWorldWidth() - halfViewPortWidth;
} else {
    camera.position.x = x;
}

if (y < halfViewPortHeight) {
    camera.position.y = halfViewPortHeight;
} else if (y > ZombieGame.getWorldHeight() - halfViewPortHeight) {
    camera.position.y = ZombieGame.getWorldHeight() - halfViewPortHeight;
} else {
    camera.position.y = y;
}

When the player is in the middle of the map, the camera will track normally. However, if the player steps outside the artificial boundaries then the camera will stay in a position in which it can never see off the map.

In the above code, we check if the player is too far to the left of the map, or too far to the right. If so, we limit where the camera can be on the X-axis. Otherwise, we just set the camera’s X parameter to match that of the player.

Similarly, we check if the player is too far towards the top or bottom of the map, and do the same.

In this way, the camera can track along one axis but not the other, or both at the same time – which will happen when the player is in a corner.



If you like these tutorials, or want to see a game that was written in much the same way, please download Dinowar from the Google Play Store. It costs nothing and is ad-free.

Following a path – Pathfinding 3


Code for this tutorial is on this git branch:

git clone -b Jump_point_search https://dglencross@bitbucket.org/dglencross/zombiegametutorial.git

Have a look here for help setting it up


Following a path

Up until now we’ve shown how to generate a path using Jump Point Search, a variant of the A* search algorithm that is much faster, but has a big limitation – that it only works on flat maps.

The final piece is to decide how to navigate the path. The path itself will be our Path class, which is a wrapper around an array of Steps. Each Step represents one coordinate on the map that we want to move towards (and they are in order).

However, they are not uniformly spaced apart, so we can’t just step from one to the next. We can’t say “go to step 1, then to step 2, then to step 3 etc”. Instead, think of it like this: “move in the direction of step 1, then once you have reached it, move in the direction of step 2” at the same pace. For this, we use a little vector calculation, which I will explain below.

 

Creating the path

You might remember the method from a previous tutorial, where we tell the PlayerCharacter where it should be moving towards. This was:

public void setDestination(Pair destination)

This is where we create our path, as we want to calculate a new one each time we touch somewhere on the screen to move towards.

This now looks like this:

public void setDestination(Pair destination) {

if (destination.isWater()) {
return;
}

pointAt(destination.asVector());

Pair currentLocation = new Pair((int)pos.x, (int)pos.y, true);

JPS landJps = new JPS(screen.getWorld(), currentLocation, destination);

path = new Path(landJps.search());
}

 

Here we tell make sure the destination is valid (i.e. not water), make sure we’re pointing at it, then generate our path. Now, our PlayerCharacter has a path to follow.

Update the PlayerCharacter’s position

public void update(float delta) {
   if (null == path || path.isEmpty()) { // we have no valid path, so just return
      return;
   }

   pos = getNextPosition(delta);
   updateOrientation();

   if (nextPathNodeIndex > path.getLength()) { // then we've arrived
      path = null;
      nextPathNodeIndex = 0;
   }
}

First off, no path means no movement.

Then we determine our next position (the method for which we’ll look at below), move towards it, and point towards it, so that the PlayerCharacter is always pointing in the direction it is moving.

Then we work out if we have arrived at our destination, and if so, nullify the path so that we stop moving.

getNextPosition()

private Vector2 getNextPosition(float delta) {
   if (nextPathNodeIndex == 0) {
      currentPN.set(stepToV2(path.getStep(0)));
      nextPathNodeIndex ++;
   } else {
      float amountToMove = 3*delta;
      do {
         nextPN.set(stepToV2(path.getStep(nextPathNodeIndex)));
         moveVec.set(nextPN);
         moveVec.sub(currentPN);

         if (moveVec.len() > amountToMove) {
            moveVec.setLength(amountToMove);
            currentPN.add(moveVec);
            amountToMove = 0;
         } else {
            amountToMove -= moveVec.len();
            currentPN.set(nextPN);
            nextPathNodeIndex++;
            if (nextPathNodeIndex>path.getLength()) {
               break;
            }
         }
      } while (amountToMove > 0);
   }
   return currentPN;
}

private Vector2 stepToV2(Step step) {
   return tmp.set((float)step.getX(),(float)step.getY());
}

This is the most complicated part of it, and to be honest even I am having to concentrate to remember how it works (always a sign of great code). The purpose of this method is always to move the same amount in one update. So if your next Step is further away than you are allowed to move (which we’ll call X), then you only move by X amount. If the next Step is less than that – e.g. it is only a quarter of X away – we move to that next Step, then work out where the Step after that is, and move the remaining distance (three-quarters of X) in that direction.

Here is the pseudocode interpretation of it:

  • If we haven’t moved yet, move to the first step (which should be where you are already, it’s just to advanced along the path).
  • Else, determine what the vector between our position and the next step is.
  • If this vector is longer than the amount we are allowed to move, reduce it until it is the maximum length we can move in one go.
  • If this vector is less than or equal to the amount we are allowed to go, move in that direction, then move in that direction, and subtract that distance from the amountToMove – so if you are allowed to move 10 units, and you have moved 2, then you have 8 units of movement left to go.
  • While amountToMove is greater than zero, repeat this process.

This might seem a bit convoluted – perhaps you will come up with a better way of doing it – but for your purposes, you might not even need to edit this method. Just remember, the point of it is to keep the PlayerCharacter moving at a constant speed along the Path that it has created.

Conclusion

If you have read the last three tutorials, you should now have Jump Point Search working and an understanding of what it is doing. The code is all provided in the repository so go ahead and play around with it. If anything is unclear, just leave a comment below the line.

We’re doing with path-finding now – next up, we will introduce some zombies to run towards the player, then after that we will work out how to shoot them.



If you like these tutorials, or want to see a game that was written in much the same way, please download Dinowar from the Google Play Store. It costs nothing and is ad-free.

Pathfinding with Jump Point Seach 2


Code for this tutorial is on this git branch:

git clone -b Jump_point_search https://dglencross@bitbucket.org/dglencross/zombiegametutorial.git

Have a look here for help setting it up


Path-finding 2

In the last tutorial, I described how Jump Point Search works (at a high level). In this tutorial, we will look at some of the key parts of the code. Specifically, we will look at the parts of code which you might want to change. If you’re creating your own project instead of following the project int this tutorial, you will be able to see what to edit.

In this tutorial we will look at how to find a path – in the next tutorial, we will look at how to follow it. That part has a bit of vector maths, but is much simpler than the JPS algorithm.

Basic elements of Jump Point Search

To get from A -> B:

  • from node A, look at surrounding nodes and decide which ones are in the correct direction
  • look at each of these potential nodes and decide if we can move to them (whether they are ‘walkable’)
  • repeat until we get to B
Pathfinding in Dinowar. The red cross shows where the dinosaur turns.

JPS.java, Heap.java and Path.java

These are the most complicated classes for JPS, and these were provided by Kevin Glass (as credited in code). They have been edited to a minimum, just to insert our own custom code.

The basic algorithm is described in the previous tutorial – if you are very interested, go back and reread it while looking at these implementations. I’m not going to go into it any further (unless anyone gets in touch to say they want it).

What is a node?

In our case, a node means a tile on the map. Our base class for the nodes is Pair.java. If we’re to integrate this into our pathfinding, we need to include some more logic. Each pair/tile/node needs to keep track of its costs – defined as:

f = g + h

for tile X, where g is the distance from the current node to tile X, and h is the distance from X to the target destination. So the JPS algorithm needs the nodes to keep track of their costs, and so they need variables to hold f, g and h, and a method to update them:

public void updateGHFP(float g, float h, Pair parent){
   this.parent = parent;
   this.g = g;
   this.h = h;
   f = g+h;
}

We also include some code to reset these values to 0, which we use when creating a new map (just to wipe out all previous values).

World.java

This is the existing class that we have modified the most. I want to highlight some methods that will interest you most if you want to change anything:

/**
 * Tests an x,y node's passability
 *
 * @param x (int) node's x coordinate
 * @param y (int) node's y coordinate
 * @return (boolean) true if the node is obstacle free and on the map, false otherwise
 */
public boolean walkable(int x, int y){

   if (MapTools.outsideTheWorld(x, y, getMap())) {
      return false;
   }

   if (getMap()[x][y].isWater()) {
      return false;
   }

   return true;
}

I hope you can get the idea here. At this stage of the project, we can still click outside of the world map (something we will later change), so first we check that the user has clicked in a valid place.

Then we check if the place the user has clicked is water. If so, our character cannot walk there!

If we passed both these checks, then our tile is ‘walkable’.

This is used by the following method, to return our valid neighbours:

/**
 * returns all adjacent nodes that can be traversed
 *
 * @param node (Pair) finds the neighbors of this node
 * @return (int[][]) list of neighbors that can be traversed
 */
public int[][] getNeighbors(Pair node){
   int[][] neighbors = new int[8][2];
   int x = node.x;
   int y = node.y;
   boolean d0 = false; //These booleans are for speeding up the adding of nodes.
   boolean d1 = false;
   boolean d2 = false;
   boolean d3 = false;

   if (walkable(x,y-1)){
      neighbors[0] = (tmpInt(x,y-1));
      d0 = d1 = true;
   }
   if (walkable(x+1,y)){
      neighbors[1] = (tmpInt(x+1,y));
      d1 = d2 = true;
   }
   if (walkable(x,y+1)){
      neighbors[2] = (tmpInt(x,y+1));
      d2 = d3 = true;
   }
   if (walkable(x-1,y)){
      neighbors[3] = (tmpInt(x-1,y));
      d3 = d0 = true;
   }
   if (d0 && walkable(x-1,y-1)){
      neighbors[4] = (tmpInt(x-1,y-1));
   }
   if (d1 && walkable(x+1,y-1)){
      neighbors[5] = (tmpInt(x+1,y-1));
   }
   if (d2 && walkable(x+1,y+1)){
      neighbors[6] = (tmpInt(x+1,y+1));
   }
   if (d3 && walkable(x-1,y+1)){
      neighbors[7] = (tmpInt(x-1,y+1));
   }
   return neighbors;
}

The JPS algorithm should only be considering tiles which are ‘walkable’. This method takes a tile, looks at all its neighbours, and returns only those which are valid.

Walkability in Dinowar

I just wanted to highlight how you could modify this for other things. In Dinowar, we have the concept of ‘border tiles’ which surround territories. These are also not walkable.

We also have dinosaurs that can travel over water (but not land). In this case, we have to pass in a variable telling the method the type of dinosaur – and the method takes this into account when determining if a tile is ‘walkable’ for a particular dinosaur.

Running JPS

In our tutorial game, we generate a path when a player clicks, so the launching of JPS is done in PlayerCharacter.java. We will look at this in more depth next time.

Conclusion

We have seen how we are generating paths, and what to change if you want to integrate this code into your own project. In the next tutorial we will look at how we use the paths that this JPS algorithm has generated for us – how to follow them, and how to point our character in the right direction.



If you like these tutorials, or want to see a game that was written in much the same way, please download Dinowar from the Google Play Store. It costs nothing and is ad-free.

Pathfinding with Jump Point Search

 


Code for this tutorial is on this git branch:

git clone -b Jump_point_search https://dglencross@bitbucket.org/dglencross/zombiegametutorial.git

Have a look here for help setting it up


Path-finding

This is where things start to get interesting, as we introduce some more complex behaviour. So far our little character walks in whichever direction you tell him. If you are standing on one island and click on another island, he will travel in a straight line, over water, towards that other island.

Instead, we want our character to travel only on land. If there is water in the way of our destination, we should walk around this water (if possible).

Excuse the shitty graphics
Path-find towards the X

There are a few different algorithms for path-finding, and most already have examples in Java.

This is part of our Libgdx tutorial series, but neither the algorithm nor the implementation are dependent on it.

 A* Search

You may have heard of A* search – if you have done anything to do with path-finding then you almost certainly have.

There are many examples of A* search tutorials in Java, and we implemented one of them originally in Dinowar. A* search tries to find the ‘cheapest’ path from one node to another, considering the costs of nodes in between. For example, if you have a map with mountains on it, any tile/node which is on a mountain will be more expensive than one on flat ground.

Imagine that you want the character from move from A to B. The path-finding algorithm will look at the surrounding tiles/nodes from A, see which is the cheapest one to move to, where its cost is defined as approximately its cost to move to (higher/lower depending on terrain of the map) added to its estimated cost to B – so the closer the node is to B, the lower this cost would be.

This is a wildly simple explanation – if you want more technical info, these resources are pretty good for explaining it:

http://web.mit.edu/eranki/www/tutorials/search/

https://en.wikipedia.org/wiki/A*_search_algorithm

Speaking of mountainous areas, an early version of Dinowar looked like this:

We implemented A* search, so you would often see the dinosaur characters move around the outside of a mountain in an attempt to get to their destination move quickly.

So, why did we go with Jump Point Search instead of A* search?

A* Search in Dinowar

When running the game on Android, we found A* search to be too slow. Dinowar can have up to 10 different bases, with each one having paths between them for both land and water dinosaurs. In theory, that can be 10! x 2 different paths. In practice, we needed the path generation to be so fast as to be unnoticeable by the player. When running on a phone, generating a path could take up to half a second, which made the game unplayable in practice.

We experimented with generating all potential paths when creating the map, but again this lead to slowness on map generation. We wanted the player to be able to press the refresh button as many times as they wanted, until they got a map they were happy to play on.

After some research, we discovered a lesser-known algorithm:

Jump Point Search

JPS is a faster version of A* search, with one major drawback – it assumes that all tiles are the same ‘cost’. No more mountains, but much, much better speed. This is why Dinowar ended up looking like this:

Paths are generated at map-creation time, and it is so fast as to be irrelevant.

How does it work? Essentially, it does the same as A* search, but because all tiles/nodes cost the same, the algorithm knows that it only has to consider its neighbours in the direction of the destination. For example, think of A -> B again. In A* search, if there is a mountain between A and B, it might actually make sense for the path to start backwards, as long as the route is still cheaper than going across the mountain. In JPS, we assume the ground is flat, and there is no need to consider the possibility of going backwards.

Check out this picture from an excellent explanation that you can find here: https://harablog.wordpress.com/2011/09/07/jump-point-search/

The arrow represents the direction of movement. On the left, you see what happens when you are moving along a straight line (straight up or straight sideways). You only have to consider the tile in front of you.

On the right, we see what happens when moving diagonally – we only have to consider three nodes.

This represents a huge saving in effort when generating paths. This is especially important in our tutorial – we will be generating a path every time the player character is told to move around the map, so we really want our path-finding to be instantaneous.


Conclusion

Try playing with the tutorial – this is the first section which uses the path-finding code that we’ve uploaded. In the next part of the tutorial, we’ll go into depth on the actual code implementation of Jump Point Search.



If you like these tutorials, or want to see a game that was written in much the same way, please download Dinowar from the Google Play Store. It costs nothing and is ad-free.

Moving a character around the map 4 – Camera, Viewport


Code for this tutorial is on this git branch:

git clone -b First_signs_of_movement https://dglencross@bitbucket.org/dglencross/zombiegametutorial.git

Have a look here for help setting it up


Viewport

A viewport is Libgdx’s way of managing your camera’s width and height. Although we will not be resizing our viewport during the game, it means that you do not need to worry about different sizes of screens.

We are using a specific Libgdx viewport – the StretchViewport.

import com.badlogic.gdx.utils.viewport.StretchViewport;

From the documentation:

A ScalingViewport that uses Scaling.stretch so it does not keep the aspect ratio, the world is scaled to take the whole screen

When you run the game on your computer, you can resize the window and see how everything updates to the correct size. This is the viewport managing the camera/graphics for you.

large small

You can see from these two (by the size of the title text) that one is zoomed and one is not, but the viewport has dealt with the resizing fine.

ZombieGame extends MyGame

When we launch the game, the ZombieGame class creates our viewport:

@Override
protected void initViewport() {
   // Total view width
   float viewWidth =32;
   float viewHeight = Math.round(Gdx.graphics.getHeight()/(Gdx.graphics.getWidth()/viewWidth));

   // World width, in squares. Always 100 wide.
   worldWidth = 32 * 3;
   worldHeight = (int) Math.floor(viewHeight);
   
   setViewport(new StretchViewport(viewWidth,viewHeight));
}

initViewport() is an abstract method, so you have no choice but to implement it.

Our first two lines are to set the width and height of our viewport.

float viewWidth =32;
float viewHeight = Math.round(Gdx.graphics.getHeight()/(Gdx.graphics.getWidth()/viewWidth));

The extra logic there is to maintain the ratio we want.

The next two lines are to set the size of the actual world that the player walks around in.

worldWidth = 32 * 3;
worldHeight = (int) Math.floor(viewHeight);

That *3 means that the world is going to be three times larger than the size of the viewport. If you want to prove that to yourself – set the worldWidth to just be 32, and you will see that it is the same size as the viewport.

Try fiddling with these variables and see the effects it creates. The wider your view, the further out you are zoomed.

Finally, all that’s left to do is create and set the viewport so the game knows about it.

setViewport(new StretchViewport(viewWidth,viewHeight));

What about the camera?

The StretchViewport creates its own instance of a camera – an OrthographicCamera.

An OrthographicCamera is one which projects 3D images into 2D. This image from Wikipedia should hopefully show you what is meant by that:

By Yuri Raysper - Has drawn from the bookThis vector image was created with Inkscape., Public Domain, https://commons.wikimedia.org/w/index.php?curid=1484146
By Yuri Raysper – Has drawn from the book This vector image was created with Inkscape., Public Domain, https://commons.wikimedia.org/w/index.php?curid=1484146

So it is good for 2D games – in the case of 3D games (outside the scope of this tutorial series), it would not be used.

All we want this camera to do is follow the player, to always be looking down on him. Therefore, we need a reference to this camera and then to update it every time the player moves.

PlayerInputSystem

When we create our PlayerInputSystem, we create a reference to the camera:

public PlayerInputSystem(MainScreen screen) {
		this.screen = screen;
		camera = (OrthographicCamera) ZombieGame.getViewport().getCamera();
	}

Now, we can update it when we want.

Why do we keep our reference in the PlayerInputSystem? This is so we can directly access the camera when pressing buttons. For example:

@Override
public boolean keyDown(int keycode) {
   if (keycode == Keys.R) {
      screen.gameController.createMap();
      screen.gameController.setRunning(true);
   }
   else if (keycode == Keys.Q) {
      screen.gameController.endGame();
   }
   
   float moveAmount = 1.0f;
   
   if (keycode == Keys.UP) {
      camera.position.y += moveAmount;
   } else if (keycode == Keys.DOWN) {
      camera.position.y -= moveAmount;
   } else if (keycode == Keys.LEFT) {
      camera.position.x -= moveAmount;
   } else if (keycode == Keys.RIGHT) {
      camera.position.x += moveAmount;
   } else if (keycode == Keys.Z) {
      camera.zoom += moveAmount;
   } else if (keycode == Keys.X) {
      camera.zoom -= moveAmount;
   }
   
   updateCamera();
   
   return false;
}

You may recognise this as code we were playing with in the first round of tutorials. This is why we have the camera here – however, you may choose to move it. It slightly irritates me having the camera here, as the PlayerInputSystem class should deal with input and nothing else. It may move in a future tutorial.


Aside: You may have also noticed that this code doesn’t work any more. I can’t zoom! I can’t navigate left and right! Is it broken? Actually, every time the game updates now, it centres the camera above the player. So this code runs, but you never see the effects of it. To get it working again, comment out everything in the updateCamera() method. Though this will, of course, stop the camera from centering over the player.


UpdateCamera() is where the action happens:

public void updateCamera() {
   if (camera == null || camera.position == null || getPlayer() == null) {
      return;
   }

   camera.position.x = getPlayer().getX();
   camera.position.y = getPlayer().getY();

}

We have a bit of code safety first, just to make sure we aren’t going to null-pointer before we’ve set up all our objects.

Then we simply set the camera’s location to be that of the player. We don’t need to worry about translating this into the correct on-screen co-ordinate, because the viewport deals with that for us.

Finally

That is pretty much it for now! The final thing I wanted to highlight was the viewport’s project/unproject functionality, which makes converting from screen co-ordinates to map co-ordinates very easy. I already wrote about this in the previous tutorial – go back to it if you missed it – but I wanted to highlight that this is another positive for the viewport.



If you like these tutorials, or want to see a game that was written in much the same way, please download Dinowar from the Google Play Store. It costs nothing and is ad-free.

Moving a character around the map 3 – Input Processing


Code for this tutorial is on this git branch:

git clone -b First_signs_of_movement https://dglencross@bitbucket.org/dglencross/zombiegametutorial.git

Have a look here for help setting it up


Next we turn to the PlayerInputSystem, our class which implements Libgdx’s InputProcessor.

When we touch the screen, we want the following to happen:

  • Detect the co-ordinates of the screen that we touched/clicked
  • Convert these to map co-ordinates
  • Work out which tile we have touched based on these map co-ordinates
  • Implement some basic logic to stop you touching off-map

ZombieGamePlayerOnScreen

Most of this logic is built-in to Libgdx. When you touch/click the screen, the method touchDown() is called. Let’s take a look at our implementation:

@Override
public boolean touchDown(int screenX, int screenY, int pointer, int button) {

   if (!screen.gameController.isRunning()) {
      return false;
   }

   currentTouch.x = screenX;
   currentTouch.y = screenY;
   
   convertScreenToWorldCoordinates(currentTouch);

   int x = (int) currentTouch.x;
   int y = (int) currentTouch.y;

   Pair selectedTile = screen.gameController.getWorld().getMap()[x][y];
   /*
    *
    * Pretty much all commands are done here...
    *
    */

   getPlayer().setDestination(selectedTile);

   return false;

}

First up, we check if the game is running. If not, we do nothing. What does this mean? Basically we just want to make sure input is not processed before we’re ready for it. We try to access elements of our map – what if we haven’t created it yet? This is just a precaution for that.

Next, we create a vector and pass it off to be converted:

convertScreenToWorldCoordinates(currentTouch);

Let’s take a look at that method:

private Vector3 convertScreenToWorldCoordinates(Vector3 touch) {
   ZombieGame.getViewport().unproject(touch);
   
   if (touch.x < 0 ){
      touch.x = 0;
   } else if (touch.x > screen.gameController.getWorld().getWidth()) {
      touch.x = screen.gameController.getWorld().getWidth();
   }

   if (touch.y < 0) {
      touch.y = 0;
   } else if (touch.y > screen.gameController.getWorld().getHeight()) {
      touch.y = screen.gameController.getWorld().getHeight();
   }

   return touch;
}

The core part of this is just the unproject() method call. This is built into Libgdx and according to the documentation: “Transforms the specified screen coordinate to world coordinates.”

Next, we make sure the co-ordinates not off-map. You may have noticed that you cannot make the player character walk off the map. In fact, you can never set its destination to be off-map. This is where we make sure of that.

Now we return to touchDown():

int x = (int) currentTouch.x;
int y = (int) currentTouch.y;

Pair selectedTile = screen.gameController.getWorld().getMap()[x][y];

We convert to ints so that we can directly access the tiles of the map, and we ask for the tile (Pair) corresponding to those co-ordinates.


Aside: you might want to round these floats first before casting them to ints. I didn’t bother – but keep in mind that casting from float to int isn’t quite the same as rounding – it doesn’t round to the nearest number, it just discards everything after the decimal point. If your game requires this precision, use Math.round() first.


Now we’ve got a Pair to work with. In Dinowar, we next have a bunch of logic depending on which Pair you’ve clicked. Did you select your a tile belonging to your own base? Did you select a tile belonging to an opponent’s base? Did you touch water? Depending on all these, different logic is applied.

Move dinosaurs around based on which tile was touched
Move dinosaurs around based on which tile was touched

For us now, all we want to do is tell the player where to go:

/*
 *
 * Pretty much all commands are done here...
 *
 */

getPlayer().setDestination(selectedTile);

In later tutorials, we’ll flesh out the logic here. What if you touch a zombie? Maybe we should fire a bullet in that situation, rather than walk towards it.

Now you’ve got an idea of how we’re selecting where to move around the map. Next up, we’ll take a look at the camera and viewport, to make sure that we always track the player’s movement.



If you like these tutorials, or want to see a game that was written in much the same way, please download Dinowar from the Google Play Store. It costs nothing and is ad-free.