Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2024 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file NBRequest.cpp
15 : /// @author Daniel Krajzewicz
16 : /// @author Jakob Erdmann
17 : /// @author Michael Behrisch
18 : /// @author Laura Bieker
19 : /// @date Tue, 20 Nov 2001
20 : ///
21 : // This class computes the logic of a junction
22 : /****************************************************************************/
23 : #include <config.h>
24 :
25 : #include <string>
26 : #include <vector>
27 : #include <set>
28 : #include <algorithm>
29 : #include <bitset>
30 : #include <sstream>
31 : #include <map>
32 : #include <cassert>
33 : #include <utils/common/MsgHandler.h>
34 : #include <utils/common/ToString.h>
35 : #include <utils/options/OptionsCont.h>
36 : #include <utils/iodevices/OutputDevice.h>
37 : #include "NBEdge.h"
38 : #include "NBContHelper.h"
39 : #include "NBNode.h"
40 : #include "NBRequest.h"
41 :
42 : //#define DEBUG_RESPONSE
43 : //#define DEBUG_SETBLOCKING
44 : #define DEBUGCOND (myJunction->getID() == "C")
45 :
46 : // ===========================================================================
47 : // static member variables
48 : // ===========================================================================
49 : int NBRequest::myGoodBuilds = 0;
50 : int NBRequest::myNotBuild = 0;
51 :
52 :
53 : // ===========================================================================
54 : // method definitions
55 : // ===========================================================================
56 42832 : NBRequest::NBRequest(const NBEdgeCont& ec,
57 : NBNode* junction,
58 : const EdgeVector& all,
59 : const EdgeVector& incoming,
60 : const EdgeVector& outgoing,
61 42832 : const NBConnectionProhibits& loadedProhibits) :
62 42832 : myJunction(junction),
63 42832 : myAll(all),
64 42832 : myIncoming(incoming),
65 42832 : myOutgoing(outgoing) {
66 42832 : const int variations = numLinks();
67 : // build maps with information which forbidding connection were
68 : // computed and what's in there
69 42832 : myForbids.reserve(variations);
70 42832 : myDone.reserve(variations);
71 263345 : for (int i = 0; i < variations; i++) {
72 220513 : myForbids.push_back(LinkInfoCont(variations, false));
73 441026 : myDone.push_back(LinkInfoCont(variations, false));
74 : }
75 : // insert loaded prohibits
76 42934 : for (NBConnectionProhibits::const_iterator j = loadedProhibits.begin(); j != loadedProhibits.end(); j++) {
77 102 : NBConnection prohibited = (*j).first;
78 102 : bool ok1 = prohibited.check(ec);
79 102 : if (find(myIncoming.begin(), myIncoming.end(), prohibited.getFrom()) == myIncoming.end()) {
80 : ok1 = false;
81 : }
82 102 : if (find(myOutgoing.begin(), myOutgoing.end(), prohibited.getTo()) == myOutgoing.end()) {
83 : ok1 = false;
84 : }
85 : int idx1 = 0;
86 102 : if (ok1) {
87 102 : idx1 = getIndex(prohibited.getFrom(), prohibited.getTo());
88 102 : if (idx1 < 0) {
89 : ok1 = false;
90 : }
91 : }
92 : const NBConnectionVector& prohibiting = (*j).second;
93 301 : for (NBConnectionVector::const_iterator k = prohibiting.begin(); k != prohibiting.end(); k++) {
94 199 : NBConnection sprohibiting = *k;
95 199 : bool ok2 = sprohibiting.check(ec);
96 199 : if (find(myIncoming.begin(), myIncoming.end(), sprohibiting.getFrom()) == myIncoming.end()) {
97 : ok2 = false;
98 : }
99 199 : if (find(myOutgoing.begin(), myOutgoing.end(), sprohibiting.getTo()) == myOutgoing.end()) {
100 : ok2 = false;
101 : }
102 199 : if (ok1 && ok2) {
103 199 : int idx2 = getIndex(sprohibiting.getFrom(), sprohibiting.getTo());
104 199 : if (idx2 < 0) {
105 : ok2 = false;
106 : } else {
107 199 : myForbids[idx2][idx1] = true;
108 : myDone[idx2][idx1] = true;
109 199 : myDone[idx1][idx2] = true;
110 199 : myGoodBuilds++;
111 : }
112 : } else {
113 0 : std::string pfID = prohibited.getFrom() != nullptr ? prohibited.getFrom()->getID() : "UNKNOWN";
114 0 : std::string ptID = prohibited.getTo() != nullptr ? prohibited.getTo()->getID() : "UNKNOWN";
115 0 : std::string bfID = sprohibiting.getFrom() != nullptr ? sprohibiting.getFrom()->getID() : "UNKNOWN";
116 0 : std::string btID = sprohibiting.getTo() != nullptr ? sprohibiting.getTo()->getID() : "UNKNOWN";
117 0 : WRITE_WARNING("could not prohibit " + pfID + "->" + ptID + " by " + bfID + "->" + btID);
118 0 : myNotBuild++;
119 : }
120 199 : }
121 102 : }
122 : // ok, check whether someone has prohibited two links vice versa
123 : // (this happens also in some Vissim-networks, when edges are joined)
124 263345 : for (int s1 = 0; s1 < variations; s1++) {
125 1723863 : for (int s2 = s1 + 1; s2 < variations; s2++) {
126 : // not set, yet
127 1503350 : if (!myDone[s1][s2]) {
128 1503238 : continue;
129 : }
130 : // check whether both prohibit vice versa
131 112 : if (myForbids[s1][s2] && myForbids[s2][s1]) {
132 : // mark unset - let our algorithm fix it later
133 : myDone[s1][s2] = false;
134 : myDone[s2][s1] = false;
135 : }
136 : }
137 : }
138 42832 : }
139 :
140 :
141 42832 : NBRequest::~NBRequest() {}
142 :
143 :
144 : void
145 36605 : NBRequest::buildBitfieldLogic() {
146 : EdgeVector::const_iterator i, j;
147 112556 : for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
148 275465 : for (j = myOutgoing.begin(); j != myOutgoing.end(); j++) {
149 199514 : computeRightOutgoingLinkCrossings(*i, *j);
150 199514 : computeLeftOutgoingLinkCrossings(*i, *j);
151 : }
152 : }
153 : // reset signalised/non-signalised dependencies
154 36605 : resetSignalised();
155 : // reset foes it the number of lanes matches (or exceeds) the number of incoming connections
156 36605 : resetCooperating();
157 36605 : }
158 :
159 :
160 : void
161 199514 : NBRequest::computeRightOutgoingLinkCrossings(NBEdge* from, NBEdge* to) {
162 199514 : EdgeVector::const_iterator pfrom = std::find(myAll.begin(), myAll.end(), from);
163 865889 : while (*pfrom != to) {
164 666375 : NBContHelper::nextCCW(myAll, pfrom);
165 666375 : if ((*pfrom)->getToNode() == myJunction) {
166 233813 : EdgeVector::const_iterator pto = std::find(myAll.begin(), myAll.end(), to);
167 954332 : while (*pto != from) {
168 720519 : if (!((*pto)->getToNode() == myJunction)) {
169 479614 : setBlocking(from, to, *pfrom, *pto);
170 : }
171 720519 : NBContHelper::nextCCW(myAll, pto);
172 : }
173 : }
174 : }
175 199514 : }
176 :
177 :
178 : void
179 199514 : NBRequest::computeLeftOutgoingLinkCrossings(NBEdge* from, NBEdge* to) {
180 199514 : EdgeVector::const_iterator pfrom = std::find(myAll.begin(), myAll.end(), from);
181 865889 : while (*pfrom != to) {
182 666375 : NBContHelper::nextCW(myAll, pfrom);
183 666375 : if ((*pfrom)->getToNode() == myJunction) {
184 233813 : EdgeVector::const_iterator pto = std::find(myAll.begin(), myAll.end(), to);
185 954332 : while (*pto != from) {
186 720519 : if (!((*pto)->getToNode() == myJunction)) {
187 479614 : setBlocking(from, to, *pfrom, *pto);
188 : }
189 720519 : NBContHelper::nextCW(myAll, pto);
190 : }
191 : }
192 : }
193 199514 : }
194 :
195 :
196 : void
197 959228 : NBRequest::setBlocking(NBEdge* from1, NBEdge* to1,
198 : NBEdge* from2, NBEdge* to2) {
199 : // check whether one of the links has a dead end
200 959228 : if (to1 == nullptr || to2 == nullptr) {
201 959228 : return;
202 : }
203 : // get the indices of both links
204 959228 : int idx1 = getIndex(from1, to1);
205 959228 : int idx2 = getIndex(from2, to2);
206 959228 : if (idx1 < 0 || idx2 < 0) {
207 : return; // !!! error output? did not happend, yet
208 : }
209 : // check whether the link crossing has already been checked
210 : assert(idx1 < (int)(myIncoming.size() * myOutgoing.size()));
211 959228 : if (myDone[idx1][idx2]) {
212 : return;
213 : }
214 : // mark the crossings as done
215 : myDone[idx1][idx2] = true;
216 479524 : myDone[idx2][idx1] = true;
217 : // special case all-way stop
218 479524 : if (myJunction->getType() == SumoXMLNodeType::ALLWAY_STOP) {
219 : // all ways forbid each other. Conflict resolution happens via arrival time
220 : myForbids[idx1][idx2] = true;
221 : myForbids[idx2][idx1] = true;
222 40 : return;
223 : }
224 : // check if one of the links is a turn; this link is always not priorised
225 : // true for right-before-left and priority
226 479484 : if (from1->isTurningDirectionAt(to1)) {
227 : myForbids[idx2][idx1] = true;
228 60661 : return;
229 : }
230 418823 : if (from2->isTurningDirectionAt(to2)) {
231 : myForbids[idx1][idx2] = true;
232 57253 : return;
233 : }
234 : // if there are no connections, there are no prohibitions
235 361570 : if (from1->isConnectedTo(to1)) {
236 211455 : if (!from2->isConnectedTo(to2)) {
237 : myForbids[idx1][idx2] = true;
238 : myForbids[idx2][idx1] = false;
239 26225 : return;
240 : }
241 : } else {
242 150115 : if (!from2->isConnectedTo(to2)) {
243 : myForbids[idx1][idx2] = false;
244 : myForbids[idx2][idx1] = false;
245 122701 : return;
246 : } else {
247 : myForbids[idx1][idx2] = false;
248 : myForbids[idx2][idx1] = true;
249 27414 : return;
250 : }
251 : }
252 : #ifdef DEBUG_SETBLOCKING
253 : if (DEBUGCOND) std::cout << "setBlocking type=" << toString(myJunction->getType())
254 : << " bentPrio=" << myJunction->isBentPriority()
255 : << " 1:" << from1->getID() << "->" << to1->getID()
256 : << " 2:" << from2->getID() << "->" << to2->getID() << "\n";
257 : #endif
258 : // check the priorities if required by node type
259 185230 : const bool typeEqual = myJunction->getType() == SumoXMLNodeType::RIGHT_BEFORE_LEFT || myJunction->getType() == SumoXMLNodeType::LEFT_BEFORE_RIGHT;
260 : if (!typeEqual) {
261 166023 : int from1p = from1->getJunctionPriority(myJunction);
262 166023 : int from2p = from2->getJunctionPriority(myJunction);
263 : #ifdef DEBUG_SETBLOCKING
264 : if (DEBUGCOND) {
265 : std::cout << " p1=" << from1p << " p2=" << from2p << "\n";
266 : }
267 : #endif
268 : // check if one of the connections is higher priorised when incoming into
269 : // the junction, the connection road will yield
270 166023 : if (from1p > from2p) {
271 : myForbids[idx1][idx2] = true;
272 60362 : return;
273 : }
274 105661 : if (from2p > from1p) {
275 : myForbids[idx2][idx1] = true;
276 48082 : return;
277 : }
278 : }
279 : // straight connections prohibit turning connections if the priorities are equal
280 : // (unless the junction is a bent priority junction)
281 76786 : if (!typeEqual && !myJunction->isBentPriority()) {
282 41645 : LinkDirection ld1 = myJunction->getDirection(from1, to1);
283 41645 : LinkDirection ld2 = myJunction->getDirection(from2, to2);
284 : #ifdef DEBUG_SETBLOCKING
285 : if (DEBUGCOND) std::cout << "setBlocking"
286 : << " 1:" << from1->getID() << "->" << to1->getID()
287 : << " 2:" << from2->getID() << "->" << to2->getID()
288 : << " dir1=" << toString(ld1) << " dir2=" << toString(ld2) << "\n";
289 : #endif
290 41645 : if (ld1 == LinkDirection::STRAIGHT) {
291 10434 : if (ld2 != LinkDirection::STRAIGHT) {
292 : myForbids[idx1][idx2] = true;
293 : myForbids[idx2][idx1] = false;
294 9655 : return;
295 : }
296 : } else {
297 31211 : if (ld2 == LinkDirection::STRAIGHT) {
298 : myForbids[idx1][idx2] = false;
299 : myForbids[idx2][idx1] = true;
300 10048 : return;
301 : }
302 : }
303 : }
304 :
305 : // check whether one of the connections is higher priorised on
306 : // the outgoing edge when both roads are high priorised
307 : // the connection with the lower priorised outgoing edge will lead
308 : // should be valid for priority junctions only
309 : /*
310 : if (from1p > 0 && from2p > 0) {
311 : assert(myJunction->getType() != SumoXMLNodeType::RIGHT_BEFORE_LEFT);
312 : int to1p = to1->getJunctionPriority(myJunction);
313 : int to2p = to2->getJunctionPriority(myJunction);
314 : if (to1p > to2p) {
315 : myForbids[idx1][idx2] = true;
316 : return;
317 : }
318 : if (to2p > to1p) {
319 : myForbids[idx2][idx1] = true;
320 : return;
321 : }
322 : }
323 : */
324 :
325 : // compute the yielding due to the right-before-left rule
326 : // (or left-before-right rule)
327 : // get the position of the incoming lanes in the junction-wheel
328 57083 : EdgeVector::const_iterator c1 = std::find(myAll.begin(), myAll.end(), from1);
329 57083 : NBContHelper::nextCW(myAll, c1);
330 : // go through next edges clockwise...
331 170122 : while (*c1 != from1 && *c1 != from2) {
332 133791 : if (*c1 == to2) {
333 : // if we encounter to2 the second one prohibits the first
334 20752 : if (myJunction->getType() == SumoXMLNodeType::LEFT_BEFORE_RIGHT) {
335 : myForbids[idx1][idx2] = true;
336 : } else {
337 : myForbids[idx2][idx1] = true;
338 : }
339 : #ifdef DEBUG_SETBLOCKING
340 : if (DEBUGCOND) std::cout << "setBlocking"
341 : << " 1:" << from1->getID() << "->" << to1->getID()
342 : << " 2:" << from2->getID() << "->" << to2->getID()
343 : << " 1 yields\n";
344 : #endif
345 20752 : return;
346 : }
347 113039 : NBContHelper::nextCW(myAll, c1);
348 : }
349 : // get the position of the incoming lanes in the junction-wheel
350 36331 : EdgeVector::const_iterator c2 = std::find(myAll.begin(), myAll.end(), from2);
351 36331 : NBContHelper::nextCW(myAll, c2);
352 : // go through next edges clockwise...
353 113056 : while (*c2 != from2 && *c2 != from1) {
354 113056 : if (*c2 == to1) {
355 : // if we encounter to1 the second one prohibits the first
356 36331 : if (myJunction->getType() == SumoXMLNodeType::LEFT_BEFORE_RIGHT) {
357 : myForbids[idx2][idx1] = true;
358 : } else {
359 : myForbids[idx1][idx2] = true;
360 : }
361 : #ifdef DEBUG_SETBLOCKING
362 : if (DEBUGCOND) std::cout << "setBlocking"
363 : << " 1:" << from1->getID() << "->" << to1->getID()
364 : << " 2:" << from2->getID() << "->" << to2->getID()
365 : << " 2 yields\n";
366 : #endif
367 36331 : return;
368 : }
369 76725 : NBContHelper::nextCW(myAll, c2);
370 : }
371 : #ifdef DEBUG_SETBLOCKING
372 : if (DEBUGCOND) std::cout << "setBlocking"
373 : << " 1:" << from1->getID() << "->" << to1->getID()
374 : << " 2:" << from2->getID() << "->" << to2->getID()
375 : << " noDecision\n";
376 : #endif
377 : }
378 :
379 :
380 : int
381 0 : NBRequest::distanceCounterClockwise(NBEdge* from, NBEdge* to) {
382 0 : EdgeVector::const_iterator p = std::find(myAll.begin(), myAll.end(), from);
383 : int ret = 0;
384 : do {
385 0 : ret++;
386 0 : if (p == myAll.begin()) {
387 : p = myAll.end();
388 : }
389 : p--;
390 0 : } while (*p != to);
391 0 : return ret;
392 : }
393 :
394 : const std::string&
395 0 : NBRequest::getFoes(int linkIndex) const {
396 : assert(linkIndex >= 0);
397 : assert(linkIndex < (int)myFoes.size());
398 0 : return myFoes[linkIndex];
399 : }
400 :
401 :
402 : const std::string&
403 182591 : NBRequest::getResponse(int linkIndex) const {
404 : assert(linkIndex >= 0);
405 : assert(linkIndex < (int)myResponse.size());
406 182591 : return myResponse[linkIndex];
407 : }
408 :
409 :
410 : void
411 35632 : NBRequest::writeLogic(OutputDevice& into) const {
412 35632 : int numLinks = (int)myResponse.size();
413 : assert((int)myFoes.size() == numLinks);
414 : assert((int)myHaveVia.size() == numLinks);
415 : const bool padding = numLinks > 10;
416 211674 : for (int i = 0; i < numLinks; i++) {
417 176042 : into.openTag(SUMO_TAG_REQUEST);
418 : into.writeAttr(SUMO_ATTR_INDEX, i);
419 176042 : if (padding && i < 10) {
420 91160 : into.writePadding(" ");
421 : }
422 176042 : into.writeAttr(SUMO_ATTR_RESPONSE, myResponse[i]);
423 : into.writeAttr(SUMO_ATTR_FOES, myFoes[i]);
424 352084 : if (!OptionsCont::getOptions().getBool("no-internal-links")) {
425 184534 : into.writeAttr(SUMO_ATTR_CONT, myHaveVia[i]);
426 : }
427 352084 : into.closeTag();
428 : }
429 35632 : }
430 :
431 :
432 : void
433 36605 : NBRequest::computeLogic(const bool checkLaneFoes) {
434 : myResponse.clear();
435 : myFoes.clear();
436 : myHaveVia.clear();
437 : int pos = 0;
438 : EdgeVector::const_iterator i;
439 : // normal connections
440 112556 : for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
441 75951 : int noLanes = (*i)->getNumLanes();
442 176861 : for (int k = 0; k < noLanes; k++) {
443 102201 : pos = computeLaneResponse(*i, k, pos, checkLaneFoes || myJunction->getType() == SumoXMLNodeType::ZIPPER);
444 : }
445 : }
446 : // crossings
447 36605 : auto crossings = myJunction->getCrossings();
448 38192 : for (auto c : crossings) {
449 1587 : pos = computeCrossingResponse(*c, pos);
450 : }
451 36605 : }
452 :
453 : void
454 36605 : NBRequest::resetSignalised() {
455 : // go through possible prohibitions
456 112556 : for (EdgeVector::const_iterator i11 = myIncoming.begin(); i11 != myIncoming.end(); i11++) {
457 75951 : int noLanesEdge1 = (*i11)->getNumLanes();
458 176861 : for (int j1 = 0; j1 < noLanesEdge1; j1++) {
459 100910 : std::vector<NBEdge::Connection> el1 = (*i11)->getConnectionsFromLane(j1);
460 282083 : for (std::vector<NBEdge::Connection>::iterator i12 = el1.begin(); i12 != el1.end(); ++i12) {
461 181173 : int idx1 = getIndex((*i11), (*i12).toEdge);
462 181173 : if (idx1 < 0) {
463 0 : continue;
464 : }
465 : // go through possibly prohibited
466 742545 : for (EdgeVector::const_iterator i21 = myIncoming.begin(); i21 != myIncoming.end(); i21++) {
467 561372 : int noLanesEdge2 = (*i21)->getNumLanes();
468 1359515 : for (int j2 = 0; j2 < noLanesEdge2; j2++) {
469 798143 : std::vector<NBEdge::Connection> el2 = (*i21)->getConnectionsFromLane(j2);
470 2730044 : for (std::vector<NBEdge::Connection>::iterator i22 = el2.begin(); i22 != el2.end(); i22++) {
471 1931901 : int idx2 = getIndex((*i21), (*i22).toEdge);
472 1931901 : if (idx2 < 0) {
473 0 : continue;
474 : }
475 : // check
476 : // same incoming connections do not prohibit each other
477 1931901 : if ((*i11) == (*i21)) {
478 581079 : myForbids[idx1][idx2] = false;
479 581079 : myForbids[idx2][idx1] = false;
480 : #ifdef DEBUG_SETBLOCKING
481 : if (DEBUGCOND) std::cout << "resetSignalised both"
482 : << " 1:" << (*i11)->getID() << "->" << (*i12).toEdge->getID()
483 : << " 2:" << (*i21)->getID() << "->" << (*i22).toEdge->getID()
484 : << "\n";
485 : #endif
486 581079 : continue;
487 : }
488 : // check other
489 : // if both are non-signalised or both are signalised
490 1133480 : if (((*i12).tlID == "" && (*i22).tlID == "")
491 1351848 : ||
492 217342 : ((*i12).tlID != "" && (*i22).tlID != "")) {
493 : // do nothing
494 1348770 : continue;
495 : }
496 : // supposing, we don not have to
497 : // brake if we are no foes
498 2052 : if (!foes(*i11, (*i12).toEdge, *i21, (*i22).toEdge)) {
499 1560 : continue;
500 : }
501 : // otherwise:
502 : // the non-signalised must break
503 492 : if ((*i12).tlID != "") {
504 246 : myForbids[idx1][idx2] = true;
505 246 : myForbids[idx2][idx1] = false;
506 : #ifdef DEBUG_SETBLOCKING
507 : if (DEBUGCOND) std::cout << "resetSignalised:2 yields"
508 : << " 1:" << (*i11)->getID() << "->" << (*i12).toEdge->getID()
509 : << " 2:" << (*i21)->getID() << "->" << (*i22).toEdge->getID() << "\n";
510 : #endif
511 : } else {
512 246 : myForbids[idx1][idx2] = false;
513 246 : myForbids[idx2][idx1] = true;
514 : #ifdef DEBUG_SETBLOCKING
515 : if (DEBUGCOND) std::cout << "resetSignalised:1 yields"
516 : << " 1:" << (*i11)->getID() << "->" << (*i12).toEdge->getID()
517 : << " 2:" << (*i21)->getID() << "->" << (*i22).toEdge->getID() << "\n";
518 : #endif
519 : }
520 : }
521 798143 : }
522 : }
523 : }
524 100910 : }
525 : }
526 36605 : }
527 :
528 :
529 : std::pair<int, int>
530 43278 : NBRequest::getSizes() const {
531 : int numLanes = 0;
532 : int numLinks = 0;
533 129861 : for (const NBEdge* const e : myIncoming) {
534 : const int numLanesEdge = e->getNumLanes();
535 199911 : for (int j = 0; j < numLanesEdge; j++) {
536 113328 : int numConnections = (int)e->getConnectionsFromLane(j).size();
537 113328 : numLinks += numConnections;
538 113328 : if (numConnections > 0) {
539 93819 : numLanes++;
540 : }
541 : }
542 : }
543 43278 : return std::make_pair(numLanes, numLinks);
544 : }
545 :
546 :
547 : bool
548 3417960 : NBRequest::foes(const NBEdge* const from1, const NBEdge* const to1,
549 : const NBEdge* const from2, const NBEdge* const to2) const {
550 : // unconnected edges do not forbid other edges
551 3417960 : if (to1 == nullptr || to2 == nullptr) {
552 : return false;
553 : }
554 : // get the indices
555 3417960 : int idx1 = getIndex(from1, to1);
556 3417960 : int idx2 = getIndex(from2, to2);
557 3417960 : if (idx1 < 0 || idx2 < 0) {
558 : return false; // sure? (The connection does not exist within this junction)
559 : }
560 : assert(idx1 < (int)(myIncoming.size() * myOutgoing.size()));
561 : assert(idx2 < (int)(myIncoming.size()*myOutgoing.size()));
562 3288075 : return myForbids[idx1][idx2] || myForbids[idx2][idx1];
563 : }
564 :
565 :
566 : bool
567 1368981 : NBRequest::forbids(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
568 : const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo,
569 : bool regardNonSignalisedLowerPriority) const {
570 : // unconnected edges do not forbid other edges
571 1368981 : if (possProhibitorTo == nullptr || possProhibitedTo == nullptr) {
572 : return false;
573 : }
574 : // get the indices
575 1368981 : int possProhibitorIdx = getIndex(possProhibitorFrom, possProhibitorTo);
576 1368981 : int possProhibitedIdx = getIndex(possProhibitedFrom, possProhibitedTo);
577 1368981 : if (possProhibitorIdx < 0 || possProhibitedIdx < 0) {
578 : return false; // sure? (The connection does not exist within this junction)
579 : }
580 : assert(possProhibitorIdx < (int)(myIncoming.size() * myOutgoing.size()));
581 : assert(possProhibitedIdx < (int)(myIncoming.size() * myOutgoing.size()));
582 : // check simple right-of-way-rules
583 1368981 : if (!regardNonSignalisedLowerPriority) {
584 587005 : return myForbids[possProhibitorIdx][possProhibitedIdx];
585 : }
586 : // if its not forbidden, report
587 781976 : if (!myForbids[possProhibitorIdx][possProhibitedIdx]) {
588 : return false;
589 : }
590 : // do not forbid a signalised stream by a non-signalised
591 144297 : if (!possProhibitorFrom->hasSignalisedConnectionTo(possProhibitorTo)) {
592 : return false;
593 : }
594 : return true;
595 : }
596 :
597 : int
598 100910 : NBRequest::computeLaneResponse(NBEdge* from, int fromLane, int pos, const bool checkLaneFoes) {
599 282083 : for (const NBEdge::Connection& c : from->getConnectionsFromLane(fromLane)) {
600 : assert(c.toEdge != 0);
601 181173 : pos++;
602 181173 : const std::string foes = getFoesString(from, c.toEdge, fromLane, c.toLane, checkLaneFoes);
603 181173 : const std::string response = getResponseString(from, c, checkLaneFoes);
604 181173 : myFoes.push_back(foes);
605 181173 : myResponse.push_back(response);
606 181173 : myHaveVia.push_back(c.haveVia);
607 100910 : }
608 100910 : return pos;
609 : }
610 :
611 :
612 : int
613 1587 : NBRequest::computeCrossingResponse(const NBNode::Crossing& crossing, int pos) {
614 3174 : std::string foes(myJunction->getCrossings().size(), '0');
615 3174 : std::string response(myJunction->getCrossings().size(), '0');
616 : // conflicts with normal connections
617 7746 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
618 6159 : const NBEdge* from = *i;
619 20138 : for (int j = from->getNumLanes(); j-- > 0;) {
620 13979 : const std::vector<NBEdge::Connection>& connected = from->getConnectionsFromLane(j);
621 13979 : const int size = (int) connected.size();
622 31829 : for (int k = size; k-- > 0;) {
623 17850 : const NBEdge* to = connected[k].toEdge;
624 : bool foe = false;
625 37344 : for (const NBEdge* const e : crossing.edges) {
626 27410 : if (e == from || e == to) {
627 : foe = true;
628 : break;
629 : }
630 : }
631 17850 : foes += foe ? '1' : '0';
632 17850 : response += mustBrakeForCrossing(myJunction, from, to, crossing) || !foe ? '0' : '1';
633 : }
634 13979 : }
635 : }
636 1587 : pos++;
637 1587 : myResponse.push_back(response);
638 1587 : myFoes.push_back(foes);
639 1587 : myHaveVia.push_back(false);
640 1587 : return pos;
641 : }
642 :
643 :
644 : std::string
645 181173 : NBRequest::getResponseString(const NBEdge* const from, const NBEdge::Connection& c, const bool checkLaneFoes) const {
646 181173 : const NBEdge* const to = c.toEdge;
647 181173 : const int fromLane = c.fromLane;
648 181173 : const int toLane = c.toLane;
649 : int idx = 0;
650 181173 : if (to != nullptr) {
651 181173 : idx = getIndex(from, to);
652 : }
653 : std::string result;
654 181173 : const bool zipper = myJunction->getType() == SumoXMLNodeType::ZIPPER;
655 : // crossings
656 181173 : auto crossings = myJunction->getCrossings();
657 199023 : for (std::vector<NBNode::Crossing*>::const_reverse_iterator i = crossings.rbegin(); i != crossings.rend(); i++) {
658 17850 : result += mustBrakeForCrossing(myJunction, from, to, **i) ? '1' : '0';
659 : }
660 181173 : const NBEdge::Connection& queryCon = from->getConnection(fromLane, to, toLane);
661 : // normal connections
662 742545 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
663 : //const std::vector<NBEdge::Connection> &allConnections = (*i)->getConnections();
664 561372 : int noLanes = (*i)->getNumLanes();
665 1359515 : for (int j = noLanes; j-- > 0;) {
666 798143 : std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
667 798143 : int size = (int) connected.size();
668 2730044 : for (int k = size; k-- > 0;) {
669 1931901 : if (c.mayDefinitelyPass) {
670 : result += '0';
671 : #ifdef DEBUG_RESPONSE
672 : if (DEBUGCOND) {
673 : std::cout << " c=" << queryCon.getDescription(from) << " pass\n";
674 : }
675 : #endif
676 1931780 : } else if ((*i) == from && fromLane == j) {
677 : // do not prohibit a connection by others from same lane
678 : // except for indirect turns
679 : #ifdef DEBUG_RESPONSE
680 : if (DEBUGCOND) {
681 : std::cout << " c=" << queryCon.getDescription(from) << " prohibitC=" << connected[k].getDescription(*i)
682 : << " itc=" << indirectLeftTurnConflict(from, queryCon, *i, connected[k], false)
683 : << "\n";
684 : }
685 : #endif
686 467666 : if (indirectLeftTurnConflict(from, queryCon, *i, connected[k], false)) {
687 : result += '1';
688 : } else {
689 : result += '0';
690 : }
691 : } else {
692 : assert(connected[k].toEdge != 0);
693 1464114 : const int idx2 = getIndex(*i, connected[k].toEdge);
694 : assert(k < (int) connected.size());
695 : assert(idx < (int)(myIncoming.size() * myOutgoing.size()));
696 : assert(idx2 < (int)(myIncoming.size() * myOutgoing.size()));
697 : // check whether the connection is prohibited by another one
698 : #ifdef DEBUG_RESPONSE
699 : if (DEBUGCOND) {
700 : std::cout << " c=" << queryCon.getDescription(from) << " prohibitC=" << connected[k].getDescription(*i)
701 : << " idx=" << idx << " idx2=" << idx2
702 : << " f=" << myForbids[idx2][idx]
703 : << " clf=" << checkLaneFoes
704 : << " clfbc=" << checkLaneFoesByClass(queryCon, *i, connected[k])
705 : << " clfbcoop=" << checkLaneFoesByCooperation(from, queryCon, *i, connected[k])
706 : << " lc=" << laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane)
707 : << " rtc=" << NBNode::rightTurnConflict(from, to, fromLane, *i, connected[k].toEdge, connected[k].fromLane)
708 : << " rtc2=" << rightTurnConflict(from, queryCon, *i, connected[k])
709 : << " mc=" << mergeConflict(from, queryCon, *i, connected[k], false)
710 : << " oltc=" << oppositeLeftTurnConflict(from, queryCon, *i, connected[k], false)
711 : << " itc=" << indirectLeftTurnConflict(from, queryCon, *i, connected[k], zipper)
712 : << " bc=" << bidiConflict(from, queryCon, *i, connected[k], false)
713 : << " rorc=" << myJunction->rightOnRedConflict(c.tlLinkIndex, connected[k].tlLinkIndex)
714 : << " tlscc=" << myJunction->tlsContConflict(from, c, *i, connected[k])
715 : << "\n";
716 : }
717 : #endif
718 2889360 : const bool hasLaneConflict = (!(checkLaneFoes || checkLaneFoesByClass(queryCon, *i, connected[k])
719 1432516 : || checkLaneFoesByCooperation(from, queryCon, *i, connected[k]))
720 1503717 : || laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane));
721 2928228 : if (((myForbids[idx2][idx] || (zipper && myForbids[idx][idx2])) && hasLaneConflict && !bidiConflict(*i, connected[k], from, queryCon, false))
722 1168102 : || rightTurnConflict(from, queryCon, *i, connected[k])
723 1167514 : || mergeConflict(from, queryCon, *i, connected[k], zipper)
724 1167330 : || oppositeLeftTurnConflict(from, queryCon, *i, connected[k], zipper)
725 1164675 : || indirectLeftTurnConflict(from, queryCon, *i, connected[k], zipper)
726 1164675 : || bidiConflict(from, queryCon, *i, connected[k], false)
727 1164661 : || myJunction->rightOnRedConflict(c.tlLinkIndex, connected[k].tlLinkIndex)
728 2628745 : || (myJunction->tlsContConflict(from, c, *i, connected[k]) && hasLaneConflict
729 1478934 : && !OptionsCont::getOptions().getBool("tls.ignore-internal-junction-jam"))
730 : ) {
731 : result += '1';
732 : } else {
733 : result += '0';
734 : }
735 : }
736 : }
737 798143 : }
738 : }
739 181173 : return result;
740 181173 : }
741 :
742 :
743 : std::string
744 181173 : NBRequest::getFoesString(NBEdge* from, NBEdge* to, int fromLane, int toLane, const bool checkLaneFoes) const {
745 362346 : const bool lefthand = OptionsCont::getOptions().getBool("lefthand");
746 : // remember the case when the lane is a "dead end" in the meaning that
747 : // vehicles must choose another lane to move over the following
748 : // junction
749 : // !!! move to forbidden
750 : std::string result;
751 : // crossings
752 181173 : auto crossings = myJunction->getCrossings();
753 199023 : for (std::vector<NBNode::Crossing*>::const_reverse_iterator i = crossings.rbegin(); i != crossings.rend(); i++) {
754 : bool foes = false;
755 37344 : for (EdgeVector::const_iterator it_e = (**i).edges.begin(); it_e != (**i).edges.end(); ++it_e) {
756 27410 : if ((*it_e) == from || (*it_e) == to) {
757 : foes = true;
758 : break;
759 : }
760 : }
761 17850 : result += foes ? '1' : '0';
762 : }
763 181173 : const NBEdge::Connection& queryCon = from->getConnection(fromLane, to, toLane);
764 : // normal connections
765 742545 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
766 1359515 : for (int j = (*i)->getNumLanes() - 1; j >= 0; --j) {
767 798143 : const std::vector<NBEdge::Connection>& connected = (*i)->getConnectionsFromLane(j);
768 798143 : int size = (int) connected.size();
769 2730044 : for (int k = size; k-- > 0;) {
770 3811255 : const bool hasLaneConflict = (!(checkLaneFoes || checkLaneFoesByClass(queryCon, *i, connected[k])
771 1889243 : || checkLaneFoesByCooperation(from, queryCon, *i, connected[k]))
772 1979971 : || laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane));
773 2543953 : if ((foes(from, to, (*i), connected[k].toEdge) && hasLaneConflict)
774 1340029 : || rightTurnConflict(from, queryCon, *i, connected[k])
775 1339441 : || myJunction->turnFoes(from, to, fromLane, *i, connected[k].toEdge, connected[k].fromLane, lefthand)
776 1338789 : || mergeConflict(from, queryCon, *i, connected[k], true)
777 1338431 : || oppositeLeftTurnConflict(from, queryCon, *i, connected[k], true)
778 1333123 : || indirectLeftTurnConflict(from, queryCon, *i, connected[k], true)
779 3265002 : || bidiConflict(from, queryCon, *i, connected[k], true)
780 : ) {
781 : result += '1';
782 : } else {
783 : result += '0';
784 : }
785 : }
786 798143 : }
787 : }
788 181173 : return result;
789 181173 : }
790 :
791 :
792 : bool
793 2508694 : NBRequest::rightTurnConflict(const NBEdge* from, const NBEdge::Connection& con,
794 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon) const {
795 5017273 : return (!con.mayDefinitelyPass &&
796 2508579 : (NBNode::rightTurnConflict(from, con.toEdge, con.fromLane, prohibitorFrom, prohibitorCon.toEdge, prohibitorCon.fromLane)
797 : // reverse conflicht (override)
798 2507366 : || (prohibitorCon.mayDefinitelyPass &&
799 72 : NBNode::rightTurnConflict(prohibitorFrom, prohibitorCon.toEdge, prohibitorCon.fromLane, from, con.toEdge, con.fromLane))));
800 :
801 :
802 : }
803 :
804 :
805 : bool
806 3978137 : NBRequest::mergeConflict(const NBEdge* from, const NBEdge::Connection& con,
807 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
808 : if (from == prohibitorFrom
809 1116284 : && con.toEdge == prohibitorCon.toEdge
810 4388593 : && ((con.toLane == prohibitorCon.toLane
811 303239 : && con.fromLane != prohibitorCon.fromLane
812 1324 : && !myJunction->isConstantWidthTransition())
813 : // this is actually a crossing rather than a merger
814 409136 : || (con.fromLane > prohibitorCon.fromLane && con.toLane < prohibitorCon.toLane)
815 409126 : || (con.fromLane < prohibitorCon.fromLane && con.toLane > prohibitorCon.toLane))) {
816 1340 : if (foes) {
817 : return true;
818 : }
819 808 : if (prohibitorCon.mayDefinitelyPass) {
820 : return true;
821 : }
822 805 : if (con.mayDefinitelyPass) {
823 : return false;
824 : }
825 805 : const bool bike = from->getPermissions(con.fromLane) == SVC_BICYCLE;
826 805 : const bool prohibitorBike = prohibitorFrom->getPermissions(prohibitorCon.fromLane) == SVC_BICYCLE;
827 805 : if (myOutgoing.size() == 1) {
828 : // at on-ramp like situations, right lane should yield
829 45 : return bike || (con.fromLane < prohibitorCon.fromLane && !prohibitorBike);
830 : } else {
831 : // priority depends on direction:
832 : // for right turns the rightmost lane gets priority
833 : // otherwise the left lane
834 775 : LinkDirection dir = myJunction->getDirection(from, con.toEdge);
835 775 : if (dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT) {
836 491 : return con.fromLane > prohibitorCon.fromLane;
837 : } else {
838 284 : if (myIncoming.size() == 1) {
839 : // at off-ramp like situations, right lane should pass unless it's a bicycle lane
840 6 : return bike || (con.fromLane > prohibitorCon.fromLane && !prohibitorBike);
841 : } else {
842 280 : return con.fromLane < prohibitorCon.fromLane;
843 : }
844 : }
845 : }
846 :
847 : } else {
848 3976797 : return false;
849 : }
850 : }
851 :
852 :
853 : bool
854 2505761 : NBRequest::oppositeLeftTurnConflict(const NBEdge* from, const NBEdge::Connection& con,
855 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
856 2505761 : LinkDirection dir = myJunction->getDirection(from, con.toEdge);
857 : // XXX lefthand issue (solve via #4256)
858 2505761 : if (dir != LinkDirection::LEFT && dir != LinkDirection::PARTLEFT) {
859 : return false;
860 : }
861 491587 : dir = myJunction->getDirection(prohibitorFrom, prohibitorCon.toEdge);
862 491587 : if (dir != LinkDirection::LEFT && dir != LinkDirection::PARTLEFT) {
863 : return false;
864 : }
865 128668 : if (from == prohibitorFrom || NBRequest::foes(from, con.toEdge, prohibitorFrom, prohibitorCon.toEdge)) {
866 : // not an opposite pair
867 75112 : return false;
868 : }
869 :
870 53556 : const double width1 = MIN2(from->getLaneWidth(con.fromLane) / 2, OptionsCont::getOptions().getFloat("internal-junctions.vehicle-width") / 2);
871 53556 : const double width2 = prohibitorCon.toEdge->getLaneWidth(prohibitorCon.toLane) / 2;
872 : PositionVector shape = con.shape;
873 53556 : shape.append(con.viaShape);
874 : PositionVector otherShape = prohibitorCon.shape;
875 53556 : otherShape.append(prohibitorCon.viaShape);
876 53556 : if (shape.size() == 0 || otherShape.size() == 0) {
877 : // no internal lanes built
878 : return false;
879 : }
880 21744 : const double minDV = NBEdge::firstIntersection(shape, otherShape, width1, width2);
881 21744 : if (minDV < shape.length() - POSITION_EPS && minDV > POSITION_EPS) {
882 : // break symmetry using edge id
883 10616 : return foes || from->getID() < prohibitorFrom->getID();
884 : }
885 : return false;
886 53556 : }
887 :
888 : bool
889 3399534 : NBRequest::indirectLeftTurnConflict(const NBEdge* from, const NBEdge::Connection& con,
890 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
891 3399534 : if (from == prohibitorFrom) {
892 1282726 : if (con.toEdge == prohibitorCon.toEdge) {
893 : return false;
894 778645 : } else if (con.indirectLeft) {
895 126 : LinkDirection dir = myJunction->getDirection(prohibitorFrom, prohibitorCon.toEdge);
896 126 : return (dir == LinkDirection::STRAIGHT);
897 778519 : } else if (foes && prohibitorCon.indirectLeft) {
898 27 : LinkDirection dir = myJunction->getDirection(from, con.toEdge);
899 27 : return (dir == LinkDirection::STRAIGHT);
900 : }
901 : }
902 : return false;
903 : }
904 :
905 : bool
906 3527755 : NBRequest::bidiConflict(const NBEdge* from, const NBEdge::Connection& con,
907 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
908 3527755 : if (from == prohibitorFrom) {
909 : return false;
910 : }
911 2625833 : if (isRailway(from->getPermissions())) {
912 : // railways manage right-of-way via signals
913 : return false;
914 : }
915 1268349 : if ((foes && (from->getBidiEdge() == prohibitorCon.toEdge))
916 3870097 : || prohibitorFrom->getBidiEdge() == con.toEdge) {
917 1102 : const bool fromBidi = from->getLaneShape(con.fromLane).reverse().almostSame(
918 551 : prohibitorCon.toEdge->getLaneShape(prohibitorCon.toLane), POSITION_EPS);
919 1102 : const bool prohibitorFromBidi = prohibitorFrom->getLaneShape(prohibitorCon.fromLane).reverse().almostSame(
920 551 : con.toEdge->getLaneShape(con.toLane), POSITION_EPS);
921 551 : if (!foes && fromBidi && prohibitorFromBidi) {
922 : // do not create a symmetrical conflict
923 : return false;
924 : }
925 530 : if (prohibitorFromBidi &&
926 661 : prohibitorFrom->getLaneShape(prohibitorCon.fromLane).reverse().almostSame(
927 131 : prohibitorCon.toEdge->getLaneShape(prohibitorCon.toLane), POSITION_EPS)) {
928 : // prohibitor has a bidi-turnaround
929 : return false;
930 : }
931 :
932 475 : return fromBidi || prohibitorFromBidi;
933 : }
934 : return false;
935 : }
936 :
937 : bool
938 3378856 : NBRequest::checkLaneFoesByClass(const NBEdge::Connection& con,
939 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon) const {
940 3378856 : if (con.toEdge != prohibitorCon.toEdge) {
941 : return false;
942 : }
943 966326 : SVCPermissions svc = con.toEdge->getPermissions(con.toLane);
944 966326 : SVCPermissions svc2 = prohibitorFrom->getPermissions(prohibitorCon.fromLane) & prohibitorCon.toEdge->getPermissions(prohibitorCon.toLane);
945 : // check for lane level conflict if the only common classes are bicycles or pedestrians
946 966326 : return ((svc & svc2 & ~(SVC_BICYCLE | SVC_PEDESTRIAN)) == 0
947 : // or if the connection is to a dedicated lane whereas the prohibitor is a "general" lane
948 966326 : || (((svc & SVC_PASSENGER) == 0) && ((svc2 & SVC_PASSENGER) != 0)));
949 : }
950 :
951 :
952 : bool
953 3321759 : NBRequest::checkLaneFoesByCooperation(const NBEdge* from, const NBEdge::Connection& con,
954 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon) const {
955 3321759 : if (con.toEdge != prohibitorCon.toEdge) {
956 : return false;
957 : }
958 : // if from and prohibitorFrom target distinct lanes for all their
959 : // connections to the common target edge, cooperation is possible
960 : // (and should always happen unless the connections cross for some byzantine reason)
961 :
962 : std::set<int> fromTargetLanes;
963 4452432 : for (const NBEdge::Connection& c : from->getConnections()) {
964 3543203 : if (c.toEdge == con.toEdge) {
965 1327996 : fromTargetLanes.insert(c.toLane);
966 : }
967 : }
968 2163449 : for (const NBEdge::Connection& c : prohibitorFrom->getConnections()) {
969 2132873 : if (c.toEdge == con.toEdge && fromTargetLanes.count(c.toLane) != 0) {
970 : //std::cout << " con=" << con->getDescription(from) << " foe=" << prohibitorCon.getDescription(prohibitorFrom)
971 : // << " no cooperation (targets=" << joinToString(fromTargetLanes, ' ') << " index=" << c.toLane << "\n";
972 : return false;
973 : }
974 : }
975 : return true;
976 : }
977 :
978 :
979 : bool
980 104832 : NBRequest::laneConflict(const NBEdge* from, const NBEdge* to, int toLane,
981 : const NBEdge* prohibitorFrom, const NBEdge* prohibitorTo, int prohibitorToLane) const {
982 104832 : if (to != prohibitorTo) {
983 : return true;
984 : }
985 : // since we know that the edge2edge connections are in conflict, the only
986 : // situation in which the lane2lane connections can be conflict-free is, if
987 : // they target the same edge but do not cross each other
988 96397 : double angle = NBHelpers::relAngle(
989 : from->getAngleAtNode(from->getToNode()), to->getAngleAtNode(to->getFromNode()));
990 96397 : if (angle == 180) {
991 : angle = -180; // turnarounds are left turns
992 : }
993 96397 : const double prohibitorAngle = NBHelpers::relAngle(
994 : prohibitorFrom->getAngleAtNode(prohibitorFrom->getToNode()), to->getAngleAtNode(to->getFromNode()));
995 96397 : const bool rightOfProhibitor = prohibitorFrom->isTurningDirectionAt(to)
996 96397 : || (angle > prohibitorAngle && !from->isTurningDirectionAt(to));
997 96397 : return rightOfProhibitor ? toLane >= prohibitorToLane : toLane <= prohibitorToLane;
998 : }
999 :
1000 : int
1001 15420652 : NBRequest::getIndex(const NBEdge* const from, const NBEdge* const to) const {
1002 15420652 : EdgeVector::const_iterator fp = std::find(myIncoming.begin(), myIncoming.end(), from);
1003 15420652 : EdgeVector::const_iterator tp = std::find(myOutgoing.begin(), myOutgoing.end(), to);
1004 15420652 : if (fp == myIncoming.end() || tp == myOutgoing.end()) {
1005 : return -1;
1006 : }
1007 : // compute the index
1008 15290767 : return (int)(distance(myIncoming.begin(), fp) * myOutgoing.size() + distance(myOutgoing.begin(), tp));
1009 : }
1010 :
1011 :
1012 : std::ostream&
1013 0 : operator<<(std::ostream& os, const NBRequest& r) {
1014 0 : int variations = r.numLinks();
1015 0 : for (int i = 0; i < variations; i++) {
1016 0 : os << i << ' ';
1017 0 : for (int j = 0; j < variations; j++) {
1018 0 : if (r.myForbids[i][j]) {
1019 0 : os << '1';
1020 : } else {
1021 0 : os << '0';
1022 : }
1023 : }
1024 : os << std::endl;
1025 : }
1026 : os << std::endl;
1027 0 : return os;
1028 : }
1029 :
1030 :
1031 : bool
1032 204466 : NBRequest::mustBrake(const NBEdge* const from, const NBEdge* const to, int fromLane, int toLane, bool includePedCrossings) const {
1033 204466 : NBEdge::Connection con(fromLane, const_cast<NBEdge*>(to), toLane);
1034 204466 : const int linkIndex = myJunction->getConnectionIndex(from, con);
1035 204466 : if (linkIndex >= 0 && (int)myResponse.size() > linkIndex) {
1036 182591 : std::string response = getResponse(linkIndex);
1037 182591 : if (!includePedCrossings) {
1038 54 : response = response.substr(0, response.size() - myJunction->getCrossings().size());
1039 : }
1040 182591 : if (response.find_first_of("1") == std::string::npos) {
1041 : return false;
1042 91219 : } else if (!myJunction->isTLControlled()) {
1043 : return true;
1044 : }
1045 : // if the link must respond it could also be due to a tlsConflict. This
1046 : // must not carry over the off-state response so we continue with
1047 : // the regular check
1048 : }
1049 : // get the indices
1050 35234 : int idx2 = getIndex(from, to);
1051 35234 : if (idx2 == -1) {
1052 : return false;
1053 : }
1054 : // go through all (existing) connections;
1055 : // check whether any of these forbids the one to determine
1056 : assert(idx2 < (int)(myIncoming.size()*myOutgoing.size()));
1057 235775 : for (int idx1 = 0; idx1 < numLinks(); idx1++) {
1058 : //assert(myDone[idx1][idx2]);
1059 325591 : if (myDone[idx1][idx2] && myForbids[idx1][idx2]) {
1060 : return true;
1061 : }
1062 : }
1063 : // maybe we need to brake for a pedestrian crossing
1064 2695 : if (includePedCrossings) {
1065 2277 : auto crossings = myJunction->getCrossings();
1066 2911 : for (std::vector<NBNode::Crossing*>::const_reverse_iterator i = crossings.rbegin(); i != crossings.rend(); i++) {
1067 1437 : if (mustBrakeForCrossing(myJunction, from, to, **i)) {
1068 : return true;
1069 : }
1070 : }
1071 2277 : }
1072 : // maybe we need to brake due to a right-turn conflict with straight-going
1073 : // bicycles
1074 1892 : const NBEdge::Connection& queryCon = from->getConnection(fromLane, to, toLane);
1075 1892 : LinkDirection dir = myJunction->getDirection(from, to);
1076 1892 : if (dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT) {
1077 626 : for (const NBEdge::Connection& fromCon : from->getConnections()) {
1078 563 : if (rightTurnConflict(from, queryCon, from, fromCon)) {
1079 : return true;
1080 : }
1081 : }
1082 : }
1083 : // maybe we need to brake due to a merge conflict
1084 9347 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
1085 7584 : int noLanes = (*i)->getNumLanes();
1086 22349 : for (int j = noLanes; j-- > 0;) {
1087 14779 : std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
1088 14779 : const int size = (int) connected.size();
1089 46034 : for (int k = size; k-- > 0;) {
1090 39294 : if ((*i) == from && fromLane != j
1091 34896 : && mergeConflict(from, queryCon, *i, connected[k], myJunction->getType() == SumoXMLNodeType::ZIPPER)) {
1092 : return true;
1093 : }
1094 : }
1095 14779 : }
1096 : }
1097 : // maybe we need to brake due to a zipper conflict
1098 1763 : if (myJunction->getType() == SumoXMLNodeType::ZIPPER) {
1099 0 : for (int idx1 = 0; idx1 < numLinks(); idx1++) {
1100 : //assert(myDone[idx1][idx2]);
1101 0 : if (myDone[idx1][idx2] && myForbids[idx2][idx1]) {
1102 : return true;
1103 : }
1104 : }
1105 : }
1106 : return false;
1107 204466 : }
1108 :
1109 :
1110 : bool
1111 43867 : NBRequest::mustBrakeForCrossing(const NBNode* node, const NBEdge* const from, const NBEdge* const to, const NBNode::Crossing& crossing) {
1112 43867 : const LinkDirection dir = node->getDirection(from, to);
1113 43867 : const bool mustYield = dir == LinkDirection::LEFT || dir == LinkDirection::RIGHT;
1114 43867 : if (crossing.priority || mustYield) {
1115 76202 : for (const NBEdge* const e : crossing.edges) {
1116 : // left and right turns must yield to unprioritized crossings only on their destination edge
1117 52812 : if ((e == from && crossing.priority) || e == to) {
1118 : return true;
1119 : }
1120 : }
1121 : }
1122 : return false;
1123 : }
1124 :
1125 :
1126 : bool
1127 0 : NBRequest::mustBrake(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
1128 : const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo) const {
1129 : // get the indices
1130 0 : int idx1 = getIndex(possProhibitorFrom, possProhibitorTo);
1131 0 : int idx2 = getIndex(possProhibitedFrom, possProhibitedTo);
1132 0 : return (myForbids[idx2][idx1]);
1133 : }
1134 :
1135 :
1136 : void
1137 1703 : NBRequest::reportWarnings() {
1138 : // check if any errors occurred on build the link prohibitions
1139 1703 : if (myNotBuild != 0) {
1140 0 : WRITE_WARNING(toString(myNotBuild) + " of " + toString(myNotBuild + myGoodBuilds) + " prohibitions were not build.");
1141 : }
1142 1703 : }
1143 :
1144 :
1145 : void
1146 36605 : NBRequest::resetCooperating() {
1147 : // map from edge to number of incoming connections
1148 : std::map<const NBEdge*, int> incomingCount; // initialized to 0
1149 : // map from edge to indices of approached lanes
1150 : std::map<const NBEdge*, std::set<int> > approachedLanes;
1151 : // map from edge to list of incoming edges
1152 : std::map<const NBEdge*, std::vector<const NBEdge*> > incomingEdges;
1153 112556 : for (const NBEdge* const e : myIncoming) {
1154 257124 : for (const NBEdge::Connection& con : e->getConnections()) {
1155 181173 : incomingCount[con.toEdge]++;
1156 181173 : approachedLanes[con.toEdge].insert(con.toLane);
1157 181173 : incomingEdges[con.toEdge].push_back(e);
1158 : }
1159 : }
1160 110412 : for (std::map<const NBEdge*, int>::iterator it = incomingCount.begin(); it != incomingCount.end(); ++it) {
1161 73807 : const NBEdge* const to = it->first;
1162 : // we cannot test against to->getNumLanes() since not all lanes may be used
1163 73807 : if ((int)approachedLanes[to].size() >= it->second) {
1164 30283 : const std::vector<const NBEdge*>& incoming = incomingEdges[to];
1165 : // make these connections mutually unconflicting
1166 69470 : for (const NBEdge* const e1 : incoming) {
1167 106396 : for (const NBEdge* const e2 : incoming) {
1168 67209 : myForbids[getIndex(e1, to)][getIndex(e2, to)] = false;
1169 : #ifdef DEBUG_SETBLOCKING
1170 : if (DEBUGCOND) std::cout << "resetCooperating"
1171 : << " 1:" << e1->getID() << "->" << to->getID()
1172 : << " 2:" << e2->getID() << "->" << to->getID()
1173 : << "\n";
1174 : #endif
1175 : }
1176 : }
1177 : }
1178 : }
1179 36605 : }
1180 :
1181 :
1182 : bool
1183 36787 : NBRequest::hasConflict() const {
1184 72261 : for (int i = 0; i < (int)myFoes.size(); i++) {
1185 52402 : if (hasConflictAtLink(i)) {
1186 : return true;
1187 : }
1188 : }
1189 : return false;
1190 : }
1191 :
1192 : bool
1193 53607 : NBRequest::hasConflictAtLink(int linkIndex) const {
1194 53607 : return myFoes[linkIndex].find_first_of("1") != std::string::npos;
1195 : }
1196 :
1197 : int
1198 278607 : NBRequest::numLinks() const {
1199 278607 : return (int)(myIncoming.size() * myOutgoing.size() + myJunction->getCrossings().size());
1200 : }
1201 :
1202 :
1203 : /****************************************************************************/
|
