User Name
Password

Go Back   Planetarion Forums > Non Planetarion Discussions > Programming and Discussion

Reply
Thread Tools Display Modes
Unread 20 May 2003, 16:16   #1
Structural Integrity
Rawr rawr
 
Structural Integrity's Avatar
 
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
Structural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriend
I need a starmap creation algorithm

As the title says, I need an algorithm which positions planets on a 2D starmap.

There are a few requirements:

- each planet on the map has AT LEAST 3 neighboring planets in a radius R
- each planet on the map MAXIMALLY has 5 neighboring planets in a radius R
- the final amount of planets (FINAL_PLANETS) should be predetermined



This is how far I got:

- Randomly position a number of planets on the map (10 times the required amount of end planets or so)

- Loop while there are still planets that don't fit the first two requirements

- Randomly select a planet (P)
- Loop through all planets and see if it's in radius R from (P)
- if the amount of planets in radius R does not fit the first two requirements, then delete (P)





Problems:

How do I make sure I can determine the amount of planets that will remain on the map?

How do I optimise this monster? Looping through 5000 planets and checking it against 5000 other planets is NOT FUNNY!

How do I determine the physical size of the starmap from the radius R and the required amount of end planets?

How do I accurately determine how many random planets I have to place? FINAL_PLANETS*10 is not very accurate.
Structural Integrity is offline   Reply With Quote
Unread 20 May 2003, 16:17   #2
BesigedB
Darling
 
BesigedB's Avatar
 
Join Date: Dec 2000
Location: Edinburgh
Posts: 890
BesigedB is a glorious beacon of lightBesigedB is a glorious beacon of lightBesigedB is a glorious beacon of lightBesigedB is a glorious beacon of lightBesigedB is a glorious beacon of light
p+it?
__________________
..
BesigedB is offline   Reply With Quote
Unread 20 May 2003, 16:23   #3
Mong
Forever Delayed
 
Join Date: Sep 2000
Location: www.netgamers.org
Posts: 1,475
Mong is on a distinguished road
Quote:
Originally posted by BesigedB
p+it?
Indeed. MOD!

M.
__________________
Firefly Oper and General l4m3r - "I Do Stuff"

O2 Rip-off campaign

<vampy> plus i hate people ... i despise humanity as a whole

pablissimo "I'm still geting over the fact you just posted a pic of your own vomit"
Mong is offline   Reply With Quote
Unread 20 May 2003, 16:45   #4
W
Gubbish
 
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
W is a jewel in the roughW is a jewel in the roughW is a jewel in the rough
I have one already, but I'm not gonna sell it cheap, it's gonna be used in my own game once I have the time to finnish it.

It's O(N) time to determine the position of N stars, and it's online, so you effective have an infinite non-repeating map.
__________________
Gubble gubble gubble gubble
W is offline   Reply With Quote
Unread 20 May 2003, 21:11   #5
Cyp
∞+♪˛
 
Join Date: Nov 2000
Location: :uo!te]oŻ|
Posts: 428
Cyp is an unknown quantity at this point
Might help a bit:

Place all the planets, divide into a grid.

Give each planet an array with pointers to all other planets within radius r, checking to see if planets in the same part of the grid are within the radius, to save time. Then forget the grid. Ignore the position of the planets from now on.

Discard all planets with not enough neighbours.

Remove planets with too many neighbours, which have neighbours with lots of neighbours. Check that all neighbours have enough neigbours afterwards, if not, remove them, and check the neighbours neighbours, and so on.

Once all planets have the right number of neighbours, keep removing planets until you have the right number of planets. Careful not to remove planets which will result in needing to remove too many planets, when close to the desired planet count.


Haven't actually tested if any of that is sensible, so no guarantees. Probably better ways of doing it.
__________________
Structural Integrity for Creator - since he'll probably make PA turn 3D.
Wikipedia forum
Note to self - Don't write Chinese letters with bold and italics...
<!--Last incarnation: Nov 2000-->
Cyp is offline   Reply With Quote
Unread 20 May 2003, 22:20   #6
pablissimo
Henry Kelly
 
