# Help with JAVA board game

• 02-08-2011, 11:22 PM
corky1501
Help with JAVA board game
I'm relatively new to JAVA programming, but have been set a task to create a basic board game and need some help to solve a problem which I've been racking my brain just to make a start on!

The premise of the game is that a 8x8 grid will be created by drawing horizontal and vertical lines within a window. Two players, Black and White, take turns to put a piece on the board; White moves first. No more than one piece may occupy any square, and pieces are never removed. The aim of Black is to build a path of black pieces between the left edge and the right edge of the board; and the aim of White is to build a path of white pieces between the top and bottom. Each path must consist of horizontally or vertically adjacent pieces (not diagonal!). The first player to construct their path wins.

In order to store the placement of the pieces, I have created a 2 dimensional array, with the squares of the grid referencing a slot in the array (i.e. the top left square will be 0,0 and reference the first slot in the array [0][0], and so on).

I have managed to get the game working, in that the board is created and the coloured counters are placed into the grid in the square clicked by the player. However, I have now hit a brick wall in the checking algorithm to find if a player has won.

I can't even think of a starting point! I don't want the exact code which I will have to implement, but a basic outline of the process of checking to see if a path has been created by either player which traverses the board as discribed.

Any help would be greatly appreciated!
• 02-08-2011, 11:53 PM
NeuroFuzzy
OOch, my first thought was a simple recursive function but my idea would get stuck in a loop (=stack overflow) really easily.

here's an idea to check if black has won:

Make a function that accepts an arraylist, an x, and a y position. If its x and y position doesn't exist in the arraylist, it adds itself. If its x and y position does exist, it returns. Then it calls itself on all adjacent black tiles and ends.

If you call this function on all the rightmost black tiles, you'll get an arraylist of all black tiles that connect to the right side. If one entry in this arraylist has an x value of 0, then black has won!.

Errm, you'll need a dummy, integer, 2d vector class, and then you'll need to create an arraylist of this 2d vector. For checking if the value has already been added... just loop through the array list checking x and y values. It might get expensive if you have a giant board size, but this is a simple solution, and faster solutions would probably be more complicated xD
• 02-09-2011, 12:52 AM
Ok, so you could use a brute force technique or you could use something math'ier and more clever. Lets look at brute force for simplicity sake.

If you think about this problem as if you were looking at graph paper, how do you as a human know if someone has won or not? Well, if you break it down, you'll see that your eye looks for a starting square, and then a series of subsequent adjacent squares.

So, clue number 1!!! We need to start with the first row (or col depending on your orientation). Whatever it is we are doing, we need to do it on each row until we reach the last row correct?
(loops)

Clue #2. We need the ability to determine of a given square has an adjacent square. What is the criteria? Lets try an example with black:
- An adjacent square must not be the current square
- An adjacent square must be no more than 1 square away, either above, below, left, or right, but not both.
- An adjacent square must be black
- We are creating paths, so we don't care about the adjacent square we just came from

Clue #3 We have found a path if we made it all the way to the other side always going from one valid adjacent square to the next.

There are other considerations and special cases, but this should get you started.
• 02-09-2011, 01:17 AM
sunde887
Are you using a class to represent the pieces? Also, how are you storing current pieces placed? It may not be a very efficient way, but you could go to each pieces and loop through the correct part of the array, only continuing if the piece has an adjacent pieces.

Try representing the grid on paper, put some random pieces out and check by hand by going through each item in the array by hand. It's a bit hard to explain exactly but, it would work when implemented correctly.

if a piece is on a 4 x 4 grid was at 3, 3, if piece is white, you would check
(2, 3), (1, 3), (0, 3), (4, 3)

if black you would check
(3. 2),(3, 1),(3, 0), (3, 4)

If you hold the pieces currently placed in an array list you can find the coords of the pieces and apply this idea to each piece.
• 02-09-2011, 01:17 AM
corky1501
Neurofuzzy & quad64bit thanks very much for the quick replies.

The answers you've given me have both given me ideas as to how to implement a way of getting from one side to the other (left-right, top-bottom).

I think the idea of creating an array for the path (pathArray[length of grid]), and populating (filling) it as the search method progresses to the next row or column, until the array is full and so has traversed the grid is the idea which is clearest in my head.

So basically, in a left-right search, it looks at the first column [0] to see if it can find the appropriate colour. If this can't be found, no successful path has been created. If it finds one, it enters a marker into pathArray[0] and looks at the adjacent square in the next column to look for the same colour. If it doesn't find one, it looks above and below. Still no match, means no path. If it finds one in the next column, a marker is placed in pathArray[1] and the process loops until the pathArray[length of grid] is filled. This would mean a successful path (linked!) across the grid.

If it searches a path to find it is not successful, it will need to return to the first column and check the remaining squares to ensure another path wasn't started further down!

I think this basic idea would do the job. Its getting a bit late so sorry for any glaring errors or mistakes in the walk through! Hopefully this looks right, but anyone who can spot any flaws or even a simpler method, please feel free to mention them as this is probably the most advanced thing I've done to date (I'm a real amateur with Java!) and so any help would be great.

Thanks again for the replies so far!:)
• 02-09-2011, 04:18 AM