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

   1 // Copyright (C) 2000, 2001, 2002, 2003 Michael Bartl
   2 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 Ulf Lorenz
   3 // Copyright (C) 2004, 2005, 2006 Andrea Paternesi
   4 // Copyright (C) 2004 John Farrell
   5 // Copyright (C) 2006, 2007, 2008, 2009 Ben Asselstine
   6 // Copyright (C) 2008 Ole Laursen
   7 //
   8 //  This program is free software; you can redistribute it and/or modify
   9 //  it under the terms of the GNU General Public License as published by
  10 //  the Free Software Foundation; either version 3 of the License, or
  11 //  (at your option) any later version.
  12 //
  13 //  This program is distributed in the hope that it will be useful,
  14 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 //  GNU Library General Public License for more details.
  17 //
  18 //  You should have received a copy of the GNU General Public License
  19 //  along with this program; if not, write to the Free Software
  20 //  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21 //  02110-1301, USA.
  22
  23 #include <stdlib.h>
  24 #include <assert.h>
  25 #include <sstream>
  26 #include <queue>
  27
  28 #include "PathCalculator.h"
  29 #include "path.h"
  30 #include "army.h"
  31 #include "GameMap.h"
  32 #include "city.h"
  33 #include "stacklist.h"
  34 #include "xmlhelper.h"
  35 #include "stack.h"
  36
  37 std::string Path::d_tag = "path";
  38
  39 using namespace std;
  40
  41   struct node
  42     {
  43       int moves;
  44       int turns;
  45       int moves_left;
  46     };
  47 //#define debug(x) {cerr<<__FILE__<<": "<<__LINE__<<": "<<x<<endl<<flush;}
  48 #define debug(x)
  49
  50 Path::Path()
  51 {
  52   clear();
  53   d_moves_exhausted_at_point = 0;
  54 }
  55
  56 Path::Path(const Path& p)
  57  : d_bonus(p.d_bonus), d_moves_exhausted_at_point(p.d_moves_exhausted_at_point)
  58 {
  59   for (const_iterator it = p.begin(); it != p.end(); it++)
  60     push_back(Vector<int>((*it).x, (*it).y));
  61 }
  62
  63 Path::Path(XML_Helper* helper)
  64 {
  65     int i;
  66     std::istringstream sx, sy;
  67     std::string s;
  68
  69     helper->getData(d_moves_exhausted_at_point, "moves_exhausted_at_point");
  70     helper->getData(i, "size");
  71
  72     helper->getData(s, "x");
  73     sx.str(s);
  74     helper->getData(s, "y");
  75     sy.str(s);
  76
  77     for (; i > 0; i--)
  78     {
  79         Vector<int> p = Vector<int>(-1,-1);
  80
  81         sx >> p.x;
  82         sy >> p.y;
  83         push_back(p);
  84     }
  85 }
  86
  87 Path::~Path()
  88 {
  89     clear();
  90 }
  91
  92 bool Path::save(XML_Helper* helper) const
  93 {
  94     bool retval = true;
  95
  96     std::stringstream sx, sy;
  97     for (const_iterator it = begin(); it != end(); it++)
  98     {
  99         sx <<(*it).x <<" ";
 100         sy <<(*it).y <<" ";
 101     }
 102
 103     retval &= helper->openTag(Path::d_tag);
 104     retval &= helper->saveData("size", size());
 105     retval &= helper->saveData("moves_exhausted_at_point",
 106                                d_moves_exhausted_at_point);
 107     retval &= helper->saveData("x", sx.str());
 108     retval &= helper->saveData("y", sy.str());
 109     retval &= helper->closeTag();
 110
 111     return retval;
 112 }
 113
 114 bool Path::checkPath(Stack* s, int enemy_city_avoidance, int enemy_stack_avoidance)
 115 {
 116     if (empty())
 117         return true;
 118     bool valid = true;
 119     if (size() > 1)
 120       {
 121         iterator secondlast = end();
 122         secondlast--;
 123         for (iterator it = begin(); it != secondlast; it++)
 124           {
 125             if (PathCalculator::isBlocked(s, *it, enemy_city_avoidance,
 126                                           enemy_stack_avoidance) == false)
 127               {
 128                 valid = false;
 129                 break;
 130               }
 131           }
 132       }
 133
 134     return valid;
 135 }
 136
 137 //this is used to update the moves_exhausted_at_point variable
 138 void Path::recalculate (Stack* s)
 139 {
 140   if (size() == 0)
 141     return;
 142
 143   // be careful to not go into cities that are now owned by the enemy
 144   reverse_iterator it = rbegin();
 145   for (; it != rend(); it++)
 146     {
 147       Vector<int> dest = *it;
 148       City *c = GameMap::getCity(dest);
 149       if (c && c->getOwner() != s->getOwner())
 150         continue;
 151       else
 152         break;
 153     }
 154   if (it == rend())
 155     {
 156       //well, it looks like all of our points were in enemy cities
 157       setMovesExhaustedAtPoint(0);
 158       clear();
 159     }
 160   else
 161     {
 162       Vector<int> dest = *it;
 163       calculate(s, dest);
 164     }
 165   return;
 166 }
 167
 168 guint32 Path::calculateToCity (Stack *s, City *c, bool zigzag)
 169 {
 170   int min_dist = -1;
 171   Vector<int> shortest = c->getPos();
 172   bool checkJoin = s->getOwner() == c->getOwner();
 173
 174   for (unsigned int i = 0; i < c->getSize(); i++)
 175     for (unsigned int j = 0; j < c->getSize(); j++)
 176       {
 177         if (checkJoin == true)
 178           {
 179             Stack *other_stack = GameMap::getStack(c->getPos() + Vector<int>(i,j));
 180             if (other_stack && GameMap::canJoin(s,other_stack) == false)
 181               continue;
 182           }
 183         int distance = dist (s->getPos(), c->getPos() + Vector<int>(i, j));
 184         if (distance > 0)
 185           {
 186             if (distance < min_dist || min_dist == -1)
 187               {
 188                 min_dist = distance;
 189                 shortest = c->getPos() + Vector<int>(i, j);
 190               }
 191           }
 192       }
 193   int mp = calculate(s, shortest, zigzag);
 194   if (mp <= 0)
 195     {
 196       //okay.. try really hard
 197       min_dist = -1;
 198       for (unsigned int i = 0; i < c->getSize(); i++)
 199         for (unsigned int j = 0; j < c->getSize(); j++)
 200           {
 201             if (checkJoin == true)
 202               {
 203                 Stack *other_stack = GameMap::getStack(c->getPos() + Vector<int>(i,j));
 204                 if (other_stack && GameMap::canJoin(s,other_stack) == false)
 205                   continue;
 206               }
 207             int dist = calculate(s, c->getPos() + Vector<int>(i, j), zigzag);
 208             if (dist > 0)
 209               {
 210                 if (dist < min_dist || min_dist == -1)
 211                   {
 212                     min_dist = dist;
 213                     shortest = c->getPos() + Vector<int>(i, j);
 214                   }
 215               }
 216           }
 217       mp = calculate(s, shortest, zigzag);
 218     }
 219   return mp;
 220 }
 221
 222 void Path::calculate (Stack* s, Vector<int> dest, guint32 &moves, guint32 &turns, bool zigzag)
 223 {
 224   //int mp;
 225   //Vector<int> start = s->getPos();
 226   debug("path from "<<start.x<<","<<start.y<<" to "<<dest.x<<","<<dest.y)
 227
 228   clear();
 229
 230   // Some notes concerning the path finding algorithm. The algorithm
 231   // uses two different lists. There is a nodes array, which contains how
 232   // many MP one needs to get to the location (x,y), and a process queue that
 233   // tells you at what point the number of movement points is calculated next.
 234   //
 235   // What we basically do is to start at the stack's position and calculate
 236   // the distance (i.e. MP needed to get there) in circles around the starting
 237   // position with the circles becoming increasingly larger. In detail, we
 238   // start by appending the starting position in the queue of positions to be
 239   // processed. Then, recursively, we take the first point in the queue and
 240   // recalculate the distance for all bordering tiles, assuming that we go
 241   // over this point and overwriting their current value if it is larger
 242   // than what we find now. Then, we append each modified tile to the queue of
 243   // tiles to be processed and continue. We stop when there are no more tiles
 244   // to process.
 245   //
 246   // Finally, all that is left is finding the minimum distance way from start
 247   // point to destination.
 248
 249
 250   int enemy_city_avoidance = -1;
 251   int enemy_stack_avoidance = -1;
 252   if (s->getOwner() && s->getOwner()->isComputer())
 253     {
 254       //If we're a computer player we don't let enemy stacks and cities
 255       //prevent us from reaching our destination.  When we encounter them
 256       //we'll fight, but we try not to encounter them.
 257       enemy_city_avoidance = 10;
 258       enemy_stack_avoidance = 10;
 259     }
 260   PathCalculator pc = PathCalculator(s, zigzag, enemy_city_avoidance,
 261                                      enemy_stack_avoidance);
 262
 263   Path *calculated_path = pc.calculate(dest, moves, turns, zigzag);
 264   if (calculated_path->size())
 265     {
 266       for(Path::iterator it = calculated_path->begin(); it!= calculated_path->end(); it++)
 267         push_back(*it);
 268     }
 269
 270   //calculate when the waypoints show no more movement possible
 271   guint32 pathcount = 0;
 272   guint32 moves_left = s->getMoves();
 273   for (iterator it = begin(); it != end(); it++)
 274     {
 275       guint32 moves = s->calculateTileMovementCost(*it);
 276       if (moves_left >= moves)
 277         moves_left -= moves;
 278       else
 279         break;
 280       pathcount++;
 281     }
 282   setMovesExhaustedAtPoint(pathcount);
 283   delete calculated_path;
 284
 285   return;
 286 }
 287
 288 guint32 Path::calculate (Stack* s, Vector<int> dest, guint32 &turns, bool zigzag)
 289 {
 290   guint32 mp = 0;
 291   calculate(s, dest, mp, turns, zigzag);
 292   return mp;
 293 }
 294
 295 guint32 Path::calculate (Stack* s, Vector<int> dest, bool zigzag)
 296 {
 297   guint32 mp = 0;
 298   guint32 turns = 0;
 299   calculate(s, dest, mp, turns, zigzag);
 300   return mp;
 301 }
 302
 303 void Path::eraseFirstPoint()
 304 {
 305   erase(begin());
 306
 307   if (getMovesExhaustedAtPoint() > 0)
 308     setMovesExhaustedAtPoint(getMovesExhaustedAtPoint()-1);
 309 }
 310
 311 // End of file