Перебор тайлов методом короеда :)

Форум для обсуждения деталей разработки программы SAS.Планета

Модераторы: vdemidov, Tolik

Re: Перебор тайлов методом короеда :)

Сообщение DJ VK » 20 окт 2010, 14:36

на твою багу ответ нашел.спираль n-го витка завершается в левом нижнем углу, и точка крайняя лежит уже не на n витке, а на n+1.
если взять вертикальную полосу 0,0 - 3,0 и точку (3,0) - для нее вообще нет ничего - все точки на n+1 витке.

решение
//---------------------------------------------------------------------------
bool __fastcall TTileIteratorAbstract::PointFound(void)
{
bool Found=false;
while(CurrentRadius<=MaxRadius+1 && !Found)
{
Found=Iterator();
if(DPhase==4)
{
DPhase=0;
CurrentRadius++;
if(CurrentRadius>MaxRadius+1) Ended=true;
}
if(Found) break;
}
Вложения
Koroed.rar
(223.36 KiB) Скачиваний: 82
Аватара пользователя
DJ VK
Гуру
 
Сообщения: 1467
Зарегистрирован: 16 апр 2009, 13:57
Откуда: 8 км. от МКАД
Благодарил (а): 82 раз.
Поблагодарили: 298 раз.

Re: Перебор тайлов методом короеда :)

Сообщение vdemidov » 20 окт 2010, 14:50

Вот теперь уже что-то похожее на правду. Можно и на делфу переводить :)
Чтобы понять программу, вы должны стать одновременно и машиной, и программой.
Аватара пользователя
vdemidov
Гуру
 
Сообщения: 1685
Зарегистрирован: 12 дек 2008, 13:10
Откуда: Киев
Благодарил (а): 191 раз.
Поблагодарили: 135 раз.

Re: Перебор тайлов методом короеда :)

Сообщение DJ VK » 20 окт 2010, 15:17

Короед 2. Работает в любую сторону (имеется выбор)
Вложения
Koroed.rar
(220.89 KiB) Скачиваний: 92
Аватара пользователя
DJ VK
Гуру
 
Сообщения: 1467
Зарегистрирован: 16 апр 2009, 13:57
Откуда: 8 км. от МКАД
Благодарил (а): 82 раз.
Поблагодарили: 298 раз.

Re: Перебор тайлов методом короеда :)

Сообщение Dima2000 » 03 апр 2012, 20:10

Скажите, а в последних версиях (после релиза 110418) не было ли обновления итератора? Что-то сейчас он стал явно тяготеть к правой стороне. До идиотизма доходит, когда правая половина экрана заполнена уже практически полностью, а левая - ни одного тайла. Такое впечатление сложилось после проверки глазками последовательности отображения, что центр экрана считается на 1 тайл правее реального. Раньше было правильнее.
Конкретнее, перебор идёт такой (координаты x,y=0,0 - центр экрана, перед проверкой экран отцентрирован в центр тайла): (1,0), (2,-1), (2,0), (2,1), (1,1), (0,1), (0,0), (0,-1), (1,-1), (2,-2), (3,-2), (3,-1), (3,0), (3,1), (3,2), (2,2), (1,2), (0,2), (-1,2), (-1,1), (-1,0), (-1,-1), (-1,-2), (0,-2), (1,-2), <пауза где-то на время 3-х тайлов>, (-2,2), (-2,1), (-2,0), (-2,-1), (-2,-2), (-3,2), (-3,-1), (-3,0), (-3,-1), (-3,-2).
Экран у меня 1680х1050, покрывается тайлами 7х5 с запасом. Видно что перебор смещён вправо на тайл. И непонятно с какой радости берётся пауза, ведь не отображаемые тайлы не должны проверяться, а тут похоже идёт проверка координаты (+4,..). И вот в момент когда заполнен тайл (0,2) практически половина экрана (правая) заполнена, а вся левая пустая. Некрасиво.
Оформлять это багом в багтрекере? Или это не баг, а так и задумано? ;)

