I'm going to be using influence maps in a game I'm developing at university, but I can't seem to find many examples of this is practice, plently in theory. Theres a good article in game programming gems I and I hear a better one in II that I haven't been able to get yet. Anyone know of anywhere with more info? I was thinking about creating a 2D array with a "InfluenceElement" class inside the array element. This will hold information about general influence as well as penilising points for a*. ~Red

Yep, the Wisdom articles are good.
Try these as well...
http://www.gameai.com/influ.thread.html
http://www.ccg.leeds.ac.uk/james/influence/
http://www.cs.uq.edu.au/~penny/strategy.htm
I'd be interested in anything else you find.

I think that Tozour article is the bible as far as influence maps go. I've seen two of those links before. It's not that difficult to envision what influence maps do, I'm just suprised about the lack of documentation about them.

If I get it working, I'll post the code if anyone's interested.

~Red

I would be happy if you post your code:)

Cool, well I'm working on it at the moment, so hopefully I'll have something working early next week.

~Red

What you basically do, is you have your board.

int board[255];

(for up to +-32767 Either way, ofr a 16*16 board).

Now, when something happens (like something moves, or a new piece is put on), you need to update the board.

Now, if something moves, you simply negitate its weighting, and reapply it. Before getting to its new spot, and applying the correct (non-negitated) Value there.

So, if you've got something that has a radius of, say 2, and an intensity of +3, you go, and at its position. Call it X. You go and do something like

board[x] += 3
board[x + 1] += 3

.....

To go and change the value, which is within a 2 radius of X, with the intensity, which is +3. And enimy unit (which is the same as this one, only its the enimies), is -3.

Now you've got that, you need to change a few things. To make it more fun.

You basically do a little thermodynamics, to figure out the "correct" value for each square".

You go, and for a set number of timesteps. (or else, continue looping until nothing changes. But it might take awhile).

Now, assume that each square, can only diffuse its value to its eight adjasent squares.

Now, also assume that some materials diffuse there values faster then others.

You now need a coefficient (c) which is from 0.00001 to 1. For each material.

We then plug that into the function colder = colder + ((Warmer - Colder) * c)

Warmer = Warmer - ((Warmer - colder) * c)

So, the colder is the colder value (closest to 0) and the warmer is the warmest value (farthest from 0). Now, everything is done, on the + side of 0. then the sign gets reinstated after the computation (to prevent difficulties).

This is only ok for one cell.

For eight cells, assume that the warmer - colder is actually one eighth what it is. (it should work)

So, you basically have to, for each cell, take the surrounding cells,
Do the formula, and update them,
And continue on.

(of cource, you need two copies of the array, so that the procedure will work.
You just have two pointers *f and *b. (to two different malloced arrays)
loop:
You then take the data from *f, and output the results to *b.
you then swap *f and *b. (3 ^'s if you know how to do it. the XOR SWAP).

Overall, a nice little algorithm.

From,
Nice coder

I was thinking of using a 2D array, I guess that would work on similar priciples.

Thanks for that, I'll have to go and digest it for a while.

~Red

I usually always use a 1D array, instead of a 2D array. it makes some things easier, and some things harder.

You can treat it like a 2D array, for some things.

You basically treat it like a 2D array. With two PO2 Dimentions.

For eg, a 8x16 array

000 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127

(Numberes represent the array index).

Now, you use 6 * 14 of it. (Which leaves a border around it. Don't worry, you still manage to get a bit of use about it.).

You can find the eight adjacent squares of X, by doing a few caluculations, and checking a few things.

By going

x + 1 == Square to the right of x
x - 1 == Square to the left of X
x + y == Square y spots the the right of X, if y is equal to the size of one row, then it is the square directly beneath x.
x - y == Squares y spots to the right of X, if y is equal to the size of one row, then it is the square directly beneath x.
x + y + 1, X + Y - 1, X - Y + 1, X - Y - 1 == The four squares, on the diagonals, if Y is equal to the size of one row.

These are nice, but how do we tell if you are in the allowed portion of the grid (not on the last line, the first line, or the edges?)

We go, and for each edge, we store a special value. We should call it NOTGRID. (as a contant, shove it into a header, make sure its a value that will never be produced from the calculations. Maybe -0? oxDEADC0DE?).

So, we can now just check that a value is on the grid, by checking that it is not NOGRID.

Simple enough?

Theres a harder way, which involved bitmasks (thats why you use PO2 dimentions), which can be used to tell if something is on the grid or not, just by using its adress.

Now notice, that the left-hand coloumn is all PO2.

And now, without further ado, i will tel you what to do.

What i'm basically going to do, is go and generate one expression to find if its on the board, and use lazy evaluation to make it fast.

what it basically is, is 3 parts.
What you do, is you precompute:
Size + 1, and store it in Si (where Size is the row size)
The adress of the seond-from-the bottom, in the righmost coloumn. Call it Di

First part:
X < si
Second part:
X > Di
Third part:
Ispo2(x & b11111......0)

Now, because either, your on the lefthand row, and your on the leftmost row, in which case, your a power of two
Or, your in the right-hand row, then your one off a power of two. In which case, you go and mask out the ones bit.

Theres a thread, on really really fast ways to tell if something is a power of two. (Search for it)

Edit: Found better metod. Something easier.

boolean isPowerOfTwo(int v){ return v & (v-1) == 0;}

I'm not sure if that works, i got it off another thread, but if it does, then :).
From,
Nice coder

[Edited by - Nice Coder on January 23, 2005 5:50:26 PM]

Thanks Nice Coder,

I was messing around with this yesterday, this is what I've work working so far.

InfluenceMap class which holds 2D array (without edges, but I like what you've done and might add that). Each element holds a InfluenceElement class which holds a SmartPtr to an object in that cell. If you try and increase the influence in that cell where an object has already exerted influence it will return. Otherwise it'll update the pointer, then increase the cell and surrounding cells using 2 for loops. Before it does this though, it looks through the array to find the previous position and negates the affect that that object once had.

I'm also going to use the InfluenceElement object for an A* implementation by holding a penalty value for crossing a cell.

~Red

There is a reson why i do not like 2D arrays, when not nessisary.

The 2D array, is actually a 1D array, with extras.

So, if your 2D array, is 2 * 4, then it would be a 1D array of size 14.

Now, if you try to acess [1][3], then it looks up row 1 * 5 + 3 which is element 8.

Formula C * (Rowlength + 1) + R
Rowlength is the length of the row, C is the coloumn, and R is the row.
Acessed as Array[C][R].

To start with
[0][0] = 0
[0][1] = 1
[0][2] = 2
[0][3] = 3
[0][4] = 4
[1][0] = 5
[1][1] = 6
.....
[2][0] = 10
[2][1] = 11
[2][2] = 12
[2][3] = 13
[2][4] = 14

So, you basically loose control of how the array is used. And it can be pretty hard, once you consider how easy the 1D method is.

The way your using it for A* is good. Very good. But i would recommend a slightly more complex method then doing two for loops (please, it isn't good).

What you can do, if your interested in being very sneaky about making this
implementation good, is that you go and make up a list (make up an array(or
vector) of a few hundred elements (Try 64K, and be sure that if your using a
vector, that your reserve 64K or more (if you have a massive influence table))).

Now, what you do, is you add to the array (use it as a stack, with a variable
keeping the first avalible space, and be sure to get it out the right way, to
increase cache efficiency (if done right, this can be really fast, and
will give you more time to do other stuff, like the rest of the pathfinding) the
elements you are going to change.

Now, what you do, is you go into a loop:

loop:X = Value popped off the stack array.Z1-8 = The values neibors (you keep a vector of the struct).Calculate the new values, using TMP1-8 as variables.for x = 1 to 8if the value at Zx is too far different from TMPx then   Add TMPx to the stack, if its not already there.end ifSet Zx to be the value of TMPxnext xContinue looping until the stack is empty.

That is good enough for most things, but when you have the need for speed, there
is a faster way.

Set weighting to a set largish valueSet Stack as new stackSet Z[0]-Z[7] as integerLoop:X = Stack.popZ[0] = X - 1..... // Calcualte new positions for the Z's, and check them. if they are off the board, then remove them.For each ZCalculate the new Value for this Z, and call it TMP[x] where X is the Z's index.For each Z,Take the difference between TMP[x] and Z[x], and multiply it by C/W. Where C isa constant, and W is Z's weighting.For each Z,Generate a new weighting, by splitting up X's weighting, based on the values calculated beforehand. (so its basically sliced up.)Remove any Z's with a very small weighting (less then 0.001 maybe?)You now add each Z to the stack, and sort the stack, so that those with thegreatest Weighting is at the top. And remove duplicates, by removing the previous values from the stack. (so, if there is node n which is on the stack,and you add m which is the same as n, just with a different weighting, youremove n, and add m at the right spot for its weighting.)Continue looping until you run out of time, or the stack is empty.

This should work, but i just came up with it.

It would basically do a search, looking and changine the values.

Just remember, you just need to figure out the right spot to shove your values.
You don't need to sesort the list every time (it would just be slow). Look up
the binary search.

What your doing seems fine, its probably going to be really slow for bigish
arrays tho, and your not going to diffuse the values properly, with the
thermodynamic model. That needs a lot of iterations until it hits equilibrium,
which is why i would use the algorithm above, it probably never hits equibrium,
but it gets there faster (nodes/change) then anything else probably would.

From,
Nice coder

[Edited by - Nice Coder on January 25, 2005 2:22:40 AM]