forum.boolean.name - Оптимизированный перебор Type'а

forum.boolean.name (http://forum.boolean.name/index.php)

- 3D-программирование (http://forum.boolean.name/forumdisplay.php?f=12)

- - Оптимизированный перебор Type'а (http://forum.boolean.name/showthread.php?t=16681)

Оптимизированный перебор Type'а

Обратил внимание что использование For Each с проверкой всех полей, при большом количестве записей начинает напрягать проц. Написал выход.

1. Обычный перебор (при 15к записей 1 кадр высчитавает 30-31 мс)

Код:

For grass.grass=Each grass

        grass\timer=grass\timer+time

        If grass\growed=False Then

        grass\scale=grassMaxScale*(grass\timer/Float(grassIntervalGrow))

        ScaleSprite grass\entity,grass\scale,grass\scale

        PositionEntity grass\entity,EntityX(grass\entity),grass\y+grass\scale,EntityZ(grass\entity)

        If grass\scale>grassMaxScale Then grass\growed=True 

        EndIf 

Next

2. Мой вариант перебора (при 15к записей 1 кадр высчитавает 16-17 мс)

Код:

Function GrassUpdate()

For grass.grass=Each grass

        grass\timer=grass\timer+time

Next 

End Function 



Function GrassCheck(n)

For i=1 To n

        If Not grassHandle Then

          grassHead.grass=First grass

          grassHandle=Handle(grassHead)

        Else

          grass.grass=Object.grass(grassHandle)

          If grass\growed=False Then

          grass\scale=grassMaxScale*(grass\timer/Float(grassIntervalGrow))

          ScaleSprite grass\entity,grass\scale,grass\scale

            PositionEntity grass\entity,EntityX(grass\entity),grass\y+grass\scale,EntityZ(grass\entity)

          If grass\scale>grassMaxScale Then grass\growed=True 

        EndIf 

        grass.grass=After grass

        grassHandle=Handle(grass)

        EndIf

Next 

End Function

В кратце смысл такой, если у вас будет несколько тысяч записей, то можно одной функцией применять изменения к "моментальным полям" всех записей (т.е. те поля, которые необходимо изменять каждый кадр), а остальные поля (которые не требуется проверять моментально) проверять в n-ом количестве, например не сразу 2000 записей за кадр, а по 100 записей.
Посмотрите пожалуста, у меня в другом коде этот метод не работает, хотя должно было работать после копи-паст.
Поделитесь какие тут недостатки

Прикреплены примеры

Ответ: Оптимизированный перебор Type'а

Визуально работают поразному, потому что трава не должна вырастать за 30 секунд :)

Ответ: Оптимизированный перебор Type'а

В твоем случае достаточно увеличить шаг роста травы в N раз и обновлять ее не каждый кадр, а раз в N кадров, тогда и общий FPS будет больше соответственно.
Ну и код оптимальнее пиши, как минимум в твоем случае:
- деление на float число заменять, по возможности, на умножение на обратное ему число.
- пользоваться Object только там, где это действительно необходимо. Некоторые думают что это работает так-же быстро как доступ к массиву, так вот это не так. Стоит знать что это поиск экземпляра по hash-map, который в лучшем случае имеет алгоритмическую сложность O(log N), а его реализация скорее всего это С++ый std::map, который основан на красно-черном дереве (т.е. при частом использовании получаем промахи кеша что дополнительно снижает быстродействие)

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

Ответ: Оптимизированный перебор Type'а

Я в таких ситуациях люблю 100%трави/фпс и апдейтить только некий процент травы за тик. И как я уже гдето постил, отличная статейка по списках, рекомендую!

Ответ: Оптимизированный перебор Type'а

Цитата:

Сообщение от Платон Александрович (Сообщение 226129)

- деление на float число заменять, по возможности, на умножение на обратное ему число.
- пользоваться Object только там, где это действительно необходимо. Некоторые думают что это работает так-же быстро как доступ к массиву, так вот это не так. Стоит знать что это поиск экземпляра по hash-map...

Ну если обратите внимание на код, то Object я использую только в том случае, если Handle() вернул ноль, а это происходит только при запуске и в конце цикла.

А про float я не понял, вы имеете ввиду использовать Integ*1.0?

Цитата:

Вы так коротко написали, не пойму, правильно подумал или нет. Т.е. как в моем коде менять N=countGrass/fps ??

А вот связанные списки для меня вообще темный лес пока ) Вообще путаюсь

