Spiiin's blog

Еще одна оставшаяся нерешенной задачка из мира старых игр - алгоритм выбора пути между уровнями в Adventure Island 2.

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

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

Поиск дал немного полезной информации - на сайте у cah4e3’а нашёлся код на выбор уровня и game-genie код для перевода игры в дебаг режим. Из него доступны - выбор любой зоны, мира, бессмертие, тест звуков и предметов.

По номерам уровня можно расчерчить карту всех участков и составить планы уровней.

00-0F - горы (обычные, снежные, вулканы)
10-17 - джунгли(обычные и снежные)
18-1F - озера
20-2F - пещеры(обычные, темные и заснеженные)
30-3A - леса(обычные, закатные, морозные)
3B - логово последнего босса
3C-3F - леса
40-41 - ночные джунгли
42-43 - пики гор
44-47 - горные озёра
48-49 - ледяные пещеры
4A-4B - пустыня
4C-4D - облака
4E - логово 2-го босса
4F - вулканы
50-57 - боссы

Визуальным поиском по оперативной памяти номеров уровней в комнате бонусов можно найти, что все они располагаются в диапазоне 3E0-3FF - “мапа” уровня вперемежку с пустыми байтами. Если поменять эти байты и исследовать поведение игры, то выяснится: - Пройденная зона отмечается байтом F0, причем иногда в мапе уровня изначально присутствуют такие байты, что наводит на мысль о существовании коридоров, через которые можно ускоряться. - Если проиграть боссу, то он перемещается в свободную зону. Но, если свободных зон уже не осталось, остается в той же. Босс движется по тому же алгоритму, что и игрок. - Обычно из каждого уровня можно перейти в один из двух возможных, но бывают и исключения. Тут стоит прекратить гадание и поставить в отладчике точку остановки на запись в диапазоне памяти 3E0-3FF. 4. Остановка срабатывает по адресу: F682: LDA #$F0, STA $03E0,X В X текущая координата, относительно мапы уровней. Ячейка памяти, из которой считывается это смещение - D1.

Дизассемблированная процедура выбора: https://gist.github.com/3814486

Описание алгоритма: Берём номер яйца с бонусом в конце уровня, пытаемся перейти последовательно по одному из 8 вариантов, соотвествующих этому яйцу и прописанных в таблице переходов в ROM, по порядку (доступные смещения переходов +1,+7,+8,+9, -1,-7,-8,-9, то есть сместиться можно либо в соседний участок на острове, либо в один из дальних). Если не выходит (участок пустой или пройденный), то пытаемся хотя бы сменить уровень на тот, что уже был пройден и повторить процедуру поиска следующего уровня сначала. Если с 4х раз не получилось, берем последний доступный уровень с конца мапы. Если же все уровни пройдены, остаемся в том же.

Мапы всех островов.

