# prushik

Members

34

164 Neutral

• Rank
Member
1. ## Collision response forces in rigid body simulation

Right, but I'm fairly confident that those cases will never happen, and I would be happier with a fast algorithm that is correct in almost all practical scenarios than a slower one which is perfectly correct all 100% of the time. However, I'll be very happy if the 100% perfect solution is faster. Actually, the incorrectness of the algorithm was a little bit useful for me, before implementing SAT, my game generated an NPC and placed it exactly on top of the player. since they were exactly the same size, no collision was registered, allowing me to drive away (as long as I drove perfectly straight) and then test collisions from different angles. Now that I'm using SAT, I need to generate the NPC elsewhere. (which I needed to implement later anyway)   I realized that after posting, there is no real contact point, the contact point is a bit of an illusion. However, I do need to choose a point somewhere in that region, since I need to apply the forces somewhere. The code that I am using right now actually still does both types of collision checking... SAT for separation axis, and the corner method for point of contact point. Obviously, that needs to be changed eventually. My old algorithm uses the point which is contained inside the other object as the contact point. Although, my SAT implementation has some trouble. It finds collisions correctly, but does not give the overlap correctly, and does not return the correct axis.   My code looks like this if you want to look at it: void SATgetMinMax(struct vehicle *obj, VEC2 *axis, double *min, double *max) { double mina,maxa; VEC2 tmp,corner; setVEC(obj->img.w/2,obj->img.h/2,&tmp); relativeToWorld(obj,&tmp,&corner); addVEC(&corner,&obj->chassis.coord,&corner); mina=dotVEC(&corner,axis); maxa=mina; setVEC(-obj->img.w/2,obj->img.h/2,&tmp); relativeToWorld(obj,&tmp,&corner); addVEC(&corner,&obj->chassis.coord,&corner); if (dotVEC(&corner,axis)<mina) mina=dotVEC(&corner,axis); if (dotVEC(&corner,axis)>maxa) maxa=dotVEC(&corner,axis); setVEC(-obj->img.w/2,-obj->img.h/2,&tmp); relativeToWorld(obj,&tmp,&corner); addVEC(&corner,&obj->chassis.coord,&corner); if (dotVEC(&corner,axis)<mina) mina=dotVEC(&corner,axis); if (dotVEC(&corner,axis)>maxa) maxa=dotVEC(&corner,axis); setVEC(obj->img.w/2,-obj->img.h/2,&tmp); relativeToWorld(obj,&tmp,&corner); addVEC(&corner,&obj->chassis.coord,&corner); if (dotVEC(&corner,axis)<mina) mina=dotVEC(&corner,axis); if (dotVEC(&corner,axis)>maxa) maxa=dotVEC(&corner,axis); *min=mina; *max=maxa; } //Check for collisions with SAT int SATXvehicles(struct vehicle *a, struct vehicle *b, VEC2 *over) { int i; double overlap, mina,maxa, minb,maxb; VEC2 tmp, axis, saxis, corner; //Axis to check setVEC(1.0,0.0,&tmp); relativeToWorld(a,&tmp,&axis); //Find min/max values on axis SATgetMinMax(a,&axis,&mina,&maxa); SATgetMinMax(b,&axis,&minb,&maxb); //Check for overlap if (!Xline1d(mina,maxa,minb,maxb)) return 0; else { overlap=minb-maxa; setVEC(-axis.y,axis.x,&saxis); } //Axis to check setVEC(0.0,1.0,&tmp); relativeToWorld(a,&tmp,&axis); //Find min/max values on axis SATgetMinMax(a,&axis,&mina,&maxa); SATgetMinMax(b,&axis,&minb,&maxb); //Check for overlap if (!Xline1d(mina,maxa,minb,maxb)) return 0; else { if (minb-maxa>overlap) { overlap=minb-maxa; setVEC(-axis.y,axis.x,&saxis); } } //Axis to check setVEC(1.0,0.0,&tmp); relativeToWorld(b,&tmp,&axis); //Find min/max values on axis SATgetMinMax(a,&axis,&mina,&maxa); SATgetMinMax(b,&axis,&minb,&maxb); //Check for overlap if (!Xline1d(mina,maxa,minb,maxb)) return 0; { if (minb-maxa>overlap) { overlap=minb-maxa; setVEC(-axis.y,axis.x,&saxis); } } //Axis to check setVEC(0.0,1.0,&tmp); relativeToWorld(b,&tmp,&axis); //Find min/max values on axis SATgetMinMax(a,&axis,&mina,&maxa); SATgetMinMax(b,&axis,&minb,&maxb); //Check for overlap if (!Xline1d(mina,maxa,minb,maxb)) return 0; { if (minb-maxa>overlap) { overlap=minb-maxa; setVEC(-axis.y,axis.x,&saxis); } } copyVEC(&saxis,over); multiplyVEC(over,overlap,over); multiplyVEC(over,5.0,over); return 1; }
2. ## Collision response forces in rigid body simulation

