Ok I feel like I'm a pretty good programmer but all my learning is self taught, so I'm trying to brush up on the "proper" ways to implement specific design patterns and other programming techniques. This situation kinda has me at a stand still scratching my head. I know how I would normally do it and for something this small it'd probably be the easiest without causing headache down the road. But I'm trying to learn so...
First to paint a picture, for the sake of this question the game is similar to 'Checkers'. Theres a game board that only two players play on. All the game pieces are the same except that they belong to different people.
What I'm wandering about is who should own the game pieces and how would interaction with the pieces be handled in all respects to OOP?
The way I would do it is the player would own the pieces and handle the interaction with the pieces. The first thing that pops out to me though is interaction between different players pieces would require each player to have some knowledge of the other players pieces. This makes me think I should have another class/function outside the player that handles player input and interaction with game pieces and just pass the whole lot of info to this controller. Am I on the right track with that?
3
18 replies to this topic
#1 Members - Reputation: 302
Posted 15 November 2012 - 03:03 PM
[ dev journal ]
[ current projects' videos ]
[ Zolo Project ]
I'm not mean, I just like to get to the point.
[ current projects' videos ]
[ Zolo Project ]
I'm not mean, I just like to get to the point.
Sponsor:
#2 Members - Reputation: 1810
Posted 15 November 2012 - 03:44 PM
Yes, I would say so.This makes me think I should have another class/function outside the player that handles player input and interaction with game pieces and just pass the whole lot of info to this controller. Am I on the right track with that?
What occurs to me is to have a Board class which models the state of the board (i.e. the position and type of all the checkers) and has public member functions for updating that state according to the rules of the game - such as moving a piece diagonally, hopping over another player's piece, kinging a piece - Not to mention some functions to query the board state in order to find out who's winning and whether the game has finished. Also, if there's an AI involved then it will probably need index into and/or iterate over the board to see precisely where pieces are located.
. David Gill :: Facebook :: twitter :: LinkedIn .
#3 Members - Reputation: 1575
Posted 15 November 2012 - 03:55 PM
Agreed. Just a 2D array of enum values something like {EMPTY, PLAYER_A_PIECE, PLAYER_B_PIECE} could represent the board state internally and then member functions using the MVC architecture would probably work great.
This would most likely use the least resources and be the most convenient way to trigger interactions between the pieces, since all the information belongs to a single class.
This would most likely use the least resources and be the most convenient way to trigger interactions between the pieces, since all the information belongs to a single class.
Edited by Khatharr, 15 November 2012 - 03:56 PM.
void hurrrrrrrr() {__asm sub [ebp+4],5;}
There are ten kinds of people in this world: those who understand binary and those who don't.
There are ten kinds of people in this world: those who understand binary and those who don't.
#6 Members - Reputation: 151
Posted 15 November 2012 - 09:13 PM
I'll agree. OOP doesn't make a whole lot of sense here.
You may find this valuable: Board Representation [Chess Programming Wiki]
Skip to the bottom and you'll find tons of great articles on the subject.
You may find this valuable: Board Representation [Chess Programming Wiki]
Skip to the bottom and you'll find tons of great articles on the subject.
#7 Members - Reputation: 1575
Posted 15 November 2012 - 11:03 PM
I'll agree. OOP doesn't make a whole lot of sense here.
Representing each piece as an object doesn't make sense, but OOP is fine in terms of implementing the board itself. A class would be a good way to isolate the data and provide a standard means of observation and safe manipulation. The benefit, like frob pointed out, is that implementing in this way allows a 'player' to be more or less anything (local player, network player, AI, chicken with a USB port wired to its brain, etc).
Edited by Khatharr, 15 November 2012 - 11:07 PM.
void hurrrrrrrr() {__asm sub [ebp+4],5;}
There are ten kinds of people in this world: those who understand binary and those who don't.
There are ten kinds of people in this world: those who understand binary and those who don't.
#8 Members - Reputation: 151
Posted 16 November 2012 - 01:05 AM
The benefit, like frob pointed out, is that implementing in this way allows a 'player' to be more or less anything (local player, network player, AI, chicken with a USB port wired to its brain, etc).
Not to start a holy war, but that's not really a benefit of OOP in this case. Wrapping the whole thing in a class is just one of many solutions that afford those same benefits, and may not ultimately be the best solution.
Yeah, that'll start a holy war. I should probably bow out at this point...
#9 Moderators - Reputation: 13594
Posted 16 November 2012 - 01:43 AM
Who are you agreeing with?I'll agree. OOP doesn't make a whole lot of sense here.
"Not everything has to be it's own class in OO" != "OO is nonsensical here".
If everything in OOP had to be a class, we'd be writing code like below, which we don't --
Assertion( Comparison( Adder( Integer(1), Integer(1) ).Result(), Integer(2) ).Result() ).Check();
Yes, in a thread asking how to use OO design in a specific situation, you're just trying to OO-bash, poorly.Yeah, that'll start a holy war. I should probably bow out at this point...
Please no one take the bait.
#11 Members - Reputation: 5886
Posted 16 November 2012 - 06:29 AM
I am not trying to feed the war on OOP, but I've been writing board games for 20 years as a hobby and I can tell you what's useful and what's not. Most of this post is advice about writing an engine for a board game. If you are writing a GUI, performance is probably much less of an issue and you can afford to use whatever design you want.
You basically need two classes when programming a board game: Board and Move. Instead of "Board" you can call the class "Game" or "GameState", since you may want it to remember the history of moves (so they can be undone, or so you can figure out if the current position is a repetition of a previous position). In my own programs I tend to call it "Board", perhaps because I am used to the name.
Using C++ for syntax, Board's interface has methods like:
* int generate_moves(Move *moves) const;
* void make_move(Move const &move);
* bool is_game_over(int &result);
Depending on what algorithm you will use for your AI and how expensive it is to copy a Board, you may want to provide a function to undo the last move (minimax can make use of this to run without ever making a copy of a Board). A method that returns a hash key of the position is also useful, for implementing transposition tables.
The details of the game are important for picking a board representation, but if it is a game like checkers or chess, with a board that is no larger than 64 useful squares (8x8 checkers uses 32 squares, 10x10 checkers uses 50 squares), you can use bitboards to represent the position. A more straight-forward representation is an array of enums, as already suggested in this thread. Bitboards are better at figuring out things like "what are all the white pawns that can move Northwest" (which takes something like 5 fast assembly instructions). But if you need to check the content of individual squares often, an array is the way to go. Sometimes you want to have both representations available simultaneously: You pay a price in the size of the Board objects (which doesn't matter if you don't copy them around) and in the cost of making moves, but then you can answer both types of questions fast.
If you use a minimax algorithm to search the game tree, you'll need an evaluation function (a heuristic function which given a position returns a number that indicates what the winning chances of each player seem to be). That function will probably need access to the details of how Board is implemented, so you can make it a friend of the class. Sometimes the search function also needs access to details of the Board. When I start writing these programs I am usually not certain about what kind of access is going to be needed, so I make everything in the Board public, which is probably just a bad habit. I am very good at keeping const-correctness in my code, so the usual risks of having everything public are not too bad. Also, if the board representation were to change at some point in the future, I would have to rewrite most of the engine code anyway.
Beyond Board and Move, you can have object classes like Player (an abstract interface which primarily has a method to pick a move on a given position), Engine (derived from Player), GameDataBase, etc. But using classes to model anything below the abstraction level of Board and Move isn't likely to be useful.
An engine typically doesn't need to perform any dynamic memory allocation at all. If you find yourself using `new' all over the place, you are probably doing it wrong. You don't need to keep a game tree structure in memory at all when implementing minimax (if this is not clear to you, I can give you some sample code so you see what I mean).
One more thing: The computer chess community learned over the years that it is extremely useful to define a text-based interface to communicate with an engine. Modern chess programs have separate processes for the GUI and for the engine (or engines), and the standardization allows you to unload an engine, load a new one written by someone else and keep going. The text interface can also be used by a program that arranges matches between engines to gather statistics, which doesn't need graphics at all and can be run in a cluster overnight. This is great for testing changes to an engine, to measure if the change is actually an improvement. Unfortunately there are two competing interfaces: XBoard and UCI (Universal Chess Interface). Neither of them is perfect, but UCI is very reasonable in many respects. For the game of go, there is a dominant interface called GTP (Go Text Protocol).
You basically need two classes when programming a board game: Board and Move. Instead of "Board" you can call the class "Game" or "GameState", since you may want it to remember the history of moves (so they can be undone, or so you can figure out if the current position is a repetition of a previous position). In my own programs I tend to call it "Board", perhaps because I am used to the name.
Using C++ for syntax, Board's interface has methods like:
* int generate_moves(Move *moves) const;
* void make_move(Move const &move);
* bool is_game_over(int &result);
Depending on what algorithm you will use for your AI and how expensive it is to copy a Board, you may want to provide a function to undo the last move (minimax can make use of this to run without ever making a copy of a Board). A method that returns a hash key of the position is also useful, for implementing transposition tables.
The details of the game are important for picking a board representation, but if it is a game like checkers or chess, with a board that is no larger than 64 useful squares (8x8 checkers uses 32 squares, 10x10 checkers uses 50 squares), you can use bitboards to represent the position. A more straight-forward representation is an array of enums, as already suggested in this thread. Bitboards are better at figuring out things like "what are all the white pawns that can move Northwest" (which takes something like 5 fast assembly instructions). But if you need to check the content of individual squares often, an array is the way to go. Sometimes you want to have both representations available simultaneously: You pay a price in the size of the Board objects (which doesn't matter if you don't copy them around) and in the cost of making moves, but then you can answer both types of questions fast.
If you use a minimax algorithm to search the game tree, you'll need an evaluation function (a heuristic function which given a position returns a number that indicates what the winning chances of each player seem to be). That function will probably need access to the details of how Board is implemented, so you can make it a friend of the class. Sometimes the search function also needs access to details of the Board. When I start writing these programs I am usually not certain about what kind of access is going to be needed, so I make everything in the Board public, which is probably just a bad habit. I am very good at keeping const-correctness in my code, so the usual risks of having everything public are not too bad. Also, if the board representation were to change at some point in the future, I would have to rewrite most of the engine code anyway.
Beyond Board and Move, you can have object classes like Player (an abstract interface which primarily has a method to pick a move on a given position), Engine (derived from Player), GameDataBase, etc. But using classes to model anything below the abstraction level of Board and Move isn't likely to be useful.
An engine typically doesn't need to perform any dynamic memory allocation at all. If you find yourself using `new' all over the place, you are probably doing it wrong. You don't need to keep a game tree structure in memory at all when implementing minimax (if this is not clear to you, I can give you some sample code so you see what I mean).
One more thing: The computer chess community learned over the years that it is extremely useful to define a text-based interface to communicate with an engine. Modern chess programs have separate processes for the GUI and for the engine (or engines), and the standardization allows you to unload an engine, load a new one written by someone else and keep going. The text interface can also be used by a program that arranges matches between engines to gather statistics, which doesn't need graphics at all and can be run in a cluster overnight. This is great for testing changes to an engine, to measure if the change is actually an improvement. Unfortunately there are two competing interfaces: XBoard and UCI (Universal Chess Interface). Neither of them is perfect, but UCI is very reasonable in many respects. For the game of go, there is a dominant interface called GTP (Go Text Protocol).
#12 Members - Reputation: 1575
Posted 16 November 2012 - 06:51 AM
If everything in OOP had to be a class, we'd be writing code like below, which we don't --
Assertion( Comparison( Adder( Integer(1), Integer(1) ).Result(), Integer(2) ).Result() ).Check();
[source lang="ruby"]smile if Ruby.isBeautiful?[/source]
Edited by Khatharr, 16 November 2012 - 06:52 AM.
void hurrrrrrrr() {__asm sub [ebp+4],5;}
There are ten kinds of people in this world: those who understand binary and those who don't.
There are ten kinds of people in this world: those who understand binary and those who don't.
#13 Members - Reputation: 839
Posted 16 November 2012 - 09:21 AM
[source lang="c"]is_readable? depend_on_dev() : ruby_char_saver();[/source]
If everything in OOP had to be a class, we'd be writing code like below, which we don't --
Assertion( Comparison( Adder( Integer(1), Integer(1) ).Result(), Integer(2) ).Result() ).Check();
[source lang="ruby"]smile if Ruby.isBeautiful?[/source]
#14 Members - Reputation: 1246
Posted 16 November 2012 - 10:18 AM
I usually tend to design more in terms of state and transformations.
Think about what structure can represent each valid configuration of your game unambiguously. Then think about which are valid transformations on that data and which actor has the authority to do these.
This should lead to a nice code structure will well defined operations where classes control the integrity of the game state.
EDIT: I realized this sounds pretty vague. Maybe it is because that's the way one should design regardless of language. I guess the TL;DR version would be: Don't think of OOP as a philosophy that forces you to program a certain way. Rather, think of it as a tool set that enables you to more efficiently implement a sensible design.
Think about what structure can represent each valid configuration of your game unambiguously. Then think about which are valid transformations on that data and which actor has the authority to do these.
This should lead to a nice code structure will well defined operations where classes control the integrity of the game state.
EDIT: I realized this sounds pretty vague. Maybe it is because that's the way one should design regardless of language. I guess the TL;DR version would be: Don't think of OOP as a philosophy that forces you to program a certain way. Rather, think of it as a tool set that enables you to more efficiently implement a sensible design.
Edited by Madhed, 16 November 2012 - 11:36 AM.
#15 Members - Reputation: 1575
Posted 16 November 2012 - 04:22 PM
[source lang="c"]is_readable? depend_on_dev() : ruby_char_saver();[/source]
If everything in OOP had to be a class, we'd be writing code like below, which we don't --
Assertion( Comparison( Adder( Integer(1), Integer(1) ).Result(), Integer(2) ).Result() ).Check();
[source lang="ruby"]smile if Ruby.isBeautiful?[/source]
"Programmer" (n) - A person so utterly maladjusted that they can take a language as beautiful and expressive as Ruby and write something that looks like a declaration of war composed by a drunken, illiterate Klingon.
Some people's Ruby makes me want to hurt myself.
...
Or them.
lol
Edited by Khatharr, 16 November 2012 - 04:24 PM.
void hurrrrrrrr() {__asm sub [ebp+4],5;}
There are ten kinds of people in this world: those who understand binary and those who don't.
There are ten kinds of people in this world: those who understand binary and those who don't.
#16 Members - Reputation: 839
Posted 17 November 2012 - 01:45 AM
[source lang="c"]is_readable? depend_on_dev() : ruby_char_saver();[/source]
If everything in OOP had to be a class, we'd be writing code like below, which we don't --
Assertion( Comparison( Adder( Integer(1), Integer(1) ).Result(), Integer(2) ).Result() ).Check();
[source lang="ruby"]smile if Ruby.isBeautiful?[/source]
"Programmer" (n) - A person so utterly maladjusted that they can take a language as beautiful and expressive as Ruby and write something that looks like a declaration of war composed by a drunken, illiterate Klingon.
Some people's Ruby makes me want to hurt myself.
...
Or them.
lol
That's true. Yet have I to see a language that assures whatever is written to look beautiful.
There are war-declaring drunk illiterate klingons everywhere.
I do think Hodgmans example involved somewhat more levels of encapsulation, but I do get what you mean.
#17 Members - Reputation: 1101
Posted 18 November 2012 - 11:47 PM
There are no "right" ways to do OO design, just like there are no right ways to do data modeling. There are ways that let you get working code, with more or less trouble than other ways, for different values of "working code" and "trouble".
But I'm going to illustrate some code suggestions, with incomplete examples, if you'll allow me the liberty. My goal is simply to get you thinking and get your design juices flowing with some concrete starting points.
First, I'm going to assume that I'm dealing with a fixed size 8x8 chess / checkers style board, and a game with well know rules and fixed sets of pieces. Not because that matters, but because it will let me focus on certain parts of the problem first, while changing those things would require going a few levels further down the rabbit hole.
[source lang="plain"]Player NamePiece Type - { Knight, Rook, etc. } Owner : PlayerSquare Color HasPiece : bool PieceBoard ClearBoard() - makes the board completely empty AddPiece(Piece) - RemovePiece(Location) - removed the piece at the specified location MovePiece(Location source, Location destination) - take a piece off of source, puts on destination - in my version I raise an error if no piece exists at source, and also if destination is not empty. - that's because I want my "game engine" deciding if pieces can kill pieces, etc - not my board. SquareAt(Location) : Square - returns the square requested, or throws out of range exception EachSqaure() : Enumerator<Square> - enumerates all 64 squares ... you can write other enumerators that might be useful for your game, such as ... EachSquareInRow(int) : Enumerator<Square> - returns the list of squares in the specified row EachSquareInColumn(int) : Enumerator<Square> - returns the list of squares in the specified column EachSquareForPlayer(Player) : Enumerator<Square> - the list of squares with pieces of the provided playerChessEngine InitializeChessBoard(Board emptyBoard, Player white, Player black) - constructs and places the white and black pieces on the board. IsValidMove(Board, Player, Location, Location) IsInCheck(Board, Player) : bool IsInCheckmate(Board, Player) : bool EachValidMove(Board, Player, Location) : Enumerator<Square> - returns each move the player can make from the selected location. returns an empty list if no valid moves existChessGame Board : Board Players : Player[2] Turn : int Phase : int - 0 for white, 1 for black[/source]
I don't have time to go any further right now ... and of course this design would change and evolve for any real-world coding exercise ... I just wanted to give you some concrete thoughts about the types of things that might be classes and their methods. Good luck.
But I'm going to illustrate some code suggestions, with incomplete examples, if you'll allow me the liberty. My goal is simply to get you thinking and get your design juices flowing with some concrete starting points.
First, I'm going to assume that I'm dealing with a fixed size 8x8 chess / checkers style board, and a game with well know rules and fixed sets of pieces. Not because that matters, but because it will let me focus on certain parts of the problem first, while changing those things would require going a few levels further down the rabbit hole.
[source lang="plain"]Player NamePiece Type - { Knight, Rook, etc. } Owner : PlayerSquare Color HasPiece : bool PieceBoard ClearBoard() - makes the board completely empty AddPiece(Piece) - RemovePiece(Location) - removed the piece at the specified location MovePiece(Location source, Location destination) - take a piece off of source, puts on destination - in my version I raise an error if no piece exists at source, and also if destination is not empty. - that's because I want my "game engine" deciding if pieces can kill pieces, etc - not my board. SquareAt(Location) : Square - returns the square requested, or throws out of range exception EachSqaure() : Enumerator<Square> - enumerates all 64 squares ... you can write other enumerators that might be useful for your game, such as ... EachSquareInRow(int) : Enumerator<Square> - returns the list of squares in the specified row EachSquareInColumn(int) : Enumerator<Square> - returns the list of squares in the specified column EachSquareForPlayer(Player) : Enumerator<Square> - the list of squares with pieces of the provided playerChessEngine InitializeChessBoard(Board emptyBoard, Player white, Player black) - constructs and places the white and black pieces on the board. IsValidMove(Board, Player, Location, Location) IsInCheck(Board, Player) : bool IsInCheckmate(Board, Player) : bool EachValidMove(Board, Player, Location) : Enumerator<Square> - returns each move the player can make from the selected location. returns an empty list if no valid moves existChessGame Board : Board Players : Player[2] Turn : int Phase : int - 0 for white, 1 for black[/source]
I don't have time to go any further right now ... and of course this design would change and evolve for any real-world coding exercise ... I just wanted to give you some concrete thoughts about the types of things that might be classes and their methods. Good luck.
#18 Moderators - Reputation: 1325
Posted 30 November 2012 - 12:10 AM
The best OOP exercise I can think of with checkers is the difference between a regular piece and king.
Chess would probably offer a lot more exercises due to the differing pieces; now you can have a (virtual) method to select the icon to draw, a (virtual) method to get the valid-moves-template, etc...
In checkers you have to force it by having a IPiece interface and implement it in a RegularPiece and a KingPiece class.
Oh as mentioned above 'moves' are a great OOP exercise - it's a proxy for Undo which is a beautiful OOP example.
You have an IMove interface that has two methods, Move and Unmove.
Then you have two stacks, the Undo stack and the Redo stack.
Whenever you make a move you create a Move instance with all the info you need to make the move then execute the 'Move'.
Then push it onto the Undo stack. If the user waps an Undo, you pop the Undo stack and 'Unmove' then push it onto the Redo stack.
(If they wap Redo, you pop the Redo stack and execute it.)
If the Undo or Redo stack is empty, grey-out the respective buttons.
Chess would probably offer a lot more exercises due to the differing pieces; now you can have a (virtual) method to select the icon to draw, a (virtual) method to get the valid-moves-template, etc...
In checkers you have to force it by having a IPiece interface and implement it in a RegularPiece and a KingPiece class.
Oh as mentioned above 'moves' are a great OOP exercise - it's a proxy for Undo which is a beautiful OOP example.
You have an IMove interface that has two methods, Move and Unmove.
Then you have two stacks, the Undo stack and the Redo stack.
Whenever you make a move you create a Move instance with all the info you need to make the move then execute the 'Move'.
Then push it onto the Undo stack. If the user waps an Undo, you pop the Undo stack and 'Unmove' then push it onto the Redo stack.
(If they wap Redo, you pop the Redo stack and execute it.)
If the Undo or Redo stack is empty, grey-out the respective buttons.
Edited by Shannon Barber, 30 November 2012 - 12:14 AM.
- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara
#19 Moderator* - Reputation: 5410
Posted 30 November 2012 - 01:46 AM
This isn't necessarily directly applicable to your case (right now, at least), but I think thinking about Antiobjects more can be very useful and constructive to good design. For example, I once made a game where there were hundreds of units doing pathfinding on a decently sized map. The "normal" OOP methodology would be to make each unit an Object of some sort and give it the ability to find a path given some information (like a game board of tiles), or make some helper class that, given a unit and a board, finds the path. Or something like that. After reading (part of) that paper, I instead made the tiles of the game board Objects and the tiles did the pathfinding, and the overall interface and design was greatly simplified after doing that.
Anyway, I just want to point out that when considering how do design your objects and relationships, sometimes the "better" solutions require you to think outside the box, where an Object (and its role) isn't the obvious.
Anyway, I just want to point out that when considering how do design your objects and relationships, sometimes the "better" solutions require you to think outside the box, where an Object (and its role) isn't the obvious.
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]
