Artificial Intelligence II – Pursuing behavior

Hello again! As promised, here I am with another cool AI implementation. In my last post I introduced you into the gdxAI framework and tried to explain how to use the Arrive behavior.

Before getting into the subject, I’d like to say thank you to Nyanla La Geekette nee-chan, who made this awesome character design for me ^^:

I invite you all to visit her blog, and remember that you can collaborate with your own art contacting me or leaving a comment in the art page.

Returning to Steering Behaviors, today I’m working with the pursuing behavior, which allows me to finally add mobs into the game. 😀

I temporally chose this eyed-spaghetti monster from this source because it is a chibi mixture of FSM and a Great Old One. It is the very first mob on the game, and its first mission consists in pursuing the kittens.

monsters
Hi!

 

Overview

How would you make an entity follow another entity? Think a moment about it before reading the reasoning below.

Visualize two characters: the mob and the kitten. The mob should go to the kitten as fast as possible. In our Euclidean world, the shortest path between two points is a straight line. Therefore, the mob should follow a straight path towards the kitten.

shortestdistance

In LibGDX, this path is delineated by Rays, which are vectors linking a starting point to a destination point.

However, we should consider that there may be obstacles along the way, like walls, rocks, holes… Let’s list the rules:

– If we throw a ray from the mob to the kitten, and it does not collide, then the mob can move straight towards the kitten.

 

– If the ray collides, then the mob should look for an alternative path to reach the target. The best solution I found was this one, based on what the author calls “smell trails”.

 

Smell trails

Definition

Briefly explained, such algorithm consists on the idea that the target leaves smell trails in the ground as he walks. If the kitten hides behind a wall, the mob will not be able to see him directly, instead, the mob checks the smell trail left by the kitten and goes to the last visible trail.

smelltrail

As the time goes by, the smell fades away, so eventually the mob will lose the trail.

nosmelltrail

Implementation

Before considering the hunter, think about the prey. Every potential target must be a Steerable agent (explained in my previous post) and be composed by a Pursuable field.

Pursuable is the class that will store and provide the methods to access the SmellTrails:

SmellTrails class keeps an array of the trails, and handles the changes on the path. For instance, it will remove the trails that are too old to be detected:

Recovering the last rule enumerated, “If the ray collides, then the mob should look for an alternative path to reach the target”, the mob will look at the smell trail left by his target and set that position as his new target:

The mob will start moving towards the last smell trail until the next steering calculation loop. Then, he will try again to reach the kitten and repeat the calculations.

 

Last rule and rules summary

There’s only one rule left:

– If the mob can’t see the kitten neither through a straight line nor through a trail, then he will stop following the target.

Summarized:

 

Brave new world

If the ray drawn by the mob collides with an obstacle, the mob should implement a different behavior. But, how can I actually know if the ray is colliding with an obstacle?

To solve this issue I created a tile manager.

The game’s world has completely changed, and now it’s more alive and dangerous than ever!

Now, the world consists in a TiledMap. The ground is divided in 32X32 squares, named “tiles”. Each tile has its own properties. For instance, there could exist grass tiles, where you can walk; water tiles, where you can dive; sand tiles, where you will be slowed down; wall tiles, which you cannot walk through; hole tiles, where you will fall, etc.

Tile map example
Tile map example

 

This factory creates different types of tiles for me, which I can later add to the Map:

 

Ray collision

Sorry for that little subsection, but it is going to be helpful to explain how collisions are managed.

Because now that we control each tile of the world, it’s easy to know if the ray launched by the mob is encountering any collisionable obstacles in its way. Using the Bresenham’s algorithm, we will get a list of tiles existing inside the line. Then, we just check if there are any collisionable tiles in the returned list:

Where:

I implemented the RaycastCollisionDetector interface, and used this Bresenham’s algorithm implementation. Here’s the complete result.

 

Putting everything together

Now we can follow all the process from the hunter’s perspective.

1. The mob is an Automaton that has a Target:

2. When setting the target, he also acquires a Pursue behavior:

3. The prey is a SteerableAgent that keeps a temporary smell trail:

4. The mob executes the calculatesteering method of his SteeringBehavior in a loop:

5. The calculateSteering method of the Pursue behavior calculates if there is any path available and makes the mob stop if there isn’t.

And this is how it works. You can read the complete version on this commit.

 

Wall repulsion

To be honest, I had a problem during the implementation, and the game looks a bit buggy at the moment. The mob follows the kitten correctly, but every time he crashes with a wall in the way, he stays stuck and doesn’t follow the kitten anymore.

After several debugs, I realized that the mob is getting into the wall, and obviously, all the rays that comes from him from that moment on, collide with the same wall that is trapping him. Thus, he is not able to pursue the kitten anymore.

To prevent this to happen, the mob must dodge the walls. It’s a bit frustrating but at the same time it is such a good moment to start working with simultaneous behaviors. I will try to make the mob pursue the kitten and, at the same time, avoid the walls.

Be aware of my next post if you’re curious! Thanks for reading ^^ Please, don’t forget to share, comment and subscribe. See you soon!

#FightingKittenBlog

Facebooktwittergoogle_plusredditpinterestlinkedintumblrmail

3 thoughts on “Artificial Intelligence II – Pursuing behavior

Add yours

  1. while (iterator.hasNext())
    {
    smellTrail = iterator.next();
    smellTrail.duration += delta;

    if (smellTrail.duration > smellTrailDecayTime)
    {
    iterator.remove();
    }
    }
    … Will lead to concurrent modification exception or even in some cases index out of bounds exception. It is better to make a new/copy map/list and add the resulting elements to it. Then, use that map as a final collection in your code.

  2. Yay, my little picture is up! Thanks for the link nee-chan :3
    About your post: wow. I literally understood nothing xD It’s amazing what we can do with technology today, although I think I’ll stay on the receiving end and not on the creating one 😉

Leave a Reply

Your email address will not be published. Required fields are marked *

Proudly powered by WordPress | Theme: Baskerville 2 by Anders Noren.

Up ↑