pablissimo's Avatar
 
Join Date: Apr 2000
Posts: 7,374
pablissimo has ascended to a higher existance and no longer needs rep points to prove the size of his e-penis.pablissimo has ascended to a higher existance and no longer needs rep points to prove the size of his e-penis.pablissimo has ascended to a higher existance and no longer needs rep points to prove the size of his e-penis.pablissimo has ascended to a higher existance and no longer needs rep points to prove the size of his e-penis.pablissimo has ascended to a higher existance and no longer needs rep points to prove the size of his e-penis.pablissimo has ascended to a higher existance and no longer needs rep points to prove the size of his e-penis.pablissimo has ascended to a higher existance and no longer needs rep points to prove the size of his e-penis.pablissimo has ascended to a higher existance and no longer needs rep points to prove the size of his e-penis.pablissimo has ascended to a higher existance and no longer needs rep points to prove the size of his e-penis.pablissimo has ascended to a higher existance and no longer needs rep points to prove the size of his e-penis.pablissimo has ascended to a higher existance and no longer needs rep points to prove the size of his e-penis.
Surely you could use some kind of modified BSP tree to avoid checking all the planets positions against every other planet, that should cut down on the amount of search you're looking at...

I thought I had a little algorithm going for a minute there but I just broke it, so I'll keep a-thinking
__________________
You're now playing ketchup
pablissimo is offline   Reply With Quote
Unread 20 May 2003, 22:21   #7
queball
Ball
 
queball's Avatar
 
Join Date: Oct 2001
Posts: 4,410
queball contributes so much and asks for so littlequeball contributes so much and asks for so littlequeball contributes so much and asks for so littlequeball contributes so much and asks for so littlequeball contributes so much and asks for so littlequeball contributes so much and asks for so littlequeball contributes so much and asks for so littlequeball contributes so much and asks for so littlequeball contributes so much and asks for so littlequeball contributes so much and asks for so littlequeball contributes so much and asks for so little
Plenty of algorithms meet those requirements. For instance, a triangular ("isomorphic"?) pattern with the occasional planet removed to bring the valencies down to 5 (with planets seperated by anything from r/2 to r) should fit your requirements. Maybe you want something like "it should look good" or "it should be a random choice from all solutions" in your spec.
queball is offline   Reply With Quote
Unread 20 May 2003, 22:34   #8
W
Gubbish
 
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
W is a jewel in the roughW is a jewel in the roughW is a jewel in the rough
nonono, you're all doing it so overly complicated. This isn't an algorithm issue, this is a maths issue. There are nice mathematical functions which give distributions that fits these criteria easilly and proveably, for an infinite domain. No loops needed. Little code beyond the expression of the function.
__________________
Gubble gubble gubble gubble
W is offline   Reply With Quote
Unread 21 May 2003, 09:31   #9
Cyp
∞+♪˛
 
Join Date: Nov 2000
Location: :uo!te]oŻ|
Posts: 428
Cyp is an unknown quantity at this point
Quote:
Originally posted by W
nonono, you're all doing it so overly complicated. This isn't an algorithm issue, this is a maths issue. There are nice mathematical functions which give distributions that fits these criteria easilly and proveably, for an infinite domain. No loops needed. Little code beyond the expression of the function.
Mind saying the name, or giving the equation, of such a function?
__________________
Structural Integrity for Creator - since he'll probably make PA turn 3D.
Wikipedia forum
Note to self - Don't write Chinese letters with bold and italics...
<!--Last incarnation: Nov 2000-->
Cyp is offline   Reply With Quote
Unread 21 May 2003, 15:02   #10
W
Gubbish
 
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
W is a jewel in the roughW is a jewel in the roughW is a jewel in the rough
Quote:
Originally posted by Cyp
Mind saying the name, or giving the equation, of such a function?
"W's star hash"? I dunno what to call it. It's not trivial, but the entire aproach of generating something by random, then checking the constraints seems entirely flawed to me. Random in a computer is always pseudorandom anyway, and you might as well simply choose a pseudorandom function that fits your criteria.
Code:
a=10
do while a>5
a=int(rnd*10+1)
loop
print "A random number from 1 to 5"
__________________
Gubble gubble gubble gubble
W is offline   Reply With Quote
Unread 21 May 2003, 15:23   #11
Structural Integrity
Rawr rawr
 
