# optimizing expanding tilecheck

This topic is 3901 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Topic :) But i might need to explain. I do a rts with rather big tiles, think civ 3 and need to do loads of "finding the closest X-tile", something like
//i need to find the closest tile==22 (water) from tile x,y
checkExpanding(x,y){
if(gameMap.tile[checkX][checkY]==22){
doStuff()
break;
}
}


Like a define or something that can check the tiles in expanding "frames" around the given starting point. I need to be able to specify the condition for "the right frame". Ive tried making this but it results in extremely ugly non-reusable functions with lots of if-cases... Thanks for your help. Erik

##### Share on other sites
i dont really understand what your question is, but here goes:

you could probably use function pointers to create a callback function:

void doSomething( x , y , int tileid );
checkExpanding( x,y,doSomething );

or:

void doSomething( x , y );
checkExpanding( x , y , tileid , doSomething )

ill probably be way of course

##### Share on other sites
So you want to find the closest tile to (x, y) that has a property P?

Simple, all you do is start at (x, y), and check gradually further away until you find a matching tile.

The questions are: (a) how are you defining "closest"? (Pythagorean or Manhattan distance would be most common) and (b) how do you want to break ties (or does it matter)?

After that, the tricky part is figuring out how to get the next-furthest-away tile.

##### Share on other sites
i want to keep it very fast so i dont even plan on using pythagoras for distance.

a function which checks all surrounding 8 tiles first (starting at lets say upper left courner), the the 16 around that etc and stops and returns a good match as fast as one is found. A tie= dont care just stop at first ok tile. The problem is i dont know how to make such a function, where i also can change the condition defining what the "right tile" is.

##### Share on other sites
 // A position object, simpler for handling 2D positionsstruct pos { int i, j; };// An "attempt" class, used to check whether a tile at a certain // offset from position 'c' in map 'gameMap' satisfies predicate 'p'// or not (and stores the resulting absolute position in 'out').// Yes, you functional language fans, this is a closure!template <typename Pred>struct Attempt{  const post & c;  const Map & gameMap;  const Pred & p;  Attempt(const Map & gameMap, const pos & c, const Pred & p)     : c(c), gameMap(gameMap), p(p) {}    bool operator()(const pos & offset, pos & out) const {    return (*this)(offset.i, offset.j, out);  }  bool operator()(int i, int j, pos & out) const {    out.i = c.i + i;    out.j = c.j + j;    if (out.i < 0 || out.i >= gameMap.width) return false;    if (out.j < 0 || out.j >= gameMap.height) return false;    const Tile & t = gameMap.tile[out.i][out.j];    return p(t);  }}// The actual search function.template <typename Pred>pos findNearest(const Map & gameMap, const pos & c, const Pred & p){  // The closure used to determine predicate satisfaction.  Attempt<Pred> check(gameMap,c,p);  // The position where the correct tile will be stored.  pos out;  // Distance 1, hard-coded offsets --------------------------------  static const pos one[] = {     { 1, 0 }, { 1, 1 }, { 1, -1 }, { 0, 1 },     { 0, -1 }, { -1, 0 }, { -1, 1 }, { -1, -1 }  };  for (int i = 0; i < sizeof(one) / sizeof(pos); ++i)  {    if (check(one, out)) return out;  }  // Distance 2, hard-coded offsets --------------------------------  static const pos two[] = {    { 2, 0 }, { 2, 1 }, { 2, 2 }, { 2, -1 }, { 2, -2 }    { 1, 2 }, { 1, -2 }, { 0, 2 }, { 0, -2 },    { -2, 0 }, { -2, 1 }, { -2, 2 }, { -2, -1 }, { -2, -2 }  };  for (int i = 0; i < sizeof(two) / sizeof(pos); ++i)  {    if (check(two, out)) return out;  }  // Distances d > 2, use an algorithm for examining them ----------  const int max = std::max(gameMap.width,gameMap.height);  for (int d = 3; d < max; ++d)   {    for (int i = -d; i <= d; ++i)    {      if (check(-d,i,out)) return out;      if (check(d,i,out)) return out;      if (check(i,d,out)) return out;      if (check(i,-d,out)) return out;    }  }  throw TileNotFound;}

##### Share on other sites
"Breadth first search" would be a useful search term for this situation.

##### Share on other sites
Quote:
 "Breadth first search" would be a useful search term for this situation.

and "Dijkstra's algorithm" if distance between tiles isn't constant.

##### Share on other sites
Quote:
 Original post by ToohrVyk *** Source Snippet Removed ***

A nice solution but not pratical or rather a bit of overkill (remember KIS - keep it simple). The main problem is that the search function is instantiated for each type of predicate, thus increasing code size (one of the downsides to templates). The search function doesn't really care about the predicate type and will behave the same regardless of the predicate type. Also, code size will increase for each implementation of the search method (e.g. random tile matching the predicate). Also, throwing an exception at the end is probably undesirable as not finding a matching tile is possibly valid (it's a minor point).

I think a simpler method is to use polymorphism. For example:
bool GameMap::FindNearest (const Point &c, IPredicate &predicate){  bool    found = false;  for each tile in search space  {    if (predicate.Check (the tile))    {      found = true;      break;    }  }  return found;}

This function returns true if a tile is found that meets the predicate or false if no tile found. But wait, how does the caller know which tile was found? Let's look at IPredicate:
class IPredicate{public:  virtual bool Check (GameMap &map, const Point &p) = 0;};