И вдобавок пожелание сделать спираль не квадратной, а сплюснутой. В соотношении 4:3 или 16:9, смотря какой экран. А то сейчас тоже странно работает, сначала перебирает тайлы на границе экрана сверху/снизу, а слева/справа ещё есть пустые полностью помещающиеся на экран тайлы. Для экрана 7х5 (в тайлах) считаю более правильной последовательность (0,0), (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (2,-1), (2,0), (2,1), (-2,1), (-2,0), (-2,-1), (3,-1), (3,0), (3,1), (3,2), (2,2), (1,2), (0,2), (-1,2), (-2,2), (-3,2), (-3,1), (-3,0), (-3,-1), (-3,-2), (-2,-2), (-1,-2), (0,-2), (1,-2), (2,-2), (3,-2). Изменение в порядке обхода выделил жирным. Для других размеров экранов аналогично. Общую формулу думать лень, но если надо, напишу. Но учитывая размеры экранов, может вообще забить последовательность в виде массива смещений const int dxy[11*9]=(...) прям по цифрам выше? И в процедуре Next просто идти по индексу массива и проверять попадание результирующих координат в ограничивающий прямоугольник? Памяти полкилобайта не так уж и жалко ... Да, не универсально. Зато для существующих экранов сойдёт, да и модифицировать тривиально.
Dima2000
Соображающий
 
Сообщения: 70
Зарегистрирован: 01 апр 2012, 18:20
Откуда: Россия, Москва
Благодарил (а): 22 раз.
Поблагодарили: 5 раз.

Перебор тайлов методом сплюснутой спирали

Сообщение Dima2000 » 03 май 2012, 23:55

Не дождавшись реакции на вышенаписанное и благодаря помощи разработчиков в багтрекере (по другому поводу), порылся в исходнике Планеты и переписал класс спирального итератора точно взамен текущего, достаточно просто подменить один файл. Специально чтобы не вковыривать использование нового класса в 8 файлов его использующих. Спасибо garl, он пересобрал для проверки Планету с данным юнитом (бета версией), всё работает. Правда описанный выше глюк так и остался, заполнение начинается не от центрального тайла, а от смещённого вправо (и иногда вниз). Значит ошибка сидит где-то выше, не в самом итераторе, а в параметрах его вызова. Опишу её в багтрекере. (Added. Описал, посмотрим что скажут - http://sasgis.org/mantis/view.php?id=1288) Пока можно полечить прямо в классе сместив центр влево-вверх, но не хотелось бы, боюсь будет некрасиво на малых экранах.

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

А именно, предлагаю такой обход спирали (для региона 11*9 тайлов, экран 2560*2048 точек):
81_82_83_84_85_86_87_88_89_90_91
80_49_50_51_52_53_54_55_56_57_92
79_48_25_26_27_28_29_30_31_58_93
78_47_24_09_10_11_12_13_32_59_94
77_46_23_08_02_01_03_14_33_60_95
76_45_22_07_06_05_04_15_34_61_96
75_44_21_20_19_18_17_16_35_62_97
74_43_42_41_40_39_38_37_36_63_98
73_72_71_70_69_68_67_66_65_64_99
Отличия в первых трёх шагах, они делаются (0,0), (-1,0), (+1,0) от центра, а потом классическая раскрутка спирали вниз-влево-вверх-вправо и т.д. При таком обходе спираль получается сплюснутой и на широких экранах (не 4:3) быстрее заполняется центральная часть по горизонтали, спираль получается более приближенной к соотношению сторон экрана, визуально более красиво. :)
На обычных экранах разница не принципиальна (вот обход для 8*6 тайлов):
25_26_27_28_29_30_31_43
24_09_10_11_12_13_32_44
23_08_02_01_03_14_33_45
22_07_06_05_04_15_34_46
21_20_19_18_17_16_35_47
42_41_40_39_38_37_36_48

Added: Обновил версию итератора до v5, умеет строить и сплюснутые и квадратные спирали, даже многопоточно общую спираль. Реализует интерфейс ITileIterator.
Вложения
u_TileIteratorWideSpiralByRect_v5.zip
Спирально-квадратный итератор
(3.63 KiB) Скачиваний: 40
Последний раз редактировалось Dima2000 11 май 2012, 18:19, всего редактировалось 3 раз(а).
Dima2000
Соображающий
 
Сообщения: 70
Зарегистрирован: 01 апр 2012, 18:20
Откуда: Россия, Москва
Благодарил (а): 22 раз.
Поблагодарили: 5 раз.

Re: Перебор тайлов методом короеда :)

Сообщение Dima2000 » 08 май 2012, 19:50

Подумал, при таких крупных тайлах всё равно не слишком красиво заполнение начинается, слишком велика разница между двумя соседними тайлами (при сдвиге карты на пиксель-два). Полагаю для спирали должны соблюдаться следующие леммы:
1. Начало спирали всегда должно быть в том тайле, в который попал центр экрана (видимой области). Для чётных размеров, если две точки попали в разные тайлы, то см. п.2.
2. Первый шаг спирали должен делаться в направлении ближайшей границы тайла (для чётных размеров тайла она есть всегда, одна или две). Если ближайших границ две, то выбрать горизонтальную.
3. Все шаги спирали должны быть лишь в горизонтальных и вертикальных направлениях ровно на 1.
4. Раскрутка спирали по часовой стрелке. Совершенно не принципиально, можно и обратно, хотя "по" - имхо красивее.
Предлагаемый мною итератор в сплюснутом случае нарушает п.3 на первых 3-х шагах, специально для сплюснутости. "От короеда" тоже нарушает п.3 на шагах 2, 10, 27, ...
Пункты 1 и 2 вообще невозможно сделать лишь в итераторе, надо дополнительно что-то делать в вызывающем методе.
Жаль.

Вот бы вообще переделать вызов итератора, чтобы шёл не по текущему зуму, а по обсчитываемому (для карты заполнения) ... :) Будет красиво, но ещё тормознее.
Dima2000
Соображающий
 
Сообщения: 70
Зарегистрирован: 01 апр 2012, 18:20
Откуда: Россия, Москва
Благодарил (а): 22 раз.
Поблагодарили: 5 раз.

Re: Перебор тайлов методом сплюснутой спирали

Сообщение DJ VK » 09 май 2012, 08:16

Dima2000 писал(а):Не дождавшись реакции на вышенаписанное и благодаря помощи разработчиков в багтрекере (по другому поводу), порылся в исходнике Планеты и переписал класс спирального итератора точно взамен текущего, достаточно просто подменить один файл.

Dima2000 писал(а):Подумал, при таких крупных тайлах всё равно не слишком красиво

Если Вы не обратили внимание, там не один итератор, а несколько разных. Если вы хотите добавить свой, создайте его со своим именем (желательно похожим на геометрию ваших измышлений), а потом ищите как его подключить к остальным, если нужно. Вообще крайне не рекомендуется Править код поверх существующего, если функционал не добавится, а видоизменится. Вы же в другом порядке просто заполнять пытаетесь.
Возможно ускорит опубликование использование tortoise hg.

За это сообщение автора DJ VK поблагодарил:
zed (09 май 2012, 08:23)
Аватара пользователя
DJ VK
Гуру
 
Сообщения: 1467
Зарегистрирован: 16 апр 2009, 13:57
Откуда: 8 км. от МКАД
Благодарил (а): 82 раз.
Поблагодарили: 298 раз.

Re: Перебор тайлов методом короеда :)

Сообщение Dima2000 » 09 май 2012, 15:55

DJ VK писал(а):Если Вы не обратили внимание, там не один итератор, а несколько разных.
Не обратил, каюсь. Архив я собственно и не смотрел, копался в исходнике ночнушки.

DJ VK писал(а):крайне не рекомендуется Править код поверх существующего,
Согласен. Выше так сделал специально, чтобы попроще было встроить и проверить, заменить один файл проще исправления 8-ми других. По уму конечно надо новый класс. Который уж точно все поленятся встраивать... Поправил.
Dima2000
Соображающий
 
Сообщения: 70
Зарегистрирован: 01 апр 2012, 18:20
Откуда: Россия, Москва
Благодарил (а): 22 раз.
Поблагодарили: 5 раз.

Re: Перебор тайлов методом короеда :)

Сообщение zed » 09 май 2012, 17:24

Dima2000 писал(а):Который уж точно все поленятся встраивать...

Ну так, хочешь что-то сделать хорошо - сделай это сам.
Хитрости GoogleEarth - то, чего вы не знаете о гугле
Аватара пользователя
zed
Гуру
 
Сообщения: 2888
ICQ: 357167611
Зарегистрирован: 16 авг 2008, 20:21
Откуда: Беларусь, Могилёв
Благодарил (а): 89 раз.
Поблагодарили: 525 раз.

Пред.

Вернуться в Раздел для разработчиков программы SAS.Планета

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1