Non-uniform random numbers

EFileTahi-A

Contributor
Joined
Aug 8, 2004
Location
Portugal / Barreiro
What would be the best approach to generate a random number that does NOT have the same equal chance of coming up.

Although I would prefer an arc, a line would also fit for the job.

Code:
Arc:
----
  0 #
    ##
    ###
    ####
 50 #####
    ########
    ###########
    #################
100 ########################


Line:
-----
  0 #
    ####
    #######
    ##########
 50 #############
    ################
    ###################
    ######################
100 #########################

So the above example tells the chance of randomizing a number between 0 to 100, where the more '#' equals a better chance of scoring.

I could manually script the chances values inside an array or similar object but the numbers can be decimal and contain a real astronomic difference between the minimum and maximum values.

Help? :)
 

snarfblam

Ultimate Contributor
Joined
Jun 10, 2003
Location
USA
If I understand correctly, in your example you're looking for a random number generator where the number zero has almost no chance of coming up, and as you approach 100 each successive value becomes more likely. 100 would be twice as likely as 50 and 50 would be twice as likely as 25, and so on. Is this right?

Even though we often generate random integers, the random number generator always starts with a random fractional number between 0 and 1 (to be more accurate, greater than or equal to zero, and less than one). Suppose we ask for a random integer from 0 to 99. The generator computes a number between 0 and 1, and multiplies that number by 100. This gives us a value that is 0 or higher and less than 100. Then the generator chops of the decimal part (truncation). This gives us an equal chance of getting any integer from 0 to 99.

Now, if we get our hands on that randomly generated value between 0 and 1, we can do the multiplying and truncating ourselves, with the added bonus of being able to mess around with the random number to change the odds. We can actually get that random fractional value with the Random.NextDouble function.

Let's start by generating a random number from 0 to 99, with equal odds for each number. We'll show the frequency of each number generated, as a percentage, in a ListBox.

Code:
    Const range As Double = 100
    Const iterations As Long = 10000000

    ' We will keep track of the frequency that each number from 0 to 99 is generated
    Dim Frequency(99) As Long
    Const FrequencyFormat As String = "{0}: {1}%"

    Public Sub DoRandomness()
        Dim r As New Random

        For i As Integer = 0 To iterations - 1
            ' Get our random value where: 0 <= value < 1
            Dim randomFraction As Double = r.NextDouble()

            ' Multiply to get the value in the range of 0 <= value < 100
            Dim scaledValue As Double = randomFraction * range
            ' Truncate to get our final value from 0 to 99
            Dim truncatedValue As Integer = CInt(Math.Floor(scaledValue))

            ' Record the number that was generated
            Frequency(truncatedValue) += 1
        Next
    End Sub

    Public Sub ShowRandomness()
        For iFreq As Integer = 0 To UBound(Frequency)
            ListBox1.Items.Add( _
            String.Format(FrequencyFormat, iFreq, (100 * (Frequency(iFreq) / iterations)).ToString("0.00")))
        Next
    End Sub

Now, to change the odds, we can apply mathematical transformations to our randomly-generated fractional value. If you use a graphic calculator to graph the equation y=x with a view window of (0,0) to (1,1), you'll see that the curve moves from (0,0) to (1,1) in a straight line. This is our base-line where each number is just as likely to be randomly generated.

Now, if you compare the graph of y=x to a graph of y=x^2, you'll see that y=x^2 curves below the line, indicating that smaller numbers are more likely to be generated than larger numbers. If we square our random fraction before multiplying and truncating, we'll get more small numbers and fewer large numbers.

If we compare y=x to y=x^0.5 (square root), you'll see that y=x^0.5 bows up above the line. This indicates larger numbers are more likely to be generated. This is what you want. In fact, this produces random numbers where a number that is twice as large is twice as likely to be produced. We can make one small change to the program and see for ourselves.

Code:
    Public Sub DoRandomness()
        Dim r As New Random

        For i As Integer = 0 To iterations - 1
            ' Get our random value where: 0 <= value < 1
            Dim randomFraction As Double = r.NextDouble()
[COLOR="Red"]
            ' Take the square root to make large numbers more likely.
            randomFraction = Math.Sqrt(randomFraction)[/COLOR]

            ' Multiply to get the value in the range of 0 <= value < 100
            Dim scaledValue As Double = randomFraction * range
            ' Truncate to get our final value from 0 to 99
            Dim truncatedValue As Integer = CInt(Math.Floor(scaledValue))

            ' Record the number that was generated
            Frequency(truncatedValue) += 1
        Next
    End Sub
Run it and you'll see that, for example, 25 comes up about half as often as 50.
 

EFileTahi-A

Contributor
Joined
Aug 8, 2004
Location
Portugal / Barreiro
I have absolutely no words for you top notch post.
Thanks to your time and effort I can finally resume my work!

I already tried your algorithm and it works like a charm! This produces the line random chance I described in my first post. Just wondering, is it too difficult to implement the curve random chance? If it is complicated forget it, this will fit quite well for what I intend to achieve. Thanks again!

PS: did you read my private message? :)
 

snarfblam

Ultimate Contributor
Joined
Jun 10, 2003
Location
USA
Just wondering, is it too difficult to implement the curve random chance?

Well, I thought I understood the math behind this, and I typed up a big long explanation about how I came to the answer that I came to, and before submitting my post, I tried a few more examples and realized I have no idea what I'm talking about, and that I just stumbled on a few cases where my bad math just so happened to give useful answers.

So here's the answer I came up with without understanding how. If you take the cube root instead of the square root, you'll get a curve. Is it the curve you want? I'm not sure. Were you looking for a specific curve?



PS: did you read my private message? :)
I did. I didn't have time to respond, I spent so much time on my (first) answer :) I'll send you a PM.
 

