О бильярде с Microsoft Visual C++ 5.0

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

"Фирменные" примеры, помогающие освоению среды программирования, - непременная принадлежность современных пакетов разработчика. Поставляются они и с системой программирования Visual C++ 5.0 корпорации Microsoft. Однако это именно учебные примеры, практические их возможности весьма ограничены.

Ниже будет по шагам описана процедура модификации одного из таких примеров, превращающая его в "трехмерную" программу. Применяемые приемы универсальны и подходят для решении практически любых задач на Visual C++. Вместе они составляют особую технологию разработки программ, называемую далее технологией конечноавтоматного параллельного программирования (КА-технология).

Стандартный пример, который мы будем рассматривать, называется MDI (от Multiple Document Interface - многодокументный интерфейс). Он демонстрирует простейшие приемы работы с графическим контекстом устройств и построение программы с многодокументным интерфейсом. Получающаяся программа порождает окна двух типов: с сообщением "Hello World!" и с мячиком, который летает внутри окна, отскакивая от его границ. Первые окна не очень интересны, зато вторые можно развивать, ставя более сложные задачи.

Для создания работающего примера вам потребуется библиотека FSA (Finite State Automation), обеспечивающая работу с КА-технологией в среде Windows. Она имеется в составе пректа MDI, приложенного к электронной версии статьи (http://www.osp.ru/pcworld/1998/01/fsamdi.zip; можно также попытаться написать нужные функции самостоятельно или обратиться к автору этих строк). Однако разбираемый пример достаточно элементарен, и для понимания сути статьи реализовывать его не обязательно.

Наша цель - FSA

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

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

В КА-технологии поведение каждого объекта задается моделью конечного автомата, а сами автоматы на формальном уровне объединены в сеть, что позволяет описывать также параллельное функционирование объектов. Поэтому, определив мячик как КА-объект, мы сможем "внедрить" в окно любое число мячиков.

Библиотека классов FSA - это своего рода надстройка над операционной средой и языком Си++, обеспечивающая интерпретацию конечных автоматов и среду для их параллельного функционирования. Из FSA нам понадобятся класс TNetFsa, отвечающий за автоматную среду, которая управляет параллельной работой КА-объектов, класс LArc, описывающий таблицу переходов конечного автомата (т. е. собственно поведение объекта), и LFsaAppl - базовый класс, инкапсулирующий данные и методы автоматного объекта.

Среди методов LFsaAppl различаются предикаты и действия. Содержательно первые отвечают за анализ, вторые - за преобразование данных. Предикаты, обозначаемые как x1, ..., xN, соответствуют входным каналам автомата и возвращают логическое значение. Действия, обозначаемые как y1, ..., yN, соответствуют переходам между внутренними состояниями автомата и не возвращают никаких значений.

Автомат задается таблицей переходов. Начальное его состояние определяется первой строкой этой таблицы, заключительное (если оно есть) носит имя "00". Безусловный переход помечается в таблице прочерком на месте предикатов. Если автомат оказывается в состоянии, для которого переход не определен, он не производит никаких действий.

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

Конечные автоматы функционируют в дискретном времени. Благодаря общей среде и встроенному механизму отсчета времени методы КА-объекта оказываются связаны между собой общим алгоритмом поведения. Минимальная физическая продолжительность одного такта формального автоматного времени определяется временем, фактически необходимым для запуска и выполнения предикатов и действий, т. е. зависит от качества реализации библиотеки FSA и быстродействия вычислительной системы. Естественно, чем она меньше, тем быстрее сможет работать автоматная модель и тем точнее удастся воспроизводить с помощью этой модели поведение реального объекта. При необходимости FSA позволяет увеличивать продолжительность такта, замедляя таким образом работу автомата.

Редактирование основного класса программы

Начнем с внесения изменений в основной класс программы CMdiApp, производный от CWinApp. Нам необходимо включить в него виртуальный метод OnIdle и две переменные. Первая - pNetFsa - представляет собой указатель на объект типа TNetFsa - автоматную среду для поддержки параллельной работы Windows-объектов. Вторая - lCountTime - это длинное целое число, определяющее продолжительность одного такта работы автоматной среды (нулевое значение соответствует минимальной продолжительности). Кроме того, для удаления дополнительно созданных объектов потребуется деструктор класса (в исходном примере его нет).

Метод OnIdle запускается операционной средой, когда очередь сообщений программы пуста, и выполняет один или несколько тактов автоматной среды. Модифицированное определение класса CMdiApp приведено в листинге 1.

Листинг 1. Описание класса CMdiApp

class CMdiApp : public CWinApp
{
public:
             ~CMdiApp() ;
        TNetFsa* pNetFsa;
        long lCountTime;
        CMdiApp();
public:
        virtual BOOL InitInstance();
             virtual BOOL OnIdle(LONG lCount);
        DECLARE_MESSAGE_MAP()
};

Реализация нового класса (конструктор, деструктор и метод OnIdle) показана в листинге 2. Конструктор создает экземпляр автоматной среды, которому через переменную lCountTime передается скорость работы (в данном случае - максимальная). Деструктор при завершении работы программы удаляет созданный в конструкторе объект автоматной среды. Метод PerformanceQuantum, определенный в классе TNetFsa, выполняет один такт работы автоматной среды при каждом запуске метода OnIdle.

Листинг 2. Реализация класса CMdiApp

CMdiApp::CMdiApp()
{
        lCountTime=0;
        pNetFsa= new TNetFsa(&lCountTime);
}

CMdiApp::~CMdiApp()
{
        delete pNetFsa;
}

BOOL CMdiApp::OnIdle(LONG lCount)
{
             pNetFsa->PerformanceQuantum();
        CWinApp::OnIdle(lCount);
        return TRUE;
}

Изменения, которые были сделаны на этом шаге, не затрагивают прикладного алгоритма и, следовательно, подходят для любого примера. Основной класс для MDI-приложений остался таким же стандартным, каким был исходный.

Редактирование прикладного класса

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

Перейдем теперь к алгоритмической стороне прикладной задачи; естественно, мы будем модифицировать ее в сторону качественного улучшения. Здесь возможно множество вариантов. Несложно было бы, скажем, наделить автоматными свойствами класс CBounceWnd из стандартного примера. Однако мы применим другой, более логичный подход: создадим отдельный класс для объекта-мячика, а классу-окну оставим только функции создания мячиков.

Назовем новый класс TBounce и сделаем его производным от класса LFsaAppl, инкапсулирующего автоматные свойства. Члены-данные, необходимые для задания характеристик самого мячика (размера, положения, цвета и т. д.), перенесем в TBounce из класса CBounceWnd (см. листинг 3). Обратите внимание на указатель pApp, необходимый для обеспечения более простого доступа к автоматной среде из объекта.

Листинг 3. Класс TBounce (определения)

class CMdiApp;
class TBounce : public LFsaAppl

{
public:
        TBounce();
        TBounce(CWnd* pW, int nNum, CSize sz);
        virtual ~TBounce();
        void SetNum(int nNum);
        int GetNum();
        void Size(CSize sz);
        void Color (COLORREF nColor);

public:
        COLORREF m_clrBall;
protected:
        int nNumBounce;
        CWnd*   pParentWnd;
        CMdiApp* pApp;
        void y1();
        void y2();

        CPoint m_ptPixel;    // pixel size
        CSize m_sizeRadius;  // radius of ball
        CSize m_sizeMove;    // move speed
        CSize m_sizeTotal;   // total size for ball bitmap
        CPoint m_ptCenter;   // current center for the ball

        // for replicating bouncing ball
        CBitmap m_bmBall;

        void MakeNewBall();
};
typedef vector TIArrayBounce;
typedef vector::iterator TIIteratorBounce;

Функции y1 и y2 соответствуют действиям автомата, реализующего поведение мячика. Для описания этого поведения достаточно автомата с двумя состояниями - обозначим их как b1 и b2. При переходе от b1 к b2 выполняется действие y1, при переходе от b2 к b1 - действие y2. Соответствующая таблица переходов задается так:

LArc BounceTBL[] = {
LArc("b1","b2", "-", "y1"),
LArc("b2","b1", "-", "y2"),
LArc()
};

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

Листинг 4. Конструктор класса TBounce.

TBounce::TBounce(CWnd* pW, int nNum, CSize sz): LFsaAppl(BounceTBL)
{
  pParentWnd = pW;
  m_clrBall = RGB(0,0,0);

  CDC* pDC = pParentWnd->GetDC();
  m_ptPixel.x = pDC->GetDeviceCaps(ASPECTX);
  m_ptPixel.y = pDC->GetDeviceCaps(ASPECTY);
  pParentWnd->ReleaseDC(pDC);

  SetNum(nNum);      //  присвоить мячику номер
  Size(sz);          //  определить его размер и положение

  pApp = (CMdiApp*)AfxGetApp();
  LoadFSA(pApp->pNetFsa,1);    //   подключение объекта к среде
  pApp->pNetFsa->go_task();    //   запуск объекта в работу
}

Коды действий y1 и y2 (см. листинг 5) полностью основаны на методе OnTime стандартного примера: y1 рисует мячик, а y2 вычисляет для него следующее положение. Можно было бы, конечно, обойтись и одним действием, которое в этом случае полностью соответствовало бы методу из примера. Метод разбит на две части, во-первых, чтобы отделить работу с графикой от вычисления положения мячика, а во-вторых, чтобы "усложнить" автомат в учебных целях.

Листинг 5. Рисование и вычисление положений мячика

void TBounce::y1() //      рисование мячика
{
   if (m_bmBall.m_hObject == NULL)
     return;      // no bitmap for the ball
   CClientDC dc(pParentWnd);
   CBitmap* pbmOld = NULL;

   CDC dcMem;
   dcMem.CreateCompatibleDC(&dc);
   pbmOld = dcMem.SelectObject(&m_bmBall);

   dc.BitBlt(m_ptCenter.x - m_sizeTotal.cx / 2,
     m_ptCenter.y - m_sizeTotal.cy / 2,
     m_sizeTotal.cx, m_sizeTotal.cy,
     &dcMem, 0, 0, SRCCOPY);

   dcMem.SelectObject(pbmOld);
   dcMem.DeleteDC();
}

void TBounce::y2() // вычисление следующего положения мячика
{
   CRect rcClient;
   pParentWnd->GetClientRect(rcClient);

   m_ptCenter += m_sizeMove;

   if ((m_ptCenter.x + m_sizeRadius.cx >= rcClient.right) ||
       (m_ptCenter.x - m_sizeRadius.cx <= 0))
   {
     m_sizeMove.cx = -m_sizeMove.cx;
   }

   if ((m_ptCenter.y + m_sizeRadius.cy >= rcClient.bottom) ||
       (m_ptCenter.y - m_sizeRadius.cy <= 0))
   {
     m_sizeMove.cy = -m_sizeMove.cy;
   }
}

Методы MakeNewBall, Size и Color повторяют соответствующие методы класса CBounceWnd с тем отличием, что вместо указателя на оконный объект в них используется переменная pParentWnd - указатель на окно, создавшее шарик.

Применение библиотеки STL

Создание специального класса для мячика упростило класс CBounceWnd из стандартного примера. Он теперь отвечает только за создание объектов-мячиков и управление ими. Чтобы реализовать эти функции достаточно компактно, мячики нужно объединить, например, создав массив указателей на соответствующие объекты.

Для создания массива воспользуемся библиотекой STL (Standard Template Library - стандартная библиотека шаблонов). Она имеется в составе компиляторов, поставляемых разными фирмами, и тем самым позволяет создавать легко переносимые программы1.

Описание класса TBounce (см. листинг 3) содержит два оператора typedef; первый определяет сокращенную запись типа для массива указателей на объекты TBounce, второй - для соответствующего итератора. Чтобы включить массив мячиков в определение класса CBounceWnd, добавим туда строку

TIArrayBounce IArrayBounce;

Теперь можно легко создать массив, например из трех мячиков, включив несколько дополнительных строк в метод OnCreate (листинг 6).

Листинг 6. Создание массива из трех мячиков

CRect r;
   GetClientRect(r);
   CSize szR = r.Size();

   IArrayBounce.push_back(new TBounce(this, 1, szR));
   IArrayBounce.push_back(new TBounce(this, 2, CSize(szR.cx/2,szR.cy/2)));
   IArrayBounce.push_back(new TBounce(this, 3, CSize(szR.cx/3,szR.cy/3)));

После этого доступ к мячикам осуществляется уже совсем просто. В листинге 7 приведен модифицированный вариант метода OnSize, который запускается при изменении MDI-окна программы и на который возложено оперативное изменение размера мячиков.

Листинг 7. Модифицированный метод OnSize

void CBounceWnd::OnSize(UINT nType, int cx, int cy)
{
  if (!IArrayBounce.empty())  {
    TIIteratorBounce iterBounce; int n=1;
    iterBounce = IArrayBounce.begin();
    TBounce* currentBounce= *iterBounce++;
    currentBounce->Size(CSize(cx/n,cy/n));
    while (iterBounce != IArrayBounce.end()) {
      currentBounce= *iterBounce++;  n++;
      currentBounce->Size(CSize(cx/n,cy/n));
      }
    }

  CMDIChildWnd::OnSize(nType, cx, cy);
}

Аналогичные изменения (с заменой метода Size на метод Color) вносятся в метод OnColor, а также в деструктор, удаляющий динамически созданные объекты-мячики.

Таймер

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

Листинг 8. Обработка прерываний от таймера

void CBounceWnd::OnTimer(UINT /* wParam */)
{
  for (int n=0; n<=50; n++)
  {
  pApp->pNetFsa->PerformanceQuantum();
  }
}

Число тактов, выполняемых при получении одного сообщения, в примере выбрано равным 50; это предельное значение для процессора Pentium-100 с 24 Мбайт ОЗУ: при дальнейшем повышении коэффициента окно не успевает перерисовываться. Чтобы еще увеличить скорость, необходимо использовать специальные приемы работы с графикой.

От теннисного мячика к бильярдным шарам

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

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

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

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

КА-технология предлагает более эффективное решение системных проблем, а часто помогает и при описании физической стороны задачи.

Лучшее - враг хорошего?

Итак, приобрел ли пример новые качества, из-за которых следовало затевать весь этот сыр-бор? Безусловно. Перечислим, чего нам удалось добиться.

1. Мы улучшили структуру задачи, разделив функции прикладного окна и объекта, который в нем создается.

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

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

4. Освободившись от оков таймера, программа более чем в сорок раз увеличила скорость работы! И это не предел, так как она автоматически учитывает аппаратные и алгоритмические нюансы, работая с максимально возможной скоростью.

5. Автоматная среда просто и эффективно организует параллельную работу, которую сложно, да и накладно организовывать стандартными средствами.

Автоматная технология программирования, безусловно, требует определенного понимания основ теории конечных автоматов, но эти основы просты и интуитивно понятны.

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

Главный эффект от применения КА-технологии, может быть, не вполне очевидный в рамках приведенного примера, связан с переходом от расплывчатых системных понятий (механизм обработки сообщений, методы создания параллельных процессов) к строгой теории и формальной модели. Он ярче проявляется на более сложных задачах, таких как синхронизация параллельных объектов (см. пример из [3]).

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

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