Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[sudgy]

I came across this problem when programming, and it's a lot harder than I thought it would be.

So, here's the problem:

Think of a quantized three-dimensional grid, some spaces have nothing in them, while some have obstacles.  Sometimes, a projectile can be thrown that follows the equations of kinematics, with gravity pulling it down in one direction.  The path that the projectile follows is continuous (well, as precise as the computer can be, anyway).  However, if the closest quantized spot to the projectile's (continuous) position at any point is an obstacle, the projectile must stop moving (imagine the projectile as just moving between quantized spots, whichever one is closest to the continuous position).

I hope I worded that well enough.  I'm still implementing my solution, but I was wondering if anybody else wanted to give it a shot.  I'll probably post my solution when I finish it.

[Davio]

Is there anything particularly hard about this?

Seems like it's pretty straightforward.

[Titandrake]

I think we need more details to judge the difficulty. By my understanding:

- You have objects that follow simple physics. Every object has a position, velocity, and acceleration, all of which are floating points.
- However, the position displayed to the end user is part of a discretized grid. So for example, divide the coordinate plane into 1 x 1 x 1 cubes, and an object whose position falls inside that box takes up the entire box.
- At every timestep, you recompute the (floating point) position, velocity, and acceleration, then turn it into the discrete location in the grid, then check for collision detection.

This sounds like it will have tons of edge cases. If you compute the state in the next frame ignoring collisions, you'll have to manually move objects back. If projectiles can collide with each other, you'll have to handle collision detection with moving objects which sounds awful. (Say 2 projectiles are in adjacent boxes, moving towards each other at 1 box per frame. If you do things naively, the two will go through each other because they'll never both occupy the same box at the same time. So then you'll either have to accept that or do some interpolation between the two to make things act according to intuition.)

Basically this seems like one of those things that is mildly interesting to think about and a huge pain to actually make.

[Davio]

That's how I understood it as well, Titandrake.

You can just round the x, y and z of the projectile to find out which space it's in and as soon as it's in a space filled with an obstacle, stop it.

[sudgy]

The problem is that if a projectile is moving too fast, when using timesteps, it might move through an obstacle.  You need to make sure that can't happen.

I forgot to mention, you don't need to worry about projectiles hitting each other.

[Accatitippi]

Maybe draw a line between the position at time 0 and position at time 1 and check collisions between it and the blocks?

[sudgy]

Maybe draw a line between the position at time 0 and position at time 1 and check collisions between it and the blocks?

That's not quite perfect, the path this is traveling is a parabola, not a line.

[DG]

Can't you draw planes along the cube edges and find where the projectile crosses each plane? From there you can surely deduce which cube is crossed when each plane is crossed.

[sudgy]

Can't you draw planes along the cube edges and find where the projectile crosses each plane? From there you can surely deduce which cube is crossed when each plane is crossed.

That's similar to what I'm doing, but without all of the mental imagery.

[werothegreat]

I actually had to do something similar for a homework problem last semester, but most of the code had already been written - poorly.  My task was to poke through it and try to fix it up.  Key word: "try".

[Davio]

The problem is that if a projectile is moving too fast, when using timesteps, it might move through an obstacle.  You need to make sure that can't happen.

I forgot to mention, you don't need to worry about projectiles hitting each other.

Well, just do some backtracking at every timestep. You know the path it has traveled to come to that point, so you can check back whether there was an obstacle on the path.