Chris Pollett > Students >

    ( Print View )


    [Project Blog]

    [CS297 Proposal]





    [CS 297 Report - PDF]

    [CS298 Proposal]


CS298 Proposal

Shortest Meeting Point in a Game Framework

Nithin Reddy (

Advisor:Professor Chris Pollett

Committee Members:Professor Chris Tseng and Professor Soon Tee Teoh


This project will implement the shortest path meeting point algorithm of multiple robots on a weighted terrain into a game framework. The game framework will then be used to study the algorithm in an attempt to verify the algorithm's efficiency. The research project will also examine some aspects that the original algorithm disregards, such as the impact of different types of robots and different terrain types.

The game framework will be based on a modified version of ex-San Jose State Professor Rudy Rucker's POP framework. The POP framework will be ported to C# 2.0, and will use managed DirectX. The purpose of porting the POP framework is to simplify the existing code base. New packages will be added to the framework to support height-based terrains, as the current POP framework only supports flat terrains.

CS297 Results

  • Direct3D Demo
  • Pick N Pop Game
  • Mesh Demo
  • Meeting Point Algorithm Demo

Proposed Schedule

Weeks 1 through 3: August 24 - September 13 Submit CS 298 Proposal. Work on implementing meeting point algorithms. Research a few meeting point algorithms for planar terrains.
Deliverable: Planar Meeting Points Demo
Weeks 4 and 5: September 14 - September 27 Begin work on height-mapped terrain engine for the Game Framework. Figure out how to generate height-maps to allow for several different terrains.
Deliverable: Game Framework Component, Height-Mapped Terrain Engine
Weeks 6 and 7: September 28 - October 11 Add Units that move on height-mapped terrain.
Deliverable: Game Framework Component, Units
Weeks 8 through 10: October 12 - November 1 Implement 3D Meeting Point Algorithm. Compare its performance with planar meeting points in terms of accuracy and speed.
Deliverable: Game Framework Component, Meeting Point Architecture
Week 11: November 2 - November 8 Create simple game that demonstrates the various features of the Game Framework. Deliverable: Sample Game using Game Framework
Weeks 12 through 15: November 9 - December 6 Finish draft of Writing Project and submit it to members of the graduate committee for review. Incorporate improvements and fix errors brought up by the graduate committee members. Submit final Writing Project to the Graduate Studies office. Prepare for thesis defense.
Deliverable: Writing Project - Draft
Week 16: December 7 - December 13 Perform touch-ups to the Writing Project.
Deliverable: Writing Project - Final

Key Deliverables:

  • Software
    • Planar Meeting Points Demo - Implement a few planar meeting point algorithms [10], [11], and [12].
    • Game Framework Component and Height-Mapped Terrain Engine - The terrain engine will take a grayscale image representation of the map, and converts it to 3D points. The engine will fill out the terrain with textures.
    • Game Framework Component and Tactical Units - The tactical units will be able to navigate the 3D based terrain and be flexible enough to have unique abilities. These abilities revolve around having different speeds depending on the type of terrain that the unit is on, and the direction that the unit is traveling. This component will also add terrain detection on the units so that they, for example, do not move "through" a hill.
    • Game Framework Component and Meeting Point Architecture - This component will allow users to plug in any type of meeting point algorithm. It will have the weighted terrain meeting point algorithm [1] implemented by default. There will also be a system that measures the performance of an algorithm.
    • Sample Game using Game Framework - This will be a simple game that exhibits the features of the game framework including the weighted terrain meeting point algorithm [1]. In addition, the algorithm will be altered to take into account tactical unit abilities.
  • Report
    • Writing Project - Draft
    • Writing Project - Final

Innovations and Challenges

  • Creating interesting and varied terrains will be tough. Trivial terrains, like a flat terrain or one that has only a few features, will be simple, but making a terrain that is diverse is more difficult. In the game industry, there are people that work solely on making realistic terrains.
  • My experience with converting algorithms from paper to code has shown me that this tends to be difficult.
  • This project will adapt the weighted terrain meeting point algorithm so that it works with units that have different abilities. The original algorithm assumes that the robots are all the same.
  • The weighted terrain meeting point algorithm will need to be optimized so that it runs in realtime. This is necessary to incorporate it into a game.
  • There are a couple of challenges when developing a game. One is to have the units move reliably moving on the terrain, and not through it. The second is to ensure proper object disposal. Since the game updates its state every second, if objects are not disposed of properly, memory will be consumed quickly.


[1] M. Lanthier, D. Nussbaum, and T-J Wang, "Calculating the Meeting Point of Scattered Robots on Weighted Terrain Surfaces"

[2] R. Rucker, "Software Engineering and Computer Games." Addison Wesley, 2002.

[3] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, "Introduction to Algorithms." MIT Press, 2001.

[4] Andera, Craig. Mesh Basics Tutorial. Retrieved May 8, 2006, from

[5] Andera, Craig. Mesh Creation Tutorial. Retrieved May 8, 2006, from

[6] MSDN DirectX Documentation from the February 2006 SDK.

[7] Schuld, Michael. (2005, June 17). Tutorial 5 :: Rendering Full Textured Meshes. Retrieved May, 2006, from

[8] Miller, Tom. Beginning 3D Game Programming. Sams Publishing: Indianapolis, 2005.

[9] Pierson, Derek. (2005). Beginning Game Development Part V - Adding Units. Retrieved February, 2006, from

[10] Eliosoff, Jacob, Unger, Richard. (1998) Welcome to the Minimum Enclosing Circle Emporium. Retrieved May, 2006, from

[11] Muhammad, Rashid Bin. Smallest Enclosing Circle Problem. Retrieved May, 2006, from

[12] D. J. Elzinga and D. W. Hearn. Geometrical solutions for some minimax location problems. Transportation Science, 6(4):379--394, 1972.

[13] Megiddo, N., "Linear-time algorithms for linear programming in R3 and related problems". SIAM Journal on Computing, vol 12 number 4, Nov 1983.