Лучший способ хранения местоположений шахматных фигур для простого поиска местоположения, заданного фигурой, или фигуры, заданной местоположением, с использованием принципов объектно-ориентированного проектирования

#c# #dictionary #oop #design-patterns #chess

Вопрос:

В настоящее время я работаю над представлением упрощенной шахматной игры. Большая часть этого достаточно проста, но одно дизайнерское решение, в котором я немного не уверен, — это взаимосвязь между шахматной доской и фигурами. Суть в том, что я пытаюсь найти наилучший способ представления отношений между шахматной доской и фигурой, чтобы я мог легко и эффективно запрашивать «задано место, есть ли здесь фигура» и «задана фигура, на каком месте она находится»?

В настоящее время класс Piece хранит как свое собственное местоположение (используя класс Spot), так и ссылку на класс Board. Совет класса представляет совет в качестве словаряlt;Spot, Piece=»»gt; (упрощенная игре всего несколько штук, так он чувствовал себя ненужным магазине в основном пустой массив из N по M мест, как других примеров, которые я видел), чтобы отслеживать, какие места на борту есть то, что фигуры на них. Это полезно и кажется мне интуитивно понятным, так как фигура может использовать ссылку на доску при попытке двигаться и спрашивать: «Есть ли кто-нибудь в этом месте?», и она может вернуть фигуру, если таковая имеется в данном месте. Точно так же, чтобы переместить фигуру, мне нужно знать, где она находится в данный момент, и сохранение местоположения на самой фигуре кажется хорошим подходом.

Часть, в которой я сталкиваюсь с некоторыми вопросами / проблемами, заключается в том, как синхронизировать эти значения, чтобы, если я вызову (общедоступный метод) Доска.movePiece() или (частный сеттер) Кусок.currentPosition = новое место() обе части.Текущая позиция и словарь Доскиlt;Spot, Piecegt; обновлены должным образом. Сохраняя все как можно более конфиденциальным, убедившись, что вызов метода либо на доске, либо на фигуре, сохраняя синхронизацию с другим классом, очень сложно, если не невозможно. Если бы у C# были классы друзей, такие как C , я мог бы просто сделать Доску другом произведения, тогда они могли бы без проблем устанавливать личные переменные друг друга (я знаю о внутренних, которые улучшают ситуацию, но я не думаю, что это мешает другому коду в проекте теоретически называть вещи, которые он не должен). Прямо сейчас мое решение этой проблемы-это пользовательский сеттер на изделии.Свойство currentPosition, чтобы каждый вызов для его изменения приводил к правильному вызову членов общественного совета (что абсолютно работает), но я чувствую, что мог бы сделать лучше. Самый большой риск заключается в том, что методы платы являются общедоступными и могут быть вызваны вне класса piece и, следовательно, не обновлять местоположение элемента, но я не большой поклонник избыточности / небольшого запаха сложности, который в настоящее время присутствует в коде.

