Gantt Chart

Gantt Chart showing the timeline for the project.

Click to enlarge

Break Down

• Task 1 - Literature Review 01/10/13 - 05/11/13 (5 Weeks)
• Task 2 - Technical Review 01/10/13 - 05/11/13 (5 Weeks)
• Task 3 - Design 01/10/13 - 05/11/13 (5 Weeks)
• Task 4 - Implementation 01/10/13 - 14/01/14 (15 Weeks)
• Task 5 - Experiments and Testing 14/01/14 - 24/02/14 (6 Weeks)
• Task 6 - Analysis 14/01/14 - 24/02/14(6 Weeks)
• Task 7 - Write Up 01/10/14 - 07/04/14(28 Weeks)
• Task 8 - Make Poster 07/04/14 - 14/04/14(1 Week)

Impact on Rendering

Offloading AI onto the GPU may have an effect on rendering if too much of the resource is taken up by the pathfinding.

May need to be aware of and test this during the testing and evaluation stage of the project. possibly create a graph showing how much time is taken up by rendering vs pathfinding.

Meetings: Friday 27th September 2013

Looked over changes made to the IPO and agreed it was ready to be handed in. Submitted it to the school of computing office at 13:30.

Discussed impact that offloading AI onto the GPU may have an effect on rendering if too much of the resource is taken up by the pathfinding. May need to be aware of and test this during the testing and evaluation stage of the project. possibly create a graph showing how much time is taken up by rendering vs pathfinding.

create gantt chart of project plan for next Friday.

Look into implementing terrain, doesn't need to be complicated, don't actually need to render anything at this stage just need to be able to access the data correctly on the GPU with minimal passing of data between the CPU and GPU as this will cause a major slowdown and greatly effect performance. Look into getting interoperability working and storing the data in VBO's etc.

Keep reading papers for the lit and tech review.

Start draft chapters for the week 9 review and keep a log of any technical work done.

Initial Project Overview

Title of Project: Comparison of Pathfinding Algorithms using the GPGPU

Overview of Project Content and Milestones

The aim of the project is to implement, test and evaluate a piece of software which compares multiple pathfinding algorithms that will be run in parallel using the GPGPU. The algorithms will be compared against CPU based implementations of themselves and against each other in a range of different pathfinding scenarios.

For the project to be successful the following aspects must be implemented. One traditional path finding algorithm implemented on both the CPU and GPGPU. One other pathfinding algorithm implemented on the CPU and GPGPU, Test both algorithms in a range of different scenarios from simple flat surfaces with few obstacles to varying terrain with a wide range of static and moving obstacles, the accompanying report and documentation.

The Main Deliverable(s):

Report showing an understanding of the project and an analysis of the data gathered comparing the chosen algorithms. To hopefully show that making use of the GPGPU for computation is a feasible option for path finding algorithms. The accompanying software containing parallel and sequential implementations of multiple pathfinding algorithms.

The Target Audience for the Deliverable(s):

Game Developers, AI researchers, parallel computing researchers, GPU manufactures.

The Work to be Undertaken:

Investigate current projects and literature which have similar goals to this and gain an understanding of their findings and what limitations and problems they faced, also to identify suitable metrics to compare the algorithms against. 

Implement the chosen algorithms both on the CPU and GPGPU and test the differences in performance between the algorithms and their sequential and parallel implementations. Evaluate the data gathered to provide an understanding of the benefits/limitations of parallel pathfinding algorithms. Document the findings and the software to be included in the accompanying analysis and report.

Additional Information / Knowledge Required:

To complete the project and achieve the main goals, an understanding of programming for the GPGPU will be required. Knowledge of artificial intelligence and the different pathfinding algorithms will also be necessary.

Information Sources that Provide a Context for the Project:

Information about GPGPU programming

Nvidia - http://www.nvidia.co.uk/page/home.html

Khronos Group(OpenCL) - http://www.khronos.org/opencl/

Cuda by Example written by Jason Sanders and Edward Kandrot

Heterogeneous Computing with OpenCL written by Benedict R. Gaster, Lee Howes, David R. Kaeli, Perhaad Mistry and Dana Schaa.

Information about AI and Pathfinding

Artificial Intelligence For Games written by Ian Millington and John Funge.

AI Game Dev - http://aigamedev.com

The Importance of the Project:

A.I algorithms are one of the last parts of a typical game engine to be exploited by the GPU. By researching into this area and determining if it is possible and worthwhile to make use of these techniques could benefit game developers by allowing better and more efficient AI in games which will create a better experience for the player specifically in the mobile section where costly A.I can be a problem due to constraints on processing power and memory.

The Key Challenge(s) to be Overcome:

The biggest difficulty may be implementing the algorithms so they run on the GPGPU. There are limited resources on parallel implementations of traditional pathfinding algorithms and implementing traditional sequential algorithms in an efficient parallel way may be a difficult challenge to overcome. 

Project Plan

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
• My Own
• Irrlicht
• 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. 

Meetings: Friday 20th September 2013

Overview of our meeting on Friday 20th September.

Went over first draft of initial project overview and discussed what changes needed to be made before handing in on Friday 27th September.

Discussed what work needs to be completed for the following week.

Next Steps

• Create wiki for the project.
• Create plan for the project.