Статья из четвёртого выпуска журнала «ПРОграммист».

Обсудить на форуме – Кое-что о ремонте…

Большинство пользователей персонального компьютера привыкли к тому, что весь результат деятельности на компьютере в той или иной степени все равно отражается в самом компьютере. В крайнем случае, отправляется на принтер или в Интернет, или же запись информации происходит на внешние носители (диски, флеш-память и т.п.). И уж мало кто задумывается, что с помощью простого РС – компьютера можно управлять различными внешними физическими устройствами.

Владимир Дегтярь

by DeKot degvv@mail.ru

Тем не менее, на форуме http://www.programmersforum.ru (да и на других также) часто появляются вопросы: «Как с компьютера зажечь светодиод?», «Как управлять освещением?» или «Можно ли компьютером закрывать шторы на окне?». Ответ:  «…однозначно да». С помощью современного персонального компьютера можно создавать, воспроизводить, управлять, хранить, моделировать, обучать и еще реализовать много и много других функций.

Введение

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

Думаю что уже достаточно теории. Перейдем к практической реализации – управлению реальными устройствами с помощью компьютера. Более всего для этого подходит «параллельный» порт LPT. Более подробно смотрим о LPT http://ru.wikipedia.org/wiki/IEEE_1284.

Параллельный порт LPT

Итак, почему параллельный, а не перпендикулярный? А какие еще бывают? Параллельный, потому что информация через такое устройство передается параллельным способом. А еще может передаваться последовательным – тогда устройство (порт) называется последовательным (последовательные порты компьютера: COM-порт, USB- порт). Наглядно это можно увидеть на рисунке 2:

Аналогично ввод информации также может быть параллельным или последовательным. Порты (устройства) через которые можно вводить и выводить информацию называют двунаправленными устройствами или устройствами ввода/вывода. Таким и есть параллельный порт LPT, имеющийся в большинстве компьютеров. Посмотрим, что из себя представляет этот порт (см. рисунок 3):

где С0…С3 – регистры контроля, S3…S7 – регистры статуса, D0…D7 – регистры данных

Как видите, это такой разъем с 25-ю выводами на задней стенке системного блока компьютера. Итак, имеем физический порт LPT, который фактически состоит из трех регистров. Состав регистров и распределение по контактам разъема приведены в таблице 1:

Каждый из регистров может содержать байт информации (256 состояний). Часть битов не используется или используется только во внутренней архитектуре компьютера для организации прерываний при работе с принтером или для переключения режимов ввод/вывод регистра «Data».

Регистр данных «Data», номер регистра в шестнадцатеричной системе счисления $378 (в десятичной 888) – двунаправленный, восьмибитный. Данные через этот регистр можно как вводить, так и выводить с компьютера, программно устанавливая уровни на выходе порта или же вводить в компьютер, также программно считывая уровни, устанавливаемые внешними устройствами.

Регистр управления «Control» $37A (890). Через него можно только выводить информацию из компьютера. На разъем LPT выводятся четыре младших байта.

Регистр статуса «Status» $379 (889). Через порт можно только считывать уровни, установленные внешними устройствами. На разъем LPT выведены пять старших байтов.

Таким образом, на разъеме LPT задействовано 17 сигнальных контактов (8 двунаправленных – регистр 888, четыре только на вывод информации – регистр 890 и пять только на ввод информации – регистр 889).

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

Следует отметить, что в некоторых компьютерах может быть до трех портов LPT: LPT1, LPT2, LPT3 (в  современных компьютерах LPT порты зачастую вообще отсутствуют). Адрес самого LPT порта соответствует адресу регистра «Data» и может быть $278, $378 или $3BC. Регистры в соответствующих портах имеют адресацию +1 и +2.

Следующие таблицы (см. таблицы 2, 3) показывают эти особенности данного порта. Для регистра $378 (888) соблюдается полное соответствие между уровнями напряжения на контактах и логическим кодом. А вот с регистрами $379 (889) и $37A (890) все обстоит по-другому:

Управление регистрами

В компьютерах с операционными системами MS-DOS, Windows 9x возможен доступ к портам непосредственно из самой операционной системы, тогда как в системах с NT такой прямой доступ невозможен. Для этих целей используются драйвера в виде библиотек (Inpout32.dll, WinIO, Giveo). Подключив соответствующие библиотеки к средам программирования, получаем возможность программно работать с портами (считывание состояния порта или установка выводов порта в необходимое состояние).

* Автор отдает предпочтение библиотеке <inpout32.dll> для работы в среде Дельфи. Библиотека

<inpout32.dll> свободно распространяется в Интернете (см. ресурсы к статье).

Итак, во-первых – помещаем <inpout32.dll> в папке с проектом. Далее в коде модуля Unit после раздела uses размещаем объявления необходимых нам функций из библиотеки:

// импорт функций inpout32.dll

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs,StdCtrls, ExtCtrls, ComCtrls;

function Inp32(PortAdr: word): byte; stdcall; external 'inpout32.dll';

function Out32(PortAdr: word; Data: byte): byte; stdcall; external 'inpout32.dll';

Функция Inp32(PortAdr) возвращает число (тип – байт), соответствующее коду, находящемся в регистре PortAdr. Функция Out32(PortAdr, Data) возвращает число (Data, тип – байт), которое запишется в регистр PortAdr. Проще сказать Inp32 считывает значение регистра, а Out32 устанавливает значение в регистр. Пример применения функций:

var val1, val2: byte;

val1:= Inp32($378);      // значение регистра «data» запишется в переменную val1

val2:= 54;

Out32($378,val2);         // в регистр «data» запишется число 54 (b 0 0 1 1 0 1 1 0)

При этом следует учитывать, что состояние уровней напряжения на выходных контактах LPT порта соответствует таблице 2 и 3. При необходимости управления отдельными битами регистров можно применить следующие функции преобразований десятичного числа в двоичное и наоборот:

// weight (для byte(8 разр.)) = 128, j = 7; weight( для word (16 разр.)) = 32 768, j = 15 ;

function Dec_Bin(N_dec: integer; weight: integer; _bit: byte): byte;

var i ,j : byte;

mas_bin: array[0..j] of byte;

N_dec: integer;

begin

for i:= 0 to j do

begin

mas_bin:= N_dec div weight;

if mas_bin = 1 then N_dec:= N_dec - weight;

weight:= weight div 2;

end;

Result:= mas_bin[_bit];            // возвращает значение бита (0 или 1) двоичного числа,

// соответствующего N_dec

end;

function Bin_Dec(weight: integer): integer;

var i , j: byte;

mas_bin: array[0..j] of byte;

N_dec: integer;

begin

N_dec:= 0;

for i:= 0 to j do

begin

N_dec:= N_dec + mas_bin * weight;

weight:= weight div 2;

end;

Result:= N_dec;           // возвращает десятичное число, соответствующее двоичному

// в виде массива битов mas_bin [ 0 .. j ]

end;

Пример применения функций:

var bit : byte;

bit := Dec_Bin(Inp32($378))[3]; // переменная bit принимает значение 3-го бита регистра «data»

** Переключение регистра «data» ($378) c «выхода» на « вход»

Возможность использования регистра «data» ($378) в качестве порта ввода определяется в настройках

BIOS для параллельного порта. Следует установить Parallel Port в EPP. Переключение регистра на «вход»

осуществляется программно, путем установки 5-го бита регистра «control» ($37A) в «1» (при этом все биты

регистра «data» устанавливаются в «1»). Следует отметить, что данная процедура возможна не на каждом

компьютере и определяется, кроме настроек, еще и конструктивными особенностями порта LPT или

материнской платы.

Вариант тестовой утилиты управления и считывания состояния регистров LPT представлен на рисунке 4 и приведен в ресурсах к статье [1]:

Заключение

Продолжение смотрите в следующем выпуске журнала «ПРОграммист»…

Ресурсы

. Модули и проекты, использованные в статье http://programmersclub.ru/pro/pro3.zip

. Сайт Валерия Ковтуна с множеством интересных программ для работы с LPT портом

http://valery-us4leh.narod.ru/main.html

Это статья из третьего номера журнала “ПРОграммист”.
Скачать его можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Работа с LPT портом в Дельфи или компьютер в роли управляющего контроллера. Часть 1

Здравствуйте, уважаемые читатели. Как и обещал, сегодня с вами мы подробно рассмотрим процедуры работы с графическими объектами, вынесенными в отдельный модуль, позволяющий использовать универсальные методы для создания движущихся изображений, находящихся в файлах, обычно в виде спрайтов…

Продолжение. Начало цикла смотрите в первом и втором выпусках журнала…

Владимир Дегтярь

DeKot degvv@mail.ru

Создание проекта с несколькими движущимися объектами. Урок 5

Создадим новый проект <Lesson 3> аналогично предыдущим. Введем в него новые движущиеся графические объекты (в папке <data> добавлено еще четыре звездолета. Размер каждого спрайта 100х80 pix. Новые звездолеты будут появляться по случайному закону (используем функцию Randomize) и двигаться будут сверху вниз. Вывод фона и основного звездолета ’ship1′ осуществляется также как и в предыдущем проекте <Lesson 2>. Для новых объектов вводим дополнительно BufShipR и BufPicR. Также объявим новые переменные – координаты вывода новых звездолетов и приращения этих координат.
Одновременно у нас будут отображаться основной звездолет ’ship 1′ и два из ’ship 2′ – ’ship 5′, выбираемые по случайному закону (см. листинг 1):

ЛИСТИНГ 1

Var

Form1: TForm1;

BufFon,BufFonDop,Buffer: TBitMap;

BufShip1,BufShipR: TBitMap; // буферы  спрайтов

BufPicS1,BufPicR: TBitMap;   //  буферы  изображений  одного спрайта

xf,yf: integer;                         //  координаты  вывода  общего буфера  на форму

dyf: integer;                           // приращение  изменения  координаты  yf  по вертикали

xS1,yS1: integer;                    //  координаты  звездолета  'ship1'

dxS1,dyS1: integer;                // приращение  координат 'ship1' по гориз. и вертик.

xR1,yR1,xR2,yR2: integer;      //  координаты  звездолетов  'ship2 - ship5'

dyR1,dxR2,dyR2: integer;       // приращение  координат 'ship2 - 5'

ns,nr1: byte;                           //  номер спрайта и выбор ship2 - ship5

nr2: byte = 3;

implementation

В процедуре OnCreate формы проведем инициализацию буферов и введем начальные данные для переменных. Процедура DrawShipR(i,j: byte) для вывода новых объектов (’ship2′ – ’ship5′) имеет два

параметра: i (изменение номера рисунка в файле спрайтов) и j (переменная для номера файла спрайтов). Т.к. выбор файла спрайта происходит по передаваемому параметру j, то инициализация буфера BufShipR и загрузка в него файла спрайтов находится в процедуре DrawShipR(i,j: byte) (см. листинг 2):

ЛИСТИНГ 2

procedure DrawShip1(i: byte);

begin

// загрузка одного спрайта в буфер рисунка

BufPicS1.Canvas.CopyRect(bounds(0,0,BufPicS1.Width,

BufPicS1.Height),

BufShip1.Canvas,

bounds(i * 66,0,

BufPicS1.Width,

BufPicS1.Height));

BufPicS1.Transparent:= true;  //  зададим прозрачность фона рисунка спрайта

BufPicS1.TransparentColor:= BufPicS1.Canvas.Pixels[1,1];

end;

Все движения организованы в обработчике таймера. Звездолеты ’ship2′ — ’ship5′ выводятся в Buffer в координаты xR1, yR1 и xR2, yR2 вне видимого окна формы выше. В каждом такте таймера происходит приращение координат для одного dyR1 по вертикали, для другого dxR2 и dyR2 – по горизонтали и вертикали. После того, как объекты выходят за пределы видимого окна формы внизу, вызываются методы random( ) для задания новых координат xR1, xR2 и номера файла спрайта (nr1, nr2). Координаты yR1, yR2 привязаны к координате yS1 , так как ’ship1′ неподвижен в координатах окна формы. Функция
random ( 4 ) возвращает числа в дипазоне 0 .. 3, а файлы спрайтов встречных звездолетов имеют номера 2 .. 5. Поэтому в процедуре загрузки спрайтов BufShipR.LoadFromFile(’data/ship’ + IntToStr(j+2) + ‘.bmp’) номер загружаемого файла определяется как IntToStr(j + 2)… В остальном процедуры обработчиков таймера и нажатия клавиш не отличаются от проекта <Lesson 2>.

Использование универсального модуля для работы с графикой. Урок 6

Если рассмотреть внимательно код программы в проекте <Lesson 3>, можно заметить, что многие методы часто повторяются для разных графических объектов (создание буферов, загрузка изображений из файлов, копирование и т.п.). При этом для упрощения, я сознательно применил файлы спрайтов одинакового размера и с равным количеством рисунков в файлах. А если файлов спрайтов будет не пять, а больше и если количество рисунков в каждом файле будет разным? Придется значительно увеличивать код для

каждого вида спрайтов. Следовательно, необходимо оптимизировать код программы. Выход здесь в написании методов обработки объектов, не зависящих от количества объектов и применимых для разных изображений.

Даная задача реализована в отдельном модуле <LoadObjectToBufferMod>, позволяющий использовать универсальные методы для создания движущихся графических объектов (находящихся в файлах, обычно в виде спрайтов), имеющих различный размер и разное количество изображений отдельных рисунков.

Модуль находится в папке <Lesson 4> (см. ресурсы к статье). Принцип организации модуля следующий:

• вся работа с графическими объектами проводится через битовые образы TBitMap и области

копирования битовых образов TRect

• для работы с фоном используются процедуры InitFon (инициализация) и LoadFon (загрузка фона из

файлов)

• функция InitSprite предназначена для инициализации и загрузки рисунков спрайтов
• для вывода фона и изображений спрайтов использован общий буфер типа TBitMap
• в процедуре InitBuff происходит инициализация общего буфера, а в процедуре FreeBuff ”переустановка”,

т.е. уничтожение общего буфера и создание снова, но уже без изображений спрайтов

• в процедуре LoadBuff происходит наложение изображений спрайтов на фон

Подробно работа модуля показана ниже…

Применение модуля LoadObjectToBufferMod

1. procedure InitFon(nw, nh: byte; FileName: string)

Создаем дополнительный и основной буферы фона:

BufFonD:= TBitmap.Create;

BufFon  := TBitmap.Create;

Далее загружаем рисунок одного из фонов в дополнительный буфер:

BufFonD.LoadFromFile(FileName) или

LoadFromResourceName(hinstance.filename);

По загруженному рисунку получаем размер одного рисунка фона (см. рисунок 1):

Причем, размер буфера фона определяем как:

WF:= nw * WFD;

HF:= nh * HFD;

2. procedure LoadFon(xf, yf: integer; FileName: string)

Загружаем все рисунки фонов в буфер фона через дополнительный буфер (см. рисунок 2):

BufFonD.LoadFromFile(FileName) или

LoadFromResourceName(hinstance.filename);

3. procedure initBuffer

Создаем основной буфер (Buffer) через который выводим спрайты на форму:

Buffer:= TBitmap.Create;

Размер основного буфера устанавливаем равным размеру буфера фона WF и HF. Загружаем в основной буфер весь фон (cм. рисунок 3):

Buffer.Canvas.Draw(0, 0, BufFon);

4. procedure FreeBuffer

Процедура уничтожаем основной буфер Buffer. Применяется когда необходимо убрать какой-либо спрайт с формы:

Buffer.Free;

Восстанавливаем-же основной буфер с фоном так:

InitBuffer;

Спрайты, которые должны оставаться на форме, следует перерисовать по новому (см. процедуру InitStprite)…

5. procedure InitStprite(SpriteName: string; N_goriz, N_vertic, N_stroka, N_kadr: byte): byte

Cоздаем буфер массива спрайтов и загружаем туда файл спрайтов (см. рисунок 4):

BufSprite:= TBitmap.Create;

BufSprite.LoadFromFile(SpriteName) или

LoadFromResourceName(hinstance.spritename);

Рис. 4. Загрузка файла спрайтов в буфер спрайтов

Создаем буфер рисунка (одного спрайта):

BufPic:= TBitmap.Create;

Далее определяем размеры буферов массива спрайтов и буфера рисунка, а также области (типа TRoot) загрузки рисунка. Загружаем спрайт в буфер рисунка (см. рисунок 5):

BufPic.Canvas.CopyRect(RectPic.BufSprite.Canvas, rectSprite);

Задаем прозрачность рисунку:

BufPic.Transparent:= true;

Для вывода следующего спрайта функция возвращает (правильнее сказать – функция принимает значение = Result) значение следующего номера спрайта N_kadr:

Result:= N_kadr;

Уничтожаем буфер массива спрайтов

BufSprite.Free;

6. procedure LoadBuffer(xf, yf, xs, ys, bs: integer)

В этой процедуре на Buffer выводится участок фона с координатами ранее выведенного спрайта, а затем очередное положение спрайта. Определяем область фона и область дополнительного буфера (см. рисунок 6):

Выводим участок фона в буфер, т.е. затираем спрайт фоном (см. рисунок 7):

Выводим очередной спрайт в дополнительный буфер Buffer (см. рисунок 8):

Buffer.Canvas.StretchDraw(Bounds(xs, ys, WP + bs, HP + bs), BufPic);

Уничтожаем буфер рисунка:

BufPic.Free;

Далее в программе выводим дополнительный буфер Buffer на форму методом Draw:

Form1.Canvas.Draw(x, y, Buffer);

Битовые образы фона (BufFon и BufFonD инициализируются (создаются – Create) в программе проекта всего один раз при инициализации программы (обычно вызовом процедуры InitFon в событиях OnCreate или OnActivate). Методы InitBuff, FreeBuff, InitSprite, LoadBuf в программе вызываются неоднократно*. Соответственно и объекты Buffer, BufSprite, BufPic создаются многократно. Поэтому после окончания действия каждого из методов происходит уничтожение битовых образов Buffer, BufSprite, BufPic методом Free.

Комментарий автора.

Загрузку фона можно производить из n – количества файлов, c одинаковым размером не более 1024 х

1024. Для этого вызывать процедуру LoadFon n -раз для разных файлов FonName и изменяя

координаты xf и yf.

Модуль можно применять и для простых объектов (один рисунок в файле SpriteName). Присвойте

переменным N_goriz и N_vertic значения = 1. Если размер спрайта не изменяется, присвойте

переменной bs значение = 0.

Можно загружать рисунки из файлов .jpg. Для этого вместо TBitMap применять класс TJpegImage и в

разделах uses LoadObjectToBufferMod и uses Unit1 добавить модуль Jpeg.

Как работать с модулем?

Для этого необходимо выполнить следующие действия:

1. В процедуре FormActivate (можно в FormCreate) инициализируем буфер фона. Вызываем procedure InitFon(nw,nh: byte; FonName: string) с одним из файлов фонов:

. n раз вызываем procedure LoadFon(xf,yf: integer; FonName: string), последовательно прикрепляя рисунки фонов как бы друг к другу

. инициализируем дополнительный буфер Buffer, вызвав procedure InitBuff. Он получит размер равный сумме размеров всех файлов фонов.

2. Для вывода необходимых спрайтов в нужном месте программы вызываем function InitSprite(SpriteName: string; N_goriz,N_vertic,N_stroka, N_kadr: byte). Функция возвращает очередной номер спрайта для последующего вывода очередного спрайта. Этот номер (N_kadr) необходимо передавать в функцию при каждом ее вызове. Причем, функцию можно использовать для вывода нескольких спрайтов, не забывая передавать ей значение N_kadr для каждых спрайтов.

Далее, вызвав процедуру LoadBuff(xf,yf,xs,ys,bs: integer), выводим спрайт на канву дополнительного буфера поверх фона. Окончательный вывод дополнительного буфера на канву формы производим методом Draw().

Заключение

Рассматриваемые в данной статье проекты полностью приведены в виде ресурсов в теме «Журнал клуба программистов. Третий выпуск» или непосредственно в архиве с журналом (папка Lesson3). Продолжение наших уроков смотрите в следующем выпуске журнала «ПРОграммист»…

Комментарий автора.

Перед запуском в среде Дельфи скопируйте в папку с проектом папку data с графическими файлами.

Это статья из третьего номера журнала “ПРОграммист”.
Скачать его можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Как работать с графикой на канве в среде Дельфи

Данная статья будет полезна начинающим программистам, которые никогда не имели дело со звуком и его передачей по сети. Смысл этой статьи заключается в изучении и применении: WINAPI функций ввода и вывода звука WaveIn() и WaveOut() в среде разработки Delphi 7.0, самих компонентов TIdUDPServerSocket и TIdUDPClientSocket. Данные компоненты можно найти в библиотеке Indy, которая в свою очередь находится в свободном распространении на просторах Internet’а.

Передача звука по сети. Прототип VoIP телефона

Уколов Александр Владимирович

by ImmortalAlexSan st_devil@mail.ru

Комментарий автора.

Если вы никогда не программировали в Delphi 7.0, версиями ниже или  выше, если вы вообще никогда не программировали на подобных ЯВУ, то эта статья не для вас.

Введение

К написанию программы для передачи звука по сети меня побудило желание получить-таки зачет по УИРС (это что-то вроде НИР – научно исследовательской работы студента) у преподавателя, ведущего мой основной предмет, и являющимся моим дипломным руководителем. Перед тем как сесть за Delphi и начать набирать код, предварительно, я изучил кучу литературы в бумажном и электронном виде о принципах упаковки звука и его передачи, о функциях ввода и вывода в самом Delphi и многом другом [1, 2]. Именно ввод и вывод заставил меня задуматься о сложности преподносимого материала. Для человека, никогда не имевшего с этим дело, разобраться в этой области очень сложно, имея под рукой множество кода без комментариев с непонятными процедурами и функциями непонятного WIN API, а если эти процедуры и функции описаны, то это описание предназначено не для начинающих программистов, приходилось все додумывать самому: смотреть подноготную каждой процедуры, и методом проб и ошибок идти медленно, но уверенно к вершине созидания. Но в конечном итоге я добился поставленной цели. И сейчас, разложив всю информацию, предоставленную мне в кашеобразном виде, по полочкам, я готов поделиться своими знаниями с вами, дорогие читатели! Итак, приступим…

Средства разработки

Прежде всего, для работы нам понадобится:

. IDE Delphi версии 7.0 и выше

. Библиотека Indy для Delphi 7.0 (TIdUDPServerSocket и TIdUDPClientSocket) [3, 4]

. колонки и микрофон

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

Практическая часть. Создадим клиента

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

Для этого, создадим новый проект в Дельфи, разместим на форме кнопку TButton и изменим ее свойство Caption на «начать отправку». После чего, разместим на форме компонент из библиотеки Indy TIdUDPClientSocket (см. рисунок 1):

Так как тестирование программы будет проводиться на локальном компьютере, то изменим значение свойства Host компонента TIdUDPClientSocket на «localhost». Далее я просто перечислю свойства компонента и их значения, что должны быть установлены: Active (false), BroadCastEnabled (false), BufferSize (8192), Name (IdUDPClient1), Port (0), ReceiveTimeOut (-2), Tag (0).

Примечание: описание некоторых вышеуказанных свойств выходит за рамки данной статьи.

Теперь, нажимаем двойным щелчком по вынесенному на форму компоненту TButton и  появится обработчик события Button1Click(), где Button1 – это значение свойства Name данного компонента. В этом обработчике пишем или копируем следующий код:

procedure TForm1.Button1Click(Sender: TObject);

begin

// если на кнопке написано «начать отправку» то

If button1.Caption='Начать отправку' then Begin // выполняем этот код, где:

// готовим заголовок для буфера, здесь WaveIn – переменная типа интегер, для

// указания идентификатора устройства ввода (микрофона например), @WaveHdr –

// указатель на структуру TWaveHdr, sizeof(Twavehdr) – размер данной структуры в байтах.

waveInPrepareHeader(waveIn,@WaveHdr,sizeof(Twavehdr));

// заносим данные в буфер

waveInAddBuffer(wavein,@WaveHdr,sizeof(TwaveHdr));

// активируем сокет клиента

IdUDPClient1.Active:= true;

// считываем данные с микрофона

waveInStart(waveIn);

// в едит для наглядности заносим количество записанных байт (делал для себя,

// чтобы проверять, пишется звук или нет)

Edit1.Text:= inttostr(WaveHdr.dwBufferLength);

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

button1.Caption:='Остановить отправку'

end else Begin // если название кнопки «остановить отправку» то

//переименовываем её

button1.Caption:='Начать отправку';

//закрываем сокет клиента

IdUDPClient1.Active:=false;

//разгружаем буфер

waveInUnprepareHeader(Wavein,@WaveHdr,sizeof(TwaveHdr));

// приостанавливаем считывание. ЗАМЕТЬТЕ! ПРИОСТАНАВЛИВАЕМ! Если мы

// напишем waveInClose(Wavein), то устройство будет закрыто, и при повторном

// нажатии на кнопку, не будет никакого результата.

waveInStop(Wavein);

// смотрим кол-во не записанных байт

Edit1.Text:=inttostr(Wavehdr.dwBytesRecorded);

end

end;

Вы спросите, а что же такое waveInPrepareHeader? Это функция, выполняющая подготовку буфера для операции загрузки данных. Общий вид:

function waveInPrepareHeader(

hWaveIn: HWAVEIN;

lpWaveInHdr: PWaveHdr;

uSize: UINT

): MMRESULT; stdcall;

Здесь:

HWaveIn                      – идентификатор открытого устройства

LpWaveInHdr                – адрес структуры WaveHdr

type TWaveHdr = record

lpData: PChar; { указатель на буфер}

dwBufferLength: DWORD; { длина буфера }

dwBytesRecorded: DWORD; { записанный байты }

dwUser: DWORD; { переменная для использования её пользователем }

dwFlags: DWORD; { флаги }

dwLoops: DWORD; { контролер }

lpNext: PWaveHdr; { переменная для драйвера }

reserved: DWORD; { переменная для драйвера }

end;

Здесь:

lpData                          – адрес буфера для загрузки данных

dwBufferLength                        – длина буфера в байтах

dwBytesRecorded        – для режима загрузки данных определяет количество загруженных в буфер байт

dwUser                        – пользовательские данные

dwFlags                       – флаги. Могут иметь следующие значения: WHDR_DONE устанавливается

драйвером при завершении загрузки буфера данными

WHDR_PREPARED     – устанавливается системой. Показывает готовность буфера к загрузке данных

WHDR_INQUEUE         – устанавливается системой, когда буфер установлен в очередь

dwLoops                      – используется только при воспроизведении. При записи звука всегда 0

lpNext                          – зарезервировано

reserved                       – зарезервировано

uSize                           – размер структуры WaveHdr в байтах

Функция waveInPrepareHeader вызывается только один раз для каждого устанавливаемого в очередь загрузки буфера. Что такое waveInAddBuffer()? Функция waveInAddBuffer() ставит в очередь на загрузку данными буфер памяти. Когда буфер заполнен, система уведомляет об этом приложение:

function waveInAddBuffer(

hWaveIn: HWAVEIN;

lpWaveInHdr: PWaveHdr;

uSize: UINT

): MMRESULT; stdcall;

Здесь:

hWaveIn                       – идентификатор открытого Waveform audio устройства ввода

lpWaveInHdr                 – адрес структуры TWaveHdr

uSize                           – размер WaveHdr в байтах

Что такое waveInStart(), waveInStop(), waveInClose()? Общий вид записи таков:

function waveInStart(hWaveIn: HWAVEIN): MMRESULT; stdcall;

waveInStop(), waveInClose() имеют совершенно одинаковый параметр – как и WaveInStart(), которую описывать не имеет смысла, ибо и так понятно, что она начинает считывать данные с устройства ввода, а вот waveInClose() закрывает устройство для записи, и его снова придется открывать с помощью WaveInOpen(), но об этом ниже… А вот waveInStop(), ставит запись как бы на паузу, и нам не надо повторно использовать WaveInOpen().

Что такое waveInUnprepareHeader? Функция аналогичная waveInPrepareHeader(), однако она возвращает выделенную память на буфер, т.е. как бы «уничтожая» его.

Как узнать, что уже можно передавать данные?

Мы разобрали некоторые функции WIN API, относящиеся к вводу данных. Не устали? Нет? Тогда двигаемся дальше! Создадим собственную процедуру для определения завершения передачи данных в блок памяти посредством WaveInAddBuffer(). А выглядит она так:

procedure TForm1.OnWaveMessage(var msg:TMessage);

begin

waveInPrepareHeader(waveIn,@WaveHdr,sizeof(Twavehdr));

waveInAddBuffer(wavein,@WaveHdr,sizeof(TwaveHdr));

// отправляем буфер на сервер, где WaveHdr.lpData^ - это ссылка на память, где

// хранятся считанные с микрофона данные, уже преобразованные в

// последовательность нулей и единиц, WaveHdr.dwBufferLength – длина буфера данных

idUDPClient1.Sendbuffer(WaveHdr.lpData^,WaveHdr.dwBufferLength);

// В переменную заносим количество отправленных байт

Bytes:=Bytes+WaveHdr.dwBufferLength;

// Формат строки. Посмотрите в google фразу format дельфи

Caption:=Format ('%u',[Bytes]);

UpDate

end;

В этой процедуре используются уже известные вам функции, по этому второй раз описывать их не будем. Пишем её сразу после строки {$R *.dfm}. А описываем эту процедуру в разделе private класса TForm1 как:

procedure OnWaveMessage(var msg:TMessage); message MM_WIM_DATA;

Эта процедура будет выполняться каждый раз как только передача данных в буфер будет завершена и система сгенерирует сообщение WIM_DATA. Заполним обработчик события формы OnClose():

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);

begin

// завершаем все действия

Action:= caFree;

// деактивируем сокет

IdUDPClient1.Active:=false;

// закрываем, теперь уже совсем, устройство записи

waveInClose(Wavein);

end;

И конечно же, заполним обработчик события формы OnCreate():

procedure TForm1.FormCreate(Sender: TObject);

begin

// with – оператор, благодаря которому можно не писать переменные, а указывать

// сразу их свойства. В данном случае WaveFormat: TWAVEFORMATEX – отвечает

// за сигнал, т.е. за все его характеристики, описан ниже.

with waveformat do begin

nChannels:=1;

wFormatTag:=WAVE_FORMAT_PCM;

nSamplesPerSec:=8000;

wBitsPerSample:=8;

nBlockAlign:=1;

nAvgBytesPerSec:=8000;

cbSize:=0;

end;

// для удобства загоняем размер буфера в переменную, которую будем вызывать

bufsize:= waveformat.nAvgBytesPerSec*2 div 16;

// размеру буфера сокета присваиваем размер буфера bufsize

IdUDPClient1.BufferSize:=bufsize;

// waveInOpen опишем чуть ниже, как и обещал, WAVE_MAPPER – система

// сама выбирает устройство

waveInOpen(@Wavein,WAVE_MAPPER,addr(waveformat),self.Handle,0,CALLBACK_WINDOW);

// выделяем память под заголовок буфера данных

WaveHdr.lpData:=Pchar(GlobalAlloc(GMEM_FIXED, bufsize));

// присваиваем длину буфера TWaveHdr’у

WaveHdr.dwBufferLength:=bufsize;

// сбрасываем флаги

WaveHdr.dwFlags:=0;

// устанавливаем порт подключения для клиента

IdUDPClient1.Port:= 10090

end;

Что же такое WaveInOpen()?

Функция waveInOpen() открывает имеющееся устройство ввода Waveform Audio для оцифровки сигнала. Типичная ее структура выглядит следующим образом:

function waveInOpen(

lphWaveIn: PHWAVEIN;

uDeviceID: UINT;

lpFormatEx: PWaveFormatEx;

dwCallback,

dwInstance,

dwFlags: DWORD

): MMRESULT; stdcall;

Здесь:

lphWaveIn – указатель на идентификатор открытого Waveform audio устройства. Идентификатор используется после того, как устройство открыто, в других функциях Waveform audio;

uDeviceID – номер открываемого устройства (см. waveInGetNumDevs). Это может быть также идентификатор уже открытого ранее устройства. Вы можете использовать значение WAVE_MAPPER для того, чтобы функция автоматически выбрала совместимое с требуемым форматом данных устройство;

lpFormatEx - указатель на структуру типа TWaveFormatEx

type TWaveFormatEx = packed record

wFormatTag: Word; { format type }

nChannels: Word; { number of channels (i.e. mono, stereo, etc.) }

nSamplesPerSec: DWORD; { sample rate }

nAvgBytesPerSec: DWORD; { for buffer estimation }

nBlockAlign: Word; { block size of data }

wBitsPerSample: Word; { number of bits per sample of mono data }

cbSize: Word; { the count in bytes of the size of }

end;

В этой структуре значения полей следующие:

wFormatTag                 – формат Waveform audio. Мы будем использовать значение WAVE_FORMAT_PCM

(это означает импульсно-кодовая модуляция) другие возможные значения

смотрите в заголовочном файле MMREG.H;

nChannels                    – количество каналов. Обычно 1 (моно) или 2(стерео);

nSamplesPerSec          – частота дискретизации. Для формата PCM – в классическом смысле, т.е.

количество выборок в секунду. Согласно теореме отсчетов должна вдвое

превышать частоту оцифровываемого сигнала. Обычно находится в диапазоне от

8000 до 44100 выборок в секунду;

nAvgBytesPerSec        – средняя скорость передачи данных. Для PCM равна nSamplesPerSec*nBlockAlign;

nBlockAlign                  – для PCM равен (nChannels*wBitsPerSample)/8;

wBitsPerSample           – количество бит в одной выборке. Для PCM равно 8 или 16;

cbSize                         – равно 0. Подробности в Microsoft Multimedia Programmer’s Reference;

dwCallback                   – адрес callback-функции, идентификатор окна или потока, вызываемого при

наступлении события;

dwInstance                   – пользовательский параметр в callback-механизме. Сам по себе не используется

dwFlags                       – флаги для открываемого устройства:CALLBACK_EVENT    dwCallback-параметр –

код сообщения (an event handle);

CALLBACK_FUNCTION            dwCallback – параметр – адрес процедуры-обработчика

CALLBACK_NULL                     dwCallback – параметр не используется

CALLBACK_THREAD               dwCallback – параметр – идентификатор потока команд;

CALLBACK_WINDOW               dwCallback – параметр – идентификатор окна

WAVE_FORMAT_DIRECT         если указан этот флаг, ACM-драйвер не выполняет преобразование данных

WAVE_FORMAT_QUERY         функция запрашивает устройство для определения

поддерживает ли оно указанный формат, но не открывает его

Мы использовали callback функцию в OnWaveMessage(). В последнюю очередь я опишу переменные, которые использовались:

type

TForm1 = class(TForm)

IdUDPClient1: TIdUDPClient;

Button1: TButton;

Edit1: TEdit;

procedure Button1Click(Sender: TObject);

procedure FormClose(Sender: TObject; var Action: TCloseAction);

procedure FormCreate(Sender: TObject);

private

procedure OnWaveMessage(var msg:TMessage); message MM_WIM_DATA;

{ Private declarations }

public

{ Public declarations }

Wavein:HWAVEIN;

WaveHdr:TWaveHdr;

bufsize:Cardinal;

end;

var

Form1: TForm1;

WaveDataLength:integer;

bytes:integer;

device:word;

waveformat: TWAVEFORMATEX;

a:integer;

Так же для работы программы необходимо добавить модуль MMSystem в раздел uses. Клиент готов! Как видите, не так страшен черт, как его малюют! Перед тем как перейти к написанию сервера, я бы вам настоятельно рекомендовал бы покопаться в генофонде всех выше описанных функций и самостоятельно глубже разобраться в том, как они устроены. Так для более углубленного изучения, советую переворошить содержимое таких компонентов из серии ACM как AcmIn, AcmOut. Только самообучением можно чего-нибудь добиться.

А что же сервер?

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

Как обычно, создадим новый проект и вынесем на форму компонент TMemo (name=memo1) (опять же-таки я использовал его в целях определения получения потока данных, перегоняя его в шестнадцатиричный формат), кнопку TButton и IdUDPServerSocket (см. рисунок 2):

Пожалуй, начнем с простого. Напишем ниже приведенный код в обработчике события OnClose() формы:

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);

begin

// завершаем действия

Action:= caFree;

// выключаем сервер

IdUDPServer1.Active:= False

end;

Далее займемся обработчиком события OnClick() кнопки TButton1 (см. код):

procedure TForm1.Button1Click(Sender: TObject);

begin

If button1.Caption='Включить сервер' then Begin

// активируем сокет сервера

IdUDPServer1.Active:= true;

button1.Caption:='Выключить сервер'

end else begin

// деактивируем сокет сервера

IdUDPServer1.Active:= false;

button1.Caption:= 'Включить сервер'

end

end;

Теперь напишем процедуру, которую мы будем использовать для воспроизведения принятого звука:

procedure TForm1.playsound(s:Tstream); // получаемый поток

Var // переменная типа сообщения

msg:Tmessage;

begin

// пока а не равно нашему количеству буферов выполняем следующее

While a<>CWaveBufferCount do Begin

// проверку пользовательской установки на то, что буфер готов к записи

If FHeaders[a].dwUser=0 then begin

// записываем в буфер данные из потока, пришедшего от клиента

s.Read(Fheaders[a].lpdata^,bufsize);

// процедура waveOutPrepareHeader аналогична процедуре waveInPrepareHeader

waveOutPrepareHeader(WaveOut,@FHeaders[a],sizeof(FHeaders));

// Процедура waveOutWrite аналогична процедуре waveInAddBuffer, только она

// осуществляет   воспроизведение данных из буфера

waveOutWrite(WaveOut,@FHeaders[a],sizeof(FHeaders));

memo1.Lines.Add('...Двоичный код потока...');

// обнуляем флаги буфера/ов в цикле

FHeaders[a].dwFlags:= 0;

// уже знакомая нам структура

With FHeaders[a] do begin

dwBufferLength:= bufsize;

dwBytesRecorded:= 0;

dwUser  := 0;

dwLoops:= 1;

// А вот здесь мы присваиваем флагу только что воспроизведенного буфера

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

// циклично используем эти 8 буферов

dwFlags:= WHDR_INQUEUE

end;

// Увеличиваем индекс, чтобы перейти к следующему буферу

inc(a);

// соответственно после воспроизведения и подготовки нам больше не нужен цикл и

// мы выходим из него

exit;

end

end

end;

Процедура разобрана, осталось ей воспользоваться… Как это осуществить? Все просто, достаточно в обработчике события OnUDPRead() idUDPServerSocket-a написать следующий код:

procedure TForm1.IdUDPServer1UDPRead(Sender: TObject; AData: TStream;

ABinding: TIdSocketHandle);

Begin

// если мы воспроизвели последний буфер то, начинаем всё сначала (с первого)

If a = CWaveBufferCount then

a:= 0;

//вызываем нашу процедуру, в скобках пишем наш поток, пришедший на сервер,

//смотрите процедуру сокета.

playsound(Adata);

// определяем сколько байт мы приняли

Bytes:=Bytes + aData.Size;

// показываем это в названии формы

Caption:= 'Принятых байт' + Format('%u', [Bytes]);

// обновляем форму

UpDate

end;

И не забыть при создании формы проинициализировать наши аудиоустройства. Для этого в обработчике OnCreate() формы запишем:

procedure TForm1.FormCreate(Sender: TObject);

begin

bytes:= 0;

WaveOut:= 0;

With WaveFormatOut do begin

nChannels:= 1;

wFormatTag:= WAVE_FORMAT_PCM;

nSamplesPerSec:= 8000;

wBitsPerSample:= 8;

nBlockAlign:= 1;

nAvgBytesPerSec:= 8000;

cbSize:= 0

end;

bufsize:= WaveFormatOut.nAvgBytesPerSec*2 div 16;

For a:= 0 to CWaveBufferCount-1 do

With FHeaders[a] do begin

dwFlags:= WHDR_INQUEUE;

dwBufferLength:= bufsize;

dwBytesRecorded:= 0;

dwUser:= 0;

dwLoops:= 1;

GetMem(Fheaders[a].lpData, bufsize);

end;

IdUDPServer1.BufferSize:= bufsize;

IdUDPServer1.DefaultPort:= 10090;

waveOutOpen(@WaveOut, WAVE_MAPPER, @WaveFormatOut, self.Handle, 0, CALLBACK_WINDOW);

end;

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

Далее осталось описать переменные и константы:

Const

CwaveBufferCount = 8;

type

TForm1 = class(TForm)

IdUDPServer1: TIdUDPServer;

Button1: TButton;

Memo1: TMemo;

procedure IdUDPServer1UDPRead(Sender: TObject; AData: TStream;

ABinding: TIdSocketHandle);

procedure FormCreate(Sender: TObject);

procedure FormClose(Sender: TObject; var Action: TCloseAction);

procedure Button1Click(Sender: TObject);

procedure playsound(s:Tstream);

private

hdr: PwaveHdr;

{ Private declarations }

public

{ Public declarations }

WaveOut:HWAVEOUT;

WaveHdrOut,WaveHdrOut2:TWaveHdr;

WaveFormatOut:tWAVEFORMATEX;

bufsize:word;

FBuffer:Pointer;

FSndBuffer:Pointer;

FHeaders:array[0..CWaveBufferCount-1] of TWAVEHDR;

FBufSize:Cardinal;

end;

var

Form1: TForm1;

bytes:Cardinal;

WaveOut: HWAVEOUT;

WaveHdrOut,WaveHdrOut2: TWaveHdr;

WaveFormatOut: tWAVEFORMATEX;

bufsize:word;

a:integer;

Я не стал описывать процедуру перегонки потока в HEX-формат, так как писал ради передачи данных в TMемо. В конце концов, вы сами запросто можете убрать ненужные строки, относящиеся к ней.

Заключение

Хочу заметить, что размеры буферов сокетов на сервере и клиенте должны быть равны размерам буферов структуры TWaveHdr, иначе вы не получите никаких звуков на выходе, кроме шипения с прерываниями, равными по длительности размеру вашего воспроизводимого буфера. Также для более быстрой реакции на события приема звука используйте меньшие размеры буферов, но и соответственно увеличьте их количество (8-ми вполне хватит). При желании, лучше использовать динамический.

Статья была написана специально для форума Клуба ПРОграммистов www.programmersforum.ru. Исходники тестового проекта (клиента и сервера) прилагаются в виде ресурсов в теме «Журнал клуба программистов. Третий выпуск» или непосредственно в архиве с журналом [5].

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

Ресурсы

. Азбука WIN API http://letitbit.net/download/1868.1502ee9dae8ee96cec9816babb/Azbuka_WIN_API.rar.html

. Описание звуковых функций http://www.delphikingdom.com/asp/viewitem.asp?catalogid=213

. Репозитарий Indy 9: https://svn.atozed.com:444/svn/Indy9 (имя пользователя: Indy-Public-RO)

. Репозитарий Indy 10: https://svn.atozed.com:444/svn/Indy10 (имя пользователя: Indy-Public-RO)

. Модули и проекты, использованные в статье http://programmersclub.ru/pro/pro3.zip

. Обсуждение на форуме разработки прототипа VoIP телефона

http://www.programmersforum.ru/showthread.php?t=91506

Это статья из третьего номера журнала “ПРОграммист”.
Скачать его можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Передача звука по сети. Прототип VoIP телефона

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

ПОИСК ПУТИ

На пути постижения мудрости не надо бояться, что свернёшь не туда.

Пауло Коэльо

Автор Utkin www.programmersforum.ru

Прокладка маршрута называется навигацией. Она бывает двух видов: автономная – когда объект (бот) самостоятельно прокладывает маршрут из одной точки карты в другую, запоминает его индивидуально (либо в общем, хранилище маршрутов для одной группы юнитов), и предварительная – когда маршруты уже проложены во время проектирования карты (опять же автоматически или программистом), или же на этапе загрузки карты игрового мира. Маршрут обычно представляет собой некоторую совокупность точек (или их координат) со связями между ними, то есть это маршрут, проложенный на графе. Сами точки называются вейпоинтами – это углы (или вершины) графа. Соответственно подавляющее большинство алгоритмов поиска пути есть алгоритмы по работе с графами.

Краткий экскурс…

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

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

Предварительный просчет точек осуществлен, например, в игре StarСraft. Это видно если отправить рабочего добывать ресурсы, он смело перемещается через туман войны и по неисследованной области, способен находить подъемы на другой уровень плоскости и сразу определять местоположение моста.

Алгоритм Дейкстры

Этот алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных.

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

Вот образец графа (см. рисунок 1):

Представьте, что нам нужно попасть из точки 1 в точку 5. Сколько имеется путей достижения точки 5? Давайте посчитаем:

а) 1-2-5

б) 1-2-6-5

в) 1-6-5

г)  1-6-2-5

Итого четыре маршрута. Вычислим расстояния по каждому маршруту (суммированием расстояний между точками). Вот расстояния между точками:

а) 1-2    расстояние 6

б) 2-5   расстояние 4

в) 2-6    расстояние 6

г) 6-5    расстояние 5

д) 1-6   расстояние 8

е) 6-2, он же 2-6 расстояние 6

Общее расстояние всего маршрута:

а) 1-2-5             расстояние 6+4=10

б) 1-2-6-5          расстояние 6+6+5=17

в) 1-6-5             расстояние 8+5=13

г) 1-6-2-5          расстояние 8+6+4=18

Самый оптимальный (для нашего примера) является путь а) расстояние всего 10. Если же будут обнаружено два и более маршрутов, имеющих одинаковую длину, то выбирается, как правило, первый (либо заранее продумано, какой из маршрутов, лишь бы выбор был осуществлен).

Также нужно обратить внимание, что на первый взгляд маршруты б) и г) равны (казалось бы, от перемены мест слагаемых сумма не меняется), однако следует не забывать, что идентификаторы здесь не несут математического смысла это просто имена точек. Таким же образом мы могли бы назвать и a, b, c и т.д. Операции идут над расстояниями, а суммы пар расстояний (1-2; 2-6) и (1-6; 2-6) не эквивалентны (не равны) между собой.

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

Перейдем к алгоритму

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

Следующей рассмотрим точку 2 (потому что она ближе к 1 точке). Для нашего графа соседями точки 2 являются 1, 6, 5 и 3. Точку 1 мы рассматривать не будем, поскольку уже было отмечено, что она была просмотрена ранее. Вот расстояния:

. до точки 6 расстояние 6;

. до точки 5 расстояние 4;

. до точки 3 расстояние 5.

Отсюда следует, что ближайшей точкой к вершине 2 будет точка 5, поскольку расстояние до нее минимально, по сравнению с вершинами 6 и 3.

На данном этапе:

. расстояние до точки 1 составляет 0;

. расстояние до точки 2 составляет 6;

. расстояние до точки 5 составляет 10 (6+4);

. маршрут до точки 5 следующий – 1-2-5 (и никакой другой до данной точки более не рассматривается);

. следующей точкой будет являться точка 5;

. точка 2, также как и точка 1 считается отмеченной и больше не рассматривается;

. расстояние до точки 6 (маршрут 1-6) равен 8 (0+8), а не 12 (маршрут 1-2-6, расстояние 6+6), поскольку хоть точка 6 и не отмечена, но текущее расстояние до нее уже было вычислено и оно менее текущего (не забываем, что изначально расстояние до каждой точки равно максимально возможному для данного графа).

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

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

Граф можно представлять многими способами, например, в виде таблицы смежности (ru.wikipedia.org/wiki/Список_ребер). Такой способ представления удобен с математической точки зрения, но абсолютно не удобен с практической. Например, точку можно представить как ее координаты и набор отношений (где отношение можно представить как пару – указатель на точку-соседа и расстояние до точки-соседа). Если отношение представляет собой расстояние между двумя точками в данной системе координат, то его можно вычислять автоматически по формуле вычисления расстояния между двумя точками (школьный курс геометрии), при этом расстояние для системы координат с числом осей более двух вычисляется аналогично по обобщенной формуле. Собственно совокупность точек графа и будут являться самим графом.

Отмеченные точки графа

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

Таблица кратчайших расстояний

Согласно алгоритму изначально расстояние до точек должно представляться максимально возможным расстоянием (за исключением стартовой, до нее расстояние минимально – 0). Затем эти расстояния заполняются в процессе выполнения алгоритма. Также эти расстояния нужны для сравнения имеющихся и предлагаемых расстояний (расстояние до точки 6 для нашего примера).

Маршруты от начальной до остальных точек

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

Заключение

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

Исходники тестового проекта прилагаются в виде ресурсов в теме «Журнал клуба программистов. Третий выпуск» или непосредственно в архиве с журналом [5].

Ресурсы

. Реализация алгоритма Дейкстры http://plagiata.net.ru/?p=90

. Описание алгоритма Дейкстры http://algolist.ru/maths/graphs/shortpath/dijkstra.php

. Математическое и неформальное описание алгоритма Дейкстры

http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры

. Дополнительные материалы http://borisvolfson.h11.ru/show_article.php?article_id=0000020 и

http://www.excode.ru/art6837p1.html

. Модули и проекты, использованные в статье http://programmersclub.ru/pro/pro3.zip

Это статья из третьего номера журнала “ПРОграммист”.
Скачать его можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Поиск пути

С выходом третьего номера журнала [ПРОграммист] у него появился собственный сайт. Разработке этого ресурса и посвящен цикл статей.

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

Первую часть будет вести Егор Горохов aka Revival1002, вторую — Алексей Шульга aka Levsha100, мы будем помогать друг другу в этом нелегком труде. Итак, начнем.

1. Дизайн

Для начала был нарисован PSD шаблон сайта в графическом редакторе Photoshop.  Оттуда же мы потом и «выдирали» картинки для сайта. В результате у нас получилось это (см. рисунок 1):

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

2. Верстка

Для создания закругленных углов использовалось свойство border-radius. К сожалению, пока что свойство работает не во всех браузерах, например в IE 6…8 оно игнорируется. Конечно существуют и альтернативные способы создания круглых углов, но они зачастую требуют до 9 (!) картинок блока (4 угла, 4 стороны и центр). Так как мы «очень ленивые», да и острые углы не очень портят дизайн, мы использовали простейшее решение, с надеждой на то, что вскоре все браузеры будут поддерживать данное свойство…

Для полупрозрачности главного div не было найдено (возможно мы плохо «гуглили») кроссбраузерного решения, поэтому мы пошли на хитрость, создав однопиксельный полупрозрачный png, и поставили его на фон. Но и этот способ, как оказалось имеет свои минусы. Например*, ненавистный всеми дизайнерами/верстальщиками IE6 его игнорирует.

* Комментарий автора.

Кстати, я уже давно не видел людей использующих IE6. Все мои знакомые, даже если они мало понимают в компьютерах (например девушки) используют браузеры типа Opera и Mozilla Firefox. Поэтому причин продолжать верстать под MSIE6 я уже не вижу.

Ознакомится с CSS можно по адресу:
http://procoder.info/style.css

3. Написание скриптов

Для начала, вынесем все наиболее часто используемые переменные в отдельный файл “config.php”, и потом будем его «инклудить» во все скрипты. Мы поместили туда логин\пароль от БД, путь к сайту и т.п. В дальнейшем, если мы захотим изменить что-либо, то это займет всего- лишь несколько секунд, и не потребуется вносить изменения во множество скриптов.

Итак, при заходе на сайт пользователь должен видеть: ленту новостей, журналы доступные для скачивания, гостевую книгу. Реализция происходит практически одинаково. Покажу на примере гостевой книги (см. листинг 1):

<?php

require_once "config.php"; // Подключение файла конфигурации

// Функция обрабатывает строку, и заменяет все bb-коды на html

function bbcodes($str)

{

$bbcode = array(

"/\[b\](.*?)\[\/b\]/is" =] "<strong>$1</strong>",

"/\[u\](.*?)\[\/u\]/is" =] "<u>$1</u>",

"/\[url\=(.*?)\](.*?)\[\/url\]/is" =] "<a href='$1'>$2</a>",

"/\[color\=(.*?)\](.*?)\[\/color\]/is" =] "<font

color='$1'>$2</font>",

"/\[i\](.*?)\[\/i\]/is" =] "<i>$1</i>]",

"/\[quote\](.*?)\[\/quote\]/is" =] "<div

class=\"quote\">$1</div>",

"/\[img\](.*?)\[\/img\]/is" =] "<img src=\"$1\">"

);

$str = preg_replace(array_keys($bbcode), array_values($bbcode),

$str);

return $str;

} // Функция взята из мануалов по PHP

// Подключение к БД

$db = mysql_connect($db_server, $db_user, $db_pass);

mysql_select_db($db_name);

// Выбираем из таблицы table_gb последние 30 записей и

сортируем их по id
$db_query=mysql_query("SELECT * FROM `table_gb` ORDER BY `id`

DESC LIMIT 0 , 30", $db);

while ($res = mysql_fetch_array($db_query)) // Вывод записей

{

echo "<div class=\"guest_comment\"><b>".$res['name']."-

".$res['date']."</b><br>";

echo bbcodes(wordwrap("<pre>".$res['text']."</pre>", 75));

echo "</div><br>";

}

?>

// Тут находится форма, для добавления записей в БД, которая
передает скрипту gb.php данные

А теперь скрипт добавляющий записи в БД (см.листинг 2):

<?php

require_once "config.php";

$db = mysql_connect($db_server, $db_user, $db_pass);

mysql_select_db($db_name);

// Получаем данные и убираем из них спец-символы,

// для защиты от XSS-атак

$name = htmlspecialchars($_POST['name']);

$text = htmlspecialchars($_POST['text']);

$date_array = getdate(time());

$date =
$date_array['mday'].".".$date_array['mon'].".".$date_array['year'];

if (($text=='') or ($text=='Введите текст'))

{

echo "<script>alert('Запись не добавлена.');</script>";

echo '<meta http-equiv="Refresh" content="0;
URL='."$index_path".'">';

}

else

{

if (($name=='Ваше имя') or ($name=='')) {$name='Аноним';}

// Добавляем запись в БД

$db_query = mysql_query("INSERT INTO `table_db` (

`id` ,

`name` ,

`text` ,

`date`

) VALUES ('', '$name', '$text', '$date');", $db);

mysql_close($db);

echo "<script]alert('Запись добавлена');</script>";

echo '<meta http-equiv="Refresh" content="0;
URL='."$index_path".'">';

}

?>

Аналогичным образом выводятся записи для новостей, журналов для закачки и другая информация (см.  рисунок 2):

Подведем предварительные итоги…

Что есть и что планируется? Пока сделано очень мало, и нововведения** будут появляться практически каждый день. Совсем скоро будет система регистрации, что позволит комментировать статьи, новости и выставлять им оценки. У каждого пользователя будет личный кабинет. Создавать отдельный форум для сайта не планируется, так как это совместный проект Клуба ПРОграммистов www.programmersclub.ru и форум уже есть. Существующие алгоритмы тоже будут улучшены. Все предложения оставляйте либо на форуме, либо отправляйте на электронный ящик редакции.

Это статья из третьего номера журнала “ПРОграммист”.
Скачать его можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Разработка ресурса для журнала. Часть 1

Многим из нас знаком советский электретный микрофон типа МКЭ-3, а те, кто не знаком, все равно применяют его или его аналоги в повсеместной практике, даже не догадываясь о замечательных свойствах материала – электрета (поляризованного диэлектрика), используемого в нем.

Не менее примечательна история появления этого замечательного материала… В 1943 году во время боевых действий на Тихом Океане американский флот захватил японский эсминец. Для изучения вражеской техники на корабль прибыли специалисты флота, осмотрели все – от трюма до капитанской рубки. Связист подробно изучил систему телефонной связи, она работала как часы. Одного он не мог понять, как система может работать без источника питания, ни батарей, ни аккумуляторов не было и в помине!

Физики разобрались в принципе работы телефонной связи на японском корабле. Ее работа стала возможной благодаря открытию японского физика Егучи, еще в 1922 году получившему новые материалы – электреты (с 1922 года работу с электретами Егучи проводил в обстановке строжайшей секретности для Министерства обороны Японии). Егучи получал электретные материалы из смеси смолы карнаубской пальмы и воска. Нагрев смесь до расплавленного состояния Егучи подал на нее напряжение 10 кВ, после застывания таблетка электрета сохраняла электростатический заряд высокой напряженности в течение нескольких часов (см. рецептуры). Современные электреты могут сохранять заряд до 100 лет, величина заряда достигает 5*10-8 Кл/см2.

В настоящее время электреты получают из таких материалов как: политетрафторэтилен (макс. Поверхностный потенциал 527 В), полиметилметакрилат или органическое стекло (3965 В), рутиловая керамика, смолы, воск,  полимеры, титанаты щелочноземельных металлов и даже растворы органических веществ в летучих растворителях.

Рецептура N1

Нагреваем 2-5 г касторового масла до температуры 75-90 °С и высыпаем в него при помешивании 50 г мелкоизмельченной канифоли (если возится неохота, то возьмите и используйте парафин вместо канифоли и масла, расплавьте его и поместите между электродами – после остывания электрет готов). После чего расплав наливаем в плоскую баночку (стеклянную) или на предметное стекло и помещаем его между электродами, на которые подается напряжение от высоковольтного выпрямителя (5-10 кВ) или электростатической машины. Толщина слоя диэлектрика должна быть менее 4 мм. После остывания канифоль достается из баночки. Электрет готов.

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

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

Рецептура N2

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

Это заметка с третьего выпуска журнала “ПРОграммист”.
Скачать этот выпуск можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Этот удивительный электрет

Новые модификации анализаторов спектра в реальном времени с технологией обработки изображений сигнала DPX™ представила компания Tektronix Inc. Модели серий RSA3000B и RSA6100В поставляются в двух исполнениях с разными диапазонами перекрываемых частот: 0-3 ГГЦ или 0-8 ГГц

Технология обработки изображений сигналов DPX, позволяет просматривать спектр в режиме реального времени, при скорости обработки более 48000 измерений спектра в секунду. Процессор обработки изображений сигналов с эффектом послесвечения позволяет выявлять в динамических сигналах отклонения и частоту их повторения, а также обеспечивает мгновенную обратную связь при временных изменениях сигналов.  Благодаря этому можно быстро просмотреть на экране переходные процессы и сигналы, которые раньше рассмотреть было невозможно, поскольку они маскировались
другими сигналами, или для их выявления приходилось проводить автономный анализ, занимающий много времени. Основные виды анализируемых тестовых сигналов (W-CDMA, GSM/EDGE, CDMA, HSDPA, TD-SCDMA, WLAN 802.11a/b/g, HDTV и даже радиочастотных меток RFID) представлены на скриншотах, а видеотестирование вы можете просмотреть тут http://raxp.radioliga.com/cnt/s.php?p=dpx.wmv

Это заметка с третьего выпуска журнала “ПРОграммист”.
Скачать этот выпуск можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Новые модификации анализаторов спектра

Спин атома кобальта смогли «сфотографировать» исследователи из университета Огайо. Несмотря на то, что спин (собственный момент импульса квантовой частицы) является ключевым свойством квантовых частиц и используется в квантовых вычислениях уже десятки лет, его изображение представлено человечеству впервые. Физики использовали специально созданный сканирующий туннельный микроскоп, с помощью которого перемещали атомы кобальта по марганцевой подложке. Атомы кобальта при этом меняли свой спин и на изображениях четко видна зависимость высоты и формы пиков атомов от направления спинов. Исследования показывают, что ученые могут наблюдать и управлять спинами атомов, что может привести к созданию электроники атомных размеров и новым направлениям спинотроники. Однако до практического применения полученных результатов пока далеко. Для этого необходимо научиться получать необходимый эффект при комнатной температуре, а не охлаждать пластину марганца жидким гелием  до 10° К

Это заметка с третьего выпуска журнала “ПРОграммист”.
Скачать этот выпуск можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Спин атома кобальта смогли «сфотографировать»

Нанофотонный лавинный фотодетектор изобрели ученые корпорация IBM, что делает возможным создание компьютерных чипов, в которых сигналы между транзисторами и ядрами будут передаваться при помощи импульсов света. В основе работы нового фотодетектора лежат свойства полупроводника. При поступлении на устройство одного импульса света в его материале высвобождается несколько носителей зарядов, которые затем высвобождают другие носители, создается известный эффект лавины. Вспомните наши отечественные лавинные транзисторы ГТ338. Устройство способно принимать оптический сигнал со скоростью 40 Гбит/с и при минимальных помехах выдавать по 400 млрд бит в секунду цифровой информации при напряжении всего 1.5В.

Это заметка с третьего выпуска журнала “ПРОграммист”.
Скачать этот выпуск можно по ссылке.
Ознакомиться со всеми номерами журнала.