SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
PedestrianRouter.h
Go to the documentation of this file.
1 /****************************************************************************/
7 // The Pedestrian Router build a special network and (delegegates to a SUMOAbstractRouter)
8 /****************************************************************************/
9 // SUMO, Simulation of Urban MObility; see http://sumo-sim.org/
10 // Copyright (C) 2001-2014 DLR (http://www.dlr.de/) and contributors
11 /****************************************************************************/
12 //
13 // This file is part of SUMO.
14 // SUMO is free software: you can redistribute it and/or modify
15 // it under the terms of the GNU General Public License as published by
16 // the Free Software Foundation, either version 3 of the License, or
17 // (at your option) any later version.
18 //
19 /****************************************************************************/
20 #ifndef PedestrianRouter_h
21 #define PedestrianRouter_h
22 
23 
24 // ===========================================================================
25 // included modules
26 // ===========================================================================
27 #ifdef _MSC_VER
28 #include <windows_config.h>
29 #else
30 #include <config.h>
31 #endif
32 
33 #include <string>
34 #include <vector>
35 #include <algorithm>
36 #include <assert.h>
37 #include <utils/common/SysUtils.h>
39 #include <utils/common/SUMOTime.h>
40 #include <utils/common/ToString.h>
41 #include <utils/common/Named.h>
45 
46 #define TL_RED_PENALTY 20
47 
48 //#define PedestrianRouter_DEBUG_NETWORK
49 //#define PedestrianRouter_DEBUG_ROUTES
50 //#define PedestrianRouter_DEBUG_EFFORTS
51 
52 template <class E, class L>
53 inline const L* getSidewalk(const E* edge) {
54  if (edge == 0) {
55  return 0;
56  }
57  const std::vector<L*>& lanes = edge->getLanes();
58  for (typename std::vector<L*>::const_iterator it = lanes.begin(); it != lanes.end(); ++it) {
59  if ((*it)->allowsVehicleClass(SVC_PEDESTRIAN)) {
60  return *it;
61  }
62  }
63  return 0;
64 }
65 
66 // ===========================================================================
67 // class definitions
68 // ===========================================================================
69 
71 template<class E, class N>
73 
74  PedestrianTrip(const E* _from, const E* _to, SUMOReal _departPos, SUMOReal _arrivalPos, SUMOReal _speed, SUMOReal _departTime, const N* _node) :
75  from(_from),
76  to(_to),
77  node(_node),
78  departPos(_departPos < 0 ? _from->getLength() + _departPos : _departPos),
79  arrivalPos(_arrivalPos < 0 ? _to->getLength() + _arrivalPos : _arrivalPos),
80  speed(_speed),
81  departTime(_departTime)
82  {}
83 
84  const E* from;
85  const E* to;
86  const N* node; // indicates whether only routing across this node shall be performed
89  const SUMOReal speed;
91 private:
94 };
95 
96 
98 template<class E, class L, class N>
99 class PedestrianEdge : public Named {
100  typedef std::pair<PedestrianEdge*, PedestrianEdge*> EdgePair;
101  /* brief build the pedestrian network (once)
102  * @param noE The number of edges in the dictionary of E
103  */
104 
105 public:
106  static size_t dictSize() {
107  return myEdgeDict.size();
108  }
109 
110  static void cleanup() {
111  myFromToLookup.clear();
112  myBidiLookup.clear();
113  myEdgeDict.clear();
114  }
115 
116  static void initPedestrianNetwork(size_t noE) {
117  if (myEdgeDict.size() > 0) {
118  return;
119  }
120 #ifdef PedestrianRouter_DEBUG_NETWORK
121  std::cout << "initPedestrianNetwork\n";
122 #endif
123  // build the Pedestrian edges
124  unsigned int numericalID = 0;
125  for (size_t i = 0; i < noE; i++) {
126  E* edge = E::dictionary(i);
127  const L* lane = getSidewalk<E, L>(edge);
128  if (edge->isInternal() || lane == 0) {
129  continue;
130  } else if (edge->isWalkingArea()) {
131  // only a single edge
132  myEdgeDict.push_back(PedestrianEdge(numericalID++, edge, lane, true));
133  } else { // regular edge or crossing
134  // forward and backward edges
135  myEdgeDict.push_back(PedestrianEdge(numericalID++, edge, lane, true));
136  myEdgeDict.push_back(PedestrianEdge(numericalID++, edge, lane, false));
137  // depart and arrival edges for (the router can decide the initial direction to take and the direction to arrive from)
138  myEdgeDict.push_back(PedestrianEdge(numericalID++, edge, lane, true, true));
139  myEdgeDict.push_back(PedestrianEdge(numericalID++, edge, lane, false, true));
140  }
141 
142  }
143  // build the lookup tables after myEdgeDict is complete
144  numericalID = 0;
145  for (size_t i = 0; i < noE; i++) {
146  E* edge = E::dictionary(i);
147  const L* lane = getSidewalk<E, L>(edge);
148  if (edge->isInternal() || lane == 0) {
149  continue;
150  } else if (edge->isWalkingArea()) {
151  // only a single edge and no connector edges
152  myBidiLookup[edge] = std::make_pair(&myEdgeDict[numericalID], &myEdgeDict[numericalID]);
153  myFromToLookup[edge] = std::make_pair(&myEdgeDict[numericalID], &myEdgeDict[numericalID]);
154  numericalID += 1;
155  } else { // regular edge or crossing
156  myBidiLookup[edge] = std::make_pair(&myEdgeDict[numericalID], &myEdgeDict[numericalID + 1]);
157  myFromToLookup[edge] = std::make_pair(&myEdgeDict[numericalID + 2], &myEdgeDict[numericalID + 3]);
158  numericalID += 4;
159  }
160  }
161 
162  // build the connections
163  for (size_t i = 0; i < noE; i++) {
164  E* edge = E::dictionary(i);
165  const L* lane = getSidewalk<E, L>(edge);
166  if (edge->isInternal() || lane == 0) {
167  continue;
168  }
169  // find all incoming and outgoing lanes for the sidewalk and
170  // connect the corresponding PedestrianEdges
171  const L* sidewalk = getSidewalk<E, L>(edge);
172  const EdgePair& pair = getBothDirections(edge);
173 
174 #ifdef PedestrianRouter_DEBUG_NETWORK
175  std::cout << " building connections from " << sidewalk->getID() << "\n";
176 #endif
177  std::vector<const L*> outgoing = sidewalk->getOutgoingLanes();
178  for (typename std::vector<const L*>::iterator it = outgoing.begin(); it != outgoing.end(); ++it) {
179  const L* target = *it;
180  const E* targetEdge = &(target->getEdge());
181 #ifdef PedestrianRouter_DEBUG_NETWORK
182  std::cout << " lane=" << getSidewalk<E, L>(targetEdge)->getID() << (target == getSidewalk<E, L>(targetEdge) ? "(used)" : "") << "\n";
183 #endif
184  if (target == getSidewalk<E, L>(targetEdge)) {
185  const EdgePair& targetPair = getBothDirections(targetEdge);
186  pair.first->myFollowingEdges.push_back(targetPair.first);
187  targetPair.second->myFollowingEdges.push_back(pair.second);
188 #ifdef PedestrianRouter_DEBUG_NETWORK
189  std::cout << " " << pair.first->getID() << " -> " << targetPair.first->getID() << "\n";
190  std::cout << " " << targetPair.second->getID() << " -> " << pair.second->getID() << "\n";
191 #endif
192  }
193  }
194  if (edge->isWalkingArea()) {
195  continue;
196  }
197  // build connections from depart connector
198  PedestrianEdge* startConnector = getDepartEdge(edge);
199  startConnector->myFollowingEdges.push_back(pair.first);
200  startConnector->myFollowingEdges.push_back(pair.second);
201  // build connections to arrival connector
202  PedestrianEdge* endConnector = getArrivalEdge(edge);
203  pair.first->myFollowingEdges.push_back(endConnector);
204  pair.second->myFollowingEdges.push_back(endConnector);
205 #ifdef PedestrianRouter_DEBUG_NETWORK
206  std::cout << " " << startConnector->getID() << " -> " << pair.first->getID() << "\n";
207  std::cout << " " << startConnector->getID() << " -> " << pair.second->getID() << "\n";
208  std::cout << " " << pair.first->getID() << " -> " << endConnector->getID() << "\n";
209  std::cout << " " << pair.second->getID() << " -> " << endConnector->getID() << "\n";
210 #endif
211  }
212  }
213 
214  bool includeInRoute(bool allEdges) const {
215  return !myAmConnector && (allEdges || (!myEdge->isCrossing() && !myEdge->isWalkingArea()));
216  }
217 
218  const E* getEdge() const {
219  return myEdge;
220  }
221 
223  static const EdgePair& getBothDirections(const E* e) {
224  typename std::map<const E*, EdgePair>::const_iterator it = myBidiLookup.find(e);
225  if (it == myBidiLookup.end()) {
226  assert(false);
227  throw ProcessError("Edge '" + e->getID() + "' not found in pedestrian network '");
228  }
229  return (*it).second;
230  }
231 
233  static PedestrianEdge* getDepartEdge(const E* e) {
234  typename std::map<const E*, EdgePair>::const_iterator it = myFromToLookup.find(e);
235  if (it == myFromToLookup.end()) {
236  assert(false);
237  throw ProcessError("Edge '" + e->getID() + "' not found in pedestrian network '");
238  }
239  return (*it).second.first;
240  }
241 
243  static PedestrianEdge* getArrivalEdge(const E* e) {
244  typename std::map<const E*, EdgePair>::const_iterator it = myFromToLookup.find(e);
245  if (it == myFromToLookup.end()) {
246  assert(false);
247  throw ProcessError("Edge '" + e->getID() + "' not found in pedestrian network '");
248  }
249  return (*it).second.second;
250  }
251 
254 
255  unsigned int getNumericalID() const {
256  return myNumericalID;
257  }
258 
260  static const PedestrianEdge* dictionary(size_t index) {
261  assert(index < myEdgeDict.size());
262  return &myEdgeDict[index];
263  }
264 
265  unsigned int getNoFollowing() const {
266  return (unsigned int)myFollowingEdges.size();
267  }
268 
269  PedestrianEdge* getFollower(unsigned int i) const {
270  return myFollowingEdges[i];
271  }
272 
273  bool prohibits(const PedestrianTrip<E, N>* const trip) const {
274  if (trip->node == 0) {
275  // network only includes PedestrianEdges
276  return false;
277  } else {
278  // limit routing to the surroundings of the specified node
279  return (myEdge->getFromJunction() != trip->node
280  && myEdge->getToJunction() != trip->node);
281  }
282  }
283 
285 
286  /*@brief the function called by RouterTT_direct
287  * (distance is used as effort, effort is assumed to be independent of time
288  */
289  SUMOReal getEffort(const PedestrianTrip<E, N>* const trip, SUMOReal time) const {
290  if (myAmConnector) {
291  return 0;
292  }
293  SUMOReal length = myEdge->getLength();
294  if (myEdge == trip->from) {
295  if (myForward) {
296  length -= trip->departPos;
297  } else {
298  length = trip->departPos;
299  }
300  }
301  if (myEdge == trip->to) {
302  if (myForward) {
303  length = trip->arrivalPos;
304  } else {
305  length -= trip->arrivalPos;
306  }
307  }
308  // ensure that 'normal' edges always have a higher weight than connector edges
309  length = MAX2(length, POSITION_EPS);
310  SUMOReal tlsDelay = 0;
311  if (myEdge->isCrossing() && myLane->getIncomingLinkState() == LINKSTATE_TL_RED) {
312  // red traffic lights occurring later in the route may be green by the time we arive
313  tlsDelay += MAX2(SUMOReal(0), TL_RED_PENALTY - (time - trip->departTime));
314 
315  }
316 #ifdef PedestrianRouter_DEBUG_EFFORTS
317  std::cout << " effort for " << getID() << " at " << time << ": " << length / trip->speed + tlsDelay << " l=" << length << " s=" << trip->speed << " tlsDelay=" << tlsDelay << "\n";
318 #endif
319  return length / trip->speed + tlsDelay;
320  }
321 
322 private:
323  PedestrianEdge(unsigned int numericalID, const E* edge, const L* lane, bool forward, bool connector = false) :
324  Named(edge->getID() + (edge->isWalkingArea() ? "" :
325  ((forward ? "_fwd" : "_bwd") + std::string(connector ? "_connector" : "")))),
326  myNumericalID(numericalID),
327  myEdge(edge),
328  myLane(lane),
329  myForward(forward),
330  myAmConnector(connector) { }
331 
333  unsigned int myNumericalID;
334 
336  const E* myEdge;
337 
339  const L* myLane;
340 
342  bool myForward;
343 
346 
348  std::vector<PedestrianEdge*> myFollowingEdges;
349 
351  static std::vector<PedestrianEdge> myEdgeDict;
352 
354  static std::map<const E*, EdgePair> myBidiLookup;
355 
357  static std::map<const E*, EdgePair> myFromToLookup;
358 
359 };
360 
361 
366 template<class E, class L, class N, class INTERNALROUTER>
367 class PedestrianRouter : public SUMOAbstractRouter<E, PedestrianTrip<E, N> > {
368 public:
369 
372 
375  SUMOAbstractRouter<E, _PedestrianTrip>("PedestrianRouter") {
378  }
379 
381  virtual ~PedestrianRouter() {
382  delete myInternalRouter;
383  }
384 
387  void compute(const E* from, const E* to, SUMOReal departPos, SUMOReal arrivalPos, SUMOReal speed,
388  SUMOTime msTime, const N* onlyNode, std::vector<const E*>& into, bool allEdges = false) {
389  //startQuery();
390  _PedestrianTrip trip(from, to, departPos, arrivalPos, speed, msTime, onlyNode);
391  std::vector<const _PedestrianEdge*> intoPed;
393  _PedestrianEdge::getArrivalEdge(to), &trip, msTime, intoPed);
394  for (size_t i = 0; i < intoPed.size(); ++i) {
395  if (intoPed[i]->includeInRoute(allEdges)) {
396  into.push_back(intoPed[i]->getEdge());
397  }
398  }
399 #ifdef PedestrianRouter_DEBUG_ROUTES
400  std::cout << TIME2STEPS(msTime) << " trip from " << from->getID() << " to " << to->getID()
401  << " departPos=" << departPos
402  << " arrivalPos=" << arrivalPos
403  << " onlyNode=" << (onlyNode == 0 ? "NULL" : onlyNode->getID())
404  << " edges=" << toString(intoPed)
405  << " resultEdges=" << toString(into)
406  << "\n";
407 #endif
408  //endQuery();
409  }
410 
413  void compute(const E*, const E*, const _PedestrianTrip* const,
414  SUMOTime, std::vector<const E*>&) {
415  throw ProcessError("Do not use this method");
416  }
417 
418  SUMOReal recomputeCosts(const std::vector<const E*>&, const _PedestrianTrip* const, SUMOTime) const {
419  throw ProcessError("Do not use this method");
420  }
421 
422  void prohibit(const std::vector<E*>& toProhibit) {
423  std::vector<_PedestrianEdge*> toProhibitPE;
424  for (typename std::vector<E*>::const_iterator it = toProhibit.begin(); it != toProhibit.end(); ++it) {
425  toProhibitPE.push_back(_PedestrianEdge::getBothDirections(*it).first);
426  toProhibitPE.push_back(_PedestrianEdge::getBothDirections(*it).second);
427  }
428  myInternalRouter->prohibit(toProhibitPE);
429  }
430 
431 private:
432  INTERNALROUTER* myInternalRouter;
433 
434 
435 private:
438 
439 private:
440 
441 };
442 
443 // common specializations
444 template<class E, class L, class N>
446  DijkstraRouterTT_Direct<PedestrianEdge<E, L, N>, PedestrianTrip<E, N>, prohibited_withRestrictions<PedestrianEdge<E, L, N>, PedestrianTrip<E, N> > > > { };
447 
448 
449 // ===========================================================================
450 // static member definitions (PedestrianEdge)
451 // ===========================================================================
452 
453 template<class E, class L, class N>
454 std::vector<PedestrianEdge<E, L, N> > PedestrianEdge<E, L, N>::myEdgeDict;
455 
456 template<class E, class L, class N>
457 std::map<const E*, typename PedestrianEdge<E, L, N>::EdgePair> PedestrianEdge<E, L, N>::myBidiLookup;
458 
459 template<class E, class L, class N>
460 std::map<const E*, typename PedestrianEdge<E, L, N>::EdgePair> PedestrianEdge<E, L, N>::myFromToLookup;
461 
462 #endif
463 
464 
465 /****************************************************************************/
466