Hello all,

I have this concept that I am currently working on that creates a procedurally generated tunnel. This is done simply by starting with a start point and generating random points being offset by a variable distance over iteration. The results produce a tunnel of set length (rather long) looking something like this small portion.

(apparently I can't put the photo here - please follow link to see if you would like to see a screen shot of the tunnel to better help you understand)

Each of these lines is drawn based on the new point added through the random generation.and the lines are drawn via the Allegro5 library. The issue I'm having is collision based on these random lines and a players avatar - currently a square. What I had mapped out was testing collision based on a set of points on the avatar. So I get these 8 points.

1. (square.x, square.y) - Top Left Corner

2. (square.x + square.width / 2, square.y) Top Middle

3. (square.x + square.width, square.y ) Top Right Corner

4. (square.x, square.y + square.height /2) Left Middle

5. (square.x + square.width, square.y + square.height /2) Right Middle

6. (square.x, square.y + square.height) Bottom Left Corner

7. (square.x + square.width / 2, square.y + square.height) Bottom Middle

8. (square.x + square.width, square.y + square.height) Bottom Right Corner

as my test points for collision. To test the collision that requires finding out if any of these points lie on each of the lines. Since the lines are generated randomly at the it seems like it would be wrong to test each frame for all lines and these points. So I started with a simple test to see if checking collision is even needed this update. This was done via this code.

for (int i = 0; i < NUM_POINTS; i++)
{
	if(points[i + 1].y < points[i].y)
	{
		//preliminary check for collision, is ship within checking range?
		if( (ship.pos.x > points[i].x) &&
		    (ship.pos.x < points[i + 1].x) &&
		    (ship.pos.y > points[i + 1].y) &&
       		    (ship.pos.y < points[i].y))

NUM_POINTS is the array that holds all randomly generated points. Lets say it currently stores 1000 points. This brings us to 999 lines in the level. There is also a BOT_NUM_POINTS set exactly the same way to make up the bottom of the tunnel. The initial check of:

if(points[i + 1].y < points[i]. y) 

is testing to see if the lines first point would be higher on the screen then the second. This determines if the line is sloped left or right. The next check of:

if( (ship.pos.x > points[i].x) &&
    (ship.pos.x < points[i + 1].x) &&
    (ship.pos.y > points[i + 1].y) &&
    (ship.pos.y < points[i].y))

is the preliminary check to see if collision is worth looking into. These works by checking to see if the ships upper left corner is within the x's of the line and if so if its between the height of the two as well. If this succeeds it continues on to perform collision checking for the line in question.

float slope = GetLineSlope(points[i], points[i + 1]);
				float intercept = GetYIntercept(points[i], slope);
				//if( IsOnLine(ship.pos.x, ship.pos.y, slope, intercept) )
				if(IsOnLine(ship.pos.x, ship.pos.y, points[i], points[i + 1]))
				{
					//Collide
					al_draw_textf(font, al_map_rgb(255,0,0), 100, 10, 0, "Line points (%5d, %5d)", points[i].x, points[i].y);
					al_draw_textf(font, al_map_rgb(255,0,0), 100, 35, 0, "Line points (%5d, %5d)", points[i + 1].x, points[i + 1].y);
					al_draw_textf(font, al_map_rgb(255,0,0), WIDTH / 2, HEIGHT / 2, 0, "COLLISION AT %5d, %5d", ship.pos.x, ship.pos.y);
					return true;
				}
				//else if ( IsOnLine((ship.pos.x + ship.boundx) / 2, ship.pos.y, slope, intercept) )
				else if( IsOnLine( (ship.pos.x + ship.boundx) / 2, ship.pos.y, points[i], points[i + 1]) )
				{
					//Collide
					al_draw_textf(font, al_map_rgb(255,0,0), 100, 10, 0, "Line points (%5d, %5d)", points[i].x, points[i].y);
					al_draw_textf(font, al_map_rgb(255,0,0), 100, 35, 0, "Line points (%5d, %5d)", points[i + 1].x, points[i + 1].y);
					al_draw_textf(font, al_map_rgb(255,0,0), WIDTH / 2, HEIGHT / 2, 0, "COLLISION AT %5d, %5d", ship.pos.x + ship.boundx, ship.pos.y);
					return true;
				}
				//else if ( IsOnLine(ship.pos.x + ship.boundx, ship.pos.y, slope, intercept) )
				else if( IsOnLine(ship.pos.x + ship.boundx, ship.pos.y, points[i], points[i + 1]) )
				{
					//Collide
					al_draw_textf(font, al_map_rgb(255,0,0), 100, 10, 0, "Line points (%5d, %5d)", points[i].x, points[i].y);
					al_draw_textf(font, al_map_rgb(255,0,0), 100, 35, 0, "Line points (%5d, %5d)", points[i + 1].x, points[i + 1].y);
					al_draw_textf(font, al_map_rgb(255,0,0), WIDTH / 2, HEIGHT / 2, 0, "COLLISION AT %5d, %5d", (ship.pos.x + ship.boundx) / 2, ship.pos.y);
					return true;
				}
			}
		}
		else if(points[i + 1].y > points[i].y)
		{
			//preliminary check for collision. Is ship within checking range?
			if( (ship.pos.x > points[i].x) &&
				(ship.pos.x < points[i + 1].x) &&
				(ship.pos.y < points[i + 1].y) &&
				(ship.pos.y > points[i].y))
			{
				//TODO: need to place another if statement here checking the slope of the line and if the point lies on the line. 
				//collide
				al_draw_textf(font, al_map_rgb(255,0,0), 100, 10, 0, "Line points (%5d, %5d)", points[i].x, points[i].y);
				al_draw_textf(font, al_map_rgb(255,0,0), 100, 35, 0, "Line points (%5d, %5d)", points[i + 1].x, points[i + 1].y);
				return true;
			}
		}
	}
	return false;
}

