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.

Optimal According to What?

Last time, I introduced the problem of finding an optimal path through Monkey Island^TM 2. If there's one thing I learned in College, it is that "optimal" can mean many things, and it is often best to specify specifically what you wish to optimize. In this case I wish to minimize the time spent traveling from screen to screen. I especially don't want to go to the larger map screens very often, and I most definitely do not want to move between islands any more than is absolutely necessary.

In order to more precisely define what I wish to optimize, consider the following simple score system:

• It costs one point to complete any objective.
• To travel from one location to another adjacent location costs some number of points greater than or equal to one.

Using this system, and trying to minimize score, the absolute lowest cost would be if all objectives were in the same location and I don't have to move at all. My score would then simply be the number of objectives. Any traveling you do on top of that acts as a penalty and brings your score up.

The first thing I needed is a discretization of the world to give values to the penalties you accrue for traveling. I painstakingly mapped out the world, and applied some serious guestimating to come up with this graph for the first act's locations:

This is not perfect by any means, but I feel it is a good approximation of the required times to move from place to place. It at least gives us some values to use while performing our search. Tweaking the criteria could potentially help us finish faster, but we'll just assume this is good enough for now.

The next thing I need to solve this problem is a list of the required objectives. This was created painstakingly by consulting a walkthrough and adding each step as an objective, making careful notes of all prerequisite objectives, and the locations where they occur. Once I have all this information I am ready to make a search.

I chose to implement a simple A* search because it is good for this job, and it has code readily available on wikipedia.

A search state can be identified as a location and a list of objectives that have already been completed. The cost function is calculated as described above (travel costs + objective costs), and the heuristic function is simply the number of uncompleted objectives. On each step I can either complete all available objectives at my current location, or if there are no available objectives, move to an adjacent location to my current one.

Using this method I am guaranteed optimality (according to my cost function above), and I get a fairly nice path:

1. Get shovel
2. Go to BarKitchen
3. Get knife
4. Go to Wally
5. Get monocle
6. Get paper
7. Go to Cleaners
8. Get bucket
9. Go to Bar
10. Talk to bartender about business
11. Get spit with paper
12. Go to Bridge
13. Go to Beach
14. Get stick
15. Go to Swamp
16. Get swampy water in bucket
17. Go to Cemetery
18. Go to CemeteryHill
19. Dig up grave
20. Go to Cemetery
21. Go to Bridge
22. Go to Hotel
23. Use knife on rope
24. Get cheese squiggles
25. Go to LargosRoom
26. Get Toupee
27. Rig door with bucket of mud
28. Go to Hotel
29. Go to Cleaners
30. Watch largo at dry cleaner
31. Go to Hotel
32. Go to LargosRoom
33. Get Laundy ticket
34. Go to Hotel
35. Go to Cleaners
36. Get Largo's Laundry
37. Go to Bridge
38. Go to Swamp
39. Go to VoodooShack
40. Get string
41. Talk to voodoo lady about doll
42. Give spit
43. Give clothes
44. Give toupee
45. Give bone
46. Go to Swamp
47. Go to Bridge
48. Go to Cleaners
49. Open box
50. Use stick and string with box
51. Put cheese squiggle in box
52. Pull string (wait for rat)
53. Open box get rat
54. Go to BarKitchen
55. Put rat in soup
56. Go to Bar
57. Get a job (order stew)
58. Go to Hotel
59. Go to LargosRoom
60. Stab largo
61. Go to Swamp
62. Go to BoatScabb
63. Give Monocle and charter ship

This was calculated in around 15 seconds on a non-special computer, and it was completed in just over 13 minutes, with distractions. I can't see any way to improve on this path.

The next step will be to put in all the objectives for the next act (which has a considerably more complicated objectives graph) and see how it does. Wish me luck.

Optimal Path for Monkey IslandTM

You may or may not be aware that LucasArts has recently re-released the first two episodes in the Monkey Island^TM series. The special editions are complete renovations of the originals, with new graphics and voice-overs, but are otherwise identical. You can even switch back and forth between the original graphics and the new ones at any time with a single key-press, and it is absolutely seamless.

If you have enjoyed the series in the past, you would definitely enjoy the refreshed version. The graphics are smooth, and the experience is like what you remember. If you have never played, or heard of Monkey Island^TM, then shame on you. Get the special edition and play through it with the old graphics first.

One new thing that was added to Monkey Island^TM 2 was a set of Steam achievements. One of the harder ones to get is to complete the game in under three hours. I did not make it really even close on my first play-through, because I was trying to enjoy the game. Now, though, it's business time. This game is really quite large. There is a good deal of sailing from island to island, and the nerdmonger in me is constantly asking me to figure out a way to minimize all that.

Sure, I could easily do it all from memory in under 3 hours now, but that's no fun. I have enough deep cs background that I should be able to solve a simple problem like this fairly easily, shouldn't I? Is it harder than I thought? Its just a traveling salesman problem, isn't it?

Here's a teaser - A graph of all necessary objectives to complete Chapter One: The Largo Embargo:

Locations are not shown there, but I am trying to complete all objectives while minimizing time spent walking.

Stay tuned for the thrilling continuation.