Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 21 Aug 2010
Offline Last Active Jul 19 2013 02:19 PM

#5065659 My Take on Monster AI (Part 4 of 5)

Posted by on 28 May 2013 - 05:53 PM

YouTube video demonstration for Part 4:

Part 4 Interactive demo can be found at:

Interactive demos for previous parts are at the usual place:

Part 4: Group Behaviours and Ranged Attacks

In Part 2 (Retreating) we briefly touched on how Fire Imps in each other's line of sight were connected as a group, and that they would share alert levels. Today, I'm going to explain a little bit more about how this group movement actually works - and also introduce a new monster to the pack: The Skeleton Archer, with its Ranged Attacks. Combine Archers and Skeletons together and you have quite a challenging group of foes to deal with.

Group Chasing Behaviours in Detail

Let's break this group chasing behaviour down:

1. Detection Phase. For each frame (more specifically each iteration of the Behaviour Tree), the monster maintains 2 lists: threats (you), and friendlies (other skeletons) - based on line of sight. Entities that cannot be seen are not included in this list. The lists are cleared at the beginning of each iteration. In addition to these, breadcrumbs dropped by both threats and friendlies are also recorded. In future versions, things like visible furniture, entrances and exit doors, walls etc... will also be added. By this point, the monster now has a reasonable view of the world on this exact frame, and we use this information to help the AI determine what to do next.

2. Intention Phase. This is where the Behaviour Tree comes in handy - to aid in the decision making process. We'll not cover the specifics of the Behaviour Tree implementation here - the details are too numerous and will best fit in a future post. For an overview of Behaviour Trees, AIGameDev covers this particularly well: http://aigamedev.com/open/article/bt-overview/

So, conceptually speaking, our tree models a list of ordered priorities: A. Deal with threats, B. Follow alerted friendlies, C. Patrol. The first one we've already covered in Part 1: monsters chase after players in their line of sight, then breadcrumbs (smell trail), then to the target's last recorded location. If these actions fail - the next branch (priority) of the tree is parsed and the monster has a look at what the friendlies are up to. If his friends are alerted, this state is passed on and the monster becomes alerted also. He then proceeds to follow the alerted friend in the same way as in priority A (again line of sight, breadcrumbs, and last recorded location). If this fails also (there are no alerted friends visible), then we fall back to patrol (with best guess).

Priority B is particularly important - it allows the monsters to follow each other in a chain/queue-like fashion. As long as the leader of the pack is alerted and can see the enemy, this state and behaviour is propagated to other mobs down in the chain. There's some bugs and caveats to this method, one of them is that it's easy for the monsters to chase each other in a loop (or pairs), so there's some failsafe hackery code to stop this from happening. This is WIP, we plan on cleaning up this behaviour during production.

3 . Movement Phase. Simply apply the intentions above to actual movement (modify velocities, update positions, repel from walls, separate from nearby entities etc..)

Skeleton Archers and Ranged Attacks in Detail

This is where the Behaviour Trees really shine. Because we've already defined a lot of the basic maneuvers described in Part 1, 2 & 3 as behaviour nodes we can now mix and match them to create new behaviours in our tree. A good example, is the Skeleton Archer. In our tree, there is a conditional node that switches between Chasing Behaviours (from Part 1) and Retreating Behaviours (Part 2). The condition is a whether the distance from the monster to the player is above or below 2 thresholds. To illustrate, we might have an Archer chase the player if it is 100 units away, but flee from the player if it is less than 50. The gap between the 50 and 100 threshold is to ensure we don't rubber band between the two states too quickly, so if the distance is 75 units, we remain in the current state.

So the resulting behaviour is that the Archer maintains a nice position away from you: never to engage in melee combat but always close enough to use his bow and arrow.


Apart from the new Archer behaviours, there's no special code to formulate groups here. It just so happens that a combination of melee type Skeletons (who are extremely aggressive and will chase you down as much as possible) and ranged Archers (who are cautious and will try to maintain a certain distance from you) results in quite effective emergent behaviour - it almost looks like they are working together.

More Ideas for Group AI

The above shows very basic, fundamental rules for group interaction. It's a work in progress - but we plan on bringing more complex manoeuvres in regards to group tactics. Depending on the monster type, critters will be able to do the following:

- Monsters won't attack if they are alone, and will flee instead. Some intelligent ones will flee towards a known group of other monsters. This results in luring, pulling the character towards a more dangerous area and then attacking again.
- Wounded skeletons prefer to escape while their friends are locked in battle - to go and find corpses, heal, and return to the fray later.
- Leaders - if a Skeleton King is in the area, his minions will tend to follow and do what he does.
- Flanking - if the player is currently engaged in battle, other monsters will attempt to flank you from either side or behind.

A plea for help for the next two days

As some of you may already know - my game TinyKeep is on Kickstarter and there are currently only 2 days left of funding to go! If you enjoy reading these kinds of technical articles, please consider pledging so I can continue active development of the game. Currently I have accrued over half the amount I need (~70%), but as Kickstarter is all or nothing I need to make the full £22k or I lose all my pledges so far. If I get funded, I plan to keep on releasing articles on all aspects of the game's development, including AI but also game mechanics, procedural generation, multiplayer networking, 3D graphics & animation, performance optimization, workflow, physics, collision detection - and everything in between! I don't claim to be an expert on all of these subejcts - this is just my journey in the world of game development, but I hope beginners out there will find inspiration from this. So please help if you can!

#5064175 My Take on Monster AI (Part 3 of 5)

Posted by on 23 May 2013 - 09:43 AM

Interactive demos for all parts are at the usual place:
Part 3: Hungry Skeletons
YouTube Video:

Today I'm going to talk about some behaviours that are specific to the Skeleton monster. The idea is that while Skeletons are not chasing or pursuing the player, they are always hungry and will seek out corpses to consume. Eating helps the Skeleton regain lost health, and also if left long enough, consumed corpses turn into more undead Skeletons! We build upon all of the behaviours discussed in the previous articles to do this.
The procedure is as follows:
1. The Skeleton is in non-alert mode (character is not in line of sight, and there are no detected breadcrumbs) and so it proceeds to patrolling the waypoints using simple A* pathfinding as before. If while in patrol mode the Skeleton detects a corpse it will set the corpse as its destination and proceed to run directly to it using the Seek Steering Behaviour.
2. If a player is detected, the Skeleton will switch out of this mode and chase the player instead in full alert mode. Skeletons ALWAYS prioritise the player over eating corpses.
3. When the Skeleton reaches the corpse, it will begin eating it. The eaten variable for this corpse increments every frame. While eating, the Skeleton's field of view is reduced to 45 degrees instead of 90, this is to give the impression that the Skeletons are busy eating to notice much else. Also, it is still in non-alert mode and will not smell any breadcrumbs. This opens up gameplay opportunities such as sneaking around a group of Skeletons who are busy munching!
4. When the eaten variable exceeds a certain amount (ie. 200) the corpse is completely consumed. At this point some corpses (such as Orc corpses) turn into more Skeletons! This has the effect of a large cluster of corpses quickly propagating into multiple Skeletons, so the player has to make sure this doesn't happen!
5. At that's it, nice and simple behaviour made possible by combining and tweaking the previous behaviours in a certain way. This is the beauty of behaviour trees, it is quick and easy to create new meta-behaviours by combining the building blocks of the previous ones.
Read more about the benefits of Behaviour Trees at AiGameDev:
The Next Few Days
As some of you may already know - my game TinyKeep is on Kickstarter and there are currently only 7 days left of funding to go! If you enjoy reading these kinds of technical articles, please consider pledging so I can continue active development of the game. Currently I have accrued almost half the amount I need, but as Kickstarter is all or nothing I need to make the full £22k or I lose all my pledges so far. If I get funded, I plan to keep on releasing articles on all aspects of the game's development, including AI but also game mechanics, procedural generation, multiplayer networking, 3D graphics & animation, performance optimization, workflow - and everything in between! So please help if you can!
Have a look at our project for more information:
TinyKeep - A 3D Multiplayer Dungeon Crawler for Windows/Mac

#5063013 My Take on Monster AI (Part 2 of 5)

Posted by on 19 May 2013 - 09:46 AM


Before I crack on to Part 2 (Retreat and defense) I would like to quickly cover the minor improvements we made since Part 1 of this AI series. Thanks to community feedback we've added a few more features, removed others and hopefully will have created more realistic behaviour.

Part 1.1 AI (Improvements) - YouTube Demo:

In short, the changes are:

1. If the Skeleton loses sight (raycasting towards hero) and smell (raycasting towards dropped breadcrumbs), he will still continue to head towards the location where the hero was last detected and investigate further.

2. If the Skeleton still cannot find the hero, it will make a best guess where it thinks he has gone and will set a patrol route to the nearest waypoint. Given these changes, we've removed the alert level as we've found this feature has become redundant and offers no extra intelligence. The "smell trails" have been reduced to balance the extra added behaviour - this also seems to help limit cheating in the AI.

Ok, let's bring on the fun stuff!

AI Explained - Part 2 of 5: Retreating and Defense, featuring TinyKeep's Fire Imp Monster!

Fire Imps (and other monsters marked with the "Shy" personality flag) will run away from the player if he gets too close. Put him in this level of distress for too long, and he'll breathe fire on you.

Part 2 AI - YouTube Demo:

The interactive demo is here on the TinyKeep website along with all of the previous demos:

As with all of these AI behaviours, what you see on the video and demo are the default settings for each of the personality flags (Aggressive, Cautious, Shy, Lumbering etc...). However we've designed our AI editor to be a lot more flexible than that - so our game designer Ben can choose from a multitude of variables to customize his monsters:

  • Enable/disable line of sight (blind monsters)
  • Smell/sound sensitivity (monsters with amazing sense of smell)
  • Roaming speed, chasing speed, fleeing speed
  • Enable/disable wall avoidance (in case some monsters can walk through walls!)
  • Distance threshold before alerted
  • Require line of sight before alerted
  • ...and many more!

We know that this will give us the ability to create really unique and varied monsters, and part of the fun of the game is figuring out the behaviours of each one.

Hope you enjoyed the post, and let us know if you have any questions about the AI!


By the way - thanks for those who recommend I post on the articles section of GameDev, will be doing this as soon as I can.


#5061881 My Take on Monster AI (Part 1 of 5)

Posted by on 14 May 2013 - 03:36 PM