As you can see the first thing I try to do is to figure out the slope of the current line. This is done by checking (y2- y1) / (x2-x1). The slope is then used in the lines formula and the points of the avatar are inserted into the formula to see if they lay on the line. The code to check to see if point is on the line is as follows.

bool IsOnLine(int boxX, int boxY, Point p1, Point p2)
{
   Point temp;
   temp.x = boxX;
   temp.y = boxY;
   return ( (p1.y - temp.y) == GetLineSlope(p1, p2) * (p1.x - temp.x) );
}

where as GetLineSlope is:

float GetLineSlope(Point p1, Point p2)
{	
    return ( (p2.y - p1.y) / (p2.x - p1.x) );
}

The issue I'm having is that it hardly recognizes collision. It does recognize it from time to time but a majority of the time the debug display that should be printed doesn't indicating a collision is not taking place. I also realize that the above code doesn't test all of the test points discussed earlier. I figured if I could get it working right for an easy point like its Top Left corner (x,y) then I could theoretically get it working correctly for the rest of the points.

My question is this. Am I over-thinking this or under-thinking it for that matter. Is there a better way to go about doing this? If not, does anyone recognize why this may not be working as intended. I understand that sounds like someone please do work for me, but I don't expect that from anyone. I am merely wondering if anyone has tried linear collision before and what method was taken to get it to work. Thank you in advance for your time and any assistance you may provide.

The immediate problem is in line 114: The probability that two independently computed float variables are exactly the same is low. You must not check whether the point of interest is on the edge, but instead check whether the point of interest is on this side (okay) or on the other side (collision) of the edge.

