TheDeveloperBlog.com
C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML
C# Pathfinding Algorithm
This C# tutorial shows how to develop a simple pathfinding algorithm.Pathfinding. A pathfinding algorithm navigates obstacles.
We use a pathfinding algorithm to always find the shortest path between two points, even with obstacles. We implement an algorithm similar to the A-Star Pathfinding algorithm.
Caution: This is not the most efficient, nor the best, pathfinding algorithm in the entire world. It works as a simple tutorial.
Steps. First, let's assume we have a program with an interface, and a 2-dimensional grid of squares for our field. We will use a 15 by 15 square grid here. What follows is how the monster will find the hero.
First steps. Beginning at the hero's location, place numbers that indicate the number of steps each square is. It uses the lowest number. Using the lowest number each time, fill up the board with these numbers.
So: As you get further from the hero, the numbers get higher. This can continue for any distance.
Checking squares. It checks when all squares have numbers. When all the squares are numbered, the hero will be surrounded by 1's, and the monster will be surrounded with much higher numbers.
Then: It finds the path. The monster's best path will be found by following the lowest number it finds on each step.
Player positions. Look at the screenshot at the top, and you can see two orange squares. The two orange squares are the monster and the hero. They are both the same color because the way the algorithm works—there is no difference.
Tip: The blue line is the best path, as found by the pathfinding algorithm described here.
Store data. We need some objects at the class level to store our data. I show what we do with these later in this tutorial. Here are the class-level member variables. These are the fields of our object model.
Code that creates 2D array: C# // Movements is an array of various directions. Point[] _movements; // Squares is an array of square objects. CompleteSquare[,] _squares = new CompleteSquare[15, 15];
Movements. We start by defining a movement array of Point structs. Think of the movements a monster can take as a grid of 9 squares, one in every direction. We can define these squares by their coordinates.
And: When we go to use this array, we add it to the regular coordinates to find the new square.
Table of movement coordinates
[-1, -1] [0, -1] [1, -1]
[-1, 0] [0, 0] [1, 0]
[-1, 1] [0, 1] [1, 1]
Method that initializes coordinates: C#
void InitMovements(int movementCount)
{
// Use 4 or 8 directions, depending on the setup. We use collection
// initializer syntax here to create the arrays.
if (movementCount == 4)
{
_movements = new Point[]
{
new Point(0, -1),
new Point(1, 0),
new Point(0, 1),
new Point(-1, 0)
};
}
else
{
_movements = new Point[]
{
new Point(-1, -1),
new Point(0, -1),
new Point(1, -1),
new Point(1, 0),
new Point(1, 1),
new Point(0, 1),
new Point(-1, 1),
new Point(-1, 0)
};
}
}
Validation. We only have a 15 * 15 square grid, and we can't allow anything to move off of the board. That would cause our program to throw an exception. Here we set up a nice validation function. The function is static: it saves no state.
ValidCoordinates method: C#
static private bool ValidCoordinates(int x, int y)
{
// Our coordinates are constrained between 0 and 14.
if (x < 0)
{
return false;
}
if (y < 0)
{
return false;
}
if (x > 14)
{
return false;
}
if (y > 14)
{
return false;
}
return true;
}
Square data. A data structure stores the board square data. Each square can have a hero, a monster, a wall, or be empty. We put that information in the form on an enum type. The following snippet shows the various enum values squares can contain.
Enum definition: C#
enum SquareContent
{
Empty,
Monster,
Hero,
Wall
};
Now, we will use that enum to define various parts on the board squares. Here I show you how we read in the maps from files on the disk. The next code I am showing is the data structure that we store each square.
Data structure for squares: C#
class CompleteSquare
{
SquareContent _contentCode = SquareContent.Empty;
public SquareContent ContentCode
{
get { return _contentCode; }
set { _contentCode = value; }
}
int _distanceSteps = 100;
public int DistanceSteps
{
get { return _distanceSteps; }
set { _distanceSteps = value; }
}
bool _isPath = false;
public bool IsPath
{
get { return _isPath; }
set { _isPath = value; }
}
public void FromChar(char charIn)
{
// Use a switch statement to parse characters.
switch (charIn)
{
case 'W':
_contentCode = SquareContent.Wall;
break;
case 'H':
_contentCode = SquareContent.Hero;
break;
case 'M':
_contentCode = SquareContent.Monster;
break;
case ' ':
default:
_contentCode = SquareContent.Empty;
break;
}
}
}
Important parts of code
Code: ContentCode
Notes: A value from the SquareContent enum
Code: DistanceSteps
Notes: Stores the number of steps needed for the monster
to get to this square
Code: IsPath
Notes: Boolean that says whether this is part of the best
path from monster to hero
Code: FromChar
Notes: Translates a char from our file into an enum value
for the ContentCode
File format. It is by far easier to use a text file to store the map information. Look at FromChar above, and you will see that W stands for Wall, and H for Hero, and M for monster, and a space for empty.
Tip: These are the characters in our files. The following text is used to build the display.
File format example
M|
WWWWWWWWWWWW|
|
|
WWWWWWWWWWW |
|
|
|
WWWWWWWW|
|
WWWWWWWWWWWW |
|
H |
|
WWWWWWWW |
Walls. If we look closely at all the W characters, which stand for walls, we see how they are turned into the map—similar to the screenshot at the top. Next, we examine the short code that reads in the file itself.
ReadMap method definition: C#
private void ReadMap(string fileName)
{
// Read in a map file.
using (StreamReader reader = new StreamReader(fileName))
{
int lineNum = 0;
string line;
while ((line = reader.ReadLine()) != null)
{
// Get the char array.
char[] parts = line.ToCharArray();
for (int i = 0; i < parts.Length; i++)
{
_squares[i, lineNum].FromChar(parts[i]);
}
lineNum++;
}
}
}
You can see that the file is read in line-by-line. Then, the squares array is set from each char. But where is that array? Look up at the first code sample—it is declared there. It is a 15 * 15 array of the CompleteSquare object.
If you look closely at the top screenshot, you will see a black rectangle. That is where the mouse pointer should be. At that point, 17 is the distance according to the algorithm I am describing.
So: The monster would need to walk 17 steps to get to the black rectangle square.
Find paths. First, I will refer you to another page on this site to see how I use enumerators to iterate through the 2D arrays that represent the board. This code is not the most efficient. You could rewrite it to directly use nested loops.
Now, we look at the important part of the algorithm. It implements the pathfinding algorithm itself. The first part, where I get a point called starting point, uses a simple function that locates the hero on the board (not shown).
Next: We set the hero's distance at 0. The algorithm will set all the surrounding squares as 1.
Pathfind method implementation: C#
void Pathfind()
{
// Find path from hero to monster. First, get coordinates of hero.
Point startingPoint = FindCode(SquareContent.Hero);
int heroX = startingPoint.X;
int heroY = startingPoint.Y;
if (heroX == -1 || heroY == -1)
{
return;
}
// Hero starts at distance of 0.
_squares[heroX, heroY].DistanceSteps = 0;
while (true)
{
bool madeProgress = false;
// Look at each square on the board.
foreach (Point mainPoint in Squares())
{
int x = mainPoint.X;
int y = mainPoint.Y;
// If the square is open, look through valid moves given
// the coordinates of that square.
if (SquareOpen(x, y))
{
int passHere = _squares[x, y].DistanceSteps;
foreach (Point movePoint in ValidMoves(x, y))
{
int newX = movePoint.X;
int newY = movePoint.Y;
int newPass = passHere + 1;
if (_squares[newX, newY].DistanceSteps > newPass)
{
_squares[newX, newY].DistanceSteps = newPass;
madeProgress = true;
}
}
}
}
if (!madeProgress)
{
break;
}
}
}
Stopping the algorithm. Our algorithm could stop once it finds its destination. The important detail here is that I only mark a step with a number, if it is a smaller number than the one already on the square.
Tip: This is because we must always look for the shortest distance and not the longest distance.
And: The longest distance is large, as you might guess. The maximum is determined by the numeric type itself.
Shortest path. Here we trace the shortest path from hero to monster. What this code does is follow the smallest number each step of the way, and mark the squares with a true Boolean if it is part of the shortest path.
Note: Look carefully at how we stop the loop, when we hit the SquareContent.Hero square.
HighlightPath method implementation: C#
private void HighlightPath()
{
// Mark the path from monster to hero.
Point startingPoint = FindCode(SquareContent.Monster);
int pointX = startingPoint.X;
int pointY = startingPoint.Y;
if (pointX == -1 && pointY == -1)
{
return;
}
while (true)
{
// Look through each direction and find the square
// with the lowest number of steps marked.
Point lowestPoint = Point.Empty;
int lowest = 100;
foreach (Point movePoint in ValidMoves(pointX, pointY))
{
int count = _squares[movePoint.X, movePoint.Y].DistanceSteps;
if (count < lowest)
{
lowest = count;
lowestPoint.X = movePoint.X;
lowestPoint.Y = movePoint.Y;
}
}
if (lowest != 100)
{
// Mark the square as part of the path if it is the lowest
// number. Set the current position as the square with
// that number of steps.
_squares[lowestPoint.X, lowestPoint.Y].IsPath = true;
pointX = lowestPoint.X;
pointY = lowestPoint.Y;
}
else
{
break;
}
if (_squares[pointX, pointY].ContentCode == SquareContent.Hero)
{
// We went from monster to hero, so we're finished.
break;
}
}
}
Also: Some pieces are missing from this document, but I have included them in the download. I hope my coding style is relatively clear.
Next: We send colors to a custom control that displays the field. The control draws all the colored rectangles.
Highlight. We take the enum on each square, and then send colors to an object called boardControl1. This next section will discuss some of the code that goes into board control. It was more difficult to create than the main algorithm.
I am not a graphics guru by any stretch of the imagination, but I have learned how to efficiently draw rectangles and use painting geometry in Windows Forms. The results are what you see in the above two screenshots.
DrawBoard method implementation, highlight: C#
void DrawBoard()
{
foreach (Point p in Squares())
{
int x = p.X;
int y = p.Y;
int num = _squares[x, y].DistanceSteps;
Color setColor = Color.Gainsboro;
SquareContent content = _squares[x, y].ContentCode;
if (content == SquareContent.Empty)
{
if (_squares[x, y].IsPath == true)
{
setColor = Color.LightBlue;
}
else
{
setColor = Color.White;
}
}
else
{
if (content == SquareContent.Hero)
{
setColor = Color.Coral;
}
else if (content == SquareContent.Monster)
{
setColor = Color.Coral;
}
else
{
setColor = Color.Gray;
}
}
boardControl1.SetHighlight(setColor, x, y);
}
boardControl1.Invalidate();
}
Summary. Here we implemented a pathfinding algorithm, but it is very simple and fundamental. I encourage you to download the full source code and play with it. The program can be fun, as the path automatically adjusts itself as you add walls.
Note: Originally this article contained a link to complete source code, but the full code is no longer available.