I'm sort of feeling my way around C# and DirectX still, so as (what I thought would be) a small learning project I decided to make a clone of a game called Kuru Kuru Kururin. It's a sort of obscure GBA game in which the player pilots a helicopter, represented by a rotating stick, through an obstacle course and tries to avoid hitting anything. I've taken a screen from my game (and drawn on it a bit) to try to illustrate this concept: (Don't worry, the graphics will get better once I find an artist to replace my crap stand-in textures :p) That image is slightly misleading - all the walls are on 45 degree angles, and no more than two meet at one point. In reality, there's no limits on the angles walls can be at or the number that can meet at one point. So, the collision detection has proven extremely difficult. I really wanted to figure this problem out myself, but I've tried many times over the past few months and just can't get it, and it's making me a little insane. What has to happen is that, one, it must be impossible for the helicopter to get through a wall, and two, when it hits a wall it has to bounce back from it a little. Has anyone had to do anything like this before? What worked for you? I'll post some things I've tried, and why they haven't worked: 1. Reactive - each frame, move the helicopter, and see if it intersects any walls. If it does, apply a counter-force so strong that it will definitely be knocked all the way back. The problem: the force would often knock the helicopter through another wall, which would just make things worse. 2. Predictive - each frame, determine where the helicopter will be, and where all the walls will be relative to the helicopter. Get segments from the endpoints of the helicopter to their future positions, and test them for collisions with the walls. Then do the same for the wall endpoints against the helicopter. If there is a collision, don't move, and apply a force away from the wall. The problem: If the force knocks it into another wall, it will stick, because it will never be able to move. I've done a ton of variations on these, but these have been the main models I used for the collision detection. Anyone have any other ideas how I could go about it?

Actually, I think your stand-in graphics are kindof cool! Nicer than many programmer graphics I've seen, and kind of a nice, stylized look that works well on handhelds!

That said...it sounds like you're concerned with collision response and not collision detection. That is, you are already able to detect when and where the collision occur, but you wish to have the helicopter respond in a way such that it does not hit the opposite wall, etc.? Am I correct in my assessment?

I realize that you have some limitations in what you can do just because of the platform's low computing power. May require too much math to do rotational impulse-momentum collision response or penalty functions with an implicit solver.

Have you considered using "potential fields" approach, such as the techniques used for path navigation described in the link below? The idea, though I haven't fleshed it, is that each wall would be an anti-force field that pushes the helicopter away (pushes the front and back of the helicopter away from the wall in the perpendicular direction). The amount of force is a function of how close the end of the helicopter is to the wall. You can get into some trouble. The usual naive explicit Euler integration won't really work for you due to stability issues. Verlet integration might work okay. You'd also have to have some spatial partitioning smarts, applying forces only from the few walls that are close to the helicopter. You'd also want to precompute the normal direction of the walls, so extra data. There might be a way to use this in a useful way....

Motion Planning using Potential Fields

From your explanation, the player does not have to avoid hitting wall, the stick will just react to the wall like one would expect. If it was just a matter of detecting if a stick hit a wall that would be easy, but as always, the response is a lot trickier than the detection...

Have you tried the stick constrain model, using verlet integration, as described by jakobsen?


I can see it kind of working like you want. You can force the stick to rotate constantly around it's centre, but at the same time react to walls in a proper way.

EDIT : BTW, I've updated a basic demo of mine using that jakobsen stuff. It's doing the helicopter thing as a proof of concept, if that's what I think you want. Look at the console for the controls.

verlet physics

[Edited by - oliii on January 7, 2005 6:56:55 PM]

you could place priority constraints for the reactions...

like:

-the reaction force would have a lower priority than the secondary collision detection

I haven't fully implemented it yet, but I've been playing around with the Verlet stuff, and I'm really amazed at how such a simple system is so stable. To get it to work in my game I'm going to have to modify the collision detection a good bit, but I think this will work out nicely.

Thanks a lot, guys!

I understand how to reflect across a normal, but that's not what was causing the problem - the issue was finding a stable way to keep the helicopter inside the walls. (I've actually it's much more effective for my purposes just to deflect the particle in the direction of the normal regardless which direction it came from).

Edit: Disregard the below! I figured out that you can solve the problem by approximating the space that the stick occupied while doing the past frame's worth of moving, and find out if wall points are inside of it :)

Verlet is working pretty well, but there's one collision detection issue that was brought up in Jakobsen's paper that I can't seem to resolve. It was the case where the object you're detecting collision with is convex. I made a program to test this out, here's a screenshot of a situation like what Jakobsen was talking about:



That's a problem, because the helicopter can pass through it without either of its vertices passing through. Moreover, the wall could be a single isolated square, so it's not necessarily case that the helicopter would be intersecting it after passing through, either.

I understand how to -resolve- a collision here, that's detailed in the paper...the issue is detecting it. It's one thing if the helicopter is just translating, because then all of its points move at the same rate - so I can find a single line segment that describes the motion of the wall's vertex relative to all of them, and see if it intersects the helicopter. However, it rotates as well, so no one segment can achieve this task. Anyone know a better way to do this? Keep in mind that there's no concept of "inside" and "outside" in this game, a wall might separate two perfectly legal areas, so I can't just test if a point is outside the legal area since it could jump through a wall but still pass that test.

[Edited by - _Flecko on January 9, 2005 5:51:50 AM]

Well if you think about the line spinning infinitely fast, it would be a solid circle.

So, I suppose you could do a swept-circle test vs the environment, and if the circle touches something, do further tests based on the line's angular velocity.

you can trace the particle at the end of the stick using the current_pos and previous_pos. That should be a lot more accurate than testing if the particle is inside the solid area. That's the method I use, but I don;t test the segment intersections. With both methods working together, it should be quite solid.

You can also decompose the trajectory of the helicopter into smaller discreet timesteps, and test collisions then. Again, a simple linear interpolation on the vertices of the helicopter should be enough.

I would recommend BSP Trees.... at first look they may seem like overkill, but under a 2D game like yours, they would be extremely easy to code, and the Collision Detection would also benefit tremendously, giving you a vector normal for the collision even...

I can also bet that the BSP information of a map, when saved to disk would have a small footprint, add to that the fact that BSP trees are fast, and you could have an easy port to portable devices...

PM me if you have any further questions on this...