Hello Héctor,
Hello Sebastian,
thank you for your quick reply. Let me re-explain my question.
The main point is the navigation system. I am looking for something
like the following:
-There is a 2D map (we don't care now about how the map has been made).
-The system gets the map as an input with a starting point and a
destination.
-The system has to calculate the shortest route (maybe with A*
algorithm or similar) from the starting point to the destination, and
avoiding obstacles (that are defined in the map). Let's think in
static obstacles only.
-The map and the route have to be displayed in the OSG scene (in the
HUD, for example, but that's not a problem for me).
So, I need to know if there is a way to define the map with obstacles
(with coordinates of whatever), load it into any library, calculate
the route and transform the coordinates of the map and the route into
something that can be displayed into OSG.
Thank you.
Cheers
Okay, I see your question is a bit off-topic. But I'll give you some
hints anyways.
In my company we developed different algorithms and tools to create such
navigation meshes, to calculate (weighted) shortest paths and to
navigate a map.
Basically one option is to define polygons (which are not necessarily
your database polygons, and should be convex) which can be visited by a
model. These polygons have neighbor which define edges for moving from
polygon A to B.
Now simply treat those polygons (e.g. their center of gravity) as nodes
in a graph, and all edges between the polygons as edges in the graph
(potentially with a weight).
The resulting graph can then be traversed with A* or similar algorithms.
Also another option is to skip the polygons and simply place points to
positions that are reachable, and define edges. So basically you sort of
draw your graph to your map. Then you would again use A* on this data
structure.
As for the display of the resulting route; simply draw the resulting
line-segments from you A* search.
There are a lot of papers about automatic/semi-automatic navigation and
map creation, based on obstacle geometries, visitable polygons etc.
You will find literally hundreds of approaches, but I'm sorry that I
cannot point to a specific one, as everything is dependent on your scene.
hth
Sebastian
_______________________________________________
osg-users mailing list
[email protected]
http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
