Tour The Galaxy

The Problem

Tour the Galaxy is a Star Trek Online mission that asks a player to fly to as many star systems as they can in a 15 minute window. The available systems are specified by the mission and the more of them a player reaches, the better the rewards. However, there is not enough time to easily fly to them all. A few strategies can be employed to increase ship speed, but this page focuses on the algorithmic problem of devising the shortest travel route between the systems.

The Solution(s)

For a short video demonstrating how the below data was gathered, please visit The Youtubes.

Want to make your own routes? Download the program. I made this for my own amusement, but if you find any bugs, feel free to let me know (or fix them yourself!) through my contact info at the github repo.

Want to automate your route? Check out www.reddit.com/u/daBelgrave's keybind instructions HERE.

I've used the following two images to perform a number of shortest path analyses based on pixel distances. The Tour the Galaxy destinations are marked in red on the map to help me click them when generating paths.

Alpha Quadrant Beta Quadrant
Base maps for Alpha and Beta Quadrants

Standalone Solutions

These solutions produce the minimum total pixel distance route that covers all the desired points. The arrows are just for clarity; the routes may be traveled in either direction.

Optimal standalone Alpha Quadrant Solution Optimal standalone Beta Quadrant Solution
Optimal paths for Alpha and Beta Quadrants individually

A variation on the standalone optimal solution involves using an Instance Change to reposition yourself within the zone. I reran the standalone maps and specified a Warp Point to which all other points can travel for cheap (20px for this calculation).

Optimal Alpha Quadrant with Instance Change Solution Optimal Beta Quadrant with Instance Change Solution
Optimal individual quadrant paths in which an Instance Change is used
Optimal Standalone Routes
QuadrantRouteDistance*
Alpha Arawath, Algira, DS9, Corwin, Betazed, Chapel, Tellar, Mizar, Tzenketh, Defera, Ferenginar, Breen 2871
Alpha (Instance) Ferenginar, Breen, Warp Point, DS9, Corwin, Betazed, Chapel, Tellar, Mizar, Tzenketh, Defera, Arawath, Algira 2677
Beta Sanek, Qo'noS, Khitomer, New Romulus, Mylasa, Gamma Eridon, Pheben, Iconia, Vorn, Alini, Lirss, Vendor, Argelius, Virinat, Archanis, Drozana, Traelus, Risa, Orion, Teneebia, Nimbus 4068
Beta (Instance) Traelus, Drozana, Archanis, Virinat, Argelius, Orion, Risa, Warp Point 1, Teneebia, Nimbus, Vendor, Lirss, Alini, Vorn, Iconia, Pheben, Gamma Eridon, Mylasa, New Romulus, Khitomer, Qo'noS, Sanek 3870

*Note that these distances are in pixels on the maps for the respective quadrants, which do not have the same scale in this instance.

Transwarp Solutions

Most players will have at least one transwarp available during the course of this mission. These images compare routes with different transwarp options. The idea is that you would travel the optimal route for one quadrant, then transwarp to the other quadrant and follow the most optimal route given your starting point.

Transwarp to Alpha Quadrant

In these examples, you follow the optimal Beta Quadrant solution and then transwarp to the Alpha Quadrant.

Optimal Alpha Quadrant route starting at Defera
Optimal Alpha Quadrant route starting at Defera
Optimal Alpha Quadrant route starting at DS9
Optimal Alpha Quadrant route starting at DS9
Optimal Alpha Quadrant Transwarp Routes
Starting SectorRouteDistance
Defera Defera, Arawath, Algira, DS9, Corwin, Betazed, Chapel, Tellar, Mizar, Tzenketh, Ferenginar, Breen 2993
DS9 DS9, Algira, Arawath, Defera, Tzenketh, Mizar, Corwin, Betazed, Chapel, Tellar, Ferenginar, Breen 3121

Transwarp to Beta Quadrant

In these examples, you follow the optimal Alpha Quadrant solution and then transwarp to the Beta Quadrant. One point of note is that, unlike all the other transwarps, "Beta Quadrant" transwarp takes you directly to Sector Space, which saves you time not reflected in this data.

