Monkey IslandTM Optimality Part 3

Last week I quite easily found an optimal path through the first part of Monkey Island^TM 2. Moving on the second episode, I ran into difficulties.

First off, the map is much expanded. I now have three islands available to me, so the search space has gotten much larger. The map, with my (somewhat arbitrary) travel costs now looks like this:

Furthermore, there are a ton more objectives:

If you color them by Island, you see this:

My hopes of an easy solution were dashed when I looked at this last graph and found a chain that required six island changes to get through the graph. Hopefully we can stick fairly close to that.

I entered all of the objectives into my system as quickly as I could and hit some problems:

1. It ran slow.
2. It ran reaaaallly slow.

The first act ran in a matter of seconds, but the second one, with the increased complexity seemed to take forever. I got lazy in implementing the search. To choose a node to explore I was resorting the list of possibilities on every iteration. This caused the search to slow down the further it got into it, and once there were about 16,000 nodes under consideration it pretty much stopped cold.

Once I swapped out my crappy list for a proper priority queue, I got much better search speed, but still was far from a solution. After 15 minutes of running and almost 7 million nodes considered, I got an OutOfMemory exception, because I was storing a list of nodes I had already considered to avoid repetition. I got to implement one of the cooler data structures I know of (the Directed Acyclic Word Graph, and finally I received a solution.

This is guaranteed to be optimal if my map weights make any sense, and if I did not overly constrain the search by the way I entered in the objectives. To the best of my knowledge this is a fairly good path. I will let you know how it goes once I play through it completely.

Here it is:

1. Get Parrot Chow
2. Go to BoatPhatt
3. Go to Wharf
4. Get Arrested(Automatic)
5. Pull Mattress
6. Get Stick
7. Get Bone
8. Get Key
9. Unlock Cell
10. Get Gorilla Envelope
11. Get Manilla Envelope
12. Open Gorilla
13. Open Manilla
14. Go to Wharf
15. Go to RouletteAlley
16. Watch Roulette
17. Go to Wharf
18. Follow dude
19. Open Peephole
20. Get winning Number
21. Go to Wharf
22. Go to RouletteAlley
23. Win Cash
24. Go to Wharf
25. Go to SecretAlley
26. Get Number
27. Go to Wharf
28. Go to RouletteAlley
29. Win Invitation
30. Go to Wharf
31. Go to Library
32. Get Lens
33. Remember Hex Book(r-recipes)
34. Remember Shipwrecks(d-disasters)
35. Check Out Books
36. Go to Wharf
37. Go to BoatPhatt
38. Go to BoatBooty
39. Go to Ville
40. Get leaflet from Kate
41. Go to CostumeShop
42. Get Costume
43. Go to Ville
44. Go to Shop
45. Buy Saw
46. Buy Horn
47. Buy Sign
48. Talk to pawn owner about trades
49. Use chow on hook
50. Get Mirror
51. Go to Ville
52. Go to MarleyMansion
53. Present Costume and Invitation
54. Go to MarleyBack
55. Push Trash Can
56. Run around to kitchen
57. Get Fish
58. Run around to front
59. Get Map Piece
60. Go outside
61. Sweet Talk Elaine
62. Go to MarleyLounge
63. Go to MarleyMansion
64. Chase Map Piece
65. Get Dog
66. Go to MarleyLounge
67. Go to MarleyUpstairs
68. Get Oar
69. Go to MarleyLounge
70. Go to MarleyMansion
71. Go to BigTree
72. Attempt to climb tree
73. Get broken oar
74. Go to BoatBooty
75. Go to BoatScabb
76. Go to Bridge
77. Go to carpenter
78. Give oar to carpenter
79. Go to Bar
80. Use banana on metronome
81. Get blue and yellow drinks
82. Pick up monkey
83. Go to Wally
84. Give lens to wally
85. Go to Cleaners
86. Saw Pegleg
87. Go to Carpenter
88. Get Hammer
89. Get Nails
90. Go to BoatScabb
91. Go to BoatPhatt
92. Go to Wharf
93. Put leaflet on wanted poster
94. Get near-grog from envelope
95. Free Kate
96. Go to Wharf
97. Go to Pier
98. Challenge Fisherman
99. Give fish and Win
100. Go to Wharf
101. Go to BoatPhatt
102. Go to BoatBooty
103. Go to Ville
104. Go to Spit
105. Switch Flags
106. Win Spitting Contest
107. Go to Ville
108. Go to Shop
109. Trade plaque
110. Go to Ville
111. Read coordinates for mad monkey
112. Charter ship and get masthead
113. Go to Stans
114. Nail Stan in coffin
115. Get Crypt key
116. Go to Ville
117. Go to Shop
118. Trade masthead for map
119. Go to Ville
120. Go to Cliff
121. Fish Up Map
122. Go to Ville
123. Go to BigTree
124. Climb Tree
125. Get Telescope
126. Use Dog to find map
127. Go to BoatBooty
128. Go to BoatPhatt
129. Go to Mansion
130. Go to MansionLobby
131. Trick Guard
132. Go to GovernersRoom
133. Swap Books
134. Go to MansionLobby
135. Go to Mansion
136. Go to Waterfall
137. Go to WaterfallTop
138. Use monkey wrench on valve
139. Go to Waterfall
140. Go to Cottage
141. Cheat at drinking contest
142. Open Window
143. Put mirror in frame
144. Put telescope in statue
145. Push correct brick
146. Get Map Piece
147. Go to Wharf
148. Go to BoatPhatt
149. Go to BoatScabb
150. Go to Cemetery
151. Use Key in Crypt
152. Go to Crypt
153. Read Pirate quotes
154. Open Coffin
155. Get Ashes
156. Go to Cemetery
157. Go to Swamp
158. Go to VoodooShack
159. Pick up ash2Life Jar
160. Talk to voodooLady and give book
161. Go to Swamp
162. Go to Cemetery
163. Go to Crypt
164. Use ash2Life on ashes
165. Go to Cemetery
166. Go to Beach
167. Go to WeenieHut
168. Use key at weenie hut
169. Turn Off Gas
170. Go to Beach
171. Go to Cemetery
172. Go to Crypt
173. Revive rapp and get mapp
174. Go to Cemetery
175. Go to Bridge
176. Go to Wally
177. Give 4 pieces to Wally

This path has 7 island changes in it, which is not too shabby. The "speed guide" I used to construct my objectives graph changed islands 8 times, so I may be on to something. I completed this part of the quest in only 46 minutes, bringing my total to this point up to just 58 minutes.