When encountering a no-access node, we need to mark the predecessor e…

…dge as a deadend so other admissibility logic will behave consistently. Graph preparation will not mark these edges as deadends, because deadendiness is access mode specific (e.g. foot may be allowed). Many *::Allowed() methods check for u-turns and depend on the "edgelabel.deadend()" flag to detect u-turns at the end of a dead-end street.
valhalla · Feb 24, 2021 · c1110e5 · c1110e5
1 parent 1ff1856
commit c1110e5
Show file tree

Hide file tree

Showing 5 changed files with 77 additions and 0 deletions.
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -19,6 +19,8 @@
    * FIXED: Honor access mode while matching OSMRestriction with the graph [#2849](https://github.com/valhalla/valhalla/pull/2849)
    * FIXED: Fix compilation errors when boost < 1.68 and libprotobuf < 3.6  [#2878](https://github.com/valhalla/valhalla/pull/2878)
 
+   * FIXED: Allow u-turns at no-access barriers when forced by heading [#2875](https://github.com/valhalla/valhalla/pull/2875)
+
 * **Enhancement**
    * CHANGED: Azure uses ninja as generator [#2779](https://github.com/valhalla/valhalla/pull/2779)
    * ADDED: Support for date_time type invariant for map matching [#2712](https://github.com/valhalla/valhalla/pull/2712)

diff --git a/src/thor/bidirectional_astar.cc b/src/thor/bidirectional_astar.cc
@@ -154,6 +154,10 @@ bool BidirectionalAStar::ExpandForward(GraphReader& graphreader,
   if (!costing_->Allowed(nodeinfo)) {
     const DirectedEdge* opp_edge = nullptr;
     const GraphId opp_edge_id = graphreader.GetOpposingEdgeId(pred.edgeid(), opp_edge, tile);
+    // Mark the predecessor as a deadend to be consistent with how the
+    // edgelabels are set when an *actual* deadend (i.e. some dangling OSM geometry)
+    // is labelled
+    pred.set_deadend(true);
     // Check if edge is null before using it (can happen with regional data sets)
     return opp_edge &&
            ExpandForwardInner(graphreader, pred, nodeinfo, pred_idx,
@@ -362,6 +366,10 @@ bool BidirectionalAStar::ExpandReverse(GraphReader& graphreader,
   if (!costing_->Allowed(nodeinfo)) {
     const DirectedEdge* opp_edge = nullptr;
     const GraphId opp_edge_id = graphreader.GetOpposingEdgeId(pred.edgeid(), opp_edge, tile);
+    // Mark the predecessor as a deadend to be consistent with how the
+    // edgelabels are set when an *actual* deadend (i.e. some dangling OSM geometry)
+    // is labelled
+    pred.set_deadend(true);
     // Check if edge is null before using it (can happen with regional data sets)
     return opp_edge &&
            ExpandReverseInner(graphreader, pred, opp_pred_edge, nodeinfo, pred_idx,

diff --git a/src/thor/timedep_forward.cc b/src/thor/timedep_forward.cc
@@ -70,6 +70,7 @@ bool TimeDepForward::ExpandForward(GraphReader& graphreader,
     const DirectedEdge* opp_edge;
     const GraphId opp_edge_id = graphreader.GetOpposingEdgeId(pred.edgeid(), opp_edge, tile);
     // Check if edge is null before using it (can happen with regional data sets)
+    pred.set_deadend(true);
     return opp_edge &&
            ExpandForwardInner(graphreader, pred, nodeinfo, pred_idx,
                               {opp_edge, opp_edge_id, edgestatus_.GetPtr(opp_edge_id, tile)}, tile,

diff --git a/src/thor/timedep_reverse.cc b/src/thor/timedep_reverse.cc
@@ -93,6 +93,7 @@ bool TimeDepReverse::ExpandReverse(GraphReader& graphreader,
     const DirectedEdge* opp_edge;
     const GraphId opp_edge_id = graphreader.GetOpposingEdgeId(pred.edgeid(), opp_edge, tile);
     EdgeStatusInfo* opp_status = edgestatus_.GetPtr(opp_edge_id, tile);
+    pred.set_deadend(true);
     return ExpandReverseInner(graphreader, pred, opp_pred_edge, nodeinfo, pred_idx,
                               {opp_edge, opp_edge_id, opp_status}, tile, offset_time, destination,
                               best_path);

diff --git a/test/gurka/test_barrier_uturns.cc b/test/gurka/test_barrier_uturns.cc
@@ -0,0 +1,65 @@
+#include "gurka.h"
+#include <gtest/gtest.h>
+
+using namespace valhalla;
+
+class BarrierUturns : public testing::TestWithParam<int> {
+protected:
+  static gurka::map map;
+
+  static void SetUpTestSuite() {
+    const std::string ascii_map = R"(
+  A----B----C
+       1    |
+       D    /
+       |   /
+       E--F)";
+
+    // BD and BE are oneways that lead away, and toward the main road A-B-C
+    const gurka::ways ways = {{"AB", {{"highway", "primary"}}}, {"BC", {{"highway", "primary"}}},
+                              {"BD", {{"highway", "primary"}}}, {"DE", {{"highway", "primary"}}},
+                              {"EF", {{"highway", "primary"}}}, {"CF", {{"highway", "primary"}}}};
+    const gurka::nodes nodes = {{"D", {{"barrier", "fence"}, {"access", "no"}}}};
+    const auto layout = gurka::detail::map_to_coordinates(ascii_map, 25);
+
+    map = gurka::buildtiles(layout, ways, nodes, {}, "test/data/break_through");
+  }
+};
+
+gurka::map BarrierUturns::map = {};
+
+TEST_F(BarrierUturns, break_waypoint) {
+  // Check with type="break" for middle waypoint (the default)
+  auto result1 = gurka::do_action(valhalla::Options::route, map, {"A", "1", "F"}, "auto");
+  gurka::assert::raw::expect_path(result1, {"AB", "BD", "BD", "BC", "CF"});
+}
+
+TEST_F(BarrierUturns, break_thruough_waypoint_into_barrier) {
+  // Check with type="break_through" for middle waypoint
+  auto result1 = gurka::do_action(valhalla::Options::route, map, {"A", "1", "F"}, "auto",
+                                  {{"/locations/1/type", "break_through"}});
+  gurka::assert::raw::expect_path(result1, {"AB", "BD", "BD", "BD", "BC", "CF"});
+}
+
+// Test various algorithms with forced heading
+TEST_P(BarrierUturns, forced_heading_into_barrier_with_algorithm) {
+  const std::string& request =
+      (boost::format(
+           R"({"locations":[{"lat":%s,"lon":%s,"heading":180,"heading_tolerance":45},{"lat":%s,"lon":%s}],
+             "costing":"auto",
+             "date_time": { "type": %d, "value": "2020-10-30T09:00"},
+             "costing_options": { "auto": { "speed_types": ["constrained"]}}})") %
+       std::to_string(map.nodes.at("1").lat()) % std::to_string(map.nodes.at("1").lng()) %
+       std::to_string(map.nodes.at("F").lat()) % std::to_string(map.nodes.at("F").lng()) % GetParam())
+          .str();
+  auto result1 = gurka::do_action(valhalla::Options::route, map, request);
+  gurka::assert::raw::expect_path(result1, {"BD", "BD", "BC", "CF"});
+}
+
+/**
+ * 0 = current time (timedep_forward)
+ * 1 = departure time (timedep_forward)
+ * 2 = arrival time (timedep_reverse)
+ * 3 = invariant time (bidirectional_astar)
+ */
+INSTANTIATE_TEST_SUITE_P(Algorithms, BarrierUturns, testing::Values(0, 1, 2, 3));