mercredi 24 novembre 2021

Best way to store chess piece locations to easily lookup a location given a piece or a piece given a location using object oriented design principles

I'm currently working on a OO representation of a simplified chess game. Most of it is straightforward enough but one design decision I'm a little unsure about is the relationship between the chessBoard and pieces. The bottom line is I'm trying to figure out the best way to represent the chessboard / piece relationship so that I can easily and efficiently query "given a spot, is there a piece here" and "given a piece, what spot is it on"?

Currently, the Piece class stores both their own location (using a Spot class) and a reference to the Board class. The board class represents the board as a Dictionary<Spot, Piece> (the simplified game only has a few pieces so it felt unnecessary to store a mostly empty array of N by M spots like other examples I've seen) to track what spots on the board have what pieces on them. This is useful and seems intuitive to me since the piece can use the reference to the board when trying to move and ask "is there anyone at this spot?" and it can return the piece if any that is on a given spot. Similarly, in order to move the piece I need to know where it currently is and storing the location on the piece itself seems like a good OO approach.

The part where I'm running into some questions / trouble is how to keep those values in sync such that if I call (public method) Board.MovePiece() or (private setter) Piece.CurrentPosition = new spot() both Piece.CurrentPosition and the Board's Dictionary<Spot, Piece> are updated properly. Keeping everything as private as possible while making sure that calling a method on either the board or the piece while keeping the other class in sync is very tricky if not impossible. If C# had friend classes like C++ I could just make the Board a friend of the Piece then they could set each other's private vars no problem (I'm aware of internal which improves things but I don't think it prevents other code in the project from theoretically calling stuff it shouldn't). Right now my solution to this is a custom setter on the piece.CurrentPosition property so that every call to change it results in the correct call to public board members (which absolutely works) but I feel like I could do better. The biggest risk is the board methods are public and could be called outside the piece class and thus not update the piece location but I'm not a huge fan of the redundancy / slight complexity smell the code has currently.

Here's a simplified look at my code:

public class Board : IBoard
    {
        private uint _width;
        private uint _height;
        private Dictionary<Spot, Piece> _pieceLocations;

        public Board(uint width, uint height)
        {
            _width = width;
            _height = height;

            _pieceLocations = new Dictionary<Spot, Piece>();
        }

        // heavily used by piece when determining legal moves, what pieces and free spaces are in range etc.
        public Piece CheckSpot(Spot spot)
        {
            Piece piece;
            if (_pieceLocations.TryGetValue(transformSpot(spot), out piece))
            {
                return piece;
            }
            return null;
        }
 
        /// remove instead of null to potentially optimize space a bit
        public bool RemovePiece(Spot spot)
        {
            if (spot != null)
            {
                return _pieceLocations.Remove(transformSpot(spot));
            }
            return false;
        }

        /// This function will simply attempt to just move the piece to the specified destination.
        /// It's up to the caller to make sure the move is a valid chess move, etc
        public Spot MovePiece(Spot destination, Piece pieceToBeMoved)
        {
            // remove piece from current position
            // note the need to have current position here
            RemovePiece(pieceToBeMoved.CurrentPosition);

            // attempt to place at and return new position
            return PlacePiece(destination, pieceToBeMoved);
        }

        /// Simply places piece at specified destination if not occupied by another piece
        private Spot PlacePiece(Spot destination, Piece pieceToPlace)
        {
            var transformedDestination = transformSpot(destination);

            //business logic to check for stuff like a piece already at destination

            _pieceLocations.Add(transformedDestination, pieceToPlace);

            return transformedDestination;
        }

Note transformSpot just makes sure coordinates are not out of bounds and "wraps them around" to be within board dimensions if need be.

public abstract class Piece : IPiece
    {
        protected IBoard _board;
        public ColorType Color { get; protected set; }
        private Spot _currentPosition;

        public Piece(ColorType color, Spot currentPosition, IBoard board)
        {
            _board = board;
            Color = color;
            CurrentPosition = currentPosition ?? throw new ArgumentNullException(nameof(currentPosition), "When creating a piece you must specify a location");
        }

        public Spot CurrentPosition { 
            get { return _currentPosition; } 

            // I wanted to make sure that the piece's current position was always in sync with the board.
            // Calling <Board> functinos here seemed like a reasonable approach.
            protected set {

                // if position is being set to null remove from board
                if (value == null)
                {
                    _board.RemovePiece(_currentPosition);
                    _currentPosition = null;
                }
                else
                {
                    _currentPosition = _board.MovePiece(value, this);
                }
            }
        }

        public void Move()
        { 
            // note that I now need the current position to figure out where I can go etc.
            
            // insert logic to determine where we can move using chess rules etc.
            var destination = new Spot(x,y);

            // if spot is occupied remove piece
            var occupyingPiece = _board.CheckSpot(destination);
            if (occupyingPiece != null)
            {
                occupyingPiece.RemovePiece();
            }

            // call custom setter which in turn updates board to move piece from current spot to destination
            CurrentPosition = destination;
        }

        public void RemovePiece()
        {
            // call custom setter which in turn updates board to remove piece
            CurrentPosition = null;
        }

And some super rough pseudo code for the main driver

            List<Piece> whitePieces = generateWhitePieces();
            List<Piece> blackPieces = generateBlackPieces();

            while (gameActive)
            {

                //somehow determine which piece to move
                var pieceToMove = whitePieces.PickPiece();

                // could pass and store CurrentPosition at this level but if it's not stored on the piece or easily 
                // accessible from the board but feels slightly icky
                pieceToMove.Move();

                pieceToMove = blackPieces.PickPiece();

                pieceToMove.Move();
                // etc.

            }

Again, main flaw on top of some possibly unneeded complexity seems to be that Board.MovePiece() needs to be public for Piece to call it but that means anyone can also call MovePiece() and move something on the board without updating the piece.

Possible solutions I have considered:

I'm totally overthinking this and this is a fairly reasonable approach.

  • having the piece own its own location feels right, just wish I had better access modifiers to protect sensitive values but allow friends to change them (I'm aware of internal but doesn't seem to solve my issues fully)

I could just remove currentPos and:

  • have the board class maintain a Dictionary<Piece, Spot>

This feels like simply shifting the issue and having board maintain two dictionaries of essentially the same info in different orders feels silly, but at least it tightly couples the data together and allows the board to be the "authority" on where everything is. Leaning towards this but have a feeling this could be optimized somehow with the right data structure

  • have the main driver / game class maintain a dictionary / tuple list of pieces and their current position and have the Piece.Move() pass back info on where the board tells them they are now.

Again this just feels like we're shifting the issue but even more so. On the other hand I can kinda see the rationale for the game to want to keep track of pieces but that still feels pretty anti OO and I'd probably prefer keeping this to the Board as described above.

In theory could also

  • Just make current position setter public so Board could change it directly and add some complex checks in both the Board functions and the Piece.CurrentPosition setter to make sure if one is changed so is the other.

Feels much worse and adds more complexities / risks than it solves in my opinion. If it weren't for this issue CurrentPosition should have a private setter.

Anyway would very much appreciate any feedback / insight!

Aucun commentaire:

Enregistrer un commentaire