CS3113 Spring 2014 Log
Lecture 17: 4/03
- Multithreading (in C#)
- Code samples posted
- Finish deadlock example
- Ordering locks.
-
For Friends example, we could use names. Example code used
hash codes.
-
If the comparison can result in ties, then for those cases use
a "tie lock"
- Exception handling and Threads.
- Barrier
- SpinLock
- Intro to 3D
- Camera
- View: position, target and "up".
-
Projection: Near and far planes, angle of view, aspect
ratio. Defines the frustum
- Demo spinning triangle.
Lecture 16: 4/01
- Multithreading (in C#)
-
Reminder, see http://www.albahari.com/threading.
- Simple example of deadlock: join self
- Mutual exclusion
-
Code that accesses and / or modifies shared data is known
as a critical region and must be protected by the
use of mutual exclusion, otherwise we risk a race
condition
-
Keyword: lock. (Same idea as Java's syncrhonized
blocks.)
-
Can use any object as the item to lock,
including
this
- Example:
lock(someObject) { /* Code to run with mutual
exclusion */ }
-
Remember to protect all code that accesses a
shared resource
-
C#'s locks are recursive. Again, similar to
Java. Note, not all librairies use recursive locks.
- Thread.Yield(), Thread.Sleep(n)
- Condition variables
-
Used when you are in a critical region, but need to wait
and allow another thread to enter the critical region.
You block on the condition variable simultaneously
releasing the lock.
-
C# allows you to identify the condition variable using the
same object as the lock.
-
Monitor.Wait(lockObject) / Monitor.Pulse(lockObject) /
Monitor.PulseAll(lockObject)
- Cyclic locking resulting in deadlock (bow / bowback).
-
Could prevent deadlock by use of Join or having everyone
use the same lock.
- But either approach results in loss of concurrency.
- Discuss next time how to order the locks
Lecture 15: 3/27
- Review Flocking
- Intro to Multithreading (in C#)
-
Chapters online from Albahari's C# in a
Nutshell: http://www.albahari.com/threading
- Why use mutlithreading in general?
- Where might we use it in game programming?
- What is a thread?
- How are threads created in general?
-
What are different ways in which we might synchronize
threads? What's the simplest?
- In C#:
- How do we create them?
- How do we wait for a thread to finish?
- How can we pass arguments to a thread function?
Lecture 14: 3/25
- A*
-
My A* demo had a bug due to an error in my heuristic for city
blocks. When computing the delta X and delta Y, I neglected to
get the absolute values of those differences..
- Data Structures for open set.
- Flocking
Spring Break: 3/17 – 3/21
Lecture 13: 3/13
- Search Algorithms continued
-
Some students had a problem with BFS because they used == to
test elements in closed set. For references, that will only
be testing the addresses. Not likely to be what
you want.
-
Note there can be special purpose implementatins of a closed
set. E.g. with the flip game, you could represent all
possible board positions in an array of 216
entries. And those entries could indicate which
configuration you got there from.
- Informed vs. Uninformed searching
-
Informed? Has some idea / guesstimate of the distance
to the goal.
- Uninformed examples: BFS, DFS, Uniform Search.
- Informed search examples: Greedy, A*.
- A*
-
For an excellent fairly extensive discussion see
Amit's
A* website
- Discuss pseudo-code. (See slides)
-
As with the Uniform Cost, we are using a priority
queue (but note the need to update items on the
queue).
-
But the value we are using for our priority has
changed: f(n) = g(n) + h(n). For uniform cost,
only the value g(n) mattered, i.e. the total cost of
getting to the node being explored. For A*,
we add in our guess h(n) (known as the
heuristic function) of the additional cost to get from
that node to the goal.
-
And it is possible for something on closed to move
back to open!
- Terminology:
-
Admissible: a heuristic that never
overestimates is called admissible. Admissible
heuristics guarantee that A* will be optimal.
If a heuristic overestimates however, A* will only
give a path that is too high by the maximum amount
that ir ever overestimated. A heuristic that
overestimates can find a solution faster than an
admissible heuristic would, even though that
solution may not be optimal.
-
Consistent: (aka monotone). A heuristic
that satisfies the "triangle inequality" is called
consistent. Conistency is more strict than
admissibility, ie. any consistent heuristic is
automatically admissible. If an algorithm is
consistent then a node never has to be moved from
the closed back to the open.
Lecture 12: 3/11
- Completed Collision Detection for Rotated Sprites
-
Transformations: translations and rotations. (Yes, there
might also e scaling and shearing, but translations and
rotations are the most common.
- Past Representations?
-
Translation: delta x and delta y. Just add that to our
position to get the new position.
-
Rotations: a scalar value representing how many radians
we want to turn. This value would be passed to the Draw
routine.
- Why the new stuff? (i.e. matrices)
-
Before we were just telling the Draw functions where and
how to draw the entire sprite.
-
Now we need to compute the location of each of the
individual pixels from our sprites.
-
Matrices allow a uniform representation for all of our
transformations and provide an easy way to
combine different transformations together using matrix
multiplication. (We will demonstrate this later in the
semester.)
-
How do we compute intersection with transformations then?
-
For every pixel in A, compute where it belongs in B's view of life.
-
If the resulting location is within the B sprite,
- get the corresponding color values.
-
And check the alpha's for non-zero. Both
non-zero we have a hit.
- Never had a hit? No intersection.
- Code is on slides.
- We can optimize this a bit.
- First we can do a Rectangular collision sanity check.
-
Second, we don't actually have to do a Matrix
multiplication for every pixel in A.
- Just do it for
- the top left pixel
- A unit vector in the X direction
- A unit vector in the Y direction.
Lecture 11: 3/06
- Posted:
- Code Samples: Rotating, Aiming, ChaseAndEvade
- Slides: 60.Collision Detection
- Pixel-level collision detection without rotations
-
Reviewed the algorithm. In particular how to map from a
point in the rectangle of intersection to an index in each
sprite's array of colors.
- Examined the code to handle the falling triangles
-
Observed that XNA's Rectangle.Bottom and Rectangle.Right are
actually one pixel beyond the rectangle.
I.e. Rectangle.Bottom == Rectangle.Y +
Rectangle.Height.
- Pixel-level collision detection with rotations
- Demoed Space War (and discussed history).
-
Discussed the use of the Draw method to display a rotated
sprite. Played with some simple code to observe the effect
of using the argument to specify the "origin" of the sprite
when displayed. This effects both the center of rotation
and also the positioning of the sprite. The code is in
Rotating.zip in the code samples.
-
Discussed the idea of rotations and translations
as transformations that can be represented by
Matrices. At the moment we are just accepting this as a
given and that "matrix multiplication" represents the
combining of to transformations. We will explore the actual
mathematics later in the semester.
-
Discussed the algorithm and explored the code for detecting
collisions when the sprites are rotated. Code is in the
Code Sample collection collisions.zip. The code comes from
the MSDN website.
-
Next assignment: Space War!
Lecture 10: 3/04
- Added Code Samples
- Invader.zip to demonstrate animation.
- ReadDataGame.zip to demonstrate how to read in a config file.
-
collision.zip. MSDN projects leading up to full pixel-level
collision detection.
- Extended due date for BFS assignment to Sunday night.
- Wandering. Considered MSDN implementation.
-
Noted how each update, they made a small change to the
direction that the want to head in. Remember it
takes time for any change to take effect.
- Use of Lerp.
- Normalization of the direction vector
-
Adding a component to the direction vector to cause us to
turn towards the center. Used the square of the ratio of
our distance from the center over the maximum distance we
want to be from the center. Discussed why.
- Hysteresis
- Pixel-level collision detection.
- Discussed the steps involved:
- Determine the rectangle of intersection.
- For each pixel in the rectangle
- determine its relative position in each sprite.
-
compare the colors of the sprites' pixels at the
correpsonding locations.
-
If both are not transparent, then we have a
collision.
- Started writing the code. Obtained the Color array.
Lecture 9: 2/27
- Search
-
BFS: checking for success when expanding (i.e. removing item
from open set) as opposed to when generating (i.e. adding an
itemto the open set)
-
Allow duplicates in open set or prevent them?
- Variations: Bounded DFS, Iterative bounded DFS
- Uniform Cost
- Uninformed vs. Informed
- See slides: AI - Basic Search
Aim / Wander / Chase / Evade
Lecture 8: 2/25
- BFS Implementation. See Prime Path code in Code Resources.
- How to implement open set?
- Main operations are add / remove.
- Checking for membership?
- How to implement closed set?
- Main operations are add / check membership.
-
Vector? Constant time for add, but would require O(n)
for membership test.
-
Self-balancing binary tree (e.g. red-black tree).
Logarithmic.
- Hash table. Constant time.
- Reducing size of open set. Bi-directional.
Lecture 7: 2/20
- Config files
-
System.IO.Stream stream = TitleContainer.OpenStream("Content/Data/gamedata.txt");
System.IO.StreamReader sreader = new System.IO.StreamReader(stream);
string line;
while ((line = sreader.ReadLine()) != null) {
// Do whatever
}
sreader.Close();
- AI: Search
- BFS / DFS
- Terminology:
- Open Set / Frontier
- Closed Set
- Complete
- Optimal
Lecture 6: 2/18
-
Implemented function to determine if there was a rectangular
intersection, i.e we implemented the Interstects method in
Rectangle.
- Platformer
- Gravity
- F = G * (m1 * m2)/(r2)
-
"Near" earth, we estimate the resulting accelleration as
~9.8 m/(s*s)
-
p = p0 + v0 * t + a * t2
v = v0 + a * t
-
v = v0 + a * t
p = p0 + v * t
-
MSDN example controlled jump velocity with:
v = vj * ( 1- (t/tM)1/7)
-
Animation.
Lecture —: 2/13
Cancelled by NYU due to weather. Make-up date scheduled for
Tuesday, May 6th.
Lecture 5: 2/11
- C# features
- Parameter Passing. See Code Samples.
- pass-by-value. The default.
-
pass-by-reference. Requires keyword
ref
both with parameter in the function's definition
and with the argument at the point of call.
-
Note the differences in effect these two mechanisms have
when the parameter is a value type vs. a reference
type.
- Determining which side of a rectangle you hit.
- Sound. See slides and inclass code.
Lecture 4: 2/06
- Time
GameTime
.
- Passed into
Update
.
-
Has a property
ElapsedGameTime
which
returns a TimeSpan
object representing the
amount of time that has passed since the last call to
Update
-
TimeSpan
. Has among other
properties: TotalMilliseconds
which is a
double, counting the amount of time since the last update in
milliseconds. We checked out the other properties,
too.
C# features
- Value types vs. reference types.
- Variables holding primitives are always handled as values.
- Variable holding defined types may be treadted either
as values or as references, depending on whether they were
defined as structs, which will be values, or as classes,
which will be references.
- Arrays: 1D, 2D and sparse arrays.
- To parse a string interpreting it as an int:
int result = int.Parse(theString);
Yes,
for many of us, it looks odd to call a static method on the
type "int".
- Random numbers:
Random rand = new Random(); // Gives us a random number generator
rand.Next(minValue, maxValue); // return an int from minValue to maxValue-1
Pong / Physics.
- Initial direction vector for the ball
-
We chose to represent the direction vector as a pair
(deltaX, deltaY) stored as a Vector2D
-
How to pick an intial pair? We computed an appropriate
vertical offset from the middle of the side of the
screen, allowing some space to prevent the ball from
being too close to the horizontal. Using that for the
deltaY and half the width of the screen for the deltaX,
we formed a Vector2. And then normalized it, resulting
in a Vector2 whose length was one. (See the uploaded
code for details.)
- Collision detection.
-
Now the ball flew but would go right through the paddle.
We used the method Intersects from the Rectangle class
to determine if a rectangle representing the ball had
intersected rectangles representing either of the
balls.
-
Bounce. Since the surfaces we are bouncing off of are
vertical or horizontal, we can represent the changes in
direction simply by flipping the sign on the deltaX or the
deltaY.
-
We finished with the ball bouncing off the right paddle.
After class, befor posting the code, I add bounces off the
other paddle, along with the top and bottom. Also detected
the ball going off the screen, reseting the paddles and
serving the ball to opposite player from the last server.
The next assignment was discussed: Breakout, a classic Atari game.
Lecture 3: 2/04
- Gimp:
- buttons
- Rounded corners
- Drawing text
- Drawing a grid. Do it in the editor or in the program?
-
Modifying the game screen size. In the constructor,
modify
graphics.PreferredBackBufferWidth
and graphics.PreferredBackBufferWidth
.
- Start of Pong / Physics.
- Collision detection.
- Direction vector
Lecture 2: 1/30
- IsActive
- Use of float for position coordinates
- Debugging output: Console.WriteLine
- Defining an enum and using it to track game states
- Testing if the key has just been pressed.
- Adding a font and writing to the screen
- SpriteFont
- SpriteBatch: DrawString
- C# Properties
Lecture 1: 1/28
- Course administrivia
- Basics of XNA
- [New] Classes
- Game
- Constructor, Initialize, LoadContent, UnloadContent
- Update / Draw
- GraphicsDevice. Property to return the GraphicsDevice.
- IsMouseVisible. Property to determine whether XNA will show the mouse cursor.
- Texture2d
- Vector2
- X, Y. float fields.
- Zero. Property that returns a Vector2 with both fields set to zero.
- Content
- Keyboard / KeyboardState / Keys
- Mouse / MouseState / ButtonState
- SpriteBatch
- GraphicsDeviceManager
- GraphicsDevice
- Clear. Clear the screen and "paint" a color.
- Viewport. Property to access the Viewport object
- Viewport
- MathHelper
-
GameTime. We haven't actually used it yet. The game
time is automatically passed in to the Update
method.
- Handy Visual Studio stuff
- Ctrl+K,R: Find All References.
- F12: Go To Definition.