Looks like this thread got derailed. Going over the problem statement again:

This tile neighbour seeking algorithm for a maximum of 8 surrounding tiles is extremely slow, if I got 54x50 tiles in a grid, and I have to compare 2700 tiles against another 2700 tiles, which takes an hour or so to complete. How do I speed up this process?

Reading that statement again slowly, a problem emerges.

Are you attempting to compare each of the 2700 tiles against all other 2700 tiles?

Going over your code, that's what it looks like:

...
  for (auto& from : m_walkables)  // 2700 loops
    {		
    std::vector neighbours;	 
    // walk walkables		 
    for (auto& to : m_walkables) // another 2700 loops, combined with the one above, that's 7.29 million iterations
      {
         ... call to.GetX(), from.GetX(), to.GetZ() and from.GetZ() four times each rather than caching their values. Are these expensive? ...
         if (getCost(from, to) >= 0) {  // Your code.  Is this expensive?
           neighbours.push_back(to);  // Potentially very bad performance. This is probably triggering an allocation, meaning potentially major performance hit.
         }
         cout << "Neighbour size: " << neighbours.size() << endl; // Calls to IO are slow.
         from.setNeighbours(neighbours); // Your code. Is this expensive?
	} 
...

So you have a loop of 7290000 iterations.

You're making roughly 28 million calls each to GetX and GetZ for the two objects, potentially doing millions of vector resizes, and potentially calling your setNeighbours function seven million times or so.

Even if your functions are moderately fast, the rest of that block is going to be quite slow mostly because of the number of times you call it.

Is that really the algorithm you wanted? 7.29 million iterations?

My guess is that you are only wanting to test the (up to) eight surrounding cells, which means 2700 iterations through a loop.

Something along the lines of:

for(int y=0; y<height; y++) {

for( int x=0; x<width; x++) {

DoNestedTest( walkables, x, y, x-1, y-1 );

DoNestedTest( walkables, x, y, x, y-1 );

This makes a single pass through the walkables and tests the ones around it, doing whatever it is that you are doing. It tests each of the eight bordering items, only about 20 thousand tests rather than over 7 million tests.

Or, if you are building a bi-directional association, just test the one to the side and the one below (of course skipping the ones past the border) and do your work there. That's only about 5000 test iterations.

Of course, if the functions you are calling are doing something more spectacular and you really do need an all-to-all comparison, then you'll probably want to do something else.

Looks like this thread got derailed. Going over the problem statement again:


Reading that statement again slowly, a problem emerges.

Are you attempting to compare each of the 2700 tiles against all other 2700 tiles?



You're making roughly 28 million calls each to GetX and GetZ for the two objects, potentially doing millions of vector resizes, and potentially calling your setNeighbours function seven million times or so.

Even if your functions are moderately fast, the rest of that block is going to be quite slow mostly because of the number of times you call it.




Is that really the algorithm you wanted? 7.29 million iterations?

I'm guessing, based on the existence of GetX and GetZ functions, that the data structure is LITERALLY just an array of tiles, where individual tiles can be placed pretty much arbitrarily (as opposed to a more traditional tilemap-like structure).

So since a tile's position in the array is independent of it's actual location, he HAS to compare tiles against each other to find adjacent tiles.

Determining whether or not this is an appropriate data structure for what he's doing (even though it probably isn't) should be the first step in optimizing neighbor-search.