A genetic alternative to grid-based path finding algorithms (e.g., A*) in 2D environments in continuous space. The algorithm uses angular encoding to represent the path from the direction of the movement and its step size. For this a time unit (e.g., a second) must be chosen which then the step size will represent the maximum distance can be taken in one unit. The presented code concerns a 2D environment with a number of rectangular objects and it solves the problem of finding a collision-free path between the centroids of any given two rectangular objects where other objects are considered as obstacles. The genetic algorithm contains traditional elements such as crossover and mutation operators. However, there are two problem-specific operators added, which are important for the convergence of the algorithm. One seeds the straight angle into the solutions. The other one increases the similarity between the angles. The objects and the path found by the genetic algorithm are then visualized using SFML.
The input file used contains the coordinates of the rectangular objects. 6 columns are used per object. Column 1: x coordinate of the lower end corner, Column 2: y coordinate of the lower end corner, Column 3: x coordinate of the upper end corner, Column 4: y coordinate of the upper end corner, Column 5: x coordinate of the centroid, Column 6: y coordinate of the centroid.