Optimal Beta Quadrant route starting at Sol System
Optimal Beta Quadrant route starting at Sol System
Optimal Beta Quadrant route starting at Beta Quadrant Transwarp
Optimal Beta Quadrant route starting at Beta Quadrant Transwarp
Optimal Beta Quadrant route starting at Starbase K7
Optimal Beta Quadrant route starting at Starbase K7
Optimal Beta Quadrant route starting at Starbase 39
Optimal Beta Quadrant route starting at Starbase 39
Optimal Beta Quadrant Transwarp Routes
Starting SectorRouteDistance
Sol System Sol System - Transwarp, Teneebia, Orion, Risa, Traelus, Drozana, Archanis, Virinat, Argelius, Vendor, Nimbus, Lirss, Alini, Vorn, Iconia, Pheben, Gamma Eridon, Mylasa, New Romulus, Khitomer, Qo'noS, Sanek 4249
Beta Quadrant Transwarp Beta Sector - Transwarp, Khitomer, Qo'noS, Sanek, Pheben, Gamma Eridon, New Romulus, Mylasa, Iconia, Vorn, Alini, Lirss, Vendor, Argelius, Virinat, Archanis, Drozana, Traelus, Risa, Orion, Teneebia, Nimbus 4277
Starbase K7 Starbase K7 - Transwarp, Traelus, Drozana, Archanis, Virinat, Argelius, Risa, Orion, Teneebia, Nimbus, Vendor, Lirss, Alini, Vorn, Iconia, Pheben, Gamma Eridon, Mylasa, New Romulus, Khitomer, Qo'noS, Sanek 4297
Starbase 39 Starbase 39 - Transwarp, Vendor, Argelius, Virinat, Archanis, Drozana, Traelus, Risa, Orion, Teneebia, Nimbus, Lirss, Alini, Vorn, Iconia, Pheben, Gamma Eridon, Mylasa, New Romulus, Khitomer, Qo'noS, Sanek 4303

Zone Boundary Solutions

A number of Transwarps are inconveniently located or require you to pass a second loading screen to reach Sector Space. This motivated me to investigate a couple of Zone Boundary solutions as well. These solutions require both a modified Alpha and Beta Quadrant map for each approach.

NOTE: Because of the way my program specifies required nodes, the first half of the routes are listed in reverse. Just follow them backward.

Tellar -> Teneebia

Zoning out from the top of the Alpha Quadrant puts you almost right next to Teneebia and is not too far from Tellar, so that is the only Alpha -> Beta zone transition I evaluated so far.

Optimal Beta Quadrant route ending at zone boundary near Tellar Optimal Alpha Quadrant route starting from zone boundery near Tellar
Route beginning in Alpha Quadrant and crossing Zone Boundary to the right of Tellar, continuing in Alpha Quadrant

Teneebia -> Tellar

Very similar to the above, this one is slightly different in that your zone in location on the Alpha quadrant is not as favorable.

Optimal Beta Quadrant route starting at zone boundary near Teneebia Optimal Alpha Quadrant route ending at the zone boundery near Teneebia
Route beginning in Beta Quadrant and crossing Zone Boundary to the left of Teneebia, continuing in Beta Quadrant

Orion -> Chapel

Optimal Beta Quadrant route starting at zone boundary near Orion Optimal Alpha Quadrant route ending at the zone boundery near Orion
Route beginning in Beta Quadrant and crossing Zone Boundary to the left of Orion, continuing in Beta Quadrant

Risa -> Betazed

