4 implement lane matching

[bdog2112]

Hey @TheDuckCow, please checkout this pull request for new Lane Matching functionality.

It includes:

• New _match_lanes function in road_segment.gd
• Addition of transition types to RoadPoint.LaneTypes enum
• New GUT tests

Some questions to ponder:

• Do I want additional input checks in match lanes function? (e.g. check for and flag multiple lane direction flips)
• Do I want additional GUT tests?
• Are there any other questions or concerns?

Please let me know if you have any questions, change requests, or if you'd like to merge.

Thanks

[TheDuckCow]

Posting a quick comment as I'm boarding shortly, will finish up full code review on plane.

First off, tests function and all pass for me - and at a glance, looks nicely exhaustive! Thanks a bunch for putting this effort in, good use of parametrized tests for sure.

Main comment in the meantime is: no need to wait for me to finish the code review before jumping into the next body of work. You can create another branch (provided you have already have "4-implement-lane-matching" checked out) which can then become the start of your next set of changes which will use this code.

Then, if I have any code comments I want you to address, you'll make them in this "4-implement-lane-matching" branch of this PR, and merge that to main; when the next PR is ready to go, it'll be diff'd off the main branch anyhow. Let me know if that makes sense!

EDIT: You'll also see that I marked the PR as assigned to you instead of me; I'm marked as a reviewer. That way it shows up in the github UI as expected, as I often use my "pull requests seeking review" as a way to keep track of where I need to do code reviews.

[bdog2112]

Hey @TheDuckCow,

Hope you're having fun on your journey. We just got blanketed with another volley of snow, here. :-)

In reply to your comments:

Most high level comment: Current code doesn't support one-way roads like F > F or RR > R. We should be able to "short circuit" detect this if we find there are only ever all F's or all R's in both RoadPoints. Right now it always returns illegal setup, which is otherwise correct except when all lanes are the same direction. Remember: all lanes going e.g. forward is conceptually like having the lane direction divider on the far left of the left-most lane.

One-way (i.e. one-lane) roads are currently out of scope. However, your suggestion is duly noted. Do you want to bring "one-lane" in scope for this change?

Second point is that it always seems to output slow lane, where I'd expect some scenarios of MIDDLE or FAST. This seems more critical to get the next stage right, but let me know if you were thinking this interpretation would happen elsewhere (though if you do, I'd actually argue that the lane matching function would be a decent spot). Related to this point: As this would require updating most of the tests, it may be an opportunity to also already address a later comment of not having quite as exhaustive of scenario coverage, since you'd now have 85 test cases to update with .FAST and .MIDDLE, where several tests start to feel redundant.

Regarding the extensive battery of tests, the intent, was really just to insure that there weren't any strange one-off transition cases that didn't work. It was faster to create the full list than to pick and choose.

On the subject of using slow lanes for tests: It was easier to write test cases using a single lane type.

The lane matching algorithm outputs the lanes types from the start point and there is plenty of opportunity to test that assertion. My standard test case would be "slow lanes on the sides and fast lanes in the middle."

In the interest of time and brevity, why don't we add 9 test cases. These will be in the same test file. But, a separate batch to signify specific testing of "lane type". (Direction flip will occur in the fast lanes.)

(F - Fast, S - Slow, A - Add, R - Remove)

1. FF > FF >> F|F
2. FF > FFS >> F|FA
3. FFS > FF >> F|FR
4. SFFS > SFF >> SF|FR
5. SFF > SFFS >> SF|FA
6. SSFF > SFF >> RSF|F
7. SFF > SSFF >> ASF|F
8. SSFFSS > FF >> RRF|FRR
9. FF > SSFFSS >> AAF|FAA

I think the remainder of the requested changes were style-related.

Conclusion:

• Please let me know if you want to bring one-lane roads into scope
• Let me know if the proposed test case updates will suffice
• In the meantime, I'll work on the requested style changes

[TheDuckCow]

Conclusion: Please let me know if you want to bring one-lane roads into scope See below, yes (both-way remains out of scope). I'd expect some examples like below to work (I'm adding the | chart just to illustrate)

• F > F >> |-
• F > FF >> |-A (adding on the "outside")
• R > RR >> |A- (adding on the "outside")
• FFF > FFFF >> ---A (but order would be FMSA, where F=fast, M=middle, S-slow, and A=add), from a texturing standpoint)

Let me know if the proposed test case updates will suffice

I support your change. Only comment would be I'd expect something like FF > SSFFSS >> AAF|FAA, wouldn't this actually be still "forward" vs "reverse" on the left side? ie FF > RRRFFF >> AAF|FAA? I think it's good to keep the "left hand side" to be just Forard's and Reverse, as that matches the input to the funciton. The output on the right should be the interpretation.

In the meantime, I'll work on the requested style changes

Thanks!

---

One-way (i.e. one-lane) roads are currently out of scope. However, your suggestion is duly noted. Do you want to bring "one-lane" in scope for this change?

Thanks for catching me on that, I think I meant to write both way lanes being out of scope but that's my bad. If you think it's not a huge difference, I do think it would be good to support single directional lanes from the start as we'll have that early on (both-way is still way out of scope for now).

[bdog2112]

