I have a game-map like this:

char terrain[MAP_SIZE][MAP_SIZE];

And need to perform fast "expanding" checks. Starting at a tile (x,y) i want to find the closest tile from the start-tile that has a certain value, and stopping directly when i find it. So i dont want to start at some distance from the start and do a 2D/nestled for() loop through ALL the tiles and check distance to the start-tile for each suitable tile.

Ties or diagonal distance can be ignored for optimization, so checking one "rectangular circle" at a time starting from the center is good enough. But how to do that efficiently? I might need a max-range so it stops after reaching the Nth "rectangular circle".

Thanks a lot!
Erik

1 hour ago, suliman said:

I have a game-map like this:

char terrain[MAP_SIZE][MAP_SIZE];

And need to perform fast "expanding" checks. Starting at a tile (x,y) i want to find the closest tile from the start-tile that has a certain value, and stopping directly when i find it. So i dont want to start at some distance from the start and do a 2D/nestled for() loop through ALL the tiles and check distance to the start-tile for each suitable tile.

Ties or diagonal distance can be ignored for optimization, so checking one "rectangular circle" at a time starting from the center is good enough. But how to do that efficiently? I might need a max-range so it stops after reaching the Nth "rectangular circle".

Thanks a lot!
Erik

Is it possible that in some game-condition DOES NOT EXIST the tile you are looking for ?

Yes if it's outside the map boundries (any indice is <0 or >=MAP_SIZE). Otherwise no.

Could it be sufficient to you to use a BFS algo and break out when you have found the element ?
 

  procedure BFS(G,v) is :

      create a queue Q
      create a set V
      enqueue v onto Q
      add v to V

      while Q is not empty loop

         t ← Q.dequeue()
         IF THIS IS WHAT WE ARE LOOKING FOR :
           return t
        end if

        for all edges e in G.adjacentEdges(t) loop
           u ← G.adjacentVertex(t,e)
           if u is not in V then
              add u to V
               enqueue u onto Q
           end if
        end loop
     end loop

     return none

end BFS

Im more looking for a simple way of checking the tiles directly, one "rectangural circle" at a time. A way to find the edging tiles/adjacent  tiles if you will. Your pseudo code doesnt explain that and introduces a lot of new stuff i'm not familiar with  No clever way of writing loops or something that checks from the inside?

how many "certain values" do you have?

If a simple expanding rect is not accurate enough, you could maybe pre-sort an array of indices (offsets) and use that for searching. (yet, for performance, the expanding rect might be quicker, simply due to how caches/ram works).

I think it's enough, but how would I implement a "expanding rect"? That is the question.

it's basically just a not-filled rect that expands every iteration, something like

ivec2 FindNearest(ivec2 o, int maxRange,int toFind)
{
  ivec2 ret(10000,1000);//some default initialization
  //the incrementing range, start an offset of 1 around the searching area
  for(int range = 1; range < maxRange; range++)
  {
    //now loop around the search area
    for(int i=-range;i<=range;i++)
    {
      ivec2 above(o.x+i,o.y-range);
      ivec2 below(o.x+i,o.y+range);
      ivec2 left(o.x-range,o.y+i);
      ivec2 right(o.x+range,o.y+i);
      if(Pixel(above)==toFind && length(above-o)<length(ret-o))
        ret=above;	//you could trim here "maxRange" to length(above-o), as it makes no sense to search further than that to find a "closer" 
      if(Pixel(below)==toFind && length(below-o)<length(ret-o))
        ret=below;
      if(Pixel(left)==toFind && length(left-o)<length(ret-o))
        ret=left;
      if(Pixel(right)==toFind && length(right-o)<length(ret-o))
        ret=right;
    }
  }
  return ret;
}

that's just a minimal/readable example, you can clearly improve that by e.g. storing the current best range instead of repeating length(ret-o) and trim maxRange etc.

"Pixel" is the function that reads from your field/array/vector/image/texture/etc. to find "toFind"

ivec2 is just a struct(int x; int y;}; as you'd use in glsl

length is your distance evaluation functions, could be sqrt(x*x+y*y) or abs(x)+abs(y),

Just as an aside, this is a very common, but slow operation. There are a number of special cases such as edge conditions, and also if you need euclidean nearest neighbour (although sounds like you are happy with manhattan distance).

Usually there is a better way to design around this problem. For instance for static nearest searches, you can simply precalculate the nearest neighbour for each gridsquare. For dynamic searches, (assuming you are going for efficiency as you say, rather than the simplest code) there is usually a faster algorithm, perhaps using a different spatial partitioning system or a coarser grid combined with a more accurate check. It may depend on the particular use case as to which method is best. (What for example would this search be used for?)

For instance, if you are trying to find the nearest of 16 enemies on a grid of 10x10 squares, it will probably be much faster to consider each of the 16 cases by brute force than to consider each of 100 squares. This speedup is likely to be more significant once you start using larger grid sizes.

Hmm yes it would be used for workers to find "tree"-tiles on the terrain, to find the closest tree to move to next (when harvesting wood). The trees as stored as a flag in the tile, which are grid-based over the entire map. So actually i have more date stored for each "tile" than terraintype.

So should i stored "trees" (or whatever) in a list instead?
And maybe have a tree-list for each section of the map? (like each 40x40 tiles)

Otherwise as the map is big, the list will be populated with thousands (all of them) of trees and checking distance to all of them each time a worker needs to decide which tree to go to next seems very slow. The same problem to look for enemies to attack; i dont want a mega list for the entire game world, right? A unit should look at a local, smaller list holding only trees/enemies/whatever residing in that region?