|
Chris Pollett > Old Classes > PIC197 ( Print View ) Enrollment info Course Info:
Homework Assignments: Practice Exams: PIC: |
PIC 197 Practice Final
The final is June 14, 8-11am.
For the actual final please bring photo ID. One of the problems
below will be on the actual final.
1. Give the algorithm for deciding if two line segments cross.
Soln. Assume our two line segments are p1p2 and p3p4 where
the pi are points. We write pi.x and pi.y for the x and y
coordinates of a point.
The algorithm from class had two components:
(a) Check bounding boxes. (Rules out non-intersecting
colinear segments).
Let x_max = max(p1.x,p2.x), x_min = min(p1.x, p2.x)
and y_max = max(p1.y,p2.y), y_min = min(p1.y, p2.y)
Let x'_max = max(p3.x,p4.x), x'_min = min(p3.x, p4.x)
and y'_max = max(p3.y,p4.y), y'_min = min(p3.y, p4.y)
check if (x_max >= x'_min) && (x'_max >= x_min) &&
(y_max >= y'_min) && (y'_max >= y_min)
if this fails then segments don't intersect
(b) Check if two segments straddle each other.
That is, the cross products (p1-p3) X (p4-p3) and
(p2-p3) X (p4-p3) have different sign.
And, the cross products (p3-p1) X (p2-p1) and
(p4-p1) X (p2-p1) have different sign.
If so they intersect. Otherwise, together with (a) they don't
2. Consider the following weighted graph where s is the start node
and d is the destination node:
s--4-.b
| |
3 5
| |
a. |
| |
| d
5 /
| 5
| /
.c
Assume this diagram is drawn to scale and we use Euclidean distance as a
heuristic for the remaining distance. Explain how the A* algorithm we
find a path from s to d.
Soln. To begin we have a priority queue open and a set
closed both of which are empty.
(i) Vertex s is pushed onto open.
Then s is removed from open and its two neighbours a and b
are examined. They are not found in closed.
a's estimated cost for a solution is 3 + sqrt(2^2+ 4^2) =3 +2sqrt(5)
b's estimated cost for a solution is 4+5 = 9
s is put in closed. a and b are added to open.
(ii) As a has least cost on open it is removed next.
Its two neighbours s and c are considered. s is found in
closed so is not considered further.
c's estimated cost for a solution is 8+5 = 13.
a is put in closed. c is added to open.
(iii) As b has least cost on open it is removed next.
Its two neighbours s and d are considered. s is found in
closed so is not considered further.
d's estimated cost for a solution is 9+0 = 9.
b is put in closed. d is added to open.
(iv) As d has least cost on open it is removed next.
It's our destination point so the path s b d is returned.
3. Describe the four basic components used to generate flocking behavior.
Soln. (i) steer to avoid crowding local flockmates.
(ii) align toward average heading.
(iii) steer to average position.
(iv) steer to avoid obstacles.
(ii) has to do with object orientation. The weighted sum of remaining
can be used to compute a move vector.
4. Write a struct pair for pair of int's: (x,y). Overload < so that
(x1,y1) < (x2, y2) is x1 < x2 or x1 == x1, and y1 < y2. Then write a
program which creates five such pairs and uses the STL template
priority_queue to sort them and print them out.
Soln.
#include <queue>
struct pair
{
int x,y;
pair(int x1, int y1);
bool operator<(pair p2);
};
pair::pair(int x1, int y1)
{
x=x1;
y=y1;
}
bool pair::operator<(pair p2)
{
if( x < p2.x || (x == p2.x && y < p2.y)) return true;
else return false;
}
ostream& operator<<(ostream &stream, pair p)
{
stream << "x=" << p.x;
stream << "y=" << p.y << endl;
return stream;
}
int main()
{
pair *p;
priority_queue< pair * > queue;
p = new pair(1,2);
queue.push(p);
p = new pair(3,4);
queue.push(p);
p = new pair(2,9);
queue.push(p);
p = new pair(9,4);
queue.push(p);
p = new pair(5,1);
queue.push(p);
while( queue.size() > 0)
{
cout << queue.top();
queue.pop();
}
return 0;
}
5. Give an algorithm for determining if a point is interior to a polygon.
Soln. Let p1 be our point
(i) Pick a point p_infinity known to be be exterior to polygon.
(can do this by computing bounding box for polygon and then
choosing some point exterior to this).
(ii) Check if line segment p1p_infinity crosses an odd number
of edges of the polygon. If so, is interior point. Otherwise,
exterior.
6. (a) Give the code for creating a DirectSound object. (b) an 2-d array
of direct sound buffers. (c) playing the sound in the (i,j)th sound
from such an array in looping mode.
Soln.
(a)
LPDIRECTSOUND lpds;
if(FAILED(DirectSoundCreate(NULL, &lpds, NULL))
{ /*error */}
(b)
#define NUM_SOUNDS 10;
#define NUM_COPIES 5;
#define DS_NUMCHANNELS 8 //number of channels
#define DS_CHANSPERSAMPLE 1 //mono sound
#define DS_BITSPERSAMPLE 8 //8 bit sound
#define DS_SAMPLERATE 22050 //22KHz sampling
#define LENGTH = 5 *DS_SAMPLERATE //5 secs of sound
LPLPDIRECTSOUNDBUFFER lpDSBuffer[NUM_SOUNDS][NUM_COPIES];
int i;
DSBUFFERDESC dsbdesc;
PCMWAVEFORMAT pcmwf;
memset(&pcmwf,0,sizeof(PCMWAVEFORMAT));
pcmwf.wf.wFormatTag=WAVE_FORMAT_PCM;
pcmwf.wf.nChannels=DS_CHANSPERSAMPLE;
pcmwf.wf.nSamplesPerSec=DS_SAMPLERATE;
pcmwf.wf.nBlockAlign=
DS_CHANSPERSAMPLE*DS_BITSPERSAMPLE/8;
pcmwf.wf.nAvgBytesPerSec=
pcmwf.wf.nSamplesPerSec*pcmwf.wf.nBlockAlign;
pcmwf.wBitsPerSample=DS_BITSPERSAMPLE;
memset(&dsbdesc,0,sizeof(DSBUFFERDESC));
dsbdesc.dwSize=sizeof(DSBUFFERDESC);
dsbdesc.dwFlags=DSBCAPS_STATIC;
dsbdesc.dwBufferBytes=LENGTH;
dsbdesc.lpwfxFormat=(LPWAVEFORMATEX)&pcmwf;
for( i = 0; i< NUM_SOUNDS; i++)
{
lpDS->CreateSoundBuffer(&dsbdesc,lpDSBuffer[i],NULL));
}
(c)
lpDSBuffer[i][j]->
Play(0,0,DSBPLAY_LOOPING);
7. (a) Explain how to handle mouse events in Windows. (b) Explain
how to find out if the left button is being pressed in DirectInput.
Soln.
(a) In windows callback function can add cases for events like
WM_MOUSEMOVE, WM_LBUTTONDOWN, WM_RBUTTONDOWN, WM_LBUTTONUP, etc.
The LPARAM that comes with these events encodes the x, y
coords where it occurred. High order two bytes for y, low order for x.
(b) Let assume we've created a DirectInput object and used it to
set up a DirectInput device lpdimouse associated with the mouse,
set its cooperative level and the data format. Then:
DIMOUSESTATE mousestate;
if(FAILED(lpdimouse->Acquire()))
{ /* error */ }
if(FAILED(lpdimouse->GetDeviceState( sizeof(DIMOUSESTATE),
(LPVOID)mousestate )))
{ /* error */}
if(mousestate.rgbButtons[0] & 128)
{ /* button is being pressed */}
if(lpdimouse)
lpdimouse->Unacquire();
8. Give the algorithm from class for randomly generating a dungeon level.
Soln.
(i) Randomly choose a number of x and y values
and use the horizontal and vertical lines associated with
these values to split up your level map into rectangular
regions.
(ii) For each region decide randomly whether or not it contains a room.
If it does create a room that is slightly inset from the boundaries
of regions rectangle.
(iii) Randomly place some doors on room.
(iv) use A* to generate a path from a a given rooms door to a neighbouring
rooms door not crossing through a room.
(v) now can generate monsters artifacts in rooms as desired.
9. Explain the steps needed to read a value from the Windows registry in C++.
Soln.
HKEY rkey;
char buf[32];
unsigned long length;
DWORD type;
// Step 1: get handle to registry folder desired
int result = RegCreateKey(HKEY_LOCAL_MACHINE, "My_Folder//My_SubFolder",
0, NULL, 0, KEY_READ, NULL, &rkey, NULL
); // sets up rkey for reading from the My_SubFolder
// subfolder of the My_Folder stored in the top level
// HKEY_LOCAL_MACHINE folder.
// Step 2: read data
if(result != ERROR_SUCCESS) return;
RegQueryValueEx(rkey, "MyName", NULL, &type,
(unsigned char *) buf, &length
); // after executing
// buf will contain the data associated with MyName key.
// type its data type and length its number of bytes.
// Step 3: free the handle
RegCloseKey(rkey);
10. Explain how to write "hello there" to a DirectDraw surface using a device
context.
Soln. Assume lpSurface points to a DirectDraw surface. Could do:
HDC hdc;
char out[15];
int len;
len=sprintf(out,"hello there"); // len is the number of char's
// placed in array
lpSurface->GetDC(&hdc); // it's a test so we don't need to do
// error checking
//This line get's device context
SetTextColor(hdc,RGB(0,0,255)); // set color to blue
SetBkMode(hdc, TRANSPARENT); // don't draw the background.
TextOut(hdc,10,20,out,len); // write out at x=10, y=20 on the surface
lpSurface->ReleaseDC(hdc); // release context when done.
|