Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

katanasi

tricki path problem

This topic is 5889 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

simple problem. i've a linelist wich consits of 10 points (1-10) now i wan't to calculate a second path wich follows the linelist on the right in a fixed distance (points a-j) so how do i calculate the a-j points? i know its a dumb ass question but i would be really appreciated for your help thx very much ps. excuse bad english
      			
			
                                   ------j
                                  ---10                                          \                                           \  i
                                        9  |
                                        |  |			                                |  |
   1--------------2                     8  |
  /                \		       /   h
 /  a-----------b   \           6-----7   /
/  /             \   3---4     /         /
  /		  \       \   /  f-----g
		   c---d   \ /  /
		        \   5  /
		     	 \    /
		     	  \  /
     			    e
    
[edited by - katanasi on May 30, 2002 5:28:20 PM]

Share this post


Link to post
Share on other sites
Advertisement
It''s not too hard, but not a dumb-ass question at all.

You''re looking to solve a constraint based problem.

Your constraints are:

Maintain the same gradient as the line segment you are parallel to (this means keeping track of what segment you are parallel to)

Maintain a constant distance from the current line segment AND the next line segment. (This latter constraint is what will cause you to move toward the next line segment. Simply make movement occur until you have satisfied this constraint... and keep satisfying the first constraint while satisfying this one)

When your movement halts (because you are at the point equidistant from the current and next line segments, simply increment the line segments... so the next segment becomes the current segment and the next+1 segment becomes the next segment.

Make sense?

Good luck and please let me know how it turns out.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
thank you for your answers.

but i don't really understand so pseudo code would be really really appreciated. (especially formula for calculating a-j points, how is this done?)

thx very much.

[edited by - katanasi on May 31, 2002 2:50:06 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Ronin Magus
Timkim,

That was an absolutely genius answer. Somewhat similar to how an ellipse is formed?


Thanks Ronin! I'm glad someone else can appreciate the beauty in the solution... I was quite proud of it myself! I guess all those years of mathematics are finally paying off!

katanasi... unfortunately I don't have time today to write code for the above algorithm. I'll try getting to it in a day or so...

Cheers,

Timkin






[edited by - Timkin on June 1, 2002 1:28:24 AM]

Share this post


Link to post
Share on other sites
Try this: Calculate a normal for each line segment. Then generate "vertex normals" - the average of the normals of the two segments that share that vertex. Once you have vertex normals for all your initial verteces, simply add each vertex''s normal to its position to create the new path. I can''t guarantee that this will work, but it sounds reasonable.

Share this post


Link to post
Share on other sites
It''s fairly trivial to generate the points a->j offline, if you have the points 1->10. The only reason I proposed the constraint satisfaction solution was that it seemed really cool... and allowed you to generate your path on the fly!

If you just want the points, then solve the following...

Each wall segment can be represented by two parametric equations:

(for the i th segment)


xi(t) = xi(0) + t(xi(1)-xi(0))
yi(t) = yi(0) + t(yi(1)-yi(0))


where:

xi(0): x value at start of line segment
xi(1): x value at end of line segment

and similarly for the y values.

Furthermore, the i th wall segment has gradient:


y(1)-y(0)
mi = ----------
x(1)-x(0)


Hence, the path segment you want to follow has the same gradient and is a constant distance r from the current line segment.

Assume that the parametric equations of this path segment have the same form as those for the wall (which they do) but are denoted by x''i and y''i. Thus, r is given by


r = sqrt( (xi(t)-x''i(t))2 + (yi(t)-y''i(t))2 )


You also have the equality

mi = m''i

and so the appropriate substituations relate x(0),x(1),y(0) & y(1) with x''(0),x''(1),y''(0) & y''(1).

you can solve this system of equations for the values of x''(0),x''(1),y''(0) & y''(1). You can then do the same for the next segment and THEN solve for the intersection of these two lines semgents!

See why I suggested that constraint based solution?!!!

In writing the psuedo-code for my wall following algorithm I have found a slightly tough nut to crack... it occurs when the gradient of the next line is less than that of the current line (ie, you have to travel a concave path). It''s not to do with the shape of the path, or the time... thats fine... it has to do with the distance to the point of intersection of the two wall segments... its different than if the wall shape is convex. I''ll solve it today or tomorrow hopefully and put up the code soon.

Cheers,

Timkin

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!