I'm certain influence maps will be useful in the game I'm working on, but I don't have much experience with them so I'd like to mine this forum for some tips... The game world is tile based and about 256 tiles wide and tall. One problem I'm going to solve with an influence map is this: an AI entity needs to decide where to build his house. This is what I have in mind: I will define the influence map as a byte array in two dimensions. The map is populated by iterating through all the map features that factor in, such as buildings, terrain etc. and incrementing the map in a radius of maybe 10 tiles from each map feature. The question is: how do I work with the data? The AI entity wants to build his house on the highest scoring tile, but, if it's unusable (maybe someone is standing there) he wants the second highest scoring tile. But iterating through the whole map to find the best tile would be wasteful, so what is the best approach of storing the influence map 'results'? Should I use a kind of high-score sorted list for this? Suppose I use the high-score list. Another problem then, is how to update the map after a new building has been placed. The most efficient way is to just update the tile positions that are affected rather than recomputing everything. But the high-score list would then be affected also. Is there a smarter way than iterating through the map and recompiling the high score list? Thank you...

I don't have experience with this, but I suppose you could maintain a quadtree, where each node maintains, e.g., maximum, minimum, and average values for all the tiles inside it...

Quote: Original post by captain_crunch
The game world is tile based and about 256 tiles wide and tall.

One problem I'm going to solve with an influence map is this: an AI entity needs to decide where to build his house.

This is what I have in mind:
I will define the influence map as a byte array in two dimensions. The map is populated by iterating through all the map features that factor in, such as buildings, terrain etc. and incrementing the map in a radius of maybe 10 tiles from each map feature.
The question is: how do I work with the data? The AI entity wants to build his house on the highest scoring tile, but, if it's unusable (maybe someone is standing there) he wants the second highest scoring tile. But iterating through the whole map to find the best tile would be wasteful, so what is the best approach of storing the influence map 'results'? Should I use a kind of high-score sorted list for this?

I'd say stop worrying.

256x256 is 65536. Comparing whether a value is more than another value is probably less than 10 instructions. So you're looking at something like 655,000 instructions to search the influence map... on computers that can perform something like 50,000,000,000 instructions per second.

Less flippantly though, influence maps contain semi-continuous data. Once you have the best tile, the surrounding tiles are highly likely to be 'almost-best', so as an optimisation you can search outwards from there to an arbitrary distance for something that looks good enough. That way at least you only search it once.

Quote: Another problem then, is how to update the map after a new building has been placed.

Again, I'd say don't worry. Recompute the whole thing. New buildings aren't placed that often.

Game Programming Gems 2 had a good article from Paul Tozour. You might be able to get it cheap or from a library.
Do searches on Influence Mapping Penny Sweetser as she wrote another good article for AI Game Programming Wisdom 2 and has online papers like this :
Combining Influence Maps and Cellular Automata for
Reactive Game Agents and this Using Cellular Automata and Influence Maps in Games
There is also the Influence Mapping thread.

These are great links! I especially like the article on combining various factors such as fire, temperature and water into a 'discomfort' influence map that agents can navigate. To this map I would add a factor 'threat' compiled from locations of previous casualties and monster sightings. To react to this, agents must evaluate the comfort level of every tile they enter on their way to their goal, possibly interrupting their path-based movement and forcing a new path to be calculated if the discomfort were great enough.

A different problem of mine is keeping agents such as soldiers or herd animals moving in relative closeness to each other. Keeping in mind that movement in my game world is discrete and tile based it is not possible to use the standard method where forces are pulling the agents together. I have an intra-agent messaging system in place, but it also seems too cumbersome for this kind of problem.
The paper that was linked to above mentions using influence maps for flocking behaviours, so that gave me a new idea for a solution to this problem.
My idea, now, is to designate a leader of the flock of agents that will follow a path to the destination as usual. The leader will emanate an influence map that the other flock members must try to stay inside. The flock members will only consider destinations within 3-4 tiles distance, as described in the paper. This should allow agents to briefly break formation in case of obstacles. In the case of squad formations, each squad member could even be given his own influence map that would mark his specific desired location within the formation. If an agent gets too far behind, it will seek the formation leader using standard path movement to bring it inside its influence map again.
How is this solution, will it work?

