Article: Real-Time Strategy High-Level Planning

Real-Time Strategy High-Level Planning

[Stefan Weijers, 2010]

In this article, the author analyzes the different elements needed for implementing AI in RTS games as well as different techniques used to achieve this. Here is a small summary:

Real-Time strategy games are computer games in which the player controls an army in real-time to destroy other players' armies, with each player requiring resources and buildings to create such army. The key to winning is to balnce the army production with the gathering of resources.

Tasks in real-time strategy games can be split in three levels of abstraction:

• Unit Control (Lowest level, players control a specific unit).
• Tactical Planning (Make plans on how to attack the enemy).
• Strategic Planning (High-Level decisions involving army creation and management).

Identified Problems in real-time strategy games:

-------------------------------------------------

Resource Management

The gathering and balancing of resources can be done with a reflex agent. The AI has all the relevant information and can simply assign more units to a certain resource when it runs low.

Decision making under uncertainty

To be able to recognize important events, the game needs some sort of pattern recognition. Even with no concrete information available, the AI should be able to plan future actions.

Spatial and temporal reasoning

Applicability of a strategy needs to be reevaluated constantly. Terrain analysis is really importante for this. An important problem encountered for this aspect is the process time, because the world might have changed while the AI is still calculating its strategy.

Collaboration

This aspect is clearly lacking in RTS. Computer players never work with human players to overcome a strong opponent. The AI should be able to recognize the allied strategy and help them in the right way.

Opponent modeling, learning

Human players can spot weaknesses in a strategy and exploit them while computer players have a hard time accomplishing this. The AI needs to learn from previous experiences and formulate aplicable counter strategies.

Reasons why current commercial RTS AI fail to challenge human players:

--------------------------------------------------------------------------

Predictability and lack of spatial reasoning.

When the AI is predictable, players will inevitably exploit it. The predictability of commercial AIs comes from the fact that all AI is scripted.

Scripting

Commercial games include a set of scripts that translate into several different strategies that the AI implements to give some diversity to games but that carries several problems:

Hard to implement

Implementation of scripts needs several expertns in the game to think of viable strategies, the game has to be near completion before the AI programmers can start implementing it and even after implementation, it needs to be tested and tweaked thoroughly.

Domain Specific

After implementing a scripted AI for a game, the implementation is not applicable for other RTS games. This forces game developers to go thorugh the implementation cycle again.

Game developers use other means to entertain players. Different scripted strategies or giving the AI more information than it should have are some examples to create diversity or add challenge.

Academic Research to solve these issues:

---------------------------------------

Dynamic Scripting

A reinforcement learning technique for scripts. This allows the AI to generate a strategy on the fly by selecting a viable tactic in the tactic database. Also, this allows the AI to overcome static challenges (players that use the same tactic over and over again).

This, however, carries some of the problems. It still needs a group of experts to create viable tactics and because most research is done with static opponents to learn from, their ability to counter other adaptive players is doubted.

Monte Carlo Planning

This type of planning generates a set of simulations for all possible actions, it then chooses the plan that corresponds with the best simulation for the player. Because in an RTS game the amount of possible actions is enormous, an abstraction of actions and states has to be found.

The problem with this technique is that it requires a lot of calculating and it doesn't learn from previous mistakes.

Case Based Planning

This technique is based on case based reasoining, which is similar to the dynamic scripting method. It is based on states and looks at past experience to calculate the best sub plan in the current state. Case Based Planning doesn't model the opponent and wont do adversarial planning. It needs a database of predefined tactics. The algorithm picks a random tactic and remembers the outcome. This technique allows an expert to play the game and teach the AI what good decisions are, simplifying the process of designing an AI.

The problem with Case Based Planning is that it needs to be trained against opponents before it can become strong. The more complex and diverse the opponents are, the longer it will take the CBP to learn how to win.

The author finally concludes that the most advanced technique is the Case Based Planning because it can adapt, change and enhance strategies, but pointing out which one of the three is the best is hard because advance scripts have been made in commercial games and the performance of the Case Based or Monte Carlo planners have yet to be proved in more complex games.

Read the full article here!

Wijers, S., 2010, Real-Time strategy high-level planning. Obtained in August 11th, 2011 from PIXEL: www.inter-actief.utwente.nl/studiereis/pixel/files/indepth/StefanWeijers.pdf

Article: Using Potential Fields in a Real Time Strategy Game

Using Potential Fields in a Real-Time Strategy Game Scenario

[Johan Hagelback, 2009]

In this article/tutorial Johan explores a potential field based approach to real-time planning and navigation.

Potential fields are similar to influence maps in the fact that they are both constructed by placing numerical values on a grid map. The difference is that influence maps use player units/buildings to set the numerical values and potential fields place the numerical value in areas of interest.

An example of an influence map.

After the potenial map spreads through the map (fading its values to zero), a moving unit can easily reach it's destination by simply moving to its current more attractive adjacent tile. The idea is to use attractive fields in the destinations and repelling fields in the obsacles. This will create a potential map that will guide the unit through the terrain.

This can also have other applications, for example, when a unit ends its "attack phase" and enters a "reload phase", it can create repellant fields to flee if the enemy unit comes closer. Another application can be for long ranged units. If they place a small repellant field to enemy units to create a "ring" for the optimum firing range.

An example of a potenial field with obstacle repellant fields.

One of the advantages of using potential fields is the ability to handle dynamic game worlds. Agents only need to see one step ahead to move. They don't need to know the full path to their destination, eliminating the risk of obsolete paths due to changes in the game world. Also, it can easily create complex behaviors by just modifying the fields, for example, several unis will surround an enemy while being at shooting range and avoiding other friendly units who are also attacking the same enemy.

The main drawback from this approach would be the fact that it would need to be carefully programmed as to require an efficient amount of resources. Although the author solved this issue, it's definetely not something trivial.

For more information, including common problems and solutions, hit the link.

Hagelbäck, Johan, 2009. Using Potential Fields in a Real Time Strategy Game Scenario. Obtained in July 28th, 2011 from AiGameDev.com : http://aigamedev.com/open/tutorials/potential-fields/

Article: Decision Making Levels in RTS Games

Decision Making Levels in RTS Games

[Muhamad Hesham, 2010]

In this short blog post, Muhamad divides the actions in RTS games in three different levels:

1. High level strategic decisions
2. Intermediate level tactical decisions
3. Low level micromanagement decisions.

The high level strategy resembles the general of a real army. The actions include building a base, training units, attacking enemis, etc. The perception at this level is based on the information from the lower levels.

Medium level actions resemble a commander that groups units into fighting elements and control them in a large war sense.

Finally the low level actions are most commonly known as actions like moving units or using a unit's special ability.

This is how players make decisions while playing RTS games and AI creation can be made to resemble this behavior. Each level should not care on how the lower levels will carry on a specific task, for example, in the high level, a decision has been made to attack the enemy, so the message arrives at the medium level. Here, it is decided which troops will move and where and finally the low level will be in charge of finding the best path and maintaining a strong formation within the group of units.

The author concludes that medium-level AI is the most complex of all and is usually lacking in most games because of this. The amount of feedback information that is needed and complex plans that need to be made make this level AI worth considering.

Read the full article here.

Hesham, Muhamed (2010). Decision Making Levels in RTS Games. Obrained in July 10th, 2011 from Adaptive AI Engine for RTS: www.rtsairesearch.wordpress.com/2010/10/27/paper-read-an-integrated-agent-for-real-time-strategy-games/

Article: How To Design Effective Achievements

The Cake Is Not A Lie: How To Design Effective Achievements

Lucas Blair [2011]

This is a really good article about something that everyone likes to add to their games: achievements/trophies/medals.

