lynn-lynn wrote:
>
> Ага, первый аргументированный ответ. Вот тут я с Вами полностью
> согласен. Да, я именно формочки + SQL умею и на них зарабатываю. В
> геймдев мне никогда не светит, там да — там надо алгоритмы колбасить.
> Только ведь из исходных постов было не ясно — куда же должен попасть
> человек со знанием графов. А мне на собеседованиях на роль MSSQL
> девелопера сортировки предлагали писать и списки реверсировать. Это —
> адекватно? Я должен дальше сидеть и с уважительным видом слушать этот
> бред из-за которого я пол Москвы проехал? В каждой избушке свои игрушки,
> но думать ведь надо о чем на собеседованиях спрашиваешь у человека и не
> надо думать что у всех вежливости хватит на то чтобы отсидеть пару часов
> двигая биты в байте, когда тебя берут отчеты в кристале рисовать.

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

Здравствуйте, Gorbatich, Вы писали:

G>Не советую копать в этом направлении. Лучше на что-нибудь боле полезное время потрать.

Всякие такие задачи оттачивают мышление. Кроме того, вроде простая задача, а если поглубже в ней разобраться, то можно усвоить много полезного.
Например у меня в подкорке сидело сомнение в целесообразности умножения, но я не обратил на это внимания и мне справедливо указали на то, чем может быть чреват такой подход.
Или опять же, если вернуться к задаче, то почему оптимальней сравнивать элементы массива тройками? Этому ведь есть простое объяснение.

Здравствуйте, Gorbatich, Вы писали:

Например...

1) Рендеринг.
Отсечение скрытих поверхностей.
Вся помощь, предоставляемая DX заключается в Z-buffer и CullFace. Но это только ОПТИМИЗАЦИЯ отбрасываня ненужных полигонов. Здесь нужно реализовывать такие вещи, как рендер посредством обхода (а в случае создания карт — разбиения) QuadTree(или OcTree), причём зачастую в каждом листе этого дерева реализуется алгоритм BSP+PVS. Или метод порталов, или много ещё чего.
2) Динамика.
а) Скелетная/морфическая анимация — Сплайновая и кватерионная интерполяция.
б) Обработка столкновений с последующей реакцией.
в) RagDoll(это когда трупики так, как надо падают )
3) AI
Ну, здесь, я думаю, даже не стоит ничего объяснять
4) GamePlay
Скриптовый интерпретатор.

Всё это нужно делать САМОМУ! Никакой поддержки со стороны DX или OGL. И это только капля в море геммороя, с которым приходится сталкиваться геймдеверам!

Ну дык что, пробуй матрицами реализовывать

Pzz>Так бы и сказали сразу, что Вы не программист. Конечно, человека Вашей
Pzz>профессии совершенно бессмысленно программистскими задачками
Pzz>тестировать. Для Вас надо какие-то другие тесты придумывать. Какие
Pzz>именно, не знаю, т.к. вашу профессию представляю себе очень
Pzz>приблизительно...

Черт его знает — какая у меня профессия. В дипломе — инженер-программист. В трудовой — программист-аналитик. В реале — рисую структуру базы со слов заказчика, потом делаю Web frontend'ы на ASP.NET'е к MSSQL, на основе собранных данных делаю OLAP кубы и строю по ним отчеты. До сих пор считал что программист, но байтики не crunch'ил уже лет 5 как

SZI>этого дерева реализуется алгоритм BSP+PVS. Или метод порталов, или много ещё чего.
Ну и где _сложная_ _математика_ в BSP алгоритме? Посчитать нормаль, скалярное и векторное произведения?
Имхо, математики тут особо нет, просто хорошо нужно понимать сам алгоритм.
SZI>2) Динамика.
SZI> а) Скелетная/морфическая анимация — Сплайновая и кватерионная интерполяция.
Операции с кватернионами (кстати, они есть в dx sdk) не сложнее операций с матрицами.
В сплайнах особой сложности не вижу.
К тому же все это (выгрузка анимации, и интерполяция ее) написано один раз, возможно, кем-то одним из разработчиков, остальные люди вряд ли знают все тонкости сплайновых преобразований.


SZI> б) Обработка столкновений с последующей реакцией.
SZI> в) RagDoll(это когда трупики так, как надо падают )
Часто используют соответствующие движки — от tokamak'а, например, до havok.

SZI> Скриптовый интерпретатор.
lua

SZI> Всё это нужно делать САМОМУ! Никакой поддержки со стороны DX или OGL.
Есть куча middleware.

