Study & Dev | Blog Archive | Программируем трехмерную графику с Irrlicht . Часть 6

Программируем трехмерную графику с Irrlicht . Часть 6

August 6, 2007

Эффективное программирование 3d-приложений с помощью Irrlicht и jython. Часть 6

В прошлый раз мы начали изучение графических средств irrlicht. Пока мы ограничиваемся работой только с 2d-графикой, параллельно изучая на простых примерах особенности языка python|jython. В статье № 4 мы начали большой пример игры “угадай число”. Сегодня мы продолжим ее развивать с помощью пользовательских функций (udf – user defined functions).

Развивающее задание № 4. Что такое функция и как они позволяют нам писать более компактный и управляемый код, я уже говорил ранее. Ранее мы уже использовали стандартные функции python, например, прочитать строку, сгенерировать случайное число.

Теперь же надо попробовать создавать собственные функции. Вам нужно будет создать функцию get_random_number, которая будет служить для генерации начального случайного числа угадываемого пользователем. У этой функции входными параметрами будут числа A,B задающие диапазон. Кроме того, созданная вами функция не должна возвращать четные числа, а только нечетные. Момент в том, что нельзя при генерации случайного числа сказать, мол, хочу только четные или только нечетные.

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

Теперь рассмотрим еще примеры UDF функций.

```
import sys
```
```
import math
```
```
 
```
```
def factorial(n):
```
```
    if n <= 1:
```
```
        return 1
```
```
    else:
```
```
        return n*factorial(n - 1)
```
```
 
```
```
def my_pow (x, y):
```
```
    mult = 1.0
```
```
    i = 0
```
```
    while i < y:
```
```
        mult *= x
```
```
        i = 1 + i    
```
```
    return mult
```
```
 
```
```
def exponenta (x, delta):
```
```
    sum = 0
```
```
    i = 0
```
```
    while 1:
```

        step = my_pow (x, i) / factorial(i)

```
        sum += step
```
```
        if (step < delta):
```
```
            break
```
```
        i = 1 + i
```
```
    return sum
```
```
 
```
```
print exponenta (2, 0.001)
```

Здесь мы вводим несколько новых понятий. Цель данной программы, расчет значения функции exp(x), или чему равно число e в степени x. Разумеется, что в модуле math, который, кстати, мы подключили во второй строке, есть функция уже умеющая это делать. Например, так:

print exponenta (2, 0.001) - math.pow(math.e, 2)

Здесь я обратился к модулю math и в нем нашел константу e равную 2.718281828 (кстати, это число легко запомнить, так как в ней после 2.7 дважды идет дата рождения Л.Н.Толстого, но это к слову). А потом я вызвал функцию pow, которая получает два аргумента: первый из них - что будет возведено в некоторую степень, а второй аргумент – соответственно значение этой самой степени.

Мне все же, хочется вычислить значение данной функции с помощью следующей суммы:

exp(x) = 1 + x + x^2/2! + x^3/3! + …, и так далее. Эта сумма является бесконечной. И очередной ее член, под номером I (кстати, отсчет начинается от нуля) определяется как x в степени I разделить на значение функции факториал от I (записывается как i!). Раз сумма бесконечная то наш цикл по идее никогда не должен был бы закончиться, он все считал бы и считал, значение exp(x), все точнее и точнее, добавляя все более меньшие и меньшие доли в итоговую сумму.

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

Так,если очередной член добавляемый к сумме меньше чем, скажем, 0.0001, то и вся последующая сумма также не превысит это поправки. Следовательно, созданная мною функция exponenta (при объявлении функции вы используете ключевое слово def – от англ. definition - определение), должна получить два параметра: собственно значение x, и второе – точность вычислений - delta. Цикл будет прерван, как только эта delta окажется больше чем очередной член бесконечного суммируемого ряда.

Для расчета значения x^n я создал собственную функцию my_pow которая получает два аргумента (какое число, и в какую степень надо его возвести). Возведение в степень я проимитировал через последовательные умножения (такой способ, правда, не будет работать, если нужно возвести число в дробную степень, скажем 5^(3/4)). Главное что результат своего расчета функция должна вернуть в тот код, откуда она была вызвана с помощью оператора return.

Когда мы разрабатываем программы, то выделяем составные части - функции, по возможности максимально автономные и слабосвязанные между собой. Здесь я упоминаю об одном из правил разработки приложений, заключающийся в стремлении избежать зависимостей одной функции от косвенных результатов деятельности другой. Прямая взаимосвязь – это когда функция вызывает другую функцию и зависит только от того, что эта вызванная функция вернула с помощью оператора return. Косвенные зависимости сложнее в определении. Например, если функция для проведения своих расчетов создает файл “tmp.calc.dat”, то это можно посчитать за косвенные влияния на другие функции. Может файл под таким именем используется другой частью программы для хранения настроек или сведений профиля пользователя, а тут мы этот файл портим.

Функция factorial гораздо сложнее, в ней вводится понятие рекурсии. Любая подпрограмма (функция) может вызывать другую подпрограмму. Возникает вопрос: а может ли некоторая подпрограмма вызвать саму себя и что из этого получится. Подобный прием называется рекурсией, практически все языки программирования поддерживают ее. Более того, существует класс задач, которые не имеют решения без использования рекурсии. В качестве простейшего примера рекурсии из жизни: представьте, что перед человеком и после его поставили зеркало. Если человек посмотрит в переднее зеркало, то увидит в нем себя и, разумеется, зеркало сзади, в котором он увидит отражение снова себя и переднего зеркала, в котором он увидит снова отражение себя и отражение заднего зеркала в котором …. и так до бесконечности. Часто для демонстрации возможностей рекурсии используют такие математические объекты как факториал, цепные дроби. В качестве примера далее приводится пример кода рекурсивного и итеративного вычисления факториала:

Как известно из математики факториал числа N! = 1*2*3 … (N-1)*N. Но ведь если взять произведение всех чисел кроме последнего то мы получим формулу факториала, правда, уже для числа N-1. Итак: N! = 1*2*3 … (N-1)*N = (N-1)!*N.

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

Уровень	Описание и состояние переменных
0	Мы еще не вызывали рекурсивную функцию
1	Значение N=5, согласно заданному условию результатом значения 5!=5*4! Следовательно, нам необходимо сделать рекурсивный вызов с N=N-1.
2	Значение N=4, мы еще не дошли до ситуации, когда не требуется применение рекурсии и, следовательно, должны снова вызвать себя уже со значение N=3
3	N=3
4	N=2
5	N=1
6	N=0, ну наконец-то, рекурсивный спуск был завершен и мы знаем значение факториала при N=0, N! = 1. Теперь начинаем подъем.
5	При подъеме уровни рекурсии постепенно уменьшаются, пока мы не дойдем до 0. т.е. не вернемся в ту точку, откуда был сделан первый рекурсивный вызов. Мы возвращаемся из функции, и в качестве результата будет значение factorial = N*1. Здесь 1 – это результат, который мы получили с уровня 5. значение N=1. Следовательно, возвращается из функции значение 1.
4	Вычисляем текущее значение factorial = 2*1
3	Вычисляем текущее значение factorial = 3*2
2	Вычисляем текущее значение factorial = 4*6
1	Наконец, мы вернулись к первому вызову рекурсивной функции, таким образом, мы завершаем подъем и как результат получаем factorial = 5 * 24 = 120
0	Работа рекурсивной функции завершена: результатом 5!= 120

Когда я в таблице описывал спуск с постепенным нарастанием уровня, то остановился, когда N стало равным нулю. До этого мы определили, что значение 0!=1 по определению (значение факториала для отрицательных значений не определено). Отсюда есть очень важное следствие: рекурсия всегда имеет терминальную или конечную ветвь. Если мы об этом забудем, то получим нечто похожее на бесконечный цикл, который забирал все ресурсы машины и никогда не завершался сам, ведь вы действительно не хотите этого.

Когда стоит применять рекурсию? На этот вопрос есть очень простой ответ: по возможности никогда. Вот пример той же функции, но не рекурсивной, а использующий цикл:

```
def factorial_cicle (_n):
```
```
    if _n < 0:
```

        print 'N не может быть менее чем ноль'

```
        os.abort () 
```

        # вызов функции abort из модуля os аварийно завершает работу всей программы

```
    f = 1
```
```
    while _n > 1:
```
```
        f *= _n
```
```
        _n = _n - 1
```
```
    return f
```

Дело в том, что рекурсия всегда является с точки зрения вычислительных ресурсов слишком дорогой и в ряде ситуаций из-за этого просто не работает. В качестве демонстрации попробуйте запустить приведенные выше фрагменты кода для N = 1, 5 , 10 , 100 , 1000, 1000000. В то время как итеративный алгоритм работает и продолжает работать, выдавая все большие и большие числа, то рекурсия начиная с какого то шага завершается аварийно.

 Примечание: если бы вы запрограммировали этот же цикл на c|c++|Delphi, то, 
 начиная с некоторого шага, получался бы неверный результат из-за переполнения переменной F, 
 дело в том, что факториал – это очень быстрорастущая функция и 
 вскоре ее значение превышает предельные 2 миллиарда для целых чисел в с/с++/delphi. 
 В python, к счастью проблема переполнения не стоит так остро.

Далее, рекурсивная же версия применительно к c|c++ с некоторого момента начинает завершаться аварийно с сообщением “stack overflow” – переполнение стека или сообщением о попытке доступа к чужой памяти. Также учитывайте, что время вычисления в рекурсивной версии заметно больше, чем в итеративной. Тогда у вас должен возникнуть вопрос: а зачем нам нужен подобный инструмент? Да потому что рекурсия гораздо гибче, чем итерация, и я снова вам повторю, что есть такой класс задач, которые не имеют решения без использования рекурсии, или их решение слишком неэффективно.

Как проектировать рекурсивные алгоритмы? Да, это действительно сложный вопрос. Прежде всего, определитесь с самой задачей – какова ее природа.

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

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

Характеристика	Рекурсивное решение	Итеративное решение
Концепция	Что есть максимальный элемент в массиве? Пусть нам будет как будто очень сложно ответить на этот вопрос и поэтому мы ищем упрощение. Да тяжело найти максимальный среди N элементов, гораздо проще найти его среди (N-1) элементов, а затем сравнить это значение и первый элемент и определить кто же на самом деле наибольший. 1) Максимальный элемент в массиве из N элементов есть наибольший из первого и максимального элемента в хвосте массива (2..N) 2) (Это терминальная ветвь, она должна обязательно присутствовать). Очевидно что в массиве состоящем из одного элемента, этот элемент и будет максимальным.	Предположим, что MAX – максимальный элемент массива – пусть это будет его первый элемент (или второй, в общем любой). Переберем все оставшиеся элементы и для каждого из них проверим истинность первого предположения: может быть мы ошибались, и на самом деле некоторый текущий элемент A[i] более подходит на роль максимального: A[i]> MAX, если данное условие выполняется, то исправим нашу “ошибку”, положив: MAX = A [i]
Реализация	def max_rec (A): if (len (A) == 0): print 'array is empty' # в массиве нет элементов и понятие максимального элемента не определено os.abort () if (len (A) == 1): return A [0] max = max_rec (A [1:]) if max < A [0]: return A [0] else: return max print 'max rec = ' , max_rec ([1,2,4,6,7,2,5,9,0]) print 'max rec = ', max_rec ([]) A = [1,2,4,6,7,2,5,9,0];	max = A [0] i = 1 while i < len (A): if (max < A [i]): max = A [i] i = 1 + i print 'max = ', max
Замечания	Когда мы формулируем рекурсивный алгоритм, то больше внимания мы уделяем описанию характеристик того, что должно получится или как оно выглядит. Рекурсивный алгоритм сводится к самому себе, но всегда чуть более простому и близкому к моменту, когда для решения поставленной задачи рекурсия будет не нужна, решение будет тривиально и достижимо с помощью итерации или иного не рекурсивного приема (терминальная ветвь).	Здесь основной упор на определение четкой последовательности действий. Пройдя их от начала до конца, мы достигнем поставленной цели.

 Запись A [1:] означает, что из массива мы берем все элементы, 
 начиная с первого (нулевой элемент не берется) и подаем на вход 
 рекурсивной функции max_rec.

Рекурсия опасна тем, что вы можете забыть или неправильно сформулировать терминальное условие. Тогда рекурсивная функция будет вызывать сама себя, мгновенно пожирая ресурсы памяти и процессора. В общем случае можно ограничить глубину рекурсии некоторым числом. Разработчики python поступили очень грамотно, когда этот предел взаимных вызовов определили в виде настраиваемого числа. Итак, есть две функции в модуле sys:

getrecursionlimit() – эта функция возвращает число максимальной глубины рекурсии.

  setcheckinterval() – а эта функция устанавливает значение этого лимита.

Для иллюстрации схемы работы этих двух функций.

```
import sys
```
```
import os
```
```
 
```
```
def factorial_recursion(n):
```
```
    if n <= 1:
```
```
        return 1
```
```
    else:
```

        return n*factorial_recursion(n - 1)

```
 
```

print 'Лимит рекурсии сейчас' , sys.getrecursionlimit ()

```
print '5! = ', factorial_recursion (5)
```

sys.setrecursionlimit (4) # теперь мы устанавливаем предел вызовов в 4

```
print '5! = ', factorial_recursion (5)
```
```
 
```

А вот результат работы примера кода выше:

Лимит рекурсии сейчас 1000

```
5! =  120
```
```
5! = 
```
```
Traceback (most recent call last):
```

  File "f:\kolya\py\src\a10.py", line 27, in ?

    print '5! = ', factorial_recursion (5)

  File " f:\kolya\py\src\a10.py", line 20, in factorial_recursion

```
    return n*factorial_recursion(n - 1)
```

  File " f:\kolya\py\src\a10.py", line 20, in factorial_recursion

```
    return n*factorial_recursion(n - 1)
```

  File " f:\kolya\py\src\a10.py", line 20, in factorial_recursion

```
    return n*factorial_recursion(n - 1)
```

RuntimeError: maximum recursion depth exceeded

Для тренировки навыков работы в 2d попробуем нарисовать какую-нибудь замечательную кривую. Вот пример программы рисующей дерево Пифагора, в основе самоповторяющегося дерева лежат “те самые штаны которые …”. Почему я сказал “самоповторяющегося дерева”?

Построение дерева пифагора начинается с квадрата, у которого на одной из сторон размещен равнобедренный прямоугольный треугольник. Катеты этих треугольников равны и являются сторонами новых квадратов. И так фигура разрастается. Если же рисовать вместо квадратов линии, можно получать картинки, очень похожие на настоящие деревья. Что и делается в примере ниже.

```
import java
```
```
import math
```
```
 
```
```
import net.sf.jirr
```
```
from net.sf.jirr import dimension2di
```
```
from net.sf.jirr import position2di
```
```
from net.sf.jirr import recti
```
```
from net.sf.jirr import SColor
```
```
 
```
```
def lineto (x, y, len, u, _driver):
```

    _driver.draw2DLine (position2di (x,y),  position2di (int(x +len*math.cos(u) ), int(y - len*math.sin(u) )),

                       SColor (255, 0 , 0 , 0)

```
            )
```
```
 
```
```
def  pifagor (x, y, len, u, _driver):
```
```
    if (len > 3):
```
```
       len = 0.7 * len
```
```
       lineto (x, y, len, u, _driver)
```
```
       x  = int (x + len*math.cos (u))
```
```
       y  = int (y - len*math.sin (u))
```

       pifagor(x, y, len, u - math.pi/4, _driver)

       pifagor(x, y, len, u + math.pi/6, _driver)

```
 
```

java.lang.System.loadLibrary ('irrlicht_wrap')

```
device = net.sf.jirr.Jirr.createDevice(
```

        net.sf.jirr.E_DRIVER_TYPE.EDT_DIRECT3D9, dimension2di(640, 480), 32

```
)
```

device.setWindowCaption("1.2 дерево пифагора");

```
driver = device.getVideoDriver()
```
```
 
```
```
while device.run():
```

    driver.beginScene(1, 1, SColor(255,255,255,255))

# вначале все поле закрашивается черным цветом

    pifagor(320, 460, 200, math.pi/2, driver);

```
    driver.endScene()
```
```
device.drop
```

Разумеется, что это не единственная самоподобная фигура.

В Интернете можно найти примеры изображений/формул/текста программ, например, на http://www.tmn.fio.ru/works/02x/306/fractals/example.html.

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

Categories: Gamedev. Все об разработке игр

Study & DevО программировании и не только

Программируем трехмерную графику с Irrlicht . Часть 6

Эффективное программирование 3d-приложений с помощью Irrlicht и jython. Часть 6

Поиск

Недавнее

Архив

Разделы