The author gives interesting advice about what to do and what to avoid when implementing a reward system in your game (of course, this is mostly the author's opinion, which means that nothing must be taken as complete truth, but it's nice as a starters guide).

The article addresses the following topics:

• Measurement vs Completion Achievements
• Expected vs Unexpected Achievements
• Achievement Difficulty
• Achievement Notifications
• Achievement Permanence
• Negative Achievements
• Incremental and Meta-Achievements
• Competitive and Non-Competitive Achievements

I agree with most of his conclusions, like "Use measurement achievements instead of completion achievements to increase intrinsic motivation through feedback" The only one that I disagree a little bit is the negative achievement one.

He says that negative achivements like "You died 100 times, congrats!" are detrimental to the player's experience, I think that depending on the game, they can be really fun. For example, in a game like Super Meat Boy, it would make sense because you will inevitably die a few thousand times before you complete the game. Another game where I've encountered negative achievements is Amorphous+. I got the "Killed 100 times" award and the "Killed in 10 different ways" award. I didn't found those achievements as adding insult to injury, but more like a "well, at least I got something". Plus, it added a little bit of humor to the gameplay.

I don't think every game out there could pull this off, but when they do, it's really cool.

All I'm saying is that if it makes sense, including negative achievements can be fun, but they could still backfire if not handled with care for the reasons stated in the article.

Read the whole article:

Part 1: http://www.gamasutra.com/view/feature/6360/the_cake_is_not_a_lie_how_to_.php

Part 2: http://www.gamasutra.com/view/feature/6375/the_cake_is_not_a_lie_how_to_.php

Part 3: http://www.gamasutra.com/view/feature/6388/the_cake_is_not_a_lie_how_to_.php

Blair, Lucas (2011). The Cake Is Not A Lie: How To Design Effective Achievements. Accessed in 3/jun/2011 from Gamasutra.com: http://www.gamasutra.com/view/feature/6360/the_cake_is_not_a_lie_how_to_.php?page=1

Article: Animal and Genetic AI

Animal and Genetic AI: A Combination to Improve AI in Video Games

Nicholas Schneider [2011]

In this article, the author analyzes how to create challenge in videogames as to make them fun. He says that artificially creating challenge through inflated health bars, unlocable moves and one hit kills don't offer a sense of realism.

A nice attempt to solve this problem was Bethesda's Radiant AI system, in which the NPC's would make choices rather than perform scripted events. Still, Schneider considers that this system still feels scripted.

On the other hand, in FPS games like Halo, enemies act intelligently by trying to flank you, run for cover and sending search parties for the player. This also feels scripted as the player needs to pass through a specific waypoint to trigger certain behaviors.

The author proposes the combination of AI with animal like behaviors, which can be the hunting habits of wolves or the social structure of bees for example. The difference is that no waypoints and scripted events would be needed as the animal like behaviors themselves would kick in the moment they are needed or as each NPC sees fit.

Even now, the AI would feel scripted, so Schneider says that combining those behaviors with Genetic AI would provide a much dynamic and interesting experience. The AI would adapt to the player and adjust it's skills while applying such behaviors like predator skills (force the player into an area where the rest of the enemies can set an ambush) thus making the experience feel more like a real life exercise in survival and less like scripted enemy guidance.

Read the full article here.

Schneider, Nicolas (2011). Animal and Genetic AI: A Combination To Improve AI in Video Games. Obtained in April 13, 2011 from Gameinformer: http://www.gameinformer.com/blogs/members/b/tognick_blog/archive/2011/04/08/animal-and-genetic-ai-a-combination-to-improve-ai-in-video-games.aspx

Article: Enabling Computers to Play Games Like Humans

Enabling Computers to Play Games Like Humans

Stephen McGlinchey [2004]

This article is a quick mention on how it might be possible to create an AI that behaves like a human.

McGlinchey states that AI players can be written with several different objectives. Some developers aim to develop AI players that are most likely to succeed in a game, others aim at producing players that will make the gaming experience more enjoyable and this means that the AI should behave like a human.