Я вот тоже не понимаю, откуда эта шумиха о "сверхсложных алгоритмических задачах в геймдеве" — на многие вещи есть сторонние движки и библиотеки.
А если чего нет (или не могут купить), так такую работу делают 1-2 человека из команды разработчиков.
Или у вас в команде _каждый_ разработчик в состоянии написать скриптовый интерпретатор? Если да, то почему же зарплаты в геймдеве низкие и в массе своей черно-темно-серые?

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

Vogul wrote:
>
> Pzz>Условие в if'е больно уж умственное. Что-то спросонья я не могу понять,
> Pzz>чем это лучше чем if( a[i] < a[i+1] && a[i+1] > a[i+2] ).
>
> Дело в том, что при if( a[i] < a[i+1] && a[i+1] > a[i+2] ) будет
> накладней сохранять знак разности для проверок в случае учета плоских
> экстремумов.

Я примерно так и подумал.

> Да и смысл более полно раскрывается, как мне кажется.

Этого мне не понять!

> Pzz>Наверное, Вы математик...
>
> Физик и Делфист, поэтому в моем решении нет ни одного класса.

Однако переменную определяете в заголовке for-цикла. Т.е., ваши сишники
имеют расширение .cpp, а не .c

> Мда, простая задача, а сколько тонкостей. Надо срочно пересмотреть свое
> отношение к программированию.
> Век живи — век учись.

Почитайте Дейкстру, "Дисциплина Программирования". Если найдете...

Здравствуйте, ggg, Вы писали:

Тссс, чего раскричался-то? Сейчас геймдеверы услышат
Я говорю не о сложности/простоте математики в геймдеве, а о том, что не место там человеку, не имеющего соответствующего склада ума(как следствие, немогущему написать банальный алгоритм сортировки) — аналитического, математического, логического, называйте, как хотите.

ЗЫ А чего пропустил пункты AI, RagDoll("Часто" не в счёт ), обработка столкновений

Здравствуйте, Pzz, Вы писали:
>> Да и смысл более полно раскрывается, как мне кажется.

Pzz>Этого мне не понять!

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

Заметьте, что

a[i+1] — a[i] > 0 тождественно a[i] < a[i+1]

это как раз и поводит четкую математическую основу под решение задачи, а такая основа придает уверенность в правильности решения.

SZI> ЗЫ А чего пропустил пункты AI, RagDoll("Часто" не в счёт ), обработка столкновений
Читай внимательнее. Ragdoll и коллизии есть в моем посте.
Про AI — сильно от игры зависит.

SZI>> RagDoll("Часто" не в счёт ),
А почему это "часто" не в счет?
Еще раз. Если вы и пишете свою физику (не пользуясь ничем сторонним), то делает это явно не вся команда. Кто-то один (два) пишут, остальные просто пользуются.
Более того, в следующей игре вы уже просто будете использовать это ваше решение (ничуть не задумываясь о тензоре инерции).
В конечном итоге придете к тому, что многое можно взять из middleware, а не писать каждый раз с нуля Так что основная часть работы вовсе не разработка и реализация алгоритмов.
Физика, кстати, на уровне студента второго курса — тензор инерции, моменты, ускорения и т.д.

Здравствуйте, ggg, Вы писали:

SZI>>> RagDoll("Часто" не в счёт ),
ggg>А почему это "часто" не в счет?
ggg>Еще раз. Если вы и пишете свою физику (не пользуясь ничем сторонним), то делает это явно не вся команда. Кто-то один (два) пишут, остальные просто пользуются.
ggg>Более того, в следующей игре вы уже просто будете использовать это ваше решение (ничуть не задумываясь о тензоре инерции).

ggg>В конечном итоге придете к тому, что многое можно взять из middleware, а не писать каждый раз с нуля Так что основная часть работы вовсе не разработка и реализация алгоритмов.

Ну я же уже всё сказал...

ggg>Физика, кстати, на уровне студента второго курса — тензор инерции, моменты, ускорения и т.д.


ЗЫ Ну ведь согласись, не матрицами одними живём...

Здравствуйте, awod, Вы писали:
Простые задачки на графы и сортировки не могут решить!
Мне в моей работе практически ни разу не приходилось решать задачки на графыи сортировку. И я не смогук толком предложить решение этих задачек (не ставлю себе это в заслугу естественно). Хотя все их я безусловно проходил в университете, и писал простые программы реализующие такие алгоритмы. Но это не значит, что я не способен их понять и разобраться в них достаточно быстро. Все эти задачки решаются простым прочтением учебников и дальннейшей их реализацией. Как говорили в универе — наша цель не столько научить вас куче алгоритмов и т.п, а научить учиться и быстро находить решение.

