KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > khumpangame > Model


1 package khumpangame;
2
3 import java.util.*;
4 import java.awt.Color JavaDoc;
5
6 /** the well known Khum Pan game (l'âne rouge en français)
7   [1] http://www.asiaspiel.ch/
8 */
9 public class Model
10 {
11   // the blocs positions zero = no piece.
12 private final int[][] actualPositions;
13   private final int[][] startPositions; // used to reset
14 private final int[][] endPositions; // used in hasReachedEndPosition()
15
16   public static final int[][] standardProblemStartPosition = new int[][] { // line, col
17 {1, 2, 2, 3},
18     {1, 2, 2, 3},
19     {0, 4, 4, 0},
20     {5, 6, 7, 8},
21     {5, 9, 10, 8} };
22
23   public static final int[][] standardProblemEndPosition = new int[][] { // line, col
24 {1, 5, 8, 3},
25     {1, 5, 8, 3},
26     {6, 7, 4, 4},
27     {0, 2, 2, 9},
28     {0, 2, 2, 10} };
29
30   public int numberOfMoves = 0;
31
32   /** default model
33   */
34   public Model()
35   {
36     this.startPositions = copy( standardProblemStartPosition );
37     this.endPositions = copy( standardProblemEndPosition );
38     this.actualPositions = copy( standardProblemStartPosition );
39   }
40
41
42   /** allow building your own problem !
43   */
44   public Model(int[][] startPositions, int[][] endPositions)
45   {
46     this.startPositions = copy( startPositions );
47     this.endPositions = copy( endPositions );
48     this.actualPositions = copy( startPositions );
49   }
50
51   public int getNumberOfLines() { return this.actualPositions.length; }
52   public int getNumberOfColumns() { return this.actualPositions[0].length; }
53
54   /** copy the array (deeper than clone !)
55   */
56   private int[][] copy(int[][] a)
57   {
58     //return (int[][]) a.clone(); // #### ERROR: this lead to the same reference !!!!!!!!!!
59
60     int[][] copy = new int[a.length][a[0].length];
61     for(int i=0; i<a.length; i++)
62     {
63       for(int j=0; j<a[0].length; j++)
64       {
65         copy[i][j] = a[i][j];
66       }
67     }
68     return copy;
69   }
70
71   public void reset()
72   {
73     for(int line=0; line<this.getNumberOfLines(); line++)
74     {
75       for(int col=0; col<this.getNumberOfColumns(); col++)
76       {
77         this.actualPositions[line][col] = startPositions[line][col];
78       }
79     }
80     this.numberOfMoves = 0;
81   }
82
83   public Color JavaDoc getColorForPiece(int piece)
84   {
85     if(piece==2) return Color.red;
86     if(piece==1 || piece==3 || piece==4 || piece==5 || piece==8) return Color.blue;
87     return Color.magenta;
88   }
89
90   /** -1: out of bounds
91   * 0: no piece.
92   * 1+: piece
93   */
94   public synchronized int getPieceAt(int x, int y)
95   {
96      if(x<0) return -1;
97      if(y<0) return -1;
98      if(y>=this.getNumberOfLines()) return -1;
99      if(x>=this.getNumberOfColumns()) return -1;
100
101      return actualPositions[y][x]; // line, col
102 }
103
104   /** @param dx must be +1 or -1
105   */
106   public synchronized void moveX(int piece, int dx)
107   {
108     if(!canMoveX(piece, dx)) return;
109     if(piece<=0) return;
110
111     Vector<int[]> newPos = new Vector<int[]>();
112     for(int line=0; line<this.getNumberOfLines(); line++)
113     {
114        for(int col=0; col<this.getNumberOfColumns(); col++)
115        {
116           if(actualPositions[line][col]==piece)
117           {
118              actualPositions[line][col] = 0;
119              newPos.addElement(new int[]{line,col+dx});
120           }
121        }
122     }
123
124     for(int[] pos: newPos)
125     {
126       actualPositions[pos[0]][pos[1]] = piece;
127     }
128
129     numberOfMoves++;
130   }
131
132   public synchronized void moveY(int piece, int dy)
133   {
134     if(!canMoveY(piece, dy)) return;
135     if(piece<=0) return;
136
137     Vector<int[]> newPos = new Vector<int[]>();
138     for(int line=0; line<this.getNumberOfLines(); line++)
139     {
140        for(int col=0; col<getNumberOfColumns(); col++)
141        {
142           if(actualPositions[line][col]==piece)
143           {
144              actualPositions[line][col] = 0;
145              newPos.addElement(new int[]{line+dy, col});
146           }
147        }
148     }
149
150     for(int[] pos: newPos)
151     {
152       actualPositions[pos[0]][pos[1]] = piece;
153     }
154
155     numberOfMoves++;
156   }
157
158
159   /** @param dx must be +1 or -1
160   */
161   public synchronized boolean canMoveX(int piece, int dx)
162   {
163     if(Math.abs(dx)!=1) throw new IllegalArgumentException JavaDoc("dx must be +-1, not "+dx);
164
165     for(int line=0; line<this.getNumberOfLines(); line++)
166     {
167       for(int col=0; col<this.getNumberOfColumns(); col++)
168       {
169          if(actualPositions[line][col]==piece)
170          {
171            int newCol = col+dx;
172            // border bounds
173 if(newCol<0) return false;
174            if(newCol>=getNumberOfColumns()) return false;
175            // not same piece and not empty
176 if(actualPositions[line][newCol]!=0 && actualPositions[line][newCol]!=piece) return false;
177          }
178       }
179     }
180     // ok, can move
181 return true;
182   }
183
184   /** @param dy is +-1
185   */
186   public synchronized boolean canMoveY(int piece, int dy)
187   {
188     if(Math.abs(dy)!=1) throw new IllegalArgumentException JavaDoc("dy must be +-1, not "+dy);
189
190     for(int line=0; line<this.getNumberOfLines(); line++)
191     {
192       for(int col=0; col<this.getNumberOfColumns(); col++)
193       {
194          if(actualPositions[line][col]==piece)
195          {
196            int newLine = line+dy;
197            // border bounds
198 if(newLine<0) return false;
199            if(newLine>=this.getNumberOfLines()) return false;
200            // not same piece and not empty
201 if(actualPositions[newLine][col]!=0 && actualPositions[newLine][col]!=piece) return false;
202          }
203       }
204     }
205     // ok, can move
206 return true;
207   }
208
209   /** @return true if the actualPositions is corresponding to the endPositions.
210   */
211   public boolean hasReachEndPosition()
212   {
213      // subtle: compare modulo reorderings of same looking pieces
214 // to achieve this, we must canonocalize the numberings
215
216      int[][] conf1 = canonicalizePositions(this.actualPositions);
217      int[][] conf2 = canonicalizePositions(this.endPositions);
218
219      for(int i=0; i<conf1.length; i++)
220      {
221         if(!Arrays.equals( conf1[i], conf2[i])) return false;
222      }
223
224      return true;
225   }
226
227   /** in order to compare two positions modulo swap of same looking pieces,
228   * one can call this to make two configurations comparable.
229   * This simply rename the pieces from left to right, top to botton, starting with 0
230   */
231   private int[][] canonicalizePositions(int[][] positions)
232   {
233     // Canonicalisation: Algorithm
234 // Step 1: walk top-down, left-right and memorize the name of first occuring pieces
235 //
236 Vector<Integer JavaDoc> piecesIDs = new Vector<Integer JavaDoc>();
237     for( int[] line: positions)
238     {
239       for(int piece: line)
240       {
241          if(!piecesIDs.contains(piece)) piecesIDs.add(piece);
242       }
243     }
244
245     // Step 2: just reattribute the piece number
246 //
247 int[][] normalized = new int[getNumberOfLines()][getNumberOfColumns()];
248     for(int line=0; line<this.getNumberOfLines(); line++)
249     {
250       for(int col=0; col<this.getNumberOfColumns(); col++)
251       {
252          int piece = positions[line][col];
253          // the indexof give 0 for the first appearing piece, 1 for the second
254 // that's the key point of our canonicalisation
255 normalized[line][col] = piecesIDs.indexOf( piece );
256       }
257     }
258
259     return normalized;
260   }
261
262   public static void main(String JavaDoc[] args)
263   {
264     new MoveApp(true);
265   }
266
267
268 } // Model
Popular Tags