I have two points in 3D space (A and B) and some sort of obstacle between them, I need to find a path to avoid colliding with an obstacle. I use a*star algorithm and in 2D space everything works fine. How to adapt this algorithm to 3D space?

On 11-02-07 12:03 PM, Modestas Sekreckis wrote:
> I have two points in 3D space (A and B) and some sort of obstacle between
> them, I need to find a path to avoid colliding with an obstacle. I use a*star
> algorithm and in 2D space everything works fine. How to adapt this algorithm
> to 3D space?

Does the obstacle have "holes" that the path might travel through?

Are you looking for shortest path or for some kind of mixed metric such as "a 
slightly longer path that has fewer turns is better, if it isn't much longer" ?

How "thick" does the path need to be? E.g., if it needs to round corners 
within obstacles then the shape of the travelling object becomes important 
because short narrow objects can navigate sharper turns than wider or longer 
objects. Even if the path must go completely outside the obstacle, we need to 
know how close it can come and "how close" it actually gets is going to depend 
upon the shape and orientation of the travelling object at the time it goes by.


Didn't you already post this question before, around September or so??

I think he's looking specifically for a MATLAB implementation of A*.
(http://en.wikipedia.org/wiki/A_star)
It's a cool algorithm.  (After I "invented" it during my dissertation,
I found out a few weeks afterward that it had already been invented
about twenty years prior.  Bummer.)  I looked, but I didn't see
anything on the File Exchange so it looks like he'll be writing his
own.  There have been a lot of variants since then (D* etc.) - maybe
some are better, I don't know since I haven't kept up to date on that
field.  Anyway, it's the kind of thing where you need to customize it
for your situation anyway so I'm not sure how much time adapting
someone else's A* would save you.

On 8 Vas, 03:10, "Think two, count blue." <rober...@hushmail.com>
wrote:
> On 11-02-07 12:03 PM, Modestas Sekreckis wrote:
>
> > I have two points in 3D space (A and B) and some sort of obstacle between
> > them, I need to find a path to avoid colliding with an obstacle. I use a*star
> > algorithm and in 2D space everything works fine. How to adapt this algorithm
> > to 3D space?
>
> Does the obstacle have "holes" that the path might travel through?
>
> Are you looking for shortest path or for some kind of mixed metric such as "a
> slightly longer path that has fewer turns is better, if it isn't much longer" ?
>
> How "thick" does the path need to be? E.g., if it needs to round corners
> within obstacles then the shape of the travelling object becomes important
> because short narrow objects can navigate sharper turns than wider or longer
> objects. Even if the path must go completely outside the obstacle, we need to
> know how close it can come and "how close" it actually gets is going to depend
> upon the shape and orientation of the travelling object at the time it goes by.
>
> Didn't you already post this question before, around September or so??

Obstacle don't have "holes".
Looking for a path to be close to the shortest, but not necessarily
the shortest. It must be capable of 3D manipulators.
 Shape of the travelling object don't important.
Yes  I wrote a similar question earlier, but then I did not know A *
algorithm. Now I know how it works and I was able to adapt it to 2D
space, but the final version of the manipulator will have to work in
3D