#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 #include #include 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 Obstacles; Obstacles obstacles_; typedef std::vector Points; Points points_; typedef std::vector ArcsLine; typedef std::vector Arcs; Arcs arcs_; static const double sqrt2_ = 1.41421356237309504880; static const double margin_ = 1.1; Point min_, max_; typedef std::vector Parent; Parent parents_; typedef std::vector Dists; Dists distsMin_; std::vector 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); /// Place les points correspondants aux obstacles. void placePoints (void); /// Construit le graph à partir des points en prenant en compte les /// obstacles. void buildGraph (void); /// Trouve les plus cours chemins vers le points d'arrivée. void findPath (int steps = -1); /// Trouve le prochain point cible à partir de p. Renvois true si trouvé. bool nextPoint (const Point &p, Point &target); private: /// Calcule la distance entre deux points en prenant les obstacles en /// compte. double computeDist (const Point &a, const Point &b) const; }; /// Sort sur un std::ostream. std::ostream &operator<< (std::ostream &os, const MapGraph &mg); } // namespace Path #endif // map_graph_h