Topic: RE: Models, screenshots, etc... in Developers' Discussion

[Recon]

Hi,
  Was reading the post http://forums.g33xnexus.com/index.php/topic,639.0.html in the developer discussion forum and though I should let you know what I am up to. I am still very green using C++ and wanted to do something that I found both interesting and useful that could help Precursors.

  Having read the forums and the development WiKi I thought that making a procedural solor system generator would be a good goal as it's not scheduled anywhere and seem a relativity simple piece of coding. Now I cant guaranty I will manage to make this or if it will be any good but I going to give it a try anyway. If I get to a stage where I feel it might be useful I will let you know.

  So, on to some details. I did a few test first just trying to mock up a solar system and immediately had problems with scale. I found that a lot of things stopped working as expected when the position of a mesh was greater than 100,000 from the 0,0,0 position, both lighting and collision detection seem to stop working. ( example world file at
http://www.uploading.com/files/Z38R0FY5/world.zip.html ).

  This world file is quite simple, has 2 camera positions , one near 0,0,0 and one near 100000,0,0 . and a couple of meshes, start walktest at the 0,0,0 position and it works , at the other position nothing is visible and you fall through meshes. So some method of getting around this will be required and I have not thought of one yet.

  So, I decided to continue anyway as generating a solar system to a smaller scale is still useful. Plan to create a class that will generate suns/planest/moons ect using a seed for each solar system and a simple rule base ( something like http://www.geocities.com/TimesSquare/2691/formula.txt ). Plan to shameless use the textures from Celestia for graphics and give each object a orbit and other information. I think that doing all this client side rather that server side is the best approach and using server system time to keep everything synchronised for different clients. (ie when a client logs onto a server, the server gives the client the current server system time, the client then used this to calculate all positions.)

  It's slow going but my C++ is improving the more I use it. And if I can manage to generate a simple solar system with orbits and graphics in Crystal Space I feel I will have managed to achieve something useful.

Regards

[whitelynx]

Hard to believe none of us have replied to this post yet... we've been talking about it a lot. :P

It would be great to see you working on a solar system generator, since that's one of the big parts missing from a playability standpoint right now.

As far as scale, that is an inherent problem with Crystal Space. It uses the C++ 'float' type for coordinates, which becomes extremely inaccurate past a certain point. (at something a good bit less than 1000000000, you lose all decimal places and have to deal with integer precision or worse) There are two ways to solve this in CS, each of which has some pros and some cons.

The first way involves splitting the space up into sectors. This works fine on a small scale, but sectors are a technique that is generally more geared toward "indoor" scenes. Basically, you'd have a cube (the current sector) with 6 faces, each of which would be a "portal" to another sector. The reason that this fixes the float issue is that each sector would be based around the origin (0,0,0) and each portal would "warp" back to the other side of the next sector so that you never get further away from the origin than the size of a sector.

The problem with the first solution is that we have to split up space into a large number of sectors, and it gets rather difficult to track what is in which sector. Also, either we have to have a huge amount of separate sectors (so the size is relatively small) or else we'll still run into some jitter near the edges of a sector.

The second solution is to put the player's ship (or character, or whatever) at the origin and translate the rest of the world to be correctly positioned around it. This is a great solution and lends itself well to deep space scenes, because once something is far enough away to cause jitter, the jitter will be small enough and far enough away that you won't notice it.

The problem with this solution is physics. ODE (and the CS physics system in general) tries to move each object around... somehow we have to then translate everything into ship-space coordinates for the renderer. It would be good to do some tests to see how well this method works with physics and whether we can adapt it to work on a large scale. If we can get past the problems with physics integration, this may well be our best solution.

As far as your ideas on seed-based system generation, that looks pretty promising! I'm not sure about using the stuff from Celestia (we'll have to check their license before you commit any of that to the repository) I have some mixed feelings as far as doing the calculations client-side. I think they should definitely be done on the client to improve speed and response, but the server needs to send updates to the clients every once in a while, and even more often if the given object goes outside of its "predicted" path for some reason. (like being rammed by a large ship or something) Keep in mind that regardless of how much of the calculation is done on the client, the server will need to have the final say on anything that affects actual gameplay.

I'd like to set up an account for you on our subversion repository so that you can commit your code there and we can help you out with it. We'll give you a sandbox directory in the repository, and I'll contact you over PM on the forums to get your login information.

Thanks for working on this! It's encouraging to see some other people getting interested in coding for Precursors.

[contingencyplan]

Hard to believe none of us have replied to this post yet... we've been talking about it a lot. :P

Well, I was mainly gonna have us talk about it with him directly before doing anything, but posting first works too :P

It would be great to see you working on a solar system generator, since that's one of the big parts missing from a playability standpoint right now.

As far as scale, that is an inherent problem with Crystal Space. It uses the C++ 'float' type for coordinates, which becomes extremely inaccurate past a certain point. (at something a good bit less than 1000000000, you lose all decimal places and have to deal with integer precision or worse) There are two ways to solve this in CS, each of which has some pros and some cons.

First off, is there no way we can just create a new coordinates class that does doubles (maybe long doubles) instead of floats? Would doing this fix our problem?

The first way involves splitting the space up into sectors. This works fine on a small scale, but sectors are a technique that is generally more geared toward "indoor" scenes. Basically, you'd have a cube (the current sector) with 6 faces, each of which would be a "portal" to another sector. The reason that this fixes the float issue is that each sector would be based around the origin (0,0,0) and each portal would "warp" back to the other side of the next sector so that you never get further away from the origin than the size of a sector.

The problem with the first solution is that we have to split up space into a large number of sectors, and it gets rather difficult to track what is in which sector. Also, either we have to have a huge amount of separate sectors (so the size is relatively small) or else we'll still run into some jitter near the edges of a sector.

Another problem with sectors is having to transition the origin seamlessly. Loading zones are anathema to this game - we *will not* have them (I'm sure that morgul and whitelynx already decided this, but I'm making it emphatic, if not official ). This in turn means that things can happen on the edges of sectors (space battles and dogfights, for example). These, in turn, likely will go between the sector edges frequently, causing the coordinates to have to be recalculated a BUNCH of times. Inefficient.

The second solution is to put the player's ship (or character, or whatever) at the origin and translate the rest of the world to be correctly positioned around it. This is a great solution and lends itself well to deep space scenes, because once something is far enough away to cause jitter, the jitter will be small enough and far enough away that you won't notice it.

The problem with this solution is physics. ODE (and the CS physics system in general) tries to move each object around... somehow we have to then translate everything into ship-space coordinates for the renderer. It would be good to do some tests to see how well this method works with physics and whether we can adapt it to work on a large scale. If we can get past the problems with physics integration, this may well be our best solution.

Sounds like this would still require an absolute coordinate system, rather than having everything relative to a moving object. Could you elaborate more on this, probably in another thread?

As far as your ideas on seed-based system generation, that looks pretty promising! I'm not sure about using the stuff from Celestia (we'll have to check their license before you commit any of that to the repository) I have some mixed feelings as far as doing the calculations client-side. I think they should definitely be done on the client to improve speed and response, but the server needs to send updates to the clients every once in a while, and even more often if the given object goes outside of its "predicted" path for some reason. (like being rammed by a large ship or something) Keep in mind that regardless of how much of the calculation is done on the client, the server will need to have the final say on anything that affects actual gameplay.