She says that there are two aspects of game AI that affect the gamer's experience: level of performance and style of play. This means that the AI must match the experience level of the player and that it must behave similar to how a human would play (AI players should not have superhuman reactions or be able to move in an impossible manner). Failing to correctly adjust any of those will make the experience less immersive and less enjoyable.

One way of solving this problem is a technique that is being researched called motion capture for AI. Which is basically training the AI with recorded data from human players, a process called GoCap (Game Observation Capture). The trained AI can then mimic the data that was used to train it.

The author suggests using Kohonen's Self Organising Map (SOM) in conjunction with the GoCap. In a simple game of pong, they were able to replicate some of the quirks that are present in human play, which can actually make the player believe that the opponent is intelligent and non-mechanized.

Read the article here.

McGlinchey, Stephen (2004). Enabling Computers to Play Games like Humans. In Ercim News 57(1),14 - 16

Article: Proof of Learning

Proof of Learning: Assessment in Serious Games

David Michael, Sande Chen [2005]

This article explains why it is not enough for a game to say that "it teaches" and leave it at that, but to include, like every other tool of education, a way of testing that the player actually learned something.

When a computer is used to test a student, what comes to mind are long sequences of multiple-choice questions (MCQs), which makes this the easiest choice for assessment in serious games. Sadly, MCQs are not always the best choice (I might go as far as to say that they are probably the worst choice), mostly because even if they are good to measure memorization and retention of facts, they fail at evaluating if the student is following a process correctly and also, during a game, this kind of assessment will be percieved as boring.

So, how can someone do a correct and useful assessment in the context of a serious game?

Currently, there are three main types of assessment that are used in serious games:

• Completion Assessment (The player completed the lesson?)
• In-Process Assessment (How did the player completed the lesson?)
• Teacher Evaluation (Does the teacher think the student understands the material?)

1) Completion Assessment

Translated to Serious Games, this could be if the student completed the game. The problem with this is that the player could have cheated or exploited holes in the system (which, as the article states, is something honored and rewarded between gamers, but not so between students). It's important to know whether the student learned the material or just learned the game and how to beat it.

2) In-Process Assessment

In Serious Games, this can be done by logging and tracking information while the student plays the game. For example, the time required to complete the lesson, the number of mistakes made, etc. Depending on the material that is intended to be learned, different kinds of information will need to be stored and different actions will need to be taken depending on them.

3) Teacher Evaluation

It's hard for a game to replace a teacher, so the game has to include tools to assist teachers in their evaluation, which can be homework control, grade tracking, reporting, etc. One example can be the inclusion of an 'Observer Mode' where the teacher and other students can actually watch the whole process.

As a game developer, implementing these methodologies can prove frustrating, because great care should be taken in maintaining the game fun. This is not an impossible task though, PIXELearning is a company that uses its own propietary engine to include pedagogy and assessment methodologies in their products.

One of these methodologies include a series of qualitative questions (I would assume at the end of a gaming session) such as: "You chose to do X. What was your basis for this decision? Why did you not choose Y?" So the teacher has more information available to judge how well the student really understands the material.

The article ends with a quote from Kevin Corti, former CEO at PIXELearning:

"[Serious games] will not grow as an industry unless the learning experience is definable, quantifiable and measurable. Assessment is the future of serious games".

Read the full article here

Michael, David; Chen, Sande. (2005). Proof of Learning: Assessment In Serious Games. Retrieved March 31, 2011 from Gamasutra.com: www.gamasutra.com/view/feature/2433/proof_of_learning_assessment_in_.php

Article: Making Hospitals Fun

Making Hospitals Fun: How can games improve the patient hospitalization experience

Erin Hoffman [2006]

This article explains how games are being used to bring entertainment and education for patients and visitors that go to the hospital. The author explains the following three projects:

