LoginLogin
Nintendo shutting down 3DS + Wii U online services, see our post

Help with terrain collision?

Root / Programming Questions / [.]

Gaelstrom_ValenceCreated:
So, in the current version of my program, I noticed the terrain collision doesn't handle diagonal movement well. At the moment, I have individual checks for each direction, done one after the other. But to fix the above issue I'm making a more dynamic system that does the necessary checks at the same time. Since before, say, since checks for tiles to right of the player came first, if they were also moving upwards, the player might 'hit' what should logically be a roof, but it would count as a wall collision since that check comes first, taking away their momentum, even if the upward checks which come later sets the player below the roof. But now I can't figure out how to have the game check only the tiles on the player's path(Ones the lines intersect), at the moment, it checks every tile in a rectangular field from the player's previous position, and to where their velocity would take them. Any advice?

It sounds like you want to draw a straight line... except instead of plotting pixels on the screen, you want to check if pixels(/tiles) are open air, or are solid. Pick any algorithm for drawing a straight line - like Bresenham's algorithm. Replace the code 'plot a pixel' with 'check the tile'. Note that this algorithm includes 45-degree 'jumps' from one pixel to the next in the line, so the corners of your walls need to be closed. Your application will need some more clever application of the algorithm, though, to follow the direction of the line after a bounce.

It sounds like you want to draw a straight line... except instead of plotting pixels on the screen, you want to check if pixels(/tiles) are open air, or are solid. Pick any algorithm for drawing a straight line - like Bresenham's algorithm. Replace the code 'plot a pixel' with 'check the tile'. Note that this algorithm includes 45-degree 'jumps' from one pixel to the next in the line, so the corners of your walls need to be closed. Your application will need some more clever application of the algorithm, though, to follow the direction of the line after a bounce.
I tried out a line algorithm, one that i could comprehend. But is there one that goes over every tile/pixel the line crosses with, instead of just the closest one to the line?

If you're using Bresenham's algorithm, you know there's an 'error term' you update for every pixel by adding a 'delta' value. When the error term exceeds 1, you subtract 1, and take a diagonal step rather than a step in the direction of the primary axis. So you want to do steps in cardinal directions rather than diagonals. Where the algorithm says take a diagonal step, and the new error term is less than half of delta, take a step along the primary axis then a step in the other direction. Where the algorithm says take a diagonal step, and the new error term is more than half of delta, take the steps in the opposite order. If it is precisely half of delta, the line goes precisely through the corner, and you really take a step diagonally.

If you're using Bresenham's algorithm, you know there's an 'error term' you update for every pixel by adding a 'delta' value. When the error term exceeds 1, you subtract 1, and take a diagonal step rather than a step in the direction of the primary axis. So you want to do steps in cardinal directions rather than diagonals. Where the algorithm says take a diagonal step, and the new error term is less than half of delta, take a step along the primary axis then a step in the other direction. Where the algorithm says take a diagonal step, and the new error term is more than half of delta, take the steps in the opposite order. If it is precisely half of delta, the line goes precisely through the corner, and you really take a step diagonally.
Huzzah! I got it to work, thank ye sir! https://miiverse.nintendo.net/posts/AYMHAAADAAADV44H3TT53Q

I have hopefully, one last issue. Say you have an object bigger than one tile? I could just have x and y for loops go through the height and width of the object, but then it would redundantly check already checked tiles with each step?

If the origin of the object is at (x0, y0), then for each point in the line (x,y), check whether (x-x0, y-y0), relative to the object's origin, is in the object. If the object is a rectangle, this means checking whether (x-x0) is between 0 and width, and (y-y0) is between 0 and height.

If the origin of the object is at (x0, y0), then for each point in the line (x,y), check whether (x-x0, y-y0), relative to the object's origin, is in the object. If the object is a rectangle, this means checking whether (x-x0) is between 0 and width, and (y-y0) is between 0 and height.
Does that account for movement or just the object's initial position?

Ah, I misunderstood your question: I thought you were asking about the line meeting an object bigger than one tile. Now, I think you're asking about an object bigger than one tile moving along the line, so I'll try and answer that question. So, you've broken down the movement of a point along the line into steps: moving one pixel left, or moving one pixel right, or moving one pixel up, or moving one pixel down, or, when the math is just right, moving one pixel diagonally. Now, if the idea is to change "move a point, one pixel to the left" to "move a larger object, one pixel to the left", then, you have to check all the pixels on a left edge of the object, in the new position. You don't have to check any interior pixels, because they will be moving from the pixel they were occupying to... another pixel that was just occupied by another part of the same object, because it was an interior pixel, so there can't be a new collision. You don't have to check any pixels on the top or bottom edges (except the top-left corners and bottom-left corners). You don't have to check any pixels on the right edge (unless the object is one pixel thin at that place, and the same pixel is on the left edge too). So, replace "Check whether the new position of the point, after moving left one step, hits a wall" with "Check whether any of the new positions of the pixels on the left edge(s), after moving left one step, hit a wall". For the diagonal step, you'll have to check two edges. (EDIT: Actually, for diagonal steps, it's probably more proper to break down the diagonal step into two steps: one horizontal and one vertical, and check the one appropriate edge for each step.) Eliminating the checks for pixels that are not on the 'leading edge' of the movement of the object will save lots of time, for bigger objects. But - it would be easier to loop over all the pixels in the object, and in small objects, the simple way may not be so much slower that it's worth the effort to pick out which pixels are on the leading edge for each step.