Graph Searches

In the process of implementing AI for my Game Engine, I ended up implementing a series of graph search algorithms in C++.

Resources

• Slideshow used for talk: Google Drive, Local
• Spreadsheet of test results: Google Drive, Local

Project Description

While working on AI for my Game Engine I underestimated just how much of an undertaking it would be to implement a semi-sophisticated navigation scheme. Some months later I now have my own implementation of both Graphs and search algorithms in C++.

Ground Work

Implementing these algorithms required quite a bit of setup as C++ does not provide a default implementation of Vertices, Edges, Graphs, or Trees. If you are interested in the implementations, please see the following links.

• Graph:
• Header
• Implementation
• Tree
• Search
• See list below for specific search implementations

Implemented Algorithms

• Breadth First Search:
• Header
• Implementation
• Depth First Search:
• Header
• Implementation
• Greedy Best First Search:
• Header
• Implementation
• A* Search:
• Header
• Implementation

Wrappers

The first wrapper I developed for these searches was for the purpose of manual testing of the search algorithms. It provides options to load a graph from a file (scroll down for graph format), running searches, and toggling Verbose Mode, which adds a lot more descriptive output of what is going on during the search. As the searchers are designed with polymorphism in mind, declaring the actual searcher based on the input given is quite simple as seen here.

The second wrapper for the searches was designed to execute automated testing for timing purposes. This wrapper runs each search algorithm against every possible combination of nodes in the specified graph. and reports on average time taken by each algorithm. This is the wrapper which was used to generate the testing results linked to below.

Simple Graph Language

The language I used to annotate graphs for this project is extremely simple and only supports two types of lines, one which indicates a vertex and one which indicates an edge.

• Vertex Syntax: v ID Heuristic
• Vertex Example: v 5 3
• Edge Syntax: e VertexID1 VertexID2 EdgeCost
• Vertex Example: e 1 2 12

This language was really only designed for testing purposes and built into the wrappers described above.