Looping uber-turn causing a crash

[dabreegster]

I've seen a crash at https://github.com/a-b-street/abstreet/blob/37404044e3e3f6ae2c8e85eeb05f9691c1df8197/map_model/src/pathfind/v2.rs#L299 in a few maps, like leeds/huge. We're transforming directed road-level uber turns to lane-level uber-turns, and if we don't wind up with the same number of input and output, the assertion trips.

The example in Leeds:

UberTurnV2 { path: [MovementID { from: DirectedRoadID { road: RoadID(21528), dir: Fwd }, to: DirectedRoadID { road: RoadID(21529), dir: Fwd }, parent: IntersectionID(17376), crosswalk: false }, MovementID { from: DirectedRoadID { road: RoadID(21529), dir: Fwd }, to: DirectedRoadID { road: RoadID(21559), dir: Fwd }, parent: IntersectionID(1216), crosswalk: false }, MovementID { from: DirectedRoadID { road: RoadID(21559), dir: Fwd }, to: DirectedRoadID { road: RoadID(21561), dir: Fwd }, parent: IntersectionID(17378), crosswalk: false }, MovementID { from: DirectedRoadID { road: RoadID(21561), dir: Fwd }, to: DirectedRoadID { road: RoadID(21560), dir: Fwd }, parent: IntersectionID(9052), crosswalk: false }, MovementID { from: DirectedRoadID { road: RoadID(21560), dir: Fwd }, to: DirectedRoadID { road: RoadID(21532), dir: Fwd }, parent: IntersectionID(17377), crosswalk: false }, MovementID { from: DirectedRoadID { road: RoadID(21532), dir: Fwd }, to: DirectedRoadID { road: RoadID(705), dir: Fwd }, parent: IntersectionID(1216), crosswalk: false }, MovementID { from: DirectedRoadID { road: RoadID(705), dir: Fwd }, to: DirectedRoadID { road: RoadID(706), dir: Fwd }, parent: IntersectionID(14873), crosswalk: false }] }

Bit of a mouthful, but I traced out what this looks like: And we uh, have a loop in the uber-turn, but pathfinding v1 doesn't trace the loop. Based on how we do a graph search to transform v2->v1, it makes sense why the loop vanishes. My question is how we possibly wound up with a loop in the first place

[dabreegster]

Past-me was wise enough to make an uber-turn debug mode. Look what we have here: I'm not spotting the more direct route in this list... which would explain why pathfinding v2 picks it. A more direct route would have a lower cost.

I need to remember how all of this stuff works, but I think uber-turns are built first by lanes, then translated to v2 / directed road level. Since they're lane-based to start with, the per-lane turn restrictions are probably causing this loopiness. Need to confirm and think about if that sort of loopy movement is ever valid.

[Robinlovelace]

That is loopy, in reality, OSM and in game! Glad it has served the purpose of exposing an edge case bug, if nothing else...