Technical Discussion February 24 2009

SFU Burnaby 12:30pm - 2:20pm

Topic 1: Block based puzzle game, block data structure.

Daniel Truong explained his block based puzzle game that he created last semester for CMPT 365. The final project for CMPT 365 was open ended which meant that Daniel could explore almost anything. Tetris and most other puzzle games do not blame the player for failing, instead the player blames himself for an incorrect decision. With this goal he created a block based puzzle game and in the end was not able to implement the full algorithm for clearing blocks and is wondering if a better data structure for storing blocks exists.

Blocks of various shapes fall down from the top of the screen. The player can shoot unlimited blocks to attempt to create rectangles of the falling blocks to clear them. More points are awarded for bigger blocks so the player can purposely make the block less rectangular to clear it when it is bigger.


In the picture above the player shoots blocks 1-12 in that order to the falling 3 blocks. The blocks fired were drawn to resemble how they would look in after they were all fired and this does not actually represent what it looks like in the game. Once the player fires blocks 1-4 it creates a perfect rectangle and will be cleared. Now instead suppose block 5 was fired before 3 & 4, then it would not be a rectangle and would not be cleared. Similarly the player cannot fire blocks 7,8,9,12 without clearing the purple block (because it forms a rectangle itself).

The rectangle detection algorithm must deal with multiple blocks and an efficient data structure is needed. Daniel is using an array as the data structure to hold the blocks.


  • The field isn't that big so no matter what data structure you choose it will be fast on any modern hardware.
  • Array + recursive algorithm to check for rectangles.

We moved on to the next topic and Daniel will resume this discussion next meeting.

Topic 2: MASS Technical Design Document exercise

Based on a simplified design document found here, discuss how we would implement these details and identify questions to ask the designers. While this is just an exercise some of the ideas discussed here will probably make it into the MASS project.

First identify what platform and specifications we have to work with. That way we can think in terms of the hardware limitations. Ideas in bold were chosen.

  • Language: C, C++, Python, Java
    • Many designers have experience with Python so if we went with it designers could help out too.
    • C++ is more commonly used in the gaming industry and people would gain more experience using it.
  • Scripting language: Python, Lua
    • More people have experience with Python and so it would be easy for them to create scripts
    • Lua is a very nice language to use for scripting and has a small memory footprint.
    • Ultimately designers may not understand "programming" (the thinking) so it would not matter much which was chosen. All of us present liked Lua more than Python and believed it would be easy for designers to use.
  • Platform: PC, DS, iPhone, XNA
    • XNA was proposed since we would have a real game on a real system that could be played by millions of players. Great way to promote the club.
    • Using SDL + OpenGL to make it cross platform.
    • It is not trivial to port an existing game to XNA or the iPhone and likewise for the DS with memory constraints.

Map - Grid vs. space

  • grid: easier to draw, supports DS quite nicely, but not natural
  • space: more fun, better suited to the concept of Asteroids

Backgrounds - Storage & drawing

  • Stars can be randomly generated for the background
  • If stars were the same for all players they could be used as meeting points
  • Or simply a looping starry background


  • Fixed size & shape, wrap around
  • Connections between sectors? (possibly multiple areas of space are connected)
  • Objects: motion & gravity
  • Minimize draw list by using quad trees or broad-phase collision detection. Either algorithm can be used for clipping and collision detection.
    • Could combine both, first use quad-tree to reduce number of objects to project on an axis and then used broad-phase.
  • Could perform collision detection and drawing during the same iteration of objects.
    • Argument against this is the simulation is usually done less frequent than rendering and it would slow things down.
  • Question for designers: Realistically how many objects are going to be in a game at any moment?
  • Question for designers: Will there be any overlapping objects that are allowed?

Daniel Truong created a multiplayer Asteroids game before in his distributed systems class.

  • issues in multiplayer design: distributed server load
  • server-based; we will probably use P2P
  • used lidgren (network library for C#)
  • boundary conditions, delays and determining where an object would be (time-stepping)

Other thoughts:

  • momentum & collisions have a negative effect when teim-stepping
  • start without physics etc. and build the client for networking from the ground up
  • simulate collision with background objects by adding an invisible black hole in the foreground.

Members Present

  • Eric Raue
  • Jon Derrick
  • Colin Hume
  • Marc DeRosier
  • Daniel Truong
Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License