Random Path Visualizer

This is a personal project that was initially started to automate the creation of permutations for my cell group for prayer purposes. I then decided to repurpose it into a generic path generator and also experiment with different ways to connect nodes in a graph to look more like a smooth curve. A visual representation of the generated path can be shown by providing an image along with an input file that will dictate the possible paths that can be drawn on the image.

Currently, the generator has 2 main methods to draw the paths between each member.

1. A greedy node selector that uses Euclidean distance heuristic that is not guaranteed to return a path. It does not use the same node twice for drawing so that no lines overlap completely with each other.

2. Dijkstra’s shortest path algorithm from each member to the next, uses Euclidean distance heuristic to improve its speed. Users can toggle between allowing usage of the same node twice, to compare between the different output.

It also has an option to convert the current paths that are stiff-looking into smooth Bezier curves.

Lastly, it has an option to adjust the Bezier curves created to minimally intersect any other members on the final image. This can be seen by comparing the image above (adjusted) and the un-adjusted image below.

Sample Results

The following images show the generated visual path of the same permutation.

• Path with Greedy algorithm:

  

• Path with Dijkstra’s algorithm:

  

  The paths are more direct compared to the Greedy algorithm

• Path with Dijkstra’s algorithm where nodes can be used more than once:

  

  Notice the overlapped paths near E that might lead to visual clutter.

• Path with Dijkstra’s algorithm that have been converted to Bezier curves:

  

  The paths are now smooth though there are a few overlaps on members' images.

• Path with Dijkstra’s algorithm as Bezier curves, adjusted for minimal overlapping:

  

  Notice the paths near E and D that have been shifted slightly.

Controls

• Type Z and X to cycle through the pathfinding methods

• Type B to convert current path into Bezier curves

• Type A to adjust Bezier curves to minimally intersect other members on the image (only when Bezier curves are being used)

• Type R to generate a new path

• Type S to save the current path (to prevent future path generation to repeat any pairs)

• Type UP ARROWKEY to increase the size of the image window

• Type DOWN ARROWKEY to decrease the size of the image window

• Type Q to quit

Features

• Visual representation of the generated path (sample input for 11 members is provided)

• Path can be saved to prevent any repetition of pairs in future path generation

  • Etc. If A → B → C was saved previously, A → B and B → C will not repeat

• Arrows on the image gradually changes color so that it is easy to follow the path

• Different pathfinding methods and modifiers in drawing lines between the members

Inputs:

• Text file with list of members (sample_input2.txt)

  • Intermediate nodes and all nodes' pixel locations followed by the adjacency list of each node (only required if visualization is desired) (sample_input.txt instead of sample_input2.txt) Also can specify member image shape and size

• Image with members represented (only required if visualization is desired) (sample_img.png)

• Total number of members (only required if visualization is desired) (Edited in random_path_generator.py)

Sample input files are included. Their filepaths can be edited in random_path_generator.py.

Nodes in the graph comprise of each member AND intermediate nodes that will form the paths between each member

Syntax of text file input with input image:

# Example in sample_input.txt
# Each member's pixel location
# Start with members, then intermediate nodes
# Members: C if a circle is closer to the member's representation in the image and S for a square representation
#          Size refers to the radius for a Circle or width for a Square, in pixels
# Add ':X' at the end of a member's line to indicate that it is only an obstacle for paths to avoid
[MemberName]:[PixelX],[PixelY]:[C/S][Size][:X if member is only an obstacle]
[MemberName2]:[PixelX],[PixelY]:[C/S][Size][:X if member is only an obstacle]
[NodeNumber]:[PixelX],[PixelY]
[NodeNumber2]:[PixelX],[PixelY]

# Leave one line empty, then the adjacency list
[NodeNumber]:[ConnectedNodeNumber],[ConnectedNodeNumber2]
[NodeNumber2]:[ConnectedNodeNumber],[ConnectedNodeNumber2]

Lines starting with "#" are treated as comments and are ignored.

Syntax of text file input without input image:

# Example in sample_input2.txt
# List of members separated by commas
[MemberName],[MemberName2],[MemberName3],[MemberName4]

Only the first uncommented line is read, following lines are ignored.

Lines starting with "#" are treated as comments and are ignored.

Required packages:

• Numpy

• OpenCV