Are there well known algorithms for efficient map knowledge?

Question

The question subject's is a little confusing, but I had no better way to express my train of thought. I'm working on an RPG at the moment, and I have a question. Using SARSA (State-Action-Reward-State-Action), I'm building a smart brain by training it through a reward system. Right now, what I want is to improve the learning process when moving each unit of the party, the selected actions will impact the team as a whole.

Moving to attack an enemy on which I have a tactical advantage, such as when a knight attacks a wizard, the wizard being weak on physical attacks, will get more damage out of the attack. The brain starts to understand that doing this gives a better reward. But, doing so could lead a unit to attack an enemy that has a tactical disadvantage against it but it has friends that can help him defeat the foe.

What I'm looking for is the following: Is there any algorithm that can parse a given data structure representing a map and see whether or not I'm moving toward a bad or good position depending on some variables such as moving toward target, target has friendly surrounding, moving toward treasure chest and etc.

I'm not looking for someone to write down an implementation for me, just to point me in the good direction because I have no idea what I'm looking for. If you're well versed in what I'm speaking and willing to give me a sample algorithm that I should follow and adapt for my game, I will gladly refer you in my prototype and send you a link once the prototype is playable!

Answer 1

Influence maps are data structures that model various relationships with respect to their locations, and typically assume that the impact of these relationships spread outward across space and/or time. For instance, positions close to cover would be considered safer than those further away. Similarly, regions with recent enemy sightings might be considered more confrontational than those that have not recently observed enemy movement. As an illustration, here's a screenshot from Brian Wanjir's project where he uses influence maps to modify path finding in order to avoid enemy turrets:

Alex Champandard identifies the following as the three core strengths of influence maps:

• Situation Summary — Influence maps do a great job of summarizing all the little details in the world and making them easy to understand at a glance. Who's in control of what area? Where are the borders between the territories? How much enemy presence is there in each area?
• Historical Statistics — Beyond just storing information about the current situation, influence maps can also remember what happened for a certain period of time. Was this area being assaulted? How well did my previous attack go?
• Future Predictions — An often ignored aspect of influence maps, they can also help predict the future. Using the map of the terrain, you can figure out where an enemy would go and how his influence would extend in the future.

Offhand, I know that in one form or another, they've been used in Ground Control 2, World In Conflict, Kohan 2, Axis & Allies and Killzone 2 & 3.

In terms of references, the earliest source I know of is Paul Tozour's "Influence Mapping" in Game Programming Gems 2. They also surface fairly often in the AI Game Programming Wisdom series; here's a partial list of related articles:

• Recognizing Strategic Dispositions: Engaging the Enemy, by Steven Woodcock in AI Game Programming Wisdom
• Strategic Decision-Making with Neural Networks and Influence Maps, by Penny Sweetser in AI Game Programming Wisdom 2
• Prioritizing Actions in a Goal-Based RTS AI, by Kevin Dill in AI Game Programming Wisdom 3
• Spatial Reasoning for Strategic Decision Making, by Kevin Dill in Game AI Pro 2

Given that influence maps have been used in a wide variety of AI contexts (including neural nets), I suspect they would work equally well with SARSA.

WorldCat might help you find a library copy near by. Also, some of the source code is available on line. Personally, I found the series to be a good investment, but your mileage may vary.

Answer 2

Well, since you want to include the particulars of your combat system, nothing will work out of the box. In general, an AI should consist of 3 parts: percepts, model, decision maker.

The percepts are simply information you feed in about the current situation. I'll want a measure of closeness to some destination. The usual A*/Dijkstra's should be fine. You will also need to feed in adjacency or closeness information for enemies/allies. Again, you can just calculate the distance between characters. You will also need to give characters' current states (hp, buff/debuffs, etc).

I don't know much about SARSA but it looks like it takes the place of the model. It will take in the information about the current state, use it to change it's overall state, compare against some machine learning model, whatever, then decide what to do.

The list of decisions is again determines by your combat system, but it's whatever actions your AI character can currently do. Your model will hopefully generate some sore of level of utility for each action, and then you can just execute the action with the highest utility.