Ну а так, что скажете по коду, нет косяков?

Ответ: Оптимизированный перебор Type'а

Цитата:

Сообщение от burovalex (Сообщение 226177)

Ну если обратите внимание на код, то Object я использую только в том случае, если Handle() вернул ноль, а это происходит только при запуске и в конце цикла.

В функции GrassCheck, 6 строчка

Код:

grass.grass=Object.grass(grassHandle)

и строчка 14

Код:

Handle(grass)

будут выполнятся "n - 1" раз

Цитата:

Сообщение от burovalex (Сообщение 226177)

А про float я не понял, вы имеете ввиду использовать Integ*1.0?

Я имею ввиду "X / Y" заменять на "X * Z", где Z - заранее расчитанная обратная величина от Y, т.е. "Z = 1.0 / Y".

Ответ: Оптимизированный перебор Type'а

Цитата:

Сообщение от burovalex (Сообщение 226177)

Вы так коротко написали, не пойму, правильно подумал или нет. Т.е. как в моем коде менять N=countGrass/fps ??

Я имел ввиду следующее. Есть у тебя 100 травинок. И есть у тебя 30 кадров в секунду.
100/30 = 3.3 В таком случае каждый кадр обновляешь не всю траву а 3.3 травинки. И ты равномерно на целую секунду распределишь всю нагрузку в обновлении травы. Даже в случае падения фпс. Только цифры эти я назвал теоретически, на практике у каждого они будут свои. просто возможно ты хочешь что б в секунду трава обновлялась не 1 раз а 3. Тогда 3.3 * 3 = примерно 10 травинок за раз апдейтишь. Таким образом ты избавишь комп от лишнего простоя. А если ты будешь апдейтить сразу всю траву раз в 1 секунду - будет скачок производительности. Короче не по программистски это ;)
Так что пробуй уже учись оптимизировать программы распределяя ресурсы процессора равномерно!

Ответ: Оптимизированный перебор Type'а

Цитата:

А если ты будешь апдейтить сразу всю траву раз в 1 секунду - будет скачок производительности.

Hulk-DS, если вы внимательнее посмотрите второй пример, то увидите что это и есть смысл заведённой темы )
Я именно так и сделал, что я не всю траву перебираю, а только n-ое её количество.
А на основной вопрос вы так и не ответили, нет ли тут косяков?

Платон Александрович

Цитата:

Я имею ввиду "X / Y" заменять на "X * Z", где Z - заранее расчитанная обратная величина от Y, т.е. "Z = 1.0 / Y".

Объясните пожалуйста, а чем будет отличаться
Z = 1.0 / Y
R=X*Y
от варианта (который я понял)
R=X/(Y*1.0)
? :4to:

Ответ: Оптимизированный перебор Type'а

Я не Платон, но влезу первый.
Смысл умножения на обратную величину в том, что умножение работает быстрее. Вместо деления на 2.0 можно использовать умножение на 0.5 - результат будет одинаковый, но умножение выполнится быстрее.

> Объясните пожалуйста, а чем будет отличаться
Z = 1.0 / Y <- это нужно делать "вне игрового цикла" (кавычки означают: бывает смена значения в цикле, но она по событию, т.е. пересчёт не в каждой итерации цикла)
R=X*Y <- это внутри цикла, только не Y там а Z должен быть, R=X*Z
> от варианта (который я понял)
R=X/(Y*1.0) <- Y*1.0 - бесполезная операция, делить и умножать на единицу нет надобности:)

Если в выражении у тебя в знаменателе идёт переменная, которая по ходу работы программы меняется, то смысла сначала делить 1.0 на эту переменную, а затем результат умножать на что-то - нет. Используй 1.0/X только в случае, когда Х хранит постоянное значение хотя бы какое-то время (потом при смене Х пересчитаешь заново Z=1.0/X и снова постоянное Z использовать будешь).

