Advertisement Jump to content


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


tricki path problem

This topic is 6077 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
                                  ---10                                          \                                           \  i
                                        9  |
                                        |  |			                                |  |
   1--------------2                     8  |
  /                \		       /   h
 /  a-----------b   \           6-----7   /
/  /             \   3---4     /         /
  /		  \       \   /  f-----g
		   c---d   \ /  /
		        \   5  /
		     	 \    /
		     	  \  /
[edited by - katanasi on May 30, 2002 5:28:20 PM]

Share this post

Link to post
Share on other sites
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.



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
Original post by Ronin Magus

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...



[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))


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:

mi = ----------

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.



Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!