Hi, so I implemented this flood fill algorithm which works fine when the map is of size 96x96, but if I multiply this size by 2 (192x192) the algorithm becomes very slow and the game unplayable. 

How can I optimize this algorithm for it to run faster?

The algorithm in question:

    public void update(Node targetNode){
        if(lastTargetNode.equals(targetNode)){
            return;
        }
        lastTargetNode.set(targetNode.x, targetNode.y);
        nodesToCalculateSize = 0;
        targetNode.fScore = 0;
        for(int i = 0; i < mapWidth; i++){
            for(int j = 0; j < mapHeight; j++){
                gradientMap[i][j] = 999999;
            }
        }
        gradientMap[targetNode.y][targetNode.x] = 0;

        neighboursAdded[targetNode.y][targetNode.x] = true;
        nodesToCalculate[nodesToCalculateSize++] = targetNode;

        while(nodesToCalculateSize > 0){
            Node currentNode = nodesToCalculate[nodesToCalculateSize-- -1];
            neighboursAdded[currentNode.y][currentNode.x] = false;
            Node [] neighbours = getNeighbours(currentNode);
            for(int i = 0; i < neighboursCount; i++){
                if(gradientMap[neighbours[i].y][neighbours[i].x] == 999999) {
                    if(neighboursAdded[neighbours[i].y][neighbours[i].x] == false) {
                        nodesToCalculate[nodesToCalculateSize++] = neighbours[i];
                        neighboursAdded[neighbours[i].y][neighbours[i].x] = true;
                    }
                    gradientMap[neighbours[i].y][neighbours[i].x] = gradientMap[currentNode.y][currentNode.x] + 1;
                }
            }
        }
    }


    Node [] getNeighbours(Node node){
        neighboursCount = 0;
        if(node.y - 1 >= 0)
            if(mapCollisionMatrix[node.y - 1][node.x] == 0){
                neighbours[neighboursCount] = nodes[node.y - 1][node.x];
                neighboursCount++;
            }

        if(node.y + 1 < mapHeight)
            if(mapCollisionMatrix[node.y + 1][node.x] == 0){
                neighbours[neighboursCount] = nodes[node.y + 1][node.x];
                neighboursCount++;
            }
        if(node.x - 1 >= 0)
            if(mapCollisionMatrix[node.y][node.x - 1] == 0){
                neighbours[neighboursCount] = nodes[node.y][node.x - 1];
                neighboursCount++;
            }
        if(node.x + 1 < mapWidth)
            if(mapCollisionMatrix[node.y][node.x + 1] == 0){
                neighbours[neighboursCount] = nodes[node.y][node.x + 1];
                neighboursCount++;
            }

        return neighbours;
    }
                                               

Thanks in advance

EDIT: I removed ArrayList (Java) container and instead used an ordinary array and it improved the speed drastically.

Is this Dijkstra algorithm? I'm confused there is a need for neighboursAdded AND gradientMap, what's the purpose of neighboursAdded?

Below is my implementation of Dijkstra to calculate paths on a mesh for reference, but i assume on a grid with equal weights for all edges the priority queue is no win so it's not ideal for you. (But if some cells are 'harder' to pass than others, different weights make sense.)

However, you might better just skip all this and go to A-Star directly, which is faster.

int ShortestPaths (const int sourceVertexIndex,
			std::vector<float> &edgeWeights,
			const int destinationVertexIndex = -1, // optional: single target 
			const std::vector<bool> *isTargetVertex = 0) // optional: multiple targets
		{
			if (edgeWeights.size() != mEdges.size()) 
				CalculateEdgeLengths (edgeWeights);

			int n = mVertices.size();
		
			mPathPrevious.resize(n);
			std::fill (mPathPrevious.begin(), mPathPrevious.end(), -1);
		
			mPathMinDistance.resize(n);
			std::fill (mPathMinDistance.begin(), mPathMinDistance.end(), FLT_MAX);

			mPathMinDistance[sourceVertexIndex] = 0;


			struct Comparator
			{
				int operator() (const std::pair<int,float> &first, 
								const std::pair<int,float> &second)
				{
					return first.second > second.second;
				}
			};

			std::priority_queue< std::pair<int,float>, std::vector<std::pair<int,float> >, Comparator> queue;
			queue.push (std::make_pair(sourceVertexIndex, mPathMinDistance[sourceVertexIndex]));

			while (!queue.empty()) 
			{
				int c = queue.top().first;
				float distC = queue.top().second;
				queue.pop();
			
				if (isTargetVertex && (*isTargetVertex)[c])
					return c;
				if (c == destinationVertexIndex)
					return c;

				const std::vector<int> &edges = mVertices[c].edgeIndices;
				for (int i=0; i<edges.size(); i++)
				{
					int n = mEdges[edges[i]].OppositeVertex(c);
					float w = edgeWeights[edges[i]];

					float distN = distC + w;
					if (distN < mPathMinDistance[n])
					{
						mPathPrevious[n] = c;
						mPathMinDistance[n] = distN;
					
						queue.push(std::make_pair(n, mPathMinDistance[n]));
					}
				}
			}

			return -1;
		}