Ответ: Оптимизированный перебор Type'а

Цитата:

Сообщение от burovalex (Сообщение 226243)

Косяков тут хватает. Я не в курсе видел ли ты свой фпс.
Кроме того 2-го примера я не вижу я вижу один.
Если б ко мне пришел человек и спросил как правильно воткнуть юзб флешку в сетевой слот(там де коннектор), то по твоей логике я должен был б дать ему молоток.
Как парни уже тебе подметили - ты юзаешь на каждую травинку по отдельному ентити. Зачем мне тебе помогать делать неправильно? Делай не спрайтами делай все в одном меше/сурфейсе. Я прикрипил для изучения тебе аттач.
Заметь пару вещей:
1. Намного фпс выше.
2. трава не крутится вечно к камере и выглядит более естественно.
3. если ты в пределах функции введешь не 15к травинок а припустим 20к то вылетит Memory Acces Violation - ошибка, а она вылетит потому, что максимальное количество вершин(или треугольников, точно не помню) в одном сурфейсе перевышено. А 1 функция как там видно крепит все на 1 сурфейс. Поэтому следи за количеством трисов на меше.
Ну а так, учись сделать тоже что я тебе аттачнул, только чтоб трава генерировалась в некотором радиусе от игрока. Другими(образными) словами, не игрок бегает по полю с травой, а трава бегает за игроком по полю. Это не тупость - это оптимизация....

upd: Я сообразил где 2-й пример. Уже лень смотреть, но походу там тоже фпс маленький - значит тоже спрайтами.
п.с. Я может в своем примере натупил с синусами косинусами, но это ничего, если надо будет сам сможешь подумать и выправить.

Ответ: Оптимизированный перебор Type'а

И фпс не маленький - это пишется время на кадр (т.е. 16-17 норма) Может вы хапустили первый пример - где обычный перебор, который тормозит.
Да дело в том, что случайная генерация травы мне не подходит, т.к. трава должна рости и размножаться если в радиусе r свободное пространство.

Пример я посмотрел, и быстрее он работает только из-за того, что вы уменьшили размер травы с 52 кб до 8 кб., при 52 кб. в вашем примере тормозить начинает сразу, даже закомментировав 45000 и оставив 15000. Так что вы меня не убедили что лучше использовать сёрфы ) , НО пример очень хороший много для себя взял и смотрится конечно такая травка намного симпатичнее. Так что всё равно, спасибо!
Просто то что я сейчас делаю наоборот направлено на простоту.

Я только не понимаю, на счет сурфейса я понял что больше 20000 трианглов будет MAV, а вот почему со спрайтом после 17000 MAV выпрыгивает на строке RenderWorld? :4to:

И сразу еще один вопрос чтоб тему не создавать
Есть куча ентити, Можно ли как-нибудь проверить что рядом с определенным объектом есть свободное место, не перебирая все ентити??

Ответ: Оптимизированный перебор Type'а

Также пространство нужно кластеризовать, разбив на секторы, и списки держать в секторах. Таким образом не нужно будет перелистывать траву совсего участка x * y километров, а только сектора которые входят в обзор видимости. Таким образом можно держать сколько угодно травы, и её количество основанное на размере мира не будет влиять сильно на логику просчётов.

Ответ: Оптимизированный перебор Type'а

Цитата:

Сообщение от burovalex (Сообщение 226382)

И фпс не маленький - это пишется время на кадр (т.е. 16-17 норма) Может вы хапустили первый пример - где обычный перебор, который тормозит.

Может у тебя видеокарта за 3к баксов, но я не могу посмотреть в сторону травы без слайд шоу, и показатель 16-17 я даже не видел.

Цитата:

Сообщение от burovalex (Сообщение 226382)

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

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

Цитата:

Сообщение от burovalex (Сообщение 226382)

Пример я посмотрел, и быстрее он работает только из-за того, что вы уменьшили размер травы с 52 кб до 8 кб.,

