Today, when vehicles leave a building or parking lot's driveway, they always turn onto the rightmost lane of the adjacent road. (Or leftmost in left-handed maps, but for simplicity, I'll just assume right-handed driving here.) This was originally done for simplicity, but the assumption trickles down and affects a whole bunch of other things. I'd like to fix this and start reaping the benefits everywhere.

Some of these notes originally from https://github.com/a-b-street/abstreet/issues/382#issuecomment-730806495

The problem

In combination with lane-changing only allowed at intersections, exiting onto the rightmost lane forces us to pathfind at the granularity of lanes, not individual roads. Why?

99749744-efffa600-2a93-11eb-812b-7327db71f1db

Imagine we're a car pulling out of the driveway of the red house. Right now, the driving_pos connection is the rightmost lane, so if our path ideally starts by turning left onto Louisa, we have to follow the green route and loop around the block to get into the proper lane. This is because we can't lane-change in the middle of a lane, only at an intersection.

If we routed by roads, then the first step of the path might say to immediately turn left, following the blue route. If we keep spawning cars in the rightmost lane only, then that wouldn't work. We could maybe try to workaround this by starting the routing from a road that we definitely can reach from the rightmost lane, but there are a few arbitrary choices, and running several pathfinding queries and picking the cheapest feels like a possible performance problem.

The goal

Allow exiting a driveway onto any lane, sometimes having "lane-changing" immediately happen.

Change vehicle pathfinding to operate on DirectedRoadIDs, not LaneIDs -- or equivalently, maybe IntersectionIDs. This will have various benefits:

It's a prerequisite to widening roads for #67
It'll reduce the contraction hierarchy size, because there are less roads than lanes. This cuts down file size and speeds up building the CH and also querying it.
It simplifies the cost function by removing the lane-changing costs, and having all of that just determined lazily at runtime. Right now we dynamically rewrite the path at the simulation layer, and this is kind of confusing.

Modeling it

At the map layer, driving_connection for buildings and parking lots will instead allow choosing any starting lane.

At the sim layer, we'll pathfind at the road granularity, then figure out the closest starting lane based on the first turn required by the path. How will we physically spawn the car in that lane? start_car_on_lane gets more complicated when we detect we have to cross a few lanes. It'll call get_idx_to_insert_car on all of the intervening queues to check for room. Only if all of them come back clear, will the car "grab the lock" on all of the queues and begin their exit. I think we'll need a new construct in Queue. Instead of just storing an ordered sequence of cars, there's a possibility of inserting a "blockage" in there at a certain index, with a fixed Distance of the back of the blockage. Calculating car positions will just use that fixed position as the back of the car, always, until it's cleaned up. When the blockage is deleted, I think we have to wake up the first follower if they were Queued and put them back in Crossing, same as for deleting a parked car or making a bus depart again.

When should we clean up the blockages, when the car is fully finished unparking? Or as they clear each queue? Probably the former to start, but the latter could work by just assuming the fixed exiting speed and calculating when they'd clear each intermediate lane.

