Optimal paths for collection of exploration badges and history plaques

[AboveTheChemist]

EDIT: This thread was for the beta version of this mod. The full release version of this mod is now available in this thread. I have tidied up some of my now-outdated posts in this thread, but since there has already been some discussion of badge/plaque collection paths here, feel free to continue to discuss that here.

 

Edited February 3, 2021 by AboveTheChemist
cleanup

[AboveTheChemist]

Reserved.

 

 

Edited February 3, 2021 by AboveTheChemist
cleanup

[Jacke]

Excellent post, @AboveTheChemist.  I've long done the same, get all the Badges and read all the Plaques in one run.  I usually just wing it with Vidiotmaps installed to guide, but I've done some zones so many times, especially Atlas Park, that I can do them without little or no help from the minimap.

 

I recently added the Sewers and the Abandoned Sewers on a toon.  They are special and are best done together.  Running the Sewers is best done overleveled at 15 or higher.  To run the Abandoned Sewers, should have a toon at 50.  Full stealth helps lower those limits, though the Abandoned Sewers has Rikti with Drones that ignore stealth, so there should be at least 40 and just keep running.  Vidiotmaps is essential because besides the location of the Badges and the one Academic Plaque deep in the Abandoned Sewers, it also has the best routes through both Sewers marked which run right past all the Badges and the Plaque.

 

There are Sewers entrances in 5 zones, Atlas Park, Kings Row, Steel Canyon, Skyway City, and Boomtown.  Each entrance has 1 Badge near it, as well as a door to the matching branch of the Abandoned Sewers, which also has 1 Badge near the start.  Using a teleport power (like the Long Range Teleporter available to all come Issue 27,  or Ourobotos to get to Atlas, or the Base Transporter power and a set of Base Telepads), in succession go to the 5 zones, then

• to the Sewers entrance and in,
• through the side door to the Abandoned Sewers,
• then to the Badge closest on the branch (all 5 Abandoned Sewers entrances have a Badge very close),
• back to the Sewers, down to the nearest Badge,
• then teleport and travel to the next zone.

 

To get the last 3 Badges in each set of Sewers, modify some of those runs to add in the deeper Badges and the Plaque in the Abandoned Sewers.  For the Sewers,  it's best to get the deeper Badges from the Kings Row entrance.  For the Abandoned Sewers,  it's best to get the deeper Badges and the Plaque from the Atlas Park entrance after changing the sequence and getting the Atlas Sewers closest Badge before going into the Abandoned Sewers.

Edited November 21, 2020 by Jacke

[AboveTheChemist]

