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

106 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
  7. Thanks for your article. Its coding is very useful to me. Thank You...Java Training in Chennai
    Java Training Institude in Chennai

    ReplyDelete
  8. ... 6 years later :)
    Hi, I'm trying to code your nice RogueLike using Monogame (c#). I think your createCreatures (PlayScreen) have a little gameplay problem. I imagine that you would like to add Zombies only at depth 3 and above, so for my part I'd prefer the implement that :

    for (int i = 0; i < z - 2; i++)
    factory.NewZombie(z, player);

    I used z - 2 instead of z + 3 (so zimbie start to be seed at depth 3).

    ReplyDelete
  9. http://ttminstitute.blogspot.com/2007/10/what-is-tiit-ttm-institute-of.html

    ReplyDelete
  10. This comment has been removed by the author.

    ReplyDelete
  11. Nice! you are sharing such helpful and easy to understandable blog in decoration. i have no words for say i just say thanks because it is helpful for me.

    robotic process automation companies in us
    Robotic Process Automation in us
    machine maintanance in us
    erp in chennai
    mobility software companies in chennai
    erp providers in us

    ReplyDelete
  12. professional bridal makeup artist in chennai Style Specializes in beauty bridal makeup and makes assured that individual bride should look like a princess.

    best bridal makeup artist in chennai

    ReplyDelete
  13. Soma pill is very effective as a painkiller that helps us to get effective relief from pain. This cannot cure pain. Yet when it is taken with proper rest, it can offer you effective relief from pain.
    This painkiller can offer you relief from any kind of pain. But Soma 350 mg is best in treating acute pain. Acute pain is a type of short-term pain which is sharp in nature. Buy Soma 350 mg online to get relief from your acute pain.

    https://globalonlinepills.com/product/soma-350-mg/


    Buy Soma 350 mg
    Soma Pill
    Buy Soma 350 mg online



    Buy Soma 350 mg online
    Soma Pill
    Buy Soma 350 mg

    ReplyDelete
  14. I gathered a lot of information through this article.Every example is easy to undestandable and explaining the logic easily.selenium training in bangalore

    ReplyDelete
  15. It’s really great information Thanks for sharing.

    Best Manual Testing Training in Bangalore, BTM layout. My Class Training Academy training center for certified course, learning on Manual Testing Course by expert faculties, also provides job placement for fresher, experience job seekers.

    ReplyDelete
  16. Really it was an awesome article,very interesting to read.You have provided an nice article,Thanks for sharing.salesforce developer training in bangalore

    ReplyDelete
  17. Thanks for sharing this blog. This very important and informative blog.dot net training in bangalore

    ReplyDelete
  18. It’s really great information for becoming a better Blogger. Keep sharing, Thanks...

    Bangalore Training Academy located in BTM - Bangalore, Best Informatica Training in Bangalore with expert real-time trainers who are working Professionals with min 8 + years of experience in Informatica Industry, we also provide 100% Placement Assistance with Live Projects on Informatica.

    ReplyDelete
  19. Thank you so much for the great and very beneficial stuff that you have shared with the world.

    Become an Expert In Python Training! The most trusted and trending Programming Language. Learn from experienced Trainers and get the knowledge to crack a coding interview, @Softgen Infotech Located in BTM Layout.

    ReplyDelete
  20. Really very happy to say, your post is very interesting to read. I never stop myself to say something about it. You’re doing a great job. Keep it up...

    Upgrade your career Learn AWS Training from industry experts get Complete hands-on Training, Interview preparation, and Job Assistance at Softgen Infotech Located in BTM Layout.

    ReplyDelete
  21. Enjoyed reading the article above, really explains everything in detail,the article is very interesting and effective.Thank you and good luck…

    Start your journey with DevOps Course and get hands-on Experience with 100% Placement assistance from experts Trainers @Softgen Infotech Located in BTM Layout Bangalore.

    ReplyDelete
  22. That was really a great Article. Thanks for sharing information. Continue doing this.

    Real Time Experts provides Best SAP PM Training in Bangalore with expert real-time trainers who are working Professionals with min 8+ years of experience in Java Training Industry, we also provide 100% Placement Assistance with Live Projects on Java Training

    ReplyDelete
  23. such a great word which you use in your article and article is amazing knowledge. thank you for sharing it.

    Start your journey with AWS Course and get hands-on Experience with 100% Placement assistance from Expert Trainers with 8+ Years of experience @eTechno Soft Solutions Located in BTM Layout Bangalore.

    ReplyDelete
  24. Such a great information for blogger i am a professional blogger thanks…

    Softgen Infotech is the Best HADOOP Training located in BTM Layout, Bangalore providing quality training with Realtime Trainers and 100% Job Assistance.

    ReplyDelete
  25. This comment has been removed by the author.

    ReplyDelete
  26. GrueBleen – One of the best social media marketing agency in Riyadh- Saudi Arabia. Visit here for the all service details of GrueBleen.
    Social Media Marketing Agency

    ReplyDelete
  27. Agriculture Solutions – Taldeen is a plastic manufacturing company in Saudi Arabia. They are manufacturing agricultural plastic products like greenhouse cover and hay cover. Visit the below link to know more details
    Agriculture Solutions
    Greenhouse Cover

    ReplyDelete
  28. GrueBleen – One of the best branding and marketing agency in Riyadh- Saudi Arabia. If you need the details, click the below link
    Branding Agency Riyadh
    Marketing Agency Riyadh

    ReplyDelete
  29. BSc in Optometry – Here is the details about Best BSc Optometry Colleges In Bangalore. If you are looking to study in Bangalore, the below link will redirect to a page that will show the best OPT colleges in Bangalore. If you are looking to study BSc Optometry in Bangalore, click the below link.
    Optometry Colleges In Bangalore

    ReplyDelete
  30. BSc Cardiac Care Technology – Here is the details about Best BSc Cardiac Care Technology Colleges In Bangalore. If you are looking to study in Bangalore, the below link will redirect to a page that will show the best BCC colleges in Bangalore
    BSc Cardiac Care Technology Colleges In Bangalore

    ReplyDelete
  31. BBA Aviation – One of the most demanding management course in recent times. Here is the details of Best BBA Aviation colleges in Bangalore. If you are looking too study in Bangalore, visit the below link.
    BBA Aviation Colleges In Bangalore

    ReplyDelete
  32. BSc Perfusion Technology – If you are looking to study BSc Perfusion Technology in Bangalore, just check out the following link. In that link you can get the details of Best BSc Medical Imaging Technology colleges in Bangalore
    BSc Perfusion Technology Colleges in Bangalore

    ReplyDelete
  33. BMIT – BSc Medical Imaging Technology – Here is the details about Best BSc Medical Imaging Technology Colleges In Bangalore. If you are looking to study in Bangalore, the below link will redirect to a page that will show the best BMIT colleges in Bangalore
    BSc Medical Imaging Technology Colleges In Bangalore

    ReplyDelete
  34. I have been more or less playing around with different paths for myself in my head and one of the new ones is to become a blogger.
    ExcelR Digital Marketing Courses In Bangalore

    ReplyDelete
  35. Thanks for sharing such a great information..Its really nice and informative..

    sap bi training

    ReplyDelete

  36. Very nice job... Thanks for sharing this amazing and educative blog post! Digital Marketing Course Pune

    ReplyDelete
  37. I just got to this amazing site not long ago. I was actually captured with the piece of resources you have got here. Big thumbs up for making such wonderful blog page!. digital marketing course Bangalore

    ReplyDelete
  38. Whatever we gathered information from the blogs, we should implement that in practically then only we can understand that exact thing clearly, but it’s no need to do it, because you have explained the concepts very well. It was crystal clear, keep sharing....

    sapui5 online training

    ReplyDelete
  39. I can see that you are an expert at your field! I am launching a website soon, and your information will be very useful for me.. Thanks for all your help and wishing you all the success in your business.satta king

    ReplyDelete
  40. With the help of creative designing team TSS advertising company provides different branding and marketing strategies in advertising industry...
    https://www.tss-adv.com/branding-and-marketing

    ReplyDelete
  41. Welcome to the party of my life here you will learn everything about me.
    Digital Marketing Courses in Pune

    ReplyDelete
  42. Needed to compose you a very little word to thank you yet again regarding the nice suggestions you’ve contributed here.

    Python Training
    Digital Marketing Training
    AWS Training

    ReplyDelete
  43. This is a splendid website! I"m extremely content with the remarks!.
    ExcelR Solutions

    ReplyDelete
  44. Other content online cannot measure up to the work you have put out here. Your insight on this subject has convinced me of many of the points you have expressed. This is great unique writing.
    Best Data Science training in Mumbai

    Data Science training in Mumbai

    ReplyDelete
  45. GrueBleen Creative Club - Digital Marketing is booming now. People & Brands are engaging Social Media for content creation alike. People are focusing to share their beautiful moments on Social Media. But, Brands are creating post for their product or service and Social Commitment alike. Brands are choose Social Media Agencies for their trust creation in Digital Media. Here, is the details that provided by GrueBleen Creative Club, Riyadh.
    Branding Agency Riyadh
    Marketing Agency Riyadh
    Digital Marketing Agency Riyadh
    Digital Marketing Agency Saudi Arabia
    Digital Marketing Agency Jeddah
    Social Media Agency Riyadh
    Social Media Agency Jeddah
    Social Media Agency Saudi Arabia
    Branding Agency Jeddah
    Marketing Agency Jeddah
    Marketing Agency Saudi Arabia
    Branding Agency Saudi Arabia

    ReplyDelete
  46. It's really a nice and useful piece of information about Selenium. I'm satisfied that you shared this helpful information with us.Please keep us informed like this. Thank you for sharing.

    Java training in chennai | Java training in annanagar | Java training in omr | Java training in porur | Java training in tambaram | Java training in velachery

    ReplyDelete
  47. It is actually a great and helpful piece of information about Java. I am satisfied that you simply shared this helpful information with us. Please stay us informed like this. Thanks for sharing.
    Java training in chennai | Java training in annanagar | Java training in omr | Java training in porur | Java training in tambaram | Java training in velachery

    ReplyDelete
  48. Not many writers can persuade me to their way of thinking. You've done a great job of doing that on many of your views here.
    SAP training in Kolkata
    SAP training Kolkata
    Best SAP training in Kolkata
    SAP course in Kolkata
    SAP training institute Kolkata

    ReplyDelete
  49. I like viewing web sites which comprehend the price of delivering the excellent useful resource free of charge. I truly adored reading your posting. Thank you!...digital marketing courses in bangalore

    ReplyDelete
  50. Very interesting blog Thank you for sharing such a nice and interesting blog and really very helpful article.

    Dell Boomi Training in Bangalore

    Best Dell Boomi Training Institutes in Bangalore

    ReplyDelete