THE WANDERINGMERCHANT
Golden HourThe Amber Expanse
THE ROUTE

Chart your route

STOPS VISITED0 / 9
YOUR DISTANCE0 km
TRAVEL ITINERARY PLANNING
A MERCHANT’S FIELD GUIDE

Visit every town.
Travel the fewest kilometres.

  1. Begin at the town named “Start”. It is already selected for you.
  2. Plan your visit order. Click each other castle or its numbered button once. Every new stop adds a straight segment to your route.
  3. Aim for the smallest total distance. Click your last selected town again to undo that stop, or use Undo or Clear route to change your plan. You can finish at any town; do not return home.
  4. Choose Begin the journey. After travelling, compare your ember-red route with the shortest route in turquoise. Chevrons show the direction of travel. Choose Try again for a new random desert.

Keyboard: type a town’s number to select it (for towns 10–13, type both digits), Backspace undoes, Enter departs.

The travelling salesman problem

The classic travelling salesman problem asks for the shortest journey that visits each city once and returns to the start. This game uses an open-path version: the start is fixed, but you may finish anywhere.

A little mathematics

Each town is a point. The distance between two towns is the straight-line distance:

d(A, B) = √[(xB − xA)² + (yB − yA)²]

Add the distances of all the segments to get your route length. The goal is to choose the order that makes that sum as small as possible.

With 10 towns and the starting town fixed, there are 9! = 362,880 possible visit orders. Here, 9! means 9 × 8 × … × 1. With 14 towns, that grows to 13! = 6,227,020,800.

100% means you found a shortest route. Choosing the nearest town at each step can help, but does not always produce the best overall journey.

Explore the travelling salesman problem on Wikipedia ↗