Задача Майхилла для Microsoft Visual C++
ОГЛАВЛЕНИЕ
Алгоритм поведения и автоматная модель стрелка
На выстрел в воздух закричал: "Кончай дурить!"
Я чуть замешкался и, не вступая в спор,
Чинарик выплюнул - и выстрелил в упор.
В. Высоцкий
В задаче Майхилла необходимо определить, как нужно действовать стрелкам, построенным в шеренгу, чтобы одновременно открыть стрельбу, если команда "Огонь!" (или "Пли!") подается крайнему в шеренге, а обмен информацией разрешается только между соседями.
Из известных решений данной задачи своей простотой и, главное, "автоматным" подходом привлекает приведенное в работе [2]. Оно заключается в том, что каждый стрелок должен руководствоваться следующим набором указаний.
1. Если ты левофланговый и получил приказ "Шеренга, пли!", то запомни число 1 - свой порядковый номер - и ровно через секунду сообщи его соседу справа.
2. Если ты неправофланговый и сосед слева сообщил тебе число V, запомни число V+1 - свой порядковый номер - и ровно через секунду сообщи его соседу справа.
3. Если ты правофланговый и сосед слева сообщил тебе число n-1, то ровно через секунду ответь ему: "Готов!" и приступай к обратному счету в уме: n, n-1, n-2, ..., отсчитывая по одному числу в секунду.
4. Если ты не правофланговый и сосед справа доложил тебе: "Готов!", то ровно через секунду приступай к обратному счету в уме: V, V-1, V-2, ..., где V - твой порядковый номер, отсчитывая по одному числу в секунду. При этом, если V>1, т.е. если ты не левофланговый, то ровно через секунду после получения сообщения от соседа справа доложи: "Готов!" соседу слева.
5. Досчитав до нуля, стреляй!
Аналогичные указания даются, когда приказ получен правофланговым.
Несложно показать, что решение не зависит от выбранного временного интервала. Более того, этот интервал может быть и "плавающим" - лишь бы он был одинаковым для всех стрелков на каждом шаге счета. Благодаря данному свойству алгоритм легко реализовать в рамках сетевой автоматной модели.
На рисунке показан КА, моделирующий поведение стрелка. Стрeлки соответствуют синхронизирующей информации, которая поступает к стрелку от его соседей слева и справа. Предикаты и действия автомата можно условно описать следующим образом:
// Предикаты
x1 Состояние соседа слева "Огонь!"?
// Команда "Огонь";
x2 Состояние соседа справа "Готов!"?
x3 Свой номер не равен нулю?
// Действия
y1 Установить свой номер: взять номер
соседа слева
и увеличить на 1
y2 Уменьшить свой номер на 1
y3 Произвести выстрел
Кстати, эти строки в дальнейшем можно превратить в комментарии к операторам "автоматной программы".
Программная модель стрелка
Имея алгоритм решения задачи и модель поведения стрелка, можно приступить к программированию. Заголовочный файл и реализация класса "Стрелок" (Rifleman) показаны в листинге 1.
У класса CRifleman, порожденного из автоматного класса LFsaAppl, имеется три предиката, три действия и таблица переходов автомата. Находясь в начальном состоянии "Сон" ("солдат спит - служба идет"), стрелок ждет команды "Огонь!", которой соответствует одноименное внутреннее состояние соседа слева (адрес соседа находится в указателе pFsaLeftMan). Анализ такой ситуации в автомате выполняет предикат x1.
При поступлении команды "Огонь!" автомат выполняет действие y1 и переходит в состояние "Огонь". Действие y1 присваивает автомату номер на единицу больше, чем у соседа слева, а состояние "Огонь" сигнализирует соседу справа о том, что дана команда открыть стрельбу.
Находясь в состоянии "Огонь", стрелок ожидает, чтобы сосед справа (адрес которого хранится в указателе pFsaRightMan) перешел в состояние "Готов", определяя соответствующий момент по истинности предиката x2. Когда это случается, он сам переходит в состояние "Готов" и выполняет действие y2, т. е. уменьшает на единицу свой номер.
Затем начинается автономная работа стрелка - уменьшение на единицу своего номера при каждом такте работы автомата. При равенстве номера нулю автомат переходит в состояние "Выстрел". При этом выполняется действие y3.
Состояние "Выстрел" послужит сигналом для пули, которая начнет свой "разящий полет" от одной границы окна к другой (напомним, что в качестве пули мы используем мячик из статьи [1]). О роли действий y3, y4, y5 и предиката x4 будет рассказано в разделе о стрельбе очередями.
Программная модель командира
В формулировке задачи нет ни слова о том, откуда берется команда. Будем считать, что ее подает командир и что он делает это, переходя во внутреннее состояние "Огонь". Заголовочный файл и реализация методов для класса "Командир" (Officer) представлены в листинге 2.
Алгоритм функционирования командира прост (но роль его важна!): это циклические переходы из состояния "Сон" в состояние "Огонь". Из "Сна" командира можно вывести принадлежащим ему методом SetCommand.
Перекуем мячи на пули
Теперь превратим мячик в пулю, придав ему новый алгоритм поведения. Для этого введем в конструктор мячика параметр - адрес таблицы переходов. Отметьте, кстати, что мы меняем алгоритм работы объекта, не меняя его методов, - прием, почти невозможный в обычном программировании.
Кроме того, как объекту некоторого контейнера библиотеки STL, классу необходимо добавить перегруженные операторы ==, !=, > и <.
Для связи со стрелком введены ссылка и метод, позволяющий ее установить. Анализ внутреннего состояния стрелка, к которому "прикреплена" пуля, при наступлении состояния "Выстрел" выполняет предикат x1. Предикат x2 определяет условие достижения пулей границы окна. Действие y4 введено для установки пули в исходную позицию в окне отображения. Метод SetCenter помещает бывший мячик (ныне - пулю) в заданную точку, а метод SetMove задает шаг перемещения по координатным осям (см. листинг 3).
В начальном состоянии st пуля ожидает события "Выстрел". Когда оно происходит, пуля вылетает и переходит в состояние b1. В этом состоянии она пребывает до тех пор, пока не достигнет границы окна, а затем возвращается в состояние st и ждет следующего выстрела (эдакая пуля-бумеранг).
Вместе весело шагать ...
Итак, все "общество" в сборе. Есть пуля, стрелок и командир. Их нужно объединить в цепь - единую систему, способную выполнить поставленную задачу. Дадим классу "Цепь" имя CchainShot (листинг 4).
Данный класс создает объект "Командир", а также массивы объектов "Стрелок" и "Пуля" - соответственно IArrayRifleman и IArrayBullet. Связи между порожденными объектами организует метод SetLink.
Метод OnSize должен вызываться сразу после создания цепи стрелков. Он служит для задания размеров мячиков-пуль, установки их начального положения и определения шагов перемещения по координатным осям за один такт автоматного времени.
Методы GetAddrRifleman и GetAddrBullet возвращают адреса стрелков и пуль по их номерам из массивов. При организации связей для каждого стрелка ищется пуля с таким же номером, как у него.
Организация связей заключается в присвоении значений указателям, входящим в состав объектов "Стрелок" и "Пуля". При этом для первого стрелка соседом слева является командир, а для последнего указатель на соседа справа имеет значение Null.
Батарея, огонь!
Коли поняли приказ -
Выполняйте сей же час!
Л. Филатов. Про Федота-стрельца, удалого молодца
Объект "Цепь стрелков" создается в теле метода OnCreate класса CFireView. При вызове метода OnSize вызывается одноименный метод объекта "Цепь стрелков", выполняющий начальную настройку цепи.
С помощью редактора ресурсов Visual C++ введем в основное меню программы команды для открытия огня и управления скоростью движения пуль. Программный код методов, связанных с этими пунктами меню, приведен в листинге 5.
Обратите внимание на то, что автоматные модели, включая и модели стрелков, сразу же после создания в методе OnCreate начинают работать. А управление скоростью движения пуль реализовано с помощью механизма управления скоростью работы сетевой автоматной среды (методы OnFast и OnSlow). Объект TNetFsa создается в основном классе программы CFireApp (подробнее см. [1], раздел "Редактирование основного класса программы").
Вот пуля пролетела, и ага, или А очередями слабo,?!
В основном варианте программы стрелки выпускают по одной пуле. А как сделать, чтобы они были готовы стрелять в любой момент? Или, по-другому, как организовать стрельбу очередями?
Оказывается, для этого достаточно внести в классы "Стрелок" и "Пуля" совсем небольшие изменения. Полностью новые классы приведены в примере, прилагаемом к электронной версии этой статьи здесь же мы рассмотрим лишь соображения, лежащие в основе реализации "автоматной" стрельбы.
Во-первых, пуля должна быть выпущена точно в нужный момент. Более всего для этого подходит действие y3 стрелка, позволяющее создать динамический объект-пулю. Пусть сам стрелок после выстрела переходит к ожиданию новой команды. Тогда действие y3 приобретет вид, показанный в листинге 6.
Во-вторых, объекту "Стрелок" следует передать адрес окна отображения, который он, в свою очередь, передаст объекту "Пуля" (см. листинг 6).
И в-третьих, необходимо придать пуле способность распознавать выстрел в автоматическом режиме, что можно сделать, присваивая ей номер, равный нулю. Кроме того, такая пуля должна самоуничтожаться, достигнув границы окна.
Таблица переходов для данного варианта алгоритма приведена в листинге 7. Подчеркнем, что при переходе КА в состояние "00" автоматный объект удаляется из сетевой автоматной среды.
Проделав описанные изменения, можно, наконец, стрелять очередями. Чтобы выпустить несколько пуль подряд, нужно прежде, чем первая пуля достигнет границы окна, дать требуемое число раз команду Fire в меню программы Command.
Меню позволяет также задать скорость полета пули, выбрав пункт Slow или Fast (по умолчанию действует Fast). В окончательном варианте пули, входящие в массив, имеют вид известных мячиков, а "автоматные" - стилизованных под пулю эллипсов.
"Разбор полетов"
Грянул выстрел в тишине,
Взвил воронью стаю,
На войне как на войне -
Иногда стреляют.
А. Розенбаум
Итак, используя минимум понятий и средств, мы за два шага (первый - в работе [1], второй - здесь) превратили весьма ограниченный по своим возможностям исходный пример, предложенный программистами Microsoft, в более интересный, решающий к тому же весьма актуальную и не такую уж простую проблему синхронизации параллельных процессов.
Кроме того, задача Майхилла по духу ближе разработчикам игровых программ, которые часто используют модель КА для описания поведения персонажей[4]. Им в этот раз особое внимание и поклон!
Итак, решая задачу Майхилла, мы:
- увидели, насколько эффективным и простым может быть решение нетривиальных проблем с использованием формальных моделей (попробуйте решить рассмотренную задачу обычными "фирменными" средствами!);
- познакомились с тем, как можно изменить алгоритм работы объекта, модифицировав таблицу переходов;
- узнали, как автоматически удалять автоматные параллельные процессы (раньше мы умели только порождать их);
- научились создавать информационные связи между автоматными объектами и синхронизировать поведение объектов с помощью их внутренних состояний;
- используя параллелизм среды и динамическое порождение объектов, смоделировали более сложную ситуацию, не предусмотренную исходной задачей;
- создали "скелет" задачи о системе из множества объектов с информационными связями между ними; он применяется как в рассмотренных ранее задачах о триггере и о мячиках, так и в нынешней задаче о стрельбе.
Пуля может быть "дурой", а может обладать "интеллектом" ПТУРСa. Так, можно резко повысить эффективность поражения целей стрелками, научив их стрелять еще и "веером". Поведение стрелков можно усложнить, заставив их передвигаться, взаимодействовать, стрелять одиночными и очередями. При разборе примера обратите внимание на то, как реализуется формирование паузы между пулями с помощью "автоматной задержки" CFDelay. Задержка - еще один вариант использования автоматных подпрограмм.
В примере стрельба очередью организуется с помощью дополнительных действий стрелка y4, y5 и предиката x4, а свойство класса стрелка nLengthQueue определяет длину очереди из пуль. Необходимые изменения внесены и в таблицы переходов пули и стрелка.
Возможны и другие варианты развития примера - были бы время и желание (и заказчики, конечно!). Со временем бывает туго, но одна из целей FSA-библиотеки - помочь его сберечь. Удачной вам охоты (с автоматами) в "программных джунглях" и до новых встреч!
Листинг 1
Программная модель стрелка
extern LArc RiflemanTBL[];
class CRifleman : public LFsaAppl
{
public:
int GetNumber();
void SetNumber(int n);
void SetLink(CRifleman *pFsaLeft,
CRifleman
*pFsaRigtht);
CRifleman *pFsaRightMan;
CRifleman *pFsaLeftMan;
CRifleman();
CRifleman(int n, CWnd* pW, LArc
*pTBL=RiflemanTBL);
virtual ~CRifleman();
bool operator==(const CRifleman
&var) const;
bool operator<(const CRifleman
&var) const;
bool operator!=(const CRifleman
&var) const;
bool operator>(const CRifleman
&var) const;
protected:
CWnd* pParentWnd;
CFireApp *pApp; // указатель на объект
// основного класса программы
int x1(); // Is fire?
int x2(); // Is ready?
int x3(); // Number is equal to zero? Shot!
int x4(); //
void y1(); // To place number.
void y2(); // To reduce number by unit.
void y3(); // Gunshot
void y4(); //
void y5(); //
int nNumber;
int nSaveNumber;
int nLengthQueue; // Length of queue.
int nCurrentQueue; //
};
typedef vector<CRifleman*>
TIArrayRifleman;
typedef vector<CRifleman*>:
:iterator TIIteratorRifleman;
extern LArc RiflemanTBL[];
CRifleman::CRifleman():LFsaAppl() { }
CRifleman::CRifleman(int n, CWnd* pW,
LArc* pTBL):
LFsaAppl(pTBL)
{
pParentWnd = pW;
pFsaRightMan = NULL;
pFsaLeftMan = NULL;
nNumber = n;
nLengthQueue = 5;
nCurrentQueue = nLengthQueue;
if (pParentWnd)
{
pApp = (CFireApp*)AfxGetApp();
FLoad(pApp->pNetFsa,1);
}
}
bool CRifleman::operator==(const CRifleman
&var) const
{
if (nNumber==var.nNumber) return true;
else return false;
}
void CRifleman::SetLink(CRifleman
* pFsaLeft, CRifleman *
pFsaRigtht)
{
pFsaRightMan = pFsaRigtht;
pFsaLeftMan = pFsaLeft;
}
LArc RiflemanTBL[] = {
LArc("Сон", "Огонь", "x1", "y1"),
LArc("Огонь", "Готов", "x2", "y2"),
LArc("Готов", "Готов", "x3", "y2"),
LArc("Готов", "Выстрел", "^x3", "y3y4"),
LArc("Выстрел", "Выстрел", "x4", "y3y5"),
LArc("Выстрел", "Сон", "^x4", "-"),
LArc()
};
int CRifleman::x1()
{
if (!pFsaLeftMan) return false;
return string((pFsaLeftMan)-
>FGetState()) == "Огонь";
}
int CRifleman::x2()
{
if (!pFsaRightMan) return true;
else return string((pFsaRightMan)-
>FGetState()) ==
"Готов";
}
int CRifleman::x3() { return nNumber; }
int CRifleman::x4() { return nCurrentQueue; }
void CRifleman::y1()
{
int n = pFsaLeftMan->GetNumber();
SetNumber(n+1);
}
void CRifleman::y2() { nNumber-; }
void CRifleman::y3() { }
void CRifleman::y4()
{
nCurrentQueue = nLengthQueue;
}
// формирование задержки между выстрелами
void CRifleman::y5()
{
CFDelay *pCFDelay;
pCFDelay = new CFDelay(200);
pCFDelay->FCall(this);
nCurrentQueue-;
}
Листинг 2
Модель командира
class COfficer : public CRifleman
{
public:
COfficer();
virtual ~COfficer();
void SetCommand();
protected:
CFireApp *pApp; //
int x1(); // Is fire?
void y1();
bool bCommandFire;
};
extern LArc OfficerTBL[];
COfficer::COfficer():CRifleman
(0,NULL,OfficerTBL)
{
bCommandFire = false;
pApp = (CFireApp*)AfxGetApp(); //
FLoad(pApp->pNetFsa,1); // подключить
объект
к КА-сети
}
COfficer::~COfficer() { }
LArc OfficerTBL[] = {
LArc("Сон", "Огонь", "x1", "y1"),
LArc("Огонь", "Сон", "-", "-"),
LArc()
};
int COfficer::x1() { return bCommandFire; }
void COfficer::y1() { bCommandFire = false; }
void COfficer::SetCommand() { bCommandFire =
true; }
Листинг 3
Модель пули
extern LArc BulletTBL[];
class CBullet : public TBounce
{
public:
void SetAddrMan (LFsaAppl
*pFsaAppl);
CBullet();
CBullet(CWnd* pW, int nNum,
CSize sz=CSize(10,10),
LArc *pTBL=BulletTBL);
virtual ~CBullet();
void SetCenter(int x, int y);
void SetMove(int cx, int cy);
protected:
int x1();
int x2();
int x3();
void y4();
protected:
LFsaAppl *pFsaShot;
};
typedef vector<CBullet*>
TIArrayBullet;
typedef vector<CBullet*>:
:iterator
TIIteratorBullet;
CBullet::CBullet(CWnd* pW, int nNum,
CSize sz, LArc *pTBL)
:TBounce(pW, nNum, sz, pTBL)
{
pFsaShot = NULL;
}
CBullet::CBullet():TBounce()
{ pFsaShot = NULL; }
CBullet::~CBullet() { }
void CBullet::SetAddrMan(LFsaAppl
* pFsaAppl) { pFsaShot =
pFsaAppl; }
//
LArc BulletTBL[] = {
LArc("st","b1", "x1", "y4"),
LArc("b1","b1", "^x2", "y1"),
LArc("b1","st", "x2", "y4"),
LArc()
};
int CBullet::x1()
{
if (!pFsaShot) return false;
return string((pFsaShot)-
>FGetState()) == "выстрел";
}
int CBullet::x2()
{
return m_ptCenter.y + m_sizeRadius.cy >=
rcClient.bottom;
}
int CBullet::x3()
{
return nNumBounce;
}
void CBullet::y4() { SetCenter(0,10); }
void CBullet::SetCenter(int x, int y)
{
if (y) m_ptCenter.y = y;
if (x) m_ptCenter.x = x;
}
void CBullet::SetMove(int cx, int cy)
{
m_sizeMove.cx = cx;
m_sizeMove.cy = cy;
}
Листинг 4
Модель цепи стрелков
class CChainShot
{
public:
CChainShot(CWnd *pW);
virtual ~CChainShot();
void SetLink();
void SetCommand();
void OnSize(int cx, int cy);
CRifleman* GetAddrRifleman(int n);
CBullet* GetAddrBullet(int n);
protected:
CWnd *pWnd;
COfficer *pCOfficer;
TIArrayRifleman IArrayRifleman;
TIArrayBullet IArrayBullet;
};
CChainShot::CChainShot(CWnd *pW)
{
pWnd = pW;
pCOfficer = new COfficer();
for (int i=1; i<=4; i++) {
IArrayRifleman.push_back(new CRifleman(i,pWnd));
IArrayBullet.push_back(new CBullet(pWnd,i));
}
SetLink();
}
CChainShot::~CChainShot()
{
if (pCOfficer) delete pCOfficer;
TIIteratorRifleman iterRifleman =
IArrayRifleman.begin();
while (iterRifleman != IArrayRifleman.end())
delete *iterRifleman++;
IArrayRifleman.erase(IArrayRifleman.begin(),
IArrayRifleman.end());
TIIteratorBullet iterBullet = IArrayBullet
.begin();
while (iterBullet!=IArrayBullet.end()) delete
*iterBullet++;
IArrayBullet.erase(IArrayBullet.begin()
,IArrayBullet.end());
}
void CChainShot::SetCommand()
{
if (pCOfficer) pCOfficer->SetCommand();
}
CRifleman* CChainShot::GetAddrRifleman(int n)
{
CRifleman* currentRifleman=NULL;
CRifleman vs(n, NULL);
TIIteratorRifleman iterRifleman
= IArrayRifleman.begin();
while (iterRifleman != IArrayRifleman.end()) {
currentRifleman= *iterRifleman++;
if (*currentRifleman==vs) break;
}
return currentRifleman;
}
CBullet* CChainShot::GetAddrBullet(int n)
{
CBullet* currentBullet=NULL;
CBullet vs(NULL, n);
if (!IArrayBullet.empty()) {
TIIteratorBullet iterBullet = IArrayBullet
.begin();
while (iterBullet != IArrayBullet.end()) {
currentBullet= *iterBullet++;
if (*currentBullet==vs) break;
}
}
return currentBullet;
}
void CChainShot::SetLink()
{
LFsaAppl *currentRifleman;
TIIteratorRifleman iterRifleman =
IArrayRifleman.begin();
int n =1;
CRifleman *pFsaLeft = NULL;
CRifleman *pFsaRight = NULL;
while (iterRifleman != IArrayRifleman.end())
{
if (n==1)
{
currentRifleman= *iterRifleman++;
((CRifleman*)currentRifleman)-
>SetNumber(n);
n++;
pFsaLeft = pCOfficer;
pFsaRight= *iterRifleman++;
((CRifleman*)pFsaRight)->SetNumber(n);
n++;
((CRifleman*)currentRifleman)->
SetLink(pFsaLeft, pFsaRight);
}
else
{
pFsaLeft = currentRifleman;
if (iterRifleman != IArrayRifleman.end())
{
currentRifleman = pFsaRight;
pFsaRight= *iterRifleman++;
((CRifleman*)pFsaRight)->SetNumber(n);
n++;
((CRifleman*)currentRifleman)->
SetLink(pFsaLeft, pFsaRight);
}
}
}
pFsaLeft = currentRifleman;
currentRifleman = pFsaRight;
pFsaRight= NULL;
((CRifleman*)currentRifleman)-
>SetLink(pFsaLeft,
pFsaRight);
TIIteratorBullet iterBullet =
IArrayBullet.begin();
while (iterBullet != IArrayBullet.end()) {
CBullet* currentBullet= *iterBullet++;
CRifleman* pRf=GetAddrRifleman
(currentBullet->GetNum());
currentBullet->SetAddrMan(pRf);
}
}
void CChainShot::OnSize(int cx, int cy)
{
int n=1;
CBullet* currentBullet;
TIIteratorBullet iterBullet =
IArrayBullet.begin();
while (iterBullet != IArrayBullet.end()) {
currentBullet= *iterBullet++;
currentBullet->Size(CSize(cx/n,cy/n));
currentBullet->SetCenter(400/n-20,10);
currentBullet->SetMove(0,1);
// currentBullet->SizeBounce(CSize(20,20));
n++;
}
}
Листинг 5
Объект окна-отображения
void CFireView::OnFire()
{
pChainShot->SetCommand();
}
int CFireView::OnCreate(LPCREATESTRUCT
lpCreateStruct)
{
if (CView::OnCreate(lpCreateStruct) == -1)
return -1;
pChainShot = new CChainShot(this);
CFireApp *pApp = (CFireApp*)AfxGetApp(); //
pApp->pNetFsa->go_task(); // запуск
КА-объекта
return 0;
}
void CFireView::OnSize(UINT nType,
int cx, int cy)
{
pChainShot->OnSize(cx, cy);
CView::OnSize(nType, cx, cy);
}
void CFireView::OnFast()
{
CFireApp *pApp = (CFireApp*)AfxGetApp();
pApp->lCountTime=0;
}
void CFireView::OnSlow()
{
CFireApp *pApp = (CFireApp*)AfxGetApp();
pApp->lCountTime=1000;
}
Листинг 6
Действие y3 модели стрелка
void CRifleman::y3()
{
CRect r;
pParentWnd->GetClientRect(r);
CSize cz = r.Size();
int x1, y1;
x1=cz.cx/nSaveNumber;
y1= cz.cy/nSaveNumber;
CBullet *currentBullet =
new CBullet(pParentWnd, 0);
// задание начального положения
пули и ее размеров
currentBullet->SetCenter(x1-50,10);
currentBullet->SetMove(0,3);//
интервал между пулями
// currentBullet->SetMove(nCurrentQueue,3);
// стрельба
// веером
currentBullet->SizeBounce(CSize(2,5));
// передача адреса стрелка новой пуле
currentBullet->SetAddrMan(this);
// currentBullet->FCall(this);
}
Листинг 7
Таблица переходов "автоматной" пули
LArc BulletTBL[] = {
LArc("st","b1", "x1x3", "y4"),
LArc("st","b1", "^x3", "y4"),
LArc("b1","b1", "^x2", "y1"),
LArc("b1","st", "x2x3", "y4"),
LArc("b1","00", "x2^x3","-"),
LArc()
};