Basic Physics Engine.. WIP
Community Forums/Showcase/Basic Physics Engine.. WIP
| ||
| Hi I made a little physics engine in bmax as a small first project and it turned out to be quite succesful! It is still very much a WIP but I am improving on it daily. Sorry there are no screenies ATM. maybe I will post some tomorrow if I have time. Please post how many boxes your comp can handle without significant slowdown. controls: arrows:move one of the starter verlets.. cant remember wich one space bar: add a box! mouse: click to grab the nearest verlet! friction test: most recent linky http://naillproductions.synthasite.com/resources/NTG%20physics%20engine%20(2).zip edit: here is a screenie!  |
| ||
| pretty good so far I could add about 6 boxes with a 2.5ghz celeron |
| ||
| only 6 boxes?!? thats um.. a little lower than I expected... I can get around 30 boxes |
| ||
| Quite slow when spawning boxes here too. |
| ||
| I started noticing some jitters fairly early too, at around 12 boxes. |
| ||
| hmmm im not sure what the jitters are, I have noticed them too. Maybe it is my inexperience with frame limiting in bmax? I simply use graphics 800,600,0,60 and asume it does the rest. Am I right to assume that or must I do something else? If I am doing everything else right I might have accidentally made my engine unstable. :p each box is 8 verlets and 14 constraints so that may also explain it. |
| ||
| No, you can't just set the graphics mode and hope it does the rest. You need a proper timing solution, and since you're doing verlet integration you'll need to have a fixed timestep. You probably already have a fixed timestep if you're doing nothing for timing, but you'll need to keep it when you integrate a timing solution. QuickSilva has a thread going on the subject in the BlitzMax beginners forum if you want to read up. |
| ||
| thanks.. hmm for some reason I thought that blitz max somhow controled the frame rate with the flip command Ill look into a timing solution. Thanks Gabriel |
| ||
| Well if VSync is enabled, it kind of will, but it's dependant upon your code running fast enough for VSync to work. If your code isn't (always) done before the next VSync, it will jerk. Also, if someone happens to have VSync disabled, it's just not going to happen. |
| ||
| Ok I think I get it. I have also rooted out the slowdown. I had it on 25 iterations in the constraint loop! oops :p |
| ||
| hmmm this is odd.. I have used waittimer for a quick way to mess around with fps and time steps but it seems even with waittimer my minimum fps is 11 and maximum fps is 111! ah well looks like ill have to do some fps experimenting the hard way.. Also I will have to rely on keeping a constant fps and NOT on changing the timestep for the type of game I am doing... It has to do with time travel so you can go back in time and visit a previous self but you cant cause a paradox with the physics! Thus changing the time step even by a small amount will cause a paradox :( its a paradoxical situation in itself :/ edit Minor Succes! Now I can have 80 boxes on screen. the only problem is as with all physics engines, it explodes because of the massive amount of weight on the bottom verlets. At least it runs at a steady 30-32 fps! new control: press a to reset the min and max fps values for testing purposes. Please post your stats at the upper left hand side of the screen(only after pressing a of course!) http://naillproductions.synthasite.com/resources/physicsenginetest%20(4).zip |
| ||
| last time it was 6 but this time it was about 22 |
| ||
| noticed the slight lag at 20 - not bad physics |
| ||
| Hey pretty cool stuff, I'm impressed. I got very little lag, but I'm on an AlienWare here at school. Once I put about 40 physics blocks in, it started freaking out. The blocks were just flying everywhere. It made me smile. Cool stuff though, where is this project headed? |
| ||
| Cool stuff though, where is this project headed? im not really sure where this project is headed. Maybe something similar to fantastic contraption or maybe even a game called ParadoxodaraP? anyway I am working on polygon collisions at the moment I know the blocks expode but this wasnt meant for high stress and the time step is a bit high at the moment due to speed issues Im glad its faster now! thanks for the feedback |
| ||
| WOW! I feel extrememly stupid. I cant believe I didnt see it before. I just messed up when I was making one of my formulas (I like to make up my own because they get better every time) and it was leading to slow innacurate jittery physics! I fixed it and now I can have ~50 boxes before it starts to slow down and there are almost no jitters until it gets to ~90 boxes! now for the polygon collisions... new download link! http://naillproductions.synthasite.com/resources/physicsenginetest%20(4).zip updated all links! |
| ||
| you should put a box counter on the screen, I got about 34 this time |
| ||
| you should put a box counter on the screen oops I planned to do that last time. will do for the next download I got about 34 this time wow thats a great improvement from 6! Im glad to know my optimizations did that much! |
| ||
| ok I have some verlet-polygon collisons now! it should still be very fast! there is now a boxcounter for those of us too lazy to count how many times you hit the spacebar (myself included) please tell me how many boxes you can get without jitters or extended drops in frame rate. (note: I cut the time step in half thus doubleing the updates per loop so be on the lookout for strange behaviour) download: http://naillproductions.synthasite.com/resources/physicsenginetest%20(4).zip |
| ||
| It was fine at 100-The physics went crazy at 111 (Guess they had nowhere else to go, started flying everywhere)-at 120 it started to slow down, and at 200 it was getting pretty laggy. |
| ||
| ok wow that sounds great! 100 boxes? or 100 verlets? or 100 constraints? I have only tested up to 90 boxes |
| ||
| the FPS dropped to about 15 after 10-14 boxes |
| ||
| thats odd it seems it has dropped significantly... I am working on optimizations and cleaning up messy bits of code at the moment. This has a long way to go. Thanks for testing Jeremy Paxman! just a wee little question: you dont happen to be running any programs like IE or word when testing this do you? When I open word my framerate also drops very low. |
| ||
| oh yeah I will make sure I didnt have a youtube video in the background........ nope still 14 boxes, have you tried replacing lists with arrays? |
| ||
| @ Jeremy Paxman - no I havent.. are they significantly faster? |
| ||
| yep a lot faster i think, |
| ||
| is there a specific method for using arrays instead of lists |
| ||
| If you have some nested loops like: working on a list with only 300 things in it for p:physicsobject=eachin objlist for q:physicsobject=eachin objlist then its 90,000 operations so that might be slow but anyway... I think you just put your objects in an array, |
| ||
| oh.. I see your point. I had never thought about that. So really it is phenomenal if any computer can get to say 75 boxes because thats 90,000 collision checks not counting the constraint loop. Also can you explain how I would go about using arrays? or maybe a link? |
| ||
| Can't you do a quick distance check between 2 boxes? If the widest part of the item+the widest part of the other item is less than the distance from centre to centre, then don't perform any more collision checks. |
| ||
| @ ross C - I just did that :) its working quite well but not as quickly as I would like. It keeps track of the largest verlet and doubles that value. If the verlets are not within that distance of eachother on the x and y axises, it doesnt even bother checking anything else. overall I have gotten my box count to 60 on a dual core 2.4 ghz. would it be more efficient and accurate enough to use a square root array to store all the sqareroots? |
| ||
| @My earlier post, I meant boxes. This little project reminds me of Garrys Mod...Think I'll go play it. |
| ||
| Are you using bitwise operations of multiplication and division? You should see an increase in performance by using bit shifts, ands, and ors instead of multiplication, division (by powers of 2 that is) and mod. Or does Blitz automatically convert division by base two numbers to bit shifts? I believe Python does this... |
| ||
| @ sauer - you lost me at bitwise.. so are you saying I should divide by 1/ a number rather than multiply? |
| ||
| No, you can use the commands SHR and SHL (bit shift right, bit shift left) which you can use in place of where you divide by a power of two. If you've ever wondered why tile based games all have tiles that are a power of two (16,32,64 are common sizes) this is it. Division takes about 11 cpu instructions to complete, whereas a binary shift takes one. This can lead to great optimization. Basically everywhere you would divide by a power of two, bit shift right, and whenever you want to multiply by a power of two, bit shift left. Basically all it does it takes all the bits and puts them one 'bin' to the right or left. I don't know how well your binary skills are but you can implement it without really knowing whats going on. Here are some examples: x/32 = x>>5 ; we can shift x five bins right, dividing by 32 (2^5) x/16 = x>>4 ; same thing, 16=2^4, so we just shift right four times x/2 = x>>1 ; you can even bit shift when dividing by two *note, >> would be SHR in blitz, in other languages it's actually an operator You can do the same with multiplication, but instead of SHR use SHL. I'm not sure how much MOD you are using, but if it's a lot and you are modding by a power of 2, there's a way to use bitwise OR to do that too, which I can also explain if needed. Hopefully that made a bit of sense. <==EDIT Awesome unintentional pun by me. :) |
| ||
| To avoid doing checks between all boxes you could divide the screens up into squares and keep track of a list of boxes for each square. Then for collision detection you only do checks between boxes in adjacent squares. |
| ||
| @ foppy wouldnt that possibly be less efficient? I can see how that would work though. Ill give it a go nice pun sauer but I soon found out that you cant do bitwise operations on floating point variables :( and that is the only place I need it Here is my code for checking collisions between verlets just so you can see what I am getting at.. the boxes are made up of 4 verlets each. For Local v:verlet = EachIn verletlist For Local vv:verlet = EachIn verletlist Local dx# = v.x - vv.x Local dy# = v.y - vv.y If Abs(dx) < maxverlsiz And Abs(dy) < maxverlsiz Then If v.id <> vv.id ' If Not the same verlet Or group Local dist# = Sqr ( dx#*dx# + dy#*dy#) Local totalr# = v.siz# + vv.siz# If dist# < totalr# Then Local dmtr# = dist#-totalr# Local Diffx# = ( dmtr# ) * ( dx# / dist# ) Local Diffy# = ( dmtr# ) * ( dy# / dist# ) If v.active = True Then v.x = v.x - Diffx# '* .5 v.y = v.y - Diffy# '* .5 EndIf If vv.active = True Then vv.x = vv.x + Diffx# '* .5 vv.y = vv.y + Diffy# '* .5 EndIf EndIf EndIf EndIf Next Next Edit: I optimized this a lot with only a few lines of < and > statements! Note: I took out the time step! It was an optimization but also because I am going for a different approach on verlet physics in which a time step messes everything up. I know its a radical move but its worth a shot. now I get 80 boxes until it starts lagging... my goal 150! |
| ||
| wouldnt that possibly be less efficient? Well, as the boxes move around there are extra operations to check if they go from one square into the next, and if so, a few operations to remove them from one list and add them to another.However if there are a lot of objects I think the smaller amount of collision checks will outweigh the extra administration, because the number of potential collision checks increases quadratically while the administration costs increase linearly. Maybe it's not as applicable to your physics engine as it is to my action games (or as easily applied). You would have to consider the size of those squares in relation to the maximum size of the objects: the algorithm relies on the fact that objects in non-adjacent square cannot touch each other. You say you are already doing a quick distance check between the boxes, this means the relative profit from the above algorithm are smaller. But still, perhaps an idea to keep in mind. |
| ||
| But still, perhaps an idea to keep in mind. ill definitely keep that in mind. it sounds like it could be just what I need but ill have to do some research and testing. |
| ||
| I can fill the screen ith boxes now, I get 110 boxes before the simulation explodes. |
| ||
| To avoid doing checks between all boxes you could divide the screens up into squares and keep track of a list of boxes for each square. Then for collision detection you only do checks between boxes in adjacent squares. zoning... there are many different methods but they really do increase your collision efficiency. [edit]below is the wrong solution![edit] but for Nate's example above another type that you could be easily implemented is just making sure you never check a collision between the same 2 objects more than once. ie, once you check the first one with all the other ones, the first one shouldn't be in any more checks... etc.. every object only has to check the objects below it in the list because the objects above have already done this check. further more there is no reason to check the onbject against itself. SuperStrict Type mytype Global list:TList = New TList Global gi:Int = 0 Field i:Int Method New() i = gi gi:+1 list.AddLast Self End Method End Type For Local i:Int = 0 To 3 New mytype Next For Local t:mytype = EachIn mytype.list For Local tt:mytype = EachIn mytype.list Print t.i+" checking "+tt.i Next Next 'as opposed to... Print "~nonly check once" Local l:TLink = mytype.list.FirstLink() While l <> mytype.list.LastLink() Local ll:TLink = l._succ While ll._succ <> mytype.list.FirstLink() Print mytype(l._value).i+" checking "+mytype(ll._value).i ll = ll._succ Wend l = l._succ Wend l = Null now I would use a singly linked list so the loop would look like this Local v:mytype = mytype.First() While v Local vv = v.succ While vv Print v.i+" checking "+vv.i vv = vv.succ Wend v = v.succ Wend |
| ||
| @Dmaz - great Idea! thanks. I never really thought about that but it does seem like it would work :) ill give it a go |
| ||
| thanks for all the help everyone (keep it coming) because I decided I will release this free with source code once I get it all fixed up.. keep in mind I made it for my own purposes so it may or maynot fulfill all of your requirements. and yes its superstrict :) I started it one day messing around to see if I could learn superstrict and types in bmax if anyone has a list of features they want please post so far there are verlets! constraints! polygon segments (only to collide with ie. the polygons dont move they just sit there) images attatched to constraints gravity vector a waterline with the following features Global Waterlevel:Int = 400 'Waterlevel in pixels Global Waterdensity:Float = 10 'The depth at wich boyancy maxes out Global BoyancyForce:Float = .1 'Best if close to gravity Global WaterFriction:Float = .01 'Needs to be really low for a very subtle effect soon to come (note: these may take a while because I'm very sick right now) optimization - a must images attatched to verlets verlets attatched to the constraints! I know.. its backwards! readablitlity! - this is the last thing I will do. Its already readable but Ill try to make it as user friendly as possible edit @ dmaz - your idea is one that seems good in theory but doesnt work in real life. I tried it and it actually does work a little but the system explodes with very few boxes. I think those extra iterations simply stabalize it more. stability comes first |
| ||
| edit @ dmaz - your idea is one that seems good in theory but doesnt work in real life. I tried it and it actually does work a little but the system explodes with very few boxes. I think those extra iterations simply stabalize it more. stability comes first well ya [hits self on head]. I wasn't thinking, in a physics sim you need to balance the collisions with all the other collisions in the local area because the collisions affect the result. I was thinking in terms of a shooter where you only care about the interaction between the 2 colliding onjects... as foppy said, zoning would be your best bet then since you limit your collisions to the local area (the box it's in and the surrounding boxes) |
| ||
| well ya [hits self on head]. [hits self on head as well] haha I guess it was worth a shot because now I will know not to try it again edit ok I have properly applied friction! it should also be almost twice as efficient as it used to be notice the upper left segment of the triangle has a very high friction while the right side has almost no friction please test here http://naillproductions.synthasite.com/resources/NTG%20physics%20engine.zip |
| ||
| ok updated! now it is much more stable and the speed has doubled for me. I now get 130-140 boxes without any slowdown. :) it is also much more stable. please test and post how many boxes you can get as well as your specs link http://naillproductions.synthasite.com/resources/NTG%20physics%20engine%20(2).zip |
| ||
| how about the ability to 'move the camera' to allow for worlds bigger than the screen I got 130 boxes this time! Ever thought about adding joints? |
| ||
| thanks for sticking with it Jeremy Paxman. I got 130 with the old demo that you just tried too but I just upped it to 170 with another rampage through the code optimizing even more. :) it is quite unstable though. I need to make it more stable now. 170 boxes = 680 verlets! and 1020 constraints! pretty good eh? what do you mean by adding joints? I can make a ragdoll demo if you want me to for proof of concept of verlets and constraints. or do you mean something else? |
| ||
| oh I didnt realise constraints were like joints, a ragdoll demo would be fun! |
| ||
| Ok I will put together an awesome ragdoll demo in a few days. hopefully tomorrow. but im really concerned as to how this is going to shape up as a full blown engine edit by the way I got the camera stuff done, the demos just dont show it edit - moved to here http://www.blitzbasic.com/Community/posts.php?topic=83810 |
   |