If you’re old, and lucky enough to have spent many an hour piloting your spacecraft from star system to star system, and spacestation to spacestation, buying and selling goods, taking on pirates and alien attacks in the game ‘Elite’, by David Braben and Ian Bell. Then you may well have been amazed by the sheer size of the game, hosting thousands of stars, planets and moons, with coordinates, descriptions, stats and stock market prices all tightly packed into 48KB of memory (in the case of the spectrum I owned, that is). Now it’s no mystery how they managed to do this, generating all their data procedurally through a fixed algorithm, so I decided to set about creating my own Universe-generating algorithm for my own projects.

Initially I found an interesting page which gives an example of creating star names from 32 ‘sounds’. So I started from this idea and expanded it to use a lot more ‘sounds’ and a list of optional name endings, which are in the vein of star, planet and moon names found in science fact and fiction, like -rsae, -peia, -ing, -land, etc. It started off very simple and I’d take a look at the resulting names and wonder how I could improve on them, until I arrived at something fairly useable. I’ll probably expand on it a little more and tweak it here and there.

At the time of writing this there are 100 ‘sounds’, which are:

const std::string nameParts[] = {
	"a"              , "e"              , "i"              , "o"              , "u"           ,
	"b[lr][eio]a"    , "b[lr][a]e"      , "b[lr][ae]i"     , "b[lr][aeio]o"   , "b[lr]u"      ,
	"z[eioy]a"       , "z[aeo]e"        , "z[ae]i"         , "z[aeo]o"        , "zu"          ,
	"c[hlr][eio]a"   , "c[hlr][aeo]e"   , "c[hlr][ae]i"    , "c[hlr][aeo]o"   , "c[hlr]u"     ,
	"y[e]a"          , "y[e]e"          , "y[eo]o"         , "d[eiory]a"      , "d[r]e"       ,
	"d[aer]i"        , "d[aeior]o"      , "d[r]u"          , "x[i]a"          , "xe"          ,
	"f[aeilor]a"     , "f[aelor]e"      , "f[aelr]i"       , "f[aeilor]o"     , "f[lr]u"      ,
	"w[aei]a"        , "w[aeo]e"        , "w[ae]i"         , "w[aeo]o"        , "wu"          ,
	"g[aeilory]a"    , "g[aelor]e"      , "g[aelr]i"       , "g[aeilor]o"     , "g[r]u"       ,
	"v[eio]a"        , "v[ael]e"        , "v[ae]i"         , "v[aeio]o"       , "vu"          ,
	"h[eioy]a"       , "h[ae]e"         , "h[ae]i"         , "h[aeo]o"        , "hu"          ,
	"t[h][r][aeio]a" , "t[h][r][ae]e"   , "t[h][r][ae]i"   , "t[h][r][aeo]o"  , "t[h][r]u"    ,
	"j[eio]a"        , "j[ae]e"         , "j[ae]i"         , "j[eo]o"         , "ju"          ,
	"s[hl][aeio]a"   , "s[hl][ae]e"     , "s[hl][ae]i"     , "s[hl][aeo]o"    , "s[hl]u"      ,
	"k[lr][aeio]a"   , "k[lr][ae]e"     , "k[lr][ae]i"     , "k[lr][aeo]o"    , "k[lr]u"      ,
	"r[aeioy]a"      , "r[ae]e"         , "r[ae]i"         , "r[aeoy]o"       , "r[y]u"       ,
	"l[l][eio]a"     , "l[l][ae]e"      , "l[ae]i"         , "l[aeio]o"       , "lu"          ,
	"p[hlr][ey]a"    , "p[hlr][e]e"     , "p[hlr]i"        , "p[hlr][aeo]o"   , "p[hlr]u"     ,
	"m[eioy]a"       , "m[ae]e"         , "m[ae]i"         , "m[aeo]o"        , "mu"          ,
	"n[aeio]a"       , "n[ae]e"         , "n[ae]i"         , "n[aeo]o"        , "nu"          };

The letters within square braces ‘[]‘ are optional characters, where there is a chance that an optional letter may appear and each optional character has an equal chance of being the one that does appear. Some ‘sounds’ have more than one optional character. For example “p[hlr][ey]a” may give “pa”, “pea”, “pya”, “pha”, “plya”, etc. Of course these ‘chances’ are also determined in particular order so as to ensure the names are consistent each time you enter the same seed into the algorithm. You might notice that each ‘sound’ ends with a vowel, this was just to ensure that it could create a good variety of words that (hopefully) weren’t too awkward to pronounce. I found it was quite easy to rectify many unwanted occurances of unpronounceable words by tweaking these strings.

The name-endings, of which there are currently 243, are:

const std::string nameEndings[] = {
	"c"    , "d"    , "g"    , "k"    , "l"    , "m"    , "n"    , "p"    , "r"    , "s"    ,
	"t"    , "x"    , "z"    , "boo"  , "bok"  , "bock" , "beia" , "beus" , "bham" , "bu"   ,
	"bi"   , "bia"  , "bae"  , "buth" , "boz"  , "biz"  , "bic"  , "bol"  , "buk"  , "cham" ,
	"ci"   , "cia"  , "ce"   , "cuth" , "car"  , "col"  , "di"   , "dia"  , "de"   , "duth" ,
	"dar"  , "dol"  , "duk"  , "du"   , "doo"  , "din"  , "dok"  , "dock" , "ding" , "deia" ,
	"dium" , "deus" , "dham" , "fi"   , "fia"  , "fah"  , "fun"  , "foo"  , "ff"   , "foon" ,
	"fael" , "frey" , "fham" , "gi"   , "gia"  , "ge"   , "gah"  , "gun"  , "gol"  , "guth" ,
	"gee"  , "goo"  , "goz"  , "gol"  , "geus" , "gham" , "ho"   , "ham"  , "han"  , "jar"  ,
	"jam"  , "jo"   , "jok"  , "kul"  , "kor"  , "king" , "kar"  , "kol"  , "kik"  , "kia"  ,
	"kol"  , "kham" , "land" , "lam"  , "lor"  , "lar"  , "ler"  , "lad"  , "lik"  , "lia"  ,
	"lus"  , "lim"  , "lphi" , "leus" , "lham" , "mar"  , "mand" , "mir"  , "mor"  , "moor" ,
	"mock" , "mak"  , "mik"  , "mitz" , "ming" , "mad"  , "mia"  , "mae"  , "mus"  , "meus" ,
	"nar"  , "nd"   , "nir"  , "nor"  , "noor" , "nock" , "nak"  , "nik"  , "nitz" , "ning" ,
	"nad"  , "nia"  , "nol"  , "nae"  , "nus"  , "neus" , "nham" , "par"  , "pia"  , "pock" ,
	"pitz" , "por"  , "pak"  , "ping" , "pad"  , "polus", "peia" , "peus" , "pae"  , "poe"  ,
	"pod"  , "pol"  , "phor" , "phus" , "phon" , "phoon", "pha"  , "phir" , "phog" , "phong",
	"phi"  , "pham" , "que"  , "rah"  , "ring" , "rhea" , "rom"  , "rok"  , "rock" , "rus"  ,
	"rag"  , "rol"  , "reus" , "rham" , "seus" , "sol"  , "som"  , "son"  , "sing" , "sand" ,
	"sik"  , "sur"  , "sog"  , "sae"  , "saeus", "sia"  , "sham" , "ti"   , "tia"  , "tae"  ,
	"teus" , "tus"  , "tos"  , "tir"  , "ton"  , "ting" , "tong" , "tom"  , "th"   , "thum" ,
	"tham" , "theus", "thom" , "thium", "thon" , "than" , "wath" , "wart" , "warg" , "wurt" ,
	"witz" , "wham" , "via"  , "vog"  , "voz"  , "vol"  , "vig"  , "vitz" , "xy"   , "y"    ,
	"bay"  , "day"  , "fay"  , "gay"  , "hay"  , "kay"  , "lay"  , "ly"   , "ley"  , "my"   ,
	"ny"   , "py"   , "ry"   , "dry"  , "ndry" , "gry"  , "ngry" , "sy"   , "ty"   , "sty"  ,
	"set"  , "rsae" , "rseus"};

In order to generate the names for a star map, I decided on using a coordinate system based on 3 sets of 3D Integer data (giving 9 digits in total) as the random seed. The first three digits are used as the X, Y and Z coordinates for what I call a ‘Quadrant’, giving a total of 1,000 quadrants in this Universe (Where X, Y and Z can each be 0 to 9), these being the largest unit of area in this particular system. Next is the ‘Sector’, again using 3 digits to represent the X, Y and Z coordinates within a quadrant. This gives 1,000 Sectors per quadrant. Finally, the last 3 digits represent a ‘SubSector’ within the specified Sector. Therefore we can procedurally generate names for 1,000 quadrants containing 1,000,000 sectors hosting 1,000,000,000 subsectors, which is a fair amount I’m sure you’ll agree.

For example, 439,016,224 would be the random seed for quadrant(4,3,9), sector(0,1,6), subsector(2,2,4). Details of the quadrant, including the name, would be determined by it’s 3 digits (439), the sector details would be dependant on the quadrant and sector coordinates (439016). This would give different results for a sector with the same number but in a different quadrant. And finally the subsector details would come from the whole number (439016224). This is reasonable when using 32-bit unsigned integers which handle numbers up to 4,294,967,295 as a single integer can store the whole random seed. Initially I was working on just producing the quadrant, sector and subsector names, where the subsector would also be the name of a star system if one was found to exist there. But this can also be used to procedurally create descriptions, statistics and other data for each item.

For good measure I decided to throw in a little extra option for subsector/star systems, whereby they had a chance of being denoted by a code. For this I chose it to be 2 letters, followed by a number between 132 and 9999, a hyphen ‘-’, a 2 digit number and then a single character either ‘A’, ‘B’, ‘C’ or ‘D’. This is just a preliminary code, until I have time to go into this further.

After this it struck me that although I was using the coordinates as the random seed within a C++ program, the same results would not necessarily appear in Java, Pascal, Php, etc. The only way to ensure that the coordinate numbers always gave the same results would be to write my own random number generator functions. This was in fact incredibly easier than I first thought, because Wikipedia actually had a set of pseudo code listed for the Mersenne Twister random number generator algorithm, and porting this to C++ was straightforward.

And this is currently as far as I have reached with this little sub-project. Although I intend to create a PHP version to place on a webpage whereby you can select a particular set of coordinates, that is a particular quadrant, sector and subsector/star system and receive names for them, or just click a button and receive a random, procedurally generated name.

Here’s a few examples of the output the current program gives for the first 16 quadrants, and the first sector and subsector/system name in each of those quadrants:

[Q000]:zamee,       [S000]:hexebay,   [s000]:klikelu
[Q001]:dokol,       [S000]:moa'gonir, [s000]:vocosaa
[Q002]:taejoneus,   [S000]:wedabok,   [s000]:ER3317-89D
[Q003]:benus,       [S000]:bujihe,    [s000]:tijuthom
[Q004]:xiaha,       [S000]:loamy,     [s000]:traopoe
[Q005]:peseus,      [S000]:claivoory, [s000]:mebajei
[Q006]:jubu,        [S000]:ritralam,  [s000]:julopak
[Q007]:charom,      [S000]:gagham,    [s000]:mizibu
[Q008]:owaakik,     [S000]:vaklu,     [s000]:AM8968-34A
[Q009]:wileateus,   [S000]:wer,       [s000]:mosufham
[Q010]:hia,         [S000]:xalo,      [s000]:waita
[Q011]:zaxavi,      [S000]:hetrulo,   [s000]:gileus
[Q012]:idi,         [S000]:trumo,     [s000]:duci
[Q013]:duulay,      [S000]:kunep,     [s000]:sevo
[Q014]:kacucla,     [S000]:sholuwart, [s000]:hajuhi
[Q015]:chaewaecuth, [S000]:nobiz,     [s000]:zema

I wonder how much alloys are going for in the Gileus system… You know the Gileus system, it’s in the Hetrulo sector on the edge of the Zaxavi quadrant…

This is my first post about a project I’ve been working on for a good while now. Unfortunately I’ve never been sure what the project was destined to be. Initially it was a simple 3D star map for use in space based games on a campaign scale, to replace one I wrote a few years ago which seemed fairly popular called 3D StarMap. But things have developed and I’m considering a full blown multiplayer online Elite clone. I might settle for something inbetween, but I’m not working to a deadline so I’ll see where it takes me. This screenshot was just to test frame rates with varying numbers of polygons, here showing a 5x5x5 cube of Python-style ships from the old Elite game. There are only about 1625 polygons for the ships, although the starfield background is mapped onto a large sphere, so that’s a few extra polys. I think I managed to get upto just over 145,000 polygons before the frame rate changed from 71 fps (frames per second) which isn’t bad.

So far I’ve been trudging through Blender to create the models, primarily because I want to keep to free software in developing this project. I use DevCpp from Bloodshed Software for development, using C++ of course, Blender as I mentioned for the 3D modelling and soon I’ll switch to GIMP for the textures and other graphics. To begin with exporting raw ASCII models from Blender was sufficient, until I wanted to include the textures which aren’t supported in the raw format. So I switched to the AC3D ASCII format which does provide support for textures and I’d much rather Blender calculated the texture coordinates that do it manually myself.

I need to find some better way of creating the background starfield, the image used is quite big as it is, but it still gets blown-up and causes the stars to look fuzzy and dull. I’m going to have to work on some functions to load .PNG format textures as the compression on these is pretty awesome, which is extremely useful as these textures could end up being rather large. I’ve had some problems with compiling a working .PNG library (libpng and glpng) for windows anyway, probably a cinch on Linux. I’ve managed to create the zlib but it seems to have problems after that which I won’t go into now.

Of course the whole thing is written using the OpenGL graphics library.

There’s one aspect of programming that has always given me cause to spout prolific expletives and yet it’s something that is required in most applications. I am of course talking about Date handling.

If I had my way then everyone would use a format which, like number systems, book contents pages and many other structures in everyday life, starts with the largest denomination or unit down to the smallest. I.e. Year Month Day Hour Minute Second, using whichever separator is preferred and unit format, e.g. ’2006-JAN-21 12:15:34′, ’06/01/21′, ’2006, January 15th’, etc.

But that would be just too logical for everyone and many systems in many countries have already adopted their preferred format. For me in the UK we have the date in reverse, eg. 10-Jan-2006 (smallest unit -> largest), whereas Americans have an almost random order with Jan-10-2006 (middle unit -> smallest -> largest). I don’t know of any other system of measurement that is affected like this, we don’t have measurements like ’4m 8mm 12cm’ or ’4lbs 8st’, so why measure time differently? So, many countries like the UK need to take extra care when dealing with dates, unlike the US which sets the standard in many languages/development tools like .NET. With the difference between the UK and US date formats it can be rather ambiguous when working with the first 12 days of any month. For example, 10/08/2006 in the UK would be regarded as the 10th of August, whereas in the US this would be the 8th of October.

Now, .NET does have it’s ways of handling these issues, but of course there’s always more than one way to skin a cat as they say.

When converting a DateTime value to say a string the conversion is relatively simple, there are mechanisms for producing the date in whatever format you choose. One way is to use the old VBScript Format function eg.

Dim str As String = Format(Now, "dd-MM-yy")

Which gives the current date in the Format defined by the string “dd-MM-yy” as a string. But in .NET we want to avoid using the old VBScript methods and instead use the .NET framework. For this .NET provides the ability to format various objects for conversion to strings in the very method that does the conversion, i.e. the ‘ToString’ method:

Dim str As String = Now.ToString("dd-MM-yy")

Well that’s the easy side covered as a String object is both fairly simple in its definition and flexible in it’s data, the Date object on the other hand is a little more complex in structure and far more constrained in its data. The process of converting a date contained in a String object for transfer into a Date/DateTime object can be a little more challenging.

I’ve seen many people suggest using the following:

Dim myDateTime As DateTime = Convert.ToDateTime("01/02/2006")

Apparently, the interpretation of a date string, e.g. ’01/02/2006′, is rather dependant on the locale settings of the machine on which it is running. But I haven’t been able to replicate this at all. Regardless of whether my regional setting is set to US or English and even though it states very clearly in the regional settings that the US format is ‘Month/Day/Year’, the string above is still interpreted as ‘Day/Month/Year’. So, it appears that I might as well use the Convert.ToDateTime method of reading date strings and stop worrying, but I won’t….

