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 2¹⁶ 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 * (m₁ * m₂)/(r²)
    • "Near" earth, we estimate the resulting accelleration as ~9.8 m/(s*s)
    • p = p₀ + v₀ * t + a * t²
      v = v₀ + a * t
    • v = v₀ + a * t
      p = p₀ + v * t
    • MSDN example controlled jump velocity with:
      v = v_j * ( 1- (t/t_M)^1/7)
  • Animation.

Lecture —: 2/13

Cancelled by NYU due to weather. Make-up date scheduled for Tuesday, May 6^th.

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
      • Width, Height
    • Vector2
      • X, Y. float fields.
      • Zero. Property that returns a Vector2 with both fields set to zero.
    • Content
      • Load
    • Keyboard / KeyboardState / Keys
    • Mouse / MouseState / ButtonState
    • SpriteBatch
      • Begin, Draw, End
    • GraphicsDeviceManager
    • GraphicsDevice
      • Clear. Clear the screen and "paint" a color.
      • Viewport. Property to access the Viewport object
    • Viewport
      • Width, Height
    • MathHelper
      • Clamp
    • 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.