Of course, I should have known by your wording. I was not using the separating axis theorem before, I was just checking if the corners were contained inside the other object. I have SAT implemented now, and I see that it does a lot less comparisons, even in the case of a collision. However, it does more math. I was under the impression that SAT was very efficient for complex shapes, but for simple shapes like rectangles, SAT is still efficient, but not as efficient as simpler methods. Comparing the code that I wrote using both methods, it looks like SAT is a lot more efficient, even in worst cases, should that be true? Anyways, my implementation of SAT doesn't return anything but a true/false, but I understand how I should get the axis and the overlap amount. Now my next question is, is there an easy way to get the contact point using SAT?
3. ## Collision response forces in rigid body simulation

Yeah, basically. Do you have any pointers on how to figure those out? Currently only a true/false is returned and a VEC2 is set to the point of contact. Now, I'm a bit confused, at first I wondered even what kind of value the overlap would be, scalar, vector? but I guess either would work given that I also have the separation axis direction. If I had those I could just multiply that by mass and add that as a force and they should separate, so I think that I understand what to do once I have that data. But how can I determine those in my collision detection? I'm not even sure what the separation direction should look like, perpendicular to the side of the vehicle?
4. ## Collision response forces in rigid body simulation

I finally got around to implementing essentially exactly what you said. although I did not add any extra velocity for separation, which remains a problem. I think really the problem is the separation. Basically it behaves about the same as it always did now that I implemented that. Sorry, I just lied: It does indeed behave much better, now that I understand what I need to use for the mass, I have collisions working both ways. So the code fixes TWO HUGE problems that I had before, collisions of two objects with greatly differing mass (1), and handling collisions when the the NPC collides with the player as opposed to the player colliding with the NPC (2).   This is the remaining problem. My collision detection algorithm is not flawless, but it works well and I think should be fairly cheap CPU-wise. It would suffer from the problem you describe, but vehicles would have to be moving at absurdly high speeds for that to happen, and vehicles will reach a max velocity which should be far less than that. Also given that I don't intend this to be a game about high speeds, its more about power, this is not an issue that worries me. However, what does worry me is how to find the separation velocity. I need them to separate. My collision detection returns 2 points, however, they are actually the same point, just given relative to each object involved in the collision. I could use the velocity of the vehicles to determine separation, but this is flawed because, depending on how fast the vehicle is going, it may push them apart too far and make it appear that a collision has occurred too soon. I could maybe separate them checking factors of their velocity to see what is necessary to separate, but that would be expensive. Or, I could guess at a factor, but this would result in overlap, which would get the two stuck on top of each other. I guess your "Vseparation = - Vapproach x restitution" method is basically the last method, right? and the first method is the same but the a restitution of 1.0, right? Is there some less brute force method that you can think of?
5. ## Collision response forces in rigid body simulation

Its all in C using SDL2 for graphics. You can checkout my code with subversion svn co https://subversion.assembla.com/svn/highwayman/   If you do so, promise not to laugh at any bad code you might find, I know its not perfect. I have some comments in the code that say "//HACK" thats where most of my really bad code is. And last time I tried, it had some problems on Windows, however, I have fixed a lot of bugs, so maybe it works now. If you run Linux, then it should work well. I didn't fix the collision resolution stuff yet, I've been really lazy this weekend and today I helped my friend move to a new apartment. The code it licensed under the Beerware license, so you can do whatever you want with it.
6. ## Collision response forces in rigid body simulation

Wow, thats great. I think it answers all my questions about impulse. Except for 1 thing, my game deals with vehicles colliding with each other, now vehicles do compress somewhat on collisions to protect the driver, so the collisions will be almost inelastic, right? However, do I want a totally inelastic collision for my game? For a wall an inelastic collision is great, I never saw a car bounce off a wall before, but in a vehicle/vehicle collision should there be some elasticity? I'm not sure. an inelastic collision could result in problems because my collision detection actually checks if they are overlapping, I figured that would be sufficient, but maybe it isn't good enough, would it be better to check if the vehicles will overlap in the next step?   My game is top down, like blimp view, so I won't need to worry about gravity in this one. The cases that I am worried about are 1. One car constantly pushing against another. Which I am afraid the AI that I am going to write will do often... 2. cars at similar speeds and directions making contact with each other.     I think I may need to do something like this too, since my collision detection allows them to overlap before it detects.
7. ## Collision response forces in rigid body simulation

