Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2026 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 MELoop.cpp
15 : /// @author Daniel Krajzewicz
16 : /// @date Tue, May 2005
17 : ///
18 : // The main mesocopic simulation loop
19 : /****************************************************************************/
20 : #include <config.h>
21 :
22 : #include <queue>
23 : #include <vector>
24 : #include <map>
25 : #include <cmath>
26 :
27 : #include <microsim/MSNet.h>
28 : #include <microsim/MSEdge.h>
29 : #include <microsim/MSGlobals.h>
30 : #include <microsim/MSLane.h>
31 : #include <microsim/MSVehicle.h>
32 : #include <microsim/MSVehicleControl.h>
33 : #include <utils/options/OptionsCont.h>
34 : #include <utils/common/ToString.h>
35 : #include <utils/common/FileHelpers.h>
36 : #include <utils/common/SUMOTime.h>
37 : #include <utils/common/RandHelper.h>
38 : #include "MELoop.h"
39 : #include "MESegment.h"
40 : #include "MELSegment.h"
41 : #include "MEVehicle.h"
42 :
43 : long long int MELoop::LeaderEvent::myEventCounter(0);
44 :
45 : // ===========================================================================
46 : // method definitions
47 : // ===========================================================================
48 7058 : MELoop::MELoop(const SUMOTime recheckInterval) : myFullRecheckInterval(recheckInterval), myLinkRecheckInterval(TIME2STEPS(1)) {
49 7058 : }
50 :
51 6958 : MELoop::~MELoop() {
52 354957 : for (std::vector<MESegment*>::const_iterator j = myEdges2FirstSegments.begin(); j != myEdges2FirstSegments.end(); ++j) {
53 1070530 : for (MESegment* s = *j; s != nullptr;) {
54 : MESegment* n = s->getNextSegment();
55 722531 : delete s;
56 : s = n;
57 : }
58 : }
59 6958 : }
60 :
61 :
62 : void
63 12586567 : MELoop::simulate(SUMOTime tMax) {
64 552998917 : while (!myLeaderCars.empty()) {
65 544325287 : LeaderEvent e = myLeaderCars.top();
66 : assert(e.time > tMax - DELTA_T);
67 544325287 : if (e.time > tMax) {
68 3912937 : return;
69 : }
70 540412350 : myLeaderCars.pop();
71 540418655 : while (!myInvalidatedLeaderCars.empty() && e.time > myInvalidatedLeaderCars.top().time) {
72 6305 : myInvalidatedLeaderCars.pop();
73 : }
74 540412350 : if (!myInvalidatedLeaderCars.empty()) {
75 190311 : if (wasInvalidated(e)) {
76 2257 : continue;
77 : }
78 : }
79 : //std::cout << SIMTIME << " checkChar " << e.veh->getID() << " on=" << e.veh->getSegment()->getID() << " t=" << e.time << " nid=" << e.veh->getNumericalID() << "\n";
80 540410093 : checkCar(e.veh);
81 : assert(myLeaderCars.empty() || myLeaderCars.top().time >= e.time);
82 : }
83 : }
84 :
85 :
86 : bool
87 190311 : MELoop::wasInvalidated(const LeaderEvent& e) {
88 190311 : if (e.time == myInvalidatedLeaderCars.top().time) {
89 : // we need to check whether any of the events with the same time
90 : // is our current vehicle because the order in which
91 : // removeLeaderCar was called is unrelated to the order of addLeaderCar
92 : std::vector<LeaderEvent> tmp;
93 : bool curInvalid = false;
94 2579 : while (!myInvalidatedLeaderCars.empty() && e.time == myInvalidatedLeaderCars.top().time) {
95 : if (e == myInvalidatedLeaderCars.top()) {
96 2257 : myInvalidatedLeaderCars.pop();
97 : curInvalid = true;
98 2257 : break;
99 : } else {
100 166 : tmp.push_back(myInvalidatedLeaderCars.top());
101 166 : myInvalidatedLeaderCars.pop();
102 : }
103 : }
104 2579 : for (LeaderEvent& le : tmp) {
105 166 : myInvalidatedLeaderCars.push(le);
106 : }
107 : return curInvalid;
108 2413 : }
109 : return false;
110 : }
111 :
112 :
113 : SUMOTime
114 540425453 : MELoop::changeSegment(MEVehicle* veh, SUMOTime leaveTime, MESegment* const toSegment, MSMoveReminder::Notification reason, const bool ignoreLink) const {
115 540425453 : int qIdx = 0;
116 : MESegment* const onSegment = veh->getSegment();
117 : if (MESegment::isInvalid(toSegment)) {
118 810396 : if (veh->isStoppedTriggered()) {
119 5398 : return leaveTime + MAX2(SUMOTime(1), myLinkRecheckInterval);
120 : }
121 804998 : if (onSegment != nullptr) {
122 800802 : onSegment->send(veh, toSegment, qIdx, leaveTime, reason);
123 : } else {
124 12588 : WRITE_WARNINGF(TL("Vehicle '%' teleports beyond arrival edge '%', time=%."),
125 : veh->getID(), veh->getEdge()->getID(), time2string(leaveTime));
126 : }
127 804998 : veh->setSegment(toSegment); // signal arrival
128 804998 : MSNet::getInstance()->getVehicleControl().scheduleVehicleRemoval(veh);
129 804998 : return leaveTime;
130 537397925 : } else if ((!MSGlobals::gCheckRoutes || veh->ignoreTransientPermissions())
131 2222043 : && !ignoreLink
132 : && !MESegment::isInvalid(onSegment)
133 2221823 : && &onSegment->getEdge() != &toSegment->getEdge()
134 541035318 : && veh->getEdge()->allowedLanes(*veh->succEdge(1), veh->getVClass()) == nullptr) {
135 1416695 : if (veh->isStopped()) {
136 4 : veh->processStop();
137 : }
138 : // all queues on the next segment are forbidden. We don't want to check
139 : // too often whether the forbiden edge has become permitted again
140 1416695 : if (MSGlobals::gTimeToGridlock > 0) {
141 : // if teleporting is enabled, make sure we look at the vehicle when the gridlock-time is up
142 1414274 : const SUMOTime recheck = MSGlobals::gTimeToTeleportDisconnected >= 0 ? MIN2(MSGlobals::gTimeToGridlock, MSGlobals::gTimeToTeleportDisconnected) : MSGlobals::gTimeToGridlock;
143 1414274 : return MAX2(MIN2(leaveTime + myLinkRecheckInterval, MIN2(veh->getBlockTime(), leaveTime) + recheck + 1), leaveTime + 1);
144 : }
145 2421 : return leaveTime + myLinkRecheckInterval;
146 : }
147 538198362 : toSegment->updateEntryBlockTime(leaveTime);
148 538198362 : const SUMOTime entry = toSegment->hasSpaceFor(veh, leaveTime, qIdx);
149 538198362 : if (entry == leaveTime && (ignoreLink || veh->mayProceed())) {
150 25974098 : if (onSegment != nullptr) {
151 25973422 : if (veh->getQueIndex() == MESegment::PARKING_QUEUE) { // parking or just aborted parking
152 5652 : if (veh->isParking()) {
153 5651 : veh->processStop();
154 : }
155 5652 : veh->getEdge()->getLanes()[0]->removeParking(veh); // TODO for GUI only
156 : } else {
157 46863908 : onSegment->send(veh, toSegment, qIdx, leaveTime, onSegment->getNextSegment() == nullptr ? MSMoveReminder::NOTIFICATION_JUNCTION : MSMoveReminder::NOTIFICATION_SEGMENT);
158 : }
159 25973422 : toSegment->receive(veh, qIdx, leaveTime, false, ignoreLink, &onSegment->getEdge() != &toSegment->getEdge());
160 : } else {
161 2028 : WRITE_WARNINGF(TL("Vehicle '%' ends teleporting on edge '%':%, time=%."),
162 : veh->getID(), toSegment->getEdge().getID(), toSegment->getIndex(), time2string(leaveTime));
163 : // this is not quite correct but suffices for interrogation by
164 : // subsequent methods (veh->getSpeed() needs segment != 0)
165 676 : veh->setSegment(myEdges2FirstSegments[veh->getEdge()->getNumericalID()]);
166 : // clean up detectors (do not add traffic data)
167 : // note: updateDatector is not called if leaveTime == getLastEntryTime()
168 676 : veh->updateDetectors(veh->getLastEntryTime(), veh->getEventTime(), true, MSMoveReminder::NOTIFICATION_TELEPORT);
169 676 : toSegment->receive(veh, qIdx, leaveTime, false, true, true);
170 : }
171 25974098 : return entry;
172 : } else {
173 512224264 : if (veh->getQueIndex() != MESegment::PARKING_QUEUE && veh->isStopped() && veh->endTriggeredStop()) {
174 96 : veh->processStop();
175 : }
176 : }
177 512224264 : if (entry == leaveTime && !ignoreLink) { // this is a long way of saying !veh->mayProceed() (which is a costly call)
178 1240537 : return entry + MAX2(SUMOTime(1), myLinkRecheckInterval);
179 : }
180 : return entry;
181 : }
182 :
183 :
184 : void
185 540410093 : MELoop::checkCar(MEVehicle* veh) {
186 : const SUMOTime leaveTime = veh->getEventTime();
187 : MESegment* const onSegment = veh->getSegment();
188 540410093 : MESegment* const toSegment = veh->getQueIndex() == MESegment::PARKING_QUEUE ? onSegment : nextSegment(onSegment, veh);
189 540410093 : const bool teleporting = (onSegment == nullptr); // is the vehicle currently teleporting?
190 : // @note reason is only evaluated if toSegment == nullptr
191 540410093 : const SUMOTime nextEntry = changeSegment(veh, leaveTime, toSegment, MSMoveReminder::NOTIFICATION_ARRIVED, teleporting);
192 540410093 : if (nextEntry == leaveTime) {
193 : return;
194 : }
195 513643827 : const bool r1 = MSGlobals::gTimeToGridlock > 0 && veh->getWaitingTime() > MSGlobals::gTimeToGridlock;
196 513643827 : const bool r3 = MSGlobals::gTimeToTeleportDisconnected >= 0 && veh->getWaitingTime() > MSGlobals::gTimeToTeleportDisconnected;
197 513643827 : if (!veh->isStopped() && (r1 || r3)) {
198 1408084 : const bool disconnected = (MSGlobals::gTimeToTeleportDisconnected >= 0
199 1400418 : && veh->succEdge(1) != nullptr
200 2808502 : && veh->getEdge()->allowedLanes(*veh->succEdge(1), veh->getVClass()) == nullptr);
201 1408084 : if ((r1 && !disconnected) || (r3 && disconnected)) {
202 7682 : teleportVehicle(veh, toSegment, disconnected);
203 7682 : return;
204 : }
205 : }
206 513636145 : if (veh->getBlockTime() == SUMOTime_MAX && (!veh->isStopped()
207 222032 : || (!veh->isStoppedTriggered() && veh->isStoppedParking()))) {
208 : veh->setBlockTime(leaveTime);
209 : }
210 513636145 : if (nextEntry == SUMOTime_MAX) {
211 : // all usable queues on the next segment are full
212 510729472 : SUMOTime newEventTime = MAX3(toSegment->getEventTime() + 1, leaveTime + 1, leaveTime + myFullRecheckInterval);
213 510729472 : if (MSGlobals::gTimeToGridlock > 0) {
214 : // if teleporting is enabled, make sure we look at the vehicle when the gridlock-time is up
215 510688101 : const SUMOTime recheck = MSGlobals::gTimeToTeleportDisconnected >= 0 ? MIN2(MSGlobals::gTimeToGridlock, MSGlobals::gTimeToTeleportDisconnected) : MSGlobals::gTimeToGridlock;
216 510688101 : newEventTime = MAX2(MIN2(newEventTime, veh->getBlockTime() + recheck + 1), leaveTime + 1);
217 : }
218 : veh->setEventTime(newEventTime);
219 : } else {
220 : // receiving segment has recently received another vehicle or the junction is blocked
221 : veh->setEventTime(nextEntry);
222 : }
223 513636145 : addLeaderCar(veh, teleporting ? nullptr : onSegment->getLink(veh));
224 : }
225 :
226 :
227 : void
228 7682 : MELoop::teleportVehicle(MEVehicle* veh, MESegment* const toSegment, bool disconnected) {
229 : const SUMOTime leaveTime = veh->getEventTime();
230 : MESegment* const onSegment = veh->getSegment();
231 7682 : if (MSGlobals::gRemoveGridlocked) {
232 48 : WRITE_WARNINGF(TL("Teleporting vehicle '%'; waited too long, from edge '%':%, time=%."),
233 : veh->getID(), onSegment->getEdge().getID(), onSegment->getIndex(),
234 : time2string(leaveTime));
235 16 : MSNet::getInstance()->getVehicleControl().registerTeleportJam();
236 : int qIdx = 0;
237 16 : onSegment->send(veh, nullptr, qIdx, leaveTime, MSMoveReminder::NOTIFICATION_TELEPORT_ARRIVED);
238 16 : veh->setSegment(nullptr);
239 16 : MSNet::getInstance()->getVehicleControl().scheduleVehicleRemoval(veh);
240 16 : return;
241 : }
242 : const bool teleporting = (onSegment == nullptr); // is the vehicle already teleporting?
243 : // try to find a place on the current edge
244 7666 : MESegment* teleSegment = disconnected ? toSegment : toSegment->getNextSegment();
245 10196 : while (teleSegment != nullptr && changeSegment(veh, leaveTime, teleSegment, MSMoveReminder::NOTIFICATION_TELEPORT, true) != leaveTime) {
246 : // @caution the time to get to the next segment here is ignored XXX
247 : teleSegment = teleSegment->getNextSegment();
248 : }
249 7666 : if (teleSegment != nullptr) {
250 380 : if (!teleporting) {
251 : // we managed to teleport in a single jump
252 746 : const std::string reason = disconnected ? " (disconnected)" : "";
253 1134 : WRITE_WARNINGF(TL("Teleporting vehicle '%'; waited too long%, from edge '%':% to edge '%':%, time=%."),
254 : veh->getID(), reason, onSegment->getEdge().getID(), onSegment->getIndex(),
255 : teleSegment->getEdge().getID(), teleSegment->getIndex(), time2string(leaveTime));
256 378 : MSNet::getInstance()->getVehicleControl().registerTeleportJam();
257 : }
258 : } else {
259 : // teleport across the current edge and try insertion later
260 7286 : if (!teleporting) {
261 : int qIdx = 0;
262 : // announce start of multi-step teleport, arrival will be announced in changeSegment()
263 14724 : WRITE_WARNINGF(TL("Teleporting vehicle '%'; waited too long, from edge '%':%, time=%."),
264 : veh->getID(), onSegment->getEdge().getID(), onSegment->getIndex(), time2string(leaveTime));
265 4908 : MSNet::getInstance()->getVehicleControl().registerTeleportJam();
266 : // remove from current segment
267 4908 : onSegment->send(veh, nullptr, qIdx, leaveTime, MSMoveReminder::NOTIFICATION_TELEPORT);
268 : // mark veh as teleporting
269 4908 : veh->setSegment(nullptr);
270 : } else {
271 2378 : veh->updateDetectors(veh->getLastEntryTime(), leaveTime, true, MSMoveReminder::NOTIFICATION_TELEPORT);
272 : }
273 : // @caution microsim uses current travel time teleport duration
274 14572 : const SUMOTime teleArrival = leaveTime + TIME2STEPS(veh->getEdge()->getLength() / MAX2(veh->getEdge()->getSpeedLimit(), NUMERICAL_EPS));
275 7286 : const bool atDest = veh->moveRoutePointer();
276 7286 : if (atDest) {
277 : // teleporting to end of route
278 4196 : changeSegment(veh, teleArrival, nullptr, MSMoveReminder::NOTIFICATION_TELEPORT_ARRIVED, true);
279 : } else {
280 : veh->setEventTime(teleArrival);
281 3090 : addLeaderCar(veh, nullptr);
282 : // teleporting vehicles must react to rerouters
283 3090 : getSegmentForEdge(*veh->getEdge())->addReminders(veh);
284 3090 : veh->activateReminders(MSMoveReminder::NOTIFICATION_JUNCTION);
285 : }
286 : }
287 : }
288 :
289 :
290 : void
291 540419887 : MELoop::addLeaderCar(MEVehicle* veh, MSLink* link) {
292 540419887 : myLeaderCars.push(LeaderEvent(veh));
293 540419887 : veh->setApproaching(link);
294 540419887 : }
295 :
296 :
297 : void
298 12 : MELoop::clearState() {
299 12 : myLeaderCars = LeaderEventQeue();
300 12 : myInvalidatedLeaderCars = LeaderEventQeue();
301 12 : }
302 :
303 :
304 : void
305 8596 : MELoop::removeLeaderCar(MEVehicle* v) {
306 8596 : myInvalidatedLeaderCars.push(LeaderEvent(v));
307 8596 : }
308 :
309 :
310 : void
311 0 : MELoop::vaporizeCar(MEVehicle* v, MSMoveReminder::Notification reason) {
312 : int qIdx = 0;
313 0 : v->getSegment()->send(v, nullptr, qIdx, MSNet::getInstance()->getCurrentTimeStep(), reason);
314 0 : removeLeaderCar(v);
315 0 : }
316 :
317 :
318 : MESegment*
319 539856120 : MELoop::nextSegment(MESegment* s, MEVehicle* v) {
320 539856120 : if (s != nullptr) { // vehicle is not teleporting
321 : MESegment* next = s->getNextSegment();
322 539853064 : if (next != nullptr) {
323 : // ok, the street continues
324 : return next;
325 : }
326 : }
327 : // we have to check the next edge in the vehicle's route
328 517520759 : const MSEdge* nextEdge = v->succEdge(1);
329 517520759 : if (nextEdge == nullptr) {
330 : // end of route
331 : return nullptr;
332 : }
333 516722813 : if (MSGlobals::gUsingInternalLanes && s != nullptr && s->getEdge().isNormal()) {
334 507362152 : const MSEdge* internal = s->getEdge().getInternalFollowingEdge(nextEdge, v->getVClass());
335 507362152 : if (internal) {
336 : nextEdge = internal;
337 : }
338 : }
339 516722813 : return myEdges2FirstSegments[nextEdge->getNumericalID()];
340 : }
341 :
342 :
343 : int
344 512206 : MELoop::numSegmentsFor(const double length, const double sLength) {
345 512206 : int no = (int)floor(length / sLength + 0.5);
346 512206 : if (no == 0) { // assure there is at least one segment
347 : return 1;
348 : } else {
349 202380 : return no;
350 : }
351 : }
352 :
353 :
354 : void
355 350511 : MELoop::buildSegmentsFor(const MSEdge& e, const OptionsCont& oc) {
356 350511 : const MESegment::MesoEdgeType& edgeType = MSNet::getInstance()->getMesoType(e.getEdgeType());
357 : const double length = e.getLength();
358 350511 : const int numSegments = numSegmentsFor(length, edgeType.edgeLength);
359 350511 : const double slength = length / (double)numSegments;
360 : MESegment* newSegment = nullptr;
361 : MESegment* nextSegment = nullptr;
362 350511 : const bool laneQueue = oc.getBool("meso-lane-queue");
363 350511 : const bool lift = oc.getBool("meso-ltm");
364 677674 : bool multiQueue = laneQueue || (oc.getBool("meso-multi-queue") && e.getLanes().size() > 1 && e.getNumSuccessors() > 1);
365 1077914 : for (int s = numSegments - 1; s >= 0; s--) {
366 1454806 : std::string id = e.getID() + ":" + toString(s);
367 : newSegment = lift
368 727403 : ? new MELSegment(id, e, nextSegment, slength, e.getLanes()[0]->getSpeedLimit(), s, multiQueue, edgeType)
369 727403 : : new MESegment(id, e, nextSegment, slength, e.getLanes()[0]->getSpeedLimit(), s, multiQueue, edgeType);
370 : multiQueue = laneQueue;
371 : nextSegment = newSegment;
372 : }
373 701022 : while (e.getNumericalID() >= static_cast<int>(myEdges2FirstSegments.size())) {
374 350511 : myEdges2FirstSegments.push_back(0);
375 : }
376 350511 : myEdges2FirstSegments[e.getNumericalID()] = newSegment;
377 751103 : for (MSLane* lane : e.getLanes()) {
378 400592 : lane->updateMesoGUISegments();
379 : }
380 350511 : }
381 :
382 :
383 : MESegment*
384 154013485 : MELoop::getSegmentForEdge(const MSEdge& e, double pos) {
385 154013485 : if (e.getNumericalID() >= (int)myEdges2FirstSegments.size()) {
386 : return nullptr;
387 : }
388 154013461 : MESegment* s = myEdges2FirstSegments[e.getNumericalID()];
389 154013461 : if (pos > 0) {
390 : double cpos = 0;
391 888661 : while (s->getNextSegment() != nullptr && cpos + s->getLength() < pos) {
392 : cpos += s->getLength();
393 : s = s->getNextSegment();
394 : }
395 : }
396 : return s;
397 : }
398 :
399 :
400 : bool
401 240461 : MELoop::isEnteringRoundabout(const MSEdge& e) {
402 653258 : for (const MSEdge* succ : e.getSuccessors()) {
403 412821 : if (succ->isRoundabout()) {
404 : return true;
405 : }
406 : }
407 : return false;
408 : }
409 :
410 :
411 540428483 : MELoop::LeaderEvent::LeaderEvent(MEVehicle* v):
412 540428483 : time(v->getEventTime()),
413 540428483 : eventIndex(myEventCounter++),
414 540428483 : nid(v->getNumericalID()),
415 540428483 : veh(v) { }
416 :
417 : /****************************************************************************/
|