[Pingus-CVS] CVS: Games/Pingus/src/worldmap path.cxx,NONE,1.1 path.hxx,NONE,1.1 Makefile.am,1.10,1.11 path_graph.cxx,1.11,1.12 path_graph.hxx,1.5,1.6 pathfinder.hxx,1.6,1.7 pingus.cxx,1.17,1.18 pingus.hxx,1.17,1.18

[grumbel]

Update of /usr/local/cvsroot/Games/Pingus/src/worldmap
In directory dark:/tmp/cvs-serv29772/worldmap

Modified Files:
        Makefile.am path_graph.cxx path_graph.hxx pathfinder.hxx 
        pingus.cxx pingus.hxx 
Added Files:
        path.cxx path.hxx 
Log Message:
cleaned up worldmap code a bit, interupting the walk and reverse half the way 
down works now

--- NEW FILE: path.cxx ---
//  $Id: path.cxx,v 1.1 2002/10/15 19:13:33 grumbel Exp $
//
//  Pingus - A free Lemmings clone
//  Copyright (C) 2002 Ingo Ruhnke <address@hidden>
//
//  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 2
//  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 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

#include <iostream>
#include "path.hxx"

namespace WorldMapNS {

Path::Path()
{
}

std::vector<Vector>::size_type 
Path::size()
{
  return vec.size();
}

float
Path::length()
{
  if (vec.empty())
    {
      return 0.0f;
    }
  else
    {
      std::cout << "Edgepath size: " << vec.size() << std::endl;
      float length = 0;
      Vec::iterator prev = vec.begin();
      for(Vec::iterator next = prev + 1; next != vec.end(); ++next)
        {
          length += Vector::distance(*prev, *next);
          prev = next;
        }
      return length;
    }
}

Vector
Path::at(float vec_position)
{
  assert(!vec.empty());

  Path::iterator current = vec.begin ();
  Path::iterator next    = vec.begin () + 1;

  float comp_length = 0.0f;
  while (next != vec.end())
    {
      float length = Vector::distance(*current, *next);

      // The pingu is between current and next
      if (comp_length + length > vec_position) 
        {
          float perc = (vec_position - comp_length) // length to walk from 
current node
            / length;

          return Vector::interpolate(*current, *next, perc);
        }

      comp_length += length;

      ++current;
      ++next;
    }
  return vec.back();
}

void
Path::reverse()
{
  std::reverse(vec.begin (), vec.end ());
}

} // namespace WorldMapNS

/* EOF */

--- NEW FILE: path.hxx ---
//  $Id: path.hxx,v 1.1 2002/10/15 19:13:33 grumbel Exp $
// 
//  Pingus - A free Lemmings clone
//  Copyright (C) 2002 Ingo Ruhnke <address@hidden>
//
//  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 2
//  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 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

#ifndef HEADER_PINGUS_WORLDMAP_PATH_HXX
#define HEADER_PINGUS_WORLDMAP_PATH_HXX

#include <vector>
#include "../vector.hxx"

namespace WorldMapNS {

/** a wrapper class around std::vector<Vector>, which can calculate
    the length of the path and a few other things */
class Path
{
private:
  typedef std::vector<Vector> Vec;
  Vec vec;
public:
  typedef Vec::iterator iterator;
  typedef Vec::reverse_iterator reverse_iterator;

  Path();

  /** Return the number of nodes */
  Vec::size_type size();

  /** @return the length of the path in pixels */
  float length();
  
  /** walk a distance of vec_position on the path and return the position,
      positions between two Vectors are interpolated, if length is
      larger then path *back() will be returned */
  Vector at(float vec_position);

  bool empty() { return vec.empty(); }
  void clear() { vec.clear(); }
  iterator begin() { return vec.begin(); }
  iterator end() { return vec.end(); }
  reverse_iterator rbegin() { return vec.rbegin(); }
  reverse_iterator rend() { return vec.rend(); }
  void push_back(const Vector& v) { vec.push_back(v); };
  void insert(Path& p) { vec.insert(vec.end(), p.vec.begin(), p.vec.end()); };
  void reverse_insert(Path& p) { vec.insert(vec.end(), p.vec.rbegin(), 
p.vec.rend()); };
  void reverse();
};

} // namespace WorldMapNS

