Using Emergent Behavior in Video Games

As some of my readers might know, I am currently doing my exchange year in Madrid, studying Artificial Intelligence. One of the courses I had was about Intelligent Agents and Multi-Agent Systems. As a short test project I wanted to create an emergent enemy AI for a simple game. Just making the game and keeping everything to myself might have been easier, but I decided to share some of my thought with you.  Underneath is a shorted version of everything, but you can also download the complete .pdf article >> Using Emergent Behavior to Improve AI in Video Games << [all rights reserved]:-D

Intro

As most know, video game industry has been competing for the best graphics in games for a long time. Now, as making graphics has become more and more easier all the time, there has to be a new hook. Some say it is the story (I totally agree), but another thing that has not evolved much is the non-player character intelligence. This is something rather hard to do and experimenting on new methods is something the triple A studios are not very eager to work with. I am no top-notch researcher, so I just decided to try to implement a simple game AI, using emergent behavior.

Ummm… Emergent Behavior?

Yeah, what is emergent behavior? It is a behavior that emerges from simple set of rules, yet it can be considered intelligent. The creator only specifies some simple rules, that in the end result in wanted behavior. Insects, for example, is something that is being studied by computer scientists in order to find this kind of emergent behavior. Ants and bees for example display this kind of behavior in finding the shortest route to their goal – not because they actively search one, but because of their behavior they mark the fastest route between two points.

The Game

The game was implemented using python programming language and pygame library. Those not familiar, can read an introduction from my previous post. The game was programmed completely from the scratch, just to practice a little bit more of my programming skills. The game itself features a player controlled character, that can move around the screen and shoot with a gun. The enemies come in form of green aliens, that try to nd the player and attack him by biting. The way they communicate, is by leaving pheromones (blue dots) to the game area, that contains information about the locationof the player character. The rest following underneath is straight taken from my paper.

The AI

The idea of the Arti cial Intelligence is to create a simple emergent behavior for thealiens. They are considered to be quite simple and the method used is somewhat basedon ideas presented by Steels (1990) and Lewis and Bekey (1992). One important thing to notice here is that the aliens cannot use direct communication to talk with each other. Because they are simple critter-like creatures, they cannot have telepathic abilities, as that could be felt cheating by the player. Thus the aliens should use pheromones to leave information to the environment and use this indirect way of communicating instead of telepathy. This approach also makes the AI easier to implement and probably less resource intensive.

The Aliens have three modes: Search, Flee and Attack. In search mode the alien is trying to find the player in the game area. The alien has no knowledge of the environment around it and it does not gather any information about the level. Because of this, the alien is implemented to walk randomly until it sees anything of interest. If the alien in search state sees pheromones on the ground, it will start to follow the trail. In case the enemy sees the player, it will attack or flee, depending on the situation. There is a threshold related to the attack/flee behavior (as seen in the figure 1, points 3 and 4). If the alien sees other aliens nearby it will attack the player, but if it is alone, it will flee. The behind this kind of behavior is to make the aliens attack in pairs or groups. This way the player will have to fight a bigger bunch of aliens and has the sensation of challenge.

In flee mode the alien is running away from the player. This might be triggered for example because of being outnumbered or heavy loss of health (in the implementation here, the fleeing depends solely on the number of aliens nearby). In flee mode the alien leaves pheromones behind, so that other aliens might find the player (or that the alien itself might find the way back to the player). The pheromones contain a direction, which points towards the player in order for the aliens to know which way to follow the trail. As the alien is running away from the player, the pheromones left point always to the opposite direction the alien is facing.

In the attack mode the alien is charging towards the player, trying to attack it. This is done by getting to a close distance to player so the alien will be able to bite the player and deal damage in that way. The algorithm shown in figure 1 portrays the behavior of the aliens.

The Initial Algorithm For the AI

The initial level is shown in the figure 2. It is just a plain level, with only the player and the aliens. The red circle around the aliens portrays the field of view of the enemies. However, as can be seen from the figure 2, the player has actually too much room to move around as well as the search space is too great a challenge for the aliens. It takes a significant amount of time for the aliens to find the player (but because of the randomness, this is not always true). Also, the pheromone trail stayed alive for a very long time and once the aliens found the trails, they did not point to the current location of the player anymore and tended to be quite long.

