]> git.zerfleddert.de Git - FreeShisen/blob - src/org/proofofconcept/shisensho/Board.java
436d187de6c869fd137fd02dd3c70f87bb084196
[FreeShisen] / src / org / proofofconcept / shisensho / Board.java
1 package org.proofofconcept.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 int k=0;
280 for (List<Point> points : piecePoints) {
281 int n=(int)points.size();
282 for (int i=0;i<n;i++) {
283 Point a=points.get(i);
284 for (int j=i+1;j<n;j++) {
285 Point b=points.get(j);
286 List<Point> path=getPath(a.copy(),b.copy());
287 if (path!=null && path.size()>0) {
288 result.add(new Line(a,b));
289 if (nresults++==maxResults) break;
290 }
291 }
292 if (nresults==maxResults) break;
293 }
294 k++;
295 if (nresults==maxResults) break;
296 }
297 return result;
298 }
299
300 public int getNumPieces() {
301 int result=0;
302 for (int j=0;j<boardSize[1];j++) {
303 for (int i=0;i<boardSize[0];i++) {
304 if (board[i][j]!=0) result++;
305 }
306 }
307 return result;
308 }
309
310 // ----------------------
311 // Private methods
312 // ----------------------
313
314 /* RAND_MAX assumed to be 32767 */
315 private int myrand() {
316 return (int)Math.floor(Math.random()*32768);
317 }
318
319 private String StringRepeat(String s, int n) {
320 String result="";
321 for (int i=0;i<n;i++)
322 result+=s;
323 return result;
324 }
325
326 private int findFreeRow(int j) {
327 for (int i=1;i<boardSize[0]-1;i++) {
328 if (board[i][j]!=0) return (i-1);
329 }
330 return (boardSize[0]-1-1);
331 }
332
333 private List<Line> getHorizontalLines(Point excludeA, Point excludeB) {
334 List<Line> result=new ArrayList<Line>();
335 for (int i=0;i<boardSize[0];i++) {
336 int j0=-1;
337 boolean empty;
338 for (int j=0;j<boardSize[1];j++) {
339 empty=(board[i][j]==0 || (i==excludeA.i && j==excludeA.j)
340 || (i==excludeB.i && j==excludeB.j));
341 if (j0==-1 && empty) {
342 j0=j;
343 } else if (j0!=-1 && !empty) {
344 result.add(new Line(new Point(i,j0), new Point(i,j-1)));
345 j0=-1;
346 }
347 }
348 if (j0!=-1) result.add(new Line(new Point(i,j0), new Point(i,boardSize[1]-1)));
349 }
350
351 // stdout.printf("\ngetHorizontalLines( %s, %s ): ",excludeA.toString(),excludeB.toString());
352 // for (Line line : result) stdout.printf("%s ",line.toString());
353 // stdout.printf("\n");
354
355 return result;
356 }
357
358 private List<Line> getVerticalLines(Point excludeA, Point excludeB) {
359 List<Line> result=new ArrayList<Line>();
360 for (int j=0;j<boardSize[1];j++) {
361 int i0=-1;
362 boolean empty;
363 for (int i=0;i<boardSize[0];i++) {
364 empty=(board[i][j]==0 || (i==excludeA.i && j==excludeA.j)
365 || (i==excludeB.i && j==excludeB.j));
366 if (i0==-1 && empty) {
367 i0=i;
368 } else if (i0!=-1 && !empty) {
369 result.add(new Line(new Point(i0,j), new Point(i-1,j)));
370 i0=-1;
371 }
372 }
373 if (i0!=-1) result.add(new Line(new Point(i0,j), new Point(boardSize[0]-1,j)));
374 }
375
376 // stdout.printf("\ngetVerticalLines( %s, %s ): ",excludeA.toString(),excludeB.toString());
377 // for (Line line : result) stdout.printf("%s ",line.toString());
378 // stdout.printf("\n");
379
380 return result;
381 }
382
383 private void processGravity(Point p) {
384 if (gravity) for (int i=p.i;i>0;i--) board[i][p.j]=board[i-1][p.j];
385 }
386
387 private void undoGravity(Point p) {
388 if (gravity) for (int i=0;i<p.i;i++) board[i][p.j]=board[i+1][p.j];
389 }
390
391 }
Impressum, Datenschutz