summaryrefslogtreecommitdiff
path: root/2004/i/nono/src/path/map_graph.h
diff options
context:
space:
mode:
Diffstat (limited to '2004/i/nono/src/path/map_graph.h')
-rw-r--r--2004/i/nono/src/path/map_graph.h86
1 files changed, 86 insertions, 0 deletions
diff --git a/2004/i/nono/src/path/map_graph.h b/2004/i/nono/src/path/map_graph.h
new file mode 100644
index 0000000..13452f8
--- /dev/null
+++ b/2004/i/nono/src/path/map_graph.h
@@ -0,0 +1,86 @@
+#ifndef map_graph_h
+#define map_graph_h
+// map_graph.h
+// nono - programme du robot 2004. {{{
+//
+// Copyright (C) 2004 Nicolas Schodet
+//
+// Robot APB Team/Efrei 2004.
+// Web: http://assos.efrei.fr/robot/
+// Email: robot AT efrei DOT fr
+//
+// 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 "utils/point.h"
+
+#include <list>
+#include <iostream>
+#include <vector>
+
+namespace Path {
+
+/// Carte vectorielle permettant de trouver son chemin.
+class MapGraph
+{
+ struct Obstacle
+ {
+ Point c;
+ double r;
+ Obstacle (const Point &c_, double r_) : c (c_), r (r_) { }
+ };
+ typedef std::list<Obstacle> Obstacles;
+ Obstacles obstacles_;
+ typedef std::vector<Point> Points;
+ Points points_;
+ typedef std::vector<double> ArcsLine;
+ typedef std::vector<ArcsLine> Arcs;
+ Arcs arcs_;
+ static const double sqrt2_ = 1.41421356237309504880;
+ static const double margin_ = 1.1;
+ Point min_, max_;
+ typedef std::vector<int> Parent;
+ Parent parents_;
+ typedef std::vector<double> Dists;
+ Dists distsMin_;
+ std::vector<int> E;
+ public:
+ /// Constructeur.
+ MapGraph (const Point &min, const Point &max);
+ /// Ajoute un obstacle.
+ void add (const Point &c, double r);
+ /// Paramètre le point d'arrivée.
+ void setGoal (const Point &goal);
+ /// Sort sur un std::ostream.
+ friend std::ostream &operator<< (std::ostream &os, const MapGraph &mg);
+// private:
+ /// Place les points correspondants aux obstacles.
+ void placePoints (void);
+ /// Construit le graph à partir des points en prenant en compte les
+ /// obstacles.
+ void buildGraph (void);
+ /// Calcule la distance entre deux points en prenant les obstacles en
+ /// compte.
+ double computeDist (const Point &a, const Point &b) const;
+ /// Trouve les plus cours chemins vers le points d'arrivée.
+ void findPath (int steps = -1);
+};
+
+/// Sort sur un std::ostream.
+std::ostream &operator<< (std::ostream &os, const MapGraph &mg);
+
+} // namespace Path
+
+#endif // map_graph_h