freddynewtondev said:
Do I have to measure the distance for each node I have with Dijkstra and then calculate the influence based on that? Surely that is quite expensive?

I don't know what ‘Influence Maps’ really is, but i assume it is about replacing greedy path finding like Dijkstra with diffusion approaches. At 15:00 ion the video i see this happening, so probably i'm right (did not listen what they say, though).

But to be sure, this would be an example of diffusion approach: We have a grid or a navmesh representing a labyrinth, a player and enemies. To make the enemies find the player, we drop fluid from the player to the grid. The fluid flows through the labyrinth. Each enemy can then find the player by following the mass gradient of the fluid. So that's very fast in a single source / many targets (or vice versa) situation. It also gives nice and natural motion for the enemies. Is it that what you want?

I have implemented such diffusion stuff for other applications. For a mesh it is more difficult, requiring to set up cotan weights for triangles (to ensure drop of fluid diffuses equally fast in every direction) and backwards euler integration, so solving a large linear system (see https://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/​ for example). I have replaced this later with Mean Value Weights and Harmonic Map, which is much faster and good enough for my needs (crossfields / wavefields on meshes for geometry processing).

For a grid it is easier because all cells are the same, so weights are trivial. Recently i worked on erosion simulation like here: https://hal.inria.fr/inria-00402079/document​ This contains a shallow water simulation which is quite simple and fast, though the fluidy behavior is not really desired here so needs to be simplified…

I think you get away by simply blurring the fluid. For each grid cell you could set the next steps fluid amount to be the average of the 3x3 neighborhood the current cell. Blocked cells (obstacles) can't get any fluid, so it will diffuse around them and so create the path to the goal as expected.

To get circular diffusion (so diagonal directions behave equally to horizontal / vertical ones) i propose those weights for the average:

1/16  2/16  1/16
2/16  4/16  2/16
1/16  2/16  1/16

Which simply is a box filter of 2x2 grid cells size.

In the video above, the results shows rectangular diffusion instead circular. Probably they used just the left/right and top/bottom neighboring cells.

Hope this helps and i haven't completely missed the point. ; )

freddynewtondev said:
need to find some blurry algorithm and then iterate through the neighbour or so

Yeah, but that's trivial. But it should be fast. Usually it's recommended to split the blur into a horizontal pass followed by a vertical pass, as common in image processing. Advantage is inner loops need to access only 2 neighbors each. An additional temporary image is needed to store the result from H pass and use it as input for the V pass:

	template <typename T>
	static void BlurTexture2x (T *dstTexture, 
		const T *srcTexture, const int *size)
	{
		const int FY = size[0];
		
		for (int y=0; y<size[1]; y++)
		{
			for (int x=1; x<size[0]-1; x++)
			{
				int g = x + y*FY;
				T sample = srcTexture[g] * 2;
				sample += srcTexture[g+1];
				sample += srcTexture[g-1];
				dstTexture[g] = sample * 0.25f;
			}
			{
				int g = y*FY;
				T sample = srcTexture[g] * 2;
				sample += srcTexture[g+1];
				dstTexture[g] = sample / 3.0f;
			}
			{
				int g = size[0]-1 + y*FY;
				T sample = srcTexture[g] * 2;
				sample += srcTexture[g-1];
				dstTexture[g] = sample / 3.0f;
			}
		}
	}

	template <typename T>
	static void BlurTexture2y (T *dstTexture, 
		const T *srcTexture, const int *size)
	{
		const int FY = size[0];
		
		for (int x=0; x<size[0]; x++)
		{
			for (int y=1; y<size[1]-1; y++)
			{
				int g = x + y*FY;
				T sample = srcTexture[g] * 2;
				sample += srcTexture[g+FY];
				sample += srcTexture[g-FY];
				dstTexture[g] = sample * 0.25f;
			}
			{
				int g = x;
				T sample = srcTexture[g] * 2;
				sample += srcTexture[g+FY];
				dstTexture[g] = sample / 3.0f;
			}
			{
				int g = x + (size[1]-1)*FY;
				T sample = srcTexture[g] * 2;
				sample += srcTexture[g-FY];
				dstTexture[g] = sample / 3.0f;
			}
		}
	}
	
	template <typename T>
	static void BlurTexture2 (T *dstTexture, 
		const T *srcTexture, const int *dstSize, T *tempTexture)
	{
		BlurTexture2x (tempTexture, srcTexture, dstSize);
		BlurTexture2y (dstTexture, tempTexture, dstSize);
	}

(above code does not skip and ignore obstacles ofc. - it's just a blur)

Though, i did not see a huge speed up form that 2 pass approach, and iterating all neighbors in a double nested loop is fine too.

Another idea of optimization would be to combine the blur with calculating the gradient vector required for movement (which accesses the same neighbors again). But this only makes sense if number of agents is not too small in comparison to number of total grid cells - otherwise calculating the gradient only where needed should be faster.

If your units can move in any direction (not just exactly 45 or 90 degree angles), there are some options about quality: The gradient can be calculated form all 8 neighbors (not just 4 as usual), and the lookup from agent to gradient field can be point sampled (using only one cell), bilinear filtered (interpolationg 2x2 cells) or using cubic filter (interpolating 3x3 cells).

The cubic filter always gives nice curves for a trajectory paths. Unlike bilinear which gives only line segments.
Can make quite a difference if grid resolution is low. Here's an image where i've used highest quality settings to trace paths of sediment transfer for erosion simulation:

(It's still visible line segments, but only because i used large steps for the tracing.)

I'll implement a small test game for my idea and post code…
Curious myself how it works : )

… halfway done already.

Green dot is player, now only need to make the other chasing him.

Gradient field looks good for straight walls. Enemy on the other side will find the player:

But energy leaks through diagonal walls - won't work:

Will try to fix that using only 4 directional blur…

Yeah that's better:

Though it won't give the shortest path, but hard to improve this.

Will continue later…