Just now, JoeJ said:

Is this Dijkstra algorithm?

Not Djikstra. Not a graph. It's a standard flood-fill (just like the paint bucket tool in MS Paint).

https://en.wikipedia.org/wiki/Flood_fill

That Wikipedia page has a discussion of scanline fill. That should be very fast (it was not too slow when implemented on a Z80 computer from 1983, so I am sure it flies now).

16 minutes ago, swiftcoder said:

Not Djikstra. Not a graph. It's a standard flood-fill (just like the paint bucket tool in MS Paint).

Hmmm, once i came up with flood filling approach on mesh myself, and later noticed it's the same as Dijkstra (just the 'slower' version not using a priority queue.) 

The difference is O(V^2) vs. O(ELogV):

https://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/

But that's about paths to all vertices, so i guess A-Star is worth it even with small (and uniform cost) grid for a single target vertex? Not sure, really.

In any case you could first reserve all memory and reuse it. Maybe it's just allocation that slows down.

I put together a little C++ demo for scanline fill (the way I understand it):

#include <iostream>
#include <vector>

struct Image {
  int height, width;
  
  std::vector<int> array;
  
  Image(int height, int width) : height(height), width(width), array(height * width, 0) {
  }
  
  int &operator()(int x, int y) {
    return array[y * width + x];
  }
};

// Assume the image(x,y) == target_color
void scanline_fill(Image &image, int x, int y, int target_color, int replacement_color) {
  int east;
  
  for (east = x ; east < image.width && image(east, y) == target_color; ++east)
    image(east, y) = replacement_color;
	  int west;
  
  for (west = x - 1; west >= 0 && image(west, y) == target_color; --west)
    image(west, y) = replacement_color;
  
  if (y > 0) {
    for (x = west + 1; x < east; ++x) {
      if (image(x, y - 1) == target_color)
        scanline_fill(image, x, y - 1, target_color, replacement_color);
    }
  }
  
  if (y < image.height - 1) {
    for (x = west + 1; x < east; ++x) {
      if (image(x, y + 1) == target_color)
        scanline_fill(image, x, y + 1, target_color, replacement_color);
    }
  }
}

int main() {
  Image image(10, 10);
  image(5,1) = 1;
  image(6,1) = 1;
  image(7,2) = 1;
  image(7,3) = 1;
  image(6,4) = 1;
  image(5,4) = 1;
  image(4,3) = 1;
  image(4,2) = 1;
  
  scanline_fill(image, 5, 5, 0, 2);
  
  for (int i = 0; i < 10; ++i) {
    for (int j = 0; j < 10; ++j)
      std::cout << image(j, i) << ' ';
    std::cout << '\n';
  }
  std::cout << '\n';
}

4 minutes ago, alvaro said:

I put together a little C++ demo for scanline fill (the way I understand it):

 

	#include <iostream>
#include <vector>
	struct Image {
  int height, width;
  std::vector<int> array;
	  Image(int height, int width) : height(height), width(width), array(height * width, 0) {
  }
	  int &operator()(int x, int y) {
    return array[y * width + x];
  }
};
	void scanline_fill(Image &image, int x, int y, int target_color, int replacement_color) {
  int east;
  for (east = x ; east < image.width && image(east, y) == target_color; ++east)
    image(east, y) = replacement_color;
	  int west;
  for (west = x - 1; west >= 0 && image(west, y) == target_color; --west)
    image(west, y) = replacement_color;
	  if (y > 0) {
    for (x = west + 1; x < east; ++x) {
      if (image(x, y - 1) == target_color)
        scanline_fill(image, x, y - 1, target_color, replacement_color);
    }
  }
  if (y < image.height - 1) {
    for (x = west + 1; x < east; ++x) {
      if (image(x, y + 1) == target_color)
        scanline_fill(image, x, y + 1, target_color, replacement_color);
    }
  }
}
	int main() {
  Image image(10, 10);
  image(5,1) = 1;
  image(6,1) = 1;
  image(7,2) = 1;
  image(7,3) = 1;
  image(6,4) = 1;
  image(5,4) = 1;
  image(4,3) = 1;
  image(4,2) = 1;
  scanline_fill(image, 5, 5, 0, 2);
  for (int i = 0; i < 10; ++i) {
    for (int j = 0; j < 10; ++j)
      std::cout << image(j, i) << ' ';
    std::cout << '\n';
  }
  std::cout << '\n';
}
	

 

 

 

That's nice. But how would I implement it to generate a gradient map where each node shows the distance to the target node?

Aside: flood-fill is one of the three most common algorithms asked in whiteboard coding interviews at the big companies I've interviewed with/for. You should spend some time understanding the exact performance/complexity tradeoffs of the various approaches.

1 minute ago, EddieK said:

That's nice. But how would I implement it to generate a gradient map where each node shows the distance to the target node?

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.

Have you used a profiler on the code yet?  It might show you what you could focus on.