Print

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

Control Flow

2 (2.2%)

Arrays, Strings, Pointers, and References

8 (9%)

Functions

4 (4.5%)

Basic object-oriented programming

30 (33.7%)

A bit more advanced OOP (Composition, Operator overloading, Inheritance, Virtual Functions)

18 (20.2%)

Templates

8 (9%)

Other (Explain)

4 (4.5%)

Working with files?  (Streams)

15 (16.9%)

Total Members Voted: 89

[Normandy]

Writing a physics engine is very difficult. Use one from the Internet; it will fit your needs better than you think it will, as you get used to it. That's how it works for any sort of library.

[Supermikhail]

Out of curiosity, how precise does it need to be?

If momentum isn't perfectly conserved, ect,

Well, to be more direct, I'd like to have an ideal gas engine with a possibility of forming molecules out of bodies. So, atoms grinding to a halt because of a leak of momentum would be undesirable, if that's what you mean. Although I can't imagine how that would happen. Which, in turn, is a great indication of how prepared for this endeavour I am.

Another point in favour of option 3 is that I'd like to get experience with using an external engine. But,

circle collisions are pretty easy. if the sum of the radius of the two circles are equal or less than the distance between the center, the circles are in contact. Unless you calculate angular momentum as well, the force and bounce physics are extremely simple vector math. Someone with some maths and programming skill could poop something like that out in a couple days. Joints? That might sounds like it will make things a little uglier.

I've mused up an idea that a way to implement joints would be to have them like a version of a force that drags an object to a certain distance away from another object. That would make joints very springy and without a certain anchor point at the exteriors of objects involved, but that's exactly the kind of joints I want. And the kind that the engine from the Internet doesn't seem to be very good with. Then, forces would be objects connecting pairs of bodies and arbitrarily accelerating the bodies towards/away from each other along the length of the force.

Of course, still pure teenage game maker speculation because I've looked into that engine from the Internet, and at some, apparently, key points I've got no idea why it needs to do what it does.

A, probably, small drawback to an external library is that the code will become less transparent, because obvious "atoms" will become some "bodies" with attached atom data, and there will have to be two separate lists for joints and bonds whose physics they represent, unless I modify the library. But for that I'll probably have to research what it does and figure it out to avoid any repercussions. And then there's the matter of time.

So, with these new details, any new opinions?

[Siquo]

Separating bodies from atom data is a good thing. Good programming is like terrorism: every cell works on a need-to-know basis.

I have NO idea how I that metaphor just popped into my head.

[Supermikhail]

I think you mean OOP, not just any programming... At least in OOP that would be one of the bases.

So, that's a good idea that I didn't realise before your metaphor, but it's a bit hard in my situation. It's true that the physics engine doesn't need to know what kind of things the bodies it manipulates represent, but what's left of the atom then? Position and velocity go to the body, chemical data stays with the element...

Which reminds me of my other gripe with that external engine - they for some reason chose to recreate lists of bodies and joints, and all other thingymajigs on every step of the simulation. And use the list kind unfit for mid-list entry removal, which I'm going to need. Actually, as the collision space keeps custom lists of all things constantly, I've got no idea how my operations will affect the speed.

I guess, for atom data not to waste any space, I could implement isotopes, but that would be a pain to add to the database. And in most cases would probably be a waste of effort.

P.S. Sorry if too much non-programming-related rambling.

[eerr]

"they for some reason chose to recreate lists of bodies and joints, and all other thingymajigs on every step of the simulation."

Did you decompile Haskell as a C program or something?

because recreating everything does not make sense to me- except for very specific formats.

What language is this.(It sounds like a functional language, as opposed to oo or procedural)

[Supermikhail]

Correction:
Most likely I'm dumb and just a padawan in Java.
Yes, it's Java, and the library is native. What messes up my perception of the problem is that on each step of the simulation in each part of the program(collision, forces, graphics) they create a new array object which then does "world.getBodies()"(or "Joints", or "Arbiters") which returns the bodies array from the world... Depending on the cost of creating a new array object (which might amount to a single pointer) it might be cheaper than keeping a single array, because at least you wouldn't have to rewind it to the first element at the beginning of each step.

You might have known all that already, but I can say that I'm a clever learning person.

I still can't forgive them using an ArrayList where one (me) would logically use a LinkedList, because it's better fit for sequential access. At least from all Google tells me.

[Normandy]

Wrong. Memory allocation is generally the slowest process in computing, so physics engines generally pre-allocate all of their memory. Hence, the use of the ArrayList. ArrayList can be accessed at any point (compared to a LinkedList, which can only be accessed sequentially), and thus are better for storing this data. A simple way Physics Engines then use that memory is separating this ArrayList into two partitions; anything with an index lower than the partition is "alive" and will be checked by the simulation. Anything with an index above the partition is "dead" and is not checked by the simulation. Allocating a new body simply becomes a matter of moving the partition up by one, and removing a body simply means swapping the body at the partition with the body that's being removed, then reducing the partition by one.

In other words, don't be so quick to dismiss things that you don't quite understand.

[Supermikhail]

Er. Alright. Yesterday I googled another way and found out that even sequential traversal for ArrayLists is faster, so I remade all my lists into ArrayLists. Well, almost all. So, what you're saying is that even removal at random positions (but reached sequentially) is faster for ArrayLists? My arraylist for bodies stays the same throughout the execution, my arraylist for collisions is refreshed each step, but I've got a LinkedList of forces that may arbitrarily change throughout the execution.

[Siquo]

