Home World Forum
Stars! AutoHost web forums

Jump to Stars! AutoHost


 
 
Home » Stars! 2.6/7 » The Academy » Problem with randomness in planet distrtibution
[LONG] Re: Problem with randomness in planet distrtibution Fri, 12 October 2007 22:54 Go to previous messageGo to next message
ck_drknes is currently offline ck_drknes

 
Crewman 2nd Class

Messages: 17
Registered: May 2007
Location: Why do you want to know?
Hmm... I'm running into a bit of the same problem in my clone (flash AS 3 AIR). It gens pretty fast for flash (10 HW, 1000 planets, 5 sec on a 2ghz) Surprised but the hw distribution seems off Confused . I'm just dividing the screen into equal plots and placing the hw inside them randomly. Sometimes it works out pretty nicely, but other times it looks like there's a lot of unused space in some corner.
Is there a way to maybe "push" the hws into that space? Confused

If you want heres the actual app (also saves the map in uncompressed xml)http://www.chasekernan.com/FlashNova.air

if you don't have AIR its a 9 meg download at http://www.adobe.com/go/getair

and heres the code (very sloppy right now, format is a little screwed up, but it works (I'm hoping there's not a problem with me posting it its a bit long):
/**
		 * Just generates a basic map for now, replacing any planets that are too close.
		 * Dimensions are a vector of width and height
		 * numberOfPlanets is the total number of planets in the map
		 * players is an array of players that should be included on the map
		 * names is the array of names to be used 
		 * germanium is the germanium of all hw (if -1, gens random from between min_hw and max
		 */
		public function generateRectMap(dimensions:Vector, numberOfPlanets:uint, players:Array, names:Array, germanium:int = -1):void
		{
			_objects	=	[];
			
			//check to make sure all obs in races are actually races
			for(var i:int = 0; i < players.length; i++)
			{
				if(!(players[i] is Player)) 
					throw new Error("players must contain all player instances");
			}
			
			//check to make surea all obs in names are strings
			for(i = 0; i < names.length; i++)
			{
				if(!(names[i] is String)) 
					throw new Error("names must contain all strings");
			}
			
			//if germanium is -1, gen random
			if(germanium == -1)	germanium	=	Math.random() * (MineralConcentrations.$MAX_CONC - MineralConcentrations.$MIN_HW_CONC) + MineralConcentrations.$MIN_HW_CONC;
			
			if(germanium < MineralConcentrations.$MIN_HW_CONC || germanium > MineralConcentrations.$MAX_CONC)
				throw new Error("germanium value must fall inbetween the values specified by the MinConcentrations class.");
			
			var sqrtPlanets		:int	=	Math.ceil(Math.sqrt(numberOfPlanets));
			
			var plotSize		:Vector	=	new Vector(dimensions.x / sqrtPlanets, dimensions.y / sqrtPlanets);
			
			var excessPlots	:int	=	int(sqrtPlanets * sqrtPlanets - numberOfPlanets);
			
			//randomize player order
			var newPlayers		:Array	=	[];
			
			for(i = players.length - 1; i >= 0; i--)
			{
				newPlayers.push(players.splice(Math.floor(Math.random() * (players.length - 0.0001)), 1)[0]);
			}
			
			players						=	newPlayers;
			
			//randomize name order
			var newNames		:Array	=	[];
			
			for(i = names.length - 1; i >= 0; i--)
			{
				newNames.push(names.splice(Math.floor(Math.random() * (names.length - 0.0001)), 1)[0]);
			}
			
			names						=	newNames;
			
			//border so planets arn't quite so close to eachother
			var border			:Number	=	0.05 * Math.min(plotSize.x, plotSize.y);
			
			var curPlanet		:int	=	0;
			
			//generic planet var
			var p				:Planet;
			
			//counter
			var j				:int;
			
			var randomIntX		:int;
			var randomIntY		:int;
			//planets to remove:
			var remove			:Array	=	[];
			//setup array
			for(i = 0; i < sqrtPlanets; i++) 
			{
				remove[i]	=	[];
				for(j = 0; j < sqrtPlanets; j++)
				{
					remove[i][j]=	1;
				}
			}
			for(i = 0; i < excessPlots; i++)
			{
				do {
					randomIntX			=	int(Math.random() * (sqrtPlanets - 0.0001));
					randomIntY			=	int(Math.random() * (sqrtPlanets - 0.0001));
				} while (remove[randomIntX][randomIntY] == 0);
				remove[randomIntX][randomIntY] = 0;
			}
			
			
			//create all of the planets
			for(i = 0; i < sqrtPlanets; i++)
			{
				for(j = 0; j < sqrtPlanets; j++)
				{
					if(remove[i][j] == 0) continue;
					
					var xloc	:int	=	i * plotSize.x + border + Math.random() * (plotSize.x - border * 2);
					var yloc	:int	=	j * plotSize.y + borde
...

Report message to a moderator

Re: [LONG] Re: Problem with randomness in planet distrtibution Sat, 13 October 2007 07:58 Go to previous messageGo to next message
m.a@stars is currently offline m.a@stars

 
Commander

Messages: 2765
Registered: October 2004
Location: Third star to the left
Well, that does seem more complex than my own code. Confused

I like the bit where player order is shuffled around. Twisted Evil

One problem I see with your "divide and conquer" strategy for HW placement is that it might create too regular (and predictable) placements. Please correct me if I'm wrong. Sherlock

Otherwise it seems a neat way to speed things up, even if it forces you to search the planet actually nearest to the HW coordinates you chose. Teleport


[Updated on: Sat, 13 October 2007 07:59]




So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Problem with randomness in planet distrtibution Sat, 13 October 2007 17:45 Go to previous messageGo to next message
ck_drknes is currently offline ck_drknes

 
Crewman 2nd Class

Messages: 17
Registered: May 2007
Location: Why do you want to know?
Yeah, I thought it would be too regular but it kinda turns out that its not regular enough. I remove random hw "sections" because not every amount of players is a square number.

So it ends up with little patches where you might expect a hw, but you just get empty planets. Heres a pic:

[img]http://www.chasekernan.com/flashNovaMap1.gif[/img]

(Its a 4000 / 2000 ly universe, the coords are shrunk 4x to get the image. There's 1000 planets and 10 HW)

The shortest distance between hw was around 600 ly, so I think it does fairly well, its just some people seem to have an advantage over others.

Report message to a moderator

Re: [LONG] Re: Problem with randomness in planet distrtibution Sun, 14 October 2007 01:33 Go to previous messageGo to next message
Drakhyulla is currently offline Drakhyulla

 
Crewman 2nd Class

Messages: 16
Registered: December 2006
Location: A crypt near you :)=
Limiting the distribution of planets to the entire shape of the rectangular universe seems to be the problem.

Define planets per race.

Define shape of galaxy race inhabits (square, rectangular,triangular, elliptical, spiral etc...)

Define volume of space occupied by planets.

Place HW in galaxy.

(define, if any, space between galaxies)

Arrange galaxies (perhaps according to predesigned configurations for particular numbers of races)

There could be additional empty galaxies, if they can be placed fairly between galaxies belonging to races.

(You can also imagine wormholes at the centre of galaxies just waiting to whisk you away to other galaxies.)

I think I could live with a 7 race universe such as:

OOOO
OOO

It's still in a rectangular space, so you can travel in the empty block. The bottom three could be shifted a half galactic width to the right without difficulty.

Obviously, there are still problems with this if the galaxies have no space between them and your HW is not centrally placed within your "galaxy".

Drakhyulla.





Report message to a moderator

Re: [LONG] Re: Problem with randomness in planet distrtibution Sun, 14 October 2007 04:05 Go to previous messageGo to next message
m.a@stars is currently offline m.a@stars

 
Commander

Messages: 2765
Registered: October 2004
Location: Third star to the left
I think I might be able to adapt the "divide and conquer" method in a somewhat simpler way. It definitely shows promise! Cool Teleport


So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Problem with randomness in planet distrtibution Sun, 14 October 2007 14:16 Go to previous messageGo to next message
ck_drknes is currently offline ck_drknes

 
Crewman 2nd Class

Messages: 17
Registered: May 2007
Location: Why do you want to know?
Alright, spent a little time optimizing it and making it easier to read. It now takes 0.631 sec to gen a 4000 by 3000 map with 16 HW (in flash Very Happy ). The spacing is also now much better.

heres the pic:
[img]http://www.chasekernan.com/flashNovaMap2.gif[/img]

I also re-uploaded the actual app in case you want to see it.

Heres the better code (put some stuff in funcs so its a bit easier to read and shorter):
public function generateRectMap(dimensions:Vector, numberOfPlanets:uint, players:Array, names:Array, germanium:int = -1):void
		{
			_objects	=	[];
			//removed the checks because they're the same from above
			
			//randomize player and name order
			players						=	randomizeArray(players);
			names						=	randomizeArray(names);
					
			var planetPoints	:Array	=	createPoints(dimensions, numberOfPlanets, 0.05);
			
			for(i = 0; i < planetPoints.length; i ++)
				_objects.push(new Planet(planetPoints[i], names[i]));
			
			var hwPoints		:Array	=	createPoints(dimensions, players.length, 0.2);
			
			for(i = 0; i < hwPoints.length; i++)
			{
				//hw loc
				var point		:Vector	=	hwPoints[i] as Vector;
				
				//find closest planet
				var dist		:Number	=	_objects[0].Location.getDistance(point);
				var curDist		:Number	=	0;
				var planetNum	:int	=	0;
				
				for(var j:int = 0; j < _objects.length; j++)
				{
					curDist				=	_objects[j].Location.getDistance(point);
					if(curDist < dist)
					{
						dist			=	curDist;
						planetNum		=	j;
					}
				}
				
				//found the planet so now change it to HW
				var planet		:Planet	=	_objects[planetNum] as Planet;
				var player		:Player	=	players[i] as Player;
				
				//probably don't want to have this hardcoded.
				planet.IsHomeworld		=	true;
				planet.Owner			=	player;
				planet.Environment		=	player.PlayerRace.PerfectEnv;
				planet.MinConcentrations.Germanium	=	germanium;
				planet.Population		=	player.PlayerRace.GrowthRate * 5000 + 50000;
				planet.Factories		=	10;
				planet.Mines			=	10;
			}
		}
		
		private function createPoints(dimensions:Vector, numberOfPoints:int, borderPercent:Number):Array
		{
			var points		:Array	=	[];
			var sqrt		:int	=	Math.ceil(Math.sqrt(numberOfPoints));
			var plotSize	:Vector	=	new Vector(dimensions.x / sqrt, dimensions.y / sqrt);
			var excessPlots	:int	=	int(sqrt * sqrt - numberOfPoints);
			var border		:Number	=	borderPercent * Math.min(plotSize.x, plotSize.y);
			
			//remove excess
			var randomIntX		:int;
			var randomIntY		:int;
			var remove			:Array	=	[];
			//setup array
			for(var i:int = 0; i < sqrt; i++) 
			{
				remove[i]	=	[];
				for(var j:int = 0; j < sqrt; j++) remove[i][j]=	1;
			}
			
			//remove extra
			for(i = 0; i < excessPlots; i++)
			{
				do {
					randomIntX			=	int(Math.random() * (sqrt - 0.0001));
					randomIntY			=	int(Math.random() * (sqrt - 0.0001));
				} while (remove[randomIntX][randomIntY] == 0);
				remove[randomIntX][randomIntY] = 0;
			}
			
			//setup actual points
			for(i = 0; i < sqrt; i++)
			{
				for(j = 0; j < sqrt; j++)
				{
					if(remove[i][j] == 0) continue;
					
					var xloc	:int	=	i * plotSize.x + border + Math.random() * (plotSize.x - border * 2);
					var yloc	:int	=	j * plotSize.y + border + Math.random() * (plotSize.y - border * 2);
					
					points.push(new Vector(xloc, yloc));
				}
			}
			return points;
		}
		
		private function randomizeArray(a:Array):Array
		{
			var newA	:Array	=	[];
			for(var i:int = a.length - 1; i >= 0; i--) 
				newA.push(a.splice(Math.floor(Math.random() * (a.length - 0.0001)), 1)[0]);
				
			return newA;
		}

Report message to a moderator

Re: Problem with randomness in planet distrtibution Mon, 15 October 2007 07:04 Go to previous messageGo to next message
m.a@stars is currently offline m.a@stars

 
Commander

Messages: 2765
Registered: October 2004
Location: Third star to the left
I wonder if that code could be adapted to other shapes, such as globular cluster, spiral, and even ring? Cool


So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Problem with randomness in planet distrtibution Sun, 21 October 2007 20:47 Go to previous messageGo to next message
ck_drknes is currently offline ck_drknes

 
Crewman 2nd Class

Messages: 17
Registered: May 2007
Location: Why do you want to know?
Ok, quick update :

http://www.chasekernan.com/HNova.htm

I switched over to haxe (compiles to flash, neko, and js). It wasn't to much work, but it runs faster, and the client code will be the same as the server! neko vm runs on apache so it should be relatively simple to setup a client/server.

The new map code is very fast (atleast for flash). It takes around 0.06 secs to gen the map, its just the actual drawing on the screen that takes flash a second.

I'll work on the ring soon, (shouldn't be too hard, just change the dividing code from rects to arcs).


[Updated on: Sun, 21 October 2007 20:49]

Report message to a moderator

Re: Problem with randomness in planet distrtibution Sun, 21 October 2007 21:44 Go to previous message
ck_drknes is currently offline ck_drknes

 
Crewman 2nd Class

Messages: 17
Registered: May 2007
Location: Why do you want to know?
Its now a ring Very Happy . This could definately use some improvement (planets tend to be a little closer in the middle). I think if I set it up with the planets on rings instead of spokes it would solve it but thats for another night Rolling Eyes .

Here it is:
http://www.chasekernan.com/HNovaRing.htm

And after a little more work it can now take a cubic bezier curve as an argument. I'm hoping this leads to just about any map possible. I'll convert it to take an array soon so that it can take an image made from beziers (would be pretty cool).

Here it is :
http://www.chasekernan.com/HNovaBezier.htm



[Updated on: Wed, 24 October 2007 14:39]

Report message to a moderator

Previous Topic: Sapping Cruisers
Next Topic: Installations destroyed by bombing
Goto Forum:
  


Current Time: Sun Apr 28 02:41:58 EDT 2024