6 replies to this topic

[lride]

I got my procedural line generation to work in my game
The lines are made up of 200 straight lines connected.
And I stored the coordinates in a deque so I can pop the first one and generate another coordinate and push it at the back.


How should I approach the collision detection?

[slayemin]

Well, you know the Y coordinates for each line, right? And you know the width of the space ship, right? So, check the top left corner and the top right coordinate against the top line, and check the bottom left corner and bottom right corner against the bottom line. It's probably "good enough" and performance will be pretty fast.

But, if you want more precision at the cost of performance and added algorithmic complexity, you can do line vs. line collision detection. Draw lines around the perimeter of your space ship (looks like you'd only need 3 since it looks like a triangle), then check to see if the lines in the space ship intersect with any of the lines in the terrain.

I can provide C# code to test line vs. line collisions if you'd like... but half the fun is doing the math and finding the solution yourself

[clb]

Since the lines are in 2D and have a cardinal direction in moving from left to right, one direction to take is the binary tree approach, where at each node of the tree, you store a horizontal range [minX, maxX] and the extent how far the border reaches inside that interval. So, for the ceiling line, you'd store the lowest position of the ceiling between [minX, maxX]. Then you subdivide to two child nodes [minX, (minX+maxX)/2] and [(minX+maxX)/2, maxX] and also for those, store the lowest position of the ceiling between those intervals. Keep subdividing until you have only a few lines in the range of the node, at which point you'll do full line-AABB of the ship search.

Another option is to simply subdivide the horizontal screen into, say, 100 buckets with distinct ranges [minX, maxX], and in each bucket store the lines that fall into those buckets. Then when doing a collision check, test the ship only against the buckets which the ship AABB overlaps.

The point of both of these methods is to avoid having to test the ship against each line on the screen.

[slayemin]

Since the lines are in 2D and have a cardinal direction in moving from left to right, one direction to take is the binary tree approach, where at each node of the tree, you store a horizontal range [minX, maxX] and the extent how far the border reaches inside that interval. So, for the ceiling line, you'd store the lowest position of the ceiling between [minX, maxX]. Then you subdivide to two child nodes [minX, (minX+maxX)/2] and [(minX+maxX)/2, maxX] and also for those, store the lowest position of the ceiling between those intervals. Keep subdividing until you have only a few lines in the range of the node, at which point you'll do full line-AABB of the ship search.

Another option is to simply subdivide the horizontal screen into, say, 100 buckets with distinct ranges [minX, maxX], and in each bucket store the lines that fall into those buckets. Then when doing a collision check, test the ship only against the buckets which the ship AABB overlaps.

The point of both of these methods is to avoid having to test the ship against each line on the screen.

Nah, that's too complicated. Just look at the X coordinate of the ship (left and right) and find the X coordinates for the line segment (ideally in O(1) time)) and see if the Y coordinates of the terrain overlap the ship position. The line segments are close enough together that this could work

Example:

//note 1: assuming we're in screen space with an inverted y-axis
//note 2: this is pseudo code to illustrate the idea, not for copy/paste -> working!
float[] TopLine = new float[200];		  //array index is the X value, array value is the Y value
float[] BottomLine = new float[200];	 

if(Ship.Y > TopLine[Ship.X] || Ship.Y < BottomLine[Ship.X])
{
	 return false;
}
return true;

[clb]

Nah, that's too complicated. Just look at the X coordinate of the ship (left and right) and find the X coordinates for the line segment (ideally in O(1) time)) and see if the Y coordinates of the terrain overlap the ship position. The line segments are close enough together that this could work

Saying something is too complicated and replacing it with a broken algorithm is not a particularly good advice.

What you are proposing in the pseudo works only if the level/screen width is equal to 200 pixels, meaning that the i'th line is only one pixel wide so that each line has its unique position. If the lines are wider, you cannot unfortunately do the lookup "ideally in O(1) time" without preprocessing. If OP wants to go this route, it requires either a line rasterization algorithm so that the height values can be tracked for each X coordinates, or if line-AABB test is used, a pre-process filler loop that fills an array that contains the associated line for each horizontal pixel. Sure, it's a feasible method as well, but the complexity is then dependent on the screen pixel width in both time and memory consumption.

[slayemin]

Saying something is too complicated and replacing it with a broken algorithm is not a particularly good advice.

What you are proposing in the pseudo works only if the level/screen width is equal to 200 pixels, meaning that the i'th line is only one pixel wide so that each line has its unique position. If the lines are wider, you cannot unfortunately do the lookup "ideally in O(1) time" without preprocessing. If OP wants to go this route, it requires either a line rasterization algorithm so that the height values can be tracked for each X coordinates, or if line-AABB test is used, a pre-process filler loop that fills an array that contains the associated line for each horizontal pixel. Sure, it's a feasible method as well, but the complexity is then dependent on the screen pixel width in both time and memory consumption.

Eh, even if the lines were 5 pixels apart, you could still fanagle a relatively simple O(1) algorithm (with division and multiplication of 5 on the index and ship x position, ignoring remainders). Then you'd have 1,000 pixels of screen space to work with. Your method would work as well and scale well with more complex levels with lots of stuff going on, but its more complicated and runs in O(log n) time. I'm marginally concerned that it may be a premature optimization which might be unnecessary given the simplicity of the problem.

I wasn't concerned with making my example algorithm actually work (hence note #2). I was just doing general hand waving to illustrate how he could structure his data to have a really simple collision detection check. Naturally, if he goes with it, the actual implementation would be a bit more rigorous ... and fun to implement

Edited by slayemin, 21 October 2012 - 10:50 AM.

[lride]

I forgot to mention that the ship will tilt up or down when going up or down.
I'll try line vs line.
Thanks