Optimized routing for Zwift's Makuri

Zwift recently released a new set of routes on a made-up island called Makuri. Different from some of the other maps, this one has a ton of cross-roads, and there’s a lot to see. It’s pretty. So, of course, instead of cycling there, I thought it would be a fun exercise to find the shortest path that lets you see everything at least once.

Without further ado, here’s the optimal path:

  • Distance total: 33.4 km (repeated: 5.6 km)
  • Routes used: 33 (used once: 25)

The optimal route uses a bunch of u-turns, so it’s not that practical. It’s a small island, so just keep cycling and you’ll make it. Hit ‘h’ to turn the HUD off :-).

Overview

The island looks like this:

(Source: Zwift)

How to get there

Technically, the map is located in Nendo, in the Santa Cruz Islands / Solomon Islands, South-Pacific. You can get there in Zwift too – I imagine it looks different in person.

The work

After looking around, this is a variation of the classical “traveling salesperson problem” (TSP). In the original problem, you just visit the locations in any order, the routes chosen don’t matter. In our case, we care about the routes (see all the sights!), so our problem matches the “Route inspection problem (also known as ‘Chinese postman problem’.”

Luckily, an ounce of googling saves a ton of noodling, and there are many solutions coded up for this. I used the “Postman Problems” Python library by Andrew Brooks, which has a “Seven Bridges” example that’s perfect for copy & paste. I’ll probably be done in an afternoon (editors note: nope).

Simplify the problem

After riding the region for a while, I took all the tracks from Strava, exported them as GPX, mapped them, and annotated them with “nodes” (crossroads) and “edges” (trails). I used GPX Studio for this, and annotated the screenshot in Google Docs.

Extract the segments

I spent way too much time trying to automatically extract edges & nodes from the GPX files. I ended up just doing it manually: created segments in Strava, and split the GPX files using My GPS Files. For the last route, Strava decided I couldn’t crreate more segments, pffft. The lengths were from Strava’s km distances, so potentially a bit off. I could recalculate them based on the GPX files, but who has time for accuracy in a virtual cycling game? (I could say the same for optimizing for that, but whatever.)

Run the solver

This was pretty non-eventful.

python3 cpp_makuri.py

INFO:__main__:Solve CPP
(..)
Solution [from, to, path] - copy into draw_*.py:
[['A', 'Q', 'Q1'], ['Q', 'O', 'O2'], ['O', 'Q', 'O2'], ['Q', 'P', 'P1'], ['P', 'L', 'L1'], ['L', 'P', 'L1'], ['P', 'O', 'O1'], ['O', 'M', 'M1'], ['M', 'L', 'L2'], ['L', 'K', 'K1'], ['K', 'L', 'K1'], ['L', 'M', 'L2'], ['M', 'H', 'H2'], ['H', 'I', 'H1'], ['I', 'K', 'I2'], ['K', 'J', 'J1'], ['J', 'G', 'G1'], ['G', 'F', 'F2'], ['F', 'D', 'D2'], ['D', 'F', 'D2'], ['F', 'G', 'F1'], ['G', 'J', 'G1'], ['J', 'I', 'I1'], ['I', 'H', 'H1'], ['H', 'E', 'E1'], ['E', 'C', 'C2'], ['C', 'E', 'C2'], ['E', 'D', 'D1'], ['D', 'C', 'C1'], ['C', 'B', 'B1'], ['B', 'A', 'A3'], ['A', 'B', 'A2'], ['B', 'A', 'A1']]
INFO:__main__:Solution summary stats:
INFO:__main__:distance_walked : 33410
INFO:__main__:distance_doublebacked : 5650
INFO:__main__:distance_walked_once : 27760
INFO:__main__:distance_walked_optional : 0
INFO:__main__:distance_walked_required : 33410
INFO:__main__:edges_walked : 33
INFO:__main__:edges_doublebacked : 8
INFO:__main__:edges_walked_once : 25
INFO:__main__:edges_walked_optional : 0
INFO:__main__:edges_walked_required : 33
(...)

Make animated image

Once everything is done, it’s time to sink more time. I used MatPlotLib + ImageMagick to plot out the GPX segments in the order. MatPlotLib animations are surprisingly straightforward and just worked.

#!/usr/bin/python3

# Draws animation of optimal trail for new Zwift island, saves as output/animated-map.gif
# by John Mueller - github.com/softplus
# License: Apache 2

import matplotlib.pyplot as plt
import matplotlib.animation as animation

# from cpp_makuri.py
solution = [['A', 'Q', 'Q1'], ['Q', 'O', 'O2'], ['O', 'Q', 'O2'], ['Q', 'P', 'P1'], ['P', 'L', 'L1'], ['L', 'P', 'L1'], ['P', 'O', 'O1'], ['O', 'M', 'M1'], ['M', 'L', 'L2'], ['L', 'K', 'K1'], ['K', 'L', 'K1'], ['L', 'M', 'L2'], ['M', 'H', 'H2'], ['H', 'I', 'H1'], ['I', 'K', 'I2'], ['K', 'J', 'J1'], ['J', 'G', 'G1'], ['G', 'F', 'F2'], ['F', 'D', 'D2'], ['D', 'F', 'D2'], ['F', 'G', 'F1'], ['G', 'J', 'G1'], ['J', 'I', 'I1'], ['I', 'H', 'H1'], ['H', 'E', 'E1'], ['E', 'C', 'C2'], ['C', 'E', 'C2'], ['E', 'D', 'D1'], ['D', 'C', 'C1'], ['C', 'B', 'B1'], ['B', 'A', 'A3'], ['A', 'B', 'A2'], ['B', 'A', 'A1']]

# reads all data points from CSV file
def get_data(trail):
    points = []
    with open("tracks/" + trail + ".csv") as f:
        lines = f.readlines()
        for line in lines[1:]:
            items = line.strip().split(",")
            points.append([float(x) for x in items])
    return points


# initialize figure, get sub-plot
fig = plt.figure(dpi=150)
ax1 = fig.add_subplot(1,1,1)

# draw the full map as background
def plot_all(solution):
    for trail in solution:
        pts = get_data(trail[2])
        ax1.plot( [d[1] for d in pts], [d[0] for d in pts], color="#77a")

# track previously visited trails to highlight extras
previously_seen = []

# animation; i=index of trails so far
def animate(i):
    ax1.clear()
    plt.title('Makuri', size=10)
    plt.axis('off')
    plot_all(solution) # draw background, scale image

    # draw trails visited so far
    for trail in solution[:i]:
        pts = get_data(trail[2])
        ax1.plot( [d[1] for d in pts], [d[0] for d in pts], color="#f00")

    # draw this trail, highlight if revisited    
    this_trail = solution[i][2]
    pts = get_data(this_trail)
    if this_trail in previously_seen and i>0:
        ax1.plot( [d[1] for d in pts], [d[0] for d in pts], color="#faa", linewidth=5)
        ax1.plot( [d[1] for d in pts], [d[0] for d in pts], color="#333", linestyle=":", linewidth=3)
    else:
        ax1.plot( [d[1] for d in pts], [d[0] for d in pts], color="#faa", linewidth=5)
    previously_seen.append(this_trail)

# animate 
ani = animation.FuncAnimation(fig, animate, interval=1000, frames=len(solution), repeat_delay=10000) 

print("Animate and save...")
plt.show()
ani.save("output/animated-map.gif", writer="imagemagick") 
print("Done")

(Will be dropped on Github at some point.)

Random screenshots

Comments / questions

There's currently no commenting functionality here. If you'd like to comment, please use Twitter and @me there. Thanks!

Tweet about this - and/or - search for latest comments / top comments

Related pages