Open Source Routing Engine for OpenStreetMap

Overview
 ██▒   █▓ ▄▄▄       ██▓     ██░ ██  ▄▄▄       ██▓     ██▓    ▄▄▄
▓██░   █▒▒████▄    ▓██▒    ▓██░ ██▒▒████▄    ▓██▒    ▓██▒   ▒████▄
 ▓██  █▒░▒██  ▀█▄  ▒██░    ▒██▀▀██░▒██  ▀█▄  ▒██░    ▒██░   ▒██  ▀█▄
  ▒██ █░░░██▄▄▄▄██ ▒██░    ░▓█ ░██ ░██▄▄▄▄██ ▒██░    ▒██░   ░██▄▄▄▄██
   ▒▀█░   ▓█   ▓██▒░██████▒░▓█▒░██▓ ▓█   ▓██▒░██████▒░██████▒▓█   ▓██▒
   ░ ▐░   ▒▒   ▓▒█░░ ▒░▓  ░ ▒ ░░▒░▒ ▒▒   ▓▒█░░ ▒░▓  ░░ ▒░▓  ░▒▒   ▓▒█░
   ░ ░░    ▒   ▒▒ ░░ ░ ▒  ░ ▒ ░▒░ ░  ▒   ▒▒ ░░ ░ ▒  ░░ ░ ▒  ░ ▒   ▒▒ ░
     ░░    ░   ▒     ░ ░    ░  ░░ ░  ░   ▒     ░ ░     ░ ░    ░   ▒
      ░        ░  ░    ░  ░ ░  ░  ░      ░  ░    ░  ░    ░  ░     ░  ░
     ░

Valhalla is an open source routing engine and accompanying libraries for use with OpenStreetMap data. Valhalla also includes tools like time+distance matrix computation, isochrones, elevation sampling, map matching and tour optimization (Travelling Salesman).

Build Status

Linux/MacOs Windows MinGW64 Code Coverage
Circle CI Build Status Valhalla MinGW Build codecov

License

Valhalla, and all of the projects under the Valhalla organization, use the MIT License. Avatar/logo by Jordan

Overview

There are several key features that we hope can differentiate the Valhalla project from other routing and network analysis engines. They are:

  • Open source software, on open source data with a very liberal license. Should allow for transparency in development, encourage contribution and community input, and foster use in other projects.
  • Tiled hierarchical data structure. Should allow users to have a small memory footprint on memory constrained devices, enable offline routing, provide a means for regional extracts and partial updates.
  • Dynamic, runtime costing of edges and vertices within the graph via a plugin architecture. Should allow for customization and alternate route generation.
  • C++ based API. Should allow for cross compilation of the various pieces to enable routing on offline portable devices.
  • A plugin based narrative and manoeuvre generation architecture. Should allow for generation that is customized either to the administrative area or to the target locale.
  • Multi-modal and time-based routes. Should allow for mixing auto, pedestrian, bike and public transportation in the same route or setting a time by which one must arrive at a location.

Organization

The Valhalla organization is comprised of several library modules each responsible for a different function. The layout of the various modules is as follows:

  • Midgard - Basic geographic and geometric algorithms for use in the various other projects.
  • Baldr - The base data structures for accessing and caching tiled route data.
  • Sif - Library used in costing of graph nodes and edges. This can be used as input to loki and thor.
  • Skadi - Library and service for accessing elevation data. This can be used as input to mjolnir or as a standalone service.
  • Mjolnir - Tools for turning open data into Valhalla graph tiles.
  • Loki - Library used to search graph tiles and correlate input locations to an entity within a tile. This correlated entity (edge or vertex) can be used as input to thor.
  • Meili - Library used to for map-matching.
  • Thor - Library used to generate a path through the graph tile hierarchy. This path and attribution along the path can be used as input to odin.
  • Odin - Library used to generate manoeuvres and narrative based on a path. This set of directions information can be used as input to tyr.
  • Tyr - Service used to handle http requests for a route communicating with all of the other valhalla APIs. The service will format output from odin and support json (and eventually protocol buffer) output.
  • Tools - A set command line tools that exercise bits of functionality from the library components above and provide the basis for quality testing and performance benchmarking.
  • Demos - A set of demos which allows interacting with the service and APIs.

Documentation

Documentation is stored in the docs/ folder in this GitHub repository. It can be viewed at valhalla.readthedocs.io.

Installation

[DEPRECATED] Get Valhalla from Personal Package Archive (PPA)

NOTICE: Since we moved to cmake build systems we haven't updated our debian packaging scripts. Because of that the packages in the PPA are very very old. Once we get time to correct this we'll remove this notice but until then we recommend building from source or using docker.

If you are running Ubuntu (trusty or xenial) Valhalla can be installed quickly and easily via PPA. Try the following:

# grab all of the valhalla software from ppa
sudo add-apt-repository -y ppa:valhalla-core/valhalla
sudo apt-get update
sudo apt-get install -y valhalla-bin

Building from Source - Linux

Valhalla uses CMake as build system. When compiling with gcc (GNU Compiler Collection), version 5 or newer is supported.

To install on a Debian or Ubuntu system you need to install its dependencies with:

sudo add-apt-repository -y ppa:valhalla-core/valhalla
sudo apt-get update
sudo apt-get install -y cmake make libtool pkg-config g++ gcc curl unzip jq lcov protobuf-compiler vim-common locales libboost-all-dev libcurl4-openssl-dev zlib1g-dev liblz4-dev libprime-server-dev libprotobuf-dev prime-server-bin
#if you plan to compile with data building support, see below for more info
sudo apt-get install -y libgeos-dev libgeos++-dev libluajit-5.1-dev libspatialite-dev libsqlite3-dev wget sqlite3 spatialite-bin
source /etc/lsb-release
if [[ $(python -c "print(int($DISTRIB_RELEASE > 15))") > 0 ]]; then sudo apt-get install -y libsqlite3-mod-spatialite; fi
#if you plan to compile with python bindings, see below for more info
sudo apt-get install -y python-all-dev

To install on macOS, you need to install its dependencies with Homebrew:

# install dependencies (automake & czmq are required by prime_server)
brew install automake cmake libtool protobuf-c boost-python libspatialite pkg-config sqlite3 jq curl wget czmq lz4 spatialite-tools unzip luajit
curl -o- https://raw.githubusercontent.com/creationix/nvm/v0.33.11/install.sh | bash
# following packages are needed for running Linux compatible scripts
brew install bash coreutils binutils
# Update your PATH env variable to include /usr/local/opt/binutils/bin:/usr/local/opt/coreutils/libexec/gnubin

Now, clone the Valhalla repository

git clone --recurse-submodules https://github.com/valhalla/valhalla.git

Then, build prime_server.

After getting the dependencies install it with:

mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make -j$(nproc) # for macos, use: make -j$(sysctl -n hw.physicalcpu)
sudo make install

Important build options include:

Option Behavior
-DENABLE_DATA_TOOLS (On/Off) Build the data preprocessing tools
-DENABLE_PYTHON_BINDINGS (On/Off) Build the python bindings
-DENABLE_SERVICES (On / Off) Build the HTTP service
-DBUILD_SHARED_LIBS (On / Off) Build static or shared libraries
-DENABLE_COMPILER_WARNINGS (ON / OFF) Build with common compiler warnings (defaults to off)
-DENABLE_WERROR (ON / OFF) Treat compiler warnings as errors (defaults to off). Requires -DENABLE_COMPILER_WARNINGS=ON to take effect.
-DENABLE_BENCHMARKS (ON / OFF) Enable microbenchmarking (defaults to on).
-DENABLE_SANITIZERS (ON / OFF) Build with all the integrated sanitizers (defaults to off).
-DENABLE_ADDRESS_SANITIZER (ON / OFF) Build with address sanitizer (defaults to off).
-DENABLE_UNDEFINED_SANITIZER (ON / OFF) Build with undefined behavior sanitizer (defaults to off).

For more build options run the interactive GUI:

cd build
cmake ..
ccmake ..

For more information on binaries, see Command Line Tools section below and the docs.

Building from Source - Windows

Support for Windows is not yet fully exploited. Building the Valhalla library works flawlessly, as well as the following application modules:

  • TOOLS: utilities to query and benchmark various components
  • DATA_TOOLS: utilities to build input data and handle transit
  • PYTHON_BINDINGS: use all actions (route, isochrones, matrix etc) via the Valhalla Python library (needs a full Python distribution in the PATH)

It's recommended to work with the following toolset:

  • Visual Studio with C++ support
  • Visual Studio Code (easier and lighter to handle)
  • vcpkg to install packages
  • CMake
  1. Install the following packages with vcpkg and your platform triplet (e.g. x64-windows). Note, you can remove all packages after zlib in .\.vcpkg_deps.txt if you don't want to build TOOLS & DATA_TOOLS:
# Basic packages
git -C C:\path\to\vcpkg checkout f4bd6423
cd C:\path\to\project
C:\path\to\vcpkg.exe --triplet x64-windows install "@.vcpkg_deps.txt"
  1. Let CMake configure the build with the required modules enabled. Note, you have to manually link LuaJIT for some reason, e.g. the final command for x64 could look like
"C:\Program Files\CMake\bin\cmake.EXE" --no-warn-unused-cli -DENABLE_TOOLS=ON -DENABLE_DATA_TOOLS=ON -DENABLE_PYTHON_BINDINGS=ON -DENABLE_HTTP=ON -DENABLE_CCACHE=OFF -DENABLE_SERVICES=OFF -DENABLE_BENCHMARKS=OFF -DENABLE_TESTS=OFF -DLUA_LIBRARIES=path\to\vcpkg\installed\x64-windows\lib\lua51.lib -DLUA_INCLUDE_DIR=path\to\vcpkg\installed\x64-windows\include\luajit -DVCPKG_TARGET_TRIPLET=x64-windows -DCMAKE_TOOLCHAIN_FILE=path\to\vcpkg\scripts\buildsystems\vcpkg.cmake -DCMAKE_EXPORT_COMPILE_COMMANDS:BOOL=TRUE -Hpath/to/project -Bpath/to/project/build -G "Visual Studio 16 2019" -T host=x64 -A x64
  1. Run the build for all targets.
cd C:\path\to\project 
cmake -B build .

Running

The following bash should be enough to make some routing data and start a server using it. (Note - if you would like to run an elevation lookup service with Valhalla follow the instructions here).

#download some data and make tiles out of it
#NOTE: you can feed multiple extracts into pbfgraphbuilder
wget http://download.geofabrik.de/europe/switzerland-latest.osm.pbf http://download.geofabrik.de/europe/liechtenstein-latest.osm.pbf
#get the config and setup
mkdir -p valhalla_tiles
valhalla_build_config --mjolnir-tile-dir ${PWD}/valhalla_tiles --mjolnir-tile-extract ${PWD}/valhalla_tiles.tar --mjolnir-timezone ${PWD}/valhalla_tiles/timezones.sqlite --mjolnir-admin ${PWD}/valhalla_tiles/admins.sqlite > valhalla.json
#build routing tiles
#TODO: run valhalla_build_admins?
valhalla_build_tiles -c valhalla.json switzerland-latest.osm.pbf liechtenstein-latest.osm.pbf
#tar it up for running the server
find valhalla_tiles | sort -n | tar cf valhalla_tiles.tar --no-recursion -T -

#grab the demos repo and open up the point and click routing sample
git clone --depth=1 --recurse-submodules --single-branch --branch=gh-pages https://github.com/valhalla/demos.git
firefox demos/routing/index-internal.html &
#NOTE: set the environment pulldown to 'localhost' to point it at your own server

#start up the server
valhalla_service valhalla.json 1
#curl it directly if you like:
curl http://localhost:8002/route --data '{"locations":[{"lat":47.365109,"lon":8.546824,"type":"break","city":"Zürich","state":"Altstadt"},{"lat":47.108878,"lon":8.394801,"type":"break","city":"6037 Root","state":"Untere Waldstrasse"}],"costing":"auto","directions_options":{"units":"miles"}}' | jq '.'

#HAVE FUN!

Contributing

We welcome contributions to valhalla. If you would like to report an issue, or even better fix an existing one, please use the valhalla issue tracker on GitHub.

If you would like to make an improvement to the code, please be aware that all valhalla projects are written mostly in C++11. We use clang-format v7.0 to format the code. We welcome contributions as pull requests to the repository and highly recommend that your pull request include a test to validate the addition/change of functionality.

Note that our CI system checks that code formatting is consistent, and the build will fail if formatting rules aren't followed. Please run ./scripts/format.sh over your code before committing, to auto-format it in the projects preferred style. To spare yourself (and the CIs) pure format commits, you can register it as a pre-commit hook so it lints your changes in-place (and will fail if files were changed, so you'll need to stage and commit again):

cat ./scripts/format.sh > .git/hooks/pre-commit && tail -n +7 scripts/error_on_dirty.sh >> .git/hooks/pre-commit
chmod +x .git/hooks/pre-commit

Also note that we run some clang-tidy linting over the code as well (see .clang-tidy for the list of rules enforced). You can run ./scripts/clang-tidy-only-diff.sh over the code before committing to ensure you haven't added any of the common problems we check for (Note: ./scripts/clang-tidy-only-diff.sh requires the exitence of a compile_commands.json database. You can generate this file by running cmake .. -DCMAKE_EXPORT_COMPILE_COMMANDS=On ... && make.

scripts/clang-tidy-only-diff.sh is run in CI and will fail the build if it detects any issues.

Additionally, a check with ASan is run in CI. We recommend testing with ASan and debug symbols locally prior to commiting, with the -DENABLE_ADDRESS_SANITIZER=ON -DCMAKE_BUILD_TYPE=Debug flags during cmake configuration. As long as leak sanitizer (which is a part of address sanitizer) is not currently supported across different platforms it is disabled in the CI. You can disable it locally with the environment variable ASAN_OPTIONS=detect_leaks=0.

Tests

We highly encourage running and updating the tests to make sure no regressions have been made. We use the Automake test suite to run our tests by simply making the check target:

make check