Optimal Beta Quadrant route starting at zone boundary near Risa Optimal Alpha Quadrant route ending at the zone boundery near Risa
Route beginning in Beta Quadrant and crossing Zone Boundary to the left of Risa, continuing in Beta Quadrant
Optimal Zone Boundary Routes
Zone SystemsRouteDistance: AlphaDistance: Beta
Tellar -> Teneebia Breen, Ferenginar, Mizar, Tzenketh, Defera, Arawath, Algira, DS9, Corwin, Betazed, Chapel, Tellar, ZONE BOUNDARY, Teneebia, Orion, Risa, Traelus, Drozana, Archanis, Virinat, Argelius, Vendor, Nimbus, Lirss, Alini, Vorn, Iconia, Pheben, Gamma Eridon, Mylasa, New Romulus, Khitomer, Qo'noS, Sanek 3106 4215
Teneebia -> Tellar Sanek, Qo'noS, Khitomer, New Romulus, Mylasa, Gamma Eridon, Pheben, Iconia, Vorn, Alini, Lirss, Nimbus, Vendor, Argelius, Virinat, Archanis, Drozana, Traelus, Risa, Orion, Teneebia, ZONE BOUNDARY, Tellar, Chapel, Betazed, Corwin, DS9, Algira, Arawath, Defera, Tzenketh, Mizar, Ferenginar, Breen 3149 4221
Orion -> Chapel Sanek, Qo'noS, Khitomer, New Romulus, Mylasa, Gama Eridon, Pheben, Iconia, Vorn, Alini, Lirss, Vendor, Nimbus, Teneebia, Argelius, Virinat, Archanis, Drozana, Traelus, Risa, Orion, ZONE BOUNDARY, Chapel, Betazed, Corwin, DS9, Algira, Arawath, Defera, Tzenketh, Mizar, Tellar, Ferenginar, Breen 3146 4243
Risa -> Betazed Traelus, Drozana, Archanis, Virinat, New Romulus, Khitomer, Qo'noS, Sanek, Pheben, Gamma Eridon, Mylasa, Iconia, Vorn, Alini, Lirss, Vendor, Nimbus, Teneebia, Argelius, Orion, Risa, ZONE BOUNDARY, Betazed, Corwin, Chapel, Tellar, Mizar, Tzenketh, DS9, Algira, Arawath, Defera, Ferenginar, Breen 3192 4212

Summary

To try and normalize this data, I used a teammate to measure some distances in lightyears and compare them to pixel distances. For the Alpha Quadrant map, we came up with a value of about 8.39 pixels per lightyear, and for the Beta Quadrant map, about 6.14 pixels per lightyear. I then combine both paths to find a total distance metric.

StrategyRouteAlpha pxDelta pxTotal LY
TW to Defera Sanek, Qo'noS, Khitomer, New Romulus, Mylasa, Gamma Eridon, Pheben, Iconia, Vorn, Alini, Lirss, Vendor, Argelius, Virinat, Archanis, Drozana, Traelus, Risa, Orion, Teneebia, Nimbus, TRANSWARP to Defera, Defera, Arawath, Algira, DS9, Corwin, Betazed, Chapel, Tellar, Mizar, Tzenketh, Ferenginar, Breen 2993 4068 1018.9
TW to Sol Arawath, Algira, DS9, Corwin, Betazed, Chapel, Tellar, Mizar, Tzenketh, Defera, Ferenginar, Breen, TRANSWARP to Sol, Teneebia, Orion, Risa, Traelus, Drozana, Archanis, Virinat, Argelius, Vendor, Nimbus, Lirss, Alini, Vorn, Iconia, Pheben, Gamma Eridon, Mylasa, New Romulus, Khitomer, Qo'noS, Sanek 2871 4249 1033.8
TW to DS9 Sanek, Qo'noS, Khitomer, New Romulus, Mylasa, Gamma Eridon, Pheben, Iconia, Vorn, Alini, Lirss, Vendor, Argelius, Virinat, Archanis, Drozana, Traelus, Risa, Orion, Teneebia, Nimbus, TRANSWARP to DS9, DS9, Algira, Arawath, Defera, Tzenketh, Mizar, Corwin, Betazed, Chapel, Tellar, Ferenginar, Breen 3121 4068 1034.1
TW to Beta Quadrant Arawath, Algira, DS9, Corwin, Betazed, Chapel, Tellar, Mizar, Tzenketh, Defera, Ferenginar, Breen, TRANSWARP to Beta Quadrant, Khitomer, Qo'noS, Sanek, Pheben, Gamma Eridon, New Romulus, Mylasa, Iconia, Vorn, Alini, Lirss, Vendor, Argelius, Virinat, Archanis, Drozana, Traelus, Risa, Orion, Teneebia, Nimbus 2871 4277 1038.3
TW to K7 Arawath, Algira, DS9, Corwin, Betazed, Chapel, Tellar, Mizar, Tzenketh, Defera, Ferenginar, Breen, TRANSWARP to K7, Traelus, Drozana, Archanis, Virinat, Argelius, Risa, Orion, Teneebia, Nimbus, Vendor, Lirss, Alini, Vorn, Iconia, Pheben, Gamma Eridon, Mylasa, New Romulus, Khitomer, Qo'noS, Sanek 2871 4297 1041.6
TW to 39 Arawath, Algira, DS9, Corwin, Betazed, Chapel, Tellar, Mizar, Tzenketh, Defera, Ferenginar, Breen, TRANSWARP to 39, Vendor, Argelius, Virinat, Archanis, Drozana, Traelus, Risa, Orion, Teneebia, Nimbus, Lirss, Alini, Vorn, Iconia, Pheben, Gamma Eridon, Mylasa, New Romulus, Khitomer, Qo'noS, Sanek 2871 4303 1042.6
Tellar -> Teneebia Breen, Ferenginar, Mizar, Tzenketh, Defera, Arawath, Algira, DS9, Corwin, Betazed, Chapel, Tellar, ZONE BOUNDARY, Teneebia, Orion, Risa, Traelus, Drozana, Archanis, Virinat, Argelius, Vendor, Nimbus, Lirss, Alini, Vorn, Iconia, Pheben, Gamma Eridon, Mylasa, New Romulus, Khitomer, Qo'noS, Sanek 3106 4215 1056.3
Teneebia -> Tellar Sanek, Qo'noS, Khitomer, New Romulus, Mylasa, Gamma Eridon, Pheben, Iconia, Vorn, Alini, Lirss, Nimbus, Vendor, Argelius, Virinat, Archanis, Drozana, Traelus, Risa, Orion, Teneebia, ZONE BOUNDARY, Tellar, Chapel, Betazed, Corwin, DS9, Algira, Arawath, Defera, Tzenketh, Mizar, Ferenginar, Breen 3149 4221 1062.4
Orion -> Chapel Sanek, Qo'noS, Khitomer, New Romulus, Mylasa, Gama Eridon, Pheben, Iconia, Vorn, Alini, Lirss, Vendor, Nimbus, Teneebia, Argelius, Virinat, Archanis, Drozana, Traelus, Risa, Orion, ZONE BOUNDARY, Chapel, Betazed, Corwin, DS9, Algira, Arawath, Defera, Tzenketh, Mizar, Tellar, Ferenginar, Breen 3146 4243 1065.6
Risa -> Betazed Traelus, Drozana, Archanis, Virinat, New Romulus, Khitomer, Qo'noS, Sanek, Pheben, Gamma Eridon, Mylasa, Iconia, Vorn, Alini, Lirss, Vendor, Nimbus, Teneebia, Argelius, Orion, Risa, ZONE BOUNDARY, Betazed, Corwin, Chapel, Tellar, Mizar, Tzenketh, DS9, Algira, Arawath, Defera, Ferenginar, Breen 3192 4212 1066.0

The main point of note here is that doing optimal Beta Quadrant trumps most other optimization. Transwarping to Defera is faster than transwarping to DS9 by a substantial margin, making that route a clear leader, though starting BQ from Sol system is close enough to optimal that it is a reasonable alternative for people who cannot transwarp to Defera.

Another notable consideration is that the TW to Beta Quadrant solution is pretty competitive with other options and requires one fewer zone transfer. I don't know if that zone transfer is worth 20 LY of flying time, but it almost certainly pushes TW to Beta Quadrant into 2nd place. Similarly, the Zone Boundary crossings at the bottom of the list only require one zone transfer, and so could be reasonably competitive if you were not able or interested in using transwarp.

Successful Tour
Successful completion of Tour the Galaxy using the Transwarp to Defera method