Неявное представление графа
Вначале, мы хотели бы обработатывать все ячейки в одинаковой степени. Следовательно, надо что-то сделать с 'отсутствующими' гранями на границах карты. Их удобно обработать при помощи, добавления отсутствующих граней в направлении за карту и установке издержки этих грани в ¥.
Специальный модификатор можно реализовать в функции стоимости, чтобы учесть это.Все ячейки/вершины теперь имеют точно ту же самую структуру, если обеспечено, что никогда не совершается 'переход' по грани с бесконечной стоимостью грани. Мы знаем то, какие грани имеются, без необходимости явно кодировать это для каждой ячейки (см. рисунок 5). Ячейки сами по себе не представляют никакого интереса; они представлены только стоимостью грани, о которой мы заботимся при определении общей стоимости пути. Однако, мы видели в предыдущих разделах, что все модификаторы стоимости грани - функции свойств грани ячеек источника и адресата. Давайте называть эти свойства для ячейки 'атрибутами', сохранять их в структуре CellAttr и определим массив, где мы сохраняем все атрибуты ячейки, по одному атрибуту для каждой вершины ячейки.
На каждую ячейку ссылаются двумерным индексом, CellRef, в этом массиве. Все, что необходимо знать для того чтобы пройти по грани от любой ячейки до другой - то, как этот как (двумерный) индекс должен быть изменен. Давайте определим номер грани по направлению по часовой стрелке от 0 до 7 (0 - Север, 1 - Северо-Восток, 2 - Восток, 3 - Юго-Восток, и так далее). Затем просто вычислим изменение индекса и сохраним это в справочной таблице, crWalkEdgeDelta[8]. Для прохода по грани, с направлением ed, все, что мы должны cделать затем 'добавлять' crWalkEdgeDelta[ed] к CellRef исходной ячейки.
5.2.2