В двух предыдущих выпусках на примере игры в шахматы я показал, как создать в памяти состояние доски. Использовались два подхода: подход "От объектов" сохранял отдельно каждый объект (фигуру), подход "От пространства" сохранял пространство (доску) целиком вместе с его содержимым.
Напомню, как в памяти выглядят фигуры:
...и как выглядит пространство доски:
Использовать можно оба подхода. Но чтобы понять, какой из них более оптимален, нужно их сравнить с точки зрения прикладных задач.
1. Сколько нужно памяти?
Для хранения всех шахматных фигур в памяти требуется 64 байта (1 фигура – 2 байта). Для хранения содержимого шахматной доски требуется тоже 64 байта (1 клетка – 1 байт). Здесь разницы нет. Но так будет не всегда – смотрите пункт 2 про масштабирование.
2. Как перебрать все фигуры, которые есть на доске?
Если у нас есть список фигур, мы просто перебираем этот список.
Если у нас есть список клеток доски, мы перебираем клетки. Но клетка - это не фигура. Нужно проверить, есть что-то в клетке или нет.
Значит, чтобы перебрать объекты, нужно столько шагов, сколько есть объектов (максимум 32). Чтобы сосчитать клетки доски с объектами, нужно всегда 64 шага. Потому что пустые клетки нужно проверять тоже.
Числа 32 и 64 на самом деле смешные, в реальной жизни они не создают никакой разницы. Но если у нас окажется 4096 объектов, а доска будет размером 1024 на 1024 клетки, разница будет огромная.
В случае с шахматами можно сказать, что оба метода справляются хорошо, но при увеличении масштаба список объектов окажется значительно быстрее.
3. Как узнать, какая фигура находится в некой клетке?
Дана клетка с координатами, а точнее с адресом. Чтобы узнать, какой объект в ней находится, нужно перебрать все объекты и сравнить их адреса с адресом клетки. Если адреса совпали – значит в этой клетке находится этот объект, и дальше поиск можно не продолжать. Если не совпали – искать дальше, пока не дойдем до конца списка. Значит, операция поиска будет требовать минимум 1 шаг и максимум 32 шага.
Если же у нас хранится доска, нам не нужно перебирать все клетки. Отмерив от начала доски нужное расстояние (адрес), мы сразу попадаем в нужную клетку и сразу можем узнать, какая фигура в ней хранится. То есть эта операция будет всегда занимать ровно один шаг.
Значит, в этом вопросе подход "от пространства" гораздо быстрее.
4. Как узнать возможные ходы фигуры?
Каждая фигура в шахматах может атаковать в разных направлениях и на разное расстояние. Возьмем для примера самую мощную фигуру – ферзя.
Как видим, ферзь может атаковать значительное количество клеток доски. Но если у него на пути стоит другая фигура, она будет закрывать собой атаку. Значит, для всех клеток, которые ферзь атакует, надо ещё выяснить, не стоят ли в них фигуры. И только после этого можно уточнить доступные ферзю ходы.
Занята клетка или нет, можно узнать из пункта 3. Операция поиска фигур повторяется столько раз, сколько надо проверить клеток, и поэтому подход "от пространства" оказывается значительно быстрее.
5. Как узнать, находится ли клетка под ударом?
Королю нельзя вставать на клетку, которая находится под ударом. Кроме того, если писать хотя бы зачатки бота для игры в шахматы, то нас в принципе должно интересовать, какие клетки в шахматной позиции находятся под ударом, а какие нет. Значит, такую проверку надо будет так или иначе выполнять для всех клеток, в том числе занятых фигурами.
Для каждой клетки доски нужно выполнить следующее:
- Найти каждую фигуру противника и получить для нее возможные ходы
- Проверить, не попадает ли наша клетка в эти ходы.
Так как для этого мы будем использовать пункт 4, то подход "от пространства" опять себя оправдывает.
Здесь "от пространства" не только окажется лучше, но его можно еще и оптимизировать. Например, хранить признак "битости" прямо в самих клетках, чтобы не считать его повторно. А что такого? Если мы храним кусок пространства, мы можем хранить и его свойства. Можем даже добавить в клетки воду или лаву. Это пространство, оно материально, делайте с ним что хотите. И вдруг вы понимаете, что можно доску превратить в карту для RPG-бродилки:
Подытожим. И метод "от объектов", и метод "от пространства" имеют свои плюсы и минусы. В данном случае, конкретно для шахмат, выигрывает метод "от пространства". Но в общем случае, метод "от объектов" более удобен, когда:
- Объекты не находятся в фиксированных клетках, то есть их координаты могут задаваться произвольно
- В одних и тех же координатах может находиться несколько объектов
- Пространство большое, а объектов в нем мало
Метод "от пространства" более удобен, когда:
- Все объекты расставлены и перемещаются строго по клеткам, и в одной клетке находится не более одного объекта
- Пространство достаточно плотно заполнено объектами
- Клетки пространства могут иметь собственные свойства, даже если в них нет объектов (камень, вода, лава, лед и т.д.), т.е. фактически пространство является "картой местности"
Не стоит, однако, принимать это как правило. Во-первых, каждый из методов можно дорабатывать, чтобы избавить его от недостатков. Во-вторых, оба подхода можно совмещать. Например, иметь карту из клеток, по которой движутся объекты с произвольными, не жестко привязанными к клеткам координатами.
В следующем выпуске я рассмотрю адресацию в массивах, которая обязательно понадобится для перебора объектов, клеток и всего прочего, что есть в программе.