Minimum Tests For Project To Be Succesful
- Time sequential diffusion application
- Time parallel diffusion application
- Compare paths of sequential and parallel diffusion in terms of distance, correctness and quality
- Time sequential Dijkstra
- Compare paths from diffusion and dijkstra in terms of distance, correctness and quality.
Extra Tests If Time Allows
- Look at number of agents against time to find a path
- Look at how paths handle introduction of obstacles over time
- Introduce obstacles which are static once placed
- Introduce dynamic obstacles
- Look at moving goals.
1. Literature Review
- Pathfinding algorithms in general
- A*
- Ant Colony
- Diffusion
- Lazy theta *
- Parallel versions of pathfinding algorithms
- Pathfinding algorithms in different scenarios
- GPGPU programming
- Difference between CPU/GPU
- Advantages/Disadvantages
- Environments/Scenarios
- Look at environments from a game perspective
- Terrain
- Enemies
- Moving Obstacles
- Metrics for comparing algorithms
- sequential vs parallel
- quality of pathfinding algorithm
2. Technical Review
- Cuda
- OpenCL
- Game Engines
- Rendering Engines
- Terrain
- What gives most control over meshes and least effect on performance.
- Physics
- Bullet
- Havok
- Is physics needed?
3. Design
- Algorithms
- pseudo code (sequential)
- pseudo code (parallel)
- scenarios
- different environments
- range of obstacles
- distance
- metrics
- what will be used?
- why are the useful?
4. Implementation
- Implement engine
- Terrain
- physics(if needed)
- cuda support
- implement algorithms
- sequential version of alg #1
- parallel version of alg #1
- sequential version of alg #2
- parallel version of alg #2
5. Experiments and Testing
- Test all implementations of the algorithms in all the identified scenerarios and gather the specificed metrics for each algorithm.
6. Analysis
- graph and compare results from experiments
- draw conculsions about the implementations of the algorithms
7. Write Up
- Write up and complete report.
