Problems designing Bejeweled game

Question

I am trying to do the design of a Bejeweled game. I have basically 3 classes. The Game class, which is what is going to be used by the player, a Board class, that represents the board, and a SwitchController class that is responsible for checking if the wanted switch on the board is valid, making the switch, counting the number of possible switches available (so I can know when the game is over, etc).

My current design is something like the following:

Game:
isGameOver()
isSwitchValid(coord1, coord2)
makeSwitch(coord1, coord2)
getPieceAt(coord)
getBoardLength()

IBoard:
getPieceAt(coord)
setPieceAt(coord, piece)
getLength()

My idea would then to have a ISwitchController:

ISwitchController:
isSwitchValid(coord1, coord2)
makeSwitch(coord1, coord2)
getAllValidSwitches()

Here is a little diagram of how the classes are to be organized:

I would have 2 different concrete classes of IBoard available for use (and for each one of them, I'd have to have an ISwitchController implementation).

The problem:

My program is to have 2 IBoard implementations:

The first, ArrayBoard, will have all the pieces of the board stored in a 2D Array. There is nothing special about it. I will define an ArrayBoardSwitchController for managing this class.

The second, ListBoard, will have for each color of pieces, a List/Set with all the coordinates of the pieces of that color. I will define a ListBoardSwitchController for managing this class.

The main issue here is that the implementation of SwitchController will be totally different on ArrayBoard and on ListBoard. For example, while for implementing getAllValidSwitches() ArrayBoardSwitchController only needs the getPieceAt() method, that would not be a good idea to do with ListBoardSwitchController(in that class I use internally lists because it's easier to check if the move is valid that way).

From what I can see, there are 2 different possible solutions:

1. I could either merge together the ISwitchController and IBoard interfaces. That way I'd only have two classes, Game and Board (while basically Game would just be a controller for the Board, as it would be the Board that had all the game logic). It wouldn't be that nice because the classes wouldn't be as cohese as they could be if I had 3 distinct classes.

2. Let the interfaces as they are and put all the methods I need to work with public in the concrete classes. For example, if I need a getYellowPiecesList() method, I'd put it public on ListBoard so ListBoardSwitchController could use it. ListBoardSwitchController would only know about it because it knows it only works against ListBoards.

What's your opinion on the matter? The focus here is not so much on how to design the Bejeweled game, but how to solve this problem, that is recurrent when you try to implement algorithms: on one hand you want to have a clear and good OOP design, and in the other sometimes that gets in the way of having a sound and effective algorithm implementation.

Answer 1

The main issue here is that the implementation of SwitchController will be totally different on ArrayBoard and on ListBoard.

If this is the case, then it sounds like you haven't designed the IBoard interface well enough so that classes can use an implementation of IBoard without knowing the implementation details. If the user of an IBoard needs to know what implementation is being used, then it almost defeats the purpose of having an interface!

I would strongly suggest re-visiting the methods you are exposing on IBoard to see if there is a way you can expose something like "get the piece at this coordinate" in a more generic way. Make sure that any methods a controller needs to invoke on a IBoard instance are only the methods in the IBoard interface.

For example, while for implementing getAllValidSwitches() ArrayBoardSwitchController only needs the getPieceAt() method, that would not be a good idea to do with ListBoardSwitchController(in that class I use internally lists because it's easier to check if the move is valid that way).

If an operation such as "get piece at this coordinate" is instrumental to the IBoard interface, then the implementations must be faithful to their contract and implement it correctly. It sounds as if your ListBoard is not faithfully meeting the contract set out in IBoard.

Answer 2

3: Let ArrayBoardSwitchController and ListBoardSwitchController be inner classes of ArrayBoard and ListBoard. The implementation of the controller is tied to the implementation of your board, thus it makes sense to keep them together. Because the controller will be an inner class you can use the implementation details from the board. Then to make it work extend the IBoard interface to return a ISwitchController.

Note that this is only slightly different from option 1. (The ISwitchController can now be used indirectly from a IBoard, merging them gives direct access to ISwitchController)

Answer 3

What is the purpose of ListBoard as an object decoupled from ArrayBoard? If I were going to bother with the list of gems at all, I would keep it in an object which also held an array of what was in each position, so that swapping the position of two gems could be done quickly and efficiently. Not that I'm clear on why you need the position list anyhow?

If a 6507 running at 1.19Mhz with 128 bytes of RAM and 20% CPU availability can handle Columns, finding all 3-in-a-row combinations on a 6x20 in less than 100ms, I would think more modern machines could scan for moves acceptably fast without using a list of what gems are where. I'd suggest padding your board array so you don't have to worry about edge cases, and for each gem check 16 combinations of various cells within 3 squares of it(*) to see if they both match it. Some moves may be double-reported (e.g. this algorithm may detect that moving a gem left will create a 3-in-a-row, and also detect that moving the gem to the left of the first one right will create a 3-in-a-row) but that shouldn't be a problem.

(*) If a gem can move left, then it must match either the two gems to the left of the destination, or the two gems above the destination, or the two gems below, or one above and one below. Likewise for the other directions.