One approach to the said check is to determine the candidate line segment (perhaps so as you did; I haven't investigated that in detail), to compute its normal (keyword: perpDot), and then compute the distance of the pint of interest from the line segment along the normal. Whether the point is on this or the other side is defined by the sign of the distance.

Thanks for the response Haegarr.

I follow that having two separate float values equaling the same is a low probability, but doesn't it at some point (despite how brief) have to equal a point on the line, say just before it crosses over the line. Does this mean that the update loop itself is too slow to catch the point as is?

I've taken a look at your proposal of using the perpendicular dot product of the line segment, but fear I don't fully comprehend it in this situation. To walk myself through it I'd like to mock up a scenario really quick.

Lets say that a line consisting of these two points A (108, 157) and B (144, 132) exists and that we are trying to find if another point collides with said line. If I'm understanding this correctly, I would want to create a perpendicular vector from this initial line to the point of interest, calculate the magnitude of this vector, if positive its on side A and if negative its on side B - resulting in collision. Is this correct? If this is not correct (albeit - perhaps even far off) would / could you provide me with a trivial example to demonstrate how the perpDot would be used correctly in this situation?

I must admit that I've been trying to re-teach myself math as it's been over a decade since my last formal math class. Its tough to re-learn after so long, hard to find a good book or resource that walks one through it much like they did in High School / College.

Once again, thank you so much for taking time to look into this. I greatly appreciate it.

Regards

Thanks for the response Trienco.

I see what your saying using the floats. It makes sense now as to why it's not working given your example. Given what you have said and what Haegarr said before you, would you suggest finding the perpendicular off of the wall line to the point of interest. Then use the two line equations to find the point of intersection on the first line. Then use that point of intersection along with the initial point of interest to calculate distance between the two. Finally testing this distance to be within a range of say 0 and 1?

Does that make sense?

I also just realized that the link containing the photo image of this scenario isn't able to be used in this thread for some reason. Is it easy enough to understand the action I'm looking for without the visual? If not, I can try and figure out another way to get the image posted on here.

Thanks again.

Lets say that a line consisting of these two points A (108, 157) and B (144, 132) exists and that we are trying to find if another point collides with said line. If I'm understanding this correctly, I would want to create a perpendicular vector from this initial line to the point of interest, calculate the magnitude of this vector, if positive its on side A and if negative its on side B - resulting in collision. Is this correct? If this is not correct (albeit - perhaps even far off) would / could you provide me with a trivial example to demonstrate how the perpDot would be used correctly in this situation?

You got it.

The edges are given in order left to right, and their respective endpoints are also ordered this way. This allows you to determine line segments and write them down as limited ray:

sn( t ) := pn + t * dn , 0 <= t <= 1

dn := pn+1 - pn

where pn denotes your points[n] array element at index n. Notice that using t==0 gives the start point, t==1 gives the end point, and 0<t<1 gives any point in-between.

Now let us use the perpDot to compute a perpendicular vector to d. There are 2 possibilities, and it makes a big difference whether we use the one or the other. We use the ceiling of our room and define that the "positive" side should be below the ceiling. Hence we want the perpendicular vector point more-or-less downwards. So we pick

vn := [ dny, -dnx ]

as the perpendicular vector.

With this we could formulate an equation with which we want to reach the point of interest c (i.e. the one to check for collision):

pn + t * dn + u * vn = c

So the steps to determine on which side the point of interest is w.r.t. to an edge are:

1.) get the 2 points from the array

2.) compute their difference vector d (take care or order)

3.) compute the perpendicular vector v

4.) compute the difference from the edge's start to the point of interest

5.) commute the distance u

6.) assess the distance with 0 as border

Notice that the floor is different, because you want to assess the point of interest to be above it (for the ceiling it was below). You can do so by either use the other perpDot result or else say that an u below 0 means no collision and greater or equal to zero means collision.

(BTW: I've written this down from the top of my head, so please check it thoroughly.)

I also just realized that the link containing the photo image of this scenario isn't able to be used in this thread for some reason. Is it easy enough to understand the action I'm looking for without the visual?

I personally had not imagined your problem correctly before I had a look at the picture. I've investigated the HTML source and found the link by searching the word "apparently". For sure that is not convenient ;)

If you want to put a link in a post then write down the link text, mark it, press the chain symbol in the editor's toolbar, and paste the URL into the opening requester. That should do the trick.

This is the original link.

Thanks for the continued information Haegarr.

I've had some internet problems with a snow storm over the weekend so I haven't been able to get on to respond. I've made some progress but I don't believe that I've done it correctly. I am having a little difficulty trying to determine what your variables in the formulas stand for.

I get the Pn is the a point for the line. I assume that dn is the distance between the two points. At this point, I kind of get lost. What is Dx and Dy? Are these the individual distances from x and y? Is Vn just a new point of (Distance of y, -Distance of x) for the start of the perpendicular to the point of interest? From here you have the equation pn + t * dn + u * vn = c.

Again I understand Pn to be one of the original points (does it matter which?) t I'm not sure about. dnI once again assume is distance calculated from point 1 to point 2 of initial line. U I'm not sure about. Same with Vn. All of this adds (add multiplies) to the point of interest c?

I apologize for sounding completely ignorant in this matter, and I thank you for the time you have already taken on this. Could you please explain the variables a little better.

Also here is a new screenshot of what I've accomplished thus far using this forum thread.

The blue lines are simply drawn from points 1 and 2 of line to point of interest. The yellow line was my initial attempt (ended up being parallel in regards to square's placement against line) and the red line is calculated as half the x and half the y difference between the two points, then drawn to the point of interest.

New Picture

Thanks again for your help thus far.

I get the Pn is the a point for the line.

Yep. For simplicity it is not just a point on the edge but a point that denotes a corner of the ceiling / floor.

I assume that dn is the distance between the two points.

Not exactly. A distance is a scalar value (i.e. single number). But dn is a vector value (i.e. several grouped numbers, one for each dimension) and denotes the difference of 2 points. The length of the difference vector can be used as distance between the points.

What is Dx and Dy? Are these the individual distances from x and y?

dnx is the first (x) component of the difference vector dn, dny is the second (y) component of the difference vector dn, so that written as vector

dn == [ dnx , dny ]

Is Vn just a new point of (Distance of y, -Distance of x) for the start of the perpendicular to the point of interest?

You must distinguish between vectors that denote a position, a difference, or a direction! vn is a difference vector like dn is; as such is has no beginning and no end, just a direction and a particular length (opposed to direction vectors that have a direction but their length is enforced to be 1). Hence vn as itself cannot point to a position. You need to add it to a position vector to yield in a position, like it happens in ...

From here you have the equation pn + t * dn + u * vn = c.

… this formula: Here pn is giving us a position because it is a position vector, t * dn is a difference vector scaled by t (i.e. its length is t times the length of dn), u * vn is a difference vector scaled by u, and all parts are added, so c gives us another position. In words: Starting with position p, go in direction of d for an arbitrary multiple of its length, and then go in direction of v for an arbitrary multiple of its length, and name the reached position c. Notice that because d and v are perpendicular, c can be any point in the plane (its just a question what values are chosen for t and u).

Again I understand Pn to be one of the original points (does it matter which?)

Yes, p is consequently used for the corner points of the ceiling / floor. It matter not exactly which of the corners it is, but the use of the subscript n and n+1 shows that although pn is any of the corner points, pn+1 is definitely the next one right to pn (as defined by our chosen convention).

t I'm not sure about. dnI once again assume is distance calculated from point 1 to point 2 of initial line. U I'm not sure about. Same with Vn. All of this adds (add multiplies) to the point of interest c?

The formula is explained above. Its sense is to say that we want c to be equal to the point of interest, i.e. the position for which collision has to be checked. If you then look at the formula, there are just 2 unknowns, namely t and u; all other values are already given. Further, since we are in 2D space here, the formula is in fact two equations, one for each dimension. Therefore we are able to compute the variables t and u so that c is equal to the point of interest. However, we actually don't do so, because we just need a part of those informations; all we need to know is whether u is positive or negative.

We do so by expressing the point of interest as "from position p we follow the difference vector from p to the point of interest" to yield in the said point of interest. This is obviously possible. We then check whether this new difference vector is roughly in the same or in the opposite direction as vn, done so: The dot-product maps the new difference vector onto vn and tells us which fraction is common to both vectors. This fraction is positive if the both vectors point more or less in the same direction, it is zero if the both vectors are perpendicular, and it is negative if the both directions are more or less opposites.

Hi Haegarr, thanks for the continued input. I feel like I'm really close to getting this, but there is part of it that eludes me visually. To better explain where I am getting lost, I'd like to provide an example and work the steps out here for it. As you know I am not necessarily trying to draw a perpendicular line, rather instead use the math behind the perpendicular line to decide whether or not my square has collided with a line.

I have an array of points P[0] through P[4000]. Each of these points in the array are end points for a line. They are all spaced 36 units away from each other along the X axis.

lets say P[42] = (105, 50) and P[43] = (141, 82)

The distance vector is represented by Dn = (Dx , Dy) where as in this example Dx = (141 - 105) = 36 and Dy = (82 - 50) = 32;

Thus Dn = (36, 32)

From DnI can gather that the magnitude (length) of the line L = (P[42], P[43]) is equal to sqrt(36^2 + 32^2) = 48.17

If I'm understanding everything correctly so far then Vn = either (-32, 36) or (32, -36) depending on the direction I want my perpendicular vector to go. One is good for my ceiling and the other is good for my floor.

In this example, I'm worried about the ceiling so I'll choose Vn = (32, -36).

This is where my mind loses its grasp.

I believe I normalize this new vector Vn by (32 / -36) / sqrt(32^2 + (-36)^2) giving me -.019.

If I plot similarly scaled coords on graph paper, I can see that my perpendicular line is correct based on the point Dn but it is way off based on the coords of P[42] and P[43].

I am not grasping how to determine the "start" point of this perpendicular line. By this I mean the perpendicular line will run infinitely parallel to itself across the line P[42], P[43] (for all the points on the line segment), How does this apply to getting the relative point on the original line?

Once I grasp this step (above), I think that all I have to do is generate the distance between the point of interest (my square) and the line, and as long as its above 0 I'll be below the line.

I apologize if this is convoluted but this is the best way I could pose a question to you to further understand it. As always thanks for your time.

Regards

You got all above this line

… This is where my mind loses its grasp.

correct! Fine

The next of your steps is:

I believe I normalize this new vector Vn by (32 / -36) / sqrt(32^2 + (-36)^2) giving me -.019.

You can do that, but it is not necessary to just detect collision. Before normalization we have a direction and a length of 48.17, and after the normalization we have qualitatively the same direction but a length of 1. We need to know whether another vector points roughly in the same direction as vn, but the real length of said other vector is of no interest for us. So you can get rid of the relatively costly sqrt function call.

If I plot similarly scaled coords on graph paper, I can see that my perpendicular line is correct based on the point Dn but it is way off based on the coords of P[42] and P[43].

I am not grasping how to determine the "start" point of this perpendicular line. By this I mean the perpendicular line will run infinitely parallel to itself across the line P[42], P[43] (for all the points on the line segment), How does this apply to getting the relative point on the original line?

One of the pitfalls when dealing with vectors is that (if you don't use homogeneous co-ordinates, as we do here) you have to strictly distinguish between vectors that denote a position / point or else a difference / direction. The latter one do not have a concept of position! Is is like a delta between 2 points (hence the "difference"). Another example: If you say that you have needed 2 hours to fulfill a task, it does not give any hint at which daytime you've done it. The difference (2 hours) is a duration and has no start and no end, and so is it with difference vectors, too. Now, if you say you have needed 2 hours and have began at 0900 this morning, then there is a point in time (0900 AM) and a duration (2 hours), and from this the end point 0900 + 0200 = 1100 can be computed as the end point of the task. The same can be seen in the formulas for sn(t) and c in one of my posts above.

However, in the said formulas there are also scalar variables like t and u. They are multiplied by the difference vectors, what means that the direction is the same but the length is changed (notice that vector normalization is also just a scaling but with a value know to force the length to become 1). Hence plotting on paper is, strictly speaking, not possible at all.

But human like to visualize ;) So: With a specific location on paper used as origin (a point, obviously), and 2 perpendicular directions, you get a co-ordinate system on paper. Relative to this co-ordinate system you can plot the points pn = P[42] and pn+1= P[43] on the paper. If you draw an line exactly between these 2 points, you have plotted sn(t) for all t in-between 0 and 1, or in other words all of the infinite many points that sn(t) takes under the given condition on t. Of course, you can choose t lower than 0 or greater than 1; doing so makes the line longer in the respective direction.

With this introductory words in mind, draw a corner (obviously a point) of the bbox you want to check for collision near to the line P[42] / P[43]. This point is what we've named c. Now take your ruler and plot a line that passes through c and is perpendicular to the (perhaps elongated) line. This newly drawn line is what we've named u*vn. It crosses the original edge at sn(t) for some specific t. You can determine t if you measure the distance on paper from P[42] to the crossing point, and the distance from P[42] to P[43], and divide the former distance by the latter one. When you do so bear in mind that points on the edge but in front of P[42] must get a "negative distance", or else they could not be distinguished from the point with the same distance but behind P[42]. (A distance itself cannot be negative, but remember that we actually use a distance and a direction, namely along or against the line P[42] to P[43].)

Similarly: c is defined as sn(t) with the above t, plus u*vn. Analogously to above, you can determine u by measuring the distance from the crossing point to c, and the distance from P[42] to P[43] (oh, why that? Because the length of vn is the same as the length of dn), and dividing the former distance by the latter one. Again, bear in mind to use negative distance for points before the crossing point, and a positive distance for points behind it. Remember that in the end the sign of u is what we're looking for!