You might want to check Steering Behaviors For Autonomous Characters especially Leader Following or try Coordinated Unit Movement and Implementing Coordinated Movement
Again the AI Game Programming Wisdom books have got some good articles as well.

Sorting a 65k item list is loose change. Especially if it is mostly sorted already.

Once you have a sorted list, as you suggested, you merely tick down the list from the most optimum position towards the less optimum ones.

Another suggestion is that perhaps having the fact that someone is standing there as a factor in your influence map might be an idea. That way, someone standing there would likely disqualify the sector. If that is not feasible or not a good idea because people standing is a very temporary thing, then you wouldn't include it. However, I would suggest that if people standing is a temporary thing, why would you disqualify a square based on that. Is there a way you can enter a "wait for this square" state? That way, once the person leaves, the house would still be built there.

Quote: Original post by InnocuousFox
Sorting a 65k item list is loose change. Especially if it is mostly sorted already.

Once you have a sorted list, as you suggested, you merely tick down the list from the most optimum position towards the less optimum ones.

Another suggestion is that perhaps having the fact that someone is standing there as a factor in your influence map might be an idea. That way, someone standing there would likely disqualify the sector. If that is not feasible or not a good idea because people standing is a very temporary thing, then you wouldn't include it. However, I would suggest that if people standing is a temporary thing, why would you disqualify a square based on that. Is there a way you can enter a "wait for this square" state? That way, once the person leaves, the house would still be built there.

I see your point, but these problems only appear because I want to save on performance by keeping the influence map around instead of just using it once and throwing it away. I'm still in the mindset that influence maps are somewhat costly to compute in a realtime game. So, that is the reason I don't factor in temporary effects such as people. (But, why can't I just build on people? This rule came about because buildings are supposed to block movement, and it is already enforced when the player places buildings).

But, if I follow your advice and worry less about performance many of these issues will dissappear.

I agree that building on a person should kick the person off to the side somehow. That gets rid of the problem.

One thing to remember is that you only need to keep one copy of the influence map. That way, any agent in the game can use it. The only caveat to this would be if different agents or differen sides have different information they want to track. Different sides using the same information isn't a problem since you can just reverse what it is you are searching the map for (i.e. positive or negative).

Another way of approaching influence maps is to layer them. You track different parameters and keep them separate. If you need to access some parameters but not others, you only use the influence maps you need and sum the grid values up.

An example might be one for buildings, one for mobile forces, one for resources, etc. You may have an army that wants to attack mobile forces. You may have an army that wants to attack mobile forces that are near buildings. You may want to have an army that attacks mobile forces that are away from buildings. You may have units that need to get to buildings but avoid mobile forces. You may want to prioritize attacking mobile forces that are approaching YOUR buildings. You may have units that need to seek out resources that are away from enemy buildings and forces... it goes on and on.

For this, you can have influence maps for your forces, your buildings, their forces, their buildings and resources. So, with 5 individually calculated influence maps, you can build a wide variety of aggregate ones depending on what it is you are trying to accomplish.

Put simply, influence maps rule.

You may be able to optimize your influence mapping by subsetting the influence map at a coarser multiplier than the tile increment. EX - 256x256 tiles ==> 128x128 influence map or 64x64 influence map... you might find that the influence 'areas' are sufficient for the logic you are using. Generalizing as 1/4th or 1/16th over a tile increment map might be useful if you do have to constantly recalculate the influence (or have different criteria for different unit types etc... -- having many more maps to calculate).

You could even use a mix of both -- using fine grain mappimg when doing something like fire cover, versus economic influences which can be more generalized (coarser map increments).


There can be different types of analysis for criteria checking. Ive done code that identifies area of 'clearings' withing a limited slope (suffiently large flat areas to place multi-tile objects). It will require repetitious scannings
to do this kind of analysis.


You may (if possible in you mechnaics) allow modification/mutation of the terrain to place certain objects -- like the pioneers did chopping down trees to create a clearing or changing the ground levels (cut/fills) to creaste a flat spot. You still will have to do your scanning for good spots which are applicable to the limited terrain mutations allopwed in your game....