There is one thing that I am really really confused about. Force = Mass * Acceleration Right? This is basic stuff. If a vehicle collides with a brick wall, I can use this equation to figure out how much force gets applied to the vehicle to make it stop moving. However, in a collision, there are TWO objects colliding. In the F=ma , which object's mass do I use? If every action has an equal and opposite reaction, it must be the same amount of force in both directions. Ok. I guess I am starting to see my problem. acceleration is not known, right? If I use the velocity of the player it applies enough force to stop the player, which won't be the case if the vehicles have different masses.   So the answer is much more compicated than I thought, I see now. However, since the vehicles that I am testing with DO have the same mass, shouldn't what I am doing (difference of velocity times mass (of either vehicle, since they are the same)) work correctly?     Ok, also confused about impulse. I understand what it is, however, in my simulation, it shouldn't apply because the collision takes place instantly instead of over a period of time. So I only need to calculate force, right? If the collision is continuous, then it will count as multiple collisions, isn't that sufficient?
8. ## Collision response forces in rigid body simulation

Cool, thanks. Awesome game, I played it far too many times before even looking at the code. Actually, still haven't gotten around to looking at it really, although I at least opened it. I don't care too much about realistic friction, your game reminds me a lot of the physics in FreeGish, which I also played an embarrassing number of times. I don't know if it will work for my game or not, but I'll check it out and see.       Yes, I have been reading about impulse. Whenever I see a site with all those big equations my mind just goes blank and I can't focus enough to make it make sense, if they would just write it all on one line like an equation in C I could understand it no problem, but instead they gotta be all mathy.   I found this site: http://hyperphysics.phy-astr.gsu.edu/hbase/truckc.html Which talks about impulse here: http://hyperphysics.phy-astr.gsu.edu/hbase/impulse.html Which seems to tell me what I want, but I think I am only thinking of the head on collision which is basically 1D, and 2D collisions are more complicated than that. I looked at the one you linked to also. Scary stuff. But thanks, I gotta sit down and work all that out and figure out how to do it in my code.
9. ## Collision response forces in rigid body simulation

Basically, its the same project I'm working on, 2D driving game. I have 2 (or more, but 2 for now) vehicles using rigid body based physics, all in 2D. right now there are no other obsticles to collide with, just the 2 vehicles. I think I can detect collisions perfectly (based on bounding boxes only), and those same collision detection functions return the point of contact relative to both vehicles. I can easily determine the velocity of those points on each vehicle. So, what I did was take the difference of those 2 speeds, and multiply that by the other vehicle's mass to get the force, and then apply that to the vehicle at the point of contact, do that for both vehicles. The result looks ok for stuff like head on collisions, or high speed collisions, if one vehicle is stationary, etc... probably not too realistic, but doesn't need to be perfect, just not too absurd. However, the real problem occurs when I try to push another vehicle with the players vehicle, the result isn't bad for the first few frames, but then the player starts to push its way into the NPC vehicle, so the images overlap. So, what is the problem here? I'm a bit confused about how this is happening, at this point, the vehicles are even the same mass, so if I mix up which vehicle's mass I am multiplying, the result should be the same. This seems like something that should have a well known solution, I'm just too dumb to figure it out on my own.
10. ## creating random rectangles to cover a grid

[quote name='laztrezort' timestamp='1355197843' post='5009300'] The simplest way I can think of (that I've personally used in the past) is to use Binary Space Partition - where you split the rectangle down recusively until you have the desired number of sub rectangles. This describes the method as used in procedurally generating a 2d dungeon: [url="http://roguebasin.roguelikedevelopment.org/index.php?title=Basic_BSP_Dungeon_generation"]http://roguebasin.ro...geon_generation[/url] [/quote] [quote name='Álvaro' timestamp='1355197812' post='5009298'] If you want the union of all the rectangles to be a big rectangle, perhaps it's easier to start at the top. Take a big rectangle and subdivide it into two rectangles, by cutting it in two by a random line (perhaps along the longest side). Repeat until you have 20 rectangles. This procedure always results in tilings that have "fault lines", but that might be acceptable in your application. [/quote] Ok, great, thanks. This solves most of my problems. I may use this kind of algorithm, although I am not entirely sure yet. I do want there to be some space that remains outside of any rectangles (the player's starting location), but that can be accomplished manually. The more I think about the problem, the more complicated it seems. I will try to use BSP and see what the result looks like. It solves many of the problems: all rectangles will fit, none will be too small, and it prevents overlapping. The cons are that it isn't quite as random as I hoped; for instance, there is always a big line down the middle. The rectangles will represent the territories of in-game rivaling factions. So the borders will be danger zones where factions conflict, and border shapes might change depending on who wins the conflicts. So what I can maybe do is use BSP to divide, and then simulate some conflicts to randomize a little more, although that runs the risk of eliminating factions before the player even gets a chance to play, although it would be very rare and I'm sure I can find a way to prevent it completely.
11. ## creating random rectangles to cover a grid

This should be simple, but for some reasons I am having trouble coming up with a solution. Essentially I have a structure which contains 2 2D vectors (coordinate and size). I have about 20 instances of this structure. I also have a grid. What I want to do is randomly set the coordinates and sizes of these 20 structures so that they all fit into the grid and do not overlap each other. The problem is that I need to have all of them in there. If I just start tossing them in randomly, its possible for one to become too big and take up the entire grid, which prevents others from forming, causing an infinite loop right in the beginning of my program (which sucks). I also want to minimize the possibility of very very small rectangles, since that could make it too easy for the player of my game (winning could consist of eliminating a specific rectangle). Any ideas?
12. ## Tractor Trailers with Rigid Bodies in 2D (hinge constraints)

UPDATE: Ok, so I have implemented something based on what I was thinking. Both the tractor and the trailer are rigid bodies. I calculate forces generated by the wheels in both objects, then integrate the forces. Then I calculate the speed difference between the attachment points on both objects and multiply by mass to get the force vector. Then I add that force vector to one object and an opposite response force vector to the other. Then integrate the forces again. Does this make sense? The result is something that looks almost right. They stay (almost) together, and pivot around the hinge point. However, sometimes weird problems occur. The trailer drifts off the hinge point (very slowly) after substantial use, and sometimes the trailer pulls the tractor into unexpected high speed turns, not sure why. I'll post the relevant code: [source lang="cpp"] struct image { const char *fname; void *texture; //SDL_Texture int w,h; double angle; }; struct rigidBody { VEC2 coord; VEC2 speed; VEC2 force; double mass; double angle; double angleV; double torque; double inertia; }; struct wheel { VEC2 coord, forward, side; double angle, speed, radius; double inertia, torque; double steer,throttle,brake; }; struct vehicle { struct rigidBody chassis; struct wheel wheel[4]; struct vehicle *trailer; VEC2 hinge,pin; struct image img; }; void updateHinge(struct vehicle *obj) { //Don't apply forces from trailer if there is no trailer if (obj->trailer==NULL) return; VEC2 hoffset,poffset,hspeed,pspeed,wspeed,force; relativeToWorld(obj,&obj->hinge,&hoffset); relativeToWorld(obj->trailer,&obj->trailer->pin,&poffset); pointVel(obj,&hoffset,&hspeed); pointVel(obj->trailer,&poffset,&pspeed); subtractVEC(&hspeed,&pspeed,&wspeed); reverseVEC(&wspeed,&wspeed); multiplyVEC(&wspeed,obj->chassis.mass,&force); addForce(&obj->chassis,&force,&hoffset); reverseVEC(&wspeed,&wspeed); multiplyVEC(&wspeed,obj->trailer->chassis.mass,&force); addForce(&obj->trailer->chassis,&force,&poffset); return; } int main() { struct vehicle user,trail; initVehicle(&user,20.0); user.chassis.coord.x=100.0; user.chassis.coord.y=200.0; user.chassis.angle=0.0; initWheel(&user,0,30.0,15.0,2.0);//FL initWheel(&user,1,30.0,-15.0,2.0);//FR initWheel(&user,2,-30.0,15.0,2.0);//RL initWheel(&user,3,-30.0,-15.0,2.0);//RR user.wheel[0].throttle=0; user.wheel[1].throttle=0; //Initialize test trailer initVehicle(&trail,40.0); trail.chassis.coord.x=100.0-32; trail.chassis.coord.y=200.0; trail.chassis.angle=0.0; initWheel(&trail,0,-25.0,15.0,5.0);//FL initWheel(&trail,1,-25.0,-15.0,5.0);//FR initWheel(&trail,2,-30.0,15.0,5.0);//RL initWheel(&trail,3,-30.0,-15.0,5.0);//RR trail.wheel[0].throttle=0; trail.wheel[1].throttle=0; trail.wheel[2].throttle=0; trail.wheel[3].throttle=0; //Attach tractor and trailer user.trailer=&trail; user.hinge.x=-32+14; user.hinge.y=0; trail.pin.x=14; trail.pin.y=0; //Set more stuff up... while (1) { //......Other stuff updateWheels(&user); updateWheels(&trail); updateRigidBody(&user.chassis); updateRigidBody(&trail.chassis); updateHinge(&user); updateHinge(&trail); updateRigidBody(&user.chassis); updateRigidBody(&trail.chassis); //....Draw the stuff here } } [/source] Now, obviously, there is a lot of code left out, but this should be the relevant parts. If there is something else that you need to see then let me know and I will provide. I intend to release my project open source, so I won't be hiding anything.
13. ## Tractor Trailers with Rigid Bodies in 2D (hinge constraints)

Basically what I want to do is implement some basic tractor trailer physics using rigid bodies. Right now I have rigid body physics that look decent (good enough for me right now) for a single segment vehicle (car, bus, etc...), however, tractor trailers are important in my game. I've been thinking about this problem for some time and searching the internet, and have come up with so much information, but nothing that really solves the problem. It seems it should be easy, this is just a simple 2d game. Should I create a point on both rigid bodies that acts similar to a wheel and applies force to the rigid body equivalent to what is needed to keep the bodies connected? or is there some other way that this should be done? Both segments will need to exert forces on each other. I found a guy who wrote an algorithm here: [url="http://gamedev.stackexchange.com/questions/18151/how-can-i-implement-revolute-hinge-joints-in-a-2d-physics-system"]http://gamedev.stack...-physics-system[/url] It seems to be what I was looking for, but from the page it seems there may be some problems with it. And the author seems unsure of himself. So, is that the right approach to take? (I'm using C and SDL2, if you want to know) EDIT: Also note that my simulation should be simpler than the article I linked to, since I only have one hinge point where it looks like the article actually has 2.
14. ## Drawing images along a line

Ok, I implemented something based on what you told me. Right now it looks pretty bad, but I am definitely on the right track. I'm storing offset vectors alongside the links and using those to draw images on the lines. I'm also storing rotation angles with the links to get the images oriented correctly. It basically does everything I asked for. The biggest issue now is the speed. I went with the brute force method, checking each image to see if it is in the view and only drawing those that are close enough, and that actually keeps it running at a reasonable speed, although in my mind I know its an absurd number of comparisons per step ( I have 2000 nodes, each with up to 4 links ). I have some ideas to optimize that though. So basically I want to say that your suggestion worked for me, thank you.
15. ## Drawing images along a line

[quote name='Emergent' timestamp='1352864305' post='5000774'] I have a suspicion that anything reasonable that you do will be plenty fast enough. The standard/obvious thing to do would be to convert your line segments to quads ahead of time, store them in some kind of spatial data structure (e.g., quad- or KD- tree, regular grid, or just arrays sorted by x and y position), do a conservative cull against your view box, and then and draw what's left with hardware texture mapping if available. The line-segment--to-quad math, by the way, is pretty cheap. If you have a line from p1 to p2, then the tangent to the line is T=normalize(p2-p1), and the normal is N=J T, where J is the 90-degree rotation matrix (it exchanges the x and y coordinates and flips the sign of one). Then, if the road width is w, and if we define an "offset vector" by d = 0.5 w N, then you can just write the vertices as p1 + d, p1 - d, p2 + d, and p2 - d.[/quote] Great thanks, that was pretty much exactly what I wanted to hear. Basically all I need to do is store normal or offset vectors in the node structure along with the node links. Seems easy enough. I'll try to get something implemented on the subway on the way to work :-P. [quote name='Emergent' timestamp='1352864305' post='5000774']Back to spatial data structures: The only other thing that springs to mind is to exploit temporal coherence and the fact that your world is a graph, by storing neighbor/linkage information in the line segments, maintaining a list of the edges currently intersecting the edge of the view box, and, each frame, only doing intersection tests with those edges and their neighbors, to determine which of these line segments are entering or leaving the view. The assumption this would make is that you can never move more than the length of an edge in a frame. This is probably the fastest method, but also the least flexible, and, since you could probably get away with brute-forcing this, I can't really recommend it, even if it is the most amusing. [/quote] I considered something like that. However, there might be some problems with that approach which could be difficult to overcome, such as if a non-neighboring line crossed a line which is in view. That shouldn't happen much, but I know it will happen sometimes. However, I'm sure it is safe to assume that the user will never move farther than the length of an edge in one step, the edges should be much much longer than the players top speed or else the game wont be much fun. I'll see what I can do and let you know what happens. thanks