CS297 Proposal

Shortest Meeting Point in a Game Framework

Nithin Reddy (nithin at bokkareddy.com)

Advisor: Dr. Chris Pollett

Description:

This project will implement the shortest path meeting point algorithm of multiple robots on a weighted terrain [1] 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.

Schedule:

Week 1: Jan.25-Jan.30	Write 297 proposal
Week 2: Jan.31-Feb.7	Research resources for managed DirectX (i.e. books, websites, etc.)
Week 3: Feb.7-13	Research basic Direct3D application. Deliverable: D3D demo.
Week 4: Feb.14-20	Research game loop in Direct3D. Implement Pick 'N Pop graphics.
Week 5: Feb.21-27	Research DirectX UI. Implement Pick 'N Pop user interface.
Week 6: Feb.28-Mar.6	Research DirectInput. Deliverable: Pick 'N Pop.
Week 7: Mar.7-13	Research D3D Meshes. Deliverable: Mesh Demo.
Week 8: Mar.14-20	Research one meeting point algorithms for a flat terrain. Implement first meeting point algorithm.
Week 9: Mar.21-Apr.3	Research second meeting point algorithm. Implement 2nd meeting point algorithm.
Week 10: Apr.4-Apr.10	Research weighted terrain meeting point algorithm. Implement weighted terrain meeting point algorithm on flat terrain. Deliverable: Flat Meeting Point Demo
Week 11: Apr.11-17	Research performance testing. Begin implementing Performance testing framework.
Week 12: Apr.18-24	More research on performance testing. Deliverable: Performance Testing Framework.
Week 13: Apr.25-May.1	Analyze the performance of meeting point algorithms on flat terrain using performance testing framework. Deliverable: Comparison Paper
Week 14: May.2-8	Research height mapped terrains. Begin implementing height mapped terrains.
Week 15: May.9-15	More research on height-mapped terrains. Continue implementation.
Week 16: May.16-23	Research unit movement on height-mapped terrains. Deliverable: Height mapped terrain demo

Deliverables:

The full project will be done when CS298 is completed. The following will be done by the end of CS297:

1. Direct3D Demo (Feb. 7)

2. Pick 'N Pop Game (Feb. 28)

3. Mesh Demo (Mar. 7)

4. Flat Meeting Point Demo (Ap. 4)

5. Performance Testing Framework (Apr. 18)

6. Comparison Paper of Meeting Point Performance in Flat Terrain (Apr. 25)

7. Height mapped terrain Demo (May 16)

References:

[Rucker2002] Software Engineering and Computer Games. R. Rucker. Addison Wesley. 2002.

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

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