git.maemo.org Git - lordsawar/blob - src/PathCalculator.cpp

   1 // Copyright (C) 2009 Ben Asselstine
   2 //
   3 //  This program is free software; you can redistribute it and/or modify
   4 //  it under the terms of the GNU General Public License as published by
   5 //  the Free Software Foundation; either version 3 of the License, or
   6 //  (at your option) any later version.
   7 //
   8 //  This program is distributed in the hope that it will be useful,
   9 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 //  GNU Library General Public License for more details.
  12 //
  13 //  You should have received a copy of the GNU General Public License
  14 //  along with this program; if not, write to the Free Software
  15 //  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  16 //  02110-1301, USA.
  17
  18 #include <stdlib.h>
  19 #include <string.h>
  20 #include <queue>
  21 #include "PathCalculator.h"
  22 #include "GameMap.h"
  23 #include "path.h"
  24 #include "stack.h"
  25 #include "maptile.h"
  26 #include "city.h"
  27 #include "stacklist.h"
  28 #include "armysetlist.h"
  29 #include "armyprodbase.h"
  30
  31 #define ENEMY_CITY_WEIGHT 10
  32 #define ENEMY_STACK_WEIGHT 10
  33 using namespace std;
  34 //#define debug(x) {cerr<<__FILE__<<": "<<__LINE__<<": "<<x<<flush<<endl;}
  35 #define debug(x)
  36
  37 void PathCalculator::populateNodeMap()
  38 {
  39   Vector<int> start = stack->getPos();
  40   int width = GameMap::getWidth();
  41   int height = GameMap::getHeight();
  42   if (start.x >= width || start.x < 0)
  43     return;
  44   if (start.y >= height || start.y < 0)
  45     return;
  46   size_t length = width * height * sizeof (struct node);
  47   nodes = (struct node*) malloc (length);
  48   memset (nodes, 0, length);
  49
  50   // Some notes concerning the path finding algorithm. The algorithm
  51   // uses two different lists. There is a nodes array, which contains how
  52   // many MP one needs to get to the location (x,y), and a process queue that
  53   // tells you at what point the number of movement points is calculated next.
  54   //
  55   // What we basically do is to start at the stack's position and calculate
  56   // the distance (i.e. MP needed to get there) in circles around the starting
  57   // position with the circles becoming increasingly larger. In detail, we
  58   // start by appending the starting position in the queue of positions to be
  59   // processed. Then, recursively, we take the first point in the queue and
  60   // recalculate the distance for all bordering tiles, assuming that we go
  61   // over this point and overwriting their current value if it is larger
  62   // than what we find now. Then, we append each modified tile to the queue of
  63   // tiles to be processed and continue. We stop when there are no more tiles
  64   // to process.
  65   //
  66   // Finally, all that is left is finding the minimum distance way from start
  67   // point to destination.
  68
  69   // the conversion between x/y coordinates and index is (size is map size)
  70   // index = y*width + x    <=>    x = index % width;   y = index / width
  71   std::queue<Vector<int> > process;
  72
  73   // initial filling of the nodes vector
  74   for (int i = 0; i < width*height; i++)
  75     {
  76       // -1 means don't know yet
  77       // -2 means can't go there at all
  78       // 0 or more is number of movement points needed to get there
  79       nodes[i].moves = -1;
  80       nodes[i].moves_left = 0;
  81       nodes[i].turns = 0;
  82       if (isBlocked(Vector<int>(i % width, i / width)))
  83         nodes[i].moves = -2;
  84     }
  85   int idx = start.toIndex();
  86   nodes[idx].moves = 0;
  87   nodes[idx].moves_left = stack->getMoves();
  88   nodes[idx].turns = 0;
  89
  90   // now the main loop
  91   process.push(start);
  92   while (!process.empty())
  93     {
  94       Vector<int> pos = process.front();
  95       process.pop();                          // remove the first item
  96
  97       std::list<Vector<int> > next = calcMoves(pos);
  98       for (std::list<Vector<int> >::iterator it = next.begin();
  99            it != next.end(); it++)
 100         process.push(*it);
 101     }
 102 }
 103
 104 PathCalculator::PathCalculator(const Stack *s, bool zig, int city_avoidance, int stack_avoidance)
 105 :stack(s), flying(s->isFlying()), d_bonus(s->calculateMoveBonus()),
 106     land_reset_moves(s->getMaxLandMoves()),
 107     boat_reset_moves(s->getMaxBoatMoves()), zigzag(zig), on_ship(stack->hasShip()), enemy_city_avoidance(city_avoidance), enemy_stack_avoidance(stack_avoidance), delete_stack(false)
 108 {
 109   populateNodeMap();
 110 }
 111
 112 PathCalculator::PathCalculator(Player *p, Vector<int> src, const ArmyProdBase *prodbase, bool zig, int city_avoidance, int stack_avoidance)
 113 {
 114   Stack *new_stack = Stack::createNonUniqueStack(p, src);
 115   Army *army;
 116   if (!prodbase)
 117     {
 118       ArmyProto *proto = Armysetlist::getInstance()->getScout(p->getArmyset());
 119       if (!proto)
 120         return;
 121       army = Army::createNonUniqueArmy (*proto, p);
 122     }
 123   else
 124     army = Army::createNonUniqueArmy (*prodbase, p);
 125
 126   if (!army)
 127     return;
 128   new_stack->push_back(army);
 129   stack = new_stack;
 130   flying = stack->isFlying();
 131   d_bonus = stack->calculateMoveBonus();
 132   land_reset_moves = stack->getMaxLandMoves();
 133   boat_reset_moves = stack->getMaxBoatMoves();
 134   zigzag = zig;
 135   enemy_city_avoidance = city_avoidance;
 136   enemy_stack_avoidance = stack_avoidance;
 137   on_ship = stack->hasShip();
 138   delete_stack = true;
 139   populateNodeMap();
 140 }
 141
 142 PathCalculator::PathCalculator(const Stack &s, bool zig, int city_avoidance, int stack_avoidance)
 143 {
 144   stack = new Stack(s);
 145   flying = stack->isFlying();
 146   d_bonus = stack->calculateMoveBonus();
 147   land_reset_moves = stack->getMaxLandMoves();
 148   boat_reset_moves = stack->getMaxBoatMoves();
 149   zigzag = zig;
 150   enemy_city_avoidance = city_avoidance;
 151   enemy_stack_avoidance = stack_avoidance;
 152   on_ship = stack->hasShip();
 153   delete_stack = true;
 154   populateNodeMap();
 155 }
 156
 157
 158 PathCalculator::PathCalculator(const PathCalculator &p)
 159 :stack(new Stack(*p.stack)), flying(p.flying), d_bonus(p.d_bonus),
 160     land_reset_moves(p.land_reset_moves),
 161     boat_reset_moves(p.boat_reset_moves), zigzag(p.zigzag), on_ship(p.on_ship),
 162     enemy_city_avoidance(p.enemy_city_avoidance), enemy_stack_avoidance(p.enemy_stack_avoidance), delete_stack(p.delete_stack)
 163 {
 164   int width = GameMap::getWidth();
 165   int height = GameMap::getHeight();
 166   size_t length = width * height * sizeof (struct node);
 167   nodes = (struct node*) malloc (length);
 168   for (size_t i = 0; i < length; i++)
 169     nodes[i] = p.nodes[i];
 170 }
 171
 172 bool PathCalculator::calcFinalMoves(Vector<int> pos, Vector<int> next)
 173 {
 174   bool traversable = false;
 175   int mp;
 176   int dxy = nodes[pos.toIndex()].moves;   // always >= 0
 177   //am i blocked from entering sx,sy from pos?
 178   bool is_blocked_dir = isBlockedDir(pos, next);
 179   printf("checking %d,%d to %d,%d\n", pos.x, pos.y, next.x, next.y);
 180   //printf("flying is %d\n", flying);
 181   //printf("isblockeddir is %d\n", is_blocked_dir);
 182   printf("moves of source is %d\n", dxy);
 183   if (!flying && is_blocked_dir)
 184     return false;
 185   //flyers can't go through the void
 186   if (flying && is_blocked_dir &&
 187       GameMap::getInstance()->getTile(next)->getMaptileType() == Tile::VOID)
 188     return false;
 189
 190   int dsxy = nodes[next.toIndex()].moves;
 191   printf("moves of dest is %d\n", dsxy);
 192   if (dsxy < -1)
 193     return false; //can't move there anyway
 194
 195   if (zigzag == false)
 196     {
 197       Vector<int> diff = pos - next;
 198       if (diff.x && diff.y)
 199         return false;
 200     }
 201   int newDsxy = dxy;
 202   mp = pointsToMoveTo(pos, next);
 203   printf("number of moves to get from source to dest is %d\n", mp);
 204   if (mp < 0)
 205     mp = 0;
 206   if (!flying && load_or_unload(pos, next, on_ship) == true)
 207     {
 208       printf("moves left for %d,%d is %d\n", pos.x, pos.y, nodes[pos.toIndex()].moves_left);
 209     mp = nodes[pos.toIndex()].moves_left;
 210   printf("correction, number of moves to get from source to dest is %d\n", mp);
 211     }
 212   newDsxy += mp;
 213   if (newDsxy == -1)
 214     printf("new algo STILL put -1 in for moves\n");
 215
 216   //printf("new value for source moves is %d\n", newDsxy);
 217   //printf("%d == -1 || %d > %d\n", dsxy, dsxy, newDsxy);
 218   if (dsxy == -1 || dsxy > newDsxy)
 219     {
 220       int idx = next.toIndex();
 221       nodes[idx].moves = newDsxy;
 222       nodes[idx].moves_left = nodes[pos.toIndex()].moves_left - mp;
 223       nodes[idx].turns = nodes[pos.toIndex()].turns;
 224       while (nodes[idx].moves_left <= 0)
 225         {
 226           if (on_ship)
 227             nodes[idx].moves_left += boat_reset_moves;
 228           else
 229             nodes[idx].moves_left += land_reset_moves;
 230           nodes[idx].turns++;
 231         }
 232
 233       // append the item to the queue
 234       traversable = true;
 235     }
 236   return traversable;
 237 }
 238
 239 bool PathCalculator::calcMoves(Vector<int> pos, Vector<int> next)
 240 {
 241   bool traversable = false;
 242   int mp;
 243   int dxy = nodes[pos.toIndex()].moves;   // always >= 0
 244   //am i blocked from entering sx,sy from pos?
 245   bool is_blocked_dir = isBlockedDir(pos, next);
 246   if (!flying && is_blocked_dir)
 247     return false;
 248   //flyers can't go through the void
 249   if (flying && is_blocked_dir &&
 250       GameMap::getInstance()->getTile(next)->getMaptileType() == Tile::VOID)
 251     return false;
 252
 253   int dsxy = nodes[next.toIndex()].moves;
 254   if (dsxy < -1)
 255     return false; //can't move there anyway
 256
 257   if (zigzag == false)
 258     {
 259       Vector<int> diff = pos - next;
 260       if (diff.x && diff.y)
 261         return false;
 262     }
 263   int newDsxy = dxy;
 264   mp = pointsToMoveTo(pos, next);
 265   if (mp < 0)
 266     mp = 0;
 267   if (!flying && load_or_unload(pos, next, on_ship) == true)
 268     mp = nodes[pos.toIndex()].moves_left;
 269   newDsxy += mp;
 270
 271   if (dsxy == -1 || dsxy > newDsxy)
 272     {
 273       int idx = next.toIndex();
 274       nodes[idx].moves = newDsxy;
 275       nodes[idx].moves_left = nodes[pos.toIndex()].moves_left - mp;
 276       nodes[idx].turns = nodes[pos.toIndex()].turns;
 277       while (nodes[idx].moves_left <= 0)
 278         {
 279           if (on_ship)
 280             nodes[idx].moves_left += boat_reset_moves;
 281           else
 282             nodes[idx].moves_left += land_reset_moves;
 283           nodes[idx].turns++;
 284         }
 285
 286       // append the item to the queue
 287       traversable = true;
 288     }
 289   return traversable;
 290 }
 291
 292 bool PathCalculator::calcFinalMoves(Vector<int> pos)
 293 {
 294   bool traversable = false;
 295   int width = GameMap::getWidth();
 296   int height = GameMap::getHeight();
 297   for (int sx = pos.x-1; sx <= pos.x+1; sx++)
 298     {
 299       if (sx < 0 || sx >= width)
 300         continue;
 301
 302       for (int sy = pos.y-1; sy <= pos.y+1; sy++)
 303         {
 304           if (sy < 0 || sy >= height)
 305             continue;
 306
 307           Vector<int> next = Vector<int>(sx, sy);
 308           if (pos == next)
 309             continue;
 310
 311           if (nodes[next.toIndex()].moves <= -1)
 312             continue;
 313           if (calcMoves(next, pos))
 314             traversable = true;
 315
 316         }
 317     }
 318   return traversable;
 319 }
 320
 321 std::list<Vector<int> > PathCalculator::calcMoves(Vector<int> pos)
 322 {
 323   int width = GameMap::getWidth();
 324   int height = GameMap::getHeight();
 325   std::list<Vector<int> > process;
 326   for (int sx = pos.x-1; sx <= pos.x+1; sx++)
 327     {
 328       if (sx < 0 || sx >= width)
 329         continue;
 330
 331       for (int sy = pos.y-1; sy <= pos.y+1; sy++)
 332         {
 333           if (sy < 0 || sy >= height)
 334             continue;
 335
 336           Vector<int> next = Vector<int>(sx, sy);
 337           if (pos == next)
 338             continue;
 339
 340           if (calcMoves(pos, next) == true)
 341             process.push_back(next);
 342
 343         }
 344     }
 345   return process;
 346 }
 347
 348 bool PathCalculator::load_or_unload(Vector<int> src, Vector<int> dest, bool &on_ship)
 349 {
 350   Stack *new_stack = Stack::createNonUniqueStack(stack->getOwner(), src);
 351   //do we load or unload if we step from SRC to DEST?
 352   bool retval = new_stack->isMovingToOrFromAShip(dest, on_ship);
 353   delete new_stack;
 354   return retval;
 355 }
 356 int PathCalculator::pointsToMoveTo(Vector<int> pos, Vector<int> next) const
 357 {
 358   guint32 moves;
 359   const Maptile* tile = GameMap::getInstance()->getTile(next);
 360
 361   if (pos == next) //probably shouldn't happen
 362     return 0;
 363
 364   moves = tile->getMoves();
 365
 366   if (enemy_city_avoidance >= 1)
 367     {
 368       //We will still try to avoid enemy cities a little.
 369       if (GameMap::getEnemyCity(pos))
 370         moves += enemy_city_avoidance;
 371     }
 372   if (enemy_stack_avoidance >= 1)
 373     {
 374       //We will still try to avoid enemy stacks a little.
 375       if (GameMap::getEnemyStack(pos))
 376         moves += enemy_stack_avoidance;
 377     }
 378
 379   // does everything in the stack have a bonus to move onto this square?
 380   if (tile->getMaptileType() & d_bonus && moves != 1)
 381     return 2;
 382
 383   return moves;
 384 }
 385
 386 PathCalculator::~PathCalculator()
 387 {
 388   free (nodes);
 389   if (delete_stack)
 390     delete stack;
 391 }
 392 //am i blocked from entering destx,desty from x,y when i'm not flying?
 393 bool PathCalculator::isBlockedDir(Vector<int> pos, Vector<int> next)
 394 {
 395   int diffx = next.x - pos.x;
 396   int diffy = next.y - pos.y;
 397   if (diffx >= -1 && diffx <= 1 && diffy >= -1 && diffy <= 1)
 398     {
 399       int idx = 0;
 400       if (diffx == -1 && diffy == -1)
 401         idx = 0;
 402       else if (diffx == -1 && diffy == 0)
 403         idx = 1;
 404       else if (diffx == -1 && diffy == 1)
 405         idx = 2;
 406       else if (diffx == 0 && diffy == 1)
 407         idx = 3;
 408       else if (diffx == 0 && diffy == -1)
 409         idx = 4;
 410       else if (diffx == 1 && diffy == -1)
 411         idx = 5;
 412       else if (diffx == 1 && diffy == 0)
 413         idx = 6;
 414       else if (diffx == 1 && diffy == 1)
 415         idx = 7;
 416       else
 417         return false;
 418       return GameMap::getInstance()->getTile(pos)->d_blocked[idx];
 419     }
 420
 421   return false;
 422 }
 423
 424 bool PathCalculator::isBlocked(const Stack *s, Vector<int> pos, bool enemy_cities_block, bool enemy_stacks_block)
 425 {
 426   const Maptile* tile = GameMap::getInstance()->getTile(pos);
 427
 428   // Return true on every condition which may prevent the stack from
 429   // entering the tile, which are...
 430
 431   // ...enemy stacks which stand in the way...
 432   if (enemy_stacks_block == true)
 433     {
 434       Stack* target = GameMap::getEnemyStack(pos);
 435       if (target)
 436         return true;
 437     }
 438
 439   //...enemy cities
 440   // saves some computation time here
 441   if (tile->getBuilding() == Maptile::CITY && enemy_cities_block == true)
 442     {
 443       City* c = GameMap::getCity(pos);
 444       if (c && (c->getOwner() != s->getOwner()))
 445         return true;
 446     }
 447
 448   //no obstacles??? well, then...
 449   return false;
 450 }
 451
 452 bool PathCalculator::isBlocked(Vector<int> pos)
 453 {
 454   return isBlocked(stack, pos, enemy_city_avoidance < 0, enemy_stack_avoidance < 0);
 455 }
 456
 457 bool PathCalculator::canMoveThere(Vector<int> dest)
 458 {
 459   Vector<int> pos = stack->getPos();
 460   if (flying && isBlockedDir(pos, dest) &&
 461       GameMap::getInstance()->getTile(dest)->getMaptileType()
 462       == Tile::VOID)
 463     return false;
 464   if (isBlocked(pos))
 465     {
 466       //psst. if it's our last step we can step into cities.
 467       //psst. if it's our last step we can step onto enemy stacks
 468       //psst.  if it's our last step and we're a computer player who was diligently walking around friendly stacks, we can merge on our last step
 469       return false;
 470     }
 471   if (isBlockedDir(pos, dest) && !flying)
 472     return false;
 473   return true;
 474 }
 475
 476 int PathCalculator::calculate(Vector<int> dest, bool zigzag)
 477 {
 478   int retval = 0;
 479   guint32 moves = 0;
 480   guint32 turns = 0;
 481   Path *p = calculate(dest, moves, turns, zigzag);
 482   if (p->size() == 0)
 483     retval = -1;
 484   delete p;
 485   if (retval == 0)
 486     retval = (int) moves;
 487   return retval;
 488 }
 489
 490 Path* PathCalculator::calculate(Vector<int> dest, guint32 &moves, guint32 &turns, bool zigzag)
 491 {
 492   Path *path = new Path();
 493   int width = GameMap::getWidth();
 494   int height = GameMap::getHeight();
 495   if (dest.x >= width || dest.x < 0)
 496     return path;
 497   if (dest.y >= height || dest.y < 0)
 498     return path;
 499
 500
 501   int idx = dest.toIndex();
 502   struct node orig_dest = nodes[idx];
 503   //now change dest node
 504   if (nodes[idx].moves == -2)
 505     {
 506       nodes[idx].moves = -1;
 507       nodes[idx].moves_left = 0;
 508       nodes[idx].turns = 0;
 509       bool traversable = calcFinalMoves(dest);
 510       if (traversable == false)
 511         {
 512           nodes[idx] = orig_dest;
 513           return path;
 514         }
 515     }
 516
 517   // The nodes array is now completely populated.
 518   // What we have to do now is find the shortest path to the destination.
 519   // We do that by starting at the destination and moving at each step to
 520   // the neighbour closest to the start.
 521
 522   int dist = nodes[idx].moves;
 523   if (dist < 0)
 524     {
 525       path->setMovesExhaustedAtPoint(0);
 526       moves = 0;
 527       turns = 0;
 528       nodes[idx] = orig_dest;
 529       return path;
 530     }
 531
 532   // choose the order in which we process directions so as to favour
 533   // diagonals over straight lines
 534   std::list<Vector<int> > diffs;
 535   if (zigzag)
 536     {
 537       diffs.push_back(Vector<int>(-1, -1));
 538       diffs.push_back(Vector<int>(-1, 1));
 539       diffs.push_back(Vector<int>(1, -1));
 540       diffs.push_back(Vector<int>(1, 1));
 541       diffs.push_back(Vector<int>(1, 0));
 542       diffs.push_back(Vector<int>(-1, 0));
 543       diffs.push_back(Vector<int>(0, -1));
 544       diffs.push_back(Vector<int>(0, 1));
 545     }
 546   else
 547     {
 548       diffs.push_back(Vector<int>(1, 0));
 549       diffs.push_back(Vector<int>(-1, 0));
 550       diffs.push_back(Vector<int>(0, -1));
 551       diffs.push_back(Vector<int>(0, 1));
 552     }
 553
 554   Vector<int> pos = dest;
 555   while (dist > 0)
 556     {
 557       path->push_front(pos);
 558
 559       int min = dist;
 560       Vector<int> minpos = pos;
 561       for (std::list<Vector<int> >::iterator it = diffs.begin();
 562            it != diffs.end(); it++)
 563         {
 564           Vector<int> next = pos + (*it);
 565           if (next.x < 0 || next.x == width || next.y < 0 || next.y == height)
 566             continue;
 567           //isBlockedDir is needed to catch crossings from land to sea when not thru a port/city
 568           if (!flying && isBlockedDir(pos, next))
 569             continue;
 570
 571           dist = nodes[next.toIndex()].moves;
 572           if (dist >= 0 && dist < min)
 573             {
 574               min = dist;
 575               minpos = next;
 576             }
 577         }
 578       // found the best spot to go to from
 579       pos = minpos;
 580       dist = min;
 581     }
 582
 583   //calculate when the waypoints show no more movement possible
 584   guint32 pathcount = 0;
 585   guint32 moves_left = stack->getMoves();
 586   for (Path::iterator it = path->begin(); it != path->end(); it++)
 587     {
 588       guint32 moves = stack->calculateTileMovementCost(*it);
 589       if (moves_left >= moves)
 590         moves_left -= moves;
 591       else
 592         break;
 593       pathcount++;
 594     }
 595   path->setMovesExhaustedAtPoint(pathcount);
 596
 597   debug("...done");
 598
 599   moves = nodes[idx].moves;
 600   turns = nodes[idx].turns;
 601
 602   //change dest back
 603   nodes[idx] = orig_dest;
 604   return path;
 605 }
 606 void PathCalculator::dumpNodeMap(Vector<int> dest)
 607 {
 608   int width = GameMap::getWidth();
 609   int height = GameMap::getHeight();
 610   printf ("==2=====================================\n");
 611   for (int i = 0; i < width; i++)
 612     {
 613     for (int j = 0; j < height; j++)
 614       {
 615         int moves = nodes[j*width+i].moves;
 616         if (stack->getPos() == Vector<int>(i,j))
 617           printf("0");
 618         else if (dest == Vector<int>(i, j))
 619           printf("1");
 620         else if (moves == -2)
 621           printf ("Z");
 622         else if (moves == -1)
 623           printf ("X");
 624         else
 625           printf("%c", (moves % 26) + 'a');
 626       }
 627     printf ("\n");
 628       }
 629   printf ("=======================================\n");
 630   return;
 631 }
 632 bool PathCalculator::compareNodeMaps(void *map)
 633 {
 634   bool found = false;
 635   int width = GameMap::getWidth();
 636   int height = GameMap::getHeight();
 637   struct node * othernodes = (struct node *) map;
 638   for (int i = 0; i < width; i++)
 639     for (int j = 0; j < height; j++)
 640       {
 641         if (othernodes[j*width+i].moves != nodes[j*width+i].moves)
 642           {
 643           found = true;
 644           break;
 645           }
 646       }
 647   return found;
 648 }
 649 bool PathCalculator::isReachable(Vector<int> pos)
 650 {
 651   return nodes[pos.toIndex()].moves >= 0;
 652 }
 653
 654 Path *PathCalculator::calculateToCity (City *c, guint32 &moves, guint32 &turns, bool zigzag)
 655 {
 656   int min_dist = -1;
 657   Vector<int> shortest = c->getPos();
 658   bool checkJoin = stack->getOwner() == c->getOwner();
 659
 660   for (unsigned int i = 0; i < c->getSize(); i++)
 661     for (unsigned int j = 0; j < c->getSize(); j++)
 662       {
 663         if (checkJoin == true)
 664           {
 665             Stack *other_stack = GameMap::getStack(c->getPos() + Vector<int>(i,j));
 666             if (other_stack && GameMap::canJoin(stack,other_stack) == false)
 667               continue;
 668           }
 669         int distance = dist (stack->getPos(), c->getPos() + Vector<int>(i, j));
 670         if (distance > 0)
 671           {
 672             if (distance < min_dist || min_dist == -1)
 673               {
 674                 min_dist = distance;
 675                 shortest = c->getPos() + Vector<int>(i, j);
 676               }
 677           }
 678       }
 679   Path *p = calculate(shortest, moves, turns, zigzag);
 680   if (p->size() > 0)
 681     return p;
 682   delete p;
 683
 684   //okay.. try really hard
 685   min_dist = -1;
 686   for (unsigned int i = 0; i < c->getSize(); i++)
 687     for (unsigned int j = 0; j < c->getSize(); j++)
 688       {
 689         if (checkJoin == true)
 690           {
 691             Stack *other_stack = GameMap::getStack(c->getPos() + Vector<int>(i,j));
 692             if (other_stack && GameMap::canJoin(stack, other_stack) == false)
 693               continue;
 694           }
 695         p = calculate(c->getPos() + Vector<int>(i,j), moves, turns, zigzag);
 696         int dist = (int) moves;
 697         delete p;
 698         if (dist > 0)
 699           {
 700             if (dist < min_dist || min_dist == -1)
 701               {
 702                 min_dist = dist;
 703                 shortest = c->getPos() + Vector<int>(i, j);
 704               }
 705           }
 706       }
 707   return calculate(shortest, moves, turns, zigzag);
 708 }
 709
 710 std::list<Vector<int> > PathCalculator::getReachablePositions(int mp)
 711 {
 712   std::list<Vector<int> > positions;
 713   int width = GameMap::getWidth();
 714   int height = GameMap::getHeight();
 715   for (int i = 0; i < width*height; i++)
 716     {
 717       if (nodes[i].moves < mp || mp == 0)
 718         positions.push_back(Vector<int>(i % width, i / width));
 719     }
 720   return positions;
 721 }