Questions tagged [astar]
A* is a graph shortest-path algorithm that uses a heuristic function to speed up the search
25 questions
3
votes
1
answer
237
views
How to improve shortest path results with Dijkstra/A* on a hexagonal mesh
I am working with traversable polygons and need to calculate the shortest path across them. To do this, I generated a hexagonal mesh over the polygons, extracted the edges, and applied both Dijkstra ...
- 497
0
votes
0
answers
76
views
Wayfinding for indoor map without route network data
In general, to implement path planning, we need to create a road network beforehand and then use algorithms like Dijkstra for pathfinding. Meanwhile, the A* algorithm has been widely used in scenarios ...
- 803
0
votes
1
answer
45
views
Create x1,y1,x2,y2 columns of pgRouting a* algorithm from a GeoJSON/shapefile
I have used pgRouting in PostgresSQL to routing using Dijkstra's algorithm. Now I need to do the same with a* algorithm, The A* algorithm needs x1,y1,x2,y2 values instead of geometry.
How can I ...
- 39
0
votes
0
answers
117
views
Converting shapefile to raster and extracting coordinates of each pixel
I currently have an EPSG:4326 - WGS 84 MultiPolygon shape in QGIS.
I need to make a path planning tool to cross the lake above. In which case I need to convert this shapefile into a raster (from ...
- 1
2
votes
1
answer
534
views
PGrouting costs
Most algorithms have two functions:
A normal one: like dijkstra()
A Cost-version: like DijkstraCost()
I want the result of the cost version: A fast computation of the total seconds.
In mine edges ...
- 123
1
vote
1
answer
178
views
How to get path cost in A* shortest path finder of GeoTools?
I am computing a shortest path with A* algorithm of GeoTools:
AStarShortestPathFinder pf = new AStarShortestPathFinder(
myGraph, nodeFrom, nodeTo, myAstarfun);
pf....
- 10.3k
0
votes
1
answer
289
views
Sequenced path using pgrouting (going through the POI of the user)
I'm using the pgr_astar function of Postgres and I want to personalize the optimal path proposed according to the preferences of the user.
For example if the pg_astar propose the red path, I want to ...
- 59
0
votes
0
answers
505
views
Road class restriction of OSM data
I'm manipulating an OSM dataset of Chicago to find the optimal path for heavy duty vehicles. Are there some roads restrictions? Which class is not allowed for heavy vehicles?
These are road classes ...
- 59
1
vote
0
answers
151
views
Optimal path proposed by pgr_astar is not the optimal one?
I'm using the function pgr_astar function of PostgreSQL to find the optimal path between two points in the dataset of Chicago.
The query I'm using is:
SELECT a.seq, a.id1 AS node, a.id2 AS edge, b....
- 59
2
votes
0
answers
68
views
pgr_astar function does not accept negative values?
I'm using postgreSQL and I'm running the pgr_astar function to get the optimal path. I calculated my path using a formula that uses angle of elevation or the angle of depression as input. So I'm ...
- 21
0
votes
1
answer
70
views
Ambiguous values on OSM to calculate optimal path: Which value should I use?
I'm using San Francisco OSM dataset, I want to calculate the optimal path using pgrouting(pgr_astar)
The problem that I don't know which column should I use?
For example:
I want to calculate the ...
- 59
0
votes
0
answers
57
views
Understanding the problem of applying A* on a multilevel network
I am currently working on an indoor routing project for a multilevel building.For this, I want to find a shortest path over multiple level (or 'floors'). I have read some papers on A* in such an ...
- 1,853
1
vote
1
answer
1k
views
How to convert a coordinates to indice array (vice versa) in a NetworkX graph?
I want to use a raster for a A* and bidirectional Dijkstra path analysis in NetworkX. I am using Python for this project.
Raster example (it's a png file converted when uploaded, but the real problem ...
- 121
3
votes
0
answers
300
views
Weird (longer) route from using cost_s as cost in pgRouting?
I am currently developing application that want to use the fastest time to arrive as parameter for the routing. And i know that pgRouting has 'cost_s' column which calculated from length_m and ...
3
votes
0
answers
752
views
Accelerating python looping process for A-star path finding on DEM surface?
I try to make an A-star Path Finding program base on tile-graph (image raster data as graph) where each pixel values represent as cost and elevation..
In my case, DEM raster data was called by using ...
- 712
-1
votes
1
answer
2k
views
Convert Road layer shapefile into a graph
I'm going to use Astar algorithm to find a path between two selected points.And I used the following code for that.Is there any way I could convert my Road Layer shapefile into a graph, which can be ...
- 145
2
votes
1
answer
2k
views
Does not show shortest path in networkx (in QGIS)
I used the following commands (in qgis console) to get the shortest path with astar algorithm. But the result shows 'NetworkXNoPath' every time. Why was that? Please help me to find a solution to this ...
- 145
1
vote
1
answer
489
views
Development guide for beginner? [duplicate]
I'm new to GIS and mapping, and I need to learn how to create web map application for my project. I'm really confused on what to use. I have read PostGIS, OpenStreetMap, and OpenLayers. I'm wondering ...
- 225
2
votes
0
answers
284
views
Adding nodes into graph using QGIS?
I'm new to qgis and in here I want to find a path between two selected points on the map(Roads-vector layer). The points are selected by the user, using mouse clicks.
So here I used the astar ...
- 145
5
votes
1
answer
1k
views
pgRouting 2.0 slow execution of A star algorithm [closed]
Recently, I wanted to test pgRouting ver. 2.0. I created the database structure with osm2po and imported UK map from geofabrik. The data was imported correctly.
When I execute a sample query in ...
- 159
1
vote
1
answer
48
views
Is it possible to calculate the route when source and destination having same junction using A* algorithm?
I am using A* Algorithm to calculate the shortest path. The route was calculated based on the junction. Shortest route was calculated when there was two or more junction in between source and ...
- 19
2
votes
2
answers
1k
views
Python/GDAL: Best way to read in raster for use in A* search algortihm
I want to create a least cost path program with Python and GDAL since I couldn't find any open source cost path additions for use in Python.
As recommended here the best approach is to use A* search ...
- 8,049
0
votes
1
answer
551
views
How to correctly convert data from OSM with osm2po to use it with A* algorithm?
I want to make my A-Star fast, by using heuristics. At the moment it is very slow and even slower than my Dijkstra. I thougt A-Star is in the worst case as fast as Dijkstra. I convert my OSM bounding ...
- 165
2
votes
1
answer
329
views
Why is pgrouting astar not consistent?
I route from 1 end of a circular route to the opposite end. Visually it is obvious that going clockwise is shorter, however shortest_path_astar sometimes picks clockwise and sometimes anti-clockwise.
...
- 1,565
3
votes
0
answers
546
views
Shortest distance from pgrouting with cost not being length: optimal solution
I'm using pgrouting shortest_path_astar with a complicated cost function. It gives back the edges, vertices and costs.
I would like to get the total distance of this shortest path (i.e., the sum of ...
- 875