|
20 May 2003, 16:16
|
#1
|
Rawr rawr
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
|
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.
|
|
|
20 May 2003, 16:17
|
#2
|
Darling
Join Date: Dec 2000
Location: Edinburgh
Posts: 890
|
p+it?
|
|
|
20 May 2003, 16:23
|
#3
|
Forever Delayed
Join Date: Sep 2000
Location: www.netgamers.org
Posts: 1,475
|
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"
|
|
|
20 May 2003, 16:45
|
#4
|
Gubbish
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
|
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
|
|
|
20 May 2003, 21:11
|
#5
|
∞+♪˛
Join Date: Nov 2000
Location: :uo!te]oŻ|
Posts: 428
|
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-->
|
|
|
20 May 2003, 22:20
|
#6
|
Henry Kelly
Join Date: Apr 2000
Posts: 7,374
|
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
|
|
|
20 May 2003, 22:21
|
#7
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
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.
|
|
|
20 May 2003, 22:34
|
#8
|
Gubbish
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
|
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
|
|
|
21 May 2003, 09:31
|
#9
|
∞+♪˛
Join Date: Nov 2000
Location: :uo!te]oŻ|
Posts: 428
|
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-->
|
|
|
21 May 2003, 15:02
|
#10
|
Gubbish
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
|
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
|
|
|
21 May 2003, 15:23
|
#11
|
Rawr rawr
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
|
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.
|
|
|
21 May 2003, 21:58
|
#12
|
∞+♪˛
Join Date: Nov 2000
Location: :uo!te]oŻ|
Posts: 428
|
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-->
|
|
|
21 May 2003, 23:40
|
#13
|
Gubbish
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
|
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
|
|
|
23 May 2003, 01:15
|
#14
|
Dum Di Dum Di
Join Date: Sep 2001
Posts: 858
|
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
|
|
|
25 May 2003, 21:29
|
#15
|
Rawr rawr
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
|
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
|
|
|
Thread Tools |
|
Display Modes |
Linear Mode
|
|
All times are GMT +1. The time now is 16:54.
| |