summaryrefslogtreecommitdiff
path: root/2004/i/nono/src/path/map_graph.h
blob: 94f572574ae9469270a466ef47e84ed071c0bb28 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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);
    /// 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