Student Projects
SCEE R&D have co-ordinated a variety of student projects in the past, for selected universities. A selection of past and present project topics are published here.
Present projects
Sponsored by the Cambridge Studio:
Past projects
- None currently listed.
Project details
Creation of reliable mesh data for agent pathfinding
For efficient pathfinding of agents in computer games, one approach is to use a "navigation mesh" which describes the traversable floor areas. These meshes often do not match the hand-built world geometry due to the vagaries of in-game collision detection and response. As an extreme example, unusually-shaped agents could have collision profiles that change over time with animation, and could give navigation meshes that do not easily correlate with the built environment.
As an example, a commercial product that uses navigation meshes can be found here:
http://www.pathengine.com/
In the past these navigation meshes have been hand-built by designers. To save development time, a tool to generate robust navigation meshes would be invaluable.
The aim of the project is to write a program that will generate reliable, well-formed "floor mesh" that could be used for agent pathfinding. The output can be a simple text format.
As input it could take a point cloud, or set of discrete connection data, generated from running a game engine. The data could be supplied from running one of our games, or from an engine of the student's choosing. In addition, we can supply mesh data from existing game scenes, if required.
Particular problems in this area are:
- coping with overlapping input data
- producing robust and efficient meshes for a variety of input data
- deciding on an in-game collision representation that works well with mesh-based navigation
- potentially supporting navigation behaviours that does not use the floor mesh (e.g. jumping over objects, using ladders)
The application would ideally support mesh simplification, to allow tuning of the mesh's complexity.
One extension of the system could be to write an application to allow automatic traversal of a virtual world to provide the input data to the mesh generator, in an efficient manner.
For demos of a commercial product with similar features, see:
http://kynogon.nerim.net/products/demos/index.html
The demo "Automatic PathData Generator" is particularly instructive, although it uses waypoint-based pathfinding rather than meshes.
This project is flexible in scope, in that it may be possible to change the emphasis so that the main part of the process is in generating topological information rather than building the mesh."
Lossless SIMD Compression/Decompression
This project would be to investigate which lossless compression algorithms would be suitable for adaptation to utilize a SIMD architecture. The student would need to detail how the algorithm and/or data would need to change to be suitable for SIMD processing. What the trade-offs of these changes would be, and to implement the algorithm and make comparisons with the original algorithm implementation. The student may also need to consider the various SIMD architectures as some may provide additional processing instructions suited to this problem.
A good source of lossless compression algorithms can be found at http://en.wikipedia.org/wiki/Category:Lossless_compression_algorithms
Lossless compression is generally used for generic text or binary data, a good example being the zip file on PC platforms. A number of the algorithms in the previous link are specific to video or audio data. The aim of this project is to investigate generic data compression and decompression for text and binary data, not just a specific types of data such as audio or video.
You should also consider the following:
- There may be no suitable solutions.
- The SIMD architecture could only be used to a limited extent
- Fully utilising the SIMD architecture causes issues or trade-offs that make its usage unfeasible in general situations.