Structural Integrity's Avatar
 
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
Structural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriend
I guess it could be done in another way too... I can't think of a mathematical way tho, so if you can give me a little hint I can look it up.

Anyway, another way would be to do it recursive:

- place planet (CENTER) in center of universe

- randomly position 4 planets around it with a minimum distance of 0.5*R

- For each planet (P) created, create two new planets (A) & (B).
- the distance between (A) or (B) and (P) is atleast 0.5*R and maximal 1*R
- the distance between (A) or (B) and (CENTER) is BIGGER than the distance between (A) or (B) and (P). (thus working outwards)



Well W, I'd like to hear what your idea is of how to do this most effectively.
Structural Integrity is offline   Reply With Quote
Unread 21 May 2003, 21:58   #12
Cyp
∞+♪˛
 
Join Date: Nov 2000
Location: :uo!te]oŻ|
Posts: 428
Cyp is an unknown quantity at this point
Of course, it would be possible to divide it into boxes, put a set number of planets into each box, and have planets near the edge of the boxes take neighbouring boxes' planets into account, and move to a suitable position to fit the requirements. Would be possible to do an infinite map that way, but I think the pattern would be noticable over a large enough area.
__________________
Structural Integrity for Creator - since he'll probably make PA turn 3D.
Wikipedia forum
Note to self - Don't write Chinese letters with bold and italics...
<!--Last incarnation: Nov 2000-->
Cyp is offline   Reply With Quote
Unread 21 May 2003, 23:40   #13
W
Gubbish
 
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
W is a jewel in the roughW is a jewel in the roughW is a jewel in the rough
Quote:
Originally posted by Cyp
Of course, it would be possible to divide it into boxes, put a set number of planets into each box, and have planets near the edge of the boxes take neighbouring boxes' planets into account, and move to a suitable position to fit the requirements. Would be possible to do an infinite map that way, but I think the pattern would be noticable over a large enough area.
Still too complex. Ideally, you'd want a function that gives the position of a star with no other input than one or more iterators.

Examine this problem in 1d. You have a string, and want pebbles randomly placed on it, so that each pebble has exactly two neighbours within unit distance, and where the distribution of the distances between neighbouring pebbles is something like f(x) proportional to 0.25-|x-0.75| where this is >0 and 0 elsewhere. You can then simply say that the position of star number n is 0.75*n+0.25*hash(n), and depending on your hashing function, might get to simplify even more. True, there's a pattern, but more likely than not, that's a beneficial side effect, instead of an unwanted one. Say if you have a pebblespace game, then the pebble density is more fixed, making the game more even for everyone. The alternative is either to work some horribly advanced math to come up with a hash that fits the criteria exactly (still possible, my solution is just the simplest one, using any standard [0,1> hash)), or accept that the distance between pebbles might be smaller, even close to 0. Or examine the neighbours of course, tho that increases drastically in complexity for more than one dimension.
__________________
Gubble gubble gubble gubble
W is offline   Reply With Quote
Unread 23 May 2003, 01:15   #14
hyfe
Dum Di Dum Di
 
Join Date: Sep 2001
Posts: 858
hyfe is a pillar of this Internet societyhyfe is a pillar of this Internet societyhyfe is a pillar of this Internet societyhyfe is a pillar of this Internet societyhyfe is a pillar of this Internet societyhyfe is a pillar of this Internet societyhyfe is a pillar of this Internet societyhyfe is a pillar of this Internet societyhyfe is a pillar of this Internet societyhyfe is a pillar of this Internet societyhyfe is a pillar of this Internet society
My 2 cents:

As W said; its pretty self-evident thats it easier to do this creation time instead of trying to fix it afterwards... However; if those 5.planets near enough are *requirements* I think your best shot is to tweak the planet generation routine to the max; and just do nasty evil checking afterwards.....

On the other hand; It might be prudent keeping some sort of map, or sectors.. So if you want to get positions of all nearby stars, you just check which are stored in this sector (and nearby sectors if close to the border) instead of checking *all* the planets. Most speed optimization comes at the cost of extra memory usage; if you want things scalable, its a cave-eat you're going to have to take take...

However.. When you're trying to work out the formula: there are a couple of other questions that pops up:
Is large clusterings of planets a good thing?
Or should the universe be quite even?
Is it ok if the planets are closer to each other in the middle? or not?

On the spot.. I can come up with a couple methods for placement: (totally ****e ones though)
1. Using length away from the middle and direction... place one planet in each direction, do some randomization... planets *will* be closer in the middle though.. (unless you factor in more maths (cba myself))
Code:
TotalSize = something;
For planet_nr in 1 to (maxplanet/16)
  For X in {0,90,180,260}
    For Y in {0,90,180,260}
       X-Angle = X + rnd * 90
       y-Angle = Y + end *90
       distance = TotalSize*planet_nr / (maxplanet/16) * (0.9 + 0.2*rnd)
    next y
 next x
next planet_nr
Or.. if you want a really nice semi-random even distribution.. Do some sort of gravitational thingie.. (ie; each time you add a planet; modify the chances of other planets chances appearing near it.. ( fx.. keep a single number for each chance, and then modify all the 9 * 9 single numbers around a planet when you add it (drastically lower the near ones, and maybe increase the ones at optimum distance chances a little).. By doing a little smart programming, it actually won't be as some slow at you'd initially think ...

Or.. do a branch thingie... From each planet made, you make 2/3/4 new planets.. when making a new planet, just try a random direction and a random distance (tweakable by you), check the near surroundings of the new planet your attempting to create; is it to near to something else? trash it!







ohh... long post.. totally off-track.. and i don't even know what i'm talking about
__________________
Ni! M00!
my boring homepage
hyfe is offline   Reply With Quote
Unread 25 May 2003, 21:29   #15
Structural Integrity
Rawr rawr
 
Structural Integrity's Avatar
 
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
Structural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriendStructural Integrity needs a job and a girlfriend
Quote:
Originally posted by hyfe
Or.. if you want a really nice semi-random even distribution.. Do some sort of gravitational thingie.. (ie; each time you add a planet; modify the chances of other planets chances appearing near it.. ( fx.. keep a single number for each chance, and then modify all the 9 * 9 single numbers around a planet when you add it (drastically lower the near ones, and maybe increase the ones at optimum distance chances a little).. By doing a little smart programming, it actually won't be as some slow at you'd initially think ...

Or.. do a branch thingie... From each planet made, you make 2/3/4 new planets.. when making a new planet, just try a random direction and a random distance (tweakable by you), check the near surroundings of the new planet your attempting to create; is it to near to something else? trash it!
ooooh.... the last two ideas are rather nice.
Create a gridlike universe and then randomise the positions a bit. Enough to make it look random, but with keeping planets in a specified distance. That could be rather fast even and when using a triangle-grid for example you can fullfill the requirements.

Or the tree thingy... that could work too, but checking it for neighboring planets would be intensive.

Anyway, W is right. I can better solve this problem when creating the map then to make the map fit the requirements afterwards.

I think I'll start prototyping this stuff this week. Didn't have much time on my hands last week.

TY
Structural Integrity is offline   Reply With Quote
Reply


Thread Tools
Display Modes

Forum Jump


All times are GMT +1. The time now is 16:54.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright ©2002 - 2018