To run an individual test, make run-<test name> from the build directory or ./test/<testname>

You may check some notes on unit tests

Coverage reports are automatically generated using codecov for each pull request, but you can also build them locally by passing -DENABLE_COVERAGE=On and running make coverage.

Benchmarks

Valhalla includes several microbenchmarks which you can build and run using:

make benchmarks
make run-benchmarks

They are enabled by the -DENABLE_BENCHMARKS=On CMake flag and are currently only available for Linux and MacOS.

Command Line Tools

valhalla_service aka one-shot mode

If you can't (e.g. Windows Server) or don't want to have the full-fledged HTTP API running, you can have the (almost) exact same behavior with the 'valhalla_service' executable in so-called "one-shot" mode. It's simple, just pass the config file, the action (route, isochrone, matrix etc) and the stringified JSON request (or alternatively a file containing the request to circumvent shell command length issues):

valhalla_service valhalla.json isochrone '{"locations":[{"lat":42.552448,"lon":1.564865}],"costing":"auto","contours":[{"time":10,"color":"ff0000"}], "show_locations":true}
# Alternatively you can pass a file with the same contents
valhalla_service valhalla.json isochrone isochrone_request.txt

It's important to note that all Valhalla logs for one-shot mode are piped to stderr while the actual JSON response will be in stdout. To completely silence the logs, pass type: "" to midgard.logging in the config file.

Batch Script Tool

