Exploring Well-Known Path-Finding Algorithms With SFML Graphics Library
In my last article, I showed you how to unify the implementation of the most well-known graph-traversal algorithms. Now, let’s look into performance differences and ways to make it more visually appealing
Behind the Scenes
A few years ago, Yandex organized a contest called Robots Couriers with an enticing prize: a ticket to a closed self-driving conference for professionals. The contest resembled a game. Participants were tasked to find optimal routes on a map and optimize delivery using robotic couriers.
As I delved into the topic, I discovered that despite route finding being a solved problem, it continued to interest the professional game development community. Between 2010 and 2020, engineers made significant optimizations to the A* algorithm, particularly beneficial for AAA games with massive maps. Reading articles and research papers on these optimizations was an exciting experience.
Furthermore, the contest requirements were designed to enable easy assessment of program outputs by the contest’s testing system. As a result, there was little emphasis on visualization.
I found exploring this field intriguing and developing a small application that uses well-known graph algorithms to find routes on a grid map. To visualize my findings, I employed the SFML graphics library.
Goal
This project builds upon one of my previous endeavors, where I demonstrated that four well-known path-finding algorithms (BFS, DFS, Dijkstra’s, and A*) are not fundamentally different and can be implemented universally. However, showcasing significant performance differences among these algorithms in that project was challenging.
I aim to use improved test data in this article and design something visually exciting. While the Yandex Contest task mentioned earlier aligns well with my goals, I will not solve their specific problem here since it heavily relies on their test system, which is currently unavailable.
Instead, I will extract general ideas for input parameters from that contest and create my implementation.
Imaginary World
Imagine a technically advanced and innovative city where the future has arrived long ago. In this city, courier robots deliver most orders, and it has become a rarity for someone to deliver an order from a cafe. In this task, we invite you to participate in finding optimal routes to deliver orders efficiently.
Let’s envision the city as an N × N map. For simplicity, we assume that each robot occupies precisely one cell, and each cell can either be passable or not for the robots. In one step, a robot can move in any of the four cardinal directions (up, down, left, or right) if the target cell is free.
And I’m ignoring the rest of the original task:
At the beginning of the test, you need to output the number of robots you want to use to deliver orders and their initial coordinates. The construction of each robot will cost
Costcrubles.Next,
Titerations of the simulation will be performed. One iteration represents one virtual minute and consists of 60 seconds. At each iteration, your program will be given the number of new orders, and in response, the program should tell you what actions each robot performs (60 actions per robot).For each successfully delivered order, you will receive
max(0, MaxTips — DeliveryTime)dollars in tips, whereMaxTipsis the maximum number of tips for one order, andDeliveryTimeis the time from when the order appeared to its delivery in seconds.The total number of points you earn in one test is calculated by the formula
TotalTips — R × Costc, whereTotalTipsis the total number of tips earned,Ris the number of robots used, andCostcis the cost of building one robot. TheCostcandMaxTipsvalues are set in each test. If you earned fewer tips than you spent on making robots, your total points will be 0. You will also receive 0 points for the test if you perform incorrect actions.
Input
The program uses standard input to read the parameters. This approach allows us to specify test data of various complexities using input files.
The first line of input contains three natural numbers: N (the size of the city map), MaxTips (the maximum number of tips per order), and Costc (the cost of building one robot). I ignore MaxTips and Costc parameters for my first implementation and may consider that in the future.
Following that, each of the next N lines contains N characters representing the city map. Each string can consist of two types of characters:
#— indicates a cell occupied by an obstacle.— indicates a free space
Next, you will receive two natural numbers: T and D (T ≤ 100,000, D ≤ 10,000,000). T represents the number of interaction iterations and D represents the total number of orders.
Output
Your task is to visualize the map and the optimal routes using the SFML graphics library.
Modelling the Maps
I’m fond of maps represented as a grid of cells. Thus, I prefer to render all the results and map them as a grid on a cell-by-cell basis.
There is also an option to execute a path search right on the grid without using any additional data structure (I have implemented this for learning purposes. You can see the results in the code).
However, because of a grid, it is easy to represent a map as a graph in one way or another. I prefer to use an adjacency list of cells for most algorithms like BFS, Dijkstra’s, and A-Star. For algorithms like Bellman-Ford, using an Edges List instead of an Adjacency List may make sense. That’s why if you explore the codebase, you will find all of it, and they are all working examples.
To split the logic and responsibility, I have a Navigator entity responsible for executing path finding according to the orders and tasks configuration specified via AppConfig file and related map files.
App Config looks like this:
{
"font": "../../data/arial.ttf",
"map": "../../data/maps/test_29_yandex_weighten_real_map",
"shadow": false,
"map_": "../../data/maps/test_08_low_res_simple_map",
"map__": "../../data/maps/test_10",
"map___": "../../data/maps/test_07_partially_blocked_map",
...Note that “map_”, “map__”, etc., are not configuration properties. They are ignored during the application run. Since there is no way to comment on part of the JSON file, I use underlining in the property name so it can stay in the config file but not be used.
The map file looks like this:
25 50 150
#########################
#########################
#########################
###.......#####.......###
###.......#####.......###
###.......#####.......###
###...................###
###.......#####.......###
###.......#####.......###
###...................###
######.###########.######
######.###########.######
######.###########.######
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
######.###########.######
#########################
#########################
#########################
#########################
2 4
2
6 6 4 20This is one of the simplest examples that contain either blocked or not blocked cells. I have prepared many examples of input parameters and test data. Starting from very small parts that let you debug and learn the code, finishing with a huge piece of map (from the real existing city) that allows us to measure the performance of a Graph algorithm.
How Do We Draw Maps
When a map contains only cells with a binary state (either blocked or non-blocked), any edge of a graph exists.
To find a path in the graph, we have to represent it efficiently. Like in my previous article, I have used an adjacency list with the relationship as Vector[NodeId]->points to->Vector[Neighbour Nodes]:
typedef std::vector<std::vector<std::shared_ptr<Cell>>> Graph;Interestingly enough, when exploring grids, it’s not necessary to use graphs at all. We are capable of traversing grids using BFS/DFS algorithms cell by cell without thinking about edges. See the method
_GetPathByBFSOnGrid.
First, the initialization code reads the file and converts it into the grid row by row and column by column. Here’s what that looks like:
bool RectangularMap::LoadMap(const std::string& filepath, bool shadow)
{
...
// Fill the grid.
_verticesNumber = 0;
for (int row = 0; row < _height; row++)
{
...
for (int col = 0; col < _width; col++)
{
int x = col;
int y = row;
if (line[col] == BLOCK_CELL)
{
// Create a shared pointer to safely pass pointers between the classes.
_grid[row][col] = std::make_shared<Cell>(x, y, line[col],
blockColor, shadow, _scaleFactor);
}
else
{
...
}
}
}
// Make a graph
InitialiseGraph();
...
}Then, it creates an actual graph as an adjacency list:
void RectangularMap::InitialiseGraph()
{
MapBase::InitialiseGraph();
...
unordered_set<int> visited;
for (int rr = 0; rr < _grid.size(); rr++)
{
for (int cc = 0; cc < _grid[rr].size(); cc++)
{
if (_grid[rr][cc]->GetId() > -1)
{
for (int i = 0; i < 4; i++)
{
int r = rr + dr[i];
int c = cc + dc[i];
if (r >= 0 && c >= 0 && r < _width && c < _height &&
_grid[r][c]->GetId() > -1)
{
if (_isNegativeWeighten)
{
...
}
else
{
_adjacencyList[_grid[rr][cc]->GetId()].push_back(_grid[r][c]);
}
}
}
}
}
}
}Grid representation is useful to draw on the screen using the SFML library. We can draw it by creating geometric objects (this is precisely what I do for small maps):
...
for (int j = _visibleTopLeftY; j < _visibleBottomRightY; j++)
{
for (int i = _visibleTopLeftX; i < _visibleBottomRightX; i++)
{
_grid[j][i]->Draw(_window, _scaleFactor);
}
}
...
sf::RectangleShape tile;
tile.setSize(sf::Vector2f(_cellSize - 5, _cellSize - 5));
tile.setPosition(sf::Vector2f(_x * _cellSize, _y * _cellSize));
tile.setFillColor(_color);
window.draw(tile);Or, for larger maps, we can do it pixel by pixel, which is more efficient. Here’s what that looks like:
sf::Uint8* pixels = new sf::Uint8[_width * _height * 4];
for (int j = _visibleTopLeftY; j < _visibleBottomRightY; j++)
{
for (int i = _visibleTopLeftX; i < _visibleBottomRightX; i++)
{
int index = (_grid[j][i]->GetY() * _width + _grid[j][i]->GetX());
sf::Color color = _grid[j][i]->GetColor();
pixels[index * 4] = color.r;
pixels[index * 4 + 1] = color.g;
pixels[index * 4 + 2] = color.b;
pixels[index * 4 + 3] = color.a;
}
}
sf::Texture texture;
texture.create(_width, _height);
texture.update(pixels);
sf::Sprite sprite;
sprite.setTexture(texture);
sprite.setScale(cellSize, cellSize);
_window.draw(sprite);Finally, let’s see what a map defined by the file test_25_xmax would look like.
Initially, the file’s definitions look like this:
..............C.................
..............#.................
.............###................
............#####...............
...........#######..............
..........##1###2##.............
.........###########............
........##3######4###...........
.......###############..........
......#################.........
.....###################........
....#####################.......
.............###................
.............###................
.............###................And a map rendered with SFML looks like this:
Because I wanted all of that to be controlled by the user with the keyboard, I left all the user-behavior logic in the main.cpp. I like to call it Controller logic.
The SFML library makes it easy to handle keyboard events:
while (window.isOpen())
{
Event event;
while (window.pollEvent(event))
{
if (event.type == Event::Closed)
window.close();
if (event.type == Event::KeyPressed && event.key.code == Keyboard::Space)
{
... Do what you need here
}
}
}The main idea is that pressing the space button will trigger the program to read and render the map file. Then, you can load routing tasks and calculate the shortest path between two points on a map by creating a second trigger (press the space button again). Here’s how to do that:
...
if (navigator->IsReady())
{
navigator->Navigate(); // Finding route between two points
}
else
{
if (map->IsReady()) // Second SPACE press runs the routing
{
skipReRendering = true;
if (navigator->LoadTasks(filepath))
{
navigator->SetMap(map);
}
}
else // Load and draw map
{
drawLoading(window, font);
if (!map->LoadMap(filepath, shadowed))
{
return 0;
}
drawProcessing(window, font);
}
}
...We Need To Go Deeper
I wanted to play with more Graph algorithms, which all have their limitations, so I also implemented multicolor maps that multiweighted graphs can represent.
Every cell is colored, which means that the edge not only exists but also applies some weight (or fee, or fine, you name it). So, the edge might be blocked, half-blocked, not blocked, etc. You got the idea.
So now, I have implemented multicolor maps that look joyful — like a game that’s ready to play (example from file test_31_multi_weight_graph_map):
Some of the configuration files contain more complex maps from really existing cities, like the test_29_yandex_weighten_real_map:
As a challenge, we should now handle maps with very flexible configurations. RectangularMap.cpp contains a lot of logic inside, including all the graph algorithms and even more than needed (because I like to play with things, even if it’s not particularly useful for now).
I have implemented BFS#Line 598, Dijkstra#Line 299, A-Star#Line 356, Bellman-Ford#Line 428 algorithms, and a number of additional “utility” algorithms like Topological Sort, Single Source Path, that are not useful for the current application state (because they work on Directly Acyclic Graphs, which are not the type of Graphs I currently use), but I have some ideas to use it in future improvements.
I didn’t polish all the code, but it allows me (and, I hope, will allow you) to play with the code and compare performance metrics.
Sorry about some commented lines here and there, maybe some dirty code… it’s all a way of learning :). To grasp an idea of what’s inside, I recommend you review the RectangularMap.h.
There are also some fun features, like a Focus feature allowing one to render only a particular map part. It changes focus by rerendering the necessary part using the Observer pattern when the user presses the PgDown or PgUp buttons. Improving this feature and implementing “Zoom” functionality is pretty easy. Use it as a homework assignment if you like it.
Focus feature with a working map file, test_29_yandex_weighten_real_map:
The Classes diagram looks like this:
Run and Play
The most joyful part is running this little application and playing with variations of its configuration and algorithms. You can do a lot of experiments by using various map files as input parameters with different test data and changing the code's logic.
After starting, you need to press SPACE. An application will render a map according to the configuration file, and it makes a lot of sense to start exploring from the simplest test cases and then transition to the most complex ones.
Pressing SPACE again executes the routing algorithms and finds the path between the start and the nearest order. By the way, it’s not done yet, but it is easy to implement ways to read all the rest of the orders available in map configuration files and to execute pathfinding to all of them.
Here is the route found on the map defined by file test_18_yandex_super_high_res:
It is also capable of finding routes in the maps that simulate existing cities, like the test_29_yandex_weighten_real_map:
Finding efficient paths between two coordinates becomes challenging for algorithms like BFS but can be easily done by A-star.
Based on the cells found in the map configuration files, the application will treat the map as a weighted or non-weighted graph and will select the right algorithm for it (and you can easily change this as well). It’s easy to see the difference between BFS and A-Star performance:
Final words
With this, I want to leave you alone and let you play with these code examples. I hope you find it fascinating and will learn a lot from it.
Stay tuned!