For starters the Convert.ToDateTime method invokes the DateTime.Parse method according to MSDN, so the following seems more efficient:

Dim myDateTime As DateTime = DateTime.Parse("01/02/2006")

Which again gives me the same results regardless of regional setting. I’d rather not rely on this very loose method of string to date conversion, especially when I have no idea why the regional setting isn’t making a difference. The methods so far are very open and return a date of ’01/02/2006′ interpreted as the 1st of February, 2006 for all of these strings: ’01/02/2006′, ’01/02/06′, ’01-02-2006′, ’01-02-06′, ’01.02.2006′, ’01.02.06′, ‘feb 01 06′, 01 feb 06′, ’2006 feb 01′, ‘february 1 2006′, ’1.2.6′, etc, etc. I don’t know about you, but I’d say that was pretty loose.

There is a more strict alternative, which is the DateTime.ParseExact method and this will allow a particular expected date and time format to be specified. The ParseExact method I’ll be looking at takes 3 parameters, the date string to be converted, a format string and something called an IFormatProvider which contains information about a particular culture to be used. For the initial example I shall not provide any information about the culture and simply pass ‘Nothing’ as the third parameter. So, if we store our date string to be converted in a string variable called ‘myString’ for example:

Dim myDateTime as DateTime = DateTime.ParseExact(myString, "dd/MM/yyyy", Nothing)

This will throw a ‘FormatException’ exception for any value in myString that does not exactly match the ‘dd/MM/yyyy’ format string. So anything like ’01-02-2006′, ’01/02/06′ or ’1/2/2006′ will all result in generating an exception. Although, for the last example it would be valid if you set the format string to ‘d/M/yyyy’ since a single ‘d’ or ‘M’ allows 1 or 2 digit values, whereas ‘dd’ and ‘MM’ allows only 2 digits so you must prefix single digit values with zeros.

You can also use format characters to represent whole format strings, such as ‘d’ which indicates a ShortDatePattern, ‘D’ is for a LongDatePattern, ‘G’ indicates a General format with a short date and a long time, etc. The whole list of these are available from MSDN along with the format pattern information for creating your own format strings like the ‘dd/MM/yyyy’ I used above.

This isn’t so bad if you are only ever going to receive the date string in one particular format, but you might want to allow some variations on the date format. We’re not trying to limit the format of the date strings we can successfully convert to DateTime objects, all we’re really after is being safe in the knowledge that we are interpreting the date strings correctly and consistently. Using the UK format I want to be sure that whenever the day and month values are represented in numerical format, that the first value is the day and the second is the month for example. So in order to specify several format strings you can pass a string array rather than just one string, again with our date string stored in myString:

Dim myFormatStrings() as String = {"d", "D"}
Dim myDateTime as DateTime = DateTime.ParseExact(myString, myFormatStrings, Nothing)

Which will convert date strings in the Short and Long formats. Also…

Dim myFormatStrings() as String = {"d/M/yyyy", "d-M-yyyy"}
Dim myDateTime as DateTime = DateTime.ParseExact(myString, myFormatStrings, Nothing)

Will allow dates with 1 or 2 day and month numbers and a 4 digit year, with either ‘/’ or ‘-’ date separators.

Finally, I should probably say a few words about the third parameter for ParseExact, IFormatProvider, since it’s not a good idea to pass Nothing as I have done so far. This parameter can be specified in a few ways but I’ll only show one here, there’s a fair few examples around the net on this if you need more info. It is possible to select the format provider based on the current culture setting for the machine, but as I mentioned before, I’d rather be a little more specific about what I require. So this example will explicitly set the format provider to “en-GB”, known as English – Great Britain. In a nutshell I create an IFormatProvider object by supplying my specific culture to the CultureInfo method of System.Globalization. So using myString and myFormatString from examples above:

Dim myFormatProvider as IFormatProvider = New System.Globalization.CultureInfo("en-GB")
Dim myDateTime As DateTime = DateTime.ParseExact(myString,myFormatString,myFormatProvider)

And that’s that, besides since I got married a couple of months ago you would think I wouldn’t need to worry about dates anymore…