On Sunday, March 31, 1996 at 1:30:00 PM UTC+5:30, Avi Pilosof wrote:
I'm studying AI, and we just got our final assignment.
One of the problems within it is to navigate a robot such that it
picks up objects and arranges them in a given pattern, avoiding
obstacles in its way. The destination point is known in advance.
This problem is not a gaming problem for me, but it certainly
seems to belong in this group, since I can easily see it applying
in a game situation.
I have alot of time before this is due, and I want to get it working
using a good method.
Meanwhile, we have had two methods hinted at (to avoid obstacles):
a) Brute force: If you hit a wall, turn a little, and keep
going. This will eventually work, but is less than
inspiring.
b) Find a good path, THEN follow it.
I don't want to use (a) unless I really have to, since it's very
el-cheapo.
I would much rather find a good way to do (b), but I'm not sure how
to go about it.
I have briefly considered 2 methods:
i) Ray casting - backwards. I'm not sure exactly how I
would do this, but I was thinking to start from the
destination, and try casting towards the robot. Upon
failure, try to offset the angle of casting a little,
until you've gone full circle (increment both +ive
and -ive with each cycle). This gives me the first
ray, but I then have to cast more rays (recursively)
until the robot is hit. But once the initial ray finds
a "way out" around the obstacles, where does the next
ray begin, etc?
ii)Graph algorithms. I was thinking to define a graph
of randomly (??) distributed vertices around the
destination, and where there is no obstacle from one
vertex to another, an edge exists. This would lend
itself to a shortest-route algo. I'm VERY vague about
this method, since it doesn't seem very concrete.
Anyway, my request is for hints and pointers and algorithm
names.
I'm **NOT** asking for a solution, I would just like some direction,
and perhaps a reference. Are my ideas worthwhile? Are they junk? etc...
I would really appreciate any response (especially via e-mail).
TIA.
###################################################################
Avi Pilosof - [email protected]
- http://www.cse.unsw.edu.au/~avip/
You cannot propel yourself forward by patting yourself on the back.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)