Define intersections technical plan

[TheDuckCow]

Once we have nice transitions from one lane to another, the natural next step is to support common intersections.

This plugin is being developed in particular for the Wheel Steal game project, which is focussed on highways and less on city scenarios. So while we should ensure we can create a general solution that will be extendable and functional for other systems, we should focus first on highway-like interactions.

This should start with a research subtask of identifying varieties of highway intersections (e.g. a highway splitting into two interstates, single or multi-lane on ramps/off ramps, a median splitting two roads or joining back up). Then, tasks can be created for the implementation of each type. Before jumping in, work should be done to ensure we have a good strategy for how texturing in these situations will work, as well as what architecture changes will be needed (will we need to implement an "intersection" node type, or just extend RoadPoint to support multiple 'points'?)

[TheDuckCow]

Started working on some aspects of this design here (non public link). To be discussed in near future.

[bdog2112]

OVERVIEW: An "Intersection" is a junction between multiple RoadPoints and Godot Road Generator needs to be able to facilitate junctions of 3 or more. A handful of Intersection Types would address the bulk of our needs and also cover a sizeable portion of overall real world possibilities.

PROPOSAL: Create an "Intersection" object that behaves much like a regular RoadPoint. But, it handles some drawing and associative tasks that make it distinct and different. Also, make limited modifications to RoadPoints.

TECHNICAL DETAILS: Intersections will draw themselves and they will bolt on to the sides and ends of RoadPoints.

The current drawing architecture employs virtual Segments that are defined by pt_inits on RoadPoints. Each RoadPoint has a "prev" and "next" RoadPoint. We need to extend this by adding "left" and "right" pt_inits. These will signify adjacent Intersections and tell the RoadPoint whether to draw shoulders.

Some Intersection types can be positioned at Segment Start and End Points. But, they won't be referenced in the RoadPoints' prev/next pt_inits. Hence, RoadPoints won't require any changes to facilitate them.

Conversely, All Intersections will carry a reference to ALL of their adjacent RoadPoints. They will need this information in order to know where to attach, which lanes to draw, and which way to route the lanes.

These changes will allow us to attach Offramps, Onramps, and T-Intersections to the sides of Segments as well as Splitters and 4-Way Stops to the ends of Segments.

INTERSECTION TYPES: A handful of Intersection "Types" would allow Road Generator to facilitate a broad range of real world scenarios.

What are the Types of Intersection?

1. Offramp - An angled connective road piece that attaches to the left or right side of a Segment. It covers the span of the entire Segment and its Start Point is the Segment's Start Point. Its End Point is a separate RoadPoint situated off to the side of the Segment and adjacent to the Segment's Stop Point. Its appearance is somewhat different than a regular Segment in terms of lane markings or lack thereof.
2. Onramp - An angled connective road piece that attaches to the left or right side of a Segment. It covers the span of the entire Segment and its End Point is the Segment's End Point. Its Start Point is a separate RoadPoint situated off to the side of the Segment and adjacent to the Segment's Start Point. Its appearance is different than a regular Segment in terms of lane markings or lack thereof.
3. Splitter - A Segment that contains two side-by-side RoadPoints on one end and one RoadPoint on the other end. The total number of lanes in equals the total number of lanes out. A common use case is splitting a two-way road into two separate one-way roads. Although, there are many possible permutations. It would be good to narrow the scope on what this type will and won't do.
4. 4-Way Stop - This takes the shape of a plus symbol and positions one RoadPoint on each side. It could, potentially, be a simple square. That really depends on whether we need to draw lines where the cars are supposed to stop. There are no lines in the middle of the Intersection.
5. T - This facilitates a regular Segment with a perpendicularly attached Intersection on one side. The user has the option to attach T-Intersections on both sides of a Segment. These Intersections will essentially be like stop signs. Whereas, the main Segment will contain unimpeded traffic flow with traditional lane markings. We could, arbitrarily, say that a white "Stop" line will be painted on any lanes that would be turning onto the main Segment (or not).

THINGS TO THINK ABOUT:

• On an Intersection, which connections are Start Points and which are End Points (i.e. the beginning or end of a road)? Does it matter?
• Should we add Intersections via the RoadPoint Panel?
• How will the RoadPoint Panel navigate various Intersections?
• How will Intersections respond to adding/removing lanes on adjacent RoadPoints?
• How will Intersections behave when an associated RoadPoint is deleted?
• Users can't select Segments. Should they be able to select Intersections?