So, what you're saying is that even removal at random positions (but reached sequentially) is faster for ArrayLists?

Only if you remove it like he said: in that the order of the elements is not important. If you remove by swapping with the last element, and then reducing the "size" (not the reserved size) by one, you'll be changing the order of the elements (but it's even faster than linked lists!). If the order is important, and you'll be adding and removing a lot in large collections, then you should use linked lists, as arrays need to move every element after the one you deleted or inserted to maintain order.

Oh, and thanks Normandy, that's quite a useful tip (for any language).

[Nadaka]

In java arrays are objects. So unless your getBodies() method clones the array, the only cost is building the frame for the method and a single reference to the object.

And Normandy, java does not allocate memory normally. Most of the time the JVM manages memory internally in a pre allocated space. Creating an object in that space takes a small fraction of the machine code instructions as it takes c to allocate an object in fresh memory. This is one of the reasons that modern optimized java approaches and occasionally even exceed the speed of c at the cost of holding on to peak memory for longer.

[Normandy]

Hrm, I was unaware of that. Even still, I imagine that resizing ArrayLists is faster when they're preallocated then when they're not, and LinkedLists can still be only read sequentially, so the concept still applies.

[Blank Expression]

Er. Alright. Yesterday I googled another way and found out that even sequential traversal for ArrayLists is faster, so I remade all my lists into ArrayLists. Well, almost all. So, what you're saying is that even removal at random positions (but reached sequentially) is faster for ArrayLists? My arraylist for bodies stays the same throughout the execution, my arraylist for collisions is refreshed each step, but I've got a LinkedList of forces that may arbitrarily change throughout the execution.

You seem to fundamentally lack an understanding of data structures algorithms. If you don't understand the properties of the various structures that comprise List<T> interpretations in Java and the algorithms that underpin them, start there before you attempt to work with them.

They're not hard. Understanding it is critical. Don't you think it's a little strange to come begging for help without bothering to establish fundamental knowledge and doing it yourself first? "I googled it" is only the first step toward asking smart questions.

Hrm, I was unaware of that. Even still, I imagine that resizing ArrayLists is faster when they're preallocated then when they're not, and LinkedLists can still be only read sequentially, so the concept still applies.

The cost of an insert is an amortized O(1). You do incur a cost when you go over capacity, which is why a smart programmer determines a reasonable capacity when instantiating an ArrayList. (The same holds true for std::vector in C++.) The copy step for these ArrayLists can be mostly ignored until n reaches a fairly large value.

[eerr]

Er. Alright. Yesterday I googled another way and found out that even sequential traversal for ArrayLists is faster, so I remade all my lists into ArrayLists. Well, almost all. So, what you're saying is that even removal at random positions (but reached sequentially) is faster for ArrayLists? My arraylist for bodies stays the same throughout the execution, my arraylist for collisions is refreshed each step, but I've got a LinkedList of forces that may arbitrarily change throughout the execution.

I don't care if it's inefficient, you need to stop shitting yourself over efficiency and get something done.

[qwertyuiopas]

From the discussions here, this is what I think would work the fastest(likely a few false assumptions, invalidating the whole thing):

Assume that there will never be more than 65535 objects (and one null value). This allows the use of a 16 bit index rather than a 32 or 64 bit pointer, allowing 2-4 times as many in each cache entry, reducing cache misses.

Furthermore, allocate the entire array once, to eliminate the reallocation penalty.

Get the individual object size as small as possible, but able to fit an integer number of them exactly in a cache entry.

Store the objects in an array, fully preallocated, or in a series of fixed-size arrays that are allocated as needed and never freed (with an array of pointers to them, null until allocated).

Each object would contain two indexes, so that they form two doubly-linked lists, one of empty objects and one of used objects. The last used object should be followed by an empty object with a null index as it's next, to signify that all of the remaining objects are empty.


That way, adding a new object is usually as simple as a removal from a doubly linked list (constant time), an insertion into a doubly linked list (again, constant time), and object initialization. Removing an object takes just as long, minus the initialization. Depending on size, a new array may have to be allocated occsionally, but since it would be a separate array, no copying of data would be nessecary.

User data would be stored as a single void*, to fit as many objects into the cache as possible, and give the objects a fixed size.



Finally, don't even bother with something like this, find an adequate third-party library and focus on the impostant part: YOUR code. It is likely that an existing physics library is highly optimized, and you will probably spend days debugging physics math before you can even approach a sufficient setup to do everything you want it to.

Spend an hour on wikipedia, starting at http://en.wikipedia.org/wiki/Physics_engine#Engines, and you will have better results, sooner.

[Supermikhail]

First off, I didn't come begging here, at least not over lists. I think the discussion of lists started because of my explanation of my previous misconceptions, which was aggravated by new misconceptions. I'm just a bit more than curious why the creators of the library I'm using as an example use the kind of array they use, while my experience (which with Java started very recently and, I must admit, without a proper theoretical backing) tells me to use another kind. I'm glad that people here feel interested in helping me. But possibly I would have been better off without their help, getting more stuff done like eerr said. That is, not. I would have googled restlessly on and on and surfed the API reference because of our dissent with the library's creators. But I feel this last bit of the discussion has solved it for me, especially with Siquo's post. Although I won't deny that Blank Expression prompted me to finally find out what exactly O estimates mean.

Thanks, guys!

e: @qwertyuiopas, the first suggestion looks too complex and time-consuming to use together with actually getting shit done. The second (about a third-party library)... well, I've already done some work on my own engine. I'll at least try to give it some UI to see if it fails entirely.