Abstract:

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

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.

References:

[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 http://pluralsight.com/wiki/default.aspx/Craig.DirectX/MeshBasicsTutorial.html

[5] Andera, Craig. Mesh Creation Tutorial. Retrieved May 8, 2006, from http://pluralsight.com/wiki/default.aspx/Craig.DirectX/MeshCreationTutorial.html

[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 http://www.thehazymind.com/archives/2005/06/tutorial_5_rend.html

[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 http://msdn.microsoft.com/coding4fun/gamedevelopment/beginning5/default.aspx

[10] Eliosoff, Jacob, Unger, Richard. (1998) Welcome to the Minimum Enclosing Circle Emporium. Retrieved May, 2006, from http://www.cs.mcgill.ca/~cs507/projects/1998/jacob/

[11] Muhammad, Rashid Bin. Smallest Enclosing Circle Problem. Retrieved May, 2006, from http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

[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.