Ликбез по программированию
За прошедший с прошлой публикации материала серии период пришло сразу несколько фактически идентичных вопросов с просьбой порекомендовать русскоязычную книгу по программированию с использованием DirectX и Direct3D в частности. Нужно отметить, что на самом деле, хорошей литературы на русском языке по этой теме выпускается предельно мало, и лучшим руководством к действию являются всевозможные публикации, интернет-форумы, а также непосредственно справка к DirectX SDK, которая описывает все основные действия. В то же время англоязычной литературы много. Причем даже при условии средних познаний в иностранном все читается довольно легко, потому как обычно такая литература, чаще всего, состоит из работоспособного кода и небольших комментариев к нему. А в русскоязычных книгах я встречал больше варианты, которые стараются объять необъятное, очень много теории, при этом в практической части приводятся уж очень тривиальные вещи, слабые примеры и т.п.
***
Некоторые из заданных на тему Direct3D вопросов были связаны абсолютно не с геймдевом (как многие могут подумать), а большей частью с визуализацией процессов. Например, самый яркий из заданных вопросов касался создания современной графической оболочки для системы, получающей информацию с 200-500 датчиков (полный обход опроса рассчитывается на 3-4 секунды). Вопрос заключался в том, что лучше выбрать: OpenGL или DirectX? Что будет работать быстрее и потребует меньших мощностей?
На самом деле, в данном случае я рекомендовал бы все-таки DirectX, особенно, если разработка будет вестись в Visual Studio. Насчет нагрузки на аппаратные мощности… В варианте использования DirectX они несколько перераспределены, то есть очень многое ложится на плечи видеоадаптера, в то время как OpenGL подразумевает чисто программные расчеты. Кстати, именно поэтому его уже редко можно увидеть в компьютерных играх. А в целом все зависит от сложности визуальной части.
Кристофер, вы писали, как сделать универсальный медиаплеер на веб-странице… там, где ответили, что все вгружается во фрейм, в нем же меняются страницы и так далее. Я сделал так, как вы сказали: меню на флеше (AS 2.0), по нажатию кнопки во фрейме грузится страница, например с плеером от Youtube, либо... Проблема возникла сразу, в Explorer’е и Mozilla во фрейме не грузится страница с флеш-анимацией (меню). Примеры кода высылаю...
Вадим
В принципе, сам код, как вы написали, должен работать, но на практике:). В общем, я долго не разбирался, потому как быстро нашел другое решение. Вы создали отдельную страницу с флеш-анимацией, которая должна отображаться во фрейме. А теперь поставьте во фрейме ссылку не на ту страницу, а на сам swf-файл. Работает?
Подскажите, чем и как вообще лучше жать видео для того же YouTube…а то уж очень большие размеры.
Устанавливаете K-Lite Codec Pack, потом программу VirtualDub. В ней вы будете жать кодеком XVid (наиболее оптимальный и качественный). Причем для уменьшения размера файла измените размер изображения (геометрию экрана). О том, как работать в VirtualDub, есть много статей в Интернете.
Хочу переделать игру Lines таким образом, чтобы компьютер рассчитывал наилучший ход. Как это сделать, собственно?
В принципе, ничего сложного тут не будет, и можно даже вовсе не использовать рекурсивные методы. Как я это вижу? Можно пойти двумя путями: первый — от хода каждого отдельного шара (просчитать варианты для каждого расположенного на доске), второй — от анализа ситуации на доске. Второй более прост в реализации. То есть нужно найти наиболее выгодные желаемые клетки, на которых нужно расположить шары определенного цвета, а потом идет поиск этих шаров с расчетом возможности их доставки до места. Наиболее выгодные ходы — закрытие линий, вторые по значимости — создание линий, которые открыты с обоих концов, и так далее. В принципе, сам алгоритм можно усложнить более сильным анализом, например, рассматривать пересекающиеся линии, но это будет громоздко и не совсем правильно. Поэтому за счет рекурсии (или лучше циклами) нужно произвести анализ дальнейших действий на определенную глубину (или просчитать на несколько ходов вперед без учета того, что компьютер будет добавлять шары).
В первом случае предстоит реализация более громоздкой структуры с введением, например, двух состояний (можно и больше): клетка пуста, на клетке стоит шар. Потом вводим оценочную функцию хода. И перебираем варианты расстановки на каждую из клеток для каждого шара. Находим лучший вариант, запоминаем, потом сравниваем. Причем лучше сделать рекурсию (или опять же цикл) на глубину равную 3 (а в циклах это три хода вперед), без учета того, что компьютер будет добавлять шары.
Рекурсия выгодна только хорошей емкой упаковкой алгоритма, если вы в этом вопросе не очень хорошо разбираетесь, то используйте циклы. В принципе, я бы мог специально для этого материала быстро написать код для обоих вариантов, но он займет много места в газете, если рассматривать все с описаниями каждого действия. Получается четыре листинга — два варианта с двумя решениями (рекурсии и циклы).
Впрочем, советую обратиться к материалам серии «Популярно об ИИ», где мы рассматривали программирование компьютерного игрока (ИИ) в шахматы и крестики-нолики.
Кстати, подобный вопрос мне присылали по тетрису и, что самое интересное — питону:). В варианте тетриса все достаточно просто: нужно просчитать не только оптимальное расположение текущей падающей фигуры, но и варианты для размещения следующей (которая может быть одной из семи, если говорить о классическом тетрисе).
Ну а питон так вообще очень тривиально решается.
Я в программировании новичок, хочу создать небольшую сметную программу, есть справочники с видами работ, создаем разделы сметы, добавляем туда работы из справочника, указываем количество работ — и сразу идет расчет и по разделам, и по смете. Есть базовая цена, есть коэфф. наценки в зависимости от даты, есть коэфф. от места строительства.... в общем, заводишь таблицы с материалами, с видами работ, таблицы коэффициентов, при чем определенные работы требуют определенных норм определенных материалов, т.е. еще таблица с нормами материалов для каждого вида работ. Какой стандарт БД посоветуете?
Игорь Анатольевич
В принципе, что угодно можете использовать или, например, просто обойтись той же Access и т.п. Хотя я бы вообще не заморачивался и использовал бы обычные текстовые файлы (и даже не XML). В качестве языка выбрал бы C#. При правильно поставленном и максимально полном ТЗ разработка всего займет очень мало времени.
***
Вообще, не так давно студенты пережили сессию, поэтому количество вопросов в рубрику, особенно по реализации алгоритмов, их визуализации в рамках интерфейса программы, было очень велико. Что самое интересное, разбираясь в тех же графах и решая сложные задачи, очень многие спотыкались на более тривиальных вещах, а именно визуализации процессов даже с использованием GDI. Вторая по популярности тема вопросов — графы (поиск кратчайшего пути, наименьшей стоимости поездки и так далее).
Что касается самих интернет-ресурсов, в которых можно ознакомиться с примерами алгоритмов, само их описание есть на http://algolist.manual.ru и http://doors.infor.ru (хотя все это есть в обычных книгах); более-менее хорошие программные реализации встречаются на многих специализированных ресурсах. Для студентов я бы порекомендовал http://plagiata.net.ru (Delphi, C++). Кстати, для более сложных математических вычислений с использованием алгоритмов специально для С# существует отдельный набор классов Math.NET (http://nmath.sourceforge.net), распространяющийся под лицензией GPL.
Причем лично меня удивили некоторые моменты, например, студент спрашивал о реализации алгоритма Дейкстры. Причем он нашел работающий вариант, написанный на Delphi, а требовалась реализация на С# или C++. Как оказалось, перевести 30 строчек кода из паскаля в С — сложнейшая задача. Нужно было уделить неделю на поиск готового кода. М-да… Ваш покорный слуга, конечно, поиздевался, сказал, что перевод из Delphi — высший пилотаж программирования:))). А вы сможете перевести? Пример листинга привожу. Задание, на самом деле — очень простое.
Алгоритм Дейкстры на Delphi (задание — переведите на C++ или С#)
const n = 10; //количество вершин в графе
var
a:array[1..n,1..n] of longint;//матрица смежности
b:array[1..n]of boolean;//список просмотренных вершин
d:array[1..n] of longint;//кратчайшие расстояния
q, i, j, m, v: integer;
begin
//Ввод данных
q := StrToIntDef(Edit1.Text, 1); //начальная вершина
if (q < 1) or (q > n) then q := 1;
for i := 1 to n do
for j := 1 to n do
a[j, i] := StrToIntDef(StringGrid1.Cells[i - 1, j - 1], -1);
//Расчет
fillchar(b,sizeof(b),0);
fillchar(d,sizeof(d), 10000);
d[q] := 0;//расстояние до начальной вершины
for i:=1 to n do
begin
m := 1000;
for j := 1 to n do
if ( (d[j] <= m) and (not b[j]) ) then
begin
m:=d[j];
v:=j;
end;
b[v] := true;
for j := 1 to n do
if ((a[v,j] <> -1) and (not b[j]) and (d[v]+a[v,j]
d[j] := d[v] + a[v,j];
end;
//Вывод результата
ListBox1.Clear;
for i := 1 to n do
ListBox1.Items.Append(IntToStr(q)
+ ' -> ' + IntToStr(i) + ': '
+ IntToStr(d[i]));
end;
Кристофер christopher@tut.by
***
Некоторые из заданных на тему Direct3D вопросов были связаны абсолютно не с геймдевом (как многие могут подумать), а большей частью с визуализацией процессов. Например, самый яркий из заданных вопросов касался создания современной графической оболочки для системы, получающей информацию с 200-500 датчиков (полный обход опроса рассчитывается на 3-4 секунды). Вопрос заключался в том, что лучше выбрать: OpenGL или DirectX? Что будет работать быстрее и потребует меньших мощностей?
На самом деле, в данном случае я рекомендовал бы все-таки DirectX, особенно, если разработка будет вестись в Visual Studio. Насчет нагрузки на аппаратные мощности… В варианте использования DirectX они несколько перераспределены, то есть очень многое ложится на плечи видеоадаптера, в то время как OpenGL подразумевает чисто программные расчеты. Кстати, именно поэтому его уже редко можно увидеть в компьютерных играх. А в целом все зависит от сложности визуальной части.
Кристофер, вы писали, как сделать универсальный медиаплеер на веб-странице… там, где ответили, что все вгружается во фрейм, в нем же меняются страницы и так далее. Я сделал так, как вы сказали: меню на флеше (AS 2.0), по нажатию кнопки во фрейме грузится страница, например с плеером от Youtube, либо... Проблема возникла сразу, в Explorer’е и Mozilla во фрейме не грузится страница с флеш-анимацией (меню). Примеры кода высылаю...
Вадим
В принципе, сам код, как вы написали, должен работать, но на практике:). В общем, я долго не разбирался, потому как быстро нашел другое решение. Вы создали отдельную страницу с флеш-анимацией, которая должна отображаться во фрейме. А теперь поставьте во фрейме ссылку не на ту страницу, а на сам swf-файл. Работает?
Подскажите, чем и как вообще лучше жать видео для того же YouTube…а то уж очень большие размеры.
Устанавливаете K-Lite Codec Pack, потом программу VirtualDub. В ней вы будете жать кодеком XVid (наиболее оптимальный и качественный). Причем для уменьшения размера файла измените размер изображения (геометрию экрана). О том, как работать в VirtualDub, есть много статей в Интернете.
Хочу переделать игру Lines таким образом, чтобы компьютер рассчитывал наилучший ход. Как это сделать, собственно?
В принципе, ничего сложного тут не будет, и можно даже вовсе не использовать рекурсивные методы. Как я это вижу? Можно пойти двумя путями: первый — от хода каждого отдельного шара (просчитать варианты для каждого расположенного на доске), второй — от анализа ситуации на доске. Второй более прост в реализации. То есть нужно найти наиболее выгодные желаемые клетки, на которых нужно расположить шары определенного цвета, а потом идет поиск этих шаров с расчетом возможности их доставки до места. Наиболее выгодные ходы — закрытие линий, вторые по значимости — создание линий, которые открыты с обоих концов, и так далее. В принципе, сам алгоритм можно усложнить более сильным анализом, например, рассматривать пересекающиеся линии, но это будет громоздко и не совсем правильно. Поэтому за счет рекурсии (или лучше циклами) нужно произвести анализ дальнейших действий на определенную глубину (или просчитать на несколько ходов вперед без учета того, что компьютер будет добавлять шары).
В первом случае предстоит реализация более громоздкой структуры с введением, например, двух состояний (можно и больше): клетка пуста, на клетке стоит шар. Потом вводим оценочную функцию хода. И перебираем варианты расстановки на каждую из клеток для каждого шара. Находим лучший вариант, запоминаем, потом сравниваем. Причем лучше сделать рекурсию (или опять же цикл) на глубину равную 3 (а в циклах это три хода вперед), без учета того, что компьютер будет добавлять шары.
Рекурсия выгодна только хорошей емкой упаковкой алгоритма, если вы в этом вопросе не очень хорошо разбираетесь, то используйте циклы. В принципе, я бы мог специально для этого материала быстро написать код для обоих вариантов, но он займет много места в газете, если рассматривать все с описаниями каждого действия. Получается четыре листинга — два варианта с двумя решениями (рекурсии и циклы).
Впрочем, советую обратиться к материалам серии «Популярно об ИИ», где мы рассматривали программирование компьютерного игрока (ИИ) в шахматы и крестики-нолики.
Кстати, подобный вопрос мне присылали по тетрису и, что самое интересное — питону:). В варианте тетриса все достаточно просто: нужно просчитать не только оптимальное расположение текущей падающей фигуры, но и варианты для размещения следующей (которая может быть одной из семи, если говорить о классическом тетрисе).
Ну а питон так вообще очень тривиально решается.
Я в программировании новичок, хочу создать небольшую сметную программу, есть справочники с видами работ, создаем разделы сметы, добавляем туда работы из справочника, указываем количество работ — и сразу идет расчет и по разделам, и по смете. Есть базовая цена, есть коэфф. наценки в зависимости от даты, есть коэфф. от места строительства.... в общем, заводишь таблицы с материалами, с видами работ, таблицы коэффициентов, при чем определенные работы требуют определенных норм определенных материалов, т.е. еще таблица с нормами материалов для каждого вида работ. Какой стандарт БД посоветуете?
Игорь Анатольевич
В принципе, что угодно можете использовать или, например, просто обойтись той же Access и т.п. Хотя я бы вообще не заморачивался и использовал бы обычные текстовые файлы (и даже не XML). В качестве языка выбрал бы C#. При правильно поставленном и максимально полном ТЗ разработка всего займет очень мало времени.
***
Вообще, не так давно студенты пережили сессию, поэтому количество вопросов в рубрику, особенно по реализации алгоритмов, их визуализации в рамках интерфейса программы, было очень велико. Что самое интересное, разбираясь в тех же графах и решая сложные задачи, очень многие спотыкались на более тривиальных вещах, а именно визуализации процессов даже с использованием GDI. Вторая по популярности тема вопросов — графы (поиск кратчайшего пути, наименьшей стоимости поездки и так далее).
Что касается самих интернет-ресурсов, в которых можно ознакомиться с примерами алгоритмов, само их описание есть на http://algolist.manual.ru и http://doors.infor.ru (хотя все это есть в обычных книгах); более-менее хорошие программные реализации встречаются на многих специализированных ресурсах. Для студентов я бы порекомендовал http://plagiata.net.ru (Delphi, C++). Кстати, для более сложных математических вычислений с использованием алгоритмов специально для С# существует отдельный набор классов Math.NET (http://nmath.sourceforge.net), распространяющийся под лицензией GPL.
Причем лично меня удивили некоторые моменты, например, студент спрашивал о реализации алгоритма Дейкстры. Причем он нашел работающий вариант, написанный на Delphi, а требовалась реализация на С# или C++. Как оказалось, перевести 30 строчек кода из паскаля в С — сложнейшая задача. Нужно было уделить неделю на поиск готового кода. М-да… Ваш покорный слуга, конечно, поиздевался, сказал, что перевод из Delphi — высший пилотаж программирования:))). А вы сможете перевести? Пример листинга привожу. Задание, на самом деле — очень простое.
Алгоритм Дейкстры на Delphi (задание — переведите на C++ или С#)
const n = 10; //количество вершин в графе
var
a:array[1..n,1..n] of longint;//матрица смежности
b:array[1..n]of boolean;//список просмотренных вершин
d:array[1..n] of longint;//кратчайшие расстояния
q, i, j, m, v: integer;
begin
//Ввод данных
q := StrToIntDef(Edit1.Text, 1); //начальная вершина
if (q < 1) or (q > n) then q := 1;
for i := 1 to n do
for j := 1 to n do
a[j, i] := StrToIntDef(StringGrid1.Cells[i - 1, j - 1], -1);
//Расчет
fillchar(b,sizeof(b),0);
fillchar(d,sizeof(d), 10000);
d[q] := 0;//расстояние до начальной вершины
for i:=1 to n do
begin
m := 1000;
for j := 1 to n do
if ( (d[j] <= m) and (not b[j]) ) then
begin
m:=d[j];
v:=j;
end;
b[v] := true;
for j := 1 to n do
if ((a[v,j] <> -1) and (not b[j]) and (d[v]+a[v,j]
d[j] := d[v] + a[v,j];
end;
//Вывод результата
ListBox1.Clear;
for i := 1 to n do
ListBox1.Items.Append(IntToStr(q)
+ ' -> ' + IntToStr(i) + ': '
+ IntToStr(d[i]));
end;
Кристофер christopher@tut.by
Компьютерная газета. Статья была опубликована в номере 27 за 2010 год в рубрике программирование
