roguelike tutorial 13: aggressive monsters

Now that we have all these cool weapons and armor and food, the bat's and fungi aren't as troublesome as they used to be. We need something that charges straight for us, something that peruses us relentlessly, a simple minded foe that we don't want to run into. For that we need a way to find a path to the player.

The monsters are only going to pathfind to the player if they see him so we could do the simpleist thing and move east if the player is east, north if the player is north, etc. That would almost always work well enough but let's go ahead and add real path finding. Entire tutorials are written about path finding but for this we can use the following code that implements the A Star algorithm and is specialized for our creatures:

package rltut;

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

public class PathFinder {
       private ArrayList<Point> open;
       private ArrayList<Point> closed;
       private HashMap<Point, Point> parents;
       private HashMap<Point,Integer> totalCost;
     
       public PathFinder() {
             this.open = new ArrayList<Point>();
             this.closed = new ArrayList<Point>();
             this.parents = new HashMap<Point, Point>();
             this.totalCost = new HashMap<Point, Integer>();
       }
     
       private int heuristicCost(Point from, Point to) {
             return Math.max(Math.abs(from.x - to.x), Math.abs(from.y - to.y));
       }

       private int costToGetTo(Point from) {
             return parents.get(from) == null ? 0 : (1 + costToGetTo(parents.get(from)));
       }
     
       private int totalCost(Point from, Point to) {
             if (totalCost.containsKey(from))
                 return totalCost.get(from);
           
             int cost = costToGetTo(from) + heuristicCost(from, to);
             totalCost.put(from, cost);
             return cost;
       }

       private void reParent(Point child, Point parent){
             parents.put(child, parent);
             totalCost.remove(child);
       }

       public ArrayList<Point> findPath(Creature creature, Point start, Point end, int maxTries) {
             open.clear();
             closed.clear();
             parents.clear();
             totalCost.clear();
       
             open.add(start);
           
             for (int tries = 0; tries < maxTries && open.size() > 0; tries++){
                   Point closest = getClosestPoint(end);
                 
                   open.remove(closest);
                   closed.add(closest);

                   if (closest.equals(end))
                         return createPath(start, closest);
                   else
                         checkNeighbors(creature, end, closest);
             }
             return null;
       }

        private Point getClosestPoint(Point end) {
            Point closest = open.get(0);
            for (Point other : open){
                if (totalCost(other, end) < totalCost(closest, end))
                    closest = other;
            }
            return closest;
        }

        private void checkNeighbors(Creature creature, Point end, Point closest) {
            for (Point neighbor : closest.neighbors8()) {
                if (closed.contains(neighbor)
                 || !creature.canEnter(neighbor.x, neighbor.y, creature.z)
                 && !neighbor.equals(end))
                     continue;
    
                if (open.contains(neighbor))
                    reParentNeighborIfNecessary(closest, neighbor);
                else
                    reParentNeighbor(closest, neighbor);
            }
        }

        private void reParentNeighbor(Point closest, Point neighbor) {
            reParent(neighbor, closest);
            open.add(neighbor);
        }

        private void reParentNeighborIfNecessary(Point closest, Point neighbor) {
            Point originalParent = parents.get(neighbor);
            double currentCost = costToGetTo(neighbor);
            reParent(neighbor, closest);
            double reparentCost = costToGetTo(neighbor);
  
            if (reparentCost < currentCost)
                open.remove(neighbor);
            else
                reParent(neighbor, originalParent);
        }

        private ArrayList<Point> createPath(Point start, Point end) {
            ArrayList<Point> path = new ArrayList<Point>();

            while (!end.equals(start)) {
                path.add(end);
                end = parents.get(end);
            }

            Collections.reverse(path);
            return path;
        }
    }

So far I've liked having Points and Lines where all the work is done in the constructor and would like to extend this idea to Paths. So let's create a Path class that hides the details from us.

package rltut;

import java.util.List;

public class Path {

  private static PathFinder pf = new PathFinder();

  private List<Point> points;
  public List<Point> points() { return points; }

  public Path(Creature creature, int x, int y){
      points = pf.findPath(creature, 
                           new Point(creature.x, creature.y, creature.z), 
                           new Point(x, y, creature.z), 
                           300);
  }
}

If having our Line path do all that work in the constructor was questionable then this is far more questionable. I may end up regretting this and making sure future employers never see this but for now I'll try it and we'll see if it becomes a problem.


Like with our other creatures we need a CreatureAi. I'll take the easy and uncreative way out and pick Zombies for our new monster. The ZombieAi will be a bit different than the others since it needs a reference to the player so it knows who to look for.

package rltut;

import java.util.List;

public class ZombieAi extends CreatureAi {
  private Creature player;

  public ZombieAi(Creature creature, Creature player) {
    super(creature);
    this.player = player;
  }
}

During the zombie's turn it will move to the player if it can see him, otherwise it will wander around. Since zombies are a little slow, I gave them a chance of doing nothing during their turn for just a little bit of interest.

public void onUpdate(){
      if (Math.random() < 0.2)
          return;
  
      if (creature.canSee(player.x, player.y, player.z))
          hunt(player);
      else
          wander();
  }

Creating a new path each turn may not be the best idea but we'll only have a few zombies and rogulikes are turn based so it shouldn't be too much of a problem. If it does be come a performance problem we can fix it.

The hunt method finds a path to the target and moves to it.

public void hunt(Creature target){
      List<Point> points = new Path(creature, target.x, target.y).points();
  
      int mx = points.get(0).x - creature.x;
      int my = points.get(0).y - creature.y;
  
      creature.moveBy(mx, my, 0);
  }

Now we can add zombies to our factory. Since the Ai needs a reference to the player, we have to pass that in.

public Creature newZombie(int depth, Creature player){
      Creature zombie = new Creature(world, 'z', AsciiPanel.white, "zombie", 50, 10, 10);
      world.addAtEmptyLocation(zombie, depth);
      new ZombieAi(zombie, player);
      return zombie;
  }

To add zombies to our world we need to update createCreatures in the PlayScreen.

for (int i = 0; i < z + 3; i++){
         factory.newZombie(z, player);
     }

Adding pathfinding to a game is a big deal. The PathFinder we're using for now is good enough but has some major inefficiencies. I'm using a HashMap of points rather than an array so we don't have to worry about the world size or anything like that. This will take up less memory and handle aarbitrarily large maps but it will be much much slower.

download the code