1. FF FF FF FF FF FF FF FF FF FF FF 36 41 FF FF FF FF 00 20 F0 40 FF FF FF 15 37 F0 18 2A FF FF FF (начало - 15, конец - 41)
2. FF 4E 1A 2C FF FF FF FF FF 01 23 31 FF FF FF FF FF FF FF FF 19 FF FF FF FF FF 14 30 FF FF FF FF (начало - 14, конец - 4E)
3. FF FF FF 4A 4B FF FF FF FF FF 33 FF FF 02 03 FF FF FF FF 10 13 FF FF FF FF FF FF 21 3D FF FF FF (начало - 3D, конец - 4A)
4. FF FF 48 FF FF FF FF FF FF 1E 43 17 FF FF FF FF 27 FF FF FF 3F FF FF FF FF 3E 08 09 FF FF FF FF (начало - 08, конец - 48)
5. 2E 46 45 2B FF FF FF FF 22 07 06 11 FF FF FF FF 32 FF FF 1C FF FF FF FF FF 24 FF FF FF FF FF FF (начало - 24, конец - 46)
6. 4D FF FF FF FF FF FF FF 2D FF FF FF 35 FF FF FF 3A 05 FF FF 1D FF FF FF 25 16 4C 04 FF FF FF FF (начало - 35, конец - 4D)
7. 4F FF FF FF FF FF FF FF 0E 0A FF FF FF FF FF FF 29 34 26 FF 0B FF FF FF 12 FF FF 3C FF FF FF FF (начало - 0B, конец - 4F)
8. FF 0C 0D 44 FF FF FF FF 2F 3B 1F 39 FF FF FF FF FF 0F 47 38 1B 49 FF FF FF FF FF 28 FF 42 FF FF (начало - 42, конец - 3B)
```

**Реверс алгоритма выбора пути и сравнение путей на питоне:** <https://gist.github.com/3814503> 

**Самые короткие и самые длинные дороги через острова:** номер означает участок, через который проходит игрок, а в скобках стоит номер яйца, необходимого для перемещения к следующему участку.

FERN ISLAND * остров содержит бонус-сокращалку, можно не сражаться с боссом
КОРОТКИЕ ПУТИ: 15 ->(0)-> 0 ->(0)-> 20 ->(0)-> 36 ->(0)-> 41 15 ->(3)-> 37 ->(4)-> 20 ->(0)-> 36 ->(0)-> 41
ДЛИННЫЕ ПУТЬ: 15 ->(0)-> 0 ->(0)-> 20 ->(0)-> 36 ->(2)-> 40 ->(2)-> 18 ->(0)-> 2A ->(0)-> 37 ->(0)-> 41

LAKE ISLAND
КОРОТКИЕ ПУТИ: 0X14 ->(0)-> 30 ->(0)-> 19 ->(0)-> 31 ->(1)-> 1A ->(1)-> 4E 0X14 ->(0)-> 30 ->(0)-> 19 ->(0)-> 31 ->(2)-> 23 ->(1)-> 4E
ДЛИННЫЙ ПУТЬ: 0X14 ->(0)-> 30 ->(0)-> 19 ->(0)-> 31 ->(0)-> 2C ->(0)-> 1A ->(3)-> 1 ->(4)-> 23 ->(0)-> 4E

DESERT ISLAND * остров содержит бонус-сокращалку, можно не сражаться с боссом
КОРОТКИЕ ПУТИ: 0X3D ->(1)-> 10 ->(0)-> 33 ->(0)-> 4A
ДЛИННЫЙ ПУТЬ: 0X3D ->(0)-> 13 ->(0)-> 2 ->(4)-> 3 ->(0)-> 21 ->(0)-> 10 ->(0)-> 33 ->(0)-> 4A

ICE ISLAND
КОРОТКИЕ ПУТИ: 0X8 ->(0)-> 9 ->(0)-> 3F ->(0)-> 17 ->(0)-> 48 0X8 ->(1)-> 3E ->(0)-> 27 ->(0)-> 1E ->(0)-> 48
ДЛИННЫЙ ПУТЬ: 0X8 ->(0)-> 9 ->(0)-> 3F ->(0)-> 17 ->(2)-> 43 ->(2)-> 1E ->(2)-> 27 ->(0)-> 3E ->(0)-> 48

CAVE ISLAND * остров содержит бонус-сокращалку, можно не сражаться с боссом
КОРОТКИЕ ПУТИ: 0X24 ->(0)-> 32 ->(0)-> 22 ->(7)-> 46 0X24 ->(0)-> 32 ->(4)-> 7 ->(0)-> 46
ДЛИННЫЙ ПУТЬ: 0X24 ->(0)-> 32 ->(0)-> 22 ->(0)-> 2E ->(2)-> 7 ->(4)-> 6 ->(0)-> 45 ->(0)-> 2B ->(0)-> 11 ->(0)-> 1C ->(0)-> 46

CLOUD ISLAND
КОРОТКИЕ ПУТИ: 0X35 ->(0)-> 1D ->(0)-> 4 ->(0)-> 4C ->(0)-> 5 ->(0)-> 2D ->(0)-> 4D
ДЛИННЫЙ ПУТЬ: 0X35 ->(0)-> 1D ->(0)-> 4 ->(0)-> 4C ->(0)-> 5 ->(0)-> 2D ->(3)-> 3A ->(0)-> 16 ->(0)-> 25 ->(0)-> 4D

VOLCANO ISLAND
КОРОТКИЕ ПУТИ: 0XB ->(0)-> 3C ->(0)-> 26 ->(0)-> A ->(0)-> 4F
ДЛИННЫЙ ПУТЬ: 0XB ->(0)-> 3C ->(0)-> 26 ->(0)-> A ->(2)-> E ->(3)-> 29 ->(0)-> 34 ->(0)-> 12 ->(0)-> 4F

DINOSAUR ISLAND
КОРОТКИЕ ПУТИ:
0X42 ->(1)-> 1B ->(0)-> 39 ->(1)-> D ->(3)-> 3B 0X42 ->(1)-> 1B ->(0)-> 39 ->(2)-> 1F ->(2)-> 3B
0X42 ->(1)-> 1B ->(0)-> 39 ->(3)-> 47 ->(1)-> 3B 0X42 ->(1)-> 1B ->(2)-> 38 ->(1)-> 1F ->(2)-> 3B
0X42 ->(1)-> 1B ->(2)-> 38 ->(2)-> 47 ->(1)-> 3B 0X42 ->(1)-> 1B ->(3)-> 28 ->(1)-> 47 ->(1)-> 3B

ДЛИННЫЙ ПУТЬ: 0X42 ->(0)-> 49 ->(0)-> 1B ->(0)-> 39 ->(0)-> 44 ->(0)-> D ->(0)-> C ->(0)-> 1F ->(4)-> 47 ->(4)-> 28 ->(0)-> 38 ->(0)-> F ->(1)-> 2F ->(0)-> 3B ```