Traffic Jam

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

Help 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.   

No problem?

Try this one!

Background & Techniques

Here'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:

Hints are available if you get stuck.
You can undo moves if you change your mind
Program will solve problems for you.
Cases are defined in a plain text file making is easy to add additional problems.
Best scores are retained and displayed along with the player's name.
Cases can be printed with the moves necessary to solve them.
Additional cases can added to the case text file.  Exits can be defined on any side of the board.  

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):

;     format for each new case, a Case line
; Case,levelname-nbr
;     followed by multiple vehicle definition lines
;     format for each vehicle line.
; Column,row,direction,size,color,winning-direction (for one vehicle)

;     direction symbols are U (up), D (down), L (left), R (right) 

;     color names are: red, blue, green, yellow, green,

;     pink,  orange aqua, lime,  dkgray, dkblue,  

;     Ltblue,  Ltgreen,  Ltpurple

;     One of the vehicles must have an exit direction specified after

;     the color

 

Case,Test-0 
2,3,R,2,RED,R
4,2,d,3,blue
3,6,r,3,green
4,5,r,2,dkblue


Non-programmers can jump to the bottom of the page to download an executable version.

Programmer Stuff

Here'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 Pieces

I 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 Search

Here'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:

  1. A way to generate a unique id (key) for each board configuration.  GenKey procedure does this for us.   I decided to use a letter to represent the row (for left/right movers) or column (for up/down movers)  for the head of each vehicle.  So a board with 8 vehicles will have an 8 letter string key, unique to any arrangement. 
  2. A mechanism for keeping track of all of the adjacent nodes for each node.  We use an array of Tvertex class instances containing information about the vertex, mainly  the board and the list of moves that got us here.
  3. A list structure (stack or queue)  to let us systematically check the nodes looking for a winning position.  I have a TStringlist named queue, how original.  The strings part of each list entry is the key of the vertex and  the objects field holds the vertex object with the rest of the information.   
  4. A way to test whether we have already visited a node to avoid chasing ourselves around in circles.  Here, there's a VerticeA array of integers which hold hashed versions of the string vertex keys.  In debugging, I've seen up to 10,000 board positions checked before finding a solution.   I defined VerticeA with 100,000 entries just to be safe and to reduce collisions when adding keys. See the Math Topic Hashing page for more good stuff on that subject.   Dynamic arrays would be more elegant, but there would be some performance penalty.   Similarly, the original string keys could be kept in a Stringlist with some performance penalty.   Hashing is generally the fastest way to find if an item already exists (i.e. a particular vertex has already been visited).

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

Version 2 will add back interactive case development, including additional vehicle shapes, patterns and images that are difficult to include in text file definition.
Still need some cleanup in moving vehicles - I  get occasional artifacts when vehicles are dragged too rapidly.  And smooth moving would be nice.

Modified:  February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.