I meant to mention this in my initial post (I've now edited it in) but I used the simplest straight-line path between each badge/plaque, which may not represent with 100% accuracy the true path one would take between badges (especially for badges within buildings or below ground level). I have not spent much time on either of the sewer network maps but I knew those maps are not conducive for straight line travel and would be problematic with my method. I appreciate the input and it's a bridge I'll cross when I get to it.

[Ura Hero]

This is awesome.  If you need computing power to get this done in a reasonable time I would be happy to help out.

[AboveTheChemist]

On 11/22/2020 at 9:48 AM, Ura Hero said:

This is awesome.  If you need computing power to get this done in a reasonable time I would be happy to help out.

Thanks for the offer! I spent most of yesterday searching for and trying out alternate algorithms, and I happened upon a nice brute force algorithm that produces optimal solutions for zones with up to 12 badges in 7 minutes or less.. That is a huge improvement over my previous method (which was a genetic algorithm), and I think I have a workaround for zones with more than 12 badges/plaques that I am tinkering with now. I've already computed optimal solutions for all zones with 12 badges or less, and if my workaround trick works I think I can get the rest computed within the next day or so.

 

EDIT: If anyone happens along and is curious, my current (as of Feb 2024) computation method includes two different dynamic programming algorithms I found and adapted for this project. They are implemented in Python 3. The main algorithm computes the shortest distance and shortest path, and can complete the computations for all 55 zones included in this project in about 2 minutes on a 2016 high-end business computer. The second algorithm, which I use as a check, computes only the shortest path, and completes the calculations in about 30 seconds. I run both algorithms as part of one script so my timing numbers listed may not be exact, but together the main computation and check take about 2.5 minutes to run. That is a massive improvement in speed compared to the methods I used in the early stages of this project.

Edited February 24 by AboveTheChemist
adding info about new method

[AboveTheChemist]

As a quick update, I've been able to compute optimal paths for all but Atlas Park. My workaround trick worked great for every zone with more than 12 badges/plaques except for Atlas Park. I'm still working on AP and hope to have something computed soon.

 

I've also taken a closer look at the Sewer Network and Abandoned Sewer Network zones, as well as the three Underground zones in Praetoria (UG Imperial, UG Neutropolis, and UG Nova), and for now I am shelving any plans to include them in this project. The confined nature of those zones just make it too difficult to try to compute an optimal path, but I won't rule out potentially revisiting them down the line. For the Sewer Network and Abandoned Sewer Network maps, I think Jacke's post above covers it quite well.

 

I was hoping to devote a decent chunk of time to this over the Thanksgiving holiday but with the release of Issue 27 page 1, I need to switch gears to updating some of my other mods/datasets/wiki pages, particularly those that relate to badges, to account for the changes in Issue 27. This is just a guess but I think it will probably be closer to Christmas before I have this TSP mod completed.

[LaconicLemur]

I'll probably never use this (but hope to). However, it's a great resource! And I love optimization algorithms so I applaud using them whenever feasible (ha ha,  get it? 'feasible'? j/k). Is there a way you can publish a baseline travel time (e.g. sprint)?

[AboveTheChemist]

19 minutes ago, LaconicLemur said:

Is there a way you can publish a baseline travel time (e.g. sprint)?

I'm not sure about travel times, but I suppose I could publish the distances of the 'optimal' paths that were computed. As mentioned in the OP I used 3-dimensional Euclidean distance between each point, but even that is not totally accurate in some cases due to badges inside buildings, under roadways, or in cases where straight line travel between points is blocked by buildings or a zone corner. Those distances were sufficient for my purposes, though, and folks could use them to compute their own (rough) travel times. Given there are so many modes and speeds of travel, I think that is a more reasonable approach. Besides, if I were to publish a travel time, then I'd invariably have to deal with folks that were upset because my published travel time didn't mesh with their own experiences.

 

In terms of a project update, I am making decent headway but I was delayed a couple of weeks due to my laptop dying. I hope to devote a lot of time over the holiday to the project but it's probably going to be after the new year before I have all the maps generated and vetted.

[Garble]

I was looking for something like this.

 

As a raging altaholic I wanted to get the Accolade power ASAP for my lowbies and the path I find easiest is:

 

Atlas Park (from the spot where Heroes start):

• Run into the City Hall and go to the statue on the left for the Patriot badge
• Turn right and follow the hall to the last room on the right (D.A.T.A.) and run up to the elevator door for the Edge of Chaos badge
• Run back outside to the statue of Atlas (if you don't have the free prestige travel powers from the P2W Vendor get them now) use Jump Pack or Steam Jump to leap to the top of the Atlas statue globe for the Top Dog badge
• Jump down to the American flag at the top of City Hall for the Patriot badge
• Jump down behind City Hall and to the left towards Henry Peter Wong (guy in blue) for the Hero Corps Insider badge (I usually then go to the plaque on the corner near the parking lot for the Pupil badge since it's needed for an Accolade)
• Head towards the Steel Canyon marker and the orange-ish building directly to the right of it, use the street ramp to the south of it to jump to the lower ledge on the right of the building and go the antenna at the back for the Undefeated badge
• Go southeast (more east than south) and find another oragey building with a water tower just north of a skyscraper. Use the hill next to the building to get to the northwest corner of the skyscraper, and jump to the ledge with the watertower and go to the air conditioning unit near the southwest corner for the Silent Sentinel badge
• Head to the Vanguard building, go inside, up the stairs to the left and go to the door on the left side for the Observant badge 

I suppose you could get Observant first but that requires more running back on the same path.

 

I'm curious how the algorithm would differ.

[HoundsTooth]

Can you share the data / raw input you're giving to the algorithm? I'm guessing it's a set of 3-dimensional coordinates for badges and plaques in each zone. I'd like to play around with a few implementations.

[AboveTheChemist]

On 12/31/2020 at 6:16 PM, HoundsTooth said:

Can you share the data / raw input you're giving to the algorithm? I'm guessing it's a set of 3-dimensional coordinates for badges and plaques in each zone. I'd like to play around with a few implementations.

It's a bit more complex than that, and this will only be useful if you are using Python (or something that can access Python pickle files), but this is my pickle file with the input data. It is parsed from the Badger repository (taken from the exploration and history badges). It's been a few weeks since I looked at the data structure but off the top of my head the data structure looks something like this:

 

Top level keys: zone names

Top level values: dictionaries containing:

keys 1 to n are the arbitrarily numbered 'points' in each zone representing each badge/plaque in the zone and corresponding to values which are dictionaries containing various bits of info about each badge/plaque, including coordinates, names, type, vidiot map key, etc.

key 0 corresponds to a value which is another nested set of dictionaries that basically contain the Euclidean distance between each possible pair of points from 1 to n, with distances only computed to points of a higher integer to avoid having duplicate distances (i.e. distance is computed from point 1 to point 7, but not from point 7 to point 1)

 

badge_coord_dist_dict.pik

 

Edited December 11, 2021 by AboveTheChemist
updated the dataset to one with more accurate coordinates

[AboveTheChemist]

3 hours ago, Keovar said:

Is there a slash command to set a map thumbtack at a specified coordinate string?   If there is, we could create a popmenu to set each of the badge & plaque waypoints along a suggested path.

There is not, but I created a suggestion thread for that idea a while back. Feel free to support the idea there. Your popmenu idea is in the same vein as the rolling keybind idea I mentioned in the OP (third spoilered section down), which would require the /thumbtack command to work. Ultimately I think that would be the best way to implement this idea, but I don't want to get my hopes up too much. Still, I've made provisions in my scripts to be able to take my output and turn it into a popmenu/keybinds without a great deal of effort, if the /thumbtack command does ever come about.

 

As far as the project goes, I am more or less done with the maps, and am finally happy with them. I ended up revisiting a few of them several times before I felt that they were complete, and of course I tested and retested to make sure they made sense. So, the in-game maps are done, and I am in the process of converting the BMPs to PNGs and cropping them for use in the offline viewer. I hope to finish that up over the weekend, and if that goes smoothly I hope to be able to post a finished product next week.

[AboveTheChemist]

I've completed the mod (for now) and have published the full version here. I have tidied up some of my now-outdated posts in this thread (mostly my first two posts), but since there has already been some discussion of badge/plaque collection paths here, feel free to continue to discuss that here.

[Ukase]

I've only just seen this post, directed from the other post. 

1. I really appreciate the manual install option. There's something about the other method that just stymies my poor brain. 
2. The real reason for my post - have you considered the Sewer Network & Abandoned Sewer Network? On characters of mine that pursue all the explorations, I will cover a zone, such as Atlas, then enter the Sewer Network and only grab the closest one to the gate, then enter the ASN and grab that closest one to the gate. 
Only after I've hit Atlas, Kings, Steel, Skyway do I head to Boomtown (no particular order, although there probably is an optimal path) to get all the Sewer Network stuff, and then all the ASN (and the plaques within in), if I'm high enough level to pursue them. If not, I may have an alt SK my character, or I may wait until I'm 40-50.  

[AboveTheChemist]

I am glad you find the manual install useful. I always recommend installation via CoH modder but I understand that is not ideal for everyone, so I do my best to provide alternate solutions.

 

I have considered the two sewer network maps. I mentioned them briefly in a post above, and in more detail in the top post of the thread for the full release of this mod, in the 'Notes' section. I'll quote that here;

 

Quote

Although the maps for the Sewer Network, the Abandoned Sewer Network, Underground Imperial, Underground Neutropolis, and Underground Nova contain more than three badges/plaques, I did not compute solutions for them because they are all underground zones where travel is restricted within a tunnel network. Straight-line paths, like those computed for the rest of the zones, would not work for these zones, and it would have been far too complex to try to model the pathways in the tunnel networks. Suggestions for badge/plaque collection in the Sewer Network and Abandoned Sewer Network can be found in this thread.

 

The link at the end of that quote links to Jacke's post above, which, while I have not tested it specifically, looks to be as optimal as any solution I could devise given the nature of these two zones. Until someone comes forth with definitive proof that there is a better method (and I am not holding my breath waiting for that!), I recommend Jacke's method of badge collection in the Sewer Network and Abandoned Sewer Network as the most optimal.