Comments
  • Support routing onto HOV lanes

    Support routing onto HOV lanes

    Definitions

    An HOV2 lane requires the vehicle to have two occupants. An HOV3 lane requires the vehicle to have three occupants. A HOT lane is an HOV lane that optionally allows the driver to pay a toll fee if they don't have the required number of occupants (high occupancy toll).

    When I say "HOV lane" I mean a separately digitized lane that is "HOV only". I am not referring to roadways that are singly digitized and have mixed-usage, e.g., the leftmost lane is HOV but the rightmost lanes are non-HOV.

    Here is an example of an HOT3 lane: https://www.openstreetmap.org/way/815145148#map=19/39.97138/-105.20052

    Issue

    Prior to these changes, only the HOVCost profile could route onto HOV (high occupancy vehicle) lanes.

    With these changes, the caller can specify the types of HOV lanes they'd like to consider for routing. These boolean options will now be honored for the AutoCost profile and ignored by other profiles: include_hov2 include_hov3 include_hot

    Research

    I've spent a fair number of hours going between Overpass-Turbo, OpenStreetMap, TagInfo, and Google Street view. Here are my conclusions:

    HOV lanes are largely found in the US with only a few examples outside. Within OSM, the most correct way to tag an HOV lane is with these two tags: hov=designated and hov:minimum=n, where n is either 2 or 3.

    A fair number of HOV lanes are tagged oneway=alternating or oneway=reversible. For example: https://www.openstreetmap.org/way/66339393#map=18/39.80735/-104.98314 . I live near this area and this HOV road is usually open to traffic going into Denver in the morning and changes direction in the evening for traffic leaving Denver. However, it can randomly be closed for unknown reasons. For this project, I've decided to avoid all HOV roads that are access conditional, time conditional, and/or alternating direction.

    In Europe I see a single HOV2 roadway: https://www.openstreetmap.org/way/198495331. There are many other usages of the hov=designated tag, but the hov:minimum tag is not present. These fall into two categories: bus lanes and parking areas.

    There are a few ways that are tagged hov:minimum=4, e.g., https://www.openstreetmap.org/way/882722563. The preceding and following ways are tagged hov:minimum=2, so I believe the tagging is incorrect.

    I also found a series of ways tagged hov:minimum=6 in the Vancouver area (but do not have hov=designated). This appears to be a bus lane on the rightmost lane.

    In conclusion, the vast majority of HOV lanes for auto's are HOV2/HOV3 and are in the US. Some of these are also tolled (with toll=yes) making them HOT lanes.

    Concept

    The guiding principle is we do not want to route onto an HOV lane unless the user elects to do so. This is because driving on an HOV lane without the correct number of occupants is illegal.

    Also, HOT lanes are seen as conceptually separate from 100% tolled roadways. The thinking is that a pragmatic driver would allow for tolled roads (the default), but would avoid HOT lanes by default.

    Design/Implementation

    ~~From the data side, we need to read/store enough information to identify non-HOV, HOV2, and HOV3 ways. Three states requires 2-bits, so you'll see 2-bits being moved through OSMWay and into DirectedEdge.~~

    Update: After much discussion and experimentation, I was able to modify the implementation to only consume one-bit within the DirectedEdge. Here's how it works:

    We can determine if a way/edge is hov-only by examining the access-mask. An hov-only edge will have the kHOVAccess bit set, but the kAutoAccess bit will not be set. There is a new method that does this determination: DirectedEdge::is_hov_only().

    If DirectedEdge::is_hov_only() returns true, the coder can call DirectedEdge::hov_type() to determine if the edge is HOV2 or HOV3.

    The trick that allows auto's to route onto HOV is to construct the AutoCost as follows: AutoCost(const CostingOptions& costing_options, uint32_t access_mask = (kAutoAccess | kHOVAccess));

    Note the | kHOVAccess. This means the auto-costing will consider HOV edges. AutoCost::EvaluateHOVAllowed() makes the final determination.

    From the input side, we simply capture the use_hot, use_hov2, and use_hov3 booleans (if present). These make their way into DynamicCost.

    Tasklist

    • [x] Add tests
    • [ ] Add #fixes with the issue number that this PR addresses
    • [ ] Update the docs with any new request parameters or changes to behavior described
    • [x] Update the changelog
    • [x] If you made changes to the lua files, update the taginfo too.
    opened by ktatterso 43
  • remove linking to boost

    remove linking to boost

    fixes #3220

    replaces boost.program_options with https://github.com/jarro2783/cxxopts at v2.2.1, v3.x has no stable release yet. that's the last boost we need to link, so we can vendor all the header libs we need and finally remove boost from dependencies!

    so far I only migrated valhalla_build_tiles which has multiple positional args so I wanted to make sure I can straighten that out first with the new lib. I'll wait for initial :+1: before I migrate all other scripts. IMO readability improved, it's a little less convoluted than the boost lib. I tested all options and it works fine.

    boost is still there, I just pulled in the new submodule. would someone be willing to help with the cmake work? I can take care of the other executables.

    tasks:

    • [x] migrate exectuables to use cxxopts and remove all references to boost::program_options in the sources (with the exception of a file which isn't even built anymore: https://github.com/valhalla/valhalla/blob/master/src/valhalla_tiles_for_elevation.cc)
    • [x] vendor header boost libs
    • [x] adapt cmake
    • [x] adapt CI
    • [x] adapt docker
    • [x] adapt documentation
    opened by nilsnolde 39
  • Potential memory leak in Matrix API

    Potential memory leak in Matrix API

    Hello,

    When building bigger matrices >250+ I am having a memory leaks all over the place and it doesn't seem like it's caching issue since I am replaying the same matrices and memory usage increases linearly. Also, when doing these bigger matrices there is a huge memory usage, for example 572x572 is using 12+GB of RAM (and not releasing it once done) - is this normal? If any data/log is needed I can provide!

    Kind regards!

    bug troubleshooting 
    opened by nmalasevic 36
  • Map-Matching: Return top

    Map-Matching: Return top "k" paths

    For short traces (trace_attribute only) allow multiple "alternate" paths to be returned along with each path having a confidence score. Involves updating Viterbi search. API input has addition of max. number of results (default is 1 with no alternates found). Service limit on max. number of alternates and possible limit to number of points in the trace or their length.

    opened by dnesbitt61 36
  • Implement bikeshare

    Implement bikeshare

    https://github.com/valhalla/valhalla/issues/1762

    • [x] Add test

    • [x] Update doc

    Seven months after this issue, here comes the PR of implementation of bike share mode. In general, the bike share algorithm remains a modified A* algorithm, the only difference is that during the expansion, it allows changing the travel mode when a bike share station is met and mode changing cost and penalty are also taken into consideration.

    To guarantee the "under-estimation condition" of A*, we use the minimum of astar_cost among pedestrian mode and bicycle mode.

    To favorize bicycle mode, we use the mode_factor function (just like what's done in transit mode) to penalize a little bit more pedestrian mode. The reason behind that is because the costs between different modes are not "normalized"(I hope you understand what I mean :p ). For example, in some cases, it will cost me "10" to traverse 100 meters by foot, but it may cost me "20" to traverse the same way by bike, which means it favorize a lot the pedestrian mode, that doesn't stick to the reality.

    I must admit that we are not very familiar with the triplegbuilder.cc part, please let us know if you have a better idea about that part.

    About the future work, in order of importance to us:

    • OneToMany
    • Import more bike station data from osm (name, capacity, ref, operator, etc.)
    • Check the compatibility of the bike stations where the bikes are rented and returned

    About the future work after the future work (it's another issue that we'll discuss with you):

    • Inject realtime/predicted data(availabilities, status, etc. ) of bike-share stations

    Bonus PR: https://github.com/valhalla/demos/pull/226 :)

    opened by xlqian 32
  • Segmentation fault in valhalla_build_tiles with latest planet files

    Segmentation fault in valhalla_build_tiles with latest planet files

    I've been getting consistent segmentation faults with the latest planet files from http://planet.openstreetmap.org (both Jan 26 & Feb 1).

    2017/02/03 03:14:36.887454 [WARN] Speed = 150 wayId= 43053918
    2017/02/03 03:14:36.887469 [WARN] Speed = 150 wayId= 43053918
    2017/02/03 03:14:36.887516 [WARN] Speed = 150 wayId= 43053918
    2017/02/03 03:14:36.887530 [WARN] Speed = 150 wayId= 43053918
    2017/02/03 03:15:11.523213 [INFO] Finished
    2017/02/03 03:15:15.294229 [INFO] Enhancing local graph...
    Segmentation fault (core dumped)
    

    Output from the 3 attempts here: https://gist.github.com/ericrwolfe/20af30839dfaf0d0006171399fb3a177

    These are using the latest master branches of all of the mjolnir dependencies (as of 1/27 and 2/2) and a "good" admin.sqlite file obtained from @kevinkreiser after an error with valhalla_build_admins the first time around (with libsqlite3-dev, libsqlite3-mod-spatialite, libspatialite-dev installed): [ERROR] sqlite3_step() error: NOT NULL constraint failed: admin_access.admin_id. Ignore if not using a planet extract.

    The machines being used here are 8 core / 2.4GHz with 160GB SSD + 16gb ram. Seemingly no issues with memory (in fact I've never seen the memory usage go beyond 3gb or so), and the disk space at the time of the segfault with planet + output on the same disk:

    Filesystem      Size  Used Avail Use% Mounted on
    /dev/vda1       156G  138G   18G  89% /
    

    I should also note that I was able to successfully run valhalla_build_tiles on an osm extract of California on the same machines before the planet attempts. However, I reran on California after the segfault and received a different segfault at a different part of the process (shortcut generation): https://gist.github.com/ericrwolfe/99df55f2ed4f4b48971d709640dfd774

    Any ideas or help I can provide debugging here? I'm rerunning on planet with coredump enabled now.

    (Moved issue over from https://github.com/valhalla/mjolnir/issues/606)

    /cc @dnesbitt61

    mjolnir 
    opened by ericrwolfe 32
  • Valhalla build failing with latest OSM files (std::bad_alloc)

    Valhalla build failing with latest OSM files (std::bad_alloc)

    Hi there.

    I am quite new to Valhalla and I spent the last 3-4 weeks going crazy trying to build my first planet tiles. My builds were always failing with several issues (more info in this issue).

    In the end, I managed to make it work with an older pbf file (from July 20). So I was wondering if the latest planet files have some kind of issue or some data that valhalla_build_tiles doesn't like.

    The common thing I noticed between my attempts was this error in the build stage.

    [ERROR] Failed tile 2/517753/0: std::bad_alloc

    Some notes:

    • the failing tile number was not always the same
    • the build would not stop at this point. It would fail later on with different types of errors (se below)

    On the top of my head, the errors I have seen are:

    • `std::exception``
    • std::runtime_error
    • segmentation fault
    • The process being killed by OOM killer

    (The errors would happen randomly in my different attemps).

    In my latest successful attempt, the 'bad_alloc' error did not show up. This is why I think this must be related somehow.

    From the logs that I kept, here are some of the bad_alloc I have seen (from different builds)

    [ERROR] Failed tile 2/517753/0: std::bad_alloc
    [ERROR] Failed tile 2/517741/0: std::bad_alloc
    [ERROR] Failed tile 2/693716/0: std::bad_alloc
    

    As you can see, it did not always happen on the same tile.

    The pbf files I have tried and have failed:

    • Sept 11
    • Sept 18
    • Sept 25

    I hope this helps.

    opened by bboure 30
  • de-singleton tile extract in graphreader

    de-singleton tile extract in graphreader

    fixes #3117

    I started with this on the side, working on it here and there. to re-iterate: we want to be able to load other tile extracts while a consumer application is running (e.g. valhalla_service). in #3117 @kevinkreiser proposed to use a fixed-width index file storing the tile_id and byte offset in the final tar file which the graphreader can read first (if available) to really fast initialize the tile_extract_t (faster because it does not have to scan through the entire tar file thanks to the index file).

    tasks:

    • [x] set up python script
    • [x] tests python (needs some refactoring)
    • [x] adapt graphreader to read the index file first if present
    • [x] tests graphreader
    • [x] some open questions:
      • ~~this (currently) does not work for existing extracts, so far it only builds an extract from mjolnir.tile_dir. is that fine with you? we could also add that ability and it sorta was what @kevinkreiser initially suggested~~ -> not necessary IMO
      • ~~where to add this functionality: python bindings for sure IMO, what about valhalla_service?~~ -> subsequent PRs

    @kevinkreiser I didn't do much yet on the c++ side, will comment a bit on the files, a few pointers would be cool:)

    example commandline: python scripts/valhalla_build_extract --config site/valhalla.json

    opened by nilsnolde 29
  • Crash of valhalla_build_tiles on OSM planet

    Crash of valhalla_build_tiles on OSM planet

    Hello! Some time ago valhalla_build_tiles core dumped on latest OSM planet. Release tag is 3.1.2. Crash is reproduced on OSM planets approximately since august, 15.

    Callstack:

    #0  0x00007ff383f737ff in raise () from /usr/lib64/libc.so.6
    #1  0x00007ff383f5dc35 in abort () from /usr/lib64/libc.so.6
    #2  0x00007ff384b4909b in __gnu_cxx::__verbose_terminate_handler() [clone .cold.1] () from /usr/lib64/libstdc++.so.6
    #3  0x00007ff384b4f53c in __cxxabiv1::__terminate(void (*)()) () from /usr/lib64/libstdc++.so.6
    #4  0x00007ff384b4f597 in std::terminate() () from /usr/lib64/libstdc++.so.6
    #5  0x00007ff384b4f7f8 in __cxa_throw () from /usr/lib64/libstdc++.so.6
    #6  0x00007ff384b4b06b in std::__throw_out_of_range_fmt(char const*, ...) [clone .cold.5] ()
       from /usr/lib64/libstdc++.so.6
    #7  0x00000000004ece9f in std::vector<valhalla::mjolnir::OSMWayNode, std::allocator<valhalla::mjolnir::OSMWayNode> >::_M_range_check (__n=<optimized out>, this=0x7ffc42def870)
        at /opt/rh/gcc-toolset-9/root/usr/include/c++/9/bits/char_traits.h:365
    #8  std::vector<valhalla::mjolnir::OSMWayNode, std::allocator<valhalla::mjolnir::OSMWayNode> >::at (
        __n=<optimized out>, this=0x7ffc42def870) at /opt/rh/gcc-toolset-9/root/usr/include/c++/9/bits/stl_vector.h:1091
    #9  valhalla::midgard::sequence<valhalla::mjolnir::OSMWayNode>::iterator::operator valhalla::mjolnir::OSMWayNode (
        this=<optimized out>) at /usr/src/debug/valhalla/midgard/sequence.h:467
    #10 valhalla::midgard::sequence<valhalla::mjolnir::OSMWayNode>::iterator::operator* (this=<optimized out>)
        at /usr/src/debug/valhalla/midgard/sequence.h:473
    #11 (anonymous namespace)::ConstructEdges(const std::string &, const std::string &, const std::string &, const std::string &, const std::function<valhalla::baldr::GraphId(const valhalla::mjolnir::OSMNode&)> &, bool) (ways_file=...,
        way_nodes_file=..., nodes_file=..., edges_file=..., graph_id_predicate=..., infer_turn_channels=true)
        at /usr/src/debug/src/mjolnir/graphbuilder.cc:212
    ...
    

    It seems that valhalla_build_tiles crashes on this line of code: https://github.com/valhalla/valhalla/blob/master/src/mjolnir/graphbuilder.cc#L208

    Here current_way_node_index somehow becomes equal to way_nodes size.

    I tried to investigate where current_way_node_index is incremented incorrectly, but for now I have no idea. Maybe you have any assumptions how to localize the problem? I couldn't reproduce it on small parts of world (England, part of Europe, etc). It is reproduced only on full planet, so it is impossible to debug.

    bug 
    opened by mesozoic-drones 28
  • Narrative/Directions Translations via TranslateWiki

    Narrative/Directions Translations via TranslateWiki

    @nemobis @nikerabbit are main contributors to the TranslateWiki project and I'd reached out to them a few weeks ago at this point to see what it would take to create a project for valhalla's narrative file

    They seem to support json but there are open questions about translating something that isnt just a file of strings but does its own text replacement etc within the routing engine.

    I just wanted to create this issue to get the ball rolling on discussing feasibility of such a project.

    opened by kevinkreiser 28
  • admin builder with c geos

    admin builder with c geos

    #3617 #3624 are just some examples of the continual problems we have with using the c++ api for libgeos. add to that the latest LTS of ubuntu has a broken version of libgeos (static linking for the c lib and completely missing parts of the library for the c++ lib) and it seems @nilsnolde was on to something when he said we should replace it in #3396. so this pr should be somethign that fixes #3396

    i recently updated to ubuntu 22.04 and am now stuck with broken valhalla for it. building geos from source is fine but its a foundational library in many of the tools we use on the project and are used elsewhere. essentially "one does not simply" swap out just libgeos with ones own build..

    so this pr is a crack at what nils suggested. i know he took a crack too but hopefully between the two of us we can get this dependency removed.

    .. and it turns out we we are heavily reliant upon the st_buffer(0) trick. and of course boost geometry bindings dont really support geometric coordinates for many algorithms including buffer. so we've changed tracks and are working on using geos via its c api. just porting the c++ to the c api which should at least remove the instability between releases and os's

    opened by kevinkreiser 27
  • move to GitHub pages

    move to GitHub pages

    • moves the documentation to Github pages, see https://valhalla.github.io/valhalla/ (I pushed already and @kevinkreiser registered it in the settings)
    • changes the theme to smth more modern than readthedocs theme (better navigation, vastly better search, dark mode)
    • moves the MD files into ./docs/docs, which is necessary when we want to keep the mkdocs.yml in the docs directory, which I'd prefer
    • adds some previously missing documents (e.g. incidents.md)
    • adds a Github Action to deploy the docs on master pushes

    @drewda would you mind removing the docs from readthedocs.io once this is merged? Then there won't be any ambiguity with a stale documentation still being live there.

    opened by nilsnolde 0
  • vehicle access

    vehicle access

    Valhalla routes bicycle, where vehicle=forestry is tagged on a track|path. I have searched a bit and found taginfo.json. Vehicle is not mentioned there. Maybe it is missing somewhere?

    PS: I should say, I used valhalla from the OSM site. And, maybe the access tags in place are used, Idk. If the directions said: push the bike there, I would know.

    opened by hungerburg 6
  • Update docs

    Update docs

    fixes #3797

    Let me know if you find anything is too aggressive here. IMO it looks quite a bit less intimidating to newcomers but still preserves all info that was there previously.

    opened by nilsnolde 9
  • Move to C++17

    Move to C++17

    As discussed in length over in #2009, the consensus is to at least move to C++17, before moving on to C++20 (find arguments in the linked issue). Also pending feedback by @dnesbitt61 and maybe @PhilippVoigt .

    I went through the improvements of C++14 to C++17 and collected some obvious TODOs for us (well, rather me, never wrote anything in 17). Feel free to edit this issue if you’re allowed, or just comment, I’ll add it to this top level list to keep it comprehensive.

    • [ ] (nils) boost::optional -> std::optional
    • [ ] (nils) std::filesystem maybe to replace our home baked one (at least to some degree)
    • [ ] (nils) not sure if we use variants? Don’t think so actually..
    • [ ] (nils) there’s a new std::clamp which sounds like it could remove our default range struct for input param processing
    • [ ] (nils) scoped_lock replaces lock_guard and is variadic now
    • [ ] (molind) make use of string_view (eg for locales), can be good for constexpr. Generally keep using const string& if the arg is used for functions expecting std::string (expensive conversion) or C strings (null termination not guaranteed)

    And a few things I noticed which we might want to watch out for:

    • emplace for sequences now returns a reference to the new element
    • string::data() can return mutable pointer to the char
    • shared_ptr for arrays now available
    opened by nilsnolde 4
  • Forward Search Path Exhausted for Truck costing

    Forward Search Path Exhausted for Truck costing

    We're running into an issue where the forward search path is exhausted, but only for truck costing on this route:

    Demo Route

    The link above returns a route for auto, but if you click on the truck costing, it returns an error message.

    In our logs, we can see the forward search is exhausted. However enabling extended_search does not produce a route, because pruning_disabled_at_destination_ is false. If we remove that check, we get the expected result, but it's unclear why forward searching is exhausted here, and only for truck costing but not auto.

    This is likely related to changes in https://github.com/valhalla/valhalla/pull/2936. Any input is appreciated, thank you!

    bug investigate 
    opened by rochadt 2
Releases(3.2.0)
  • 3.2.0(Oct 27, 2022)

    Release Date: 2022-10-26 Valhalla 3.2.0

    • Removed

      • REMOVED: "build-*" docker image to decrease complexity #3689
    • Bug Fix

      • FIXED: Fix precision losses while encoding-decoding distance parameter in openlr #3374
      • FIXED: Fix bearing calculation for openlr records #3379
      • FIXED: Some refactoring that was proposed for the PR 3379 3381
      • FIXED: Avoid calling out "keep left/right" when passing an exit 3349
      • FIXED: Fix iterator decrement beyond begin() in GeoPoint::HeadingAtEndOfPolyline() method #3393
      • FIXED: Add string for Use:kPedestrianCrossing to fix null output in to_string(Use). #3416
      • FIXED: Remove simple restrictions check for pedestrian cost calculation. #3423
      • FIXED: Parse "highway=busway" OSM tag: https://wiki.openstreetmap.org/wiki/Tag:highway%3Dbusway #3413
      • FIXED: Process int_ref irrespective of use_directions_on_ways_ #3446
      • FIXED: workaround python's ArgumentParser bug to not accept negative numbers as arguments #3443
      • FIXED: Undefined behaviour on some platforms due to unaligned reads #3447
      • FIXED: Fixed undefined behavior due to invalid shift exponent when getting edge's heading #3450
      • FIXED: Use midgard::unaligned_read in GraphTileBuilder::AddSigns #3456
      • FIXED: Relax test margin for time dependent traffic test #3467
      • FIXED: Fixed missed intersection heading #3463
      • FIXED: Stopped putting binary bytes into a string field of the protobuf TaggedValue since proto3 protects against that for cross language support #3468
      • FIXED: valhalla_service uses now loki logging config instead of deprecated tyr logging #3481
      • FIXED: Docker image valhalla/valhalla:run-latest: conan error + python integration #3485
      • FIXED: fix more protobuf unstable 3.x API #3494
      • FIXED: fix one more protobuf unstable 3.x API #3501
      • FIXED: Fix valhalla_build_tiles imports only bss from last osm file #3503
      • FIXED: Fix total_run_stat.sh script. #3511
      • FIXED: Both hov:designated and hov:minimum have to be correctly set for the way to be considered hov-only #3526
      • FIXED: Wrong out index in route intersections #3541
      • FIXED: fix valhalla_export_edges: missing null columns separator #3543
      • FIXED: Removed/updated narrative language aliases that are not IETF BCP47 compliant #3546
      • FIXED: Wrong predecessor opposing edge in dijkstra's expansion #3528
      • FIXED: exit and exit_verbal in Russian locale should be same #3545
      • FIXED: Skip transit tiles in hierarchy builder #3559
      • FIXED: Fix some country overrides in adminconstants and add a couple new countries. #3578
      • FIXED: Improve build errors reporting #3579
      • FIXED: Fix "no elevation" values and /locate elevation response #3571
      • FIXED: Build tiles with admin/timezone support on Windows #3580
      • FIXED: admin "Saint-Martin" changed name to "Saint-Martin (France)" #3619
      • FIXED: openstreetmapspeeds global config with nulls now supported #3621
      • FIXED: valhalla_run_matrix was failing (could not find proper max_matrix_distance) #3635
      • FIXED: Removed duplicate degrees/radians constants #3642
      • FIXED: Forgot to adapt driving side and country access rules in #3619 #3652
      • FIXED: DateTime::is_conditional_active(...) incorrect end week handling #3655
      • FIXED: TimeDistanceBSSMatrix: incorrect initialization for destinations#3659
      • FIXED: Some interpolated points had invalid edge_index in trace_attributes response #3646
      • FIXED: Use a small node snap distance in map-matching. FIxes issue with incorrect turn followed by Uturn. #3677
      • FIXED: Conan error when building Docker image. #3689
      • FIXED: Allow country overrides for sidewalk #3711
      • FIXED: CostMatrix incorrect tile usage with oppedge. #3719
      • FIXED: Fix elevation serializing #3735
      • FIXED: Fix returning a potentially uninitialized value in PointXY::ClosestPoint #3737
      • FIXED: Wales and Scotland name change. #3746
      • FIXED: Pedestrian crossings are allowed for bikes #3751
      • FIXED: Fix for Mac OSx. Small update for the workdir for the admin_sidewalk_override test. #3757
      • FIXED: Add missing service road case from GetTripLegUse method. #3763
      • FIXED: Fix TimeDistanceMatrix results sequence #3738
      • FIXED: Fix status endpoint not reporting that the service is shutting down #3785
      • FIXED: Fix TimdDistanceMatrix SetSources and SetTargets #3792
      • FIXED: Added highway and surface factor in truckcost #3590
      • FIXED: Potential integer underflow in file suffix generation #3783
      • FIXED: Building Valhalla as a submodule #3781
      • FIXED: Fixed invalid time detection in GetSpeed #3800
      • FIXED: Osmway struct update: added up to 33 and not 32 #3808
    • Enhancement

      • CHANGED: Pronunciation for names and destinations #3132
      • CHANGED: Requested code clean up for phonemes PR #3356
      • CHANGED: Refactor Pronunciation class to struct #3359
      • ADDED: Added support for probabale restrictions #3361
      • CHANGED: Refactored the verbal text formatter to handle logic for street name and sign #3369
      • CHANGED: return "version" and "tileset_age" on parameterless /status call #3367
      • CHANGED: de-singleton tile_extract by introducing an optional index.bin file created by valhalla_build_extract #3281
      • CHANGED: implement valhalla_build_elevation in python and add more --from-geojson & --from-graph options #3318
      • ADDED: Add boolean parameter to clear memory for edge labels from thor. #2789
      • CHANGED: Do not create statsd client in workers if it is not configured #3394
      • ADDED: Import of Bike Share Stations information in BSS Connection edges #3411
      • ADDED: Add heading to PathEdge to be able to return it on /locate #3399
      • ADDED: Add prioritize_bidirectional option for fast work and correct ETA calculation for depart_at date_time type. Smoothly stop using live-traffic #3398
      • CHANGED: Minor fix for headers #3436
      • CHANGED: Use std::multimap for polygons returned for admin and timezone queries. Improves performance when building tiles. #3427
      • CHANGED: Refactored GraphBuilder::CreateSignInfoList #3438
      • ADDED: Add support for LZ4 compressed elevation tiles #3401
      • CHANGED: Rearranged some of the protobufs to remove redundancy #3452
      • CHANGED: overhaul python bindings #3380
      • CHANGED: Removed all protobuf defaults either by doing them in code or by relying on 0 initialization. Also deprecated best_paths and do_not_track #3454
      • ADDED: isochrone action for /expansion endpoint to track dijkstra expansion #3215
      • CHANGED: remove boost from dependencies and add conan as prep for #3346 #3459
      • CHANGED: Remove boost.program_options in favor of cxxopts header-only lib and use conan to install header-only boost. #3346
      • CHANGED: Moved all protos to proto3 for internal request/response handling #3457
      • CHANGED: Allow up to 32 outgoing link edges on a node when reclassifying links #3483
      • CHANGED: Reuse sample::get implementation #3471
      • ADDED: Beta support for interacting with the http/bindings/library via serialized and pbf objects respectively #3464
      • CHANGED: Update xcode to 12.4.0 #3492
      • ADDED: Add JSON generator to conan #3493
      • CHANGED: top_speed option: ignore live speed for speed based penalties #3460
      • ADDED: Add include_construction option into the config to include/exclude roads under construction from the graph #3455
      • CHANGED: Refactor options protobuf for Location and Costing objects #3506
      • CHANGED: valhalla.h and config.h don't need cmake configuration #3502
      • ADDED: New options to control what fields of the pbf are returned when pbf format responses are requested #3207
      • CHANGED: Rename tripcommon to common #3516
      • ADDED: Indoor routing - data model, data processing. #3509
      • ADDED: On-demand elevation tile fetching #3391
      • CHANGED: Remove many oneof uses from the protobuf api where the semantics of optional vs required isnt necessary #3527
      • ADDED: Indoor routing maneuvers #3519
      • ADDED: Expose reverse isochrone parameter for reverse expansion #3528
      • CHANGED: Add matrix classes to thor worker so they persist between requests. #3560
      • CHANGED: Remove max_matrix_locations and introduce max_matrix_location_pairs to configure the allowed number of total routes for the matrix action for more flexible asymmetric matrices #3569
      • CHANGED: modernized spatialite syntax #3580
      • ADDED: Options to generate partial results for time distance matrix when there is one source (one to many) or one target (many to one). #3181
      • ADDED: Enhance valhalla_build_elevation with LZ4 recompression support #3607
      • CHANGED: removed UK admin and upgraded its constituents to countries #3619
      • CHANGED: expansion service: only track requested max time/distance #3532
      • ADDED: Shorten down the request delay, when some sources/targets searches are early aborted #3611
      • ADDED: add pre-commit hook for running the format.sh script #3637
      • CHANGED: upgrade pybind11 to v2.9.2 to remove cmake warning #3658
      • ADDED: tests for just_gtfs reading and writing feeds #3665
      • CHANGED: Precise definition of types of edges on which BSS could be projected #3658
      • CHANGED: Remove duplicate implementation of adjust_scores #3673
      • ADDED: convert GTFS data into protobuf tiles #3629
      • CHANGED: Use starts_with() instead of substr(0, N) getting and comparing to prefix #3702
      • ADDED: Ferry support for HGV #3710
      • ADDED: Linting & formatting checks for Python code #3713
      • CHANGED: rename Turkey admin to Türkiye #3720
      • CHANGED: bumped vcpkg version to "2022.08.15" #3754
      • CHANGED: chore: Updates to clang-format 11.0.0 #3533
      • CHANGED: Ported trace_attributes serialization to RapidJSON. #3333
      • ADDED: Add helpers for DirectedEdgeExt and save them to file in GraphTileBuilder #3562
      • ADDED: Fixed Speed costing option #3576
      • ADDED: axle_count costing option for hgv #3648
      • ADDED: Matrix action for gurka #3793
      • ADDED: Add warnings array to response. #3588
      • CHANGED: Templatized TimeDistanceMatrix for forward/reverse search #3773
      • CHANGED: Templatized TimeDistanceBSSMatrix for forward/reverse search #3778
      • CHANGED: error code 154 shows distance limit in error message #3779
    Source code(tar.gz)
    Source code(zip)
  • 3.1.4(Oct 7, 2021)

    Release Date: 2021-10-07 Valhalla 3.1.4

    • Removed

    • Bug Fix

      • FIXED: Revert default speed boost for turn channels #3232
      • FIXED: Use the right tile to get country for incident #3235
      • FIXED: Fix factors passed to RelaxHierarchyLimits #3253
      • FIXED: Fix TransitionCostReverse usage #3260
      • FIXED: Fix Tagged Value Support in EdgeInfo #3262
      • FIXED: TransitionCostReverse fix: revert internal_turn change #3271
      • FIXED: Optimize tiles usage in reach-based pruning #3294
      • FIXED: Slip lane detection: track visited nodes to avoid infinite loops #3297
      • FIXED: Fix distance value in a 0-length road #3185
      • FIXED: Trivial routes were broken when origin was node snapped and destnation was not and vice-versa for reverse astar #3299
      • FIXED: Tweaked TestAvoids map to get TestAvoidShortcutsTruck working #3301
      • FIXED: Overflow in sequence sort #3303
      • FIXED: Setting statsd tags in config via valhalla_build_config #3225
      • FIXED: Cache for gzipped elevation tiles #3120
      • FIXED: Current time conversion regression introduced in unidirectional algorithm refractor #3278
      • FIXED: Make combine_route_stats.py properly quote CSV output (best practice improvement) #3328
      • FIXED: Merge edge segment records in map matching properly so that resulting edge indices in trace_attributes are valid #3280
      • FIXED: Shape walking map matcher now sets correct edge candidates used in the match for origin and destination location #3329
      • FIXED: Better hash function of GraphId #3332
    • Enhancement

      • CHANGED: Favor turn channels more #3222
      • CHANGED: Rename valhalla::midgard::logging::LogLevel enumerators to avoid clash with common macros #3237
      • CHANGED: Move pre-defined algorithm-based factors inside RelaxHierarchyLimits #3253
      • ADDED: Reject alternatives with too long detours #3238
      • ADDED: Added info to /status endpoint #3008
      • ADDED: Added stop and give_way/yield signs to the data and traffic signal fixes #3251
      • ADDED: use_hills for pedestrian costing, which also affects the walking speed #3234
      • CHANGED: Fixed cost threshold fot bidirectional astar. Implemented reach-based pruning for suboptimal branches #3257
      • ADDED: Added exclude_unpaved request parameter #3240
      • ADDED: Added support for routing onto HOV/HOT lanes via request parameters include_hot, include_hov2, and include_hov3 #3273
      • ADDED: Add Z-level field to EdgeInfo. #3261
      • CHANGED: Calculate stretch threshold for alternatives based on the optimal route cost #3276
      • ADDED: Add preferred_z_level as a parameter of loki requests. #3270
      • ADDED: Add preferred_layer as a parameter of loki requests. #3270
      • ADDED: Exposing service area names in passive maneuvers. #3277
      • ADDED: Added traffic signal and stop sign check for stop impact. These traffic signals and stop sign are located on edges. #3279
      • CHANGED: Improved sharing criterion to obtain more reasonable alternatives; extended alternatives search #3302
      • ADDED: pull ubuntu:20.04 base image before building #3233
      • CHANGED: Improve Loki nearest-neighbour performance for large radius searches in open space #3233
      • ADDED: testing infrastructure for scripts and valhalla_build_config tests #3308
      • ADDED: Shape points and information about where intermediate locations are placed along the legs of a route #3274
      • CHANGED: Improved existing hov lane transition test case to make more realistic #3330
      • CHANGED: Update python usage innall scripts to python3 #3337
      • ADDED: Added exclude_cash_only_tolls request parameter #3341
      • CHANGED: Update api-reference for street_names #3342
      • ADDED: Disable msse2 flags when building on Apple Silicon chip #3327
    Source code(tar.gz)
    Source code(zip)
  • 3.1.3(Jul 20, 2021)

    Release Date: 2021-07-20 Valhalla 3.1.3

    • Removed

      • REMOVED: Unused overloads of to_response function #3167
    • Bug Fix

      • FIXED: Fix heading on small edge #3114
      • FIXED: Added support for access=psv, which disables routing on these nodes and edges unless the mode is taxi or bus #3107
      • FIXED: Disables logging in CI to catch issues #3121
      • FIXED: Fixed U-turns through service roads #3082
      • FIXED: Added forgotten penalties for kLivingStreet and kTrack for pedestrian costing model #3116
      • FIXED: Updated the reverse turn bounds #3122
      • FIXED: Missing fork maneuver #3134
      • FIXED: Update turn channel logic to call out specific turn at the end of the turn channel if needed #3140
      • FIXED: Fixed cost thresholds for TimeDistanceMatrix. #3131
      • FIXED: Use distance threshold in hierarchy limits for bidirectional astar to expand more important lower level roads #3156
      • FIXED: Fixed incorrect dead-end roundabout labels. #3129
      • FIXED: googletest wasn't really updated in #3166 #3187
      • FIXED: Minor fix of benchmark code #3190
      • FIXED: avoid_polygons intersected edges as polygons instead of linestrings [#3194]((https://github.com/valhalla/valhalla/pull/3194)
      • FIXED: when binning horizontal edge shapes using single precision floats (converted from not double precision floats) allowed for the possiblity of marking many many tiles no where near the shape #3204
      • FIXED: Fix improper iterator usage in ManeuversBuilder #3205
      • FIXED: Modified approach for retrieving signs from a directed edge #3166 #3208
      • FIXED: Improve turn channel classification: detect slip lanes #3196
      • FIXED: Compatibility with older boost::optional versions #3219
      • FIXED: Older boost.geometry versions don't have correct() for geographic rings #3218
      • FIXED: Use default road speed for bicycle costing so traffic does not reduce penalty on high speed roads. #3143
    • Enhancement

      • CHANGED: Refactor base costing options parsing to handle more common stuff in a one place #3125
      • CHANGED: Unified Sign/SignElement into sign.proto #3146
      • ADDED: New verbal succinct transition instruction to maneuver & narrativebuilder. Currently this instruction will be used in place of a very long street name to avoid repetition of long names #2844
      • ADDED: Added oneway support for pedestrian access and foot restrictions #3123
      • ADDED: Exposing rest-area names in passive maneuvers #3172
      • CHORE: Updates robin-hood-hashing third-party library
      • ADDED: Support barrier=yes|swing_gate|jersey_barrier tags #3154
      • ADDED: Maintain access=permit|residents tags as private #3149
      • CHANGED: Replace avoid_* API parameters with more accurate exclude_* #3093
      • ADDED: Penalize private gates #3144
      • CHANGED: Renamed protobuf Sign/SignElement to TripSign/TripSignElement #3168
      • CHORE: Updates googletest to release-1.11.0 #3166
      • CHORE: Enables -Wall on sif sources #3178
      • ADDED: Allow going through accessible barrier=bollard and penalize routing through it, when the access is private #3175
      • ADDED: Add country code to incident metadata #3169
      • CHANGED: Use distance instead of time to check limited sharing criteria #3183
      • ADDED: Introduced a new via_waypoints array on the leg in the osrm route serializer that describes where a particular waypoint from the root-level array matches to the route. #3189
      • ADDED: Added vehicle width and height as an option for auto (and derived: taxi, bus, hov) profile (https://github.com/valhalla/valhalla/pull/3179)
      • ADDED: Support for statsd integration for basic error and requests metrics #3191
    Source code(tar.gz)
    Source code(zip)
  • 3.1.2(May 26, 2021)

    Release Date: 2021-05-26 Valhalla 3.1.2

    • Removed

    • Bug Fix

      • FIXED: Change unnamed road intersections from being treated as penil point u-turns #3084
      • FIXED: Fix TimeDepReverse termination and path cost calculation (for arrive_by routing) #2987
      • FIXED: Isochrone (::Generalize()) fix to avoid generating self-intersecting polygons #3026
      • FIXED: Handle day_on/day_off/hour_on/hour_off restrictions #3029
      • FIXED: Apply conditional restrictions with dow only to the edges when routing #3039
      • FIXED: Missing locking in incident handler needed to hang out to scop lock rather than let the temporary disolve #3046
      • FIXED: Continuous lane guidance fix #3054
      • FIXED: Fix reclassification for "shorter" ferries and rail ferries (for Chunnel routing issues) #3038
      • FIXED: Incorrect routing through motor_vehicle:conditional=destination. #3041
      • FIXED: Allow destination-only routing on the first-pass for non bidirectional A* algorithms. #3085
      • FIXED: Highway/ramp lane bifurcation #3088
      • FIXED: out of bound access of tile hierarchy in base_ll function in graphheader #3089
      • FIXED: include shortcuts in avoid edge set for avoid_polygons #3090
    • Enhancement

      • CHANGED: Refactor timedep forward/reverse to reduce code repetition #2987
      • CHANGED: Sync translation files with Transifex command line tool #3030
      • CHANGED: Use osm tags in links reclassification algorithm in order to reduce false positive downgrades #3042
      • CHANGED: Use CircleCI XL instances for linux based builds #3043
      • ADDED: ci: Enable undefined sanitizer #2999
      • ADDED: Optionally pass preconstructed graphreader to connectivity map #3046
      • CHANGED: ci: Skip Win CI runs for irrelevant files #3014
      • ADDED: Allow configuration-driven default speed assignment based on edge properties #3055
      • CHANGED: Use std::shared_ptr in case if ENABLE_THREAD_SAFE_TILE_REF_COUNT is ON. #3067
      • CHANGED: Reduce stop impact when driving in parking lots #3051
      • ADDED: Added another through route test #3074
      • ADDED: Adds incident-length to metadata proto #3083
      • ADDED: Do not penalize gates that have allowed access #3078
      • ADDED: Added missing k/v pairs to taginfo.json. Updated PR template. #3101
      • CHANGED: Serialize isochrone 'contour' properties as floating point so they match user supplied value #3078
      • NIT: Enables compiler warnings as errors in midgard module #3104
    Source code(tar.gz)
    Source code(zip)
  • 3.1.1(Apr 21, 2021)

    Release Date: 2021-04-21 Valhalla 3.1.1

    • Removed

      • REMOVED: The tossing of private roads in #1960 was too aggressive and resulted in a lot of no routes. Reverted this logic. #2934
      • REMOVED: stray references to node bindings #3012
    • Bug Fix

      • FIXED: Fix compression_utils.cc::inflate(...) throw - make it catchable #2839
      • FIXED: Fix compiler errors if HAVE_HTTP not enabled #2807
      • FIXED: Fix alternate route serialization #2811
      • FIXED: Store restrictions in the right tile #2781
      • FIXED: Failing to write tiles because of racing directory creation #2810
      • FIXED: Regression in stopping expansion on transitions down in time-dependent routes #2815
      • FIXED: Fix crash in loki when trace_route is called with 2 locations.#2817
      • FIXED: Mark the restriction start and end as via ways to fix IsBridgingEdge function in Bidirectional Astar #2796
      • FIXED: Dont add predictive traffic to the tile if it's empty #2826
      • FIXED: Fix logic bidirectional astar to avoid double u-turns and extra detours #2802
      • FIXED: Re-enable transition cost for motorcycle profile #2837
      • FIXED: Increase limits for timedep_* algorithms. Split track_factor into edge factor and transition penalty #2845
      • FIXED: Loki was looking up the wrong costing enum for avoids #2856
      • FIXED: Fix way_ids -> graph_ids conversion for complex restrictions: handle cases when a way is split into multiple edges #2848
      • FIXED: Honor access mode while matching OSMRestriction with the graph #2849
      • FIXED: Ensure route summaries are unique among all returned route/legs #2874
      • FIXED: Fix compilation errors when boost < 1.68 and libprotobuf < 3.6 #2878
      • FIXED: Allow u-turns at no-access barriers when forced by heading #2875
      • FIXED: Fixed "No route found" error in case of multipoint request with locations near low reachability edges #2914
      • FIXED: Python bindings installation #2751
      • FIXED: Skip bindings if there's no Python development version #2893
      • FIXED: Use CMakes built-in Python variables to configure installation #2931
      • FIXED: Sometimes emitting zero-length route geometry when traffic splits edge twice #2943
      • FIXED: Fix map-match segfault when gps-points project very near a node #2946
      • FIXED: Use kServiceRoad edges while searching for ferry connection #2933
      • FIXED: Enhanced logic for IsTurnChannelManeuverCombinable #2952
      • FIXED: Restore compatibility with gcc 6.3.0, libprotobuf 3.0.0, boost v1.62.0 #2953
      • FIXED: Dont abort bidirectional a-star search if only one direction is exhausted #2936
      • FIXED: Fixed missing comma in the scripts/valhalla_build_config #2963
      • FIXED: Reverse and Multimodal Isochrones were returning forward results #2967
      • FIXED: Map-match fix for first gps-point being exactly equal to street shape-point #2977
      • FIXED: Add missing GEOS:GEOS dep to mjolnir target #2901
      • FIXED: Allow expansion into a region when not_thru_pruning is false on 2nd pass #2978
      • FIXED: Fix polygon area calculation: use Shoelace formula #2927
      • FIXED: Isochrone: orient segments/rings acoording to the right-hand rule #2932
      • FIXED: Parsenodes fix: check if index is out-of-bound first #2984
      • FIXED: Fix for unique-summary logic #2996
      • FIXED: Isochrone: handle origin edges properly #2990
      • FIXED: Annotations fail with returning NaN speed when the same point is duplicated in route geometry #2992
      • FIXED: Fix run_with_server.py to work on macOS #3003
      • FIXED: Removed unexpected maneuvers at sharp bends #2968
      • FIXED: Remove large number formatting for non-US countries #3015
      • FIXED: Odin undefined behaviour: handle case when xedgeuse is not initialized #3020
    • Enhancement

      • Pedestrian crossing should be a separate TripLeg_Use #2950
      • CHANGED: Azure uses ninja as generator #2779
      • ADDED: Support for date_time type invariant for map matching #2712
      • ADDED: Add Bulgarian locale #2825
      • FIXED: No need for write permissions on tarball indices #2822
      • ADDED: nit: Links debug build with lld #2813
      • ADDED: Add costing option use_living_streets to avoid or favor living streets in route. #2788
      • CHANGED: Do not allocate mapped_cache vector in skadi when no elevation source is provided. #2841
      • ADDED: avoid_polygons logic #2750
      • ADDED: Added support for destination for conditional access restrictions #2857
      • CHANGED: Large sequences are now merge sorted which can be dramatically faster with certain hardware configurations. This is especially useful in speeding up the earlier stages (parsing, graph construction) of tile building #2850
      • CHANGED: When creating the intial graph edges by setting at which nodes they start and end, first mark the indices of those nodes in another sequence and then sort them by edgeid so that we can do the setting of start and end node sequentially in the edges file. This is much more efficient on certain hardware configurations #2851
      • CHANGED: Use relative cost threshold to extend search in bidirectional astar in order to find more alternates #2868
      • CHANGED: Throw an exception if directory does not exist when building traffic extract #2871
      • CHANGED: Support for ignoring multiple consecutive closures at start/end locations #2846
      • ADDED: Added sac_scale to trace_attributes output and locate edge output #2818
      • ADDED: Ukrainian language translations #2882
      • ADDED: Add support for closure annotations #2816
      • ADDED: Add costing option service_factor. Implement possibility to avoid or favor generic service roads in route for all costing options. #2870
      • CHANGED: Reduce stop impact cost when flow data is present #2891
      • CHANGED: Update visual compare script #2803
      • CHANGED: Service roads are not penalized for pedestrian costing by default. #2898
      • ADDED: Add complex mandatory restrictions support #2766
      • ADDED: Status endpoint for future status info and health checking of running service #2907
      • ADDED: Add min_level argument to valhalla_ways_to_edges #2918
      • ADDED: Adding ability to store the roundabout_exit_turn_degree to the maneuver #2941
      • ADDED: Penalize pencil point uturns and uturns at short internal edges. Note: motorcycle and motor_scooter models do not penalize on short internal edges. No new uturn penalty logic has been added to the pedestrian and bicycle costing models. #2944
      • CHANGED: Allow config object to be passed-in to path algorithms #2949
      • CHANGED: Allow disabling Werror
      • ADDED: Add ability to build Valhalla modules as STATIC libraries. #2957
      • NIT: Enables compiler warnings in part of mjolnir module #2922
      • CHANGED: Refactor isochrone/reachability forward/reverse search to reduce code repetition #2969
      • ADDED: Set the roundabout exit shape index when we are collapsing the roundabout maneuvers. #2975
      • CHANGED: Penalized closed edges if using them at start/end locations #2964
      • ADDED: Add shoulder to trace_attributes output. #2980
      • CHANGED: Refactor bidirectional astar forward/reverse search to reduce code repetition #2970
      • CHANGED: Factor for service roads is 1.0 by default. #2988
      • ADDED: Support for conditionally skipping CI runs #2986
      • ADDED: Add instructions for building valhalla on arm64 macbook #2997
      • CHANGED: nit(rename): Renames the encoded live speed properties #2998
      • ADDED: ci: Vendors the codecov script #3002
      • CHANGED: Allow None build type #3005
      • CHANGED: ci: Build Python bindings for Mac OS #3011
    Source code(tar.gz)
    Source code(zip)
  • 3.1.0(Jan 25, 2021)

    Release Date: 2021-01-25 Valhalla 3.1.0

    • Removed

      • REMOVED: Remove Node bindings. #2502
      • REMOVED: appveyor builds. #2550
      • REMOVED: Removed x86 CI builds. #2792
    • Bug Fix

      • FIXED: Crazy ETAs. If a way has forward speed with no backward speed and it is not oneway, then we must set the default speed. The reverse logic applies as well. If a way has no backward speed but has a forward speed and it is not a oneway, then set the default speed. #2102
      • FIXED: Map matching elapsed times spliced amongst different legs and discontinuities are now correct #2104
      • FIXED: Date time information is now propogated amongst different legs and discontinuities #2107
      • FIXED: Adds support for geos-3.8 c++ api #2021
      • FIXED: Updated the osrm serializer to not set junction name for osrm origin/start maneuver - this is not helpful since we are not transitioning through the intersection. #2121
      • FIXED: Removes precomputing of edge-costs which lead to wrong results #2120
      • FIXED: Complex turn-restriction invalidates edge marked as kPermanent #2103
      • FIXED: Fixes bug with inverted time-restriction parsing #2167
      • FIXED: Fixed several bugs with numeric underflow in map-matching trip durations. These may occur when serializing match results where adjacent trace points appear out-of-sequence on the same edge #2178
        • MapMatcher::FormPath now catches route discontinuities on the same edge when the distance percentage along don't agree. The trip leg builder builds disconnected legs on a single edge to avoid duration underflow.
        • Correctly populate edge groups when matching results contain loops. When a loop occurs, the leg builder now starts at the correct edge where the loop ends, and correctly accounts for any contained edges.
        • Duration over-trimming at the terminating edge of a match.
      • FIXED: Increased internal precision of time tracking per edge and maneuver so that maneuver times sum to the same time represented in the leg summary #2195
      • FIXED: Tagged speeds were not properly marked. We were not using forward and backward speeds to flag if a speed is tagged or not. Should not update turn channel speeds if we are not inferring them. Added additional logic to handle PH in the conditional restrictions. Do not update stop impact for ramps if they are marked as internal. #2198
      • FIXED: Fixed the sharp turn phrase #2226
      • FIXED: Protect against duplicate points in the input or points that snap to the same location resulting in nan times for the legs of the map match (of a 0 distance route) #2229
      • FIXED: Improves restriction check on briding edge in Bidirectional Astar #2228
      • FIXED: Allow nodes at location 0,0 #2245
      • FIXED: Fix RapidJSON compiler warnings and naming conflict #2249
      • FIXED: Fixed bug in resample_spherical_polyline where duplicate successive lat,lng locations in the polyline resulting in nan for the distance computation which shortcuts further sampling #2239
      • FIXED: Update exit logic for non-motorways #2252
      • FIXED: Transition point map-matching. When match results are on a transition point, we search for the sibling nodes at that transition and snap it to the corresponding edges in the route. #2258
      • FIXED: Fixed verbal multi-cue logic #2270
      • FIXED: Fixed Uturn cases when a not_thru edge is connected to the origin edge. #2272
      • FIXED: Update intersection classes in osrm response to not label all ramps as motorway #2279
      • FIXED: Fixed bug in mapmatcher when interpolation point goes before the first valid match or after the last valid match. Such behavior usually leads to discontinuity in matching. #2275
      • FIXED: Fixed an issue for time_allowed logic. Previously we returned false on the first time allowed restriction and did not check them all. Added conditional restriction gurka test and datetime optional argument to gurka header file. #2286
      • FIXED: Fixed an issue for date ranges. For example, for the range Jan 04 to Jan 02 we need to test to end of the year and then from the first of the year to the end date. Also, fixed an emergency tag issue. We should only set the use to emergency if all other access is off. #2290
      • FIXED: Found a few issues with the initial ref and direction logic for ways. We were overwriting the refs with directionals to the name_offset_map instead of concatenating them together. Also, we did not allow for blank entries for GetTagTokens. #2298
      • FIXED: Fixed an issue where MatchGuidanceViewJunctions is only looking at the first edge. Set the data_id for guidance views to the changeset id as it is already being populated. Also added test for guidance views. #2303
      • FIXED: Fixed a problem with live speeds where live speeds were being used to determine access, even when a live speed (current time) route wasn't what was requested. #2311
      • FIXED: Fix break/continue typo in search filtering #2317
      • FIXED: Fix a crash in trace_route due to iterating past the end of a vector. #2322
      • FIXED: Don't allow timezone information in the local date time string attached at each location. #2312
      • FIXED: Fix short route trimming in bidirectional astar #2323
      • FIXED: Fix shape trimming in leg building for snap candidates that lie within the margin of rounding error #2326
      • FIXED: Fixes route duration underflow with traffic data #2325
      • FIXED: Parse mtb:scale tags and set bicycle access if present #2117
      • FIXED: Fixed segfault. Shape was missing from options for valhalla_path_comparison and valhalla_run_route. Also, costing options was missing in valhalla_path_comparison. #2343
      • FIXED: Handle decimal numbers with zero-value mantissa properly in Lua #2355
      • FIXED: Many issues that resulted in discontinuities, failed matches or incorrect time/duration for map matching requests. #2292
      • FIXED: Seeing segfault when loading large osmdata data files before loading LuaJit. LuaJit fails to create luaL_newstate() Ref: #2158 Resolution is to load LuaJit before loading the data files. #2383
      • FIXED: Store positive/negative OpenLR offsets in bucketed form #2405
      • FIXED: Fix on map-matching return code when breakage distance limitation exceeds. Instead of letting the request goes into meili and fails in finding a route, we check the distance in loki and early return with exception code 172. #2406
      • FIXED: Don't create edges for portions of ways that are doubled back on themselves as this confuses opposing edge index computations #2385
      • FIXED: Protect against nan in uniform_resample_spherical_polyline. #2431
      • FIXED: Obvious maneuvers. #2436
      • FIXED: Base64 encoding/decoding #2452
      • FIXED: Added post roundabout instruction when enter/exit roundabout maneuvers are combined #2454
      • FIXED: openlr: Explicitly check for linear reference option for Valhalla serialization. #2458
      • FIXED: Fix segfault: Do not combine last turn channel maneuver. #2463
      • FIXED: Remove extraneous whitespaces from ja-JP.json. #2471
      • FIXED: Checks protobuf serialization/parsing success #2477
      • FIXED: Fix dereferencing of end for std::lower_bound in sequence and possible UB #2488
      • FIXED: Make tile building reproducible: fix UB-s #2480
      • FIXED: Zero initialize EdgeInfoInner.spare0_. Uninitialized spare0_ field produced UB which causes gurka_reproduce_tile_build to fail intermittently. 2499
      • FIXED: Drop unused CHANGELOG validation script, straggling NodeJS references #2506
      • FIXED: Fix missing nullptr checks in graphreader and loki::Reach (causing segfault during routing with not all levels of tiles availble) #2504
      • FIXED: Fix mismatch of triplegedge roadclass and directededge roadclass #2507
      • FIXED: Improve german destination_verbal_alert phrases #2509
      • FIXED: Undefined behavior cases discovered with undefined behavior sanitizer tool. 2498
      • FIXED: Fixed logic so verbal keep instructions use branch exit sign info for ramps #2520
      • FIXED: Fix bug in trace_route for uturns causing garbage coordinates #2517
      • FIXED: Simplify heading calculation for turn type. Remove undefined behavior case. #2513
      • FIXED: Always set costing name even if one is not provided for osrm serializer weight_name. #2528
      • FIXED: Make single-thread tile building reproducible: fix seed for shuffle, use concurrency configuration from the mjolnir section. #2515
      • FIXED: More Windows compatibility: build tiles and some run actions work now (including CI tests) #2300
      • FIXED: Transcoding of c++ location to pbf location used path edges in the place of filtered edges. #2542
      • FIXED: Add back whitelisting action types. #2545
      • FIXED: Allow uturns for truck costing now that we have derived deadends marked in the edge label #2559
      • FIXED: Map matching uturn trimming at the end of an edge where it wasn't needed. #2558
      • FIXED: Multicue enter roundabout #2556
      • FIXED: Changed reachability computation to take into account live speed #2597
      • FIXED: Fixed a bug where the temp files were not getting read in if you started with the construct edges or build phase for valhalla_build_tiles. #2601
      • FIXED: Updated fr-FR.json with partial translations. #2605
      • FIXED: Removed superfluous const qualifier from odin/signs #2609
      • FIXED: Internal maneuver placement #2600
      • FIXED: Complete fr-FR.json locale. #2614
      • FIXED: Don't truncate precision in polyline encoding #2632
      • FIXED: Fix all compiler warnings in sif and set to -Werror #2642
      • FIXED: Remove unnecessary maneuvers to continue straight #2647
      • FIXED: Linear reference support in route/mapmatch apis (FOW, FRC, bearing, and number of references) #2645
      • FIXED: Ambiguous local to global (with timezone information) date time conversions now all choose to use the later time instead of throwing unhandled exceptions #2665
      • FIXED: Overestimated reach caused be reenquing transition nodes without checking that they had been already expanded #2670
      • FIXED: Build with C++17 standard. Deprecated function calls are substituted with new ones. #2669
      • FIXED: Improve German post_transition_verbal instruction #2677
      • FIXED: Lane updates. Add the turn lanes to all edges of the way. Do not "enhance" turn lanes if they are part of a complex restriction. Moved ProcessTurnLanes after UpdateManeuverPlacementForInternalIntersectionTurns. Fix for a missing "uturn" indication for intersections on the previous maneuver, we were serializing an empty list. #2679
      • FIXED: Fixes OpenLr serialization #2688
      • FIXED: Internal edges can't be also a ramp or a turn channel. Also, if an edge is marked as ramp and turn channel mark it as a ramp. 2689
      • FIXED: Check that speeds are equal for the edges going in the same direction while buildig shortcuts #2691
      • FIXED: Missing fork or bear instruction #2683
      • FIXED: Eliminate null pointer dereference in GraphReader::AreEdgesConnected #2695
      • FIXED: Fix polyline simplification float/double comparison #2698
      • FIXED: Weights were sometimes negative due to incorrect updates to elapsed_cost #2702
      • FIXED: Fix bidirectional route failures at deadends #2705
      • FIXED: Updated logic to call out a non-obvious turn #2708
      • FIXED: valhalla_build_statistics multithreaded mode fixed #2707
      • FIXED: If infer_internal_intersections is true then allow internals that are also ramps or TCs. Without this we produce an extra continue manuever. #2710
      • FIXED: We were routing down roads that should be destination only. Now we mark roads with motor_vehicle=destination and motor_vehicle=customers or access=destination and access=customers as destination only. #2722
      • FIXED: Replace all Python2 print statements with Python3 syntax #2716
      • FIXED: Some HGT files not found #2723
      • FIXED: Fix PencilPointUturn detection by removing short-edge check and updating angle threshold #2725
      • FIXED: Fix invalid continue/bear maneuvers #2729
      • FIXED: Fixes an issue that lead to double turns within a very short distance, when instead, it should be a u-turn. We now collapse double L turns or double R turns in short non-internal intersections to u-turns. #2740
      • FIXED: fixes an issue that lead to adding an extra maneuver. We now combine a current maneuver short length non-internal edges (left or right) with the next maneuver that is a kRampStraight. #2741
      • FIXED: Reduce verbose instructions by collapsing small end ramp forks #2762
      • FIXED: Remove redundant return statements #2776
      • FIXED: Add support for geos-3.9 c++ api #2739
      • FIXED: Fix check for live speed validness #2797
    • Enhancement

      • ADDED: Matrix of Bike Share #2590
      • ADDED: Add ability to provide custom implementation for candidate collection in CandidateQuery. #2328
      • ADDED: Cancellation of tile downloading. #2319
      • ADDED: Return the coordinates of the nodes isochrone input locations snapped to #2111
      • ADDED: Allows more complicated routes in timedependent a-star before timing out #2068
      • ADDED: Guide signs and junction names #2096
      • ADDED: Added a bool to the config indicating whether to use commercially set attributes. Added logic to not call IsIntersectionInternal if this is a commercial data set. #2132
      • ADDED: Removed commerical data set bool to the config and added more knobs for data. Added infer_internal_intersections, infer_turn_channels, apply_country_overrides, and use_admin_db. #2173
      • ADDED: Allow using googletest in unit tests and convert all tests to it (old test.cc is completely removed). #2128
      • ADDED: Add guidance view capability. #2209
      • ADDED: Collect turn cost information as path is formed so that it can be seralized out for trace attributes or osrm flavored intersections. Also add shape_index to osrm intersections. #2207
      • ADDED: Added alley factor to autocost. Factor is defaulted at 1.0f or do not avoid alleys. #2246
      • ADDED: Support unlimited speed limits where maxspeed=none. #2251
      • ADDED: Implement improved Reachability check using base class Dijkstra. #2243
      • ADDED: Gurka integration test framework with ascii-art maps #2244
      • ADDED: Add to the stop impact when transitioning from higher to lower class road and we are not on a turn channel or ramp. Also, penalize lefts when driving on the right and vice versa. #2282
      • ADDED: Added reclassify_links, use_direction_on_ways, and allow_alt_name as config options. If use_direction_on_ways = true then use direction and int_direction on the way to update the directional for the ref and int_ref. Also, copy int_efs to the refs. #2285
      • ADDED: Add support for live traffic. #2268
      • ADDED: Implement per-location search filters for functional road class and forms of way. #2289
      • ADDED: Approach, multi-cue, and length updates #2313
      • ADDED: Speed up timezone differencing calculation if cache is provided. #2316
      • ADDED: Added rapidjson/schema.h to baldr/rapidjson_util.h to make it available for use within valhalla. #2330
      • ADDED: Support decimal precision for height values in elevation service. Also support polyline5 for encoded polylines input and output to elevation service. #2324
      • ADDED: Use both imminent and distant verbal multi-cue phrases. #2353
      • ADDED: Split parsing stage into 3 separate stages. #2339
      • CHANGED: Speed up graph enhancing by avoiding continuous unordered_set rebuilding #2349
      • CHANGED: Skip calling out to Lua for nodes/ways/relations with not tags - speeds up parsing. #2351
      • CHANGED: Switch to LuaJIT for lua scripting - speeds up file parsing #2352
      • ADDED: Ability to create OpenLR records from raw data. #2356
      • ADDED: Revamp length phrases #2359
      • CHANGED: Do not allocate memory in skadi if we don't need it. #2373
      • CHANGED: Map matching: throw error (443/NoSegment) when no candidate edges are available. #2370
      • ADDED: Add sk-SK.json (slovak) localization file. #2376
      • ADDED: Extend roundabout phrases. #2378
      • ADDED: More roundabout phrase tests. #2382
      • ADDED: Update the turn and continue phrases to include junction names and guide signs. #2386
      • ADDED: Add the remaining guide sign toward phrases #2389
      • ADDED: The ability to allow immediate uturns at trace points in a map matching request #2380
      • ADDED: Add utility functions to Signs. #2390
      • ADDED: Unified time tracking for all algorithms that support time-based graph expansion. #2278
      • ADDED: Add rail_ferry use and costing. #2408
      • ADDED: street_side_max_distance, display_lat and display_lon to locations in input for better control of routing side of street #1769
      • ADDED: Add addtional exit phrases. #2421
      • ADDED: Add Japanese locale, update German. #2432
      • ADDED: Gurka expect_route refactor #2435
      • ADDED: Add option to suppress roundabout exits #2437
      • ADDED: Add Greek locale. #2438
      • ADDED (back): Support for 64bit wide way ids in the edgeinfo structure with no impact to size for data sources with ids 32bits wide. #2422
      • ADDED: Support for 64bit osm node ids in parsing stage of tile building #2422
      • CHANGED: Point2/PointLL are now templated to allow for higher precision coordinate math when desired #2429
      • ADDED: Optional OpenLR Encoded Path Edges in API Response #2424
      • ADDED: Add explicit include for sstream to be compatible with msvc_x64 toolset. #2449
      • ADDED: Properly split returned path if traffic conditions change partway along edges #2451
      • ADDED: Add Dutch locale. #2464
      • ADDED: Check with address sanititizer in CI. Add support for undefined behavior sanitizer. #2487
      • ADDED: Ability to recost a path and increased cost/time details along the trippath and json output #2425
      • ADDED: Add the ability to do bikeshare based (ped/bike) multimodal routing #2031
      • ADDED: Route through restrictions enabled by introducing a costing option. #2469
      • ADDED: Migrated to Ubuntu 20.04 base-image #2508
      • CHANGED: Speed up parseways stage by avoiding multiple string comparisons #2518
      • CHANGED: Speed up enhance stage by avoiding GraphTileBuilder copying #2468
      • ADDED: Costing options now includes shortest flag which favors shortest path routes #2555
      • ADDED: Incidents in intersections #2547
      • CHANGED: Refactor mapmatching configuration to use a struct (instead of boost::property_tree::ptree). #2485
      • ADDED: Save exit maneuver's begin heading when combining enter & exit roundabout maneuvers. #2554
      • ADDED: Added new urban flag that can be set if edge is within city boundaries to data processing; new use_urban_tag config option; added to osrm response within intersections. #2522
      • ADDED: Parses OpenLr of type PointAlongLine #2565
      • ADDED: Use edge.is_urban is set for serializing is_urban. #2568
      • ADDED: Added new rest/service area uses on the edge. #2533
      • ADDED: Dependency cache for Azure #2567
      • ADDED: Added flexibility to remove the use of the admindb and to use the country and state iso from the tiles; #2579
      • ADDED: Added toll gates and collection points (gantry) to the node; #2532
      • ADDED: Added osrm serialization for rest/service areas and admins. #2594
      • CHANGED: Improved Russian localization; #2593
      • ADDED: Support restricted class in intersection annotations #2589
      • ADDED: Added trail type trace #2606
      • ADDED: Added tunnel names to the edges as a tagged name. #2608
      • CHANGED: Moved incidents to the trip leg and cut the shape of the leg at that location #2610
      • ADDED: Costing option to ignore_closures when routing with current flow #2615
      • ADDED: Cross-compilation ability with MinGW64 #2619
      • ADDED: Defines the incident tile schema and incident metadata #2620
      • ADDED: Moves incident serializer logic into a generic serializer #2621
      • ADDED: Incident loading singleton for continually refreshing incident tiles#2573
      • ADDED: One shot mode to valhalla_service so you can run a single request of any type without starting a server #2624
      • ADDED: Adds text instructions to OSRM output #2625
      • ADDED: Adds support for alternate routes #2626
      • CHANGED: Switch Python bindings generator from boost.python to header-only pybind11#2644
      • ADDED: Add support of input file for one-shot mode of valhalla_service #2648
      • ADDED: Linear reference support to locate api #2645
      • ADDED: Implemented OSRM-like turn duration calculation for car. Uses it now in auto costing. #2651
      • ADDED: Enhanced turn lane information in guidance #2653
      • ADDED: top_speed option for all motorized vehicles #2667
      • CHANGED: Move turn_lane_direction helper to odin/util #2675
      • ADDED: Add annotations to osrm response including speed limits, unit and sign conventions #2668
      • ADDED: Added functions for predicted speeds encoding-decoding #2674
      • ADDED: Time invariant routing via the bidirectional algorithm. This has the effect that when time dependent routes (arrive_by and depart_at) fall back to bidirectional due to length restrictions they will actually use the correct time of day for one of the search directions #2660
      • ADDED: If the length of the edge is greater than kMaxEdgeLength, then consider this a catastrophic error if the should_error bool is true in the set_length function. 2678
      • ADDED: Moved lat,lon coordinates structures from single to double precision. Improves geometry accuracy noticibly at zooms above 17 as well as coordinate snapping and any other geometric operations. Addes about a 2% performance pentalty for standard routes. Graph nodes now have 7 digits of precision. #2693
      • ADDED: Added signboards to guidance views. #2687
      • ADDED: Regular speed on shortcut edges is calculated with turn durations taken into account. Truck, motorcycle and motorscooter profiles use OSRM-like turn duration. #2662
      • CHANGED: Remove astar algorithm and replace its use with timedep_forward as its redundant #2706
      • ADDED: Recover and recost all shortcuts in final path for bidirectional astar algorithm #2711
      • ADDED: An option for shortcut recovery to be cached at start up to reduce the time it takes to do so on the fly #2714
      • ADDED: If width <= 1.9 then no access for auto, truck, bus, taxi, emergency and hov. #2713
      • ADDED: Centroid/Converge/Rendezvous/Meet API which allows input locations to find a least cost convergence point from all locations #2713
      • ADDED: Added support to process the sump_buster tag. Also, fixed a few small access bugs for nodes. #2731
      • ADDED: Log message if failed to create tiles directory. #2738
      • CHANGED: Tile memory is only owned by the GraphTile rather than shared amongst copies of the graph tile (in GraphReader and TileCaches). #2340
      • ADDED: Add Estonian locale. #2748
      • CHANGED: Handle GraphTile objects as smart pointers #2703
      • CHANGED: Improve stability with no RTTI build #2759 and #2760
      • CHANGED: Change generic service roads to a new Use=kServiceRoad. This is for highway=service without other service= tags (such as driveway, alley, parking aisle) #2419
      • ADDED: Isochrones support isodistance lines as well #2699
      • ADDED: Add support for ignoring live traffic closures for waypoints #2685
      • ADDED: Add use_distance to auto cost to allow choosing between two primary cost components, time or distance #2771
      • CHANGED: nit: Enables compiler warnings in part of loki module #2767
      • CHANGED: Reducing the number of uturns by increasing the cost to for them to 9.5f. Note: Did not increase the cost for motorcycles or motorscooters. #2770
      • ADDED: Add option to use thread-safe GraphTile's reference counter. #2772
      • CHANGED: nit: Enables compiler warnings in part of thor module #2768
      • ADDED: Add costing option use_tracks to avoid or favor tracks in route. #2769
      • CHANGED: chore: Updates libosmium #2786
      • CHANGED: Optimize double bucket queue to reduce memory reallocations. #2719
      • CHANGED: Collapse merge maneuvers #2773
      • CHANGED: Add shortcuts to the tiles' bins so we can find them when doing spatial lookups. #2744
    Source code(tar.gz)
    Source code(zip)
  • 3.0.9(Nov 22, 2019)

    Release Date: 2019-11-21 Valhalla 3.0.9

    • Bug Fix

      • FIXED: Changed reachability computation to consider both directions of travel wrt candidate edges #1965
      • FIXED: toss ways where access=private and highway=service and service != driveway. #1960
      • FIXED: Fix search_cutoff check in loki correlate_node. #2023
      • FIXED: Computes notion of a deadend at runtime in bidirectional a-star which fixes no-route with a complicated u-turn. #1982
      • FIXED: Fix a bug with heading filter at nodes. #2058
      • FIXED: Bug in map matching continuity checking such that continuity must only be in the forward direction. #2029
      • FIXED: Allow setting the time for map matching paths such that the time is used for speed lookup. #2030
      • FIXED: Don't use density factor for transition cost when user specified flag disables flow speeds. #2048
      • FIXED: Map matching trace_route output now allows for discontinuities in the match though multi match is not supported in valhalla route output. #2049
      • FIXED: Allows routes with no time specified to use time conditional edges and restrictions with a flag denoting as much #2055
      • FIXED: Fixed a bug with 'current' time type map matches. #2060
      • FIXED: Fixed a bug with time dependent expansion in which the expansion distance heuristic was not being used. #2064
    • Enhancement

      • ADDED: Establish pinpoint test pattern #1969
      • ADDED: Suppress relative direction in ramp/exit instructions if it matches driving side of street #1990
      • ADDED: Added relative direction to the merge maneuver #1989
      • ADDED: Refactor costing to better handle multiple speed datasources #2026
      • ADDED: Better usability of curl for fetching tiles on the fly #2026
      • ADDED: LRU cache scheme for tile storage #2026
      • ADDED: GraphTile size check #2026
      • ADDED: Pick more sane values for highway and toll avoidance #2026
      • ADDED: Refactor adding predicted speed info to speed up process #2026
      • ADDED: Allow selecting speed data sources at request time #2026
      • ADDED: Allow disabling certain neighbors in connectivity map #2026
      • ADDED: Allows routes with time-restricted edges if no time specified and notes restriction in response #1992
      • ADDED: Runtime deadend detection to timedependent a-star. #2059
    Source code(tar.gz)
    Source code(zip)
  • 3.0.8(Sep 7, 2019)

    • Bug Fix

      • FIXED: Added logic to detect if user is to merge to the left or right #1892
      • FIXED: Overriding the destination_only flag when reclassifying ferries; Also penalizing ferries with a 5 min. penalty in the cost to allow us to avoid destinati on_only the majority of the time except when it is necessary. #1895
      • FIXED: Suppress forks at motorway junctions and intersecting service roads #1909
      • FIXED: Enhanced fork assignment logic #1912
      • FIXED: Added logic to fall back to return country poly if no state and updated lua for Metro Manila and Ireland #1910
      • FIXED: Added missing motorway fork instruction #1914
      • FIXED: Use begin street name for osrm compat mode #1916
      • FIXED: Added logic to fix missing highway cardinal directions in the US #1917
      • FIXED: Handle forward traversable significant road class intersecting edges #1928
      • FIXED: Fixed bug with shape trimming that impacted Uturns at Via locations. #1935
    • Enhancement

      • ADDED: Caching url fetched tiles to disk #1887
      • ADDED: filesystem::remove_all #1887
      • ADDED: Minimum enclosing bounding box tool #1887
      • ADDED: Use constrained flow speeds in bidirectional_astar.cc #1907
      • ADDED: Bike Share Stations are now in the graph which should set us up to do multimodal walk/bike scenarios #1852
    Source code(tar.gz)
    Source code(zip)
  • 3.0.7(Jul 18, 2019)

  • 3.0.6(Jul 15, 2019)

    Release Date: 2019-7-15 Valhalla 3.0.6

    • Bug Fix

      • FIXED: Admin name changes. #1853 Ref: #1854
      • FIXED: valhalla_add_predicted_traffic was overcommitted while gathering stats. Added a clear. #1857
      • FIXED: regression in map matching when moving to valhalla v3.0.0 #1863
      • FIXED: last step shape in osrm serializer should be 2 of the same point #1867
      • FIXED: Shape trimming at the beginning and ending of the route to not be degenerate #1876
      • FIXED: Duplicate waypoints in osrm serializer #1880
      • FIXED: Updates for heading precision #1881
      • FIXED: Map matching allowed untraversable edges at start of route #1884
    • Enhancement

      • ADDED: Use the same protobuf object the entire way through the request process #1837
      • ADDED: Enhanced turn lane processing #1859
      • ADDED: Add global_synchronized_cache in valhalla_build_config #1851
    Source code(tar.gz)
    Source code(zip)
  • 3.0.5(Jun 4, 2019)

    Release Date: 2019-06-04 Valhalla 3.0.5

    • Bug Fix

      • FIXED: Protect against unnamed rotaries and routes that end in roundabouts not turning off rotary logic #1840
    • Enhancement

      • ADDED: Add turn lane info at maneuver point #1830
    Source code(tar.gz)
    Source code(zip)
  • 3.0.4(May 31, 2019)

    Release Date: 2019-05-31 Valhalla 3.0.4

    • Bug Fix
      • FIXED: Improved logic to decide between bear vs. continue #1798
      • FIXED: Bicycle costing allows use of roads with all surface values, but with a penalty based on bicycle type. However, the edge filter totally disallows bad surfaces for some bicycle types, creating situations where reroutes fail if a rider uses a road with a poor surface. #1800
      • FIXED: Moved complex restrictions building to before validate. #1805
      • FIXED: Fix bicycle edge filter whan avoid_bad_surfaces = 1.0 #1806
      • FIXED: Replace the EnhancedTripPath class inheritance with aggregation #1807
      • FIXED: Replace the old timezone shape zip file every time valhalla_build_timezones is ran #1817
      • FIXED: Don't use island snapped edge candidates (from disconnected components or low reach edges) when we rejected other high reachability edges that were closer #1835
    Source code(tar.gz)
    Source code(zip)
  • 3.0.3(May 9, 2019)

    Release Date: 2019-05-08 Valhalla 3.0.3

    • Bug Fix

      • FIXED: Fixed a rare loop condition in route matcher (edge walking to match a trace).
      • FIXED: Fixed VACUUM ANALYZE syntax issue. #1704
      • FIXED: Fixed the osrm maneuver type when a maneuver has the to_stay_on attribute set. #1714
      • FIXED: Fixed osrm compatibility mode attributes. #1716
      • FIXED: Fixed rotary/roundabout issues in Valhalla OSRM compatibility. #1727
      • FIXED: Fixed the destinations assignment for exit names in OSRM compatibility mode. #1732
      • FIXED: Enhance merge maneuver type assignment. #1735
      • FIXED: Fixed fork assignments and on ramps for OSRM compatibility mode. #1738
      • FIXED: Fixed cardinal direction on reference names when forward/backward tag is present on relations. Fixes singly digitized roads with opposing directional modifiers. #1741
      • FIXED: Fixed fork assignment and narrative logic when a highway ends and splits into multiple ramps. #1742
      • FIXED: Do not use any avoid edges as origin or destination of a route, matrix, or isochrone. #1745
      • FIXED: Add leg summary and remove unused hint attribute for OSRM compatibility mode. #1753
      • FIXED: Improvements for pedestrian forks, pedestrian roundabouts, and continue maneuvers. #1768
      • FIXED: Added simplified overview for OSRM response and added use_toll logic back to truck costing. #1765
      • FIXED: temp fix for location distance bug #1774
      • FIXED: Fix pedestrian routes using walkway_factor #1780
      • FIXED: Update the begin and end heading of short edges based on use #1783
      • FIXED: GraphReader::AreEdgesConnected update. If transition count == 0 return false and do not call transition function. #1786
      • FIXED: Only edge candidates that were used in the path are send to serializer: 1788
      • FIXED: Added logic to prevent the removal of a destination maneuver when ending on an internal edge #1792
      • FIXED: Fixed instructions when starting on an internal edge #1796
    • Enhancement

      • Add the ability to run valhalla_build_tiles in stages. Specify the begin_stage and end_stage as command line options. Also cleans up temporary files as the last stage in the pipeline.
      • Add remove to filesystem namespace. #1752
      • Add TaxiCost into auto costing options.
      • Add preferred_side to allow per-location filtering of edges based on the side of the road the location is on and the driving side for that locale.
      • Slightly decreased the internal side-walk factor to .90f to favor roads with attached sidewalks. This impacts roads that have added sidewalk:left, sidewalk:right or sidewalk:both OSM tags (these become attributes on each directedEdge). The user can then avoid/penalize dedicated sidewalks and walkways, when they increase the walkway_factor. Since we slightly decreased the sidewalk_factor internally and only favor sidewalks if use is tagged as sidewalk_left or sidewalk_right, we should tend to route on roads with attached sidewalks rather than separate/dedicated sidewalks, allowing for more road names to be called out since these are labeled more.
      • Add via and break_through location types #1737
      • Add street_side_tolerance and search_cutoff to input location #1777
      • Return the Valhalla error Path distance exceeds the max distance limit for OSRM responses when the route is greater than the service limits. #1781
    Source code(tar.gz)
    Source code(zip)
  • 3.0.2(Feb 20, 2019)

    Release Date: 2019-01-14 Valhalla 3.0.2

    • Bug Fix
      • FIXED: Transit update - fix dow and exception when after midnight trips are normalized #1682
      • FIXED: valhalla_convert_transit segfault - GraphTileBuilder has null GraphTileHeader #1683
      • FIXED: Fix crash for trace_route with osrm serialization. Was passing shape rather than locations to the waypoint method.
      • FIXED: Properly set driving_side based on data set in TripPath.
      • FIXED: A bad bicycle route exposed an issue with bidirectional A* when the origin and destination edges are connected. Use A* in these cases to avoid requiring a high cost threshold in BD A*.
      • FIXED: x86 and x64 data compatibility was fixed as the structures weren't aligned.
      • FIXED: x86 tests were failing due mostly to floating point issues and the aforementioned structure misalignment.
    • Enhancement
      • Add a durations list (delta time between each pair of trace points), a begin_time and a use_timestamp flag to trace_route requests. This allows using the input trace timestamps or durations plus the begin_time to compute elapsed time at each edge in the matched path (rather than using costing methods).
      • Add support for polyline5 encoding for OSRM formatted output.
    • Note
      • Isochrones and openlr are both noted as not working with release builds for x86 (32bit) platforms. We'll look at getting this fixed in a future release
    Source code(tar.gz)
    Source code(zip)
  • 3.0.1(Dec 5, 2018)

    Release Date: 2018-11-21 Valhalla 3.0.1

    • Bug Fix
      • FIXED: Fixed a rare, but serious bug with bicycle costing. ferry_factor_ in bicycle costing shadowed the data member in the base dynamic cost class, leading to an unitialized variable. Occasionally, this would lead to negative costs which caused failures. #1663
      • FIXED: Fixed use of units in OSRM compatibility mode. #1662
    Source code(tar.gz)
    Source code(zip)
  • 3.0.0(Nov 21, 2018)

    Release Date: 2018-11-21 Valhalla 3.0.0

    • NOTE
      • This release changes the Valhalla graph tile formats. Tile data is incompatible with Valhalla 2.x builds, and code for 3.x is incompatible with data built for Valahalla 2.x versions. Valhalla tile sizes are slightly smaller (for datasets using elevation information the size savings is over 10%). In addition, there is increased flexibility for creating different variants of tiles to support different applications (e.g. bicycle only, or driving only).
    • Enhancement
      • Remove the use of DirectedEdge for transitions between nodes on different hierarchy levels. A new structure, NodeTransition, is now used to transition to nodes on different hierarchy level. This saves space since only the end node GraphId is needed for the transitions (and DirectedEdge is a large data structure).
      • Change the NodeInfo lat,lon to use an offset from the tile base lat,lon. This potentially allows higher precision than using float, but more importantly saves space and allows support for NodeTransitions as well as spare for future growth.
      • Remove the EdgeElevation structure and max grade information into DirectedEdge and mean elevation into EdgeInfo. This saves space.
      • Reduce wayid to 32 bits. This allows sufficient growth when using OpenStreetMap data and frees space in EdgeInfo (allows moving speed limit and mean elevation from other structures).
      • Move name consistency from NodeInfo to DirectedEdge. This allows a more efficient lookup of name consistency.
      • Update all path algorithms to use NodeTransition logic rather than special DirectedEdge transition types. This simplifies PathAlgorithms slightly and removes some conditional logic.
      • Add an optional GraphFilter stage to tile building pipeline. This allows removal of edges and nodes based on access. This allows bicycle only, pedestrian only, or driving only datasets (or combinations) to be created - allowing smaller datasets for special purpose applications.
    • Deprecate
      • Valhalla 3.0 removes support for OSMLR.
    Source code(tar.gz)
    Source code(zip)
  • 2.7.2(Nov 20, 2018)

    Release Date: 2018-11-20 Valhalla 2.7.2

    • Enhancement
      • UPDATED: Added a configuration variable for max_timedep_distance. This is used in selecting the path algorithm and provides the maximum distance between locations when choosing a time dependent path algorithm (other than multi modal). Above this distance, bidirectional A* is used with no time dependencies.
      • UPDATED: Remove transition edges from priority queue in Multimodal methods.
      • UPDATED: Fully implement street names and exit signs with ability to identify route numbers. #1635
    • Bug Fix
      • FIXED: A timed-turned restriction should not be applied when a non-timed route is executed. #1615
      • FIXED: Changed unordered_map to unordered_multimap for polys. Poly map can contain the same key but different multi-polygons. For example, islands for a country or timezone polygons for a country.
      • FIXED: Fixed timezone db issue where TZIDs did not exist in the Howard Hinnant date time db that is used in the date_time class for tz indexes. Added logic to create aliases for TZIDs based on https://en.wikipedia.org/wiki/List_of_tz_database_time_zones
      • FIXED: Fixed the ramp turn modifiers for osrm compat #1569
      • FIXED: Fixed the step geometry when using the osrm compat mode #1571
      • FIXED: Fixed a data creation bug causing issues with A* routes ending on loops. #1576
      • FIXED: Fixed an issue with a bad route where destination only was present. Was due to thresholds in bidirectional A*. Changed threshold to be cost based rather than number of iterations). #1586
      • FIXED: Fixed an issue with destination only (private) roads being used in bicycle routes. Centralized some "base" transition cost logic in the base DynamicCost class. #1587
      • FIXED: Remove extraneous ramp maneuvers #1657
    Source code(tar.gz)
    Source code(zip)
  • 2.7.1(Oct 2, 2018)

    • Enhancement
      • UPDATED: Added date time support to forward and reverse isochrones. Add speed lookup (predicted speeds and/or free-flow or constrained flow speed) if date_time is present.
      • UPDATED: Add timezone checks to multimodal routes and isochrones (updates localtime if the path crosses into a timezone different than the start location).
    • Data Producer Update
      • UPDATED: Removed boost date time support from transit. Now using the Howard Hinnant date library.
    • Bug Fix
      • FIXED: Fixed a bug with shortcuts that leads to inconsistent routes depending on whether shortcuts are taken, different origins can lead to different paths near the destination. This fix also improves performance on long routes and matrices.
      • FIXED: We were getting inconsistent results between departing at current date/time vs entering the current date/time. This issue is due to the fact that the iso_date_time function returns the full iso date_time with the timezone offset (e.g., 2018-09-27T10:23-07:00 vs 2018-09-27T10:23). When we refactored the date_time code to use the new Howard Hinnant date library, we introduced this bug.
      • FIXED: Increased the threshold in CostMatrix to address null time and distance values occuring for truck costing with locations near the max distance.
    Source code(tar.gz)
    Source code(zip)
  • 2.7.0(Sep 14, 2018)

    • Enhancement
      • UPDATED: Refactor to use the pbf options instead of the ptree config #1428 This completes 1357
      • UPDATED: Removed the boost/date_time dependency from baldr and odin. We added the Howard Hinnant date and time library as a submodule. #1494
      • UPDATED: Fixed 'Drvie' typo #1505 This completes 1504
      • UPDATED: Optimizations of GetSpeed for predicted speeds 1490
      • UPDATED: Isotile optimizations
      • UPDATED: Added stats to predictive traffic logging
      • UPDATED: resample_polyline - Breaks the polyline into equal length segments at a sample distance near the resolution. Break out of the loop through polyline points once we reach the specified number of samplesthen append the last polyline point.
      • UPDATED: added android logging and uses a shared graph reader
      • UPDATED: Do not run a second pass on long pedestrian routes that include a ferry (but succeed on first pass). This is a performance fix. Long pedestrian routes with A star factor based on ferry speed end up being very inefficient.
    • Bug Fix
      • FIXED: A* destination only
      • FIXED: Fixed through locations weren't honored #1449
    Source code(tar.gz)
    Source code(zip)
  • 2.6.3(Jul 16, 2018)

    API: FIXED: Use a non-linear use_highways factor (to more heavily penalize highways as use_highways approaches 0). ENHANCEMENT: Added logic to modulate the surface factor based on use_trails. ADDED: New customer test requests for motorcycle costing.

    Source code(tar.gz)
    Source code(zip)
  • 2.6.1(Jun 1, 2018)

    • Data Producer Update
      • Allow busses to route on hov=designated roads.
      • Route on roads if any lane on the road is not designated (even if hov=designated)
    • Infrastructure:
      • CHANGED: Fix install targets #1330
    Source code(tar.gz)
    Source code(zip)
  • 2.6.0(May 28, 2018)

  • 2.5.0(May 24, 2018)

    • Enhancement
      • Add time dependnet forward and reverse A* methods.
      • Add code formatting and linting.
      • Added new motorcycle costing, motorcycle access flag in data and use_trails option.
    • Bug Fix
      • Increase minimum threshold for driving routes in bidirectional A* (fixes some instances of bad paths).
    • Data Producer Update
      • Updates to properly handle cycleway crossings.
      • Conditionally include driveways that are private.
      • Added logic to set motorcycle access. This includes lua, country access, and user access flags for motorcycles.
    Source code(tar.gz)
    Source code(zip)
  • 2.4.9(Apr 11, 2018)

    • Enhancement
      • Added European Portuguese localization for Valhalla
      • Updates to EdgeStatus to improve performance. Use an unordered_map of tile Id and allocate an array for each edge in the tile. This allows using pointers to access status for sequential edges. This improves performance by 50% or so.
      • A couple of bicycle costing updates to improve route quality: avoid roads marked as part of a truck network, to remove the density penalty for transition costs. When optimal matrix type is selected, now use CostMatrix for source to target pedestrian and bicycle matrix calls when both counts are above some threshold. This improves performance in general and lessens some long running requests.
    • Data Producer Update
      • Added logic to protect against setting a speed of 0 for ferries.
    Source code(tar.gz)
    Source code(zip)
  • 2.4.8(Mar 27, 2018)

    Release Date: 2017-03-27 Valhalla 2.4.8

    • Enhancement
      • Optionally disable candidate edge penalty in path finding
      • OSRM compatible route, matrix and map matching response generation
      • Minimal Windows build compatibility
      • Refactoring to use PBF as the IPC mechanism for all objects
      • Improvements to internal intersection marking to reduce false positives
    • Bug Fix
      • Cap candidate edge penalty in path finding to reduce excessive expansion
      • Fix trivial paths at deadends
    Source code(tar.gz)
    Source code(zip)
  • 2.4.7(Feb 8, 2018)

    Release Date: 2017-02-8 Valhalla 2.4.7

    • Enhancement
      • Speed up building tiles from small OSM imports by using boost directory iterator rather than going through all possible tiles and testing each if the file exists.
    • Bug Fix
      • Protect against overflow in string to float conversion inside OSM parsing.
    Source code(tar.gz)
    Source code(zip)
  • 2.4.6(Jan 26, 2018)

  • 2.4.5(Jan 25, 2018)

  • 2.4.4(Jan 19, 2018)

    Release Date: 2017-01-19 Valhalla 2.4.4

    • Enhancement
      • Elevation service speed improvments and the ability to serve lz4hc compressed data
      • Basic support for downloading routing tiles on demand
      • Deprecated valhalla_route_service, now all services (including elevation) are found under valhalla_service
    Source code(tar.gz)
    Source code(zip)
Owner
valhalla
Valhalla is an Open Source Routing Library/Service
valhalla
🗺️ OMAPS.APP — Offline OpenStreetMap maps for iOS and Android. A community-driven fork of MAPS.ME.

OMaps is an open source cross-platform offline maps application, built on top of crowd-sourced OpenStreetMap data. It was publicly released for iOS and Android.

OMaps 4.4k Jan 7, 2023
A Rideshare Simulation built in C++, using OpenStreetMap data

My Capstone project for the C++ Nanodegree at Udacity, a rideshare simulator. It extends the concurrency project based on a traffic simulation, as well as taking in parts of the earlier route planning project, in order to simulate ridesharing apps that are able to pick up passengers

Michael Virgo 13 Nov 8, 2022
Organic Maps is a better fork of MAPS.ME, an Android & iOS offline maps app for travelers, tourists, hikers, and cyclists based on top of crowd-sourced OpenStreetMap data and curated with love by MAPS.ME founders.

?? Organic Maps is a better fork of MAPS.ME, an Android & iOS offline maps app for travelers, tourists, hikers, and cyclists based on top of crowd-sourced OpenStreetMap data and curated with love by MAPS.ME founders. No ads, no tracking, no data collection, no crapware.

Organic Maps 4.4k Jan 2, 2023
Library for building multi-level indoor routes using routing algorithms.

Library for building multi-level indoor routes using routing algorithms. You can easily construct routing graphs and find the shortest path for optimal indoor navigation.

Navigine 5 Nov 21, 2022
This library contains a set of algorithms for working with the routing graph.

Library for building multi-level indoor routes using routing algorithms. You can easily construct routing graphs and find the shortest path for optimal indoor navigation.

Navigine 5 Nov 21, 2022
Repos containing simulation code for drafts seen in the IETF routing area

Simulation Repository Brief introduction This repository will over time aim to accumulate code to simulate the behavior of ideas and drafts as propose

Andrew Alston 1 Oct 16, 2021
[NeurIPS 2021 Spotlight] Learning to Delegate for Large-scale Vehicle Routing

Learning to Delegate for Large-scale Vehicle Routing This directory contains the code, data, and model for our NeurIPS 2021 Spotlight paper Learning t

null 45 Dec 24, 2022
A VLSI Detailed-routing Tool based on A* Algorithm

DRouter A simple VLSI detailed-routing tool based on A* Algorithm 1.how to build step 1: Download the source code $ git clone https://github.com/zyGao

null 1 Jun 22, 2022
Open 3D Engine (O3DE) is an Apache 2.0-licensed multi-platform AAA Open 3D Engine

Open 3D Engine (O3DE) is an Apache 2.0-licensed multi-platform 3D engine that enables developers and content creators to build AAA games, cinema-quality 3D worlds, and high-fidelity simulations without any fees or commercial obligations.

O3DE 5.8k Jan 7, 2023
MAZE (My AmaZing Engine) - 🎮 Personal open-source cross-platform game engine

MAZE (My AmaZing Engine) is the self-written open-source cross-platform game engine in the active development stage. At the moment it is my main pet project, developed for the purpose of learning and preserving different game dev technologies.

Dmitriy Nosov 13 Dec 14, 2022
OpenMW is an open-source open-world RPG game engine that supports playing Morrowind.

OpenMW is an open-source open-world RPG game engine that supports playing Morrowind.

null 4.5k Jan 2, 2023
Open Source Cheat for Apex Legends, designed for ease of use. Made to understand reversing of Apex Legends and respawn's modified source engine as well as their Easy Anti Cheat Implementation.

Apex-Legends-SDK Open Source Cheat for Apex Legends, designed for ease of use. Made to understand reversing of Apex Legends and respawn's modified sou

null 111 Jan 8, 2023
MySQL Server, the world's most popular open source database, and MySQL Cluster, a real-time, open source transactional database.

Copyright (c) 2000, 2021, Oracle and/or its affiliates. This is a release of MySQL, an SQL database server. License information can be found in the

MySQL 8.6k Dec 26, 2022
This is a list of different open-source video games and commercial video games open-source remakes.

This is a list of different open-source video games and commercial video games open-source remakes.

Ivan Bobev 173 Jan 2, 2023
Rogy-Engine- - My 3D game engine source code.

Rogy-Engine Development My 3D game engine. (NOT THE FINAL VERSION- Windows only) Features: PBR shading and reflection probes with parallax correction.

AlaX 97 Dec 28, 2022
Open-source, cross-platform, C++ game engine for creating 2D/3D games.

GamePlay v3.0.0 GamePlay is an open-source, cross-platform, C++ game framework/engine for creating 2D/3D mobile and desktop games. Website Wiki API De

gameplay3d 3.9k Jan 8, 2023
KlayGE is a cross-platform open source game engine with plugin-based architecture.

KlayGE KlayGE is a cross-platform open source game engine with plugin-based architecture. It's started since 2003. The explicit goal of KlayGE is: to

Minmin Gong 1.8k Dec 23, 2022
Powerful, mature open-source cross-platform game engine for Python and C++, developed by Disney and CMU

Panda3D Panda3D is a game engine, a framework for 3D rendering and game development for Python and C++ programs. Panda3D is open-source and free for a

Panda3D 3.6k Dec 31, 2022
MIT Licensed Open Source version of Torque 2D game engine from GarageGames

We've moved! All torque engines have moved to a new organization, Torque Game Engines. Torque2D can be found at https://github.com/TorqueGameEngines/T

GarageGames 1.7k Dec 14, 2022
RakNet is a cross platform, open source, C++ networking engine for game programmers.

RakNet 4.081 Copyright (c) 2014, Oculus VR, Inc. Package notes The Help directory contains index.html, which is full help documentation in HTML format

Facebook Archive 3.1k Dec 30, 2022