de_dust2 Pathfinding

This was a project for my Master's. It includes pre-processing on the Counter Strike: Global Offensive map de_dust2 followed by multiple pathfinding algorithms.

The original image of the map can be found in the URL: https://readtldr.gg/simpleradar.

Original Map

Preprocessing

• importing map

• whiten available areas

• blacken parts with obstacles and outside areas

• plot the occupancy grid map

The first step was importing the map and transforming it to an occupancy grid map (OGM). Then BrushFire algorithm was used to help us with the next step.

Occupancy grid map

BrushFire

Probabilistic road maps (PRM)

• uniform graph applied on the map

• In the random graph the points are dispersed randomly on the map ​

• blue dots are the nodes of the graph ​

• red dots are the staring and ending points(not necessarily in the graph) ​

• green lines are the bidirectional connections

The second step was equipping the map with a uniform probabilistic road map (PRM) and a random one. After this the pathfinding algorithm where use on random point on the map.

Uniform PRM

Random PRM

Dijkstra & A*

• Applied dijkstra and a_star on both PRMs

• The path is visible in the plot (blue dots)

• The expansions (searches) are visible in the plot (red lines)

Step three, Dijkstra and A* are executed on the PRMs and plotted showing the searched area (red lines) by the algorithm and the final path it found (blue dots). Every step of the algorithms can be seen by a single tweak in the code.

Dijkstra Uniform PRM

Dijkstra Random PRM

A* Uniform PRM

A* Random PRM

Rapidly-expanding Random Tree (RRT) and Rapidly-expanding Random Tree Star(RRT*)

• the RRT algorithm does not use the graph

• instead makes a new (random) path inside the empty space

• For the RRT* the way of expansion is a little different resulting on combed looking tree

• RRT* algorithm has the choice of running for double the duration for an even more "combed" tree

Step four, rapidly-expanding random trees (RRT) and rapidly-expanding random trees star (RRT*) were used straight on the OGM to connect the goal with the start node. As in the previous step area visited and found path can be seen on the plots.

RRT

RRT*

Path smoothing

• Makes the path smoother to allow for model restrictions

• Attention is needed so the new path does not overlap with obstacles

Lastly, path smoothing is applied in every path found by the algorithms with care, so none of the points end up outside the bound of the map.

Dijkstra Uniform PRM Smooth Path

Dijkstra Random PRM Smooth Path

A* Uniform PRM Smooth Path

A* Random PRM Smooth Path

RRT Smooth Path

RRT* Smooth Path

Observations:

• The algorithms take much longer to run on the random graph. That is normal due to its size.

• Something I found very interesting is that the path searched area (red lines) on the random PRM look awfully similar with the RRT searched area.

• RRT algorithms take longer to run which is normal considering the way new expansions are chosen and how many are rejected.