This safe routing package / API was created for LA Hacks 2023. This was created to solve the problem of efficient path finding with point avoidance, as the original project idea catered to finding walkable paths while avoiding areas deemed as dangerous.
The original maps and corresponding graphs are sourced from Open Street Maps. All coordinates are assumed to be in cartesian format.
The package centers around the Routes object, which gives a path given a graph (of type Graph, also in package) and a level_handler, which is described in more detail below.
The algorithm is essentially a-star with pruning as defined by a user-given function, passed in through the level_handler parameter of the Routes object. The level_handler takes in four parameters: neighbor_ids, current_point_id, source_id, destintation_id, and the Graph object. The output of level_handler should be a subset of neighbor_ids.
The reason for inputting and outputting an entire list rather than checking for whether an individual point is valid is to allow for pruning according to the entire neighbor_ids list, as well as the source_id and destination_id.
To get coordinates from a node_id, use the function Graph.get_coordinate.
First, create the graph from an OSM ID (from Open Street Maps). This is done through graph.util.get_graph_from_osmid. Then initialize the corresponding Graph and pass it into Routes. A rough outline can be seen in runserver.py.
Call Routes.get_path to generate a path and whose output will be of type Route. Use Route.path to get a list of ordered coordinates.
The REST API can also be used. It is currently setup to only path within the San Francisco region as defined by OSM ID R111968, although this can be changed in runserver.py. If you do change this, make sure to change the corresponding BOUNDS variable. Otherwise you will receieve an error.
To change the level handler to your custom implementation, replace dummy_handler on line 30 in the runserver.py file with your function call.
To start it, run the runserver.py script. It will start a Django server at localhost:8000. To get a path, make a GET request to the path https://localhost:8000/api/routing/route with parameters x0, y0, x1, and y1. These are used to define the source and destination coordinates, which are (x0, y0) and (x1, y1) respectively. The response will be in JSON format, converted from a Route object.