X-Git-Url: http://git.maemo.org/git/?p=lordsawar;a=blobdiff_plain;f=src%2Fpath.cpp;fp=src%2Fpath.cpp;h=61ebec327ed575b87ddccea9c0a95c8d81da9cdd;hp=0000000000000000000000000000000000000000;hb=9eda00ff73353c55ecef6f82131166d5d4a85e29;hpb=3d34d4aa85a929f912464f71158396a388274f27

diff --git a/src/path.cpp b/src/path.cpp
new file mode 100644
index 0000000..61ebec3
--- /dev/null
+++ b/src/path.cpp
@@ -0,0 +1,311 @@
+// Copyright (C) 2000, 2001, 2002, 2003 Michael Bartl
+// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 Ulf Lorenz
+// Copyright (C) 2004, 2005, 2006 Andrea Paternesi
+// Copyright (C) 2004 John Farrell
+// Copyright (C) 2006, 2007, 2008, 2009 Ben Asselstine
+// Copyright (C) 2008 Ole Laursen
+//
+//  This program is free software; you can redistribute it and/or modify
+//  it under the terms of the GNU General Public License as published by
+//  the Free Software Foundation; either version 3 of the License, or
+//  (at your option) any later version.
+//
+//  This program is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+//  GNU Library General Public License for more details.
+//
+//  You should have received a copy of the GNU General Public License
+//  along with this program; if not, write to the Free Software
+//  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 
+//  02110-1301, USA.
+
+#include <stdlib.h>
+#include <assert.h>
+#include <sstream>
+#include <queue>
+
+#include "PathCalculator.h"
+#include "path.h"
+#include "army.h"
+#include "GameMap.h"
+#include "city.h"
+#include "stacklist.h"
+#include "xmlhelper.h"
+#include "stack.h"
+
+std::string Path::d_tag = "path";
+
+using namespace std;
+
+  struct node
+    {
+      int moves;
+      int turns;
+      int moves_left;
+    };
+//#define debug(x) {cerr<<__FILE__<<": "<<__LINE__<<": "<<x<<endl<<flush;}
+#define debug(x)
+
+Path::Path()
+{
+  clear();
+  d_moves_exhausted_at_point = 0;
+}
+
+Path::Path(const Path& p)
+ : d_bonus(p.d_bonus), d_moves_exhausted_at_point(p.d_moves_exhausted_at_point)
+{
+  for (const_iterator it = p.begin(); it != p.end(); it++)
+    push_back(Vector<int>((*it).x, (*it).y));
+}
+
+Path::Path(XML_Helper* helper)
+{
+    int i;
+    std::istringstream sx, sy;
+    std::string s;
+
+    helper->getData(d_moves_exhausted_at_point, "moves_exhausted_at_point");
+    helper->getData(i, "size");
+
+    helper->getData(s, "x");
+    sx.str(s);
+    helper->getData(s, "y");
+    sy.str(s);
+
+    for (; i > 0; i--)
+    {
+        Vector<int> p = Vector<int>(-1,-1);
+
+        sx >> p.x;
+        sy >> p.y;
+        push_back(p);
+    }
+}
+
+Path::~Path()
+{
+    clear();
+}
+
+bool Path::save(XML_Helper* helper) const
+{
+    bool retval = true;
+
+    std::stringstream sx, sy;
+    for (const_iterator it = begin(); it != end(); it++)
+    {
+        sx <<(*it).x <<" ";
+        sy <<(*it).y <<" ";
+    }
+
+    retval &= helper->openTag(Path::d_tag);
+    retval &= helper->saveData("size", size());
+    retval &= helper->saveData("moves_exhausted_at_point", 
+                               d_moves_exhausted_at_point);
+    retval &= helper->saveData("x", sx.str());
+    retval &= helper->saveData("y", sy.str());
+    retval &= helper->closeTag();
+
+    return retval;
+}
+
+bool Path::checkPath(Stack* s, int enemy_city_avoidance, int enemy_stack_avoidance)
+{
+    if (empty())
+        return true;
+    bool valid = true;
+    if (size() > 1)
+      {
+	iterator secondlast = end();
+	secondlast--;
+	for (iterator it = begin(); it != secondlast; it++)
+	  {
+	    if (PathCalculator::isBlocked(s, *it, enemy_city_avoidance, 
+					  enemy_stack_avoidance) == false)
+	      {
+		valid = false;
+		break;
+	      }
+	  }
+      }
+
+    return valid;
+}
+
+//this is used to update the moves_exhausted_at_point variable
+void Path::recalculate (Stack* s)
+{
+  if (size() == 0)
+    return;
+
+  // be careful to not go into cities that are now owned by the enemy
+  reverse_iterator it = rbegin();
+  for (; it != rend(); it++)
+    {
+      Vector<int> dest = *it;
+      City *c = GameMap::getCity(dest);
+      if (c && c->getOwner() != s->getOwner())
+	continue;
+      else
+	break;
+    }
+  if (it == rend())
+    {
+      //well, it looks like all of our points were in enemy cities
+      setMovesExhaustedAtPoint(0);
+      clear();
+    }
+  else
+    {
+      Vector<int> dest = *it;
+      calculate(s, dest);
+    }
+  return;
+}
+
+guint32 Path::calculateToCity (Stack *s, City *c, bool zigzag)
+{
+  int min_dist = -1;
+  Vector<int> shortest = c->getPos();
+  bool checkJoin = s->getOwner() == c->getOwner();
+
+  for (unsigned int i = 0; i < c->getSize(); i++)
+    for (unsigned int j = 0; j < c->getSize(); j++)
+      {
+	if (checkJoin == true)
+	  {
+	    Stack *other_stack = GameMap::getStack(c->getPos() + Vector<int>(i,j));
+	    if (other_stack && GameMap::canJoin(s,other_stack) == false)
+	      continue;
+	  }
+	int distance = dist (s->getPos(), c->getPos() + Vector<int>(i, j));
+	if (distance > 0)
+	  {
+	    if (distance < min_dist || min_dist == -1)
+	      {
+		min_dist = distance;
+		shortest = c->getPos() + Vector<int>(i, j);
+	      }
+	  }
+      }
+  int mp = calculate(s, shortest, zigzag);
+  if (mp <= 0)
+    {
+      //okay.. try really hard
+      min_dist = -1;
+      for (unsigned int i = 0; i < c->getSize(); i++)
+	for (unsigned int j = 0; j < c->getSize(); j++)
+	  {
+	    if (checkJoin == true)
+	      {
+		Stack *other_stack = GameMap::getStack(c->getPos() + Vector<int>(i,j));
+		if (other_stack && GameMap::canJoin(s,other_stack) == false)
+		  continue;
+	      }
+	    int dist = calculate(s, c->getPos() + Vector<int>(i, j), zigzag);
+	    if (dist > 0)
+	      {
+		if (dist < min_dist || min_dist == -1)
+		  {
+		    min_dist = dist;
+		    shortest = c->getPos() + Vector<int>(i, j);
+		  }
+	      }
+	  }
+      mp = calculate(s, shortest, zigzag);
+    }
+  return mp;
+}
+
+void Path::calculate (Stack* s, Vector<int> dest, guint32 &moves, guint32 &turns, bool zigzag)
+{
+  //int mp;
+  //Vector<int> start = s->getPos();
+  debug("path from "<<start.x<<","<<start.y<<" to "<<dest.x<<","<<dest.y)
+
+  clear();
+
+  // Some notes concerning the path finding algorithm. The algorithm
+  // uses two different lists. There is a nodes array, which contains how
+  // many MP one needs to get to the location (x,y), and a process queue that
+  // tells you at what point the number of movement points is calculated next.
+  //
+  // What we basically do is to start at the stack's position and calculate
+  // the distance (i.e. MP needed to get there) in circles around the starting
+  // position with the circles becoming increasingly larger. In detail, we
+  // start by appending the starting position in the queue of positions to be
+  // processed. Then, recursively, we take the first point in the queue and
+  // recalculate the distance for all bordering tiles, assuming that we go
+  // over this point and overwriting their current value if it is larger
+  // than what we find now. Then, we append each modified tile to the queue of
+  // tiles to be processed and continue. We stop when there are no more tiles
+  // to process.
+  //
+  // Finally, all that is left is finding the minimum distance way from start
+  // point to destination.
+
+    
+  int enemy_city_avoidance = -1;
+  int enemy_stack_avoidance = -1;
+  if (s->getOwner() && s->getOwner()->isComputer())
+    {
+      //If we're a computer player we don't let enemy stacks and cities
+      //prevent us from reaching our destination.  When we encounter them
+      //we'll fight, but we try not to encounter them.
+      enemy_city_avoidance = 10;
+      enemy_stack_avoidance = 10;
+    }
+  PathCalculator pc = PathCalculator(s, zigzag, enemy_city_avoidance, 
+				     enemy_stack_avoidance);
+
+  Path *calculated_path = pc.calculate(dest, moves, turns, zigzag);
+  if (calculated_path->size())
+    {
+      for(Path::iterator it = calculated_path->begin(); it!= calculated_path->end(); it++)
+	push_back(*it);
+    }
+
+  //calculate when the waypoints show no more movement possible
+  guint32 pathcount = 0;
+  guint32 moves_left = s->getMoves();
+  for (iterator it = begin(); it != end(); it++)
+    {
+      guint32 moves = s->calculateTileMovementCost(*it);
+      if (moves_left >= moves)
+	moves_left -= moves;
+      else
+	break;
+      pathcount++;
+    }
+  setMovesExhaustedAtPoint(pathcount);
+  delete calculated_path;
+
+  return;
+}
+
+guint32 Path::calculate (Stack* s, Vector<int> dest, guint32 &turns, bool zigzag)
+{
+  guint32 mp = 0;
+  calculate(s, dest, mp, turns, zigzag);
+  return mp;
+}
+
+guint32 Path::calculate (Stack* s, Vector<int> dest, bool zigzag)
+{
+  guint32 mp = 0;
+  guint32 turns = 0;
+  calculate(s, dest, mp, turns, zigzag);
+  return mp;
+}
+
+void Path::eraseFirstPoint()
+{
+  erase(begin());
+
+  if (getMovesExhaustedAtPoint() > 0)
+    setMovesExhaustedAtPoint(getMovesExhaustedAtPoint()-1);
+}
+
+// End of file