← Back to branch summary

~ubuntu-branches/ubuntu/saucy/lordsawar/saucy

« back to all changes in this revision

Viewing changes to src/path.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Barry deFreese, Barry deFreese
  • Date: 2008-12-20 13:52:12 UTC
  • mfrom: (1.1.6 upstream) (5.1.2 squeeze)
  • Revision ID: james.westby@ubuntu.com-20081220135212-noeb2w3y98ebo7o9
Tags: 0.1.4-1
[ Barry deFreese ]
* New upstream release.
* Move 0.0.8-2.1 changelog entry to correct point in changelog.
* Make lordsawar-data suggest lordsawar.
* Update my e-mail address.
* Add build-depends on intltool, uuid-dev, and libboost-dev.
* Don't install locales since there are no translations currently.
* Add simple man page for new lordsawar-pbm binary.
* Drop gcc4.3 patches as they have been fixed upstream.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/path.cpp
25
25
#include <queue>
26
26
 
27
27
#include "path.h"
28
 
#include "defs.h"
29
28
#include "army.h"
30
29
#include "GameMap.h"
31
30
#include "Location.h"
35
34
#include "xmlhelper.h"
36
35
#include "stack.h"
37
36
 
 
37
std::string Path::d_tag = "path";
 
38
 
38
39
using namespace std;
39
40
 
40
41
//#define debug(x) {cerr<<__FILE__<<": "<<__LINE__<<": "<<x<<endl<<flush;}
85
86
        sy <<(*it)->y <<" ";
86
87
    }
87
88
 
88
 
    retval &= helper->openTag("path");
 
89
    retval &= helper->openTag(Path::d_tag);
89
90
    retval &= helper->saveData("size", size());
90
91
    retval &= helper->saveData("moves_exhausted_at_point", 
91
92
                               d_moves_exhausted_at_point);
115
116
{
116
117
  d_bonus=s->calculateMoveBonus();
117
118
  Vector<int> pos = s->getPos();
 
119
  bool flying = s->isFlying();
 
120
  if (flying && isBlockedDir(pos.x, pos.y, dest.x, dest.y) &&
 
121
      GameMap::getInstance()->getTile(dest.x, dest.y)->getMaptileType()
 
122
      == Tile::VOID)
 
123
    return false;
118
124
  if (isBlocked(s, pos.x, pos.y, dest.x, dest.y))
119
125
    return false;
120
 
  if (isBlockedDir(pos.x, pos.y, dest.x, dest.y))
 
126
  if (isBlockedDir(pos.x, pos.y, dest.x, dest.y) && !flying)
121
127
    return false;
122
128
  return true;
123
129
}
223
229
  return mp;
224
230
}
225
231
 
226
 
Uint32 Path::calculate (Stack* s, Vector<int> dest, bool zigzag)
 
232
bool Path::load_or_unload(Stack *s, Vector<int> src, Vector<int> dest, bool &on_ship)
 
233
{
 
234
  //do we load or unload if we step from SRC to DEST?
 
235
  Vector<int> old = s->getPos();
 
236
  s->setPos(src);
 
237
  bool retval = s->isMovingToOrFromAShip(dest, on_ship);
 
238
  s->setPos(old);
 
239
  return retval;
 
240
}
 
241
 
 
242
void Path::calculate (Stack* s, Vector<int> dest, Uint32 &moves, Uint32 &turns, bool zigzag)
227
243
{
228
244
  int mp;
229
245
  Vector<int> start = s->getPos();
235
251
    {
236
252
      Vector<int> *p = new Vector<int>(dest);
237
253
      push_back(p);
238
 
      setMovesExhaustedAtPoint(1);
239
 
      return 1;
 
254
      if (s->canMove() == true)
 
255
        setMovesExhaustedAtPoint(1);
 
256
      else
 
257
        setMovesExhaustedAtPoint(0);
 
258
      moves = 1;
 
259
      turns = 0;
 
260
      return;
240
261
    }
241
262
  int width = GameMap::getWidth();
242
263
  int height = GameMap::getHeight();
243
264
  d_bonus = s->calculateMoveBonus();
 
265
  int land_reset_moves = s->getMaxGroupLandMoves();
 
266
  int boat_reset_moves = s->getMaxGroupBoatMoves();
 
267
 
244
268
  //if (isBlocked(s, dest.x, dest.y, dest.x, dest.y))
245
269
  //{
246
270
  //s->setMovesExhaustedAtPoint(0);
248
272
  //}
249
273
 
250
274
  // Some notes concerning the path finding algorithm. The algorithm
251
 
  // uses two different lists. There is a distance array, which contains how
 
275
  // uses two different lists. There is a nodes array, which contains how
252
276
  // many MP one needs to get to the location (x,y), and a process queue that
253
277
  // tells you at what point the number of movement points is calculated next.
254
278
  //
269
293
  // the conversion between x/y coordinates and index is (size is map size)
270
294
  // index = y*width + x    <=>    x = index % width;   y = index / width
271
295
  int length = width*height;
272
 
  int distance[length];
 
296
  struct node
 
297
    {
 
298
      int moves;
 
299
      int turns;
 
300
      int moves_left;
 
301
    };
 
302
  struct node nodes[length];
273
303
  std::queue<Vector<int> > process;
274
304
  bool flying = s->isFlying();
 
305
  bool on_ship = s->hasShip();
275
306
 
276
 
  // initial filling of the distance vector
 
307
  // initial filling of the nodes vector
277
308
  for (int i = 0; i < width*height; i++)
278
309
    {
279
310
      // -1 means don't know yet
280
311
      // -2 means can't go there at all
281
312
      // 0 or more is number of movement points needed to get there
282
 
      distance[i] = -1;
 
313
      nodes[i].moves = -1;
 
314
      nodes[i].moves_left = 0;
 
315
      nodes[i].turns = 0;
283
316
      if (isBlocked(s, i % width, i/width, dest.x, dest.y))
284
 
        distance[i] = -2;
 
317
        nodes[i].moves = -2;
285
318
    }
286
 
  distance[start.y*width+start.x] = 0;
 
319
  nodes[start.y*width+start.x].moves = 0;
 
320
  nodes[start.y*width+start.x].moves_left = s->getGroupMoves();
 
321
  nodes[start.y*width+start.x].turns = 0;
287
322
 
288
323
  // now the main loop
289
324
  process.push(Vector<int>(start.x, start.y));
292
327
      Vector<int> pos = process.front();
293
328
      process.pop();                          // remove the first item
294
329
 
295
 
      int dxy = distance[pos.y*width+pos.x];   // always >= 0
 
330
      int dxy = nodes[pos.y*width+pos.x].moves;   // always >= 0
296
331
 
297
332
      for (int sx = pos.x-1; sx <= pos.x+1; sx++)
298
333
        {
310
345
              //am i blocked from entering sx,sy from pos?
311
346
              if (!flying && isBlockedDir(pos.x, pos.y, sx, sy))
312
347
                continue;
 
348
              //flyers can't go through the void
 
349
              if (flying && isBlockedDir(pos.x, pos.y, sx, sy) &&
 
350
                  GameMap::getInstance()->getTile(sx, sy)->getMaptileType()
 
351
                  == Tile::VOID)
 
352
                continue;
313
353
 
314
 
              int dsxy = distance[sy*width+sx];
 
354
              int dsxy = nodes[sy*width+sx].moves;
315
355
              if (dsxy < -1)
316
356
                continue; // can't move there anyway
317
357
 
323
363
                }
324
364
              int newDsxy = dxy;
325
365
              mp = pointsToMoveTo(s, pos.x, pos.y, sx, sy);
326
 
              if (mp >= 0)
327
 
                newDsxy += mp;
 
366
              if (mp < 0)
 
367
                mp = 0;
 
368
              if (!flying && load_or_unload(s, pos, Vector<int>(sx, sy), on_ship) == true)
 
369
                mp = nodes[pos.y*width+pos.x].moves_left;
 
370
              newDsxy += mp;
 
371
 
328
372
 
329
373
              if (dsxy == -1 || dsxy > newDsxy)
330
374
                {
331
 
                  distance[sy*width+sx] = newDsxy;
 
375
                  nodes[sy*width+sx].moves = newDsxy;
 
376
                  nodes[sy*width+sx].moves_left = 
 
377
                    nodes[pos.y*width+pos.x].moves_left - mp;
 
378
                  nodes[sy*width+sx].turns = nodes[pos.y*width+pos.x].turns ;
 
379
                  while (nodes[sy*width+sx].moves_left <= 0)
 
380
                    {
 
381
                      if (on_ship)
 
382
                        nodes[sy*width+sx].moves_left += boat_reset_moves;
 
383
                      else
 
384
                        nodes[sy*width+sx].moves_left += land_reset_moves;
 
385
                      nodes[sy*width+sx].turns++;
 
386
                    }
332
387
 
333
388
                  // append the item to the queue
334
389
                  process.push(Vector<int>(sx, sy));
337
392
        }
338
393
    }
339
394
 
340
 
  // The distance array is now completely populated.
 
395
  // The nodes array is now completely populated.
341
396
  // What we have to do now is find the shortest path to the destination.
342
397
  // We do that by starting at the destination and moving at each step to
343
398
  // the neighbour closest to the start.
344
399
 
345
 
  int dist = distance[dest.y * width + dest.x];
 
400
  int dist = nodes[dest.y * width + dest.x].moves;
346
401
  if (dist < 0)
347
402
    {
348
403
      setMovesExhaustedAtPoint(0);
349
 
      return 0;
 
404
      moves = 0;
 
405
      turns = 0;
 
406
      return;
350
407
    }
351
408
 
352
409
  // choose the order in which we process directions so as to favour
393
450
          if (!flying && isBlockedDir(x, y, newx, newy))
394
451
            continue;
395
452
 
396
 
          dist = distance[newy*width+newx];
 
453
          dist = nodes[newy*width+newx].moves;
397
454
          if (dist >= 0 && dist < min)
398
455
            {
399
456
              rx = newx;
422
479
  setMovesExhaustedAtPoint(pathcount);
423
480
 
424
481
  debug("...done");
425
 
  return distance[dest.y * width + dest.x];
 
482
  moves = nodes[dest.y * width + dest.x].moves;
 
483
  turns = nodes[dest.y * width + dest.x].turns;
 
484
  return;
 
485
}
 
486
 
 
487
Uint32 Path::calculate (Stack* s, Vector<int> dest, Uint32 &turns, bool zigzag)
 
488
{
 
489
  Uint32 mp = 0;
 
490
  calculate(s, dest, mp, turns, zigzag);
 
491
  return mp;
 
492
}
 
493
 
 
494
Uint32 Path::calculate (Stack* s, Vector<int> dest, bool zigzag)
 
495
{
 
496
  Uint32 mp = 0;
 
497
  Uint32 turns = 0;
 
498
  calculate(s, dest, mp, turns, zigzag);
 
499
  return mp;
426
500
}
427
501
 
428
502
void Path::eraseFirstPoint()