OUT OF SCOPE

• Sidewalks.
• 5-way, 6-way, 7-way... Intersections

[bdog2112]

It just occurred to me that Segments are drawn by the RoadSegment class, not RoadPoint. It follows that Intersections are Segments and they would also be drawn by RoadSegment. But, this raises some issues.

Segments are virtual constructs derived from data stored in RoadPoints. Our current Segments are also a simple type of Intersection. Hence, one logical approach would be to store Intersection data in RoadPoints. However, this would result in some data redundancy, which can be difficult to manage.

If we think of Segments as a database, we already have some data duplication since RoadPoints identify Prev/Next RoadPoints twice; once in each associated RoadPoint. This works fine. But, when we start adding more RoadPoint association fields, the data duplication grows. When we change the data in one place, we have to update it in all the others.

In a normalized database, data would be de-duplicated and stored in a separate "associative" table. Hence, that may be a reasonable justification to have a separate "associative" class such as "Intersection".

If we choose to go down the path of retrofitting RoadPoint, then we would probably add an "IntersectionType" property and branch existing code, where necessary, to support new and different Intersections as well as updating RoadSegment to draw them.

[bdog2112]

When it comes to the RoadPoint Panel navigating forward and back across Segments, I am of the mind that Intersections should be treated as the end of the road or the beginning of a road depending on whether it is a Start Point or End Point that terminates on the Intersection.

[bdog2112]

For Intersection RoadPoint associations, it would be good to have a distinct Intersection object with an array of RoadPoints. The number of points would vary from one Intersection Type to the next.

One way of itegrating this into the existing architecture would be to give every RoadPoint a placeholder for an Intersection object. Then, share the same object between all of the RoadPoints that need it.

An alternative to this approach would be to simply add 3-4 additional pt_init properties to the RoadPoint class plus a property called IntersectionType. Then, just make sure that those fields get updated consistently for all RoadPoints that belong to a given Intersection.

That approach may have some problems if a RoadPoint is part of both a regular Segment AND an Intersection.

[bdog2112]

If a RoadPoint connected to an Intersection via Prev/Next, then the RoadPoint would expect the Intersection to be a RoadPoint. In turn, the RoadPoint would expect the Intersection to have a valid lane configuration so that it could run Auto Lanes and perform other tasks.

Due to an Intersection's complex nature and the fact that it connects to several RoadPoints, it would be best if it was treated as different type of entity. Hence, RoadPoints would need to perform additional checks when evaluating Prev/Next to see if the attached RoadPoint is an Intersection.

[bdog2112]

There is a good case for storing an Intersection's list of RoadPoints in the Intersection since RoadPoints don't need to know about attached Intersections and Intersections do need to know about attached RoadPoints. But, there are many considerations.

If RoadPoints connect to an Intersection as if it's just another RoadPoint, then the Intersection may not have any record of the ones that are attached.

In the case of a Splitter, it's important for the Intersection to know the lane configurations of all of the attached RoadPoints in order to route and draw them. Hence, it will have to iterate the entire list of RoadPoints in search of the ones attached. It would be more efficient to simply store the list in the Intersection.

On that note, the individual RoadPoints don't necessarily need to know about the Intersection. To them, they're simply at the end of the road. Hence, Intersection associations don't need to be stored in individual RoadPoints.

From a user perspective, it would be nice to be able to select a RoadPoint and click in the RoadPoint Panel to attach an Intersection. But, users don't necessarily need to know that the record is stored in the Intersection vs the RoadPoint. However, in this use case, it would be convenient to have the Intersection listed in the RoadPoint. Otherwise, we would have to search the RoadPoint array for Intersections that referenced this RoadPoint.

Finally, it is possible to store an Intersection's RoadPoint associations both in the individual RoadPoints AND the Intersection. This would eliminate the need to search the entire RoadPoints array to find the points belonging to an Intersection.

At any rate, this is a conundrum. Where do we store an Intersection's list of RoadPoints?

[TheDuckCow]

To be discussed with @bdog2112, a synthesized proposal. There's likely some things that will need to change or be modified, but I feel this is a good foundation. They key point here is that it works well for both procedurally generated intersections as well as hand crafted, since we want to ensure both of those are always available for end users.

intersections v1.pdf

[bdog2112]

The preliminary suggestions for the high-level structure seem reasonable:

