Project Orbiter Galaxy

[jedidia]

Solved that one, now it seems I'm running into trouble with the random number generator (default srand). I have to keep a bit of a tighter ship now and reinitialise more often, since the goal is to enable generation of selective stars. Luckily I had this prepared beforehand already, every star has its own seed.

but it doesn't really look that way. Indeed, the cubes form earily regular geometric shapes, which seems mostly due to the random numbers generatoed for the stars being awfully close to each other. Here's an example:

Stars with the seed 36123393112042 to ...48 get the following values for their x positions:

1.8239387
-4.8962369
-1.6161077
1.6643269
-4.9444561
-1.7754143
1.5047151

So far nothing special, but stars with the seed 36123393113042 to ...48 get very similiar values:

1.9771416
-4.743044
-1.4625995
1.8175298
-4.9023409
-1.622213
1.6579180

(All numbers are supposed to be between -5 and 5). I assume a possible cause of this is that srand should be seeded with an integer, and I guess it mangles the double I pass it. Still that doesn't explain why the sequence is so similiar but still not the same. The stars in the cubes form rather accurate diagonal patterns that are aligned with each other along each axis (i.e. you can see lines of stars along the general directions of the x-axis, y-axis and z- axis), see attached screenshot. Honestly I couldn't align them like that if I wanted to, so what on earth is going on here?

 

[Wishbone]

Argh. Please explain your "seed" selection process. The pseudo-random generator should be seeded once and then a sequence of numbers is obtained. If there is weirdness going on, search the net for Marsaglia pRNG, which is better than default generators.

 

[jedidia]

Well, since the process has a lot of entry points, I can't just generate the whole thing from a single seed (In that case, you'd have to scroll through the galaxy, and couldn't convieniently select a position). Instead, every cube has its own seed, and every system within a cube has its own seed... Which means I need a few billion seeds at least. The bug I'm encountering now has been in all along, but hasn't shown itself, because there was another convienient bug in there that made counteracted the other one, although not really in a predictable way. There are probably a lot of duplicates in the current version...

Anyways, I clearly isolated the problem by now. srand takes a long integer, which isn't long enough for my purposes, so I need a random generator that can be seeded with a double, or everything above a certain seed just gets shorted to the maximum length (still doesn't explain the slight deviations, but one thing at a time...). I'll have a look at the one you recommended, thanks!

 

[Wishbone]

An afterthought: there may also be some leftover variables from the previous runs. Worth checking just in case.

 

[jedidia]

I have found a really nifty small generator by Marsaglia (all of three lines big) here, and some further information on it here.

I have also been able to make it work, the ability to work with two seeds provides more than enough possibilities for my needs. However, there's one question left: Since I'm not really much of a programmer and have never bothered with bit-crunching, I don't really know what exactly this thing is doing, nor do I really need to know. However, what I definitaley do need to know is the exact maximum range of this thing, i.e. the highest number it can possibly generate. I'll need that to reliably generate numbers in a defined range. Can anybody tell from my code?

long double NextNumber()
{
    v = 36969*(v & 65535) + (v >> 16);
    u = 18000*(u & 65535) + (u >> 16);
    return (v << 16) + u;
}

u and v are both unsigned int. As far as I know the highest number that can be represented with an unsigned integer is 4,294,967,295, so it would be kind of logical if the maximum result would be twice as big, but I would feel a lot more confident about it if someone could confirm this assumption...

 

[jedidia]

I got the generator framework rewritten and running now and am fully immersed in writing a solution for the long-range pathfinding.

After learning a few ways how not to do it, I'm finally getting something. Results are... erm... shall we say "not quite there yet" (see attached screenshot) :shifty:. They make me feel a bit lost in space :lol:

However, the speed at which this garble is calculated is already very encouraging. Now I only have to find out why on earth that silly code is linking stars so weird...

 

[Wishbone]

Are you using A*? Have you tested the framework on simple mazes?

 

[Linguofreak]

I got the generator framework rewritten and running now and am fully immersed in writing a solution for the long-range pathfinding.

After learning a few ways how not to do it, I'm finally getting something. Results are... erm... shall we say "not quite there yet" (see attached screenshot) :shifty:. They make me feel a bit lost in space :lol:

However, the speed at which this garble is calculated is already very encouraging. Now I only have to find out why on earth that silly code is linking stars so weird...

Wait, what exactly is wrong? Is that supposed to be a shortest path between two stars?

 

[jedidia]

Wait, what exactly is wrong? Is that supposed to be a shortest path between two stars?

Don't worry, it was only the first run of the new algorithm. I could trace the source of that weird outcome pretty fast to a simple typo. The algorithm seems to work decently for middle distances, and still has a lot of potential for improvement. For example it currently just stops at the first connection found, which it finds pretty fast, so There's lot of room to expand the search.

The really tough thing will be to expand it for really long ranges more than 40 to 50 parsecs between the origin and the target. The really heavy stars with a lot of jump-range aren't much use, their just too rare to have a high enough probability to make a linking pair. Most of the long range trafic is done between stars between 2 and 5 solar masses, it seems.

Are you using A*? Have you tested the framework on simple mazes?

Nope, because I still don't think it is very practicle for this scenario. giving a cost to the different nodes is pretty tough, because it lies in the actual number of nodes that are needed to form a complete path, and is not inherent in the node itself. And with longer range navigation, we're easily talking 50,000 to 100,000 nodes, and making a graph of them seems just too costly in terms of cpu cycles... If I tried running a BFS with about 30,000 nodes, and that took already about 10 minutes, so the brute-force aproach is pretty much out of the question...

 

[Wishbone]

The algorithm has to be correct, and there's nothing that can beat small test cases for that purpose (validation whether the algorithm works on problems with known answers).

 

[jedidia]

Sorry, I meant "no, I'm not using A*".

 

[Wishbone]

Understood as much, but the comment on testing it in vitro before going to clinical trials stands.

 

[Linguofreak]

Don't worry, it was only the first run of the new algorithm.

I wasn't exactly worrying, I just didn't know quite what was supposed to be happening, so I didn't know exactly how bad it was.

I could trace the source of that weird outcome pretty fast to a simple typo. The algorithm seems to work decently for middle distances, and still has a lot of potential for improvement. For example it currently just stops at the first connection found, which it finds pretty fast, so There's lot of room to expand the search.

The really tough thing will be to expand it for really long ranges more than 40 to 50 parsecs between the origin and the target. The really heavy stars with a lot of jump-range aren't much use, their just too rare to have a high enough probability to make a linking pair.

Well, feel free to tweak the high end of the tables into something that gives better results. I just pulled it off the top of my head anyways.

 

[jedidia]

Understood as much, but the comment on testing it in vitro before going to clinical trials stands.

The problem is that the major challenge of the algorithm is to work in unknown scenarios... When the distance between Origin and target gets larger, there are more and more unknown nodes in between due to the procedural nature. A major part of the whole thing is to decide which ones to create.

Well, feel free to tweak the high end of the tables into something that gives better results. I just pulled it off the top of my head anyways.

We'll take care of that later... The situation won't get much better, though, since no matter the distance, the stars still have to have a somewhat exact distance. Extending the tolerance on the distance for higher mass classes is about the only thing that could help this case.

 

[Linguofreak]

The problem is that the major challenge of the algorithm is to work in unknown scenarios... When the distance between Origin and target gets larger, there are more and more unknown nodes in between due to the procedural nature. A major part of the whole thing is to decide which ones to create.



We'll take care of that later... The situation won't get much better, though, since no matter the distance, the stars still have to have a somewhat exact distance. Extending the tolerance on the distance for higher mass classes is about the only thing that could help this case.

Well, there's a 15% tolerance. And it's not so much a matter of finding a distance to go with a mass range as finding a mass range to go with a distance.

If you'll pass me a recent build of OG I can start experimenting with things myself. (Actually, that assumes you're using config files for the tables. If you've got them hard coded that wouldn't work...)

 

[jedidia]

If you'll pass me a recent build of OG I can start experimenting with things myself. (Actually, that assumes you're using config files for the tables. If you've got them hard coded that wouldn't work...)

You'll get one as soon as I have the algorithm working relyably and more universally, I'll be relying on you to put it through its paces and tweak the jump tables. Tables are standard CSV format, you'll be able to edit them in OpenOffice.

---------- Post added at 10:50 PM ---------- Previous post was at 10:35 AM ----------

Algorithm heavily optimised, with customizable thouroughness. I'm getting quite nice results now after about 15 seconds calculation on my machine with a maximum of 10 generations.

That leaves me with the task to extend the range. Will be another tough modification, but by now I'm pretty confident that I'll get it to work decently...

Another good thing is that the algorithm terminates pretty quickly if it can't find a solution. But I'm afraid that trait won't hold up when I extend the range.

 

[rko1963]

Hi all there,

first of all thanks to You, Jedidia, for that nice addon - its really a fun.....

only, if I am in a different system than sol, neither quicksave, nor "save" function
in scenario editor or strg+q (current state) do work and orbiter ctd´s....
in the save-files only the first eight lines are written, followed by nothing.

Anybody else experienced this problem, or is it up to my installation only
(fresh Orb2010P1 + UCGO2.0 + DGIV2+ OrbSound3.5 + OrbGalaxy&Patch)?
Local Light Sources are off!

If this question is in-appropriate here, please delete....

THX in advance, rko1963

 

[jedidia]

The question is apropriate alright, but you are the first to report the problem, so I have no Idea yet what the cause might be. Two things that might be connected come to mind however, please try them and tell me if it helps:

1. Make sure Orbiter is set to respawn and not to deallocate (Launchpad->Extre->Debugging Options->Orbiter Shutdowon options). If the problem persists, try step 2.

2. See if the trouble happens with other vessels than the DGIV (for example, stock deltaglider). Although I can't quite see how that could be a problem, I never ran it with the DGIV, so it might be worth giving it a try. If the problem still persists after doing both of these steps, I currently have no Idea what might be going on... Other than maybe not enough diskspace available, but that seems ridiculous. On the other hand, the textures generated take up a lot of space, so you never know...

 

[rko1963]

Hi Jedida,

THX for the quick reply.....
Just found out that it was just some stupid setup which comes
along as a standard.....

You must not have any presets for the camera defined !!!
As they reference to System Sol its causes a CTD if You try to
do a Save whilst in another Star-System......

Easy enough, but sometimes one trips over a Tree instead of a matchstick....

so long, rko1963:facepalm:

 

[jedidia]

Connection at home is completely gone these days, so I'm posting a bit unfrequently from an internet cafe...

rko, if I understand that right you have the camera set up to point to a certain body in the solar system at startup? I didn't even know that set-up is possible, I thought camera settings are noted in the scenario file.

However, that seems to be a valuable information, I'll have to put in some saveguards to prevent crashes coming from camera setups.

On another note, the long-range pathfinding is taking on shape. My last attempt resulted in a 2oo lines algorithm from hell, that worked quite decently. There was a slight misplaning in the overall concept, which together with the terrible spaghetti monster it had become was motivation enough to re-write the whole thing. Much more orderly now, and works decently fast. Still has a few hickups and isn't optimised at all, but it's getting there...