Здравствуйте, Pzz, Вы писали:
Pzz>Мда. Вот с Вами я бы поговорил насчет возможного сотрудничества, если бы
Pzz>у меня были открытые вакансии...

Поздно. Как минимум в течении года я точно не буду менять работу в силу подписанного договора.
А вообще по поводу уточнения задания... Я просто достаточно с этим шишек набил. Не всегда творчество приносит пользу. При наличии неких разночтений всегда лучше уточнить у заказчика. Иначе потом придётся делать всё заново так, как ему это нравится.

Здравствуйте, A_l_e_x_e_y, Вы писали:

A__>Здравствуйте, Pzz, Вы писали:
Pzz>>Мда. Вот с Вами я бы поговорил насчет возможного сотрудничества, если бы
Pzz>>у меня были открытые вакансии...
A__>Поздно. Как минимум в течении года я точно не буду менять работу в силу подписанного договора.
В договоре написано, что ты не имеешь права уволится менее чем через год? Можешь игнорировать данный пункт договора как противоречящий законодательству РФ(Трудовой кодекс)
<skipped>.

Здравствуйте, LuciferMoscow, Вы писали:
Pzz>>>Мда. Вот с Вами я бы поговорил насчет возможного сотрудничества, если бы
Pzz>>>у меня были открытые вакансии...
A__>>Поздно. Как минимум в течении года я точно не буду менять работу в силу подписанного договора.
LM>В договоре написано, что ты не имеешь права уволится менее чем через год? Можешь игнорировать данный пункт договора как противоречящий законодательству РФ(Трудовой кодекс)

Нет. Ничего такого в договоре нет. Просто я подписался на квартирный кредит от конторы.

Здравствуйте, awod, Вы писали:

AS>>или найти быстрый и бесплатный... не ограничиваетесь рамками "медленный алгоритм" и "быстрый но дорогой" это сужает картину мира...

A>Быстрый и бесплатный, не всегда поддерживаемый.

Алгоритм Дейксты поддерживаемый? Или Кнута-Морриса-Пратта?

Здравствуйте, Pzz, Вы писали:

Pzz>vitaly_spb wrote:
>>
>> Pzz>Но вот простейшую задачку решить не смог. Мы его не взяли.
>>
>> А что за задачка?

Pzz>Подсчитать количество локальных максимумов в массиве целых чисел.
Pzz>Локальный максимум — такой элемент массива, который больше своих соседей.

А это че — на графы разве задачка?
Я б решил так

template<class TTPred,class TTIterator>
size_t countMaxes( TTIterator _start_it, TTIterator _end_it, const TTPred& _pred = TTPred() )
{
    size_t nCnt = 0;
    size_t nSize = std::distance( _start_it, _end_it );
    size_t nCurr = 0;
    assert( nSize >= 0 );
    TTIterator val_it = _start_it;
    TTIterator prev_it = val_it, next_it = val_it;
    if( nSize > 0 )
    {
        ++next_it; 
    }//if
    while( val_it != _end_it )
    {
        if( (val_it == prev_it || _pred( *val_it, *prev_it )) &&
            (val_it == next_it || _pred( *val_it, *next_it )))
        {
            ++nCnt;
        }//if
        ++val_it;
        if( nCurr == 0 ) ++prev_it;
        if( nCurr < nSize ) ++next_it;
        ++nCurr;
    }//while
    return nCnt;

}

int main(int argc, char* argv[])
{
    int val[] = {4,1,2,3,1,3,1,3};
    size_t result = countMaxes< std::greater<int> >( val, val + 8 );
    
    return 0;    
}

Здравствуйте, Gorbatich, Вы писали:

G>Здравствуйте, Anatolix, Вы писали:

A>>И что? Не спрашивали же про соседей справа и слева. A>подразумевается ВСЕХ соседей. Сосед 1.

G>Тут ясновидящих, телепатов и прочих медиумов нет. И кем же это подразумевается?

Это и без посторонней помощи видно глазами...

Vogul wrote:
>
> Pzz>Этого мне не понять!
>
> Ну как же! Первая производная в экстремуме меняет знак.

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

if( a[i-1] < a[i] && a[i] > a[i+1] ) ...

И далее совершенно естественно возникает вопрос о диапазоне i, в котором
определены a[i-1] и a[i+1].

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

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

> Заметьте, что
>
> a[i+1] — a[i] > 0 тождественно a[i] < a[i+1]
>
> это как раз и поводит четкую математическую основу под решение задачи, а
> такая основа придает уверенность в правильности решения.

Заметил, но для меня это совершеннейшая тавтология

Вы, кстати, никогда не смотрели в сторону функционального
программирования (Haskell, Ocaml, ...)? Посмотрите — Вам это должно
понравиться.