1 package org.opentrafficsim.road.gtu.lane.tactical.routesystem;
2
3 import java.util.LinkedHashMap;
4 import java.util.LinkedHashSet;
5 import java.util.Map;
6 import java.util.Set;
7 import java.util.SortedSet;
8 import java.util.TreeSet;
9
10 import org.djunits.value.vdouble.scalar.Length;
11 import org.djutils.exceptions.Throw;
12 import org.djutils.immutablecollections.ImmutableMap;
13 import org.djutils.immutablecollections.ImmutableMap.ImmutableEntry;
14 import org.djutils.multikeymap.MultiKeyMap;
15 import org.opentrafficsim.core.gtu.GTUDirectionality;
16 import org.opentrafficsim.core.gtu.GTUException;
17 import org.opentrafficsim.core.gtu.GTUType;
18 import org.opentrafficsim.core.network.LateralDirectionality;
19 import org.opentrafficsim.core.network.Node;
20 import org.opentrafficsim.core.network.route.Route;
21 import org.opentrafficsim.road.network.lane.DirectedLanePosition;
22 import org.opentrafficsim.road.network.lane.Lane;
23
24 /**
25 * Default route system. This system stores a set for each combination of a {@code Lane}, {@code GTUDirectionality},
26 * {@code Route} and {@code GTUType}. The set provides route information over a given distance beyond the end of the lane. If
27 * more distance is required, the set is recalculated. If less is required, a subset is returned. Distances in the returned
28 * route information are adjusted for the specific position of the GTU.
29 * <p>
30 * Copyright (c) 2013-2022 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
31 * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
32 * <p>
33 * @version $Revision$, $LastChangedDate$, by $Author$, initial version 7 nov. 2019 <br>
34 * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
35 * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
36 * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
37 */
38 public class DefaultRouteSystem implements RouteSystem
39 {
40
41 /** Cache. */
42 private MultiKeyMap<LaneChangeInfoSet> cache = new MultiKeyMap<>(Lane.class, GTUDirectionality.class, Route.class,
43 GTUType.class);
44
45 /** {@inheritDoc} */
46 @Override
47 public SortedSet<LaneChangeInfo> getLaneChangeInfo(final DirectedLanePosition position, final Length front,
48 final Route route, final GTUType gtuType, final Length distance)
49 {
50 /*
51 // obtain set
52 LaneChangeInfoSet set = this.cache.get(() -> determineSet(position, route, gtuType, distance), position.getLane(),
53 position.getGtuDirection(), route, gtuType);
54 // check if previous search was far enough
55 if (set.suppliesDistance(distance))
56 {
57 // far enough, return info with distances adjusted to GTU position
58 Length pos = position.getGtuDirection().isPlus() ? position.getPosition() : position.getLane().getLength().minus(
59 position.getPosition());
60 return set.getAdjustedSet(pos, distance);
61 }
62 */
63 // previously calculated set does not have sufficient length, clear and recalculate
64 this.cache.clear(position.getLane(), position.getGtuDirection(), route, gtuType);
65 return getLaneChangeInfo(position, front, route, gtuType, distance);
66 }
67
68 /**
69 * Determines a set of lane change info.
70 * @param position DirectedLanePosition; position
71 * @param front Length; distance required for the front (relative to reference position)
72 * @param route Route; route, may be {@code null}
73 * @param gtuType GTUType; GTU type
74 * @param distance Length; distance over which required lane changes are desired to be known
75 * @return SortedSet<LaneChangeInfo>; lane change information
76 * @throws GTUException in case of multiple adjacent lanes
77 */
78 private LaneChangeInfoSet determineSet(final DirectedLanePosition position, final Length front, final Route route,
79 final GTUType gtuType, final Length distance) throws GTUException
80 {
81 // the search can stop as soon as all lanes are reachable on a link that starts beyond 'distance' of the end of the lane
82
83 Map<LaneRecord, LaneChangeInfo> currentSet = new LinkedHashMap<>();
84 Map<LaneRecord, LaneChangeInfo> nextSet = new LinkedHashMap<>();
85 Length startDistance = (position.getGtuDirection().isPlus() ? position.getPosition() : position.getLane().getLength()
86 .minus(position.getPosition())).plus(front).neg();
87 LaneRecord record = new LaneRecord(startDistance, position.getLane(), position.getGtuDirection());
88 Length remainingDistance = position.getLane().getLength().minus(startDistance);
89 currentSet.put(record, new LaneChangeInfo(0, remainingDistance, record.isDeadEnd(gtuType),
90 LateralDirectionality.NONE));
91
92 while (!currentSet.isEmpty())
93 {
94 // move lateral
95 nextSet.putAll(currentSet);
96 for (LateralDirectionality lat : new LateralDirectionality[] {LateralDirectionality.LEFT,
97 LateralDirectionality.RIGHT})
98 {
99 for (LaneRecord laneRecord : currentSet.keySet())
100 {
101 laneRecord = lat.isLeft() ? laneRecord.left(gtuType) : laneRecord.right(gtuType);
102 if (!currentSet.containsKey(laneRecord))
103 {
104 LaneChangeInfo info = currentSet.get(laneRecord);
105 LaneChangeInfo adjInfo = new LaneChangeInfo(info.getNumberOfLaneChanges() + 1, remainingDistance,
106 laneRecord.isDeadEnd(gtuType), lat);
107 nextSet.put(laneRecord, adjInfo);
108 }
109 }
110 }
111 }
112
113 return new LaneChangeInfoSet(null, null);
114 }
115
116 /**
117 * Set of lane change info, that can be adjusted for a specific GTU position on the origin lane.
118 * <p>
119 * Copyright (c) 2013-2022 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
120 * <br>
121 * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
122 * <p>
123 * @version Feb 11, 2020 <br>
124 * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
125 * @author <a href="http://Hansvanlint.weblog.tudelft.nl">Hans van Lint</a>
126 * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
127 * @author <a href="http://www.citg.tudelft.nl">Guus Tamminga</a>
128 * @author <a href="http://www.citg.tudelft.nl">Yufei Yuan</a>
129 */
130 private class LaneChangeInfoSet
131 {
132
133 /** Distance of info that this set can supply. */
134 private final Length dist;
135
136 /** Set with info. */
137 private final SortedSet<LaneChangeInfo> set;
138
139 /**
140 * @param distance Length; distance within which the info is gathered
141 * @param set SortedSet<LaneChangeInfo>; set with info
142 */
143 LaneChangeInfoSet(final Length distance, final SortedSet<LaneChangeInfo> set)
144 {
145 this.dist = distance;
146 this.set = set;
147 }
148
149 /**
150 * Returns whether this set can supply up to the requested distance.
151 * @param distance Length; requested distance of info
152 * @return boolean; whether this set can supply up to the requested distance
153 */
154 public boolean suppliesDistance(final Length distance)
155 {
156 return distance.le(this.dist);
157 }
158
159 /**
160 * Returns the set of information with distances adjusted to the GTU position.
161 * @param position Length; position of the GTU on the origin lane
162 * @param distance Length; maximum distance of included info
163 * @return SortedSet<LaneChangeInfo>; set of information with distances adjusted to the GTU position
164 */
165 public SortedSet<LaneChangeInfo> getAdjustedSet(final Length position, final Length distance)
166 {
167 SortedSet<LaneChangeInfo> adjustedSet = new TreeSet<>();
168 for (LaneChangeInfo info : this.set)
169 {
170 Length adjustedDistance = info.getRemainingDistance().minus(position);
171 if (adjustedDistance.le(distance))
172 {
173 adjustedSet.add(new LaneChangeInfo(info.getNumberOfLaneChanges(), adjustedDistance, info.deadEnd(), info
174 .getLateralDirectionality()));
175 }
176 else
177 {
178 // we can stop, further info is beyond the requested scope
179 break;
180 }
181 }
182 return adjustedSet;
183 }
184
185 }
186
187 /**
188 * Helper class to aid route algorithms.
189 * <p>
190 * Copyright (c) 2013-2022 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
191 * <br>
192 * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
193 * <p>
194 * @version $Revision$, $LastChangedDate$, by $Author$, initial version 13 feb. 2020 <br>
195 * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
196 * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
197 * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
198 */
199 private class LaneRecord
200 {
201
202 /** Start distance. */
203 private final Length startDistance;
204
205 /** Lane. */
206 private final Lane lane;
207
208 /** Direction of travel. */
209 private final GTUDirectionality direction;
210
211 /** Previous record. */
212 private LaneRecord prev;
213
214 /** Left record. */
215 private LaneRecord left;
216
217 /** Whether the left records was determined. */
218 private boolean determinedLeft = false;
219
220 /** Right record. */
221 private LaneRecord right;
222
223 /** Whether the right records was determined. */
224 private boolean determinedRight = false;
225
226 /**
227 * @param startDistance Length; start distance
228 * @param lane Lane; lane
229 * @param direction GTUDirectionality; direction of travel
230 */
231 LaneRecord(final Length startDistance, final Lane lane, final GTUDirectionality direction)
232 {
233 this.startDistance = startDistance;
234 this.lane = lane;
235 this.direction = direction;
236 }
237
238 /**
239 * Returns a set of next lanes along the route. This set may be empty. Note that this does not mean the lane can be
240 * considered a dead-end, as the route is considered.
241 * @param route Route route;
242 * @param gtuType GTUType; gtuType
243 * @return set of next lanes, which may be empty.
244 */
245 public Set<LaneRecord> next(final Route route, final GTUType gtuType)
246 {
247 Set<LaneRecord> set = new LinkedHashSet<>();
248 ImmutableMap<Lane, GTUDirectionality> lanes = this.lane.downstreamLanes(this.direction, gtuType);
249 for (ImmutableEntry<Lane, GTUDirectionality> entry : lanes.entrySet())
250 {
251 // check route
252 Node from;
253 Node to;
254 if (entry.getValue().isPlus())
255 {
256 from = entry.getKey().getParentLink().getStartNode();
257 to = entry.getKey().getParentLink().getEndNode();
258 }
259 else
260 {
261 from = entry.getKey().getParentLink().getEndNode();
262 to = entry.getKey().getParentLink().getStartNode();
263 }
264 if (route.indexOf(to) == route.indexOf(from) + 1)
265 {
266 LaneRecord record = new LaneRecord(this.getStartDistance().plus(this.lane.getLength()), entry.getKey(),
267 entry.getValue());
268 record.prev = this;
269 set.add(record);
270 }
271 }
272 return set;
273 }
274
275 /**
276 * Returns the previous (upstream) record.
277 * @return LaneRecord; previous (upstream) record
278 */
279 public LaneRecord prev()
280 {
281 return this.prev;
282 }
283
284 /**
285 * Returns the left adjacent lane, or {@code null} if no such lane.
286 * @param gtuType GTUType; GTU type
287 * @return left adjacent lane, or {@code null} if no such lane
288 * @throws GTUException in case of multiple adjacent lanes
289 */
290 public LaneRecord left(final GTUType gtuType) throws GTUException
291 {
292 if (!this.determinedLeft)
293 {
294 this.left = adjacent(gtuType, LateralDirectionality.LEFT);
295 this.determinedLeft = true;
296 if (this.left.lane.accessibleAdjacentLanesLegal(LateralDirectionality.RIGHT, gtuType, this.left.direction)
297 .contains(this.lane))
298 {
299 this.left.right = this;
300 }
301 this.left.determinedRight = true;
302 }
303 return this.left;
304 }
305
306 /**
307 * Returns the right adjacent lane, or {@code null} if no such lane.
308 * @param gtuType GTUType; GTU type
309 * @return right adjacent lane, or {@code null} if no such lane
310 * @throws GTUException in case of multiple adjacent lanes
311 */
312 public LaneRecord right(final GTUType gtuType) throws GTUException
313 {
314 if (!this.determinedRight)
315 {
316 this.right = adjacent(gtuType, LateralDirectionality.RIGHT);
317 this.determinedRight = true;
318 if (this.right.lane.accessibleAdjacentLanesLegal(LateralDirectionality.LEFT, gtuType, this.right.direction)
319 .contains(this.lane))
320 {
321 this.right.left = this;
322 }
323 this.right.determinedLeft = true;
324 }
325 return this.right;
326 }
327
328 /**
329 * Returns the left or right adjacent lane, or {@code null} if no such lane.
330 * @param gtuType GTUType; GTU type
331 * @param lat LateralDirectionality; left or right
332 * @return left or right adjacent lane, or {@code null} if no such lane
333 * @throws GTUException in case of multiple adjacent lanes
334 */
335 private LaneRecord adjacent(final GTUType gtuType, final LateralDirectionality lat) throws GTUException
336 {
337 Set<Lane> set = this.lane.accessibleAdjacentLanesLegal(lat, gtuType, this.direction);
338 Throw.when(set.size() > 1, GTUException.class,
339 "Default route system found multiple adjacent lanes, which is not supported.");
340 if (set.size() == 1)
341 {
342 return new LaneRecord(this.startDistance, set.iterator().next(), this.direction);
343 }
344 return null;
345 }
346
347 /**
348 * Returns the start distance, relative to the end of the origin lane.
349 * @return Length; start distance, relative to the end of the origin lane
350 */
351 public Length getStartDistance()
352 {
353 return this.startDistance;
354 }
355
356 /**
357 * Returns whether there is no available next lane (ignoring the route).
358 * @param gtuType GTUType; GTU type
359 * @return whether there is no available next lane (ignoring the route)
360 */
361 public boolean isDeadEnd(final GTUType gtuType)
362 {
363 return this.lane.downstreamLanes(this.direction, gtuType).isEmpty();
364 }
365
366 }
367
368 }