A very simple C++ application routing lines to not intersect each other. The Graphical User Interface (GUI) consists of a 600 x 600 pixel map in which it is possible to draw lines by mouse clicks. The first click will set the start point of the line and the second click will set the end point and draw the line. The line will be drawn so that it will not intersect with any other line nor the pixel map border.
This has only been tested on Ubuntu Linux 18.04 LTS running
- CMake 3.10.2
- QT 5.9.5
- libcanberra-gtk-module 0.30
- gcc/g++ 7.3.0
- GNU Make 4.1
with common software development packages. It is not configured to build for Windows yet.
All the commands listed here are assumed to be run in a Linux shell.
To configure the CMake build environment (or to clean it), go to the Build directory under the root path and run
./cmake_build.sh
This should only have to be run once initially or when wanting to clean the CMake environment. To make the Line router application run
make line_router
On success the binary file will end up in the Bin/line_router folder under the root path.
Google Test 1.8.0 has been integrated with the source code and will be built when building the tests. Configure the CMake build environment if not already done so (see the Build section above)
./cmake_build.sh
To build and run the tests run
make all test
CMake and GNU Make is used as a build environment to generate the executable. The source code consists of three main parts
- Line router main
- UI (QT 5)
- Path planner (A*)
and grid help classes under Grid.
The main function decides what kind of path planner to use (currently there is only A_star_planner available) and
its grid size. Right now it creates a 600 x 600 A_star_planner (Path_planner). It will also create and start the
UI window Line_router_window and pass along the Path_planner.
The UI is using the QT 5 toolkit. It consists of one window, the Line_router_window. It sets up the window,
creates a Line_router_paint_widget and passes along the Path_planner.
The Line_router_paint_widget sets up the pixel map environment where it is possible to draw lines. It will wait
for a mouse click on a point that is inside of the pixel map and set that point to be the start point. Then the start
point is marked with a red dot on the pixel map. The second mouse click inside the pixel map will set the end point and
will pass the start and end point to the Path_planner. If the Path_planner is successful in finding a path from
start to end a line will be drawn on the given path and all the points passed will be set to blocked in the
Path_planner. If the Path_planner is unsuccessful in finding a path it will just unmark the first point and wait
for the first mouse click again. Would have been nice with a dialog popup in those cases.
The algorithm to find the route from start to end is based on the search algorithm A*. It is designed to find the path from the start point to the given end point which has the smallest cost. In this implementation the cost is the pixel-distance traveled.
The algorithm has to determine, for each point visited, the cost to the point where it is currently at and an estimate of the cost to the end point from the current point. More specifically:
f(p) = g(p) + h(p)
where g(p) is the cost from the start point to the point p and h(p) is the estimated cost from point p to the end point. f(p) is the total minimal cost from start to end going through the point p.
In this implementation the horizontal and vertical travel of one point increases the g(p) by one. A diagonal move, however, increases the g(p,s) by
sqrt( 1^2 + 1^2 ) ~= 1.4142136.
The estimate of the cost to the end point is calculated as the coordinate distance from point p to the end point, such -that
h(p) = sqrt( dx^2 + dy^2 )
where dx is the x-coordinate distance from start point to point p and dy is the y-coordinate distance from start point to point p.
The algorithm will calculate and store the total cost f(p) for the point currently visited, p, and its eight neighbors (horizontal, vertical and diagonal). Neighbors outside border are not considered. It will then decide what point to visit by choosing the point with the currently cheapest total minimal cost f(p). It could be a neighbor to the currently visited point or a point visited previously or its neighbors.
If a point has another line crossing it, it will not be considered for visit and the cost will remain infinite.
For more general information, see A* search algorithm.
There are three grids implemented (if not counting the QPixmap)
- Availability grid
- Path cost grid
- Path grid
All grids are implemented as flattened fixed sized std::vector. In a width x height grid the index in the
std::vector for the width coordinate x and height coordinate y is as follows
index = x + y * width
where x and y are zero indexed. And for calculating x and y from index
x = modulus( index, width )
y = floor( index / width )
All grids have the same size as the QPixmap, right now it is 600 x 600. The total size of all the 600 x 600 grids,
discarding std::vector overhead, is
sizeof(bool)x600x600 + sizeof(float)x600x600 + sizeof(size_t)x600x600
On my 64-bit system with g++ 7.3.0 this makes a total cost of
1x600x600 + 4x600x600 + 8x600x600 ~= 4.46 MB
This bool grid is used to set available/blocked grid points. It is initialized with all true values, i.e. available. Once a line has been drawn all the points it has been passing and all of their neighbors will be marked as false, i.e. blocked. The neighbors are marked in order to more clearly see that the lines are not intersecting.
This float grid is used to keep track of the path cost g(p) (see Path finding algorithm section) for each visited point. It is initialized to infinity, except for the starting position which has a zero value. The path cost grid will be updated for the currently visited point and its available neighbors.
This size_t grid consists of flattened grid indexes that point to a previous neighbor point visited. It is updated by the currently visited point that sets all its available neighbors to the currently visited flattened grid index. When the end point has been reached this grid can be used to backtrack the path to the start point.
The grid is initialized to zero but the initial value does not matter since the path grid won't be used (only updated) until the end point has been reached.
The code has been tested on Ubuntu Linux 18.04 LTS running on a Dell XPS 15 Infinity (9560) with the following specifications:
- CPU: Intel Core i7 7th Gen. 2.8 Ghz.
- GPU: Nvidia GeForce GTX 1050 Ti Max-Q.
- RAM: 16GB DDR4/2,400MHz.
For a 600 x 600 grid with all points available it takes around 0.4 ms to find a path from point (0, 0) to
(599, 599).
For a 2000 x 2000 grid with all points available it takes around 2.3 ms to find a path from point (0, 0) to
(1999, 1999).
For a 600 x 600 grid with a diagonal block from point (1, 598) to (599, 0) it takes around 85 ms to find a path
from point (0, 0) o (599, 599).
For a 2000 x 2000 grid with a diagonal block from point (1, 1998) to (1999, 0) it takes around 1.1 s.
The most costly parts of the code is when checking if neighbors are available and when adjusting the heap of the priority queue where the points to visit are located.