EFileTahi-A

Contributor
Joined
Aug 8, 2004
Location
Portugal / Barreiro
No, the problem is definitely not yours. Its my poor math skills that didn't get me to see your explanation. I payed more attention now and I actually understood how the whole think works. I must also confess that I got too much excited with the code you posted which got most of my attention.

Anyway, I got the (Math.Pow(Value, (1.0 / 3.0)) expression to cubic root it.
This is awesome as I will also require different magnitudes of arcs I simply need to replace the 3.0 for a different value.

Just for to let you know this is for a exploration-space-game I'm developing which generates a galaxy on the fly. It creates stars based on astrophysics real info. Each solar system will have their own planets, asteroids, comets etc. Planets will have their own atmosphere, type of terrain and resources based on their distance from their stars and size.

Since I'm using our solar system as a model, planets are most likely to appear closer to stars and more likely to have lower eccentricities on their orbits, hence the non-uniform random function.

At the moment the game already generates a full spiral galaxy with stars. Now I just need to populate the solar systems with celestial bodies. We can already travel around the galaxy and watch all stars and their designated names.

I have great plans for this project :)
(\me imagines snarfblam asking about that project of his) :D
 
Last edited:

snarfblam

Ultimate Contributor
Joined
Jun 10, 2003
Location
USA
Actually, it's strange how similar that is to a loosely-formed idea that has been floating around my head for a while. I thought it would be cool to have a space exploration game with action/RPG elements mixed in, but I've never investigated the idea or hashed out the details because if I get started with something new I'll never finish what I've got going now.

So now I'm a bit curious. Is this an XNA game? What sort of gameplay is involved?
 

EFileTahi-A

Contributor
Joined
Aug 8, 2004
Location
Portugal / Barreiro
Actually, it's strange how similar that is to a loosely-formed idea that has been floating around my head for a while. I thought it would be cool to have a space exploration game with action/RPG elements mixed in, but I've never investigated the idea or hashed out the details because if I get started with something new I'll never finish what I've got going now.

So now I'm a bit curious. Is this an XNA game? What sort of gameplay is involved?

Sorry for the late response. It has been crazy at my job handling nearly 100 teachers to use my software to plot all their student's scores.

Regarding "our" project :D. It does have strong RPG elements in it with customizable ships and equipment for the following types of space ships:

- Frigate
- Battle Frigate
- Destroyer
- Light Cruiser
- Heavy Cruiser
- Small Freighter
- Large Freighter
- Battle Freighter
- Battleship
- Dreadnought
- Capitalship

Have you ever player Elite? Frontier (Elite II)? First Encounters? Well this project is strongly inspired in such game. Ships have jump drives to travel between solar systems. Although Elite was a 3D game this project will be strictly 2D. I'm replacing the cool 3D aspect of it by a even cooler 2D Game play mechanics.

The game play:
You will cruise through the thousands of stars which compose the galaxy. You will be able to trade, go freelancer, run missions (quests), join the military for several factions or simply travel by your own for fortune and glory without any predefine path.

The above is similar to the original game Elite. What I've changed was the combat and the possibilities of equipping your ship, adding also heavy tactical / strategic turn based combats. But I'm not talking about a top-down / isometric view with a grid-map where you move your ship and fire by turns.

No no, the action will consist of a screen split in half. One half for each faction, you and the enemy. Action points is what will decide the faith of both factions during combat. Here are some possibilities:

- Shields up / down (if any)
- Transfer energy between shields. For example, transfer energy from the rear to the front shields so that armor remains protected.
- Charge weapons.
- Fire weapons and missiles
- Canalize energy between equipment.
- Order crew to battle stations.
- Order crew to repair pretty much anything on the ship.
- Order crew to replace equipment (if you brought spare ones).
- Order crew to put out fires.
- Order crew to escape pods.
- Manage the wounded.
- Evasive actions.
- Increase decrease speed (the faster the ship is traveling the harder the enemy will hit it but also more power will be consumed at the end of the turn.)
- Approach enemy vessel.
- Board enemy vessel.
- Jump away (escape). It take a few turns. If the enemy ship has a jump disruptor you might not be able to escape at all.
- Bring equipment ON / OFF line. This will critically affect the amount of energy the ship will have available for the next turn.

Probably the most important aspect of the ship is the power it generates. Power cores are the life of a ship. Without energy the ship is a dead rock. Power cores, like pretty much all sort of equipment have many variants and models.

Energy is produced at the begin of your round. You spend it by charging weapons / shields and on repairs. Its a good a idea to leave some energy at the end of your turn for your defense phase so that the weapons you charged but you didn't fire may try to destroy enemy missiles and other hazards.

Ships have a certain number of slots for weapons and equipment with specific sizes. For example frigates, battle frigates and destroyer use small size slots while cruisers and battle cruisers use medium size slots.

Well, there is too much to tell. Now I will tell you something which probably you won't appreciate at all. The game is being done using only GDI+. Why? It's so easy to work with and makes it go cross-platform. There is no great need for speed. It does at the moment an average of 40 fps at 1920x1200. Thought I think I will limit it to 20fps so it can run stable in slower computers.

The project is still being crafted so I can change anything you want. I'm quite serious about this one. If you want I can add some screen shots of what is done at the moment. :)
 
Last edited:

EFileTahi-A

Contributor
Joined
Aug 8, 2004
Location
Portugal / Barreiro
LOL Yes, a compliment. I am expressing jealousy over your cool projects compared to my boring ones.

I don't know how many projects you have in your database but I advise you to reduce their count so you can put a lot more effort in a single one. If you need help in game design or ideas drop me a line (assuming your projects are games).
 
Top Bottom