[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Pingus-CVS] CVS: Games/Pingus/src/worldmap path.cxx,NONE,1.1 path.hxx,N
From: |
grumbel |
Subject: |
[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 |
Date: |
15 Oct 2002 19:13:35 -0000 |
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&);
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [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 <=
- Prev by Date:
[Pingus-CVS] CVS: Games/Pingus/src vector.cxx,1.1,1.2 vector.hxx,1.1,1.2
- Next by Date:
[Pingus-CVS] CVS: Games/Pingus/data/images/groundpieces/ground/green Makefile.am,NONE,1.1
- Previous by thread:
[Pingus-CVS] CVS: Games/Pingus/src vector.cxx,1.1,1.2 vector.hxx,1.1,1.2
- Next by thread:
[Pingus-CVS] CVS: Games/Pingus/data/images/groundpieces/ground/green Makefile.am,NONE,1.1
- Index(es):