4. Упражнения
Создайте в MS Visual C++ проект консольного приложения и добавьте в этот проект файлы queen.h (объявление класса CQueen), queen.cpp (реализация класса CQueen) и testprg.cpp (главная программа). Распределите по этим файлам компоненты программы, приведенные в лекции. Запустите программу и убедитесь, что она находит одно из решений задачи о восьми ферзях.
Измените программу так, чтобы она выдавала все возможные решения задачи о восьми ферзях. Как можно отбросить решения, которые являются поворотами других решений?
Как изменится программа, если обобщить задачу на случай N ферзей? Т.е. как найти возможные расположения N ферзей на шахматной доске размерами NxN? Существуют некоторые N, для которых вообще нет решений (например, N=2 и N=3). Что будет выдавать программа в подобных случаях?
Измените программу так, чтобы она динамически изображала на шахматной доске расположение каждого ферзя во время своей работы. Для отображения ферзей используйте библиотеку OpenGL. Какие фрагменты программы оказываются ответственными за отображение?
Рекомендации: ферзей можно изображать условно, в виде пирамид или параллелепипедов. Для организации задержки между перемещениями ферзей можно использовать функцию Sleep(int dt) из Win32 API (параметр dt задает задержку выполнения программы в миллисекундах).
Лекция 5. Учебный пример: игра "Бильярд"
В данной лекции рассматривается программа, имитирующая движение шаров по бильярдному столу со стенками и лузами. Чтобы разобраться в этой программе, надо изучить лекции 1-4 по ООП и знать основные методы работы с библиотекой OpenGL. OpenGL применяется в несколько необычном для ОС Windows качестве: как библиотека двумерной графики. Это позволяет существенно уменьшить исходный текст программы по сравнению с вариантом программы, который для рисования пользуется функциями Windows API.
Основное внимание при разработке программы "Бильярд" уделяется созданию автономных агентов, взаимодействующих между собой для достижения желаемого результата – имитации движения шаров по бильярдному столу.
1. Описание модели бильярда
Программа отображает на экране окно, в котором в виде прямоугольника изображен бильярдный стол. В его 4-х углах находятся лузы. На столе расположены 15 синих шаров и 1 белый шар (рис. 5.1).
Щелчком левой кнопки мыши в произвольной точке стола пользователь имитирует удар кием по белому шару, сообщая ему некоторую начальную скорость в направлении указателя мыши. Движущийся шар упруго соударяется со стенками и другими шарами. При движении по столу шары теряют энергию за счет трения и со временем останавливаются. При попадании в лузу синие шары удаляются со стола, а белый помещается в начальную позицию (рис. 5.1).
Рис. 5.1. Изображение бильярдного стола с 4-мя угловыми лузами.
2. Основные классы модели
Основными классами в данной задаче являются стенки, лузы и шары. Объектам этих классов приписана некоторая экранная область и они умеют изображать себя внутри этой области. Будем называть эти объекты графическими объектами. Графические объекты каждого типа хранятся в программе в виде связных списков. Для этого в каждом классе есть указатель на следующий объект списка.
Размещение ссылок внутри объектов для объединения этих объектов в некоторый абстрактный тип данных (например, связный список) считается плохим стилем программирования. Лучше отделить реализацию АТД от объектов, которые в нем хранятся. Но решение этой задачи содержит некоторые нетривиальные аспекты, которые усложнили бы рассматриваемую программу.
Примем упрощающее предположение, что все графические объекты занимают прямоугольную область. Конечно, для круглых объектов (например, шаров и луз) это неверно. Но учет реальной формы объектов значительно усложнил бы программу. Главные цели в ее изучении – рассмотрение способа, которым объекты наделяются собственным поведением и как организовано взаимодействие объектов. Каждый графический объект не только умеет изображать себя, но и может взаимодействовать с другими объектами модели бильярда.
2.1 Класс CRect (прямоугольник)
Класс CRect является вспомогательным классом, который предназначен для хранения координат прямоугольника и выполнения некоторых операций с этими координатами. Операции с координатами прямоугольников применяются при реализации поведения графических объектов. Далее приведено объявление класса, в котором большая часть функций-членов сделаны встраиваемыми.
class CRect {
public :
// Конструкторы
CRect()
{ x1 = y1 = x2 = y2 = 0; }
CRect( int nx1, int ny1, int nx2, int ny2 )
{ x1 = nx1; y1 = ny1; x2 = nx2; y2 = ny2; }
// Инициализация координат прямоугольника
void SetRect( int left, int top, int right, int bottom )
{ x1 = left; y1 = top; x2 = right; y2 = bottom; }
// Смещение прямоугольника
void OffsetRect( int dx, int dy )
{ x1 += dx; y1 += dy; x2 += dx; y2 += dy; }
// Получение координат центра прямоугольника
void CenterPoint( int* x, int* y )
{ *x = (x1 + x2)/2; *y = (y1 + y2)/2; }
// Проверка на совпадение координат углов прямоугольника
bool IsRectEmpty()
{ return ( x1 == x2 && y1 == y2 ); }
// Получение ширины прямоугольника
int Width() { return x2 - x1 + 1; }
// Получение высоты прямоугольника
int Height() { return y2 - y1 + 1; }
// Функция вычисляет пересечение объекта с прямоугольником another
CRect IntersectRect( CRect& another );
// Нормализация координат прямоугольника
void NormalizeRect();
// Общедоступные атрибуты
int x1, y1, x2, y2;
};
Атрибуты прямоугольника (координаты) сделаны общедоступными, т.к. этот класс очень прост, не обладает собственным поведением и нет существенной опасности от несанкционированного изменения координат.
Будем называть прямоугольник нормализованным, если его координаты (x1, y1) и (x2, y2) соответствуют левому верхнему и правому нижнему углу. Такое упорядочение координат упрощает расчет пересечения прямоугольников. Эта операция выполняется функцией-членом IntersectRect() и требуется для отслеживания столкновения графических объектов.
2.2 Класс CWall (стенка бильярдного стола)
Класс СWall объявляется следующим образом:
class CWall {
public:
CWall( int left, int top, int right, int bottom,
double cf, CWall* pNextWall );
// Рисование стенки
void Draw();
// Извещение стенки о том, что в нее попал шар
void HitBy( CBall* pBall );
CRect GetRegion() { return region; }
CWall* GetLink() { return pLink; }
private:
CWall* pLink;
CRect region; // Экранные координаты стенки
double convertFactor; // Значение, из которого вычитается
// направление ударившегося шара, чтобы
// получилось зеркальное отражение
};
Атрибут pLink служит для организации связного списка объектов CWall. Значение этого атрибута, а также координаты области для рисования стенки и параметр отскока инициализируются в конструкторе:
CWall::CWall( int left, int top, int right, int bottom,
double cf, CWall* pNextWall )
{
convertFactor = cf;
region.SetRect( left, top, right, bottom );
pLink = pNextWall;
}
Стенка рисуется на экране как сплошной зеленый прямоугольник. Это делается с помощью функций OpenGL:
void CWall::Draw()
{
glColor3ub( 0, 255, 0 );
glRecti( region.x1, region.y1, region.x2, region.y2 );
}
Когда о стенку ударяется шар, то направление его движения изменяется в соответствии со значением атрибута convertFactor. Для горизонтальных стенок convertFactor=0, а для вертикальных convertFactor=Pi. В результате шар зеркально отражается от стенки:
void CWall::HitBy( CBall* pBall )
{
pBall->SetDirection( convertFactor - pBall->GetDirection() );
}
2.3 Класс CHole (луза бильярдного стола)
Ниже приведено объявление класса CHole:
class CHole {
public:
CHole( int x, int y, CHole* pNextHole );
// Рисование лузы
void Draw();
// Извещение лузы о том, что в нее попал шар
void HitBy( CBall* pBall );
CRect GetRegion() { return region; }
CHole* GetLink() { return pLink; }
private:
CHole* pLink; // Указатель на следующую лузу для образования
// связного списка
CRect region; // Экранные координаты области лузы
};
Конструктор и функция-член для рисования лузы устроены очень просто:
CHole::CHole( int x, int y, CHole* pNextHole )
{
// Описывающий прямоугольник для лузы с центром в точке (x, y)
region.SetRect( x - 5, y - 5, x + 5, y + 5 );
pLink = pNextHole;
}
void CHole::Draw()
{
// Луза рисуется в виде желтого круга, вписанного в область region
glColor3ub( 255, 255, 0 );
glPointSize( (float)region.Width() );
glEnable( GL_POINT_SMOOTH );
glBegin( GL_POINTS );
int cx, cy;
region.CenterPoint( &cx, &cy );
glVertex2i( cx, cy );
glEnd();
glDisable( GL_POINT_SMOOTH );
}
При попадании шара в лузу возможны два варианта. Если шар оказался белым, то он возвращается на исходную позицию. В остальных случаях шар останавливается и рисуется за пределами стола в строке, предназначенной для отображения выбитых шаров.
void CHole::HitBy( CBall* pBall )
{
// Энергия шара обнуляется
pBall->SetEnergy( 0.0 );
if ( pBall->IsCue() )
pBall->SetCenter( 50, 108 );
else
{
pBall->SetCenter( 10 + saveRack*15, 250 );
saveRack++; // Увеличение глобального счетчика забитых шаров
}
}
2.4 Класс CBall (бильярдный шар)
Последним графическим объектом является шар, определяемый следующим описанием класса:
class CBall {
public:
CBall( int x, int y, bool fc, CBall* pNextBall );
// Рисование шара в текущем положении
void Draw();
// Изменение положения шара в предположении, что с момента
// предыдущего изменения прошел единичный промежуток времени
void Update();
// Извещение шара о том, что в него попал другой шар
void HitBy( CBall* pBall );
// Расчет угла между осью OX и направлением от центра шара до точки,
// смещенной от центра шара на (dx, dy)
double HitAngle( double dx, double dy );
// Функции-члены для доступа к переменным класса
void SetEnergy( double v ) { energy = v; }
void SetCenter( int newx, int newy );
void SetDirection( double newDir ) { direction = newDir; };
CRect GetRegion() { return region; }
CBall* GetLink() { return pLink; }
double GetEnergy() { return energy; }
void GetCenter( int* x, int* y );
double GetDirection() { return direction; }
bool IsCue() { return fCue; }
private:
CBall* pLink; // Указатель на следующий шар связного списка
CRect region; // Экранная область, в которую вписан шар
double direction; // Направление движения шара (угол в радианах
// относительно оси OX)
double energy; // Энергия шара
bool fCue; // Признак белого шара
};
Специфическими для шара атрибутами являются direction (направление движения), energy (кинетическая энергия шара) и флаг fCue, который равен true для единственного в модели белого шара. Шары инициализируются координатами центра (подобно лузам), признаком белого шара и указателем на следующий шар в списке. Энергия и направление шара первоначально равны нулю.
CBall::CBall( int x, int y, bool fc, CBall* pNextBall )
{
SetCenter( x, y );
SetDirection( 0 );
SetEnergy( 0.0 );
pLink = pNextBall;
fCue = fc;
}
На экране шар рисуется в виде круга белого или синего цвета. Отображение выполняет функция-член Draw().
void CBall::Draw()
{
if ( IsCue() )
glColor3ub( 255, 255, 255 ); // Белый цвет
else
glColor3ub( 0, 0, 255 ); // Синий цвет
glPointSize( (float)region.Width() );
glEnable( GL_POINT_SMOOTH );
glBegin( GL_POINTS );
int cx, cy;
region.CenterPoint( &cx, &cy );
glVertex2i( cx, cy );
glEnd();
glDisable( GL_POINT_SMOOTH );
}
Функция-член Update() используется для изменения положения шара через единичный промежуток времени, прошедший с момента предыдущего вызова этой функции. Если шар обладает достаточной энергией, то он перемещается и затем проверяет, не задел ли он другой объект. Если хотя бы один шар на столе сдвинулся, то глобальная переменная-флаг fBallMoved устанавливается равной true. Если шар задел другой объект, то шар сообщает об этом объекту. Сообщения бывают трех типов: они соответствуют ударам по лузе, стенке и другому шару.
void CBall::Update()
{
// Для движения у шара должна быть некоторая кинетическая энергия
if ( energy <= 0.5 )
return;
fBallMoved = true;
// На каждом шаге энергия шара уменьшается за счет трения
energy -= 0.05;
// Смещение шара вычисляется с учетом квадратичной зависимости
// кинетической энергии от скорости. Константа 2.0 выбрана для
// обеспечения более-менее реалистичного движения шаров
int dx = (int)( 2.0*sqrt(energy)*cos(direction) );
int dy = (int)( 2.0*sqrt(energy)*sin(direction) );
region.OffsetRect( dx, dy );
// Проверка на попадание в лузу
CHole* hptr = listOfHoles;
while ( hptr )
{
CRect is = region.IntersectRect( hptr->GetRegion() );
if ( !is.IsRectEmpty() )
{
hptr->HitBy( this );
hptr = NULL;
}
else
hptr = hptr->GetLink();
}
// Проверка на попадание в стенку
CWall* wptr = listOfWalls;
while ( wptr )
{
CRect is = region.IntersectRect( wptr->GetRegion() );
if ( !is.IsRectEmpty() )
{
wptr->HitBy( this );
wptr = NULL;
}
else
wptr = wptr->GetLink();
}
// Проверка на попадание в другой шар
CBall* bptr = listOfBalls;
while ( bptr )
{
if ( bptr != this )
{
CRect is = region.IntersectRect( bptr->GetRegion() );
if ( !is.IsRectEmpty() )
{
bptr->HitBy( this);
break;
}
}
bptr = bptr->GetLink();
}
}
При соударении шаров считается, что шар, по которому производится удар, неподвижен и энергия ударившего шара делится между ними пополам. При ударе также меняются направления движения обоих шаров.
void CBall::HitBy( CBall* pBall )
{
// Уменьшаем энергию ударившегося шара вдвое
pBall->SetEnergy( pBall->GetEnergy()/2.0 );
// и прибавляем ее к собственной энергии
energy += pBall->GetEnergy();
// Расчет нового направления для текущего шара
int cx1, cy1, cx2, cy2;
GetCenter( &cx1, &cy1 );
pBall->GetCenter( &cx2, &cy2 );
SetDirection( HitAngle( cx1 - cx2, cy1 - cy2 ) );
// Модификация направления ударившегося щара
double da = pBall->GetDirection() - GetDirection();
pBall->SetDirection( pBall->GetDirection() + da );
}
// Расчет угла между осью OX и вектором (dx, dy). Функция возвращает
// значение угла радианах в диапазоне (0,PI) или (-PI,0)
double CBall::HitAngle( double dx, double dy )
{
double na;
if ( fabs(dx) < 0.05 )
na = PI/2;
else
na = atan( fabs(dy/dx) );
if ( dx < 0 )
na = PI - na;
if ( dy < 0 )
na = -na;
return na;
}
|