One-way (i.e. one-lane) roads are currently out of scope. However, your suggestion is duly noted. Do you want to bring "one-lane" in scope for this change?

Thanks for catching me on that, I think I meant to write both way lanes being out of scope but that's my bad. If you think it's not a huge difference, I do think it would be good to support single directional lanes from the start as we'll have that early on (both-way is still way out of scope for now).

I think it would be fairly easy to implement certain aspects of "one-way" in the _match_lanes routine. As you said, just add a short-circuit case for all FORWARD (or REVERSE?) lanes. Although, this may necessitate further requirements gathering and discussion.

At some point, a one-way road must connect with other two-way roads. Hence, there must be rules for facilitating that. New rules necessitate more code to support them.

An alternative might be to say that one-way can never connect to two-way. But, that seems pretty restrictive.

Any way you look at it, you'll probably want to do one-way. It's just a question of, "now or later?"

[TheDuckCow]

Let's do one ways connecting to one ways only for now, supporting both forward and reverse -only variants. A one way connecting to a two way sounds like an "intersection" in a way, which I'm happy to push out till later.

[bdog2112]

It just hit me: there can be such a thing as one-way transitions. For example: 1>2 lanes. The transition algorithm may or may not handle this scenario. But, it might!

Given that it iterates the REVERSE lanes and then the FORWARD lanes, it follows that it could probably handle a set of single-direction lanes and produce the expected result. At any rate, there could also be unexpected surprises/glitches requiring additional work.

Do you still want to proceed with one-way support?

[bdog2112]

As I dig into this, I see that the solution is not just a simple: "short-circuit if all the lanes are going in the same direction."

Allowing FORWARD lanes to come first nullifies the previously used assumptions that REVERSE lanes always come first. Thus, necessitating a new and more complex set of rules. But, it's do-able.

[bdog2112]

Well, I moved forward and I'm happy to say everything went well! I've uploaded the "one-lane" _match_lanes prototype!

Had to add a _get_lane_flip_offset routine to de-duplicate some code.

Pay attention to where lanes are being added/removed. Remember, we said lanes would always be added on the "outside". What that meant was that FORWARD lanes always had transitions on the right. REVERSE lanes always had transitions on the left. In the future, you may want more flexibility than that. But, this change made good use of the existing algorithm while also facilitating decent one-lane support.

In order to test, I needed some test cases. So, I created 10. I'll include them in the commit in case you can use them. But, feel free to do with them as you wish.

Regarding testing, you recently mentioned that you would like to see the Lane Type in the result labels. Although, one of your recent posts also suggested to continue using dashes. I used Lane Type instead of dashes. Hopefully, that provides greater transparency as to what's actually happening. Pipes were also included in the new test labels.

Given that we're working on one-lane and/or one-way roads, it's also worth observing the texture line placement (figuratively speaking). FORWARD lanes should have lines on the left. REVERSE lanes, lines on the right. Additionally, they will have shoulders on the left and right, which also provide lines. So, I've placed SLOW lanes on the outside and MIDDLE lanes on the inside in order to position lines only in the middle of the road. Does that make sense?

Both the old tests and the new tests passed.

Does this address the remaining issues in this pull request?

[TheDuckCow]

This looks and works great, thanks @bdog2112! The comments make sense and I was able to follow the logic. The only thing I started to wonder is, at this stag, is there a substantial difference between a "slow" lane and a "middle" lane from a texturing standpoint? Since the shoulder now fully contain the shoulder line, and both the middle and fast lane contain just a dotted line on the side which is more "inside".

The number and variety of tests added work well, cover enough cases and illustrate what is needed (including where the "inside" is).

Regardless, things are looking good, and I'd say we're in good shape to move to the next phase of connecting this up with the geometry generation! Do you have enough direction to work on that at this point? Any unknowns you'd like me to think through to provide enough direction? I expect it should mix quite nicely with the work you've already done to generate added/removed lanes earlier.

[bdog2112]

The only thing I started to wonder is, at this stag, is there a substantial difference between a "slow" lane and a "middle" lane from a texturing standpoint?

You're right. We may no longer need the "middle" Lane Type.

You had called out testing only "slow" lanes and the lack of "middle" and "fast" lanes in a recent post. Texturing one-way roads meant that we wouldn't use fast lanes and I got the mistaken impression that "middle" lanes were solid gray. Although, after further review, I see that they're, as you said, pretty much the same as slow lanes.

We can feed whatever lane textures we want into the lane matching tests. The important thing is to observe that the inputs get routed to the proper lanes in the output. In that regard, it was helpful to include middle lanes.

I'd say we're in good shape to move to the next phase of connecting this up with the geometry generation! Do you have enough direction to work on that at this point? Any unknowns you'd like me to think through to provide enough direction?

Regarding the next phase: Multiple processes run before Lane Drawing including a bit of code that prevents differences of more than two lanes on the start and end points and, also, "assign_lanes".

Is it safe to say we can now disable/remove the two-lane difference restrictor?

Assign Lanes might also need updates since we've added one-way configurations. However, Lane Drawing isn't expressly dependent on that in order to proceed.

I don't have any further questions at the moment. I'll let you know if anything comes up.