--- /dev/null
+package de.cwde.shisensho;
+
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.List;
+
+public class Board {
+ private static String charpieces = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
+
+ public int difficulty=1; // 1=Hard ... N=Easy
+ public boolean gravity=true;
+ public int [] boardSize;
+ public char[][] board;
+ public LinkedList<Move> history;
+
+ // ----------------------
+ // Public methods
+ // ----------------------
+
+ public Board() {
+ }
+
+ // The board always has a 1-square width free rectangle that has
+ // to be taken into account when specifying the size
+ public void initialize(int sizeI, int sizeJ) {
+ boardSize = new int[2];
+ boardSize[0]=sizeI;
+ boardSize[1]=sizeJ;
+ board = new char[boardSize[0]][boardSize[1]];
+ for (int i=0;i<boardSize[0];i++)
+ for (int j=0;j<boardSize[1];j++)
+ board[i][j]=0;
+ history=new LinkedList<Move>();
+ }
+
+ public static String pieceToString(char piece) {
+ return charpieces.substring(piece,1);
+ }
+
+ public static char StringToPiece(String piece) {
+ char upiece;
+ long charpiecesLen=charpieces.length();
+ for(upiece=0;(upiece<charpiecesLen && charpieces.substring(upiece,1)!=piece);upiece++);
+ if (upiece<charpiecesLen) return upiece;
+ else return 0;
+ }
+
+ public String toString() {
+ String result=" ";
+ for (int j=0;j<boardSize[1];j++) {
+ if (j>0) result+=" ";
+ result+=""+(j%10);
+ }
+ result+="\n "+StringRepeat("--",boardSize[1]);
+ for (int i=0;i<boardSize[0];i++) {
+ result+="\n"+(i%10)+"|";
+ for (int j=0;j<boardSize[1];j++) {
+ if (j>0) result+=" ";
+ result+=charpieces.substring(board[i][j],board[i][j]+1);
+ }
+ result+=" |\n";
+ if (i<boardSize[0]-1)
+ result+=" |"+StringRepeat(" ",boardSize[1])+"|";
+ }
+ result+=" "+StringRepeat("--",boardSize[1])+"\n";
+ return result;
+ }
+
+ public void buildRandomBoard(int sizeI, int sizeJ, int difficulty, boolean gravity) {
+ initialize(sizeI,sizeJ);
+ this.difficulty=difficulty;
+ this.gravity=gravity;
+
+ int numDifferentPieces=((boardSize[0]-2)*(boardSize[1]-2)/((difficulty+1)*2))+1;
+ for (int n=0;n<((difficulty+1)*2);n++) {
+ for (int k=0;k<numDifferentPieces;k++) {
+ int i,j;
+ do {
+ j=(myrand() % (boardSize[1]-2))+1;
+ i=findFreeRow(j);
+ } while (i<1);
+ // ShisenSho.log("numDifferentPieces="+numDifferentPieces+", n="+n+", k="+(int)k+", i="+i+", j="+j);
+ // ShisenSho.log(toString());
+ board[i][j]=(char)k;
+ }
+ }
+ }
+
+ /*
+ ALGORITHM TO COMPUTE CONNECTION PATH BETWEEN PIECES A (IA,JA) AND B (IB,JB)
+
+ - Delete A and B from the board (consider them as blank spaces)
+ - Calculate the set H of possible horizontal lines in the board (lines through blank spaces)
+ - Calculate the set V of possible vertical lines in the board
+ - Find HA, VA, HB, VB in the sets
+ - If HA=HB, result is a straight horizontal line A-B
+ - If VA=VB, result is a straight vertical line A-B
+ - If HA cuts VB, the result is an L line A-(IA,JB)-B
+ - If VA cuts HB, the result is an L line A-(IB,JA)-B
+ - If exists an V line that cuts HA and HB, the result is a Z line A-(IA,JV)-(IB-JV)-B
+ - If exists an H line that cuts VA and VB, the result is a Z line A-(IV,JA)-(IV,JB)-B
+
+ The following data types are defined:
+
+ - Board
+ - Point(int i, int j)
+ - Line(Point a, Point b)
+ - LineSet(Line l1, ..., Line lN)
+
+ The following operations are defined
+
+ - LineSet getHorizontalLines(Board board, Point a, Point b) // a and b needed to consider them as blank
+ - LineSet getVerticalLines(Board board, Point a, Point b)
+ - boolean lineIsHorizontal(Line l)
+ - boolean lineIsVertical(Line l)
+ - boolean lineContainsPoint(Line l, Point p)
+ - boolean lineEqualsLine(Line l1, Line l2)
+ - boolean lineCutsLine(Line l1, Line l2)
+ */
+ public List<Point> getPath(Point a, Point b) {
+ List<Point> result=new ArrayList<Point>();
+
+ if (getPiece(a)!=getPiece(b)) return result;
+
+ List<Line> h=getHorizontalLines(a,b);
+ List<Line> v=getVerticalLines(a,b);
+ Line ha=null, va=null, hb=null, vb=null;
+
+ for (Line l : h) {
+ if (l.contains(a)) ha=l;
+ if (l.contains(b)) hb=l;
+ if (ha!=null && hb!=null) break;
+ }
+
+ for (Line l : v) {
+ if (l.contains(a)) va=l;
+ if (l.contains(b)) vb=l;
+ if (va!=null && vb!=null) break;
+ }
+
+ // stdout.printf("va=%s, ha=%s, vb=%s, hb=%s\n",va.toString(),ha.toString(),vb.toString(),hb.toString());
+
+ if ((ha==null && va==null) || (hb==null && vb==null))
+ return result;
+
+ if (ha.equals(hb) || va.equals(vb)) {
+ result.add(a);
+ result.add(b);
+ return result;
+ }
+
+ Point ab;
+
+ ab=ha.cuts(vb);
+ // stdout.printf("(ha cuts vb) ab=%s\n",ab.toString());
+
+ if (ab!=null) {
+ result.add(a);
+ result.add(ab);
+ result.add(b);
+ return result;
+ }
+
+ ab=va.cuts(hb);
+ // stdout.printf("(va cuts hb) ab=%s\n",ab.toString());
+
+ if (ab!=null) {
+ result.add(a);
+ result.add(ab);
+ result.add(b);
+ return result;
+ }
+
+ for (Line l : v) {
+ Point al=l.cuts(ha);
+ Point bl=l.cuts(hb);
+
+ // stdout.printf("(%s cuts ha) al=%s\n",l.toString(),al.toString());
+ // stdout.printf("(%s cuts hb) bl=%s\n",l.toString(),bl.toString());
+
+ if (al!=null && bl!=null) {
+ result.add(a);
+ result.add(al);
+ result.add(bl);
+ result.add(b);
+ return result;
+ }
+ }
+
+ for (Line l : h) {
+ Point al=l.cuts(va);
+ Point bl=l.cuts(vb);
+
+ // stdout.printf("(%s cuts va) al=%s\n",l.toString(),al.toString());
+ // stdout.printf("(%s cuts vb) bl=%s\n",l.toString(),bl.toString());
+
+ if (al!=null && bl!=null) {
+ result.add(a);
+ result.add(al);
+ result.add(bl);
+ result.add(b);
+ return result;
+ }
+ }
+
+ return result;
+ }
+
+ public char getPiece(Point p) {
+ return board[p.i][p.j];
+ }
+
+ public void setPiece(Point p, char piece) {
+ board[p.i][p.j]=piece;
+ }
+
+ public String getStrPiece(Point p) {
+ char piece=board[p.i][p.j];
+ return charpieces.substring(piece,1);
+ }
+
+ public void setStrPiece(Point p, String piece) {
+ char upiece;
+ long charpiecesLen=charpieces.length();
+ for(upiece=0;(upiece<charpiecesLen && charpieces.substring(upiece,1)!=piece);upiece++);
+ if (upiece<charpiecesLen) board[p.i][p.j]=upiece;
+ }
+
+ public void play(Point a0, Point b0) {
+ // It's important to sink the upper piece first
+ Point a=(a0.i<b0.i)?a0:b0;
+ Point b=(a0.i<b0.i)?b0:a0;
+ Move m=new Move(a,b,getPiece(a));
+ history.add(0,m);
+ setPiece(a,(char)0);
+ processGravity(a);
+ setPiece(b,(char)0);
+ processGravity(b);
+ }
+
+ public boolean getCanUndo() {
+ return !history.isEmpty();
+ }
+
+ public void undo() {
+ if (!getCanUndo()) return;
+ Move m=history.remove(0);
+ undoGravity(m.b);
+ setPiece(m.b,m.piece);
+ undoGravity(m.a);
+ setPiece(m.a,m.piece);
+ }
+
+ public List<Line> getPairs(int maxResults) {
+ List<Line> result=new ArrayList<Line>();
+ List<Integer> pieces=new ArrayList<Integer>();
+ List<List<Point>> piecePoints=new ArrayList<List<Point>>();
+ for (int i=0;i<boardSize[0];i++)
+ for (int j=0;j<boardSize[1];j++) {
+ int piece=(int)board[i][j];
+ if (piece==0) continue;
+ int key=pieces.indexOf(piece);
+ Point p=new Point(i,j);
+ if (key==-1) {
+ List<Point> points0=new ArrayList<Point>();
+ points0.add(p);
+ pieces.add(piece);
+ piecePoints.add(points0);
+
+ key=pieces.indexOf(piece);
+ piecePoints.get(key);
+ } else {
+ List<Point> points1=piecePoints.get(key);
+ points1.add(p);
+ }
+ }
+
+ int nresults=0;
+ for (List<Point> points : piecePoints) {
+ int n=(int)points.size();
+ for (int i=0;i<n;i++) {
+ Point a=points.get(i);
+ for (int j=i+1;j<n;j++) {
+ Point b=points.get(j);
+ List<Point> path=getPath(a.copy(),b.copy());
+ if (path!=null && path.size()>0) {
+ result.add(new Line(a,b));
+ if (nresults++==maxResults) break;
+ }
+ }
+ if (nresults==maxResults) break;
+ }
+ if (nresults==maxResults) break;
+ }
+ return result;
+ }
+
+ public int getNumPieces() {
+ int result=0;
+ for (int j=0;j<boardSize[1];j++) {
+ for (int i=0;i<boardSize[0];i++) {
+ if (board[i][j]!=0) result++;
+ }
+ }
+ return result;
+ }
+
+ // ----------------------
+ // Private methods
+ // ----------------------
+
+ /* RAND_MAX assumed to be 32767 */
+ private int myrand() {
+ return (int)Math.floor(Math.random()*32768);
+ }
+
+ private String StringRepeat(String s, int n) {
+ String result="";
+ for (int i=0;i<n;i++)
+ result+=s;
+ return result;
+ }
+
+ private int findFreeRow(int j) {
+ for (int i=1;i<boardSize[0]-1;i++) {
+ if (board[i][j]!=0) return (i-1);
+ }
+ return (boardSize[0]-1-1);
+ }
+
+ private List<Line> getHorizontalLines(Point excludeA, Point excludeB) {
+ List<Line> result=new ArrayList<Line>();
+ for (int i=0;i<boardSize[0];i++) {
+ int j0=-1;
+ boolean empty;
+ for (int j=0;j<boardSize[1];j++) {
+ empty=(board[i][j]==0 || (i==excludeA.i && j==excludeA.j)
+ || (i==excludeB.i && j==excludeB.j));
+ if (j0==-1 && empty) {
+ j0=j;
+ } else if (j0!=-1 && !empty) {
+ result.add(new Line(new Point(i,j0), new Point(i,j-1)));
+ j0=-1;
+ }
+ }
+ if (j0!=-1) result.add(new Line(new Point(i,j0), new Point(i,boardSize[1]-1)));
+ }
+
+ // stdout.printf("\ngetHorizontalLines( %s, %s ): ",excludeA.toString(),excludeB.toString());
+ // for (Line line : result) stdout.printf("%s ",line.toString());
+ // stdout.printf("\n");
+
+ return result;
+ }
+
+ private List<Line> getVerticalLines(Point excludeA, Point excludeB) {
+ List<Line> result=new ArrayList<Line>();
+ for (int j=0;j<boardSize[1];j++) {
+ int i0=-1;
+ boolean empty;
+ for (int i=0;i<boardSize[0];i++) {
+ empty=(board[i][j]==0 || (i==excludeA.i && j==excludeA.j)
+ || (i==excludeB.i && j==excludeB.j));
+ if (i0==-1 && empty) {
+ i0=i;
+ } else if (i0!=-1 && !empty) {
+ result.add(new Line(new Point(i0,j), new Point(i-1,j)));
+ i0=-1;
+ }
+ }
+ if (i0!=-1) result.add(new Line(new Point(i0,j), new Point(boardSize[0]-1,j)));
+ }
+
+ // stdout.printf("\ngetVerticalLines( %s, %s ): ",excludeA.toString(),excludeB.toString());
+ // for (Line line : result) stdout.printf("%s ",line.toString());
+ // stdout.printf("\n");
+
+ return result;
+ }
+
+ private void processGravity(Point p) {
+ if (gravity) for (int i=p.i;i>0;i--) board[i][p.j]=board[i-1][p.j];
+ }
+
+ private void undoGravity(Point p) {
+ if (gravity) for (int i=0;i<p.i;i++) board[i][p.j]=board[i+1][p.j];
+ }
+
+}
projects / FreeShisen / blobdiff