f1627b046d41396799f4dd0895ec03881b5839c4
[FreeShisen] / src / de / cwde / shisensho / Board.java
1 package de.cwde.shisensho;
2
3 import java.util.ArrayList;
4 import java.util.LinkedList;
5 import java.util.List;
6
7 public class Board {
8 private static String charpieces = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
9
10 public int difficulty=1; // 1=Hard ... N=Easy
11 public boolean gravity=true;
12 public int [] boardSize;
13 public char[][] board;
14 public LinkedList<Move> history;
15
16 // ----------------------
17 // Public methods
18 // ----------------------
19
20 public Board() {
21 }
22
23 // The board always has a 1-square width free rectangle that has
24 // to be taken into account when specifying the size
25 public void initialize(int sizeI, int sizeJ) {
26 boardSize = new int[2];
27 boardSize[0]=sizeI;
28 boardSize[1]=sizeJ;
29 board = new char[boardSize[0]][boardSize[1]];
30 for (int i=0;i<boardSize[0];i++)
31 for (int j=0;j<boardSize[1];j++)
32 board[i][j]=0;
33 history=new LinkedList<Move>();
34 }
35
36 public static String pieceToString(char piece) {
37 return charpieces.substring(piece,1);
38 }
39
40 public static char StringToPiece(String piece) {
41 char upiece;
42 long charpiecesLen=charpieces.length();
43 for(upiece=0;(upiece<charpiecesLen && charpieces.substring(upiece,1)!=piece);upiece++);
44 if (upiece<charpiecesLen) return upiece;
45 else return 0;
46 }
47
48 public String toString() {
49 String result=" ";
50 for (int j=0;j<boardSize[1];j++) {
51 if (j>0) result+=" ";
52 result+=""+(j%10);
53 }
54 result+="\n "+StringRepeat("--",boardSize[1]);
55 for (int i=0;i<boardSize[0];i++) {
56 result+="\n"+(i%10)+"|";
57 for (int j=0;j<boardSize[1];j++) {
58 if (j>0) result+=" ";
59 result+=charpieces.substring(board[i][j],board[i][j]+1);
60 }
61 result+=" |\n";
62 if (i<boardSize[0]-1)
63 result+=" |"+StringRepeat(" ",boardSize[1])+"|";
64 }
65 result+=" "+StringRepeat("--",boardSize[1])+"\n";
66 return result;
67 }
68
69 public void buildRandomBoard(int sizeI, int sizeJ, int difficulty, boolean gravity) {
70 initialize(sizeI,sizeJ);
71 this.difficulty=difficulty;
72 this.gravity=gravity;
73
74 int numDifferentPieces=((boardSize[0]-2)*(boardSize[1]-2)/((difficulty+1)*2))+1;
75 for (int n=0;n<((difficulty+1)*2);n++) {
76 for (int k=0;k<numDifferentPieces;k++) {
77 int i,j;
78 do {
79 j=(myrand() % (boardSize[1]-2))+1;
80 i=findFreeRow(j);
81 } while (i<1);
82 // ShisenSho.log("numDifferentPieces="+numDifferentPieces+", n="+n+", k="+(int)k+", i="+i+", j="+j);
83 // ShisenSho.log(toString());
84 board[i][j]=(char)k;
85 }
86 }
87 }
88
89 /*
90 ALGORITHM TO COMPUTE CONNECTION PATH BETWEEN PIECES A (IA,JA) AND B (IB,JB)
91
92 - Delete A and B from the board (consider them as blank spaces)
93 - Calculate the set H of possible horizontal lines in the board (lines through blank spaces)
94 - Calculate the set V of possible vertical lines in the board
95 - Find HA, VA, HB, VB in the sets
96 - If HA=HB, result is a straight horizontal line A-B
97 - If VA=VB, result is a straight vertical line A-B
98 - If HA cuts VB, the result is an L line A-(IA,JB)-B
99 - If VA cuts HB, the result is an L line A-(IB,JA)-B
100 - If exists an V line that cuts HA and HB, the result is a Z line A-(IA,JV)-(IB-JV)-B
101 - If exists an H line that cuts VA and VB, the result is a Z line A-(IV,JA)-(IV,JB)-B
102
103 The following data types are defined:
104
105 - Board
106 - Point(int i, int j)
107 - Line(Point a, Point b)
108 - LineSet(Line l1, ..., Line lN)
109
110 The following operations are defined
111
112 - LineSet getHorizontalLines(Board board, Point a, Point b) // a and b needed to consider them as blank
113 - LineSet getVerticalLines(Board board, Point a, Point b)
114 - boolean lineIsHorizontal(Line l)
115 - boolean lineIsVertical(Line l)
116 - boolean lineContainsPoint(Line l, Point p)
117 - boolean lineEqualsLine(Line l1, Line l2)
118 - boolean lineCutsLine(Line l1, Line l2)
119 */
120 public List<Point> getPath(Point a, Point b) {
121 List<Point> result=new ArrayList<Point>();
122
123 if (getPiece(a)!=getPiece(b)) return result;
124
125 List<Line> h=getHorizontalLines(a,b);
126 List<Line> v=getVerticalLines(a,b);
127 Line ha=null, va=null, hb=null, vb=null;
128
129 for (Line l : h) {
130 if (l.contains(a)) ha=l;
131 if (l.contains(b)) hb=l;
132 if (ha!=null && hb!=null) break;
133 }
134
135 for (Line l : v) {
136 if (l.contains(a)) va=l;
137 if (l.contains(b)) vb=l;
138 if (va!=null && vb!=null) break;
139 }
140
141 // stdout.printf("va=%s, ha=%s, vb=%s, hb=%s\n",va.toString(),ha.toString(),vb.toString(),hb.toString());
142
143 if ((ha==null && va==null) || (hb==null && vb==null))
144 return result;
145
146 if (ha.equals(hb) || va.equals(vb)) {
147 result.add(a);
148 result.add(b);
149 return result;
150 }
151
152 Point ab;
153
154 ab=ha.cuts(vb);
155 // stdout.printf("(ha cuts vb) ab=%s\n",ab.toString());
156
157 if (ab!=null) {
158 result.add(a);
159 result.add(ab);
160 result.add(b);
161 return result;
162 }
163
164 ab=va.cuts(hb);
165 // stdout.printf("(va cuts hb) ab=%s\n",ab.toString());
166
167 if (ab!=null) {
168 result.add(a);
169 result.add(ab);
170 result.add(b);
171 return result;
172 }
173
174 for (Line l : v) {
175 Point al=l.cuts(ha);
176 Point bl=l.cuts(hb);
177
178 // stdout.printf("(%s cuts ha) al=%s\n",l.toString(),al.toString());
179 // stdout.printf("(%s cuts hb) bl=%s\n",l.toString(),bl.toString());
180
181 if (al!=null && bl!=null) {
182 result.add(a);
183 result.add(al);
184 result.add(bl);
185 result.add(b);
186 return result;
187 }
188 }
189
190 for (Line l : h) {
191 Point al=l.cuts(va);
192 Point bl=l.cuts(vb);
193
194 // stdout.printf("(%s cuts va) al=%s\n",l.toString(),al.toString());
195 // stdout.printf("(%s cuts vb) bl=%s\n",l.toString(),bl.toString());
196
197 if (al!=null && bl!=null) {
198 result.add(a);
199 result.add(al);
200 result.add(bl);
201 result.add(b);
202 return result;
203 }
204 }
205
206 return result;
207 }
208
209 public char getPiece(Point p) {
210 return board[p.i][p.j];
211 }
212
213 public void setPiece(Point p, char piece) {
214 board[p.i][p.j]=piece;
215 }
216
217 public String getStrPiece(Point p) {
218 char piece=board[p.i][p.j];
219 return charpieces.substring(piece,1);
220 }
221
222 public void setStrPiece(Point p, String piece) {
223 char upiece;
224 long charpiecesLen=charpieces.length();
225 for(upiece=0;(upiece<charpiecesLen && charpieces.substring(upiece,1)!=piece);upiece++);
226 if (upiece<charpiecesLen) board[p.i][p.j]=upiece;
227 }
228
229 public void play(Point a0, Point b0) {
230 // It's important to sink the upper piece first
231 Point a=(a0.i<b0.i)?a0:b0;
232 Point b=(a0.i<b0.i)?b0:a0;
233 Move m=new Move(a,b,getPiece(a));
234 history.add(0,m);
235 setPiece(a,(char)0);
236 processGravity(a);
237 setPiece(b,(char)0);
238 processGravity(b);
239 }
240
241 public boolean getCanUndo() {
242 return !history.isEmpty();
243 }
244
245 public void undo() {
246 if (!getCanUndo()) return;
247 Move m=history.remove(0);
248 undoGravity(m.b);
249 setPiece(m.b,m.piece);
250 undoGravity(m.a);
251 setPiece(m.a,m.piece);
252 }
253
254 public List<Line> getPairs(int maxResults) {
255 List<Line> result=new ArrayList<Line>();
256 List<Integer> pieces=new ArrayList<Integer>();
257 List<List<Point>> piecePoints=new ArrayList<List<Point>>();
258 for (int i=0;i<boardSize[0];i++)
259 for (int j=0;j<boardSize[1];j++) {
260 int piece=(int)board[i][j];
261 if (piece==0) continue;
262 int key=pieces.indexOf(piece);
263 Point p=new Point(i,j);
264 if (key==-1) {
265 List<Point> points0=new ArrayList<Point>();
266 points0.add(p);
267 pieces.add(piece);
268 piecePoints.add(points0);
269
270 key=pieces.indexOf(piece);
271 piecePoints.get(key);
272 } else {
273 List<Point> points1=piecePoints.get(key);
274 points1.add(p);
275 }
276 }
277
278 int nresults=0;
279 for (List<Point> points : piecePoints) {
280 int n=(int)points.size();
281 for (int i=0;i<n;i++) {
282 Point a=points.get(i);
283 for (int j=i+1;j<n;j++) {
284 Point b=points.get(j);
285 List<Point> path=getPath(a.copy(),b.copy());
286 if (path!=null && path.size()>0) {
287 result.add(new Line(a,b));
288 if (nresults++==maxResults) break;
289 }
290 }
291 if (nresults==maxResults) break;
292 }
293 if (nresults==maxResults) break;
294 }
295 return result;
296 }
297
298 public int getNumPieces() {
299 int result=0;
300 for (int j=0;j<boardSize[1];j++) {
301 for (int i=0;i<boardSize[0];i++) {
302 if (board[i][j]!=0) result++;
303 }
304 }
305 return result;
306 }
307
308 // ----------------------
309 // Private methods
310 // ----------------------
311
312 /* RAND_MAX assumed to be 32767 */
313 private int myrand() {
314 return (int)Math.floor(Math.random()*32768);
315 }
316
317 private String StringRepeat(String s, int n) {
318 String result="";
319 for (int i=0;i<n;i++)
320 result+=s;
321 return result;
322 }
323
324 private int findFreeRow(int j) {
325 for (int i=1;i<boardSize[0]-1;i++) {
326 if (board[i][j]!=0) return (i-1);
327 }
328 return (boardSize[0]-1-1);
329 }
330
331 private List<Line> getHorizontalLines(Point excludeA, Point excludeB) {
332 List<Line> result=new ArrayList<Line>();
333 for (int i=0;i<boardSize[0];i++) {
334 int j0=-1;
335 boolean empty;
336 for (int j=0;j<boardSize[1];j++) {
337 empty=(board[i][j]==0 || (i==excludeA.i && j==excludeA.j)
338 || (i==excludeB.i && j==excludeB.j));
339 if (j0==-1 && empty) {
340 j0=j;
341 } else if (j0!=-1 && !empty) {
342 result.add(new Line(new Point(i,j0), new Point(i,j-1)));
343 j0=-1;
344 }
345 }
346 if (j0!=-1) result.add(new Line(new Point(i,j0), new Point(i,boardSize[1]-1)));
347 }
348
349 // stdout.printf("\ngetHorizontalLines( %s, %s ): ",excludeA.toString(),excludeB.toString());
350 // for (Line line : result) stdout.printf("%s ",line.toString());
351 // stdout.printf("\n");
352
353 return result;
354 }
355
356 private List<Line> getVerticalLines(Point excludeA, Point excludeB) {
357 List<Line> result=new ArrayList<Line>();
358 for (int j=0;j<boardSize[1];j++) {
359 int i0=-1;
360 boolean empty;
361 for (int i=0;i<boardSize[0];i++) {
362 empty=(board[i][j]==0 || (i==excludeA.i && j==excludeA.j)
363 || (i==excludeB.i && j==excludeB.j));
364 if (i0==-1 && empty) {
365 i0=i;
366 } else if (i0!=-1 && !empty) {
367 result.add(new Line(new Point(i0,j), new Point(i-1,j)));
368 i0=-1;
369 }
370 }
371 if (i0!=-1) result.add(new Line(new Point(i0,j), new Point(boardSize[0]-1,j)));
372 }
373
374 // stdout.printf("\ngetVerticalLines( %s, %s ): ",excludeA.toString(),excludeB.toString());
375 // for (Line line : result) stdout.printf("%s ",line.toString());
376 // stdout.printf("\n");
377
378 return result;
379 }
380
381 private void processGravity(Point p) {
382 if (gravity) for (int i=p.i;i>0;i--) board[i][p.j]=board[i-1][p.j];
383 }
384
385 private void undoGravity(Point p) {
386 if (gravity) for (int i=0;i<p.i;i++) board[i][p.j]=board[i+1][p.j];
387 }
388
389 }
Impressum, Datenschutz