I'd like to set up an account for you on our subversion repository so that you can commit your code there and we can help you out with it. We'll give you a sandbox directory in the repository, and I'll contact you over PM on the forums to get your login information.

Thanks for working on this! It's encouraging to see some other people getting interested in coding for Precursors.

Back to the main point of the post: I heartily agree with whitelynx's last statement. As time goes on, I'm looking forward to working with more than just 2 people (mainly one, since morgul is more a manager than a codester). Like I've said in other posts, I have mad C++ skillz, so *please* contact me directly or via the forums with any programming questions you have. I'll also check in on your little playground area in the repository to see how / what you're up to, and make suggestions as I'm able (if that's alright with you, of course).

Also, we've discussed this, so I may as well make it official: if you can succeed at this, or at least demonstrate a significant effort, then we'll be more than happy to make you a full dev on the team. No, mad C++ skillz are not a "must-have" - we'll teach you what you need to know.

[Morgul]

How about a type that can contain an arbitrary number of digits? How about one with an optimised implementation? I happen to know where to get one.

A few years ago, I helped a friend write an RBI class, "Really Big Integer". We needed it for cryptographics purposes.. even long is MUCH to small for a really secure crypto system. He's been tweaking it over the years; Yes, it is only an integer, but it's an integer of theoretically infinite length. I'm sure we could easily represent 10^300th. Now, consider, the galaxy is only 9.4605284 x 10^29 nanometers, so I think we'd be fine without floats. We'd have to do a custom thing for CS, but I think they might go for it.

Oh, I can also say that our implementation is actioly about 2x as fast as python's interpreter's implementation. (My firend looked up how they do arbitrary length ints in python.. they use our method, but it' a bit inefficient.)

I think this is a computer science problem waiting for a computer scientist to answer.

[contingencyplan]

Heh - Dr. Desrosiers had us to a similar project, HugeInt, to teach us operator overloading. I'm sure, especially since your friend has been working on it for a while now, that y'all's is a much better system overall. I'm very interested to see this.

The main question is whether we want to represent everything in nanometers (would require a very large number to do anything significant), or treat it as a fixed point (like .NET's System.Decimal type). Personally, I'd like the latter better, so we aren't having to deal in such large numbers (both conceptually and realistically). Talk to your friend and see how easily one could convert his implementation to also do fixed point arithmetic, if you could.

How soon can we get a hold of the library to start looking through it?

[Morgul]

Well, I've got an old version kicking around somewhere. I'll talk to him tonight, and see if I can get him to send me the latest greatest version.

I only mention nanometers for the simple fact that it's an absurdly small number. Then again, it's small enough that we could do some Shit Fuck Magic (tm) and have it appear like a float but really be an RBI measuring in nanometers. As for fixed point, it shouldn't be too hard.. he might already have that in there. I know he's got integer arithmetic... and it's not too far a leap to fixed point.

One concern I have is that most of his work recently has been on a port to Pic ASM he did of this code. He's planning on back porting his work, but I don't know what stage the c++ lib is at with the back port. If he tells me what needs doing, I can actually back port it for him... and possibly even add fixed point arithmetic too. We'll see.

[contingencyplan]

Kickass. I'm up for working on that if need be - it doesn't sound too difficult, and something that we can play around with SFM optimizations, too.

Template metaprogramming, for example. ;D

[Morgul]

[...]Template metaprogramming, for example. ;D

Say what? *blinks* I'm a fomer CS major, and I swear that's in wookie, or twi'lek, or something.

[contingencyplan]

If you're joking - "haha".

If you're serious (i.e., never heard of "template metaprogramming")...... 

Wait till you see RaptorNL when I'm finished. 8)

Remember: I can do things with C++ nobody should be able to do.

(This, and the possibility of using SequenceL for writing the generation algorithms is one of the main reasons I wish Recon would get back to me on the double... :-\)

[whitelynx]

Ok, as far as really big numbers...

First off, there's next to no chance of us getting CS to change the coordinate system used in the base libraries. (especially the renderer) If nothing else, it would require hardware support on the video card end, and that's something that just won't happen.

However, if we took my second suggestion (the rendered area of the world being centered around the player or camera) and then used an RBI/RBF implementation as our "universal" coordinates but converted back into float when doing rendering and localized stuff like physics, then it would probably work pretty well.

Now... as far as getting decimals out of RBI. I think the best way might be to store an exponent, which should only need 8 bits or so (that's all that's used in float) and then use RBI as the mantissa. (or, technically, "significand") If we use all 8 bits of the exponent as denoting a negative exponent, this gives us quite a bit of precision, and since RBI is the mantissa we won't need the exponent to make bigger numbers. (only smaller) To compute the actual value of a number of this type (let's call it RBF for simplicity) you use the following formula:

Code: [Select]

mantissa * 10^(-exponent)
This gives us a precision of about 10^-256, which means about 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

If that isn't enough precision, then you're too damn picky.

[contingencyplan]

Hrm. This sounds good, but I still want to see the implementation on the RBI / RBF before I can sign off on this. I think this will work, thinking about it, but we'll have to see it in action. And we still have to consider the cost of converting it to a float / double / long double. Likely the latter two - if we convert it to float, we'll still be running into the jitter issue, methinks: the jitter is caused by rounding and lack of precision. It doesn't matter how much precision we have when storing the value in the RBF. What matters is how much precision we have after storing it in memory as a floating point value (not necessarily a float).

Oh, and if we only have 8 bits, then we have a precision of 10 ^ -128 to 10 ^ 127, since we need to account for positve exponents too. But we'll see. I still think doing something of a fixed point implementation might be a better way to go about it, since we can guarantee to have a certain precision about what we're doing.

Morgul, any thoughts on when we can get a hold of the RBI code?

[whitelynx]

Hrm. This sounds good, but I still want to see the implementation on the RBI / RBF before I can sign off on this. I think this will work, thinking about it, but we'll have to see it in action. And we still have to consider the cost of converting it to a float / double / long double. Likely the latter two - if we convert it to float, we'll still be running into the jitter issue, methinks: the jitter is caused by rounding and lack of precision. It doesn't matter how much precision we have when storing the value in the RBF. What matters is how much precision we have after storing it in memory as a floating point value (not necessarily a float).

The issue with floats only arises when the values are relatively far from 0; ie. really big positive or negative numbers. If we're converting into a localized coordinate system (such as one centered around the player) the stuff that's far away doesn't matter because it'd be so small on the screen, so we don't care if it jitters. If it's closer, then it has good precision. Besides, float is all that CS and the hardware understand.

Oh, and if we only have 8 bits, then we have a precision of 10 ^ -128 to 10 ^ 127, since we need to account for positve exponents too. But we'll see. I still think doing something of a fixed point implementation might be a better way to go about it, since we can guarantee to have a certain precision about what we're doing.

Actually, as I said above, we don't need positive exponents at all. RBI will handle that, since we have an effectively infinite range for the mantissa. The only thing we can't do with RBI currently is non-integral values, which is what the exponent would be for.

[contingencyplan]

Hrm. This sounds good, but I still want to see the implementation on the RBI / RBF before I can sign off on this. I think this will work, thinking about it, but we'll have to see it in action. And we still have to consider the cost of converting it to a float / double / long double. Likely the latter two - if we convert it to float, we'll still be running into the jitter issue, methinks: the jitter is caused by rounding and lack of precision. It doesn't matter how much precision we have when storing the value in the RBF. What matters is how much precision we have after storing it in memory as a floating point value (not necessarily a float).

The issue with floats only arises when the values are relatively far from 0; ie. really big positive or negative numbers. If we're converting into a localized coordinate system (such as one centered around the player) the stuff that's far away doesn't matter because it'd be so small on the screen, so we don't care if it jitters. If it's closer, then it has good precision. Besides, float is all that CS and the hardware understand.

They don't even understand double? Honestly, I don't think adding the ability to consider coordinate systems as doubles would be very hard; just have an #ifdef to switch between them.

Oh, and if we only have 8 bits, then we have a precision of 10 ^ -128 to 10 ^ 127, since we need to account for positve exponents too. But we'll see. I still think doing something of a fixed point implementation might be a better way to go about it, since we can guarantee to have a certain precision about what we're doing.

Actually, as I said above, we don't need positive exponents at all. RBI will handle that, since we have an effectively infinite range for the mantissa. The only thing we can't do with RBI currently is non-integral values, which is what the exponent would be for.

Ah, missed that part, sorry. Yeah, that should work then. Like I said, my main other concern is speed of conversion between these formats, especially if we're doing such conversions frequently (I'd suspect we'd be doing them numerous times per second, especially when there's a BUNCH of stuff on the screen [e.g., major battles]).

[whitelynx]

They don't even understand double? Honestly, I don't think adding the ability to consider coordinate systems as doubles would be very hard; just have an #ifdef to switch between them.

They have support for double in certain classes (see http://crystalspace3d.org/docs/online/api/group__geom__utils.php) but those classes aren't used in most of the engine proper, and we'd probably have a tough time convincing them that there was a need for #defines like that... There doesn't seem to be an option in configure to enable it currently.

After talking to the devs, they agree that there should be some work put into getting a better coord system into CS, but thebolt says that double probably isn't the way to go... Even if we did use double, it wouldn't solve much... it is still as non-linear as float is, as far as precision; it just wouldn't start to show the jitter as soon. (see http://home.comcast.net/~tom_forsyth/blog.wiki.html#%5B%5BA%20matter%20of%20precision%5D%5D for more info, and check out the OffendOMatic while you're there)

Ah, missed that part, sorry. Yeah, that should work then. Like I said, my main other concern is speed of conversion between these formats, especially if we're doing such conversions frequently (I'd suspect we'd be doing them numerous times per second, especially when there's a BUNCH of stuff on the screen [e.g., major battles]).

That is a valid concern... I'm tempted to simply go for a fixed-point implementation where the rightmost n digits of the RBI are beyond the decimal point (multiply the RBI by 10^-n) since it would simplify calculations and still give us a usable infinite coordinate system. (as long as we ignore the performance impact of extremely large numbers)

Of course, there's still other solutions we can explore... we could go with a paged memory-influenced algorithm, where we have a "sector" we specify with an int 3-vector, (so we basically have a 3D grid of sectors, kinda like a rubiks cube) and then float coords within that. The size of the sectors would depend on how much distance we can squeeze out before it gets jittery. Of course, this then brings up the question of what to do when we approach boundaries... my instinctual solution in this case would be to simply use sectors and portals, since that's what they're made for. :P

Edit: After reading up on that Tom Forsyth page, I'm starting to think a straight 64-bit int might be the best way to go... as he says, using a 64-bit int as a fixed-point number "gets you to the furthest distance of Pluto from the Sun (7.4 billion km) with sub-micrometer precision." That should be enough for in-system coords at least...

What do you guys think?

[contingencyplan]

I'm gonna look at some fixed-point implementations online, see if we find any of interest.

DDJ article on a fixed point implementation: http://www.ddj.com/dept/cpp/193200474
The implementation described: http://www.mentor.com/products/c%2Dbased%5Fdesign/

Freaking long article on rounding algorithms: http://www.diycalculator.com/sp-round.shtml

(For those who don't know, DDJ is Dr. Dobb's Journal, a kickass publication for programmers. I'm going to be renewing my subscription soon, since the CS dept stopped having the free mag handouts a while back. I'd strongly recommend that everyone here subscribe - not every article is for you, but you oftentimes learn something new from reading through them.)