The first project, created by the Entertainment Technology Center in Carnegie Mellon, was a frog-like shape kiosk that was placed in the waiting rooms with several activities for kids, the most popular of them being an interactive coloring book that allowed kids to create their own pictures and then 'play' them through an animation sequence.

This project created a fun environment for kids in the hospital's waiting room so they felt more comfortable while being there.

The second project, created by the Johns Hopkins University in conjunction with the Pediatric Rehabilitation Center in Mt. Washington, was aimed at kids with weight problems. The project involved the use of the Sony EyeToy and CatEye Fitness gamebikes to create a fun environment to do excercise. Also, that provided a safe place where all the kids could go and not be judged by their weight.

The last project, called HOPE (Hospital-based Online Pediatric Environment) was aimed at kids who were in isolated sociological situations in the hospital environment (kids that have to be in the hospital several days a week for several hours). The project involved the use of Xbox consoles and E-rated games so kids could play with each other, talk and connect socially. This made the isolated and frightening hospital experience less traumatic.

This article shows how videogames can really change lives in ways that you may never had thought. Some people say that videogames are a waste of time, the people involved in these projects can provide a different point of view.

Read the full article here.

Hoffman, Erin. (2006). Making Hospitals Fun: How can games improve the patient hospitalization experience? Retrieved March 16, 2001 from SeriousGamesSource.com: http://www.seriousgamessource.com/features/feature_110806_gfh4_2.php

Article: Theta*

Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments

Alex Nash [2010]

A* is commonly used algorithm that involves searching the shortest path in a given grid. Although this works well, it has some problems, one of them is the unrealistic looking paths that it creates. This happens because it is restricted to the actual grid. There are several aesthetic optimization that can be done to the algorithm, but they can make the process slow or create a sub-optimal path.

To solve this problem, Nash developed Theta*, which considers paths that are not constrained to grid edges. The main difference is that Theta* allows the parent of a vertex to be any vertex, unlike A* where the parent must be a visible neighbor.

[Note: Theta* algorithm is described in the article and original paper]

A* Path (Red) vs Theta* Path (Blue)

They tested the Theta* algorithm with a square grid in several different maps (game-based and random) and they found that on average, the ratio of the lengths of the paths found by Theta* were 1.007 on game maps and 1.002 on random maps, which were better than the 1.04 ratio of A* paths. In other words (their own words, actually), Theta* is orders of magnitude faster than standard implementations of A* searches.

Theta* is a good alternative when A* is not enough for a realistic "shortest-path".

Read the article here.

Nash, A. (2010, September 8). Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments. Retrieved February 28, 2011, from AiGameDev.com: http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/

Article: Do Girls Play Computer Games?

Do Girls Play Computer Games?

Anna [2009]

In this interesting post from Anna's Serious Games Interactive Blog, she discusses the importance of gender when designing a game. She also talks about the unbalanced gender representations in games.

Anna says that there is a social preconception of computer games being for boys, and while it's true that boys generally play more games than girls, that is no reason to completely forget about the female gender while designing a game.

One important aspect to consider which is often overlooked, is the gender of the avatar. While it might not seem important when compared to other elements like graphics, music and engine considerations, it can be a very important issue for female players. As an example, she talks about the game she's been developing "Playing History: The Plague" in which the main character is a non-gender specific mouse, which can be customized by the player. This means that the player can give the avatar gender specific traits, so both genders can be interested in the same avatar.

She also talks about the issue of marketing and packaging, in which she interestingly found that educational games were regarded differently from other genres. Educational games are regarded as 'good for you' games while every other game is regarded as 'fun games'. Also, girl-oriented games are shelved with the educational games, reinfocing the idea that computers are tools, while boy-oriented games are shelved in the 'fun' shelves.

Care should be taken when designing the game, as to not overlook these important aspects.

Read the article here.

Anna. (2009, April 11). Do Girls Play Computer Games? Retrieved February 25, 2011, from Serious Games Interactive: http://www.seriousgames.dk/da/node/370