started a little game, using potential maps to do my pathfinding. a lot of the stuff online seems to involve precomputing your potential map, but i want to do it real time, procedurally. at the moment, ive got an array which contains the potential for each cell, and each frame the potential is recalculated based on the potential of the 8 surrounding cells and itself (ie take the average). is there a better model for dispersion of potential based on the fact that i would want to be in control of decay, falloff, spread rate, etc? for example, i may have two potential maps, one for sound and one for light, and i would (for example) want the sound potential map to have a shorter falloff and slower spread rate than the light potential map. cheers.

A "better" model how? More accurate? More flexible? Faster?

As far as the speed goes, you could get the GPU to do it. Should be fairly simple. Just use the old map as input texture, and render a new texture by sampling neighboring texels on the old map.

yeah, i guess more accuracy and flexibility is what im after, so if i have a single high point of influence on my potential map, i can specify what the falloff will look like with distance (ie exponential, linear), and the maximum distance. specifying these neednt be explicit, but it would be nice to have that sort of control.

Just store the parameters for your potential function per region and compute the force contributions on each body from each potential source on the fly. If you have many thousands of sources and/or sinks you may want to consider an efficient spatially partitioned data structure (such as a quad, oct or k-d tree, as appropriate) for efficient range searches.

The inefficient aspect of computing potentials on the fly is the distance checks, which will chew up clock cycles quickly if you have many sources/sinks and many dynamic objects. Consider caching previous values and using approximations where possible.

Cheers,

Timkin

i'm getting around the distance checks by, instead of calculating the potential each frame, allowing the potential to spread like a gas.

i was working on this again last night, and i realised that as i'm getting the gas to flow based on an average of a cell's surrounding cells, the falloff will always be 1/r^2. taking the square root (or cube root) of the potential map allows for linear(ish) falloffs, hooray!

Quote: Original post by combatdave
i'm getting around the distance checks by, instead of calculating the potential each frame, allowing the potential to spread like a gas.

i was working on this again last night, and i realised that as i'm getting the gas to flow based on an average of a cell's surrounding cells, the falloff will always be 1/r^2. taking the square root (or cube root) of the potential map allows for linear(ish) falloffs, hooray!

...so you're doing a simple diffusion then...

The simplest way to implement this on a discrete grid is with a matrix convolution. Your kernel would be (given your initial description) a 3x3 matrix with entries that sum to 1. You need to add padding cells around your map with constant zero potential in them. Then simply perform a convolution of your map grid and your kernel to get the updated potential for a cell.

One note though: you'll find that within a finite time this model converges to a steady state (or an oscillitory function of a finite set of states if you have constant inputs). This may not be desirable for your application, although given the limited amount of information you have provided it's not possible to discern.

Cheers,

Timkin

convolution matrices look like just the thing, cheers