2 * Quoridor server and related libraries
3 * Copyright (C) 2009-2010 Jaroslav Tulach <jaroslav.tulach@apidesign.org>
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program. Look for COPYING file in the top folder.
16 * If not, see http://www.gnu.org/licenses/.
19 package cz.xelfi.quoridor;
21 import cz.xelfi.quoridor.Player.Direction;
22 import java.io.BufferedReader;
23 import java.io.EOFException;
24 import java.io.IOException;
25 import java.io.Reader;
26 import java.io.Writer;
27 import java.util.ArrayList;
28 import java.util.Arrays;
29 import java.util.BitSet;
30 import java.util.Collection;
31 import java.util.Collections;
32 import java.util.HashSet;
33 import java.util.List;
35 import java.util.TreeSet;
36 import java.util.logging.Level;
37 import java.util.logging.Logger;
38 import java.util.regex.Matcher;
39 import java.util.regex.Pattern;
42 * Represents a snapshot of the game position,
43 * including all the placed and not-yet placed fences and player positions.
44 * It it can print itself to stream in
45 * <a href="http://www.gamerz.net/pbmserv/quoridor.html">ascii art format<a/>
46 * and can it read back. The class is immutable
47 * but it contains {@link #apply(cz.xelfi.quoridor.Move)}
48 * that produce new {@link Board} with position created after
49 * applying some {@link Move}. Use:
51 * Board whiteOnTurn = Board.empty();
52 * Board blackOnTurn = whiteOnTurn.apply(Move.NORTH);
53 * Board whiteAgain = blackOnTurn.apply(Move.SOUTH);
54 * Board withOneFence = whiteAgain.apply(Move.fence('D', 7));
57 * @author Jaroslav Tulach
59 public final class Board {
61 private final Player winner;
63 private final List<Player> players;
64 /** fences placed on board */
65 private final Set<Fence> fences;
66 /** occurpied bits (coordinates encoded by toIndex methods)
69 +-----------------------------------+
87 +-----------------------------------+
88 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
91 * even indexes == position of the pawns
92 * odd indexes == centers of fences
93 * even x odd == side of a fence
94 * odd x even == side of a fence
96 private final BitSet occupied;
97 /** which player's turn is next? */
98 private final int turn;
101 * Creates a new instance of Board
103 private Board (int x1, int y1, int f1, int x2, int y2, int f2) {
104 this.players = Collections.unmodifiableList (Arrays.asList (new Player[] {
105 new Player (x1, y1, f1, Player.Direction.NORTH),
106 new Player (x2, y2, f2, Player.Direction.SOUTH),
108 this.fences = Collections.emptySet ();
110 this.occupied = computeOccupied (players, fences);
111 } catch (IllegalPositionException ex) {
112 throw new IllegalStateException (ex.getMessage ());
118 /** Copy constructor that provides players and fences.
120 private Board (int turn, List<Player> players, Set<Fence> fences)
121 throws IllegalPositionException {
122 this.players = Collections.unmodifiableList (players);
123 this.fences = Collections.unmodifiableSet (fences);
124 this.occupied = computeOccupied (players, fences);
126 for (Player p : players) {
127 BitSet bs = new BitSet(17 * 17);
128 if (!accessibleFinalLine (p, p.endDirection, occupied, bs)) {
129 throw new IllegalPositionException ("Player " + p + " cannot reach " + p.endDirection + " side"); // NOI18N
132 this.turn = turn % players.size();
136 /** Copy constructor for resigning the game */
137 private Board(Board previous, int winner) {
138 this.players = previous.players;
139 this.turn = winner % players.size();
140 this.fences = previous.fences;
141 this.occupied = previous.occupied;
142 this.winner = players.get(this.turn);
145 /** Returns empty board with default starting position.
146 * @return board with two pawns.
148 public static Board empty () {
149 return new Board (8, 0, 10, 8, 16, 10);
152 /** Returns players in the game.
153 * @return player object
155 public List<Player> getPlayers () {
159 /** The fences currently on board.
161 * @return immutable set of Fences
163 public Set<Fence> getFences () {
167 /** The player that is supposed to play now.
168 * @return the player to do next move, null if the game is over
170 public Player getCurrentPlayer() {
171 if (getWinner() != null) {
174 return players.get(turn);
177 /** The play who wins on current board.
179 * @return the winning player or <code>null</code>
181 public Player getWinner() {
182 if (winner != null) {
185 for (Player p : players) {
186 if (p.endDirection.reached(p)) {
193 /** Applies given move to current board.
195 * @param move move creates by one of the factory methods or fields of the {@link Move} class
196 * @return new board derived from this one
198 * @throws cz.xelfi.quoridor.IllegalPositionException throws exception if the move is illegal
200 public Board apply(Move move) throws IllegalPositionException {
201 if (getWinner() != null) {
202 throw new IllegalPositionException("Game finished!"); // NOI18N
204 return apply(move, getCurrentPlayer());
207 private Board apply(Move move, Player p) throws IllegalPositionException {
208 if (move.direction != null) {
209 return move(p, move.direction);
211 if (move.fence != null) {
212 return fence(p, move.fence);
214 return new Board(this, turn + 1);
219 /** Is there a move that would take the player onto given position while
220 * respecting situation on board?
222 * @param p the player to try to move
223 * @param column desired x-coordinate. Between 0-8. See {@link Player#getColumn()}.
224 * @param row desired y-coordinate. Between 0-8. See {@link Player#getRow()}.
225 * @return the move that can be {@link #apply applied} to the position and
226 * that would move the player p into desired position or null, if such
227 * move does not exist
230 public Move findMove(Player p, int column, int row) {
231 int idx = getPlayers().indexOf(p);
235 for (Move m : Move.allMovements()) {
239 } catch (IllegalPositionException ex) {
243 b.getPlayers().get(idx).getColumn() == column &&
244 b.getPlayers().get(idx).getRow() == row
252 /** Can the move be applied to current board position?
254 * @param move the move to apply
255 * @return true if one can call {@link #apply} method without getting
258 public boolean isApplicable(Move move) {
260 // trivial implementation is enough for now
263 } catch (IllegalPositionException ex) {
268 /** Moves the player in given direction. The direction usually
269 * is one of Player.Direction constants, but in case the move
270 * is a jump over another players pawn it can be followed by
271 * another (usually, if there is no fence the same) direction.
273 * @param player the player to move
274 * @param where one or two directions saying where
275 * @return the new board
276 * @exception IllegalPositionException if the move is not possible
278 final Board move (Player player, Player.Direction... where) throws IllegalPositionException {
279 if (where.length != 1 && where.length != 2) {
280 throw new IllegalPositionException ("Move over one or two Directions"); // NOI18N
283 int index = players.indexOf (player);
284 Player[] arr = players.toArray (new Player[0]);
286 Player oneStep = newPosition (player, where[0]);
288 if (where.length == 1) {
289 arr[index] = oneStep;
290 return new Board(turn + 1, Arrays.asList (arr), fences);
293 // straight jump over
294 for (Player p : players) {
295 if (p.getXInternal () == oneStep.getXInternal () && p.getYInternal() == oneStep.getYInternal ()) {
296 // ok, we are jumping over this one
297 GO_ON: if (where[0] != where[1]) {
298 // first of all ensure that we cannot go straight
300 newPosition (oneStep, where[0]);
301 } catch (IllegalPositionException ex) {
305 throw new IllegalPositionException ("You have to jump straight if there is no wall"); // NOI18N
307 arr[index] = newPosition (oneStep, where[1]);
308 if (arr[index].equals(player)) {
309 throw new IllegalPositionException("You cannot jump forth and back"); // NOI18N
311 return new Board (turn + 1, Arrays.asList (arr), fences);
314 throw new IllegalPositionException ("Cannot use multi direction when there is not oponent pawn"); // NOI18N
317 final Board fence (Player player, char x, int y, Fence.Orientation orientation) throws IllegalPositionException {
318 return fence(player, new Fence ((x - 'A') * 2 + 1, y * 2 - 1, orientation));
321 private void columnLine(int width, int spaceX, Writer w) throws IOException {
323 for (int x = 0; x < width - 1; x++) {
324 if (x % (spaceX + 1) == 0 && x > 0) {
326 ch = (char) (ch + 1);
333 private Board fence(Player player, Fence fence) throws IllegalPositionException {
334 if (player.getFences () == 0) {
335 throw new IllegalPositionException ("Not enough fences: " + player); // NOI18N
338 int index = players.indexOf (player);
339 Player[] arr = players.toArray (new Player[0]);
340 arr[index] = new Player (arr[index].getXInternal(), arr[index].getYInternal(), arr[index].getFences() - 1, arr[index].endDirection);
342 HashSet<Fence> fen = new HashSet<Fence> (this.fences);
343 if (!fen.add (fence)) {
344 throw new IllegalPositionException ("Fence already prsent: " + fence); // NOI18N
347 return new Board (turn + 1, Arrays.asList (arr), fen);
354 private static final Pattern northSouthPattern = Pattern.compile("(\\+(\\|*)(\\*)?-+\\+)");
356 /** Reads the board from a reader. Opposite operation to {@link #write(java.io.Writer)}.
358 * @param r the reader
359 * @return the read board
360 * @throws IOException if I/O error occurs
361 * @throws IllegalPositionException if the reader does not contain description
364 public static Board read(Reader r) throws IOException, IllegalPositionException {
365 BufferedReader b = new BufferedReader(r);
367 String s = b.readLine();
369 throw new IOException("No board found!");
371 Matcher m = northSouthPattern.matcher(s);
373 return readFromBetween(b, m);
378 /** Translates the string into board, if possible. String created by
379 * use of {@link #toString()} is accepted, more information about the
380 * format is avaliable in the description of {@link #write(java.io.Writer)}
383 * @param board string to analyze
384 * @return board object, if the string can be read
385 * @throws IllegalPositionException if the string does not represent the board
387 public static Board valueOf(String board) {
388 return new Board(board);
391 private static int assertChar(String s, int pos, char... ch) throws IOException {
392 if (s.length() >= pos) {
393 for (int i = 0; i < ch.length; i++) {
394 if (ch[i] == s.charAt(pos)) {
399 throw new IOException("Not found " + ch[0] + " at " + pos + " in" + s);
402 private static Player findPlayer(
403 Player previous, String line, int y, int spaceX, Player.Direction dir, int fences
405 int index = line.indexOf(dir.player);
409 int x = (index - 1) / (spaceX + 1) * 2;
410 return new Player(x, y - 1, fences, dir);
413 private static Board readFromBetween(BufferedReader b, Matcher firstMatcher)
414 throws IOException, IllegalPositionException {
415 final int from = firstMatcher.start(1);
416 final int to = firstMatcher.end(1);
417 final int northFences = firstMatcher.end(2) - firstMatcher.start(2);
418 final int spaceX = (to - from - 1) / 9 - 1;
419 final int spaceY = 1;
423 Set<Fence> fences = new HashSet<Fence>();
425 StringBuffer sb = new StringBuffer();
427 for (int y = (spaceY + 1) * 9 - 1; y > 0; y--) {
428 String s = b.readLine();
430 throw new EOFException();
434 if (s.length() < to) {
435 throw new IOException("Too short line: " + s); // NOI18N
437 assertChar(s, from, '|');
438 assertChar(s, to - 1, '|');
440 if (y % (spaceY + 1) == 0) {
441 for (int x = 1; x < 9; x++) {
442 switch (assertChar(s, from + (spaceX + 1) * x, '+', '-', '|')) {
444 fences.add(new Fence(x * 2 - 1, row * 2 + 1, Fence.Orientation.HORIZONTAL));
447 fences.add(new Fence(x * 2 - 1, row * 2 + 1, Fence.Orientation.VERTICAL));
457 String line = s.substring(from, to);
458 p = findPlayer(p, line, y, spaceX, Player.Direction.NORTH, -1);
459 q = findPlayer(q, line, y, spaceX, Player.Direction.SOUTH, northFences);
463 String last = b.readLine();
465 throw new EOFException();
467 Matcher lastMatcher = northSouthPattern.matcher(last);
468 if (!lastMatcher.find()) {
469 throw new IOException("Unrecognized last line: " + last);
472 List<Player> arr = new ArrayList<Player>(2);
474 int southFences = lastMatcher.end(2) - lastMatcher.start(2);
475 arr.add(new Player(p.getXInternal(), p.getYInternal(), southFences, p.endDirection));
477 int turn = "*".equals(lastMatcher.group(3)) ? 0 : 1; // NOI18N
478 return new Board(turn, arr, fences);
483 /** Writes the board to the provided writer. <b>P</b> denotes position
484 * of the first player and <b>Q</b> of the second. Number of remaining
485 * fences of each player are shown in left bottom and left top corner
486 * as appropriate number of <b>|||</b> - one <b>|</b> per fence. The
487 * player that is supposed to move in this turn has <b>*</b> right after
488 * the set of its fences.
495 +|||||------------------------------+
497 8--| + + + + + + + + |--8
499 7--| + | + +-------+-------+ |--7
501 6--|-------+-------|-------+-------+ |--6
503 5--| + + + + + + + + |--5
505 4--| + + + | + + +-------|--4
507 3--| + + + +-------+ + + |--3
509 2--| + + + + + + + + |--2
511 1--| + + + + + | + + |--1
513 +|||*-------------------------------+
519 * @param w writer to write the board to
520 * @exception IOException if communiction with writer fails
522 public void write (Writer w) throws IOException {
526 private void northSouthSign(int width, char sign, Writer w) throws IOException {
527 int middle = width / 2;
528 for (int x = 0; x < width; x++) {
530 if (x == middle - 1) {
536 if (x == middle + 1) {
541 w.write(System.getProperty("line.separator")); // NOI18N
544 private void subColumnLine(int width, int spaceX, Writer w) throws IOException {
545 for (int x = 0; x < width - 1; x++) {
546 if (x % (spaceX + 1) == 0 && x > 0) {
554 /** This will print the board with provided spacing.
555 * This is example of 3:1 spacing:
561 * and this 4:2 spacing:
569 private void write (Writer w, int spaceX, int spaceY) throws IOException {
570 int width = spaceX * 9 + 10;
571 int height = spaceY * 9 + 10;
572 char[][] desk = new char[height][];
573 for (int i = 0; i < height; i++) {
574 desk[i] = new char[width];
575 for (int j = 0; j < width; j++) {
576 if (i % (spaceY + 1) == 0 && j % (spaceX + 1) == 0) {
583 desk[i][width - 1] = '|';
585 for (int i = 1; i < width - 1; i++) {
587 desk[height -1][i] = '-';
590 desk[0][width - 1] = '+';
591 desk[height - 1][0] = '+';
592 desk[height - 1][width - 1] = '+';
595 for (Player p : players) {
596 int px = p.getXInternal() / 2;
597 int py = p.getYInternal() / 2;
599 [1 + py * (spaceY + 1) + spaceY / 2]
600 [1 + px * (spaceX + 1) + spaceX / 2] = p.endDirection.player;
601 paintLeftFences(desk, p.endDirection, p.getFences(), p.equals(getCurrentPlayer()));
605 for (Fence f : fences) {
606 int fx = (f.getX() / 2 + 1) * (spaceX + 1);
607 int fy = (f.getY() / 2 + 1) * (spaceY + 1);
608 switch (f.getOrientation()) {
610 for (int i = -spaceX; i <= spaceX; i++) {
611 desk[fy][fx + i] = '-';
615 for (int i = -spaceY; i <= spaceY; i++) {
616 desk[fy + i][fx] = '|';
620 throw new IllegalStateException ("Unknown orientation: " + f.getOrientation ()); // NOI18N
624 northSouthSign(width, 'N', w);
625 w.write(System.getProperty("line.separator")); // NOI18N
627 columnLine(width, spaceX, w);
628 w.write(System.getProperty("line.separator")); // NOI18N
630 subColumnLine(width, spaceX, w);
631 w.write(System.getProperty("line.separator")); // NOI18N
633 for (int y = height - 1; y >= 0; y--) {
634 if (y == height / 2) {
639 boolean number = y % (spaceY + 1) == 0 && y > 0 && y < height - 1;
642 w.write(Integer.toString(cnt));
647 for (int x = 0; x < width; x++) {
652 w.write(Integer.toString(cnt));
656 if (y == height / 2) {
659 w.write(System.getProperty("line.separator")); // NOI18N
662 subColumnLine(width, spaceX, w);
663 w.write(System.getProperty("line.separator")); // NOI18N
665 columnLine(width, spaceX, w);
666 w.write(System.getProperty("line.separator")); // NOI18N
667 w.write(System.getProperty("line.separator")); // NOI18N
669 northSouthSign(width, 'S', w);
673 private void paintLeftFences(char[][] desk, Direction endDirection, int fences, boolean currentTurn) {
674 assert fences >= 0 && fences <= 10 : "Players: " + players;
675 switch (endDirection) {
677 for (int i = 0; i < fences; i++) {
678 desk[desk.length - 1][i + 1] = '|';
681 desk[desk.length - 1][fences + 1] = '*';
686 for (int i = 0; i < fences; i++) {
687 desk[0][i + 1] = '|';
690 desk[0][fences + 1] = '*';
706 public int hashCode () {
707 return occupied.hashCode ();
711 public boolean equals (Object o) {
712 if (o instanceof Board) {
714 return occupied.equals (b.occupied) && players.equals (b.players);
719 /** Converts the board into string representation. For more information
720 * about the format see {@link #write(java.io.Writer)}. To read the
721 * string back use {@link #valueOf(java.lang.String)}.
723 * @return string representing the board
726 public String toString() {
731 // Validation methods
734 /** Computes new position of a player and checks whether there is no
735 * fence between the old and new.
737 private Player newPosition (Player old, Player.Direction direction) throws IllegalPositionException {
738 return newPosition (old, direction, occupied);
742 private static Player newPosition (Player old, Player.Direction direction, BitSet occupied) throws IllegalPositionException {
765 default: throw new IllegalStateException ("Unknown direction: " + direction); // NOI18N
768 if (nx < 0 || nx > 16) throw new IllegalPositionException ("Wrong player position: " + nx + ":" + ny); // NOI18N
769 if (ny < 0 || ny > 16) throw new IllegalPositionException ("Wrong player position: " + nx + ":" + ny); // NOI18N
771 int fenceIndex = toIndex (fx, fy);
772 if (occupied.get (fenceIndex)) {
773 throw new IllegalPositionException ("You cannot go over fences"); // NOI18N
776 return new Player (nx, ny, old.getFences (), old.endDirection);
779 /** @param position the current position of the player
780 * @param endDir the side the player wants to reach
781 * @param fences bits set to 1 when fences are placed
782 * @param reached bits on squares that were already reached (modified during run)
783 * @return true if the end line can be reached
785 private static boolean accessibleFinalLine (Player position, Player.Direction endDir, BitSet fences, BitSet reached) {
786 int index = toIndex (position);
787 if (reached.get (index)) {
788 // already visited without success
792 if (endDir.reached(position)) {
798 for (Player.Direction oneDirection : Player.Direction.values ()) {
800 if (accessibleFinalLine (newPosition (position, oneDirection, fences), endDir, fences, reached)) {
803 } catch (IllegalPositionException ex) {
811 /** Computes mask of the occupried bits.
813 private static BitSet computeOccupied (
814 Collection<Player> players, Collection<Fence> fences
815 ) throws IllegalPositionException {
816 BitSet occupied = new BitSet (17 * 17);
818 for (Player p : players) {
819 if (p.getXInternal() % 2 == 1) throw new IllegalPositionException ("Wrong player position: " + p); // NOI18N
820 if (p.getYInternal() % 2 == 1) throw new IllegalPositionException ("Wrong player position: " + p); // NOI18N
822 int index = toIndex (p);
823 if (occupied.get (index)) {
824 throw new IllegalPositionException ("There cannot be two players at " + p); // NOI18N
826 occupied.set (index);
829 for (Fence f : fences) {
831 for (int i = -1; i <= 1; i++) {
832 int index = toIndex (f, i);
833 if (index < 0 || index > occupied.size ()) {
834 throw new IllegalPositionException ("Wrong fence position: " + f); // NOI18N
836 if (occupied.get (index)) {
837 throw new IllegalPositionException ("Fence collition: " + f); // NOI18N
840 occupied.set (index);
848 /** Converts twodimensional coordinates of player to one dimensional index.
850 private static int toIndex (Player p) {
851 return toIndex (p.getXInternal(), p.getYInternal());
854 /** Converts twodimensional coordinates of fence to one dimensional index.
856 * @param whichPart (-1, 0, 1)
858 private static int toIndex (Fence f, int whichPart) {
862 switch (f.getOrientation ()) {
863 case HORIZONTAL: x += whichPart; break;
864 case VERTICAL: y += whichPart; break;
865 default: throw new IllegalStateException ("Wrong orientation: " + f.getOrientation ()); // NOI18N
868 return toIndex (x, y);
871 /** Diagonal conversion of two positive integers to one integer.
880 private static int toIndex (int x, int y) {
881 assert x >= 0 && x < 17;
882 assert y >= 0 && y < 17;
886 Board(String hashCode) throws IllegalStateException{
887 this.fences = new HashSet<Fence>();
888 if((hashCode != null) && (hashCode.length() > 6)){
889 char[]c = hashCode.toCharArray();
890 this.players = Collections.unmodifiableList (Arrays.asList (new Player[] {
891 new Player ((c[0]-'A')*2, (c[1]-'0')*2, c[2]-'a', Player.Direction.NORTH),
892 new Player ((c[3]-'A')*2, (c[4]-'0')*2, c[5]-'a', Player.Direction.SOUTH),
902 this.winner = this.players.get(0);
905 this.winner = this.players.get(1);
910 for(int i=7; i<c.length;i+=2){
911 int f = Integer.parseInt(hashCode.substring(i, i+2),16);
912 Fence.Orientation o = Fence.Orientation.HORIZONTAL;
914 o = Fence.Orientation.VERTICAL;
917 fences.add(new Fence((f/8)*2+1, (f%8)*2+1,o));
920 this.players = Collections.unmodifiableList (Arrays.asList (new Player[] {
921 new Player (8,0,10,Player.Direction.NORTH),
922 new Player (8,16,10,Player.Direction.SOUTH),
928 this.occupied = computeOccupied (players, fences);
929 } catch (IllegalPositionException ex) {
930 throw new IllegalStateException (ex.getMessage ());
934 public final String getCode() {
936 StringBuilder sb = new StringBuilder();
937 for(Player p: b.getPlayers()){
938 sb.append((char)(p.getColumn() + 'A'));
939 sb.append((char)(p.getRow() + '0'));
940 sb.append((char)(p.getFences() + 'a'));
942 Player winner = b.getWinner();
944 if(b.players.indexOf(b.getCurrentPlayer())==0)
946 else if(b.players.indexOf(b.getCurrentPlayer())==1)
951 if(b.players.indexOf(winner)==0)
953 else if(b.players.indexOf(winner)==1)
959 TreeSet<Integer> fences = new TreeSet<Integer>();
960 for(Fence f: b.getFences()){
961 int a = (f.getColumn() - 'A')*8 + (f.getRow()-1);
962 if(f.getOrientation().equals(Fence.Orientation.VERTICAL))
969 sb.append(Integer.toHexString(f));
971 return sb.toString();