Genetic Path Finding

Genetic Path Finding was my major project and dissertation I completed within my third year of University. I had an interest in AI and was widening my horizons with this project. The project is essentially a comparison between a genetically created program and A* that each attempt to reach the target location on a randomly generated map. I began by researching into a variety of different areas of AI and I came across Genetic Algorithms. This was only part of my project since I wanted to move a character based on a specific program or set of code generated by the algorithm, this is known as Genetic Programming.

  • Language: C++,
  • IDE: Visual Studio 2010,
  • Graphics API: OpenGL 3.3.

1.0 Research

The project began as all projects should; with research. I looked into a wide variety of topics to gain knowledge and an understanding of AI and path finding. The topics researched include; A*, group movement, Neural Networks (and back propagation), Genetic Algorithms (and Genetic Programming) and the main two graphics APIs for the graphical representation section of the program. This led to reading sections of some books, articles and journals written by great authors such as John Koza.

2.0 Design

The next logical step was to design the system, I had been given a very basic framework to work with which displayed a basic cube through a application wrapper using OpenGL. This was the initial starting point for the project before developing all the additions that brought the project to completion. The best way to understand my design is to look over the UML diagram created during the design phase of the project.

The classes in the upper-left of the diagram ( CGApp, CGAppDelegate and OpenGL) show the basic framework provided while the others show the classes I have either modified or entirely created myself while developing the project. I decided upon a naming convention early in the project which was to name prefix the classes that I had written with the letter 'P' (standing for 'project') since this was my third year project and dissertation.

The first class I wrote was the PController class, this interfaced with the OpenGL class in that there were the standardised Update and Render calls. The design I went with was to call these methods within each of the classes that composed the PController class. An example of this is that the map must be both updated and rendered at each frame interval, this would be done by the placing a call to the controller's update and render functions within the OpenGL class, the controller would then call the corresponding functions within the PMap class and the PMap would then call the corresponding functions within the PGround class resulting in a rendered ground object within the scene. This basic design was mimic for each of the classes that needed to be either updated or rendered within the entire program to create a consistent and easy-to-understand design.

The controller class also acts as a Mediator (design pattern) in that other classes can only gain certain information by asking the PController class. An example of this is that for path finding to work correctly; a simple representation of how the map is laid out is required. The PAIPath class computes the path finding within the project and so would ask the controller class to collect the information from the PMap class. The path finding algorithm used was the A* algorithm, however this was only used to compare against the program created through the evolution processes of genetic programming.

2.1 Genetic Programming

The genetic programming element, and arguably the main part of the project was designed and implemented, and this section explains the design and implementation of the system. A basic genetic programming library was used (originally written by Larry Gritz) with some modifications since it was written purely in C rather than C++. The Genetic Program class provides the interface that is used by the different scenes (the path finding scene and the painted desert scene), however each of the classes that setup a given scene are also responsible for the setup of the GP. This is completed by defining the essential group of elements for the GP, these are:

  • Objective: A statement of the problem which we are attempting to solve.
  • Terminal Set: The list of terminals which can be included in any symbolic expressions generated by the GP.
  • Function Set: The list of functions which can be included in any symbolic expressions generated by the GP.
  • Fitness cases: A problem dependant set of test cases which will be used by the fitness function to derive the raw fitness value for each individual.
  • Raw fitness: The method by which the fitness function will calculate the raw fitness measure for each individual.
  • Standardised fitness: An optional method of conversion between raw fitness and standardised fitness.
  • Hits: An auxiliary measure of the number of fitness cases which achieve satisfactory fitness.
  • Wrapper: An optional conversion between output values of an evolved symbolic expression and input values needed by the fitness function.
  • Parameters: Any of the major or minor parameters which control the GP run.
  • Success predicate: An optional condition which may terminate the GP run before the maximum number of iterations.

Once each and every one of these elements have been correctly setup and defined; the genetic program begins to create populations of potential individuals (in this case, collections of functions with terminals as inputs). Once an initial, random, set of individuals are created; they are each tested using the fitness function (defined within the setup). This function returns the fitness score for the individual based on how effective it is at moving the green cube from the starting location in the lower right position of the grid to the end point at the upper left grid position.

3.0 Screenshots

It was clear that with the description above alone, it would be hard to visualise what my completed program was doing and so a collection of screenshots along with explanations was pieced together to construct a more clear image of the completed program.

This image shows how the path finding problem was graphically rendered, there is a basic plane showing the grid-layout of the map with black cubes showing the walls. The green cube and path shows the program generated by the genetic program for this problem and the red cube and path shows how it would be solved using the A* algorithm. This was a failed attempt for the genetic program

This image shows how an evolved program can find a solution that almost matches the optimal path computed by the A* algorithm.

Alongside the main program and graphical representation a basic debug console was written within a small class that redirected the output stream. This was used mainly for debug purposes and it was interesting to output the results and the programs generated.

4.0 Implementation and Additional Information

The complete code can be found on my Github account, the project write-up including research, design and implementation in more depth can also be found here.

Mesh Stripification

Mesh Stripification was the first assignment for the graphics module completed as part of the masters year of my degree. It consists of converting a polygonal mesh into a series of triangle strips in order to save on the number of points and indices sent to the GPU when rendering.

  • Language: C++,
  • IDE: Visual Studio 2012,
  • Graphics API: DirectX 11.

1.0 Research

The project began with research into the various stripification algorithms and how they were implemented. Once a group of stripification algorithms were discovered it was clear that a data structure was required in order to stripify the mesh correctly, the requirement that could not be satisfied with the simple set of vertices and indices was a quick way of searching for edges that were touching eachother, this is when I discovered the Doubly Connected Edge List data structure.

This data structure was used along with a custom version of the  Stripstripification algorithm.

2.0 Design

There wasn't a great deal of designing to do since there was a data structure that was freely available that could be used and the Strip algorithm had already been designed, however the system was built using the DirectX 11 graphics API with a single class created for the loading, converting and rendering of the stripified mesh.

The design and general idea of the algorithm can be found here.

3.0 Screenshots

This image shows the program running, there is also a debug window used for the output of each phase of the stripification process.

4.0 Implementation

The complete code can be found on my Github account, the project write-up including, research, design and implementation in much more depth can be found here.

Cloth Simulation

Cloth Simulation was the second assignment for the graphics module in the masters year of my degree. It consists of simulating a particle lattice using forces and constraints that results in a cloth-like material when rendered. The normal method of simulating cloth - such as Nvidia's method found here - uses the geometry shader, however for this implementation I used a new feature in DirectX 11 called the compute shader.

  • Language: C++,
  • IDE: Visual Studio 2012,
  • Graphics API: DirectX 11.

1.0 Research

A great deal of research went into the DirectX 11 pipeline, how to use the compute shader, general cloth simulation and verlet integration in order to get the cloth rendering using the GPU at a good framerate.

2.0 Design

This was a fairly small project and so the design was already readily available within the Nvidia paper linked above and other resources on the internet. I created a new class to encapsulate all of the cloth properties and setup.

3.0 Screenshots

The above image shows the program running alongside the debug window showing the force controls and the time taken for the class to setup the cloth. During university I would often time my code and attempt to speed it up as much as possible.

4.0 Implementation

The full project and code can be downloaded from my Github account. The write up is also available, it contains a more in-depth explanation of the research, design and implementation phases of this project and can be found here.