I'm a gameplay programmer
focused on developing
engaging and unique experiences!

My Resume Learn more

Pathfinding Algorithms in openFrameworks

The code for this article can be found on GitHub here!

One of the many problems a game developer will run into is how to have an AI agent navigate around their simulation. This article will explore the approach of representing the game world as a directed weighted graph that can be used in conjunction with Pathfinding Algorithms like A*. The end result will be an agent that appears to have environmental awareness as it moves throughout the world!

Directed Weighted Graphs

Directed Weight Graphs are a common data structure that consist of vertices and edges. They can be used to model a variety of real and simulated structures such as roadmaps and flow charts, however in games they are particularly useful for modeling spaces agents exist in. It allows us to break a continuous world into a discrete form that code can understand.

Pallet Town as a Directed Weighted Graph

A simple example maybe a directed weighted graph for the first town in Pokemon, Pallet Town!

If we were to overlay a Directed Weighted Graph over this simulated world, one possible outcome may look like this.

In this image, letters represent vertices and lines represent edges that connect vertices. Vertices are usually points of interest in the world and edges are the paths that one would take between those points of interest. The numbers over the lines represent the "weight" of that edge, which usually indicate the amount of effort it would be to use that path.

Generating Directed Weighted Graphs

While you can hand create graphs for the spaces your agent will navigate i n, it is an incredibly time consuming process. Another approach is to generate a directed weight graph based on a Division Scheme. Division Schemes are an approach to dividing up your game world in a semi-automatic to fully automatic fashion.

Tiled Graphs

One of the simplest ways to automatically generate a graph is to overlay a grid over your game world. Then have each rectangle on that graph represent a vertex with edges connecting adjacent rectangles.

This technique can be used to generate as many vertices and edges your computer can handle with little manual work. Some parameters you can change to tweak the resulting grid would be the width and height of each rectangle.

Localization & Quantization

Division schemes also have the feature of converting between graph vertices and actual world positions. Quantization is the process of converting from world positions into graph vertices and Localization is the process of converting from graph vertices into world positions.

Directed Weighted Graphs Data Structures

Directed Weighted Edges

One possible representation of a Directed Weighted Graph is to actually only track the edges between vertices! This class would look similar to this:

class CDirectedWeightedEdge
{
public:
	CDirectedWeightedEdge(float InCost, int InSource, int InSink);

	inline float GetCost() const { return Cost; }
	inline int GetSource() const { return Source; }
	inline int GetSink() const { return Sink; }

private:
	float Cost;
	int Source;
	int Sink;
};

This means that nodes could simply be integers to indicate a unique node in the graph.

Directed Weighted Graphs

A graph could than be simply represented as a vector of DirectedWeightedEdges:

class CDirectedWeightedGraph
{
private:
	std::vector<CDirectedWeightedEdge> Edges;
};

Pathfinding Algorithms

Now that we have a representation of Directed Weighted Graphs, we can iterate over them using pathfinding algorithims to help an agent navigate through the world. The most common pathfinding algorithm in games is A*, however it is closely related to Dijkstra. For games, A* is useful as an optimization over Dijkstra using heuristics.

Heuristics

Heuristics are a rule of thumb that algorithms can use to make educated guesses on the data set they are working with. A good heuristic allows A* to find the shortest path to a given node much faster than Dijkstra. These educated guesses maybe based on the estimated cost of going down a certain path. Good heuristics have the qualities of being admissible, which means they consistently underestimate or is equal to the actual cost of what its estimating.

Random Heuristic

One example of a heuristic can be as basic as returning a random estimate.

float GetEstimate(int CurrentNode, int GoalNode) const
{
	return static_cast<float>(rand()) / (static_cast<float>(RAND_MAX));
}

However, this has many qualities of a bad heuristic since it isn't admissible. It may randomly underestimate the cost of a given vertex, but isn't consistent at all. As it is random, it also has the possibility of overestimating.

Euclidean Distance

A more practical example of a heuristic is euclidean distance.

float GetEstimate(int CurrentNode, int GoalNode) const
{
	ofVec2f CurrentPosition = DivisionScheme->Localize(CurrentNode);
	ofVec2f GoalPosition = DivisionScheme->Localize(GoalNode);

	return (CurrentPosition - GoalPosition).length();
}

Euclidean Distance is admissible because it consistently underestimates the cost of a node. This is because there is no possible shortest path between two nodes other than the line between them. It's also consistent in this way, which makes a great heuristic for A*.

Conclusion

In the end, directed weight graphs and pathfinding algorithms are another step in creating agents that appear intelligent! However, a look under the hood shows their intelligence has foundationsl in discrete logic.

No Comments Yet.

Leave a comment