# pgRouting with Shooting-Star algorithm

Shooting-Star algorithm is the latest of pgRouting shortest path algorithms. Its speciality is that it routes from link to link, not from vertex to vertex as Dijkstra and A-Star algorithms do. This makes it possible to define relations between links for example, and it solves some other vertex-based algorithm issues like "parallel links", which have same source and target but different costs.

## Prepare routing table for Shooting-Star

For Shooting-Star you need to prepare your network table and add the "reverse_cost" and "to_cost" column. Like A-Star this algorithm also has a heuristic function, which prefers links closer to the target of the search.

ALTER TABLE ways ADD COLUMN reverse_cost double precision; UPDATE ways SET reverse_cost = length;

ALTER TABLE ways ADD COLUMN to_cost double precision; ALTER TABLE ways ADD COLUMN rule text;

## Shortest Path Shooting-Star core function

Shooting-Star algorithm introduces two new attributes:

- rule: a string with a comma separated list of edge IDs, which describes a rule for turning restriction (if you came along these edges, you can pass through the current one only with the cost stated in to_cost column)
- to_cost: a cost of a restricted passage (can be very high in a case of turn restriction or comparable with an edge cost in a case of traffic light)

shortest_path_shooting_star( sql text, source_id integer, target_id integer, directed boolean, has_reverse_cost boolean )

Note:

- Source and target IDs are link IDs.
- Undirected graphs ("directed false") ignores "has_reverse_cost" setting

### Example for Shooting-Star "rule"

Shooting* algorithm calculates a path from edge to edge (not from vertex to vertex). Column vertex_id contains start vertex of an edge from column edge_id.

To describe turn restrictions:

gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule -----+--------+--------+------+----+----+----+----+---------+------ 12 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 14

means that the cost of going from edge 14 to edge 12 is 1000, and

gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule -----+--------+--------+------+----+----+----+----+---------+------ 12 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 14, 4

means that the cost of going from edge 14 to edge 12 through edge 4 is 1000.

If you need multiple restrictions for a given edge then you have to add multiple records for that edge each with a separate restriction.

gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule -----+--------+--------+------+----+----+----+----+---------+------ 11 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 4 11 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 12

means that the cost of going from either edge 4 or 12 to edge 11 is 1000. And then you always need to order your data by gid when you load it to a shortest path function..

### Example of Shooting-Star core function

SELECT * FROM shortest_path_shooting_star(' SELECT gid as id, source::integer, target::integer, length::double precision as cost, x1, y1, x2, y2, rule, to_cost FROM ways', 293, 761, false, false);

vertex_id | edge_id | cost -----------+---------+--------------------- 4232 | 293 | 0.0059596293824534 3144 | 293 | 0.0059596293824534 4232 | 4632 | 0.0846731039249787 ... | ... | ... 51 | 761 | 0.0305298478239596 (63 rows)

### Wrapper function WITH bounding box

Wrapper functions extend the core functions with transformations, bounding box limitations, etc..

SELECT gid, AsText(the_geom) AS the_geom FROM shootingstar_sp('ways', 293, 761, 0.1, 'length', true, true);

gid | the_geom --------+--------------------------------------------------------------- 293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833)) 293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833)) 4632 | MULTILINESTRING((18.4074149 -33.9443308,18.4077388 -33.9436183)) ... | ... 762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966)) 761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275)) (62 rows)

Note:

- There is currently no wrapper function for A-Star without bounding box, since bounding boxes are very useful to increase performance. If you don't need a bounding box Dijkstra will be enough anyway.
- The projection of OSM data is "degree", so we set a bounding box containing start and end vertex plus a 0.1 degree buffer for example.