Хэш уровня для игры Sokoban
В интернете опубликованы тысячи уровней для игры Sokoban. Многие из них очень похожи, а иногда попадаются совсем одинаковые.
Есть ли способ быстро найти дубликаты?
Нужно посчитать хэш уровня, который будет зависеть от всех значащих клеток уровня, но не будет зависеть от несущественных клеток, а также от вращения, отражения уровня и от места старта.
Хэш уровня позволит мгновенно сравнивать два уровня, а также быстро искать дубликаты уровней среди большой коллекции.
Для расчёта хэша предлагается следующий алгоритм:
1) От стартовой клетки запускается волновой алгоритм, заполняющий все клетки уровня, доступные от стартовой. Волновой алгоритм поглощает ящики, однако не проходит сквозь стены.
2) Все клетки, до которых не дошёл алгоритм, заполняются стенами.
3) От уровня отрезаются лишние строки и столбцы, чтобы со всех 4-х сторон остались стены толщиной в 1 клетку.
4) От стартовой клетки снова запускается волновой алгоритм, заполняющий клетки уровня, доступные от стартовой без сдвигания ящиков. Теперь волновой алгоритм не проходит сквозь стены и ящики. Все клетки, поглощенные волной, отмечаются как стартовые.
5) Уровень превращается в строку - все клетки кодируются в соответствии с набором [#$ .*@+], затем строки составляются через разделитель ";" (в конце разделитель не ставится).
6) Строка, кодирующая уровень, превращается в байтовую последовательность согласно кодировке ASCII.
7) Байтовая последовательность хэшируется алгоритмом MD5. Хэш представляется в шестнадцатеричном виде.
8) Шаги 5-7 повторяются для 7 вариантов вращения-отражения уровня
9) Из восьми хэшей выбирается самый большой (считая, что "F" > "E" > "D" > ... > "1" > "0").
Этото хэш и считается хэшем уровня.
Например, для уровня:
#####
# @ #####
#...# * #
#$$$#####
# #
# #
######
На 1-м шаге волновой алгоритм поглотит клетки, отмеченные "!":
#####
#!!!#####
#!!!# * #
#!!!#####
#!!!!#
#!!!!#
######
В результате заполнения стенами получим:
##########
## @ #####
##...#####
##$$$#####
## ####
## ####
##########
Отрежем лишнее:
######
# @ ##
#...##
#$$$##
# #
# #
######
Второй волновой алгоритм отметит 6 клеток как стартовые:
######
#@@@##
#+++##
#$$$##
# #
# #
######
В виде строки получится так:
######;#@@@##;#+++##;#$$$##;# #;# #;######
Хэш по MD5 будет:
7FBD65B2C6C1D8D97B9351889AAD7BA5
Ещё 7 хэшей:
ACB3AB03A5A88A88DC79C1927AE58C8F
F297F897C2F148FABC7E60A3A1E818B9
F954EC89F5D96AF46C360E3560A437D9
F1CC3ACADB379C7D0FD95E2C3F5F5C77
B023CCFB6BCD72381DAC137172C038DB
22D14E54802D9BC0721737A58926C77D
FC1DCABE2E461BB6431A82A22FF9A4FE
Максимальный из них такой:
FC1DCABE2E461BB6431A82A22FF9A4FE
Это и есть хэш уровня.
Правила сравнения:
Если уровни равны, то и хэши равны.
Если уровни разные, то и хэши будут разные.
Ну есть вероятность коллизии хэшей (уровни разные, хэш одинаков), но она 2-128 (примерно 3*10-39), т.е. пренебрежимо мала.
Устойчивость хэша к модификации уровня:
1) Если уровень вращать или отражать, на шаге 9 всега будет выбираться один и тот же максимальный хэш.
2) Если перемещать место старта (не перебрасывая его через ящики), то на шаге 4 всё равно получится один и тот же результат.
3) Если добавить лишние стены, пустоты и даже ящики вне досягаемости от старта - они зальются стенами на шаге 2 и отрежутся на шаге 3.
4) А вот если стартовую точку перебросить через ящики, или если добавить ящики/стены/цели/пустоты в досягаемости от старта - хэш уровня станет другим.
Почти идентичный алгоритм описан на странице игры Sokoban от Bjorn Kallmark:
http://sourcecode.se/sokoban/level_id.php
Однако там алгоритм не содержит шага 4, поэтому не находит некоторые дубликаты.
Натравив мой алгоритм на коллекцию уровней на сайте Kallmark-а, я обнаружил 63 уровня, которые повторяются, причём некоторые - более одного раза.
Большая часть дубликатов несущественна (наборы Boxxle частично заимствованы из Classic, в сборнике Loma использованы уровни из других наборов, есть несколько повторений в пределах одного набора из-за невнимательности авторов, и т.п.)
Однако 11 уровней дублируются у разных авторов независимо.
В частности, один из уровней обнаружился 6 раз:
- Choriban.slc, уровни 26 и 34
- HomzLevels.slc, уровни 8 и 177
- Novoban.slc, уровень 40
- Pufiban.slc, уровень 126
Теперь есть возможность для моей игры SokobanCompact более грамотно составить коллекцию уровней.
P.S. Напишу Kallmark-у, посмотрим, что скажет.
Есть ли способ быстро найти дубликаты?
Нужно посчитать хэш уровня, который будет зависеть от всех значащих клеток уровня, но не будет зависеть от несущественных клеток, а также от вращения, отражения уровня и от места старта.
Хэш уровня позволит мгновенно сравнивать два уровня, а также быстро искать дубликаты уровней среди большой коллекции.
Для расчёта хэша предлагается следующий алгоритм:
1) От стартовой клетки запускается волновой алгоритм, заполняющий все клетки уровня, доступные от стартовой. Волновой алгоритм поглощает ящики, однако не проходит сквозь стены.
2) Все клетки, до которых не дошёл алгоритм, заполняются стенами.
3) От уровня отрезаются лишние строки и столбцы, чтобы со всех 4-х сторон остались стены толщиной в 1 клетку.
4) От стартовой клетки снова запускается волновой алгоритм, заполняющий клетки уровня, доступные от стартовой без сдвигания ящиков. Теперь волновой алгоритм не проходит сквозь стены и ящики. Все клетки, поглощенные волной, отмечаются как стартовые.
5) Уровень превращается в строку - все клетки кодируются в соответствии с набором [#$ .*@+], затем строки составляются через разделитель ";" (в конце разделитель не ставится).
6) Строка, кодирующая уровень, превращается в байтовую последовательность согласно кодировке ASCII.
7) Байтовая последовательность хэшируется алгоритмом MD5. Хэш представляется в шестнадцатеричном виде.
8) Шаги 5-7 повторяются для 7 вариантов вращения-отражения уровня
9) Из восьми хэшей выбирается самый большой (считая, что "F" > "E" > "D" > ... > "1" > "0").
Этото хэш и считается хэшем уровня.
Например, для уровня:
#####
# @ #####
#...# * #
#$$$#####
# #
# #
######
На 1-м шаге волновой алгоритм поглотит клетки, отмеченные "!":
#####
#!!!#####
#!!!# * #
#!!!#####
#!!!!#
#!!!!#
######
В результате заполнения стенами получим:
##########
## @ #####
##...#####
##$$$#####
## ####
## ####
##########
Отрежем лишнее:
######
# @ ##
#...##
#$$$##
# #
# #
######
Второй волновой алгоритм отметит 6 клеток как стартовые:
######
#@@@##
#+++##
#$$$##
# #
# #
######
В виде строки получится так:
######;#@@@##;#+++##;#$$$##;# #;# #;######
Хэш по MD5 будет:
7FBD65B2C6C1D8D97B9351889AAD7BA5
Ещё 7 хэшей:
ACB3AB03A5A88A88DC79C1927AE58C8F
F297F897C2F148FABC7E60A3A1E818B9
F954EC89F5D96AF46C360E3560A437D9
F1CC3ACADB379C7D0FD95E2C3F5F5C77
B023CCFB6BCD72381DAC137172C038DB
22D14E54802D9BC0721737A58926C77D
FC1DCABE2E461BB6431A82A22FF9A4FE
Максимальный из них такой:
FC1DCABE2E461BB6431A82A22FF9A4FE
Это и есть хэш уровня.
Правила сравнения:
Если уровни равны, то и хэши равны.
Если уровни разные, то и хэши будут разные.
Ну есть вероятность коллизии хэшей (уровни разные, хэш одинаков), но она 2-128 (примерно 3*10-39), т.е. пренебрежимо мала.
Устойчивость хэша к модификации уровня:
1) Если уровень вращать или отражать, на шаге 9 всега будет выбираться один и тот же максимальный хэш.
2) Если перемещать место старта (не перебрасывая его через ящики), то на шаге 4 всё равно получится один и тот же результат.
3) Если добавить лишние стены, пустоты и даже ящики вне досягаемости от старта - они зальются стенами на шаге 2 и отрежутся на шаге 3.
4) А вот если стартовую точку перебросить через ящики, или если добавить ящики/стены/цели/пустоты в досягаемости от старта - хэш уровня станет другим.
Почти идентичный алгоритм описан на странице игры Sokoban от Bjorn Kallmark:
http://sourcecode.se/sokoban/level_id.php
Однако там алгоритм не содержит шага 4, поэтому не находит некоторые дубликаты.
Натравив мой алгоритм на коллекцию уровней на сайте Kallmark-а, я обнаружил 63 уровня, которые повторяются, причём некоторые - более одного раза.
Большая часть дубликатов несущественна (наборы Boxxle частично заимствованы из Classic, в сборнике Loma использованы уровни из других наборов, есть несколько повторений в пределах одного набора из-за невнимательности авторов, и т.п.)
Однако 11 уровней дублируются у разных авторов независимо.
В частности, один из уровней обнаружился 6 раз:
- Choriban.slc, уровни 26 и 34
- HomzLevels.slc, уровни 8 и 177
- Novoban.slc, уровень 40
- Pufiban.slc, уровень 126
Теперь есть возможность для моей игры SokobanCompact более грамотно составить коллекцию уровней.
P.S. Напишу Kallmark-у, посмотрим, что скажет.