[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionHelp the red car escape the traffic jam by moving other vehicles out of the way. Vehicles can only be moved in the direction of their longest axis.
Background & TechniquesHere's a Delphi version of a popular physical puzzle, RushHour(TM), produced by Binary Arts. Users can click and drag vehicles vertically or horizontally to get the red car to the exit. (Vehicles move only in the direction of their long axis.) Other features of this version:
This is a version stripped down from the original program that I wrote several years ago. I removed support for interactive problem generation to make the program a little less complicated. It still contains nearly 3000 lines of code - definitely in the advanced category. I've included about half of the problems included with original RushHour puzzle. I encourage you to buy the original RushHour game, it's available from Binary Arts (now ThinkFun) website, Thinkfun.com, from Amazon, or many retail stores for about $20. (I bought mine locally at one of those "Imagination" kid's toy stores.) I see that they now have RushHour versions 1 through 4 as well as a RushHour Jr. available. Problems are provided in a text file "TrafficJams.txt" containing multiple cases. Each case looks like this sample (lines beginning with semicolon, ; are comments):
Programmer StuffHere's another program that would require a fair sized book to describe everything that goes on. I've reviewed the code and tried to comment most of what didn't seem obvious. I also removed lots of code that allowed interactive problem development (plan to put it back in Version 2), so there are still some unused artifacts floating around. A modified field for example, and code to draw vehicle images and shapes other than the rounded rectangle are currently unused. As usual, there are a number of objects defined: TVehicle with information about each vehicle, TCase with an array of TVehicle objects, problem name and other information about a particular case, and a TCaseList, a TList derivative that holds the entire set of available cases. Currently drawing is performed on BoardBox, a TPaintbox control, but I'll probably make TCase a TPaintBox derivative in the next version and embed more of the drawing code there. The toughest parts to code were the mouse handling and the auto-solve features. Moving PiecesI spent a couple of days this week trying to implement drag/drop handlers to care of moving the vehicles, but could never overcome one specific problem - I wanted to force the drag operation to end when the target vehicle was dragged to the winning position, without waiting for the user to release the button and trigger drag-drop processing. Never could get it, so I finally left the code as originally written using MouseDown, MouseMove and MouseUp exits. Nothing really wrong with it, we just need to make sure that mouse coordinates are converted appropriately to be BoardBox based using ScreenToClient procedure calls. Solution SearchHere's a chance to review graph searching - we use a breadth first search to find solutions as required (when the user requests a hint or asks us to solve the puzzle). Beginners are sometimes confused when we talk about graph searching for a problem that doesn't seem to have much to do with graphs. The graph is an imaginary one where every node, (corner or vertex), of the graph represents a state of the board and the edges of the graph represent transitions from node to node that can be made with a single move. See Graph Searching page over in Math-Topics for a more complete discussion. So we'll be looking for a path (a series of moves) that get us from one particular node (the starting position) to another (node (one with the target car at the exit). The prerequisites for searching a graph for a particular node are:
These prerequisites are the same whether we are doing a depth or breadth first search. The difference is in how we select which node to visit next. In breadth first searching searching used here, we'll sit in a loop retrieving, and deleting, the top (oldest and therefore shortest move list ) node from the queue and add it's unchecked adjacent positions to the end of the queue. With each of these we'll save a list of the moves that would get us to this node. Sooner or later we'll find a node with the target vehicle in the winning position (assuming it exists) and that moves list is the solution. Well, not quite done - since all of the moves are single block moves solution will be the the shortest possible measured by number of blocks moved, but is probably not optimum in terms of vehicles moved. e.g. moving a car 3 blocks to the left will show as 3 moves in the solution. I wrote an OptimizeMoves procedure to combine these moves when possible. I guess it's not perfect since I have solved cases with fewer vehicle moves than the program reports. In the next version I may try expanding the definition of adjacents to include multiple block moves. The search code exists in a separate file MakeWinningMoveList2.Inc just to ease code browsing during debugging. It's included in the main program unit U_TrafficJams1.pas with the compiler Include directive: {$I MakeWinningMoves2.Inc} Addendum March 15, 2008: Grandson Luke recently challenged me with a hand-drawn diagram of a case that had a vehicle blocking the red target vehicle from the "exit" and moves in the same direction as the target. This meant that the blocking car had to be physically removed when it reached the Exit block so that the red car could reach the Exit. In the program the blocking vehicle had to be removed or at least made invisible when it reach the Exit block. Version 1.1 posted today does that. Luke's Puzzle now appears as the 1st entry in the Intermediate level of the included cases.
Running/Exploring the Program
Suggestions for Further Explorations
Modified: May 15, 2018 |
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |