Важная информация

User Tag List

Показано с 1 по 7 из 7

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

  1. #1
    Veteran
    Регистрация
    29.12.2010
    Адрес
    Москва
    Сообщений
    1,497
    Благодарностей: 668
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию Кодирование сети дорог на карте

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

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

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

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

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

    Может есть еще что-то из теории графов?
    Формально всё правильно, а по существу - издевательство (В.И.Ленин)

  2. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  3. #2
    Guru
    Регистрация
    03.01.2006
    Адрес
    Рязань
    Сообщений
    2,935
    Благодарностей: 1071
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

  4. Этот пользователь поблагодарил alone за это полезное сообщение:
    Andrew771 (27.09.2011)

  5. #3
    Veteran
    Регистрация
    29.12.2010
    Адрес
    Москва
    Сообщений
    1,497
    Благодарностей: 668
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

  6. #4
    Member Аватар для Antipod
    Регистрация
    19.08.2008
    Адрес
    Украина, Львов
    Сообщений
    116
    Благодарностей: 10
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Нужно подумать, как сократить.
    Тогда с разбегу на ум приходит:
    Код:
    struct Node{
        uint8_t _x;
        uint8_t _y;
    };
    
    // массив всех точек
    Node allNodes[256]; // 256 - максимум
    
    // одна дорога
    struct Road{
        uint8_t _len; // длина дороги в узлах
        uint8_t* _indexes; // массив индексов для allNodes
    };
    Последний раз редактировалось Antipod; 03.10.2011 в 15:05.

  7. Этот пользователь поблагодарил Antipod за это полезное сообщение:
    Andrew771 (04.10.2011)

  8. #5
    Veteran
    Регистрация
    29.12.2010
    Адрес
    Москва
    Сообщений
    1,497
    Благодарностей: 668
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Antipod Посмотреть сообщение
    Тогда с разбегу на ум приходит
    По-моему, это даже больше места займет, чем у 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
    Как-то так. Оптимальнее пока не придумал
    Формально всё правильно, а по существу - издевательство (В.И.Ленин)

  9. #6
    Member Аватар для Antipod
    Регистрация
    19.08.2008
    Адрес
    Украина, Львов
    Сообщений
    116
    Благодарностей: 10
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

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

  10. #7
    Veteran
    Регистрация
    29.12.2010
    Адрес
    Москва
    Сообщений
    1,497
    Благодарностей: 668
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

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

    Получается, что когда мало дорог, выгодно хранить сетку. А когда много - битмап.
    Формально всё правильно, а по существу - издевательство (В.И.Ленин)

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Оптимальное LZ-кодирование
    от lvd в разделе Программирование
    Ответов: 66
    Последнее: 04.06.2014, 04:35
  2. "Пыль Звездных Дорог" demo
    от moroz1999 в разделе Игры
    Ответов: 10
    Последнее: 20.08.2006, 13:53
  3. Ответов: 13
    Последнее: 24.02.2005, 05:06

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •