Разработка findcolor, findimage, Pure lua Опции

[DarkMaster]

эммм... я тебе отвечал по моим финдам... тема вроде как про них)
пилот будет искать в области 10 10 19 19 +/- размер паттерна. +/- естественно в сторону увеличения области. раньше он искал так, потом продолжил искать так же, но результаты начали фильтроватсья выкидывая найденые в полях (производительность на выкид). Потом подозреваю этот момент достаточно высокой вепроятностью мог быть корректно исправлен.

[Cockney]

Ну тема в целом не только по ним)

Так я вот и не понял, а как там корректно можно исправить этот выкид ? Постоянно на каждом шаге проверять выходим или нет за зону поиска ?

[DarkMaster]

Постоянно на каждом шаге проверять выходим или нет за зону поиска ?

а просто искать в адекватной области не?) изменить начало и конец диапазона. Если в рамках пилота, как пользователя - ничего особо не сделаешь. Можешь попробовать изначально задавать меньше область.

[Cockney]

Что в твоем понимании искать в адекватной области ? Предположим, паттерн 10х10 может быть найден в самом начале области поиска 0,0,10,10 по последним 3 пикселям. Точность и прочее не рассматриваем. Вот как мне начать сравнивать начало области поиска [0,0;0,0;0,0] с куском паттерна [9,7;9,8;9,9] ?

[DarkMaster]

если в рамках пилота и стандартных функций - дерни гетимиджем, потом внутри ищи. избавит от проблем. хот фикс не работает или не устраивает? который кривой.

[Cockney]

Блин, наверное не могу с первого раза доносить смысл... нет, меня интересует строго алгоритм без привязки к реализации. И мне интересно как можно находить паттерны, НАЧАЛО которых лежит ЗА областью поиска, а в самой области поиска находится 3-5 пикселей или того меньше, при этом производительность не должна улетать в помойку из-за постоянных проверок выхода за область. Например, cirus, страниц 5-6 назад находил такие кейсы, собственно поэтому ты мне там и пытался объяснить как якобы это в пилоте работает (работало).

если там алгоритм такой: ищем в паттерне первый пиксель который подходит, и только потом продолжаем сравнивать остальные, то мне понятна механика такая, НО мне не понятно как такое работает, если там потенциально могут большие куски пропускаться без проверок из-за какого-то смещения на 1 пиксель.

[DarkMaster]

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

[Cockney]

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

конкретно в пилоте - все утекает

т.е. много ситуаций, когда должен был найти, но не нашел ?

просто разбивал паттерн на саб паттерны, которые искались бы исключительно внутри области

что это дает ? условно, делить паттерн на 4 части, и искать только те, которые влезают в область ? ну это можно и так сделать, без какой то разбивки.

[DarkMaster]

без какой то разбивки.

можно, но на математике указателей будет просадка, плюс у тебя чтение будет не оптимизировано.

т.е. много ситуаций, когда должен был найти, но не нашел ?

в пилоте утекает производительность за счет попыток поиска на полях.

что это дает ?

сколько раз ты будешь считать смещения? Ну вот скажем ты пошел обрабатывать верхнее поле. И у тебя нужно каждый раз вворачивать доп математику указателя. Ищем мы пусть в фулл хд, паттерн 10х10 пикселей, точность позволяет сделать 3 пикселя на вертикальном поле. Т.е. нам нужно будет каждый канал, каждый пиксель считать при этом со смещением.
1920*10(ширина)*3(каналы)*1(самое верхнее положение паттерна, только один пискель может быть ошибочным)
+
1920*10(ширина)*3(каналы)*11(забег на поле 2 линии)
+
1920*10(ширина)*3(каналы)*21
И все это будет считаться каждый раз. Зачем? Причем это идеальный случай, когда у нас вообще ничего нигде не совпадает и поиск сразу переходит к следующей позиции. А если оно будет срываться на последнем пикселе? У нас просадка будет очень существенной. Я этими тестами занимался три месяца. Так делать короче не нужно)

По поводу не найдет - тут есть фатальный баг. Хз как он пролез, но если не будет найден самый редкий пиксель на паттерне - то поиск ничего не найдет. Это катастрофа. Обнаружилось с год назад. Т.е. как правило если второй слева верхний пиксель не найден, то изображение вообще не будет найдено. Отсюда и пушечная скорость ибо он огромный кусок проверок просто выкидывает. Я видел исходник финдимиджа. Там много заморочек и оптимизаций. Практически все из них я перепробовал при создании своего аналога. Ирония в том, что эти оптимизации должны работать по логике, на практике очень много вопросов. Так же часть из них отсеялась математически из-за сильного перекоса вероятностей. Личено я пришел к тому, что сам поиск должен быть максимально примитивен и предсказуем для предвыборки процессора. Кстати а есть какие-нибудь способы сказать компилятору "вот это держи в регистрах проца"? Все остальные оптимизации - это кэш паттернов (прирост примерно в 10 раз, если НЕ ssd), уход к самостоятельному менеджменту памяти без free и malloc при каждом вызове.

[Cockney]

чтение будет не оптимизировано.

это широкий вопрос, нужно по факту смотреть как читается куда и что, в общем случае идеальное чтение э то линейный проход по памяти.

1920*10(ширина)*3(каналы)*1

я делал математику без делений / умножений, считать там не так много на самом деле. но т.к. у меня в целом алгоритм кривой - я не замерял скорость на такой математике.

если не будет найден самый редкий пиксель на паттерне - то поиск ничего не найдет. Это катастрофа. Обнаружилось с год назад. Т.е. как правило если второй слева верхний пиксель не найден, то изображение вообще не будет найдено.

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

Я видел исходник финдимиджа.

пошарить возможно, или гриф секретности ?

Личено я пришел к тому, что сам поиск должен быть максимально примитивен и предсказуем для предвыборки процессора

это не всегда работает, т.к. есть ассимптотическая сложность. если тебе физически возможно перелопатить в 3-4 раза меньше данных чем обычно, то там все равно на кеш процессора и прочее - скорость будет выше, если не брать какие-нибудь пограничные случаи.

Кстати а есть какие-нибудь способы сказать компилятору "вот это держи в регистрах проца"?

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

[DarkMaster]

это широкий вопрос, нужно по факту смотреть как читается куда и что, в общем случае идеальное чтение э то линейный проход по памяти.

да, но в общем случае у нас будет, как раз разрыв линейности если мы используем некторый субпаттерн по средствам указателей.

я не замерял скорость на такой математике.

я замерял. Не надо так делать.

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

Если все цвета уникальные либо повторяются одинаковое количество раз - второй пиксель. А вообще самый редкий. Просте если редких несколько, то счтаем слева-направо, сверху-вниз. Какой попался первым тот и будет критическим.

пошарить возможно, или гриф секретности ?

Не уверен, что он у меня есть с собой. Я не в россии и без разрешения кнайта я шарить не буду. Чужое я не трогаю - решать не мне.

это не всегда работает, т.к. есть ассимптотическая сложность. если тебе физически возможно перелопатить в 3-4 раза меньше данных чем обычно, то там все равно на кеш процессора и прочее - скорость будет выше, если не брать какие-нибудь пограничные случаи.

Согласен, но мои соображения привели к тому, что лучше получить некторое усреднение работы, чем те перекосы по скорости которые могли быть. Условно говоря я не хочу получать 2x скорость в 50%, если в остальных 50% случаев будет 0.5х, а эти случаи еще и наиболее медленные в силу заданных точности/девийшена/размеров. Т.е. можно получить пушку на примитивных случаях и тормоз на и без того сложных и медленных. Да это зависит от ситуации, но поведение должно быть прогнозируемым и простой поиск он и без того будет достаточно быстрым, чтобы не вызвать проблем, а вот медленные моменты нужно ускорять.

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

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

Сообщение отредактировал DarkMaster - 22.12.2023, 20:22

[Cockney]

да, но в общем случае у нас будет, как раз разрыв линейности если мы используем некторый субпаттерн по средствам указателей.

он будет в любом случае, т.к. паттерн (минимум он) ходит туда-сюда

я замерял. Не надо так делать.

лично у меня это пара сложений и иногда один-два минуса. это не може быть медленней умножения/деления (за исключением умножения на степень 2, наверное)

[DarkMaster]

он будет в любом случае, т.к. паттерн (минимум он) ходит туда-сюда

и да и нет. паттерн как раз таки самый линейный в плане чтения. даже когда мы переходим на следующую линию по вертикали, мы все так же линейно его читаем. Да, на каждой новой позиции мы начинаем читать с начала, но линейно. Скрин же на каждой новой линии рвется линейность чтения. Это дает сильный эффект. Если же мы паттерн начинаем обрабатывать указателями, как сабпаттерны, то вся линейность (для каждой позиции) будет рваться при новой линии сабпаттерна. Т.е. получим тоже самое, что на скрине.

лично у меня это пара сложений и иногда один-два минуса. это не може быть медленней умножения/деления (за исключением умножения на степень 2, наверное)

ну у меня тоже их нет. точнее нет в поиске. в конверторе есть умножение, которе компилятор вычисляет ровно один раз ибо *restrict. Уверенности не было, что рабоатет, так, как должно, но тесты показали, что он реально не пресчитывает это значение. А ну и на степень двойки умножаю. Так что все красиво относительно. Вопрос не в том, что их не много, а в том, что они есть. И когда у нас большие зоны поиска, большой паттерн, низкая точность, то эти ничтожные пару +/- дают эффект. Естественно это не лютый слив производительности, но он вполне детектируемый на тестах.

[Иллидан]

а как в таком поиске одинаковой картинки, указать минимальный размер картинки, чтобы небыло ложных кликов, ближе друг к другу, чем размер искомой картинки?

Код

set #a findimage (0 0 1600 900 (Scripts\Screens/1.bmp) %arr 2 75 -1 25)
set #w size (%arr) // получим число найденных картинок
msg Найдено картинок: #w
//hint Найдено картинок: #w
for #i 1 #w
    set #x %arr [#i 1]+5
    set #y %arr [#i 2]+5
    move #x #y     // переместить курсор на найденную картинку
    hint картинка в координатах: #x #y
end_for

[nykep]

а как в таком поиске одинаковой картинки, указать минимальный размер картинки, чтобы небыло ложных кликов, ближе друг к другу, чем размер искомой картинки?

ничего не понятно

[Иллидан]

ничего не понятно

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

тоесть надо както задать размер искомой области, шобы за найденную единицу щиталась эта 1 область, например если картинка 30х30 пикселей

[DarkMaster]

25 очень много

[Иллидан]

25 очень много

для постоянно изменяющейся анимированной картинки?
Мне тоже показалось что много, но зато работает, иных же способов искать динамичные объекты вроде нету, а этот находит все, но и ложные(поверх/в том же месте найденной картинки) тоже (IMG:style_emoticons/default/sad.gif)

несколько лет назад, в другом кликере, такая проблема была решена с помощью добавления границ тела поиска, по которым все найденные одинаковые объекты, в указанном x y радиусе от каждого, считались за 1 объект, чтобы не тыкать в том же самом месте несколько раз(со смещением на 1 или пару пикселей, но всё ещё внутри 1 уже тыкнутого объекта), теперь такое надо и в уопилоте как-то воссоздать (IMG:style_emoticons/default/rolleyes.gif)

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

[nykep]

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

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

[Иллидан]

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

в моём случае, на экране примерно 30 анимированных полупрозрачных картинок одинаковой формы и размера, на разном статичном фоне и после нажатий они просто становятся статичными, а не пропадают, по этому так искать врятле получится (IMG:style_emoticons/default/laugh.gif)