The Initial Version of the Game

As a solution to these problems, there had to be a time-out on the pheromones. A timer was added, that would make the pheromones to disappear after certain amount of seconds had passed. This way the pheromones no longer led to empty places nor were dozens of pheromones long. Another addition that can be seen from the figure 3 was the addition of the walls. Because this kind of shooter games usually happen in tight, closed spaces, the playing area was divided into smaller rooms. The rooms reduce the search space for the aliens significantly, so they were able to find the player within the room quite quickly. The running movement of the player is also restricted within the rooms and there are only few doorways leading out from each of the rooms.

The Game After Adding the Walls

The changes led to faster search times for the aliens and better challenge for the player. However, as the alien fled from one room to another leaving a trail of pheromones behind the player was still able to run away. Once the aliens came back, the trail was a dead-end. Also in cases when the aliens attacked the player, other aliens nearby still just kept searching and did not react to the attacking aliens nearby.

To fix the problem, another type of pheromone was added to the game. These red pheromones are left when the alien switches to attack behavior. In attack mode it leaves pheromones that point towards the way it is moving (as opposite to the fleeing pheromones). Now when the alien goes into attack mode, it gather other aliens on it’s route to also attack the player. In the case where the player decides to run away, the enemies keep following and leave a trail that gathers even more aliens to join the attack. This means, that if the player runs around the whole game level with only one alien pursuing in the beginning, the player will end up with all the aliens in the current level following him. The final version of the implementation can be seen from the figure 4.

The Final Version of the Game

Conclusion

A good aspect of emergent behavior is it’s simplicity to implement. With just a couple of simple rules it is possible to create “intelligently” performing agents. However, as can be seen well in this paper, the design stage is somewhat complicated. Even though the end goal was clear in the beginning, the behavior rules had to be adjusted a little. The aliens behaved less smartly than they were supposed to. The positive thing was that adjusting the behavior was quiet easy, because of the simplicity of the behavior rules.

One good side of the emergent behavior and the simplicity is the low amount of processing power required. Dozens of aliens can be running at the same time on the screen without the loss of frame rate (one thing to remember though is that the graphics are not that complicated either). With some optimization it would probably be possible to gain even better performance than there currently is.

However there still remains more tweaking possibilities to be done for the aliens. They don’t seem to recognize the pheromones really well so there could be a bigger area effect on the pheromones. Other possible implementation could be to make the aliens scream when they attack the player. This way the scream might attract other aliens nearby (for example within the same room) to join the attackers.

References

If you are interested in reading more, check for example the following scientific papers for more on Artificial Intelligence.

S. Cass, Mind games [computer game ai]. Spectrum, IEEE 39(12), 40{44 (2002).doi:10.1109/MSPEC.2002.1088444F.
Dignum, J. Westra, W.a. van Doesburg, M. Harbers, Games and Agents: Designing Intelli-gent Gameplay. International Journal of Computer Games Technology 2009, 1{19 (2009).doi:10.1155/2009/837095. http://www.hindawi.com/journals/ijcgt/2009/837095.html
M.A. Lewis, G.A. Bekey, The Behavioral Self-organization Of Nanorobots Using Local Rules,in Intelligent Robots and Systems, 1992., Proceedings of the 1992 lEEE/RSJ InternationalConference on, vol. 2, 1992, pp. 1333{1338. doi:10.1109/IROS.1992.594558
J. Orkin, Three states and a plan: the AI of FEAR. Game Developers Conference, 1{18 (2006)L. Steels, Cooperation Between Distributed Agents Through Self-organisation, in IntelligentRobots and Systems ’90. ‘Towards a New Frontier of Applications’, Proceedings. IROS’90. IEEE International Workshop on, 1990, pp. 8{14. doi:10.1109/IROS.1990.262534

The Source Code

The source for all I have written above is available for download. Get it from here >> Swarm Game Source << You are free to use the code for your own use, just please, give the credit to the one whom it belongs to. It is a .rar archive. All you need is Python and PyGame libraries to get it working, the images and everything are included.

Hope this helped someone or gave new ideas. Until next time!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s