Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2002-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 MSLaneChanger.h
15 : /// @author Christian Roessel
16 : /// @author Daniel Krajzewicz
17 : /// @author Michael Behrisch
18 : /// @author Jakob Erdmann
19 : /// @date Fri, 01 Feb 2002
20 : ///
21 : // Performs lane changing of vehicles
22 : /****************************************************************************/
23 : #pragma once
24 : #include <config.h>
25 :
26 : #include "MSLane.h"
27 : #include "MSEdge.h"
28 : #include "MSVehicle.h"
29 : #include <vector>
30 : #include <utils/iodevices/OutputDevice.h>
31 :
32 :
33 : // ===========================================================================
34 : // class declarations
35 : // ===========================================================================
36 :
37 :
38 : // ===========================================================================
39 : // class definitions
40 : // ===========================================================================
41 : /**
42 : * @class MSLaneChanger
43 : * @brief Performs lane changing of vehicles
44 : */
45 : class MSLaneChanger {
46 : public:
47 : /// Constructor
48 : MSLaneChanger(const std::vector<MSLane*>* lanes, bool allowChanging);
49 :
50 : /// Destructor.
51 : virtual ~MSLaneChanger();
52 :
53 : /// Start lane-change-process for all vehicles on the edge'e lanes.
54 : void laneChange(SUMOTime t);
55 :
56 : public:
57 : /** Structure used for lane-change. For every lane you have to
58 : know four vehicles, the change-candidate veh and its follower
59 : and leader. Further, information about the last vehicle that changed
60 : into this lane is needed */
61 : struct ChangeElem {
62 :
63 : ChangeElem(MSLane* _lane);
64 :
65 : /// @brief Register that vehicle belongs to Changer Item to after LC decisions
66 : void registerHop(MSVehicle* vehicle);
67 :
68 : ///@brief the leader vehicle for the current change candidate
69 : MSVehicle* lead;
70 : ///@brief the lane corresponding to this ChangeElem (the current change candidate is on this lane)
71 : MSLane* lane;
72 : ///@brief last vehicle that changed into this lane
73 : MSVehicle* hoppedVeh;
74 : /// @brief the next vehicle downstream of the ego vehicle that is blocked from changing to this lane
75 : MSVehicle* lastBlocked;
76 : /// @brief the farthest downstream vehicle on this edge that is blocked from changing to this lane
77 : MSVehicle* firstBlocked;
78 : /// @brief the next vehicle downstream of the ego vehicle that is stopped (and thus an obstacle)
79 : MSVehicle* lastStopped;
80 :
81 : double dens;
82 :
83 : /// @brief whether changing is possible to either direction
84 : bool mayChangeRight;
85 : bool mayChangeLeft;
86 :
87 : /// relative indices of internal lanes with the same origin lane (siblings)
88 : /// only used for changes on internal edges
89 : std::vector<int> siblings;
90 :
91 : /// @name Members which are used only by MSLaneChangerSublane
92 : /// @{
93 : // the vehicles in front of the current vehicle (only on the current edge, continously updated during change() )
94 : MSLeaderInfo ahead;
95 :
96 : // the vehicles in front of the current vehicle (including those on the next edge, contiously update during change() ))
97 : MSLeaderDistanceInfo aheadNext;
98 :
99 : /// vehicles that cannot be stored in ahead because they are outside the lane bounds
100 : std::vector<MSVehicle*> outsideBounds;
101 :
102 : /// visibility distance to the closest zipper link that may be encountered when driving on this lane
103 : double zipperDist;
104 :
105 : /// the back position of the last blocked vehicle that wants to change to this lane
106 : double lastBlockedBackPos;
107 :
108 : /// the waiting time of the last blocked vehicle that wants to change to this lane
109 : SUMOTime lastBlockedWaitingTime;
110 : ///@}
111 :
112 : };
113 :
114 : public:
115 : /** @brief The list of changers;
116 : For each lane, a ChangeElem is being build */
117 : typedef std::vector< ChangeElem > Changer;
118 :
119 : /// the iterator moving over the ChangeElems
120 : typedef Changer::iterator ChangerIt;
121 :
122 : /// the iterator moving over the ChangeElems
123 : typedef Changer::const_iterator ConstChangerIt;
124 :
125 : /// @brief return changer (only to be used by MSLaneChangerSublane from another instance)
126 : Changer& getChanger() {
127 : return myChanger;
128 : }
129 :
130 : /// @brief retrieve properties of a blocked vehicle that wants to chane to the lane with the given index
131 : std::pair<double, SUMOTime> getLastBlocked(int index) const;
132 :
133 : void postloadInitLC();
134 :
135 : protected:
136 : /// Initialize the changer before looping over all vehicles.
137 : virtual void initChanger();
138 :
139 : /** @brief Check if there is a single change-candidate in the changer.
140 : Returns true if there is one. */
141 : bool vehInChanger() const {
142 : // If there is at least one valid vehicle under the veh's in myChanger
143 : // return true.
144 566882506 : for (ConstChangerIt ce = myChanger.begin(); ce != myChanger.end(); ++ce) {
145 369887185 : if (veh(ce) != 0) {
146 : return true;
147 : }
148 : }
149 : return false;
150 : }
151 :
152 : /** Returns the furthes unhandled vehicle on this change-elements lane
153 : or 0 if there is none. */
154 : MSVehicle* veh(ConstChangerIt ce) const {
155 : // If ce has a valid vehicle, return it. Otherwise return 0.
156 5776940005 : if (!ce->lane->myVehicles.empty()) {
157 5483346940 : return ce->lane->myVehicles.back();
158 : } else {
159 : return 0;
160 : }
161 : }
162 :
163 :
164 : /** Find a new candidate and try to change it. */
165 : virtual bool change();
166 :
167 :
168 : /** try changing to the opposite direction edge. */
169 : bool changeOpposite(MSVehicle* vehicle, std::pair<MSVehicle*, double> leader, MSVehicle* lastStopped);
170 :
171 : std::pair<MSVehicle* const, double> getOncomingVehicle(const MSLane* opposite, std::pair<MSVehicle*,
172 : double> neighOncoming, double searchDist, double& vMax, const MSVehicle* overtaken = nullptr,
173 : MSLane::MinorLinkMode mLinkMode = MSLane::MinorLinkMode::FOLLOW_NEVER);
174 :
175 : std::pair<MSVehicle* const, double> getOncomingOppositeVehicle(const MSVehicle* vehicle,
176 : std::pair<MSVehicle*, double> overtaken, double searchDist);
177 :
178 : /** Update changer for vehicles that did not change */
179 : void registerUnchanged(MSVehicle* vehicle);
180 :
181 : /// @brief Take into account traci LC-commands.
182 : /// @note This is currently only used within non-actionsteps.
183 : void checkTraCICommands(MSVehicle* vehicle);
184 :
185 : /// @brief Execute TraCI LC-commands.
186 : /// @note This is currently only used within non-actionsteps for the non-sublane model.
187 : /// @return whether lane was changed
188 : bool applyTraCICommands(MSVehicle* vehicle);
189 :
190 : /** After the possible change, update the changer. */
191 : virtual void updateChanger(bool vehHasChanged);
192 :
193 : /** During lane-change a temporary vehicle container is filled within
194 : the lanes (bad practice to modify foreign members, I know). Swap
195 : this container with the real one. */
196 : void updateLanes(SUMOTime t);
197 :
198 : /** @brief Find current candidate.
199 : If there is none, myChanger.end() is returned. */
200 : ChangerIt findCandidate();
201 :
202 : /* @brief check whether lane changing in the given direction is desirable
203 : * and possible */
204 : int checkChangeWithinEdge(
205 : int laneOffset,
206 : const std::pair<MSVehicle* const, double>& leader,
207 : const std::vector<MSVehicle::LaneQ>& preb) const;
208 :
209 : /* @brief check whether lane changing in the given direction is desirable
210 : * and possible */
211 : int checkChange(
212 : int laneOffset,
213 : const MSLane* targetLane,
214 : const std::pair<MSVehicle* const, double>& leader,
215 : const std::pair<MSVehicle* const, double>& follower,
216 : const std::pair<MSVehicle* const, double>& neighLead,
217 : const std::pair<MSVehicle* const, double>& neighFollow,
218 : const std::vector<MSVehicle::LaneQ>& preb) const;
219 :
220 : /* @brief call lanechange model to check the merits of an opposite-direction
221 : * change and update state accordingly */
222 : virtual bool checkChangeOpposite(
223 : MSVehicle* vehicle,
224 : int laneOffset,
225 : MSLane* targetLane,
226 : const std::pair<MSVehicle* const, double>& leader,
227 : const std::pair<MSVehicle* const, double>& neighLead,
228 : const std::pair<MSVehicle* const, double>& neighFollow,
229 : const std::vector<MSVehicle::LaneQ>& preb);
230 :
231 :
232 : /* @brief start the lane change maneuver (and finish it instantly if gLaneChangeDuration == 0)
233 : * @return False when aborting the change due to being remote controlled*/
234 : bool startChange(MSVehicle* vehicle, ChangerIt& from, int direction);
235 :
236 : /// @brief continue a lane change maneuver and return whether the vehicle has completely moved onto the new lane (used if gLaneChangeDuration > 0)
237 : bool continueChange(MSVehicle* vehicle, ChangerIt& from);
238 :
239 : std::pair<MSVehicle* const, double> getRealFollower(const ChangerIt& target) const;
240 :
241 : std::pair<MSVehicle* const, double> getRealLeader(const ChangerIt& target) const;
242 :
243 : /// @brief whether changing to the lane in the given direction should be considered
244 : bool mayChange(int direction) const;
245 :
246 : /// @brief return the closer follower of ego
247 : static MSVehicle* getCloserFollower(const double maxPos, MSVehicle* follow1, MSVehicle* follow2);
248 :
249 : /** @brief Compute the time and space required for overtaking the given leader
250 : * @param[in] vehicle The vehicle that wants to overtake
251 : * @param[in] leader The vehicle to be overtaken
252 : * @param[in] gap The gap between vehicle and leader
253 : * @param[out] timeToOvertake The time for overtaking
254 : * @param[out] spaceToOvertake The space for overtaking
255 : */
256 : static void computeOvertakingTime(const MSVehicle* vehicle, double vMax, const MSVehicle* leader, double gap, double& timeToOvertake, double& spaceToOvertake);
257 :
258 : /** @brief return leader vehicle that is to be overtaken
259 : * @param[out] maxSpace The maxium space that can be used for the overtaking maneuver (limits speed)
260 : * @param[in] vehicle The vehicle that wants to overtake
261 : * @param[in] leader The vehicle to be overtaken and the gap to this vehicle
262 : * @param[in] maxLookAhead The maximum lookahead distance
263 : *
264 : * This methods calls itself recursively to find the leader of a column of
265 : * vehicles to be overtaken (if there is no sufficient gap for stopping in between)
266 : */
267 : static std::pair<MSVehicle*, double> getColumnleader(double& maxSpace, MSVehicle* vehicle, std::pair<MSVehicle*, double> leader, double maxLookAhead = std::numeric_limits<double>::max());
268 :
269 : /// @brief return the next lane in conts beyond lane or nullptr
270 : static const MSLane* getLaneAfter(const MSLane* lane, const std::vector<MSLane*>& conts, bool allowMinor, bool& contsEnd);
271 :
272 : /// @brief whether vehicle has an opposite-direction stop within relevant range
273 : static bool hasOppositeStop(MSVehicle* vehicle);
274 :
275 : /// @brief decide whether to change (back or forth) for an opposite stop
276 : bool checkOppositeStop(MSVehicle* vehicle, const MSLane* oncomingLane, const MSLane* opposite, std::pair<MSVehicle*, double> leader);
277 :
278 : /** @brief avoid opposite-diretion deadlock when vehicles are stopped on both sides of the road
279 : * The method may call saveBlockerLength to affect vehicle speed in the next step
280 : */
281 : bool avoidDeadlock(MSVehicle* vehicle,
282 : std::pair<MSVehicle*, double> neighLead,
283 : std::pair<MSVehicle*, double> overtaken,
284 : std::pair<MSVehicle*, double> leader);
285 :
286 : /** @brief keep stopping to resolve opposite-diretion deadlock while there is oncoming traffic
287 : * The method may call saveBlockerLength to affect vehicle speed in the next step
288 : */
289 : bool resolveDeadlock(MSVehicle* vehicle,
290 : std::pair<MSVehicle* const, double> leader,
291 : std::pair<MSVehicle*, double> neighLead,
292 : std::pair<MSVehicle*, double> overtaken);
293 :
294 : /// @brief check whether to keep stopping for oncoming vehicles in the deadlock zone
295 : bool yieldToDeadlockOncoming(const MSVehicle* vehicle, const MSVehicle* stoppedNeigh, double dist);
296 :
297 : /// @brief check whether to yield for oncoming vehicles that have waited longer for opposite overtaking
298 : bool yieldToOppositeWaiting(const MSVehicle* vehicle, const MSVehicle* stoppedNeigh, double dist, SUMOTime deltaWait = 0);
299 :
300 : /// @brief determine for how long the vehicle can drive safely on the opposite side
301 : double computeSafeOppositeLength(MSVehicle* vehicle, double oppositeLength, const MSLane* source, double usableDist,
302 : std::pair<MSVehicle*, double> oncoming, double vMax, double oncomingSpeed,
303 : std::pair<MSVehicle*, double> neighLead,
304 : std::pair<MSVehicle*, double> overtaken,
305 : std::pair<MSVehicle*, double> neighFollow,
306 : double surplusGap, const MSLane* opposite,
307 : bool canOvertake);
308 :
309 : // @brief compute distance that can safely be driven on the opposite side
310 : static double computeSurplusGap(const MSVehicle* vehicle, const MSLane* opposite, std::pair<MSVehicle*, double> oncoming, double timeToOvertake,
311 : double spaceToOvertake, double& oncomingSpeed, bool oncomingOpposite = false);
312 :
313 : // @brief find hilltop within searchDistance
314 : static bool foundHilltop(MSVehicle* vehicle, bool foundHill, double searchDist, const std::vector<MSLane*>& bestLanes, int view, double pos, double lastMax, double hilltopThreshold);
315 :
316 : /// @brief add LaneQ for opposite lanes
317 : static std::vector<MSVehicle::LaneQ> getBestLanesOpposite(MSVehicle* vehicle, const MSLane* stopLane, double oppositeLength);
318 :
319 : /// @brief compute maximum maneuver speed
320 : static double getMaxOvertakingSpeed(const MSVehicle* vehicle, double maxSpaceToOvertake);
321 :
322 : protected:
323 : /// Container for ChangeElemements, one for every lane in the edge.
324 : Changer myChanger;
325 :
326 : /** Change-candidate. Last of the vehicles in changer. Only this one
327 : will try to change. Every vehicle on the edge will be a candidate
328 : once in the change-process. */
329 : ChangerIt myCandi;
330 :
331 : /* @brief Whether vehicles may start to change lanes on this edge
332 : * (finishing a change in progress is always permitted) */
333 : const bool myAllowsChanging;
334 :
335 : /// @brief whether this edge allows changing to the opposite direction edge
336 : const bool myChangeToOpposite;
337 :
338 : /* @brief whether neigboring lanes target the same outgoing edge but have different foe links and
339 : * therefore require an extra MSLink::opened check before changing */
340 : bool checkOpened;
341 :
342 : private:
343 : /// Default constructor.
344 : MSLaneChanger();
345 :
346 : /// Copy constructor.
347 : MSLaneChanger(const MSLaneChanger&);
348 :
349 : /// Assignment operator.
350 : MSLaneChanger& operator=(const MSLaneChanger&);
351 : };
|
