a* tutorial, for beginners

[Admin]

Another robot pathfinding tutorial:

http://www.policyalmanac.org/games/aStarTutorial.htm

[neo01124]

http://theory.stanford.edu/~amitp/GameProgramming/
Check this out as well, really interesting link 

Hey Admin i wanted to ask, isnt ur wavefront algorithm a special case of a* where g is set to zero?

[paulstreats]

Is there any advantage over using a standard wavefront style algorythm?

The only one that i can see is that it calculates for turning while you are moving. If you look at the diagrams, there is a faster way or a way to get to the goal in less steps then what is shown but this approach seems to work on the basis that it is faster to move through say 4 blocks instead of 3 to get to the goal because otherwise you have to stop and turn first

[benji]

nice links guys

the problem of these algorithms is that they consider that the size of an obstacle is the same size of the robot

[HDL_CinC_Dragon]

The only one that i can see is that it calculates for turning while you are moving. If you look at the diagrams, there is a faster way or a way to get to the goal in less steps then what is shown but this approach seems to work on the basis that it is faster to move through say 4 blocks instead of 3 to get to the goal because otherwise you have to stop and turn first

.... what? Are you talking about the picture above? Because the route plotted is the fastest route in that case. Explain your thinking a bit?

[benji]

Robots needs smooth paths,, not always shortest , another good link

http://www.gamasutra.com/features/20010314/pinter_01.htm

[paulstreats]

A traditional wavefront would look like this:



But to actually follow the path, the robot would have to stop and and turn at the bottom of the blue pillar.

So, assuming that the robot is at a standing start, the following image would be better, There is 1 more square involved but the robot wouldnt have to stop which would save time even though its travelling a greater distance (it would also operate more smoothly)



The following would be more realistic though to make sure that the bot didnt bump into the corners

[HDL_CinC_Dragon]

It would have to turn the same amount of times though.
In both pictures, assume that the bot is already facing the bottom of the image.
Original path:
It would drive forward 1 square(1s,0t). Then turn 45deg to its right(1s,1t). Then drive forward 1 square(2s,1t). Then turn 45deg to its right(2s,2t). Then drive forward 2 squares(4s,2t). Then turn 90deg to its right(4s,3t). Then drive forward 1 square(5s,3t). Then turn to its left 45deg(5s,4t). Then drive forward 1 square(6s,4t).
So for the first path, it had a displacement of 6 squares and turned four times and turned 225 total degrees. And with your suggested path:

Suggested path:
It would drive forward 1 square(1s,0t). Then turn 45deg to its right(1s,1t). Then drive forward 1 square(2s,1t). Then turn 45deg to its right(2s,2t). Then drive forward 2 squares(4s,2t). Then turn 45deg to its right(4s,3t). Then drive forward 1 square(5s,3t). Then turn to its right 45deg(5s,4t). Then drive forward 1 square(6s,4t).
So for the second path, it had a displacement of 6 squares and turned four times and turned 180 total degrees.


You win My bad >_< Sorry to have doubted you Paul

[benji]

you can have a path similar to the one generated by the A-STAR by modding the wavefront a little bit

1- you check for all adjacent squares( all the 8 )
2-when there is an obstacle to the right you dont take the squares ( south-right nor north-right )
 -same goes for all directions

step 1 to let robot move with angle 45
step 2 to not bump into the wall (just like paul's pics)

it seems to work like the A* exactly,, still not sure,,but the problem here is that this would take more computational time

[benji]

sorry guys , it seems it started to fail, i even tried to give a weight of 1.4 to 45 degrees transitions but it still bumps into corners
actually the first step works fine , the problem is in the second step
,,lookslike we still need the A* one

[paulstreats]

I think that there is a difference between the a* and the wavefront systems.

The difference is that the a* seems to be made to accomplish several things in 1 routine Wheras wavefront is there just to literally find a path.

 I would personally go with a wavefront to produce the initial results, and then translate those results into something more realistic.

 Its like modern day computing vs old day computing. In the old days 1 program was built to accomplish everything that was required(a*). These days individual programs are made that work together to produce the result(a basic wavefront would be one of these programs)

[benji]

but the wavefront fails also when you make 45 degrees movement available
(or it works only to find the shortest path only)
you cannot add any other conditions, so in robot navigation it fails because in case of robots you neeed to add other conditions in the algorithm
like making sure that there is enough space for the robot bodyalong the path
(im considering that the robot body occupies more than one square thats because i dont want to treat a small obstacle the same as the robot body).
considering any small obstacle the same size as the robot then the wavefront alone with no added conditions would do
but this would be very basic ....u know,, a big robot would cancel possible paths because of a tiny obstacle ?? thats a lil stupid

[benji]

Admin, do you have the algorithm to make the wavefront capable of making diagonal movements?

i tried but i couldnt get it to work ....

[Admin]

Yes, a wavefront can do 45 deg motions. It will of course be much more computationally expensive, in return for a more optimal robot path. My wavefront code, with minor modifications, can be made to work. Use my simulator code to test your modifications.

What many of you guys are discussing is called cost of motion. There are various algorithms out there that find multiple paths (not just one solution), calculate the cost of motion, then tell the robot to take the path with the lowest cost of motion. Whats great about this is that you can not only account for number of turns, but also terrain - hills, mud, etc.

One day I'll write a tutorial on it . . . but for now, here is some stuff for those who are interested to search and read up on:
accessability, departability, connectivity, and visibility graph maps
cell decomposition map
adjacency graph

Each of those maps will find multiple paths, then your robot can choose the optimal one.

[benji]

with minor modifications

  couldnt get it to work diagonally

[Admin]

A friend of mine, who doesn't do robots but instead game programming, sent me this neat A* demo:

http://www.societyofrobots.com/programming_nav_a_star_demo.shtml

(yeap, robot navigation algorithms are heavily used in video games)

[benji]

nice demo

[benji]

by the way, under what catagory is the A* catagorized?