[patch] Build two parallel ways in one drag (prototype, r12110)

[victor_18993]

I have a working prototype of a tool that builds two parallel ways, one tile
apart, with a single drag.

I would appreciate feedback on the direction before extending it. Supporting
diagonals, slopes, bridges and tunnels will require substantially more work, and
I would rather confirm that the basic approach is acceptable first.
The patch is against r12110 and is split into two files: the feature patch and
the tests. Only the feature patch is intended for trunk.

Current behaviour
Two tools are added to the same toolbar as the ordinary way tools, one for each
side. The player selects a side and drags once to build two parallel ways.
Both routes are planned against the untouched world. Both must be valid, their
costs are added, and the player's funds are checked before either route is
built. If either route fails, nothing is built and nothing is charged.
The currently validated scope is:

• road and rail;
• straight runs and bends;
• flat ground;
• one-tile spacing.

The same code path currently accepts tram, narrow gauge, monorail and maglev,
but those have not yet received equivalent test coverage.
Deliberately unsupported for now:

• pure diagonals;
• slopes;
• bridges and tunnels;
• terraforming;
• elevated ways;
• rivers, canals and runways;
• configurable spacing;
• more than two ways;
• signals and electrification.

The tool adds no persistent state and does not change the savegame format.

Implementation
The second route is not generated tile by tile.
The selected endpoints are offset sideways, and the ordinary way search plans
the route between those offset endpoints. This reuses the existing
is_allowed_step(), cost calculation, slope handling and staircase behaviour
instead of implementing a separate pathfinder.
The main logic is contained in a new double_way_builder_t class in
builder/double_way_builder.cc. It receives the endpoints, side, way descriptor
and flags, and fills two way_builder_t instances.
It does not modify the world and does not depend on the tool, menu or global
state.
Optional forbidden tiles in way_builder_t
The only general engine addition is an optional list of forbidden tiles in
way_builder_t.
The builder keeps its own copy. If the list is empty, existing callers follow
the previous path unchanged. When it is present, is_allowed_step() rejects a
forbidden destination before changing costs or performing the remaining checks.
The change is 29 added lines across wegbauer.h and wegbauer.cc.
This was necessary because offsetting only the endpoints is not sufficient for
bends. I encountered three separate cases:

• The second search could select an equal-cost route crossing the first route.
• After the first route was forbidden, it could move two tiles away around a
  bend.
• After adding a corridor boundary, it could walk around an endpoint and
  return on the opposite side.

The double-way planner therefore forbids the first route, fences the outer edge
of the permitted corridor and caps its ends. The generic builder only sees one
optional list of forbidden positions; all corridor-specific logic remains in
double_way_builder_t.

Relation to prefer_parallel
This does not replace or modify prefer_parallel.
prefer_parallel changes the cost preference when routing near an already
existing way. This tool plans and builds both ways as one operation. I believe
the two features address different use cases and can coexist.

Atomicity within the current scope
There is no general rollback mechanism suitable for this operation, so both
routes are validated before construction begins.
Within the currently supported subset, both builders receive null bridge and
tunnel descriptors, automatic bridges and tunnels are disabled, terraforming is
not requested, and elevated ways and runways are rejected.
Under those restrictions, building the first route does not alter the terrain
required by the second route. The operation therefore has no expected partial
failure path within the accepted scope.

Toolbar integration
menuconf.tab belongs to the pakset and is not part of the main source
repository. Adding entries there would make the tool available only in paksets
that updated their configuration.
The prototype therefore adds the two tools from way_builder_t::fill_menu(), the
same code path that already inserts way tools based on their descriptors.
This is one of the design choices on which I would particularly welcome
feedback.

Verification
The project builds without new warnings.
I added 24 scenario tests. The complete reference suite passes:

Code Select Expand

225/225
The patches were also applied to a clean checkout of r12110 and built from
scratch.
The tests cover:

• straight routes in three orientations and on both sides;
• bends on both sides;
• a tied-cost case and deterministic repetition;
• disjointness of the two routes;
• cost equality against building both routes separately;
• blocked corridors;
• map boundaries;
• insufficient funds;
• malformed parameters;
• scenario restrictions, including a restriction affecting only the second
  route.

Known limitations of the prototype

• The two toolbar buttons currently reuse the way icon and differ only by
  tooltip and position. Proper left/right icons would require suitable artwork.
• I have confirmed that the toolbar opens and is drawn, but I have not completed
  a reliable end-to-end manual check of each button on my development machine.
• The preview is not directly covered by an automated mouse-input test. It uses
  the same planning function as construction.
• Network games require matching binaries. I do not claim compatibility with
  clients that do not know the new tool ID.
• Road and rail have full test coverage; the other accepted waytypes do not yet.
• Forbidden-tile lookup is currently linear and has not been profiled on long
  routes.

Two new English strings are added:

Code Select Expand

Build double way left
Build double way right
No other language files are changed.

Questions
Before extending the implementation, I would particularly appreciate feedback
on two points:

• Is an optional forbidden-tile list in way_builder_t an acceptable general
  engine addition?
• Is offsetting the endpoints and letting the existing way search calculate
  both routes the preferred direction for extending this to slopes and
  bridges, or would another approach be more appropriate?

[prissi]

I think such a tool needs to handle all the diagonal, slopes and crossing cases properly before a release. Also parallel way building without terraform would lead to large detours if routes are found at all. I think, at one point, one would need it own is_allowed step and so on.

I would rather suggest an extra parameter to the fill_menu tools for double way tools (and for the bridge+tunnel too?) So one could exclude double ways for channels and airstrips.

Currently, the waytool is a mess as it handles also powerlines and elevated ways with totally different rules from the rest. I think a new tool for double ways is the right way forward. I wonder if not a proper separation into a single tool, double way tool, elevated tool, and powerline tool would be more future proof and would reduce a lot of the long case trees even more.

On the forbidden tile list: The route searcher does not enter marked tiles. Thus, can one not reuse the marked tiles for this? I am a little unsure, waht the forbidden tile list's purpose. Because, when searching large routes such lists can get long and appending and removing are long operation. So when there are 1 million tiles in the list to check on larger maps, I fear the slowdown and stutter of the display will be large. But I must admid that it has been a very long time since I worked with the waybuilder.

[danivenk]

Also, an important thing IMO for such a tool is the ability to set the separation of the ways.

Sidenote: isn't this already possible with tool scripting?

[victor_18993]

Configurable separation is definitely something I would like to support later.

The prototype fixes it at one tile only to keep the first geometry and test surface manageable. Once diagonals, slopes, crossings and side preservation are reliable, allowing a wider corridor would be a natural extension.

Regarding scripting: a scripted two-click tool could mark preview tiles and invoke the ordinary way-building command twice. However, as far as I can see, it would not have direct access to the two native way_builder_t plans, their complete routes and costs before either command changes the world.

The native implementation is mainly intended to let both routes be planned against the untouched world and validated together, so that failure of the second route cannot leave the first one built.

If there is a scripting API that exposes that planning stage and I have overlooked it, I would be interested in looking at it.