3

Пытаюсь в силу своих знаний написать движок дли игры в русские шашки на C++ (если точнее, уже по большей части написал). Требуется определить, какую структуру данных лучше использовать для хранения оных, так как при большой глубине повторяющиеся позиции увеличивают сложность просчёта.

struct data {
uint32_t fields[4]; 
char turn; //0 или 1
}

Пусть есть рассматриваемый элемент из графа, по которому построен новый элемент. Требуется, чтобы можно было быстро найти, есть ли уже новый элемент в графе, а если есть, то присвоить текущему рассматриваемому элементу ссылку на него, если нет - то создать новый элемент с текущим рассматриваемым в качестве родительского. Правда будут образовываться циклы.

Также не хотелось бы терять быстрый доступ к дочерним и родительским элементам, да и вообще к элементам из-за каких-нибудь коллизий, но чтобы при этом было быстро. Я понимаю, что все желания не удовлетворить, но посоветуйте что-то, пожалуйста. Да и вообще что можно почитать по структурам данных (не конкретно для C++)?

1 ответ 1

0

Просто оценим разные способы представления позиции в шашках.
Клеток всего 32 — 64 клетки пополам, насколько я помню шашки.

Вариант 1. Идем от шашек. Максимум 24. Каждая имеет цвет (1 бит), дамка или нет (еще 1 бит), координата (32 клетки — 5 бит). Ну, еще один бит, увы, — на доске ли она (жаль, но координатами тут не сыграть). Итого — 8 бит на шашку. 24*8 — 192 бита.

Вариант 2. Идем от доски. Состояний каждой клетки не более чем 5: пустая, черная шашка, белая шашка, черная дамка, белая дамка. Итого 3 бита на клетку. Всего 96 бит.

Вариант 3. Опять же от доски, но с префиксным кодом. Итак, бит 0 — клетка пустая; бит 1 — клетка не пустая, и тогда следующие 2 бита означают, какая именно на ней шашка. Итого в пределе 8 бит на пустые + 24*3 бита на занятые (а то и меньше, после снятия шашек) — в сумме 80 бит. Для равномерности заполнения можно забивать неиспользованные позиции нулями.

Ну, это уже long double, если не ошибаюсь :) Словом, вполне хранимая и быстро отыскиваемая структура. Только вот чем она короче, тем длиннее код, который ее распаковывает.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.