X-Git-Url: http://git.zerfleddert.de/cgi-bin/gitweb.cgi/FreeShisen/blobdiff_plain/b023eec723db5ee6d0a6a6aca7795c391d98377e..d0e04237b00df7c11616f359200255a8b47e79d7:/src/de/cwde/shisensho/Board.java

diff --git a/src/de/cwde/shisensho/Board.java b/src/de/cwde/shisensho/Board.java
new file mode 100644
index 0000000..140b855
--- /dev/null
+++ b/src/de/cwde/shisensho/Board.java
@@ -0,0 +1,389 @@
+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];
+	}
+
+}