А вот и нет. Он быстрее работает потому что я все травинки объеденил в один сурфейс(одну поверхность) в одной модели. Когда я применю MoveEntity GrussMesh[0],x,y,z - у меня переместится не одна травинка. А целое поле травы которое генерировала функция в которой указана модель GrussMesh[0], а это потому что целое поле - единый сурфейс, единая модель, единая поверхность. Не представляю как тебе это по другому объяснить. Пойми одно, твой метод со спрайтами - неправильный!!! Это тут тебе любой скажет.
п.с. я не размер файла с 52 кб до 8 кб. уменьшил. У тебя трава 512х512пикселей изображение. Для такой травы и 64х64 хватит. Но я сделал тогда 128х128.

Цитата:

Сообщение от burovalex (Сообщение 226382)

при 52 кб. в вашем примере тормозить начинает сразу, даже закомментировав 45000 и оставив 15000.

Ничего подобного. Если хочешь использовать свою огромную. Так оно и есть - это очень, нафик, ОГРОМНАЯ текстура травы, то сделай вместо моей текстуры:
Global GrassTex=LoadTexture("Grass.png",1+4+8+256)
Свою, но с другими циферками в конце:
Global GrassTex=LoadTexture("Grass1.png",1+4+8 )
И мой пример даже 120 000 травинок выдержит. Прикрепил в аттаче где пример с твоей текстурой и 120 тисяч травинок работают при 60 фпс. Стоко ФПСа тебе еще долго убивать твоей травой.

Цитата:

Сообщение от burovalex (Сообщение 226382)

Так что вы меня не убедили что лучше использовать сёрфы )

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

Цитата:

Сообщение от burovalex (Сообщение 226382)

НО пример очень хороший много для себя взял и смотрится конечно такая травка намного симпатичнее. Так что всё равно, спасибо!
Просто то что я сейчас делаю наоборот направлено на простоту.

Я не понимаю как первое предложение можна перечеркнуть третьим.
Зачем учится табуреткой забивать гвозди, если 99.999999999999% тебе это в жизни не пригодится. Трава спрайтами - это для меня выглядит как если человек отказываясь от молотка берет табуретку для забивания гвоздей.
Хотя я тебе скажу, когда я учился делал вещи и по ужасней :-D

Цитата:

Сообщение от burovalex (Сообщение 226382)

Я только не понимаю, на счет сурфейса я понял что больше 20000 трианглов будет MAV, а вот почему со спрайтом после 17000 MAV выпрыгивает на строке RenderWorld? :4to:

Я не скажу точной причины. Но 17тыщь моделей это перебор. В играх когда их 1тыщя - это уже мощная игра.

Я не "Вы" говори на меня - "Ты"

Ответ: Оптимизированный перебор Type'а

После твоего примера сложно остаться с прежним мнением )
Только мне твой пример

Цитата:

Global GrassTex=LoadTexture("Grass.png",1+4+8+256)
Свою, но с другими циферками в конце:
Global GrassTex=LoadTexture("Grass1.png",1+4+8 )

просто вынес моск )
Я всегда думал "если поместить текстуру в видеопамять - будет на 100% работать быстрее", теперь я понял что я ничего не понимаю :4to: Объясни пожалуста как так получается?

И на счет тормозов, я недавно переставил винду и запустил свой пример, он у меня очень тормозил (не понял в чем дело), потом установил блитц 1.99 и опять начал нормально идти )
И тестю я на буке с урезанным i3 и радик средненький :)

Ответ: Оптимизированный перебор Type'а

Цитата:

Сообщение от burovalex (Сообщение 226469)

После твоего примера сложно остаться с прежним мнением )
Только мне твой пример

просто вынес моск )
Я всегда думал "если поместить текстуру в видеопамять - будет на 100% работать быстрее", теперь я понял что я ничего не понимаю :4to: Объясни пожалуста как так получается?

Ну да ты прав, только вот, виде-память не безгранична, 765 метров это сильно!:-D
у тебя пара Сапфиров что-ли стоит