• Change RoadPoint.prev/next_pt_init to allow "InterPoints" (Spatial)
• Create InterPoint to hold RoadPoints and intersection types
• Create InterSegment to draw intersections

Those will probably require some changes to RoadPoint. There are also a number of general considerations to be made.

• How will the T-junction and On/Offramps attach to the side of a RoadPoint? Either the RoadPoint will have to be modified to allow side attachments OR the Intersections will have to mimic a segment.
• Will Intersections draw lanes? Splitter and Rounadabout probably, yes. On/Offramp maybe, maybe not. 4-way, probably not.
• It is good to think about the needs of all Intersection types at once. But, at some point, it would be good to pick just ONE and focus on that. (Perhaps Onramp.) Then, gradually work our way through the list one at a time.

How will Intersections be created?

• Converting nodes to Intersections could be problematic since, as you mentioned, there might not be enough space. A safe and easy approach would be to have the user designate the starting RoadPoint and add the Intersection. Then, position a pre-defined Intersection shape at that RoadPoint. Each Intersection could have a default input that will be attached to the starting RoadPoint. Other RoadPoints must be designated after the Intersection is added to the scene. Assuming each Intersection has a rigid footprint, the remaining RoadPoints will probably have to be moved in order to attach, anyway. The Intersection could automatically re-position the remaining RoadPoints when the user associates them with it.
• An alternative approach would be to present a dialog box with an Intersection diagram, a letter for each RoadPoint in the diagram, and a sortable list of RoadPoints. For a 3-way intersection, the diagram would show points A, B, and C. The sortable list would also show an A, B, and C. Users could attach RoadPoints to the list and move them up and down in order to designate where they attach in the diagram. We could, arbitrarily, say that the A RoadPoint is always the anchor or, maybe, have a radio button that allows the user to designate the anchor.
• It would be good to continue brainstorming potential options a bit more.

[TheDuckCow]

Adding some thoughts I just had after doing some QA on the recent create 2x2 work (particularly when testing that we can indeed set a roadnetwork as a scene root now)

In terms of scene tree hierarchy:

• InterPoints are added at the same hierarchy depth as other RoadPoints who are not intersections
• RoadPoints are added as children of this interpoint, so it's very clear that those "belong" to that intersection
• Any RoadPoints connecting to the intersection are actually connecting to children of the interpoint.
• A roadpoint whose parent is an interpoint would then know that it should not try to trigger any roadsegments reconstruction. We'd have to decide if this endpoint roadpoint actually specifies the InterPoint as the "next point" or not (probably still helpful, so it's clear which "slot" of the roadpoint is open for other roadpoints to connect to.

I am liking how this structure sounds, because it could pave the way to creating intricate prefab scenes which either we provide as out of the box, or end users can use to create their own. In this world, an intersection point could actually be itself a nested scene (with the caveat that users would have a hard time manually overriding the connections since the children of the scene would not be scene visible).

This does make authoring of these interpoint intersection scenes a little awkward, since in order for anything to be dynamically drawn, there would need to be a roadnetowrk contained. I can imagine a few ways to get around that issue, but I'm probably jumping a few too many steps ahead and we should discuss first (after v0.3.1 of course)

This is still a discussion for later, just wanted to note it down before I lose track of it.

[TheDuckCow]

Alright, I'm going to be closing out the technical plan here as we discussed today and came to a flexible and good solution in the meantime, which gives room for growth:

• In line with the above, there will be a RoadIntersection class created (using the term "road" to make searching easier) which will house children of RoadPoints and pre-defined geometry
  • Predefined geometry means: hand authored for now, eventually we can do procedural intersection creation. But we don't want to delay, and we know custom scenes will be necessary for some people anyways.
• This will also immediately open the door for manually defined road segment scenes with custom geometry and so forth.
  • In practice, they'll behave the same way as intersections do, sitting in a prefab scene
• To make this all work, we necessarily need interactive tools for helping connect RoadPoints (in the current scene, or as the children of packed scenes).

To do this, we'll go in a few steps:

1. https://github.com/TheDuckCow/godot-road-generator/issues/74
2. https://github.com/TheDuckCow/godot-road-generator/issues/115
3. https://github.com/TheDuckCow/godot-road-generator/issues/116
4. https://github.com/TheDuckCow/godot-road-generator/issues/117
5. https://github.com/TheDuckCow/godot-road-generator/issues/118

There will be a couple steps after this, but the above represents the main body of work.