Last time, I introduced the problem of finding an optimal path through Monkey IslandTM 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.
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:
- Get shovel
- Go to BarKitchen
- Get knife
- Go to Wally
- Get monocle
- Get paper
- Go to Cleaners
- Get bucket
- Go to Bar
- Talk to bartender about business
- Get spit with paper
- Go to Bridge
- Go to Beach
- Get stick
- Go to Swamp
- Get swampy water in bucket
- Go to Cemetery
- Go to CemeteryHill
- Dig up grave
- Go to Cemetery
- Go to Bridge
- Go to Hotel
- Use knife on rope
- Get cheese squiggles
- Go to LargosRoom
- Get Toupee
- Rig door with bucket of mud
- Go to Hotel
- Go to Cleaners
- Watch largo at dry cleaner
- Go to Hotel
- Go to LargosRoom
- Get Laundy ticket
- Go to Hotel
- Go to Cleaners
- Get Largo's Laundry
- Go to Bridge
- Go to Swamp
- Go to VoodooShack
- Get string
- Talk to voodoo lady about doll
- Give spit
- Give clothes
- Give toupee
- Give bone
- Go to Swamp
- Go to Bridge
- Go to Cleaners
- Open box
- Use stick and string with box
- Put cheese squiggle in box
- Pull string (wait for rat)
- Open box get rat
- Go to BarKitchen
- Put rat in soup
- Go to Bar
- Get a job (order stew)
- Go to Hotel
- Go to LargosRoom
- Stab largo
- Go to Swamp
- Go to BoatScabb
- 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.
No comments:
Post a Comment