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.