Hey everyone! I decided that I will post more game development articles and videos in the future to inspire the community and also hopefully promote my game TinyKeep (http://tinykeep.com) as well!

This is the first of the multi-part series of updates about TinyKeep's AI, over the next few days I will be posting a series of videos about the monster intelligence system that I've developed for the game. Today I'm going to talk about simple roaming and chasing behaviours for a single monster. For the later parts, I'll progress to more sophisticated concepts such as Group Tactics and Rivalry.

I've posted a detailed YouTube video of the Roaming and Chasing behaviour

In a nutshell, here's how it works:

1 . A connected waypoint graph is calculated for a new procedurally generated dungeon. Generally we will have one waypoint per room (though some larger rooms may contain 2 or 3), and a few waypoints along long corridors.

2 . By default a monster will be in non-alert (roam/patrol) mode, as it's not chasing anything. So, it will use A* (shortest path) pathfinding to travel to randomly selected waypoints in the dungeon.

3 . The monster has a FOV of 90 degrees, and can only detect another entity if it is in within its FOV and direct line of sight (we use raycasting to determine if a nearby enemy is in its direct line of sight).

4 . Once an enemy is detected, it's alert level is increased to 200 and it begins chase. We use the Seek Steering Behaviour on the monster to follow its target.

5 . If the enemy escapes line of sight, the monster is still able to follow it even though it can't see it. It does this by targeting "smell trails" or "breadcrumbs" that the enemy has left behind. Again the monster uses Seek to follow the trail. Most recent trails are detected via line of sight (raycasting) and are tracked first. Trails are not detected if the monster is not in alert mode.

This is the most important part of the AI, as it allows the monster to follow an enemy all around the dungeon even though it can't see its quarry - so if an enemy hides behind a corner the monster can still find him. The best thing about this elegant solution is that it does not need to use any expensive or complicated pathfinding, planning AI or anything like that. Neither does the monster need to have any internal representation of the dungeon layout. The player has done the hard work for the AI, by leaving behind the trail to follow.

6 . Trails decay over time (smells disappear), so eventually the monster will stop following if it hasn't seen the enemy for a while. At this point, the monster's alert level runs down. The monster is confused, looks around for a bit, decides that he has lost the enemy and goes back to the patrol routine.

7 . All the while - a handful of rays are cast (about 6) around the monster to detect nearby walls. If it exceeds a certain distance the monster is repelled from the wall using the Separate Steering Behaviour. This pretty much guarantees that monsters won't get stuck on walls, corners and other awkward features of the dungeon.

That's pretty much it!

You can have a play yourself on the interactive demo shown on the video:

If you like what you see, stay tuned for parts 2-5 where I'll be discussing more complex aspects of the AI:

Part 2: Retreating and Defense

Part 3: Foraging

Part 4: Group Tactics and Luring

Part 5: Monster Rivarly!

Thanks for reading!

#5058904 My Procedural Dungeon Generation Algorithm Explained for my game TinyKeep

Posted by on 03 May 2013 - 06:56 AM

Hey guys,
I was originally going to advertise my Kickstarter project TinyKeep here, but as everyone knows spamming a message board is not good etiquette so I thought I'd share some knowledge with the community as well. Hopefully this will somewhat pay for the sin I am about to commit at the end of the post.

Today I'm going to talk about one technical aspect of the game, that is random procedural dungeon generation. It's pretty over-engineered, but hopefully will give anyone who is interested some ideas on generating dungeon layouts for their own games.

The interactive demo can be found here:

Here's how I do it, step by step:

1. First I set the number of cells I want to generate, say 150. This is an arbitrary amount really, but the higher the number the larger the dungeon and in general more complexity.

2. For each "cell" I spawn a Rectangle of random width and length within some radius. Again the radius doesn't matter too much, but it should probably be proportionate to the number of cells.

Instead of using uniformly distributed random numbers (the default Math.random generator in most languages), I'm using Park-Miller Normal Distribution. This skews the size of the cells so that they are more likely to be of a small size (more smaller cells, less larger cells). The reason for this will be explained later!

In addition to this I ensure that the ratio between the width and length of each cell is not too large, we don't want perfectly square rooms but neither do we want really skinny ones, but somewhere in between.

3. At this point we have 150 random cells in a small area, most are overlapping. Next we use simple separation steering behaviour to separate out all of the rectangles so that none are overlapping. This technique ensures that the cells are not overlapping, yet in general remain as tightly packed together as possible.

4. We fill in any gaps with 1x1 sized cells. The result is that we end up with a square grid of differently sized cells, all perfectly packed together.

5. Here is where the fun begins. We determine which of the cells in the grid are rooms - any cell with a width and height above a certain threshold is made into a room. Because of the Park-Miller Normal Distribution described earlier, there will only be a small amount of rooms in comparison to the number of cells, with lots of space between. The remaining cells are still useful however... read on.

6. For the next stage we want to link each room together. To begin we construct a graph of all of the rooms' center points using Delaunay Triangulation. So now all rooms are connected to each other without intersecting lines.

7. Because we don't want every single room to be linked to every other with a corridor (that would make for a very confusing layout), we then construct a Minimal Spanning Tree using the previous graph. This creates a graph that guarantees all rooms are connected (and therefore reachable in the game).

8. The minimal spanning tree looks nice, but again is a boring dungeon layout because it contains no loops, it is the other extreme to the Delaunay Triangulation. So now we re-incorporate a small number of edges from the triangulated graph (say 15% of the remaining edges after the minimal spanning tree has been created). The final layout will therefore be a graph of all rooms, each guaranteed to be reachable and containing some loops for variety.

9. To convert the graph to corridors, for each edge we construct a series of straight lines (or L shapes) going from each room of the graph to its neighbour. This is where the cells we have not yet used (those cells in the grid which are not rooms) become useful. Any cells which intersect with the L shapes become corridor tiles. Because of the variety in cell sizes, the walls of the corridors will be twisty and uneven, perfect for a dungeon.

And here's an example of the finished result!


That's it!


And here comes the plug:


TinyKeep is a 3D Multiplayer Dungeon Crawler with focus on intelligent monster AI, currently being funded on Kickstarter.

We really need your help with pledges or the game will not be made!