wrongsyntax/astar

A* pathfinding implementation in Python

Uzair // wrongsyntax

A software engineering student at UofA.

• All of my projects are available at https://github.com/wrongsyntax?tab=repositories

Languages and Tools:

astar's Issues

IndexError when trying to add another waypoint to data.csv

Traceback (most recent call last):
  File "[...]/AStar/tree.py", line 136, in <module>
    waypoints, nofly_region = create_safe_waypoints(parsed_nodes)
                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "[...]/AStar/tree.py", line 63, in create_safe_waypoints
    safe_waypoints[name] = (safe_region.vertices[i].x, safe_region.vertices[i].y)
                            ~~~~~~~~~~~~~~~~~~~~^^^
IndexError: list index out of range

Occurred when attempting to add a new obstacle node 'F' at the end of data.csv.

Generate test data

Find a way to generate more test data, rather than just one csv file.

• Randomly generated polygon vertices that form a valid polygon
• START and TARGET node
• Classify nodes as either 'start', 'target', or 'obstacle'
• Save to csv files for use in testing

Given a list of nodes, find all valid connections between nodes

Given a list of nodes and their (x,y) coordinates, find connections between nodes that avoid the region that must be avoided.

Nodes are given as:

• The current position is known. This is the START position.

• A series of nodes is given as the region that must be avoided. A safety_margin is added to the nodes. All nodes will move a constant amount away from where they originally are given as. A route needs to be found around this region.

• The TARGET node is given.

• Check if a straight line drawn between two nodes passes through the no-fly zone.

• Generate the tree as required for the A* algorithm.

• Find distance of each node from START (G_COST)

• Find distance of each node from TARGET (H_COST)

Create documentation for treeplot.py

Create and add documentation for treeplot.py in the wiki.

Refactor tree.py to use OOP

Making a Waypoint and Tree class could make the code more clear.

Not a necessary change as functionality would not change but could be done.

Create documentation for datagen.py

Create and add documentation for datagen.py in the Wiki.

Implement A* on the generated tree to find optimal route

Return list of waypoints in order.

Visualize all nodes, paths, regions, etc.

Implement a way to visualize everything to ensure nothing weird is happening (polygons being incorrect was discovered by visualizing them)

Using matplotlib, plot all relevant data.

• Original waypoints
• Safe waypoints
• Restricted no-fly region
• Valid paths between waypoints
• Maybe invalid paths as well (?)
• Label points