Гомоку Правление представительства
Я работаю над игрой Gomoku и мне нужна эффективная структура данных для хранения состояния плат, я думал о том, чтобы сохранить ее в 2D-массиве, но я уверен, что есть более эффективный способ. Спасибо
1 ответ
С точки зрения эффективности времени, поскольку я считаю, что вы будете в основном выполнять поиск по индексу, массив будет в значительной степени лучшим выбором - он поддерживает этот поиск в постоянное время с низким постоянным коэффициентом.
С точки зрения эффективности использования пространства:
Каждый квадрат может быть либо пустым, либо заполненным любым игроком. Таким образом, существует максимум 3 возможности. Для максимальной эффективности использования пространства мы могли бы хранить всю нашу плату в представлении base-3, но, поскольку компьютер работает в двоичном формате, нам необходимо обработать всю плату, чтобы определить значение некоторого заданного квадрата (таким образом, простой поиск по индексу будет занять время, пропорциональное размеру доски - если время действительно не проблема, вы можете рассмотреть это). Вместо этого я бы рекомендовал использовать 2 бита на квадрат, что позволило бы нам указать одну из 4 возможностей (четвертая не используется).
Многие языки имеют своего рода реализацию наборов битов, что позволяет вам работать с массивом битов, который идеально подходит для вышеперечисленного.
Вы также хотели бы только один набор битов (не 2D), поскольку при работе с 2D-структурами обычно требуется немного дополнительной памяти. Преобразование из 2D в 1D простое - мы могли бы преобразовать 2D индекс в 1D с помощью любого x*height + y или же y*width + x,
Хотя я бы рекомендовал сначала быть уверенным, что вам нужно выполнить эту оптимизацию - я считаю, что платы Gomoku обычно малы, поэтому даже громоздкое представление будет работать идеально (хотя некоторые методы искусственного интеллекта делают много копий платы, поэтому, если вы при этом минимальное представление имело бы смысл).