#endif

/* EOF */

Index: Makefile.am
===================================================================
RCS file: /usr/local/cvsroot/Games/Pingus/src/worldmap/Makefile.am,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -d -r1.10 -r1.11
--- Makefile.am 13 Oct 2002 23:02:29 -0000      1.10
+++ Makefile.am 15 Oct 2002 19:13:33 -0000      1.11
@@ -34,7 +34,8 @@
 level_dot.hxx level_dot.cxx \
 pathfinder.hxx \
 path_drawable.hxx path_drawable.cxx \
-graph.cxx
+graph.cxx \
+path.hxx path.cxx
 
 #node.cxx
 #node.hxx

Index: path_graph.cxx
===================================================================
RCS file: /usr/local/cvsroot/Games/Pingus/src/worldmap/path_graph.cxx,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -d -r1.11 -r1.12
--- path_graph.cxx      15 Oct 2002 17:12:59 -0000      1.11
+++ path_graph.cxx      15 Oct 2002 19:13:33 -0000      1.12
@@ -147,25 +147,12 @@
 
           Path full_path;
           
full_path.push_back(graph.resolve_node(lookup_node(source)).data->get_pos());
-          full_path.insert(full_path.end(), path->begin(), path->end());
+          full_path.insert(*path);
           
full_path.push_back(graph.resolve_node(lookup_node(destination)).data->get_pos());
 
           // FIXME: merge this together with the Pingus::distance() stuff in a 
seperate Path class
-          float cost = 0;
-          {
-            //std::cout << "Edgepath size: " << edge_path.size() << std::endl;
-            Path::iterator prev = full_path.begin();
-            for(Path::iterator next = prev + 1; next != full_path.end(); 
++next)
-              {
-                float x = prev->x - next->x;
-                float y = prev->y - next->y;
-  
-                float distance = fabsf(sqrt((x * x) + (y * y)));
-                cost += distance;
-                prev = next;
-              }
-          }
-          
+          float cost = full_path.length();
+
           // FIXME: Memory leak
           //worldmap->add_drawable(new PathDrawable(full_path));
           
@@ -174,7 +161,9 @@
                                       lookup_node(destination), 
lookup_node(source), 
                                       cost /* costs */);
 
-          EdgeId id2 = graph.add_edge(new Path(path->rbegin(), path->rend()), 
// FIXME: Memory leak!
+          Path* path2 = new Path();
+          path2->reverse_insert(*path);
+          EdgeId id2 = graph.add_edge(path2, // FIXME: Memory leak!
                                       lookup_node(source), 
lookup_node(destination), 
                                       cost /* costs */);
           
@@ -194,18 +183,12 @@
     }    
 }
 
-std::vector<NodeId>
+PathfinderResult
 PathGraph::get_path(NodeId start_id, NodeId end_id)
 {
-  //Node<Dot*>& start = graph.resolve_node(start_id);
-  //Node<Dot*>& end   = graph.resolve_node(end_id);
-
+  // FIXME: This could get cached by the node
   Pathfinder<Dot*, Path*> pathfinder(graph, start_id);
-  std::vector<NodeId> path = pathfinder.get_path(end_id);
-
-  assert(path.size() > 0);
-
-  return path;
+  return pathfinder.get_result(end_id);
 }
 
 EdgeId

Index: path_graph.hxx
===================================================================
RCS file: /usr/local/cvsroot/Games/Pingus/src/worldmap/path_graph.hxx,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- path_graph.hxx      15 Oct 2002 15:48:49 -0000      1.5
+++ path_graph.hxx      15 Oct 2002 19:13:33 -0000      1.6
@@ -24,6 +24,8 @@
 #include <vector>
 #include "../vector.hxx"
 #include "../libxmlfwd.hxx"
