Thursday, August 30, 2012

Puzzle Quest Solver (2007)

In 2007 I got my hands on Puzzle Quest DS, an awesome game I played many times over.

I started building a Lego robot to play the game on DS for me, using a webcam for visual recognition, but I never finished writing the software; I was in the middle of recognizing tiles on the game board when something else caught my interest.  I only have a few pictures of this robot, but it was pretty cool.  Built with first-generation Mindstorms, it sported two arms in SCARA configuration: an upper arm (red) on the end of which was attached a lower arm (green).  The rotations were performed in the plane of the DS's screen, to position a Lego "stylus" which was brought down on the screen using a Lego micromotor (blue).  This gave a cylindrical coordinate system.

Robot mockup; webcam and DS models from Google 3D Warehouse.
The robot, in two parts.  The three tires hold up the DS; the articulated arm is on the left.  The long part on the right serves as an attachment point for the webcam.
A closer view of the interesting part of the robot.  You can see the micromotor which moves the end effector in and out.  The end effector is the long axle with a blue circular part that limits travel.
The motor on the right controls the upper arm; the motor on the left controls the lower arm through a series of gears along the upper arm.
A better view of the lower arm mechanism.
The DS, as seen from the webcam's vantage point.  You can see part of the stylus mechanism on the left.
Though the vast majority of the game is random-based, at specific points in the game, preauthored challenges are presented.  Later on these get quite tricky, and I much preferred the meta-challenge of writing a solver for these instead of banging my head on them for hours on end.

Below is sample output from my solver.  The solver is a simple brute-force search through the space of legal moves.  It prints backwards, so the solution must be read bottom-up:


  ABCDEFGH

1 ........
2 ........
3 ........
4 ........
5 ........
6 ........
7 ........
8 ........
C8/D8 -> 3
  ABCDEFGH

1 ........
2 ........
3 ........
4 ........
5 ........
6 ........
7 ........
8 SS.S....
B8/C8 -> 3
  ABCDEFGH

1 ........
2 ........
3 ........
4 ........
5 ........
6 ........
7 ...S....
8 SRSRR...
F7/F8 -> 1
  ABCDEFGH

1 ........
2 ........
3 ........
4 ........
5 ........
6 ...SRGG.
7 ...RSRKK
8 SRSRRSSG
C7/D7 -> 3
  ABCDEFGH

1 ........
2 ........
3 ........
4 ........
5 ........
6 ...SRGG.
7 SSRSSRKK
8 SRSRRSSG
C6/D6 -> 3
  ABCDEFGH

1 ........
2 ........
3 ........
4 ........
5 ........
6 $$S$RGG.
7 SSRSSRKK
8 SRSRRSSG
F6/F7 -> 3
  ABCDEFGH

1 ........
2 ........
3 ........
4 ........
5 ...$RG..
6 $$S$$RG.
7 SSRSS$KK
8 SRSRRSSG
G5/G6 -> 3
  ABCDEFGH

1 ........
2 ......G.
3 ......K.
4 ....RGR.
5 ...$SSR.
6 $$S$$RS.
7 SSRSS$RK
8 SRSRRSSG
B8/C8 -> 1
  ABCDEFGH

1 ....RG..
2 ...$SSG.
3 ..S$$RK.
4 ..RSS$R.
5 ..SRRSR.
6 $$GYYGS.
7 SSBKKBRK
8 SSRKKRSG
A6/A7 -> 3
  ABCDEFGH

1 ....RG..
2 ...$SSG.
3 $.S$$RK.
4 G.RSS$R.
5 G.SRRSR.
6 S$GYYGS.
7 GSBKKBRK
8 SSRKKRSG
B6/B7 -> 3
  ABCDEFGH

1 ....RG..
2 ...$SSG.
3 $$S$$RK.
4 GGRSS$R.
5 GGSRRSR.
6 SSGYYGS.
7 GGBKKBRK
8 SSRKKRSG
H5/H6 -> 3
  ABCDEFGH

1 ....RG..
2 ...$SSG.
3 $$S$$RK.
4 GGRSS$RK
5 GGSRRSRS
6 SSGYYGSG
7 GGBKKBRS
8 SSRKKRSS
H6/H7 -> 3
  ABCDEFGH


1 ....RG.K
2 ...$SSGS
3 $$S$$RKG
4 GGRSS$RR
5 GGSRRSRR
6 SSGYYGSS
7 GGBKKBRR
8 SSRKKRSS

No comments:

Post a Comment