A pure virtual base class, the implementation of Check needs to be provided by a derived class:
class CheckTileType : public IPredicate{public:  CheckTileType (TileType type) : m_type (type)  {  }  Point MatchedPoint (void)  {     return m_matched_point;  }private:  virtual bool Check (GameMap &map, const Point &p)  {    bool      match = false;    if (map.Tile .Type == m_type)    {      match = true;      m_matched_point = p;    }    return match;  }  Point    m_matched_point;  const TileType    m_type;};

And use it like this:
  Check    predicate (TileType.Desert);  if (map.FindNearest (search_centre, predicate))  {    Point      pos = predicate.MatchedPoint ();    // do something with the position  }

So, for each new predicate class the code size of the search function remains constant and for each new search method the code size is not dependant on the number of predicate types that are used with it.

I think it's a lot clearer and easier to follow what's going on. I agree that templates have their place, but here I think it's a bit unnecessary - it is the 'For Beginners' section afterall.

Skizz

Nitpicker's Corner: Yes, I know that PCs have gigabytes of RAM these days, but it's generally a good idea to keep your resource usage to a minimum. Consider the GameBoy where bigger ROMs cost more and reduce profit.

##### Share on other sites
Quote:
 Original post by SkizzThe main problem is that the search function is instantiated for each type of predicate, thus increasing code size (one of the downsides to templates).

It would probably be instantiated once for bool (*)(const tile&), and once for IPredicate [wink], so that's not too heavy. Note that I'm thinking of a very simple IPredicate along the lines of:

struct IPredicate {   virtual bool operator()(const tile &);};

Quote:
 Also, throwing an exception at the end is probably undesirable as not finding a matching tile is possibly valid (it's a minor point).

I admit that I was too lazy to alter the function signature to boost::optional<pos> [smile]

##### Share on other sites
hmm this blew out of proportions. I just need to iterate through a 2D position starting at a given position (expanding in cicles (or more specifically rectangles) around that start-position) with the posibility to react and interupt the iteration. It needs to be fast and all i can write includes a lot of ifs and loops everywhere.

Like so:

//start at 12,20. This define/function iterates through myLoopX and myLoopY and i can check these values to check tiles etc expanding from the starting position.myLoopThingy(12,20)//here i can add whatever i likeif(myMap[myLoopX][myLoopY]==somethingCool){   setGoal(myLoopX,myLoopY);   break;}   if(myLoopCurrentDistance&gt;8)   break;//end of iterationendMyLoopThingy

[Edited by - suliman on June 20, 2007 11:55:02 AM]

##### Share on other sites
Something like this then:
enum CheckResult{    NotFound,    Found,    Clipped};//  IPredicate is described in my previous postbool Map::Find (int x, int y, IPredicate *predicate){    bool        found = false;    //  Do the single tile at (x,y) first    if (predicate->Check (x, y))    {        found = true;    }    else    {        //  do an expanding square search        //  this algorithm skips tiles that are outside the map area as efficently as possible,        //  i.e. the innermost loop does no (x,y) checking and only tiles on the map are considered        //  the map area is given by (m_min_x,m_min_y)-(m_max_x,m_max_y)        int            clip_flags = 0, // this is a bitfield used to identify which edges of the search square are off the map                            // bit 0 = top,                            // bit 1 = bottom,                            // bit 2 = left,                            // bit 3 = right            radius = 1; // the size of the search square: x+-radius,y+-radius inclusive        do        {            //  check the top of the square            if ((clip_flags & 0x1) == 0)            {                switch (CheckHorizontal (x - radius, x + radius, y - radius, predicate))                {                case Found:                    found = true;                    break;                case Clipped:                    clip_flags |= 0x01;                    break;                }            }            //  check the bottom of the square            if ((clip_flags & 0x2) == 0)            {                switch (CheckHorizontal (x - radius, x + radius, y + radius, predicate))                {                case Found:                    found = true;                    break;                case Clipped:                    clip_flags |= 0x02;                    break;                }            }            //  check the left of the square (don't need to do top,bottom of edge since that is done above)            if ((clip_flags & 0x4) == 0)            {                switch (CheckVertical (x - radius, y + radius - 1, y - radius + 1, predicate))                {                case Found:                    found = true;                    break;                case Clipped:                    clip_flags |= 0x04;                    break;                }            }            //  check the right of the square (don't need to do top,bottom of edge since that is done above)            if ((clip_flags & 0x8) == 0)            {                switch (CheckVertical (x + radius, y + radius - 1, y - radius + 1, predicate))                {                case Found:                    found = true;                    break;                case Clipped:                    clip_flags |= 0x08;                    break;                }            }            ++radius;        } while (!found && clip_flags != 0xf);    }    return found;}// do a horizontal line check, x values are inclusiveCheckResult Map::CheckHorizontal (int x_start, int x_end, int y, IPredicate *predicate){    CheckResult        result = NotFound;    if (y < m_min_y || y > m_max_y)    {        result = Clipped;    }    else    {        //  clip the horizontal line to the map size        int            search_start = Math::Max (m_min_x, x_start),            search_end = Math::Min (m_max_x, x_end);        //  do the search        for (int x = search_start ; x <= search_end ; ++x)        {            if (predicate->Check (x, y))            {                result = Found;                break;            }        }    }    return result;}CheckResult Map::CheckVertical (int x, int y_start, int y_end, IPredicate *predicate){    // TO DO}

Skizz