Here’s a simplified look at my code:

 public class Board : IBoard  {  private uint _width;  private uint _height;  private Dictionarylt;Spot, Piecegt; _pieceLocations;   public Board(uint width, uint height)  {  _width = width;  _height = height;   _pieceLocations = new Dictionarylt;Spot, Piecegt;();  }   // 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 lt;Boardgt; 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

 Listlt;Piecegt; whitePieces = generateWhitePieces();  Listlt;Piecegt; 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 Dictionarylt;Piece, Spotgt;

Это похоже на то, как просто перенести проблему и заставить совет директоров поддерживать два словаря по существу одной и той же информации в разных порядках, кажется глупым, но, по крайней мере, это тесно связывает данные вместе и позволяет совету быть «авторитетом» в том, где все находится. Склоняюсь к этому, но чувствую, что это можно как-то оптимизировать с помощью правильной структуры данных

  • попросите основной класс драйверов / игр вести список фигур по словарю / кортежу и их текущее положение, а также передайте Piece.Move() информацию о том, где они находятся сейчас на доске.

Опять же, это просто похоже на то, что мы меняем тему, но еще больше. С другой стороны, я отчасти вижу причину, по которой игра хочет отслеживать фигуры, но это все еще кажется довольно анти-ОО, и я, вероятно, предпочел бы оставить это на доске, как описано выше.

Теоретически можно было бы также

  • Просто обнародуйте текущее положение, чтобы Правление могло напрямую изменить его и добавить некоторые сложные проверки как в функции Правления, так и в Фигуру.Установщик текущего положения, чтобы убедиться, что если одно из них изменено, то и другое тоже.

Чувствует себя намного хуже и добавляет больше сложностей / рисков, чем решает, на мой взгляд. Если бы не эта проблема, у currentPosition должен был бы быть частный сеттер.

В любом случае, я был бы очень признателен за любую обратную связь / понимание!

ПРАВКА: для ясности я предполагаю, что класс фигур владеет своей логикой, когда дело доходит до того, как он может перемещаться, и использует состояние доски, чтобы определить, в какие места он может перемещаться. Что-то вроде Кусочка.DetermineMove(). В частности, фигура должна знать, где она находится и какие части, если таковые имеются, находятся в местах, куда она может перемещаться, части, которые ей угрожают, и т. Д.

Если это плохой дизайн, я весь внимание, но мне трудно поверить, что класс предметов не должен обладать собственной логикой движения в дизайне ООП.

Комментарии:

1. Во-первых, я бы спросил себя, действительно ли необходима дополнительная избыточность/сложность или простого (линейного) поиска будет достаточно для одного из двух возможных запросов.

2. Это очень правильный вопрос, но я не думаю, что это действительно хорошее расширяемое / долгосрочное дизайнерское решение. Для ясности вы предлагаете мне просто взять словарьlt;Место, фрагментgt; и перебирать записи, пока фрагмент не найдет себя? Я понимаю вашу точку зрения, но я пытаюсь продемонстрировать хорошую практику проектирования, и это кажется наивным.

3. Да, это была моя первая идея. Если их всего несколько штук, это будет трудно превзойти с помощью более сложного алгоритма.

4. Предполагая, что я игнорирую удвоение пространства на секунду и добавляю перевернутый словарьlt;Кусок, пятноgt;, как вы думаете, дополнительные шаги по добавлению / удалению, необходимые для обслуживания второго диктатора, все равно затмят сложность O(N) поиска в списке каждый раз для определения местоположения фрагмента? Такое ощущение, что это попадает в сорняки деталей реализации и оптимизации компилятора, но моя интуиция говорит, что все, что превышает 2-3 части, начинает затягиваться по сравнению с простым поддержанием второго диктатора.

5. Тем не менее, я полагаю, что есть смысл в снижении сложности и использовании пространства (хотя опять же мы предполагаем, что диктанты содержат очень мало записей). На бумаге, однако, поиск идет от времени O(1) и пространства O(n) с двумя указаниями ко времени O(n) и все еще пространству O(n), если мы просто ищем одно. Может быть, время на часах благоприятствует поисковому подходу, но на бумаге я не уверен, что мы получаем слишком много за пределами простоты и лучшего владения.

Ответ №1:

На этот счет будет много мнений, и на самом деле нет абсолютно правильного ответа. У каждого из них будут свои плюсы и минусы, некоторые из которых вы, возможно, узнаете гораздо позже в процессе разработки. Как бы то ни было, вот мое. 🙂

Что вы действительно хотите сделать, так это убедиться, что в вашем приложении есть только один способ выполнения любой операции и только одно место, где в приложении хранятся библейские данные (помимо религиозных коннотаций, библейское значение «истинно»).

Вы можете начать с логических объектов (в вашем домене) и попытаться поместить этот метод в объект, для которого он имеет смысл. Если это не имеет смысла, вам может потребоваться другая [ментальная] модель.

Ты начал с Board Piece того , Spot и до сих пор мне это нравится. Поскольку мы хотим сохранить данные о местоположении фигуры в одном месте, я думаю, что мы хотим сделать это на уровне доски, потому что это облегчит движение (фигуре не придется «подниматься» на доску и «опускаться» на другую фигуру).

Это означает, что у a Piece не будет Spot свойства, только тип (рыцарь, слон и т. Д.) И тип цвета (белый/черный). На доске будет словарь для фигур с ключом в Spot качестве ключа (это хороший ключ — на квадрате может быть только одна фигура). Это значительно упрощает логику. Перемещение части означает, что вынимаете ее из диктанта и возвращаете в пункт назначения:

 // Move attempt method might look like this:  Piece thisPiece = ... ; Spot old = (1, 1); // origin ..  Spot new = (2, 2); // .. destination  // do some validation if (pieces.Contains(new) amp;amp; pieces[new].color == thisPiece.color)  throw new SpotOccupiedByFriendlyPieceAndThisIsntACastleException();   // capture a piece if (pieces.Contains(new) amp;amp; pieces[new].color != thisPiece.color) {  pieces.Remove(new); } pieces.Remove(old); // move the old piece from "old"... pieces.Add(new, thisPiece); //... to "new"  

Поместив все фигуры в a Dictionarylt;Spot, Piecegt; на уровне доски, можно получить только одну коллекцию, которая поддерживает отношения «части к пятнам» (она принадлежит доске), и доска может выполнять всю логику, которая ей нужна.

Комментарии:

1. Я согласен с вашим предложением сохранить логику для фактического перемещения фигур и представления того, где они находятся на доске, в самом классе доски, но это не решает мою фундаментальную проблему: как класс доски эффективно определит местоположение данной фигуры только с помощью словаряlt;Место, фигураgt; ? В моей модели, допустим, я сохраняю всю логику для определения того, какой ход сделать в фигуре. Функция DecideWhereToMove (). Эта функция должна задать правлению два разных вопроса: «Что находится в пространстве X, Y?» и «Где я нахожусь?».

2. Я могу легко ответить на первый вопрос с помощью словаряlt;Spot, Piecegt; через существующую доску. Проверьте пятно(точечное пятно), как показано выше. Но если я сохраню все в классе доски, мне также понадобится что-то вроде доски. GetPieceLocation(фрагмент) , который возвращает место, на котором находится фрагмент. Идеи, с которыми я столкнулся, включают второй словарь, но перевернутый (так что словарьlt;Кусок, пятноgt;), но у него есть некоторые недостатки в удвоении хранилища и необходимости поддерживать два диктанта. Другое предложение состоит в том, чтобы просто линейно перебирать существующий словарь, пока мы вслепую не найдем искомый фрагмент, но это кажется наивным.

3. В моей модели выше вам никогда не нужно «находить место для данной детали», а вместо этого «находить деталь для данной детали». Фигура не должна знать, куда двигаться, или действительно иметь какое-либо представление о состоянии доски. Эти данные «выше его уровня оплаты». Совет директоров должен выполнить эту работу.

4. (В целом) действительно плохо дублировать данные в двух диктах — вы открываете себя классу ошибок десинхронизации. Я имею в виду, что в шахматах нам никогда не нужно получать фигуру абстрактно (т. Е. Мы никогда не говорим «на каком месте мой король»), мы получаем фигуру только начиная с места («что на (1,1)?»). Позвольте мне сформулировать это по — другому-когда вы спрашиваете: «Как класс доски эффективно определил бы местоположение данной фигуры?», я отвечаю: «доска никогда не должна нуждаться в этом». Части не существуют без точки, и мы начинаем каждую операцию с точки (перемещение, захват, оценка «откуда»).

5. Вы предполагаете, что Фигура не должна обладать собственной логикой движения (пешки могут двигаться так, короли могут делать это и т. Д.) ? Если я правильно понимаю, то доска будет не только владеть состоянием доски, но и заключать в себе все возможности перемещения каждого типа фигур, и это кажется неправильным для чего-то, что должно быть ООП по своей природе. Возможно, если бы вы привели пример того, как фигура будет вызывать метод доски, чтобы переместить ее, я бы лучше понял. В частности, я хочу понять, откуда берутся / заселяются старые и новые пятна, если они не передаются по частям.