+#include "path.hxx"
+#include "pathfinder.hxx"
 #include "graph.hxx"
 
 namespace WorldMapNS {
@@ -31,8 +33,6 @@
 class Dot;
 class WorldMap;
 
-typedef std::vector<Vector> Path;
-
 /** This class represents the walkable path on the Worldmap */
 class PathGraph
 {
@@ -62,7 +62,7 @@
 
   /** @return a list of positions to walk to reach node \a end, by
       starting from \a start */
-  std::vector<NodeId> get_path(NodeId start, NodeId end);
+  PathfinderResult get_path(NodeId start, NodeId end);
 
   /** Get a node by it id */
   Dot* get_dot(NodeId id);

Index: pathfinder.hxx
===================================================================
RCS file: /usr/local/cvsroot/Games/Pingus/src/worldmap/pathfinder.hxx,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- pathfinder.hxx      15 Oct 2002 17:12:59 -0000      1.6
+++ pathfinder.hxx      15 Oct 2002 19:13:33 -0000      1.7
@@ -25,6 +25,12 @@
 
 namespace WorldMapNS {
 
+struct PathfinderResult
+{
+  std::vector<NodeId> path;
+  float cost;
+};
+
 /** */
 template<class T, class C>
 class Pathfinder
@@ -138,6 +144,20 @@
          }     
       }
     while (1);
+  }
+
+  /** @return the cost of the path to node */
+  float get_cost(NodeId node)
+  {
+    return stat_graph[node].cost;
+  }
+
+  PathfinderResult get_result(NodeId node)
+  {
+    PathfinderResult res;
+    res.path = get_path(node);
+    res.cost = get_cost(node);
+    return res;
   }
 
   void push_to_open (NodeId handle)

Index: pingus.cxx
===================================================================
RCS file: /usr/local/cvsroot/Games/Pingus/src/worldmap/pingus.cxx,v
retrieving revision 1.17
retrieving revision 1.18
diff -u -d -r1.17 -r1.18
--- pingus.cxx  15 Oct 2002 15:48:49 -0000      1.17
+++ pingus.cxx  15 Oct 2002 19:13:33 -0000      1.18
@@ -67,7 +67,7 @@
   // Update the edge_path_position
   edge_path_position += velocity * delta;
   
-  if (edge_path_position > edge_path_length) // target reached
+  if (edge_path_position > edge_path.length()) // target reached
     {
       if (node_path.empty ()) // final target reached
         {
@@ -83,26 +83,12 @@
   pos = calc_pos ();
 }
 
-float 
-Pingus::calc_edge_path_length()
-{
-  std::cout << "Edgepath size: " << edge_path.size() << std::endl;
-  float length = 0;
-  Path::iterator prev = edge_path.begin();
-  for(Path::iterator next = prev + 1; next != edge_path.end(); ++next)
-    {
-      length += distance(*prev, *next);
-      prev = next;
-    }
-  return length;
-}
-
 bool
 Pingus::walk_to_node (NodeId target)
 {
   if (current_node != NoNode) // pingu stands still
     {
-      node_path = path->get_path (current_node, target);
+      node_path = path->get_path (current_node, target).path;
 
       // Simulate that we just reached current_node, then update the edge_path
       target_node = node_path.back(); // equal to current_node;
@@ -114,27 +100,44 @@
     }
   else // pingu between two nodes
     {
-      assert(false);
-#if 0
-      std::vector<NodeId> node_path1 = path->get_path (source_node, target);
-      std::vector<NodeId> node_path2 = path->get_path (target_node, target);
-       
-      // Select the shorter path
-      if (length (node_path1) < length (node_path2))
-        { // walk to source node, which means to reverse the pingu
-          node_path = node_path1;
-
+      if (target_node == target)
+        {
+          node_path.clear();
+          return true;
+        }
+      else if (source_node == target)
+        {
           // Reverse the pingu
           std::swap(target_node, source_node);
-          std::reverse(edge_path.begin (), edge_path.end ());
-          edge_path_position = edge_path_lenght - edge_path_position;
+          edge_path.reverse();
+          edge_path_position = edge_path.length() - edge_path_position;        
 
+          node_path.clear();
+          return true;
         }
       else
-        { // walk to target_node
-          node_path = node_path2;
+        {
+          PathfinderResult node_path1 = path->get_path (source_node, target);
+          PathfinderResult node_path2 = path->get_path (target_node, target);
+       
+          // Select the shorter path
+          if (node_path1.cost < node_path2.cost)
+            { // walk to source node, which means to reverse the pingu
+              node_path = node_path1.path;
+
+              // Reverse the pingu
+              std::swap(target_node, source_node);
+              edge_path.reverse();
+              edge_path_position = edge_path.length() - edge_path_position;
+            }
+          else
+            { // walk to target_node
+              node_path = node_path2.path;
+            }
+          // Pop the first element on the stack, since we are already 
targeting it
+          node_path.pop_back();
+
+          return true;
         }
-#endif
-      return false;
     }
 }
 
@@ -147,49 +150,10 @@
     }
   else // between two nodes
     {
-      Path::iterator current = edge_path.begin ();
-      Path::iterator next    = edge_path.begin () + 1;
-
-      float comp_length = 0.0f;
-      while (next != edge_path.end())
-        {
-          float length = distance(*current, *next);
-
-          // The pingu is between current and next
-          if (comp_length + length > edge_path_position) 
-            {
-              float perc = (edge_path_position - comp_length) // length to 
walk from current node
-                / length;
-
-              return interpolate (*current, *next, perc);
-            }
-
-          comp_length += length;
-
-          ++current;
-          ++next;
-        }
-      assert (!"This shouldn't happen, traveled bejoint target node");
-      return path->graph.resolve_node(target_node).data->get_pos ();
+      return edge_path.at(edge_path_position);
     }
 }
 
-float
-Pingus::distance(const Vector& a, const Vector& b)
-{
-  float x = b.x - a.x;
-  float y = b.y - a.y;
-  
-  return fabsf(sqrt((x * x) + (y * y)));
-}
-
-Vector
-Pingus::interpolate(const Vector& a, const Vector& b, float perc)
-{
-  Vector c = b - a;
-  return a + (c * perc);
-}
-
 void
 Pingus::set_position (NodeId node)
 {
@@ -206,7 +170,7 @@
 }
 
 void
-Pingus:: update_edge_path()
+Pingus::update_edge_path()
 {
   // Update source and target nodes
   source_node = target_node;
@@ -220,10 +184,8 @@
           
   edge_path.push_back(path->graph.resolve_node(source_node).data->get_pos());
   // Why do we need to reverse this?!
-  edge_path.insert(edge_path.end(), partial_path->rbegin(), 
partial_path->rend());
+  edge_path.reverse_insert(*partial_path);
   edge_path.push_back(path->graph.resolve_node(target_node).data->get_pos());
-  
-  edge_path_length = calc_edge_path_length();
 }
 
 bool

Index: pingus.hxx
===================================================================
RCS file: /usr/local/cvsroot/Games/Pingus/src/worldmap/pingus.hxx,v
retrieving revision 1.17
retrieving revision 1.18
diff -u -d -r1.17 -r1.18
--- pingus.hxx  15 Oct 2002 15:48:49 -0000      1.17
+++ pingus.hxx  15 Oct 2002 19:13:33 -0000      1.18
@@ -66,9 +66,6 @@
       both source and destinations position, so it is complete */
   Path edge_path;
   
-  /** The length of the edge_path in pixels */
-  float edge_path_length;
-
   /** The position in the edge_path, 0 means the pingu is on the
       source_node, edge_path_length means that the pingu has reached
       the target node. Position between edge_path nodes is
@@ -107,14 +104,13 @@
 
 private:
   void  update_walk (float delta);
-  void  update_edge_path();
+
+  void update_edge_path();
+
   float calc_edge_path_length();
   
   /** */
   Vector interpolate(const Vector& a, const Vector& b, float perc);
-
-  float distance(const Vector& a, const Vector& b);
-
 
   Pingus (const Pingus&);
   Pingus& operator= (const Pingus&);