Developer Documentation
wayfind.hh
1 /*===========================================================================*\
2 * *
3 * OpenFlipper *
4  * Copyright (c) 2001-2015, RWTH-Aachen University *
5  * Department of Computer Graphics and Multimedia *
6  * All rights reserved. *
7  * www.openflipper.org *
8  * *
9  *---------------------------------------------------------------------------*
10  * This file is part of OpenFlipper. *
11  *---------------------------------------------------------------------------*
12  * *
13  * Redistribution and use in source and binary forms, with or without *
14  * modification, are permitted provided that the following conditions *
15  * are met: *
16  * *
17  * 1. Redistributions of source code must retain the above copyright notice, *
18  * this list of conditions and the following disclaimer. *
19  * *
20  * 2. Redistributions in binary form must reproduce the above copyright *
21  * notice, this list of conditions and the following disclaimer in the *
22  * documentation and/or other materials provided with the distribution. *
23  * *
24  * 3. Neither the name of the copyright holder nor the names of its *
25  * contributors may be used to endorse or promote products derived from *
26  * this software without specific prior written permission. *
27  * *
28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39 * *
40 \*===========================================================================*/
41 
42 
43 
44 #ifndef VSI_WAYFIND_HH
45 #define VSI_WAYFIND_HH
46 
47 //== INCLUDES =================================================================
48 #include <QRegion>
49 #include <QPolygonF>
50 #include <QPoint>
51 #include <QLinkedList>
52 
53 //== NAMESPACES ===============================================================
54 namespace VSI {
55 
56 //== FORWARDDECLARATIONS ======================================================
57 class GraphicsScene;
58 class Connection;
59 
60 //== CLASS DEFINITION =========================================================
61 
64 class WayFind {
65 
66  public:
68  explicit WayFind (GraphicsScene *_scene);
69 
71  ~WayFind ();
72 
74  QPolygonF findWay (Connection *_conn, QPoint _from, QPoint _to);
75 
76  private:
77 
78  // Area node class
79  class Node {
80  public:
81 
82  // node direction
83  enum Type {
84  Vertical,
85  Horizontal
86  };
87 
88  explicit Node (unsigned int _counter);
89  ~Node ();
90 
91  public:
92  // last used counter
93  unsigned int counter_;
94 
95  // current direction
96  Type type_;
97 
98  // neighbor nodes
99  Node *n_[4];
100 
101  // linked list handling
102  Node *prev_;
103  Node *next_;
104 
105  // node position
106  QPoint pos_;
107 
108  // initialized from
109  Node *from_;
110 
111  // A-Star consts
112  unsigned int g_;
113  unsigned int f_;
114  unsigned int h_;
115 
116  // node cost
117  unsigned int cost_;
118 
119  // already traversed
120  bool closed_;
121  };
122 
123  // Next position in distance _step from _pnt in direction _dir
124  QPoint validPos (unsigned int _dir, int _step, QPoint _pnt);
125 
126  // Heuristic distance from _from to _to
127  int heuristicDistance (const QPoint &_from, const QPoint &_to) const;
128 
129  // cleanup ununsed nodes
130  void cleanup ();
131 
132  private:
133 
134  GraphicsScene *scene_;
135 
136  unsigned int counter_;
137 
138  QLinkedList<Node *> nodes_;
139  QHash<QPair<int, int>, Node*> map_;
140 
141  Node *ll_;
142  QPoint oldFrom_;
143  QRegion oldReg_;
144 };
145 
146 }
147 
148 #endif
~WayFind()
Destructor.
Definition: wayfind.cc:86
WayFind(GraphicsScene *_scene)
Constructor.
Definition: wayfind.cc:76
QPolygonF findWay(Connection *_conn, QPoint _from, QPoint _to)
Finds a way from _from to _to ignoring any already existent connections from _conn.
Definition: wayfind.cc:95