Friday, September 30, 2011

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

7 comments:

  1. I can't seem to get this to work, I get the following error in the Pathfinding class;
    java.lang.StackOverflowError
    at java.util.HashMap.get(Unknown Source)


    It seems to be getting stuck on the costToGetTo() method, any ideas on what is causing it to error out?

    ReplyDelete
    Replies
    1. A StackOverflowError is usually caused by a recursive function going haywire and not terminating. I'm guessing that some point is the parent of itself but I'm not sure what to do without the code you're running. Have you looked at other implementations? A* pathfinding is a simple enough idea that you could probably swap this implementation for another. I tried to keep the pathfinding stuff completely unaware of the World and that really shaped the implementation. It turns out that's not good for performance, debugging, or overall clarity.

      Delete
  2. Hi thanks for getting back to me. The code is exactly the same as what you have here except I've taken out the z level stuff as well as casted some floats to ints and vice versa. I've been following the tutorials here; http://randomtower.blogspot.co.uk/ and I wanted to see if I could put pathfinding in by seeing how you did it.

    What other pathfinding algorithms would you recommend if I were to use something else other then A*, this is really my first time I've played around with pathfinding.

    ReplyDelete
  3. I had a weird NullPointerException pop up in the Zombie AI.

    In the method

    public void hunt(Creature target)
    {
    ArrayList 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);
    }

    the line int mx = points.get(0).x - creature.x; threw it. I was in the bottom floor and almost everything was surrounded by fungus, including the zombie I aggrod. Do you think it was just that there were no points for it to move to, so it threw the exception? I'm personally thinking that's what caused it but haven't been able to get it to throw again.

    ReplyDelete
  4. I'm guessing that the points is null; probably because findPath couldn't find a way to the player so it returns null after a while (300 tries I think). The hunt method should return if points is null or has a length of zero.

    ReplyDelete
  5. The principles have been well cited above and surely would even proved to be much better for them to proceed further with all those instances and the values which are indeed said to be important.

    ReplyDelete
  6. Because you calculate a new path on every onUpdate call (given a monster can see a player), you are solely relying on an heuristic function of A* algorithm. You might as well drop A*, unless you make the monster to calculate a path once and update it if necessary (on player's move).

    You have to at least check if a path that you get in hunt method is not null, otherwise you could get some unexpected behaviour.

    ReplyDelete