Кодирование сети дорог на карте

[Andrew771]

Подскажите какие-нибудь идеи экономичного кодирования и хранения сетей дорог на карте местности максимум 256х256 клеток. Не связанных друг с другом сетей может быть несколько. Быстродействие не важно.

Вот способы, которые на ум пришли:

1. Самое простое - две координаты каждой клетки дороги. Очень затратно по памяти. Итого 2n байт.

2. Базовая клетка - две координаты. Соседние клетки одной сети кодируются смещениями от базовой клетки, от 1 до 16 по вертикали и горизонтали - 1 байт на клетку. Если сеть больше 16х16, то заводим новую базовую клетку. Итого примерно 1.1n байт.

3. Базовая клетка - две координаты. Соседние клетки одной сети кодируются направлениями от базовой клетки - вверх, вниз, влево, вправо - 2 бита на клетку. Плюс какая-то часть памяти на указание соседства. Очень геморный кодировщик и раскодировщик. Итого примерно 0.4n байт.

Может есть еще что-то из теории графов? :)

[alone]

Каждая дорога - запись вида
(число отрезков, X0, Y0, направление1, длина1, направление2, длина2, ... направлениеN, длинаN)

[Andrew771]

Каждая дорога - запись вида
(число отрезков, X0, Y0, направление1, длина1, направление2, длина2, ... направлениеN, длинаN)
Отлично!
А если сеть разветвленная, как в игре Civilization, то базовых точек X0,Y0 очень много будет. Нужно подумать, как сократить.

[Antipod]

Нужно подумать, как сократить.
Тогда с разбегу на ум приходит:

struct Node{
uint8_t _x;
uint8_t _y;
};

// массив всех точек
Node allNodes[256]; // 256 - максимум

// одна дорога
struct Road{
uint8_t _len; // длина дороги в узлах
uint8_t* _indexes; // массив индексов для allNodes
};

[Andrew771]

Тогда с разбегу на ум приходит
По-моему, это даже больше места займет, чем у Alone.

Если конкретно для Цивилизации, то появилась идея - сначала отметить клетки только суши, а затем для них кодировать дороги обычным способом - по 2 бита на клетку (3 типа дорог и отсутствие). Если, к примеру, суша на карте занимает 40%, то для карты 256х192 это займет 256*192*0.40/4 = 4916 байт. Саму карту (леса, луга, горы) планирую кодировать налагающимися друг на друга прямоугольниками разного размера, 400 штук по 3 байта (верт.координата, гориз.координата, длина 4 бита/ширина 4 бита) = 1200 байт. Где нет прямоугольников на карте - это океан. Вот тут пример: http://zx.pk.ru/showpost.php?p=376027&postcount=63
Как-то так. Оптимальнее пока не придумал :)

[Antipod]

Если конкретно для Цивилизации
Приведенный пример допускал создание натурально "сетки" дорог и экономил место удаляя дубликаты точек ( перекрестки ).

Изображения на "Цивилизацю" нагуглил.
Возможно подразумевается, что дороги сгибаются только под прямыми углами и расположены только вертикально и горизонтально, в этом случае мона заюзать тупо битмапину, 1 - есть дорога, 0 - нет дороги. Для 256х256 займет 8кб. И при выводе нужно будет подключить некую логику, которая будет детектить перекрестки.

[Andrew771]

Приведенный пример допускал создание натурально "сетки" дорог и экономил место удаляя дубликаты точек ( перекрестки ).
Сложновато будет при добавлении новой клетки с дорогой. И неэкономично всё-таки.


Изображения на "Цивилизацю" нагуглил.
Возможно подразумевается, что дороги сгибаются только под прямыми углами и расположены только вертикально и горизонтально, в этом случае мона заюзать тупо битмапину, 1 - есть дорога, 0 - нет дороги. Для 256х256 займет 8кб. И при выводе нужно будет подключить некую логику, которая будет детектить перекрестки.
Ну если битмап, то можно во все 8 сторон изгибать (дорога толщиной в пиксель). Причем битмап только для суши (40% от карты), т.к. на море дорог нет. А два бита, т.к. предполагается три типа дорог - грунтовая, асфальтированная и железная дорога.

Получается, что когда мало дорог, выгодно хранить сетку. А когда много - битмап. :)