Also this queue "blockage" construct will probably help with later implementing dynamic lane over-taking (#81).

Queueing on driveways?

Today when a car fails to spawn, it waits BLIND_RETRY_TO_SPAWN = 5 seconds and tries again. I think we can continue doing the same thing. If multiple cars are trying to leave at once, that's invisible to the player. There's no internal order -- they'll all just keep retrying and competing. If one of them has less lanes to cut across, they might wind up getting the lock sooner. This seems fine.

Other cleanup steps

The crux of cutting over to road-based pathfinding seems like it's exiting driveways, but there are lots of other steps too. In no particular order:

Deciding whether to keep the lane-based Path struct, and/or creating some HighLevelPath struct with the roads instead
Drawing paths. When we're previewing a route and we only know roads, we could draw a thick fuzzy band or along centerlines or something. When we're drawing the route that a vehicle has followed so far or in the past, we might want to continue showing exactly their lane changes -- or maybe not, if it's not useful to see that.
Handling uber-turns -- we still need to do this at the CH level and n the sim to detect entering/exiting an UT. The UT would have to be expressed at the road segment level, not individual lanes and turns.
Figuring out what to do with pedestrian paths. I think a list of DirectedRoadIDs is unambiguous for figuring out what side of the road they're on, but need to think more carefully about this.

Later on

At first, I started writing this issue up to include turning left out of driveways, turning left into driveways, and using center left-turn lanes for driveways. But then I realized the smaller first step. Will revisit this after this issue is done. It has implications for gridlock (very silly paths because vehicles are forced into right turns) and parking blackholes.

Impl plan

TODO. Maybe a first step is just allowing any start lane, and warping the car there, without doing the queue blockage thing. Figuring out all the path / high-level path API changes is maybe the first step there.

The 2nd is sounding better, but I'm sure I'll end up pivoting a bit once I start doing this and discovering unanticipated messes.

Impl plan, take 1

In a separate branch, to avoid having to rebuild all maps before things are settled.

1) Fork pathfind/driving.rs for roads. Figure out a road-based representation for uber-turns. 2) Fork most of pathfind/mod.rs, creating a "high-level" PathV2, and maybe a PathRequestV2. 3) Create a transformation from PathV2 to lane-based Path, that selects particular lanes for each step. Don't bother trying to factor in LCing costs. This'll be a temporary shim. This is also the place to pick the starting lane. Probably also need to change driving_connection or make another one. I think we'll need a different method for entering the driveway and leaving it, actually. 4) Cut sim over to use PathV2 for requests. It'll sometimes ask for starting lanes that aren't the rightmost. Either cancel the trip when that happens, or just magically spawn them there -- the point is, don't worry about the queue blockage thing yet. Map it over to the lane Path inside router.rs, continuing to do the same stuff. 5) Cut over router.rs to use PathV2 more natively, deferring the lane choice as long as possible. Maybe this'll work lazily -- it'll keep a PathV2 and shift steps off of it, and create a small list of specific lanes and turns. Usually just 1 pair, but maybe few more for uber-turns. 6) Reconcile pedestrian paths with the new road-based approach. The problem is PathRequest has PathConstraints in there; the shape of the query and response has to be the same for vehicles and pedestrians. I don't think we want to change that, so at some point, we have to make these two have the same API. 7) Cut over all UI things, both in game and 15m, to use PathV2 natively without the shim. Drawing paths will probably be the center-line or thickened road style. 8) Remove the old CH and the shim. Everything's natively using PathV2 now. 9) Finally, implement the new queue blockage idea.

Impl plan, take 2

Maybe it's kind of confusing to maintain all of this separate implementation AND API during the transition.

1) Create PathV2, PathRequestV2, and give Map public v2 methods for everything. Create the translation layer to Path, failing if the starting lane doesn't match the original request. 2) Change the driving CH, walking CH, and Dijkstra impls to all internally use roads and serve the new V2 API. 3) Cut over sim to natively use the v2 API everywhere. 4) Same for all the UIs. 5) Remove the PathV2 -> Path shim, along with all the old APIs and objects. 6) Rename the v2 API, since there's just one now. 7) Finally, implement the new queue blockage idea.

Anticipated complications

What does PathRequestV2 look like? Instead of a position (lane+distance), just DirectedRoadID + distance? Are all callers OK with that; which absolutely need to know lanes?

What's PathV2 look like? Is a list of DirectedRoadIDs enough? The IntersectionIDs for turns could be implied or explicit. For vehicle paths, this seems pretty straightforward. But walking paths... DirectedRoadID is enough to uniquely specify the sidewalk or shoulder. But we should still explicitly say backwards or forwards on that -- PathStep::Forward(DirRoadID) and PathStep::Contraflow(DirRoadID). How about turns? Need to draw a diagram, but sometimes this winds up being a sequence of crosswalks and shared sidewalk corners. There are multiple ways to go between two DirRoadIDs + directions (aka, sidewalk endpoints). It seems fine to leave the specifics up to the sim layer. But I guess for rendering the route, sometimes we want the detail here.

Do we have a lookahead problem? Imagine a corridor with bike lanes, that branches off into a dedicated cyclepath later. If we changed turn generation to not allow entering the bike lanes at every intersection, then we would have to lookahead to actually realize the path. Maybe a better example is interstate express lanes, if they were modeled as part of the same road. But since things don't work this way, I think it's fine.

I'm looking at entering/exiting driveways onto either side of the road again. Some notes from a prototype:

Many places create a PathRequest, and filling out any sort of "alternate" start/end Positions there is going to be a mess. Those insisting on a single lane anyway is a soon-outdated assumption, if we're going to handle exiting onto any lane.
- Should the v2 request maybe just TripEndpoint -- a building, border, or sudden appearance spawning position?
In some degenerate cases where the source and target are on the same road and same side, sometimes the winning path is the off-side, even though it winds up being impossible to follow.
- Maybe weighting the initial and final nodes to penalize off-side would help
- Or just special-case it
Doing off-side driveway connections kind of first requires exiting onto any lane. Or maybe we just break a few paths in the meantime; the problem can happen more often with off-side.
Underlying multi-start/end queries with contraction hierarchies seem to work, though not sure yet about multi-ends: https://github.com/easbar/fast_paths/pull/29#issuecomment-861294707
If we want the Dijkstra impl to stay in sync and handle multiple starts/ends, it's going to be easiest to first refactor away from petgraph and use my own thing. Or maybe this is an opportunity to move everything to the fast_paths InputGraph and update the dijkstra impl there too.

Or maybe this is an opportunity to move everything to the fast_paths InputGraph and update the dijkstra impl there too.

Can you explain what you are missing from the fast_path dijkstra implementation?

Can you explain what you are missing from the fast_path dijkstra implementation?

Just support for multiple start and end nodes, like you just added to CH. It looks much simpler to implement. I can look at doing it sometime next week if you don't have time right now.

My earlier comment was conflating a few things. A/B Street currently uses a mix of fast_paths (for CHs), petgraph (for A* / Dijkstra's when the a map is built without CHs for faster testing), and a custom Dijkstra's implementation that returns all intermediate costs and stops early once a maximum weight is reached. Before introducing multiple start nodes for this issue, I could've actually removed petgraph and used the dijkstra implementation from fast_paths, which would save me the code that creates an input graph for both libraries. Now that exiting from driveways is almost ready to go, I wouldn't do this refactor without adding multi start/end to fast_paths dijkstra's.

I think so far fast_path does not even export the dijkstra implementation. Basically it is internal to fast_paths and only used for CH preparation. It also features a few specialities for this purpose. But sure we could either publish it as is or maybe even implement some kind of version of it that you think is useful.

I'm looking into exporting it now and adding a few things:

getting all node weights after running a calculation
handling multiple sources & targets
optionally omitting an end node, so we just floodfill from some sources and calculate the minimum cost to others

But juggling some other work, so no guarantee when I'll get to this. If you think adding any of this might not be ideal for the use for CH preparation, I could maybe also just start a simpler fresh implementation for public export. The use case being that a caller already does work of assembling an InputGraph and wants to also use Dijkstra's on it for things like calculating travel-time isochrones.

getting all node weights after running a calculation

You mean all node weights from a single source search?

handling multiple sources & targets

Handling multiple targets kind of contradicts getting all node weights from a single source search. Handling multiple targets like we did for CH is easy using a bidirectional search, but getting all node weights for a single source would be just a uni-directional search.

optionally omitting an end node, so we just floodfill from some sources and calculate the minimum cost to others

this is kind of like the first bullet point, except for multiple sources.

It sounds like you need one algorithm that just builds a shortest path tree from multiple sources and a bidirectional search to support multiple targets. In principle of course you could also use the former and run the search until you found all targets. The search space size for the bidirectional search is about half, so it can be roughly twice as fast.

If you think adding any of this might not be ideal for the use for CH preparation, I could maybe also just start a simpler fresh implementation for public export.

The problem I see here is that InputGraph by itself is not routeable, since it is just a (sorted) list of edges, but there is no efficient way to expand a node or something. This is why fast_paths builds another temporary data structure (PreparationGraph) to build the CH. If you wanted to run Dijkstra without keeping the same graph in memory twice, ideally you would have to run Dijkstra on the FastGraph that is also used for CH.

The use case being that a caller already does work of assembling an InputGraph and wants to also use Dijkstra's on it for things like calculating travel-time isochrones.

Ok, I think the real question we need to answer in fast_paths then is whether we can support some of your use-cases using FastGraph, because this is the only data structure that is kept in memory (apart from temporary data we use during the CH building phase). Otherwise it would be more about adding some code that builds some routeable graph from InputGraph that we can use to support the queries you want to do. But this way we'd still need two versions of the graph in memory and there would just be a common API (both are built from InputGraph), so not sure if this would be much of an improvement here.

You mean all node weights from a single source search?

Correct. The use case is calculating isochrones for a 15m neighborhood tool. We floodfill from one or more nodes, terminate after the cost exceeds 15 minutes, and use the weight of all the reached nodes to draw the isochrone.

Handling multiple targets kind of contradicts getting all node weights from a single source search.

You're correct. These'd be two different uses of Dijkstra's. One of them used for regular vehicle routing, same as with CHs, with multiple sources/targets possibly. The other would be a new call, something like fn calculate_all_weights(&self, sources: Vec<(NodeID, Weight)>) -> HashMap<NodeID, Weight> -- it wouldn't even take any targets, because that doesn't make sense here.

But this way we'd still need two versions of the graph in memory and there would just be a common API

I see. I was picturing calling PreparationGraph::from_input_graph before feeding into some variation of the current Dijkstra's implementation. But to avoid repeating work for every query, we'd probably want to expose PreparationGraph, make it serializable, etc. Lots of hassle.

It may not be worth it. Maintaining some duplicate logic in abst for creating input graphs isn't horrible, just a slight maintenance burden.

a-b-street / abstreet

Pathfinding v2 / Exit driveways onto any lane #555