A Vector Math solution to Pathfinding in a free coordinate system
Author
Here''s something I''ve been formulating for a few days. I can''t quite seem to get it to work very well, maybe there''s a shorter way:
www.gryfter.net/~wickedewok/pathfinding.jpg
80 percent of the time, it does avoid walls..but sometimes it chokes, especially when it A(see diagram) is inside circle C.
I really don''t know any other algorithms that works for a free coordinate system. If anyone is willing to offer me suggestions, please email me at marvg007@aol.com. Thanks!
ps. the method should be efficient enough since objects in the game are quad tree sorted..that way you only compare paths with objects immediately surrounding it.
-=~''''^''''~=-.,_Wicked_,.-=~''''^''''~=-
I tried to do something like this before didn''t do well at it my suggestion would be to simply not use a circle as the obstruction use a shape that fits the object better like a rectangle that way its much less likely that you inside the area. I found getting around a few objects pretty easy the problem comes in when two or more objects have no space between them.
Author
well the algorithm works now after I tweaked it a bit. Needed a test to see if |CA| > R . Wonder if there''s anything that calculates faster.
Author
yea it probably is faster than a Vector Length call, but when I said ''faster'', I was refering to the general algorithm of pathfinding in free space. But thanks anyway;p
Is AB the heading of the object?
Why not test to see if the objects heading is within or without the cone defined by AE and AE'' (E'' on opposite side of circle from E)?
Timkin
Why not test to see if the objects heading is within or without the cone defined by AE and AE'' (E'' on opposite side of circle from E)?
Timkin
Author
Timkin, most of the algorithm is just there to find E, and once we''ve found it, we use it construct AE. Once is found(step 7), we just do two more steps to decide whether or not the object is in the yellow zone. A Normalize and a Dot product. I''m not sure how, once you get AE, you can find out if the object''s heading is between AE and AE* with less than two steps. The main cycle eater is in finding E in the first place. Is there another way to check if AE > AB > AE*? I probably have to find the angles they create..and that would take an atan() call..which is expensive?
You could certainly be correct that your method is the fastest to compute. I have this intuition floating around in my head that it would be better to work with the point E being the tangent line from A to the circle... but I haven''t justified it to myself yet, so I won''t post my thoughts here until I do.
Cheers,
Timkin
Cheers,
Timkin
If you project the object's position into the agents local coordinate system the calculation is made simple. If your agent has radius rA, and your object to be avoided has radius rO and is at position C:
First, project C into the agent's local co-ordinates.
If the object's local x coordinate is negative then it is either behind the agent or the agent is inside the object (which shouldn't occur [and if it should occur is very easy to test for]).
If the object's x is positive then it must be infront of the agent so we now have to test to see if it lays in the path of the agent(again assuming the agent is not inside the object). This is very simple and quick. Expand rO by half rA If this interects the x axis then you have a potential collision. Use your favourite line segment - circle intersection test to find the points.
ai-junkie.com
[edited by - fup on January 26, 2003 3:40:16 PM]
First, project C into the agent's local co-ordinates.
If the object's local x coordinate is negative then it is either behind the agent or the agent is inside the object (which shouldn't occur [and if it should occur is very easy to test for]).
If the object's x is positive then it must be infront of the agent so we now have to test to see if it lays in the path of the agent(again assuming the agent is not inside the object). This is very simple and quick. Expand rO by half rA If this interects the x axis then you have a potential collision. Use your favourite line segment - circle intersection test to find the points.
ai-junkie.com
[edited by - fup on January 26, 2003 3:40:16 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
