1 hour ago, alvaro said:

Oh, I didn't realize that's what you were using it for. In that case I can't think of anything better than Dijkstra's algorithm.

Flood fill is generally a breadth-first search rather than Djikstra's. There's no early termination of the search, no variable edge weights, you don't care about traversing the lowest-cost nodes first, and you don't revisit nodes you've already visited once.

So long as the edge weights are constant, BFS should produce the same results as Djikstras, and in less time.

Looking at OP code again, this seems NOT intended to find the single shortest path between source and target, but to find paths from all points to a single target?

In that case A-Star makes no sense and Dijkstra is the way to go.

Also we may need to differentiate between 'flood filling' and 'region growing'. Region growing seems the better term for OP code and my comments.

So you could try the priority queue as in my code, but i assume that's only slower for you (but not sure). Still i think the neighoursAdded flag is redundant and can be removed, and then you may already have Dijkstra. So little room for improvement other than memory alloc and access.

3 hours ago, JoeJ said:

In that case A-Star makes no sense and Dijkstra is the way to go.

Ok, I get that we're a fancy game development forum and all... but what is up with everyone being obsessed with fancy path finding algorithms instead of the basic, vanilla breadth-first search?  

Breadth-first search is sufficient for this case, is simpler to write, and has the better time-complexity than the most optimal variants of A* or Djikstra.

You would only need an actual path-finding algorithm here if there were variable-weight edges in the graph.

18 minutes ago, swiftcoder said:

You would only need an actual path-finding algorithm here if there were variable-weight edges in the graph, or if there were obstacles to path around.

Oh, agree - You're right.

I just assumed blocked regions, but in the code every node is assigned to the same high number, so no obstacles - no need for path finding. But even no need for BFS, just Manhattan distance would do it ???

Really confused now about what's the problem is

Edit: Ah, there's mapCollisionMatrix, so obstacles.

2 hours ago, swiftcoder said:

Breadth-first search is sufficient for this case, is simpler to write, and has the better time-complexity than the most optimal variants of A* or Djikstra.

I became a bit uncertain. Below is the code i've in mind, please take a look if you think it can be improved. To me this is still Dijkstra, it just uses BFS instead priority queue.

@EddieK

This proofs additional flag like in your code is not necessary, i use only one stream of data for everything. 

It should also be possible to avoid the previous array, and instead search for the closest neighbour by looking at the distance stored in data to build the path. Depends on how many paths you extract what's better.

			int data [8*8] = {
				1,1,1,1,1,1,1,1,
				1,0,0,0,0,7,0,1,
				1,0,0,0,0,0,0,1,
				1,0,0,1,1,1,1,1,
				1,0,0,1,0,9,0,1,
				1,0,0,1,0,0,0,1,
				1,0,0,0,0,0,0,1,
				1,1,1,1,1,1,1,1};

			int start = 0, target = 0;
			for (int i=0; i<64; i++)
			{
				int x = data[i];
				if (x==7) start = i;
				if (x==9) target = i;
				data[i] = (x == 1 ? 1000 : 999);
			}

			int previous[64] = {};
			int stack[64];
			stack[0] = target;
			data[target] = 0;
			int tail = 1;

			for (int i=0; i<tail; i++)
			{
				int c = stack[i];
				int distC = data[c];
				int distN = distC + 1;

				//if (c==start) break; // optional early out if we want only one path

				int x = c&7;
				int y = (c>>3);
				for (int j=0; j<4; j++)
				{
					int n = c;
					switch (j)
					{
						case 0: n++; break;
						case 1: n--; break;
						case 2: n+=8; break;
						default: n-=8;
					}
					if (data[n] == 1000) continue;
					
					if (distN < data[n])
					{
						data[n] = distN;
						previous[n] = c;
						stack[tail++] = n; 
					}
				}
			}

			char output[8][9] = {};

			for (int y=0; y<8; y++) for (int x=0; x<8; x++) 
			{
				output[y][x] = data[y*8+x] == 1000 ? 'X' : ' ';
			}

			int path = start;
			while (path)
			{
				output[path>>3][path&7] = '@';
				path = previous[path];
			}

			for (int y=0; y<8; y++) 
			{
				SystemTools::Log(output[y]);
				SystemTools::Log("\n");
			}
ouput:

XXXXXXXX
X    @ X
X @@@@ X
X @XXXXX
X @X@@ X
X @X@  X
X @@@  X
XXXXXXXX

2 hours ago, JoeJ said:

Edit: Ah, there's mapCollisionMatrix, so obstacles.

So there is. I somehow missed that.

17 minutes ago, JoeJ said:

To me this is still Dijkstra, it just uses BFS instead priority queue.

Breadth-first search is Djikstra's without the priority queue. The only difference between the two is that Djikstra's needs a priority queue to deal with edge weights that aren't equal to one.

10 minutes ago, swiftcoder said:

The only difference between the two is that Djikstra's needs a priority queue to deal with edge weights that aren't equal to one.

Disagree, i used method almost as above with weights, priority queue only makes it faster. But probably we just argue about terminology - that's not my strength

When using the open/closed system, or "visited/unvisited" flags, the priority queue is necessary. It saves considerably on redundant calculations, and it is the most common implementation.  If the higher cost nodes can be evaluated first then they may visit a node and change the flag, and a lower cost path won't evaluate it because it has already been visited.

18 hours ago, EddieK said:

But how would I implement it to generate a gradient map where each node shows the distance to the target node?

Since this looks like a complete fill of the space relative to the target node, it seems that you're expanding out from that point and you don't need to do anything else.

As mentioned above, plain old Dijkstra's shortest path tree algorithm could do it.  If you have the target node as the starting point with 0 cost, then store the costs in a second 192x192 grid as you visit the nodes, that grid will generate your gradient map automatically.  By keeping the open/closed flags -- which can simply be a test to see if there is a value in the cell already -- you can guarantee you won't visit any node more than once.  So 192*192=36864 nodes to process in the worst case.  This works the same as most flood fill algorithms.

Without the open/close tests and a sorted list to work from the smallest paths first, there is potentially far more processing since newly discovered shorter paths trigger a new round of tests on their neighbors, potentially causing paths to be re-evaluated many times as different paths through the map are evaluated. It will still finish eventually, but the same 192x192 grid may require several hundred thousand steps rather than just 37 thousand steps.