Randomly distributed N unique items (Topic)

Staredit Network > Forums > SC1 UMS Mapmaking Assistance > Topic: Randomly distributed N unique items

Randomly distributed N unique items

May 7 2014, 9:20 am
By: sethmachine

Pages: 1

May 7 2014, 9:20 am sethmachine Post #1

Hi,

Suppose I want to be fair and I have N unique units I want to give out to N players, where each player receives exactly one of those unique units, and no player has an identical unit.

For simplicity here is an example for N=4

4 players, 4 unique options:
0 = Terran Marine
1 = Terran Ghost
2= Terran Firebat
3= Terran Medic

I know how to randomly generate a number in the editor (a single switch with a death counter). But how do I prevent the other players from generating a number that has already been picked?

Suppose player one rolls number 0. He is assigned the Terran Marine.

Now player two rolls. In order to make sure he does not roll 0 or rather I resize the mapping to now roll a number 0-2 (0 = ghost, 1 = firebat, 2 = medic). I would need to iterate over all four cases (one of 0, 1, 2, or 3 is taken by player 1). This is a little silly I think.

When player three rolls, I need to iterate over two choose four possible cases to make sure he can only random an option not picked.

In the general case I would need this many "cases" for N players:

(1 choose N) + (2 choose N) + ... + (N - 1 choose N) = some very large number

I know if I bruteforced it for N unique options there would have to be N! cases (that is I simply generate a random number where each one represents a possible combination of the N options).

Now there are easier alternatives:

junk yard dog

or basing it on a player's action (e.g. when they move to a location).

I do not want to use either of those. So what is the solution using switch randomization with a DC?

Edit: Another stupid solution would be to have each player keep re-rolling until they get a number that hasn't been used. In the general case I don't think that's feasable but I know for a fact my N <= 6. So perhaps I should just use that.

Edit: Bruteforce solution isn't working because for some reason I am not generating a number 0-719... Please tell me what is wrong with my triggers (attached in text file...).

Edit: I found a working method. But I realized something...the RNG must fix itself in singleplayer, because I kept looping between only two of six choices when using "Restart Mission." But on Battle.net each game resulted in one of the six choices like it should >_>

Attachments:

random_trigs_fixed.txt
Hits: 5 Size: 919.4kb

random_trigs.txt
Hits: 0 Size: 854.13kb

Post has been edited 3 time(s), last time on May 7 2014, 11:43 am by sethmachine.

None.

May 7 2014, 5:04 pm

O)FaRTy1billion[MM] Post #2

👻 👾 👽 💪

That's quite a bit of triggers...

I did this in one of my maps with 6 or fewer players who spawn in a randomized location each round... I used units, I don't know if you want to. But I had a small area with 7 locations, the first 6 corresponding with starting positions and the 7th as a 'needs to be sorted' spot. First I spawn 1 burrowed Zergling for each player at the 7th spot. Then have the set of triggers that randomizes 3 switches. For the first two cases rerandomize, for the rest check if a zergling is already at the corresponding position and if it is rerandomize otherwise move the player's zergling there. When the 7th spot has no more zerglings then all players will have a unique starting position/whatever.

One draw back is it can take several trigger cycles to complete. You could also use switches/deaths instead of units on a map for a less visible sorting. Like instead of units filling spots, use switches and then to mark the player has that switch use a death for that player (like randswitch1 is set, randswitch2 is clear, randswitch3 is set, position5switch is clear then set position5switch and set deaths for current player to 5).

EDIT:
I can also think of other ways using units representing players to randomize them... Like having 6 spots filled either by units owned by the players or a unit corresponding to each players (so the player can't see it) and then for each spot choose one random other spot to swap with, effectively shuffling the contents. The benefit of this method is it wouldn't need to re-randomize (other than the two extra switch cases) so would take a more constant amount of time.

Post has been edited 2 time(s), last time on May 7 2014, 5:18 pm by FaRTy1billion.

TinyMap2 - Latest in map compression! ( 7/09/14 - New build! )
EUD Action Enabler - Lightweight EUD/EPD support! (ChaosLauncher/MPQDraft support!)
EUDDB - topic - Help out by adding your EUDs! Or Submit reference files in the References tab!
MapSketch - New image->map generator!
EUDTrig - topic - Quickly and easily convert offsets to EUDs! (extended players supported)
SC2 Map Texture Mask Importer/Exporter - Edit texture placement in an image editor!
$\:farty\:$ This page has been viewed [img]http://farty1billion.dyndns.org/Clicky.php?img.gif[/img] times!

May 7 2014, 5:27 pm

Sacrieur Post #3

Still Napping

Each player gets a different hero.

Randomize start location.

Boom.

None.

May 8 2014, 1:13 am sethmachine Post #4

I did not want to use units because it's not completely random (all units have different sizes), and patterns do emerge from junkyard dog script. I do not understand your method with the burrowed lings. But it seems like they keep moving until they find a grid which isnt the 7th option and isnt already occupied. In the past I've just used n unique units in a box and then the give command.

I considered using randomize start location but it brings up a number of problems, especially if I want to have player 1 act as a host slot (choosing modes, etc.).

Edit: So since there are n=6 options, there were a total of 720 unique permutations (6 x 5 x 4 x 3 x 2 x 1). Switch randomization gives a number from 0 - 2^m. The smallest power of 2 that is larger than 720 is 1024 (2^10). Therefore I needed 1024 triggers, one for each unique bit string mapped to one of the 720 unique permutations. For remaining 304 bit strings, I randomly chose 304 permutations of the 720 additionally.

Post has been edited 1 time(s), last time on May 8 2014, 1:20 am by sethmachine.

None.

May 8 2014, 1:21 am

jjf28 Post #5

Cartography Artisan

randomize start locations & have chooser units owned by p11, given immediately to p1?

TheNitesWhoSay - Clan Aura - github

Reached the top of StarCraft theory crafting 2:12 AM CST, August 2nd, 2014.

May 8 2014, 1:54 am

O)FaRTy1billion[MM] Post #6

👻 👾 👽 💪

Quote from sethmachine

I wasn't talking about units moving or Junk Yard Dog, I was talking about the Move Unit action and simply using the units as placeholders. I went on to describe a way to instead use switches and deaths to accomplish the same thing. ;o

EDIT:
This map does both methods I described. The first part of the triggers (Players 1-6) shuffles the units at each position (how I described in the edit of my first post). The next part of the triggers (Force 1) randomly selects a position for each player.
The only issue with my map right now is that the shuffling only works if all 6 players are present, but that can be resolved either by using a DC instead of relying on the players or in the case that each "position" will necessarily be a specific player (if position 1 was always player 1, then if only player 1 was present then he'd get a successfully random unit).

Attachments:

randomize.scx
Hits: 1 Size: 27.49kb

Post has been edited 1 time(s), last time on May 8 2014, 2:37 am by FaRTy1billion.

May 8 2014, 8:03 am

Azrael Post #7

Quote from

jjf28

randomize start locations & have chooser units owned by p11, given immediately to p1?

This. It has the benefit of not needing a dedicated host slot, because if P1 isn't there (or leaves), you can give it to P2, then P3, and so on. I'd recommend using P12 instead of P11 though, as it makes the whole "giving host-specific units to another player if the host leaves" thing a bit easier.

If you really want to accomplish this with just switches and DCs, though...

These triggers are owned by all 6 players.

CONDITIONS:
Always.
ACTIONS:
Randomize Switch 1.
Randomize Switch 2.
Randomize Switch 3.
Randomize Switch 4.
Randomize Switch 5.
Randomize Switch 6.
Randomize Switch 7.
Randomize Switch 8.
Randomize Switch 9.
Randomize Switch 10.
Randomize Switch 11.
Randomize Switch 12.
Randomize Switch 13.

CONDITIONS:
Switch 1 is Set.
ACTIONS:
Add 1 death of Cantina for Current Player.

CONDITIONS:
Switch 2 is Set.
ACTIONS:
Add 2 death of Cantina for Current Player.

CONDITIONS:
Switch 3 is Set.
ACTIONS:
Add 4 death of Cantina for Current Player.

CONDITIONS:
Switch 4 is Set.
ACTIONS:
Add 8 death of Cantina for Current Player.

CONDITIONS:
Switch 5 is Set.
ACTIONS:
Add 16 death of Cantina for Current Player.

CONDITIONS:
Switch 6 is Set.
ACTIONS:
Add 32 death of Cantina for Current Player.

CONDITIONS:
Switch 7 is Set.
ACTIONS:
Add 64 death of Cantina for Current Player.

CONDITIONS:
Switch 8 is Set.
ACTIONS:
Add 128 death of Cantina for Current Player.

CONDITIONS:
Switch 9 is Set.
ACTIONS:
Add 256 death of Cantina for Current Player.

CONDITIONS:
Switch 10 is Set.
ACTIONS:
Add 512 death of Cantina for Current Player.

CONDITIONS:
Switch 11 is Set.
ACTIONS:
Add 1024 death of Cantina for Current Player.

CONDITIONS:
Switch 12 is Set.
ACTIONS:
Add 2048 death of Cantina for Current Player.

CONDITIONS:
Current Player has suffered at most 1364 deaths of Cantina.
ACTIONS:
Add 1 death of Cantina for Player 8.

CONDITIONS:
Current Player has suffered at least 1365 deaths of Cantina.
Current Player has suffered at most 2730 deaths of Cantina.
ACTIONS:
Add 2 death of Cantina for Player 8.

CONDITIONS:
Switch 13 is Set.
ACTIONS:
Add 3 death of Cantina for Player 8.

CONDITIONS:
Player 8 has suffered at least 6 deaths of Cantina.
ACTIONS:
Subtract 6 death of Cantina for Player 8.

CONDITIONS:
Player 8 has suffered exactly 0 deaths of Cantina.
Force 1 brings at least 1 [Buildings] to "City1".
ACTIONS:
Add 1 death of Cantina for Player 8.

CONDITIONS:
Player 8 has suffered exactly 1 deaths of Cantina.
Force 1 brings at least 1 [Buildings] to "City2".
ACTIONS:
Add 1 death of Cantina for Player 8.

CONDITIONS:
Player 8 has suffered exactly 2 deaths of Cantina.
Force 1 brings at least 1 [Buildings] to "City3".
ACTIONS:
Add 1 death of Cantina for Player 8.

CONDITIONS:
Player 8 has suffered exactly 3 deaths of Cantina.
Force 1 brings at least 1 [Buildings] to "City4".
ACTIONS:
Add 1 death of Cantina for Player 8.

CONDITIONS:
Player 8 has suffered exactly 4 deaths of Cantina.
Force 1 brings at least 1 [Buildings] to "City5".
ACTIONS:
Add 1 death of Cantina for Player 8.

CONDITIONS:
Player 8 has suffered exactly 5 deaths of Cantina.
Force 1 brings at least 1 [Buildings] to "City6".
ACTIONS:
Set deaths of Cantina to 0 for Player 8.

CONDITIONS:
Player 8 has suffered exactly 0 deaths of Cantina.
Force 1 brings at least 1 [Buildings] to "City1".
ACTIONS:
Add 1 death of Cantina for Player 8.

CONDITIONS:
Player 8 has suffered exactly 1 deaths of Cantina.
Force 1 brings at least 1 [Buildings] to "City2".
ACTIONS:
Add 1 death of Cantina for Player 8.

CONDITIONS:
Player 8 has suffered exactly 2 deaths of Cantina.
Force 1 brings at least 1 [Buildings] to "City3".
ACTIONS:
Add 1 death of Cantina for Player 8.

CONDITIONS:
Player 8 has suffered exactly 3 deaths of Cantina.
Force 1 brings at least 1 [Buildings] to "City4".
ACTIONS:
Add 1 death of Cantina for Player 8.

CONDITIONS:
Player 8 has suffered exactly 4 deaths of Cantina.
Force 1 brings at least 1 [Buildings] to "City5".
ACTIONS:
Add 1 death of Cantina for Player 8.

CONDITIONS:
Always.
ACTIONS:
Set deaths of Cantina to 1 for Current Player.

CONDITIONS:
Current Player has suffered exactly 1 deaths of Cantina.
Player 8 has suffered exactly 0 deaths of Cantina.
ACTIONS:
Give all [Buildings] at "City1" to Current Player.

CONDITIONS:
Current Player has suffered exactly 1 deaths of Cantina.
Player 8 has suffered exactly 1 deaths of Cantina.
ACTIONS:
Give all [Buildings] at "City2" to Current Player.

CONDITIONS:
Current Player has suffered exactly 1 deaths of Cantina.
Player 8 has suffered exactly 2 deaths of Cantina.
ACTIONS:
Give all [Buildings] at "City3" to Current Player.

CONDITIONS:
Current Player has suffered exactly 1 deaths of Cantina.
Player 8 has suffered exactly 3 deaths of Cantina.
ACTIONS:
Give all [Buildings] at "City4" to Current Player.

CONDITIONS:
Current Player has suffered exactly 1 deaths of Cantina.
Player 8 has suffered exactly 4 deaths of Cantina.
ACTIONS:
Give all [Buildings] at "City5" to Current Player.

CONDITIONS:
Current Player has suffered exactly 1 deaths of Cantina.
Player 8 has suffered exactly 5 deaths of Cantina.
ACTIONS:
Give all [Buildings] at "City6" to Current Player.

CONDITIONS:
Always.
ACTIONS:
Set deaths of Cantina to 0 for Current Player.

That's significantly less triggers than what you're currently using, and it only uses switches, plus a single DC.

Alternatively, you could physically cycle the buildings between owners a random number of times.

You can note that the randomization here isn't perfectly unbiased; it takes advantage of the fact that every integer modulo 3 has a difference of 1 or less with 0, and 1/2^n becomes rapidly arbitrary as n increases linearly. This means if you feel the insignificant bias here isn't trivial enough already, you can simply randomize more than 12 switches to reduce it even further.

As it stands, with just 12 switches, it'd give you fair randomization thousands of times in a row before it'd show bias once. I don't think using more switches is really necessary, since the difference is already incredibly negligible. You'll also notice the system utilizes Player 8's Cantina DC for all players, with each player's randomization starting where the previous player's ended, which makes a single biased result trivial anyways.

May 14 2014, 10:52 am sethmachine Post #8

Thank you for this. What is this method called?

None.

May 14 2014, 2:48 pm

Azrael Post #9

I just came up with it, but I guess we could call it "Approximate Randomization" lol

Options

Pages: 1

Back to forum
Please log in to reply to this topic or to report it.
Members in this topic: None.

Global Shoutbox

[01:24 pm]

Vrael -- NEED SOME SPORTBALL> WE GOT YOUR SPORTBALL EQUIPMENT MANUFACTURING

[2024-4-30. : 5:08 pm]

Oh_Man -- https://youtu.be/lGxUOgfmUCQ

[2024-4-30. : 7:43 am]

NudeRaider -- Vrael

Vrael shouted: if you're gonna link that shit at least link some quality shit: https://www.youtube.com/watch?v=uUV3KvnvT-w

Yeah I'm not a big fan of Westernhagen either, Fanta vier much better! But they didn't drop the lyrics that fit the situation. Farty: Ich bin wieder hier; nobody: in meinem Revier; Me: war nie wirklich weg

[2024-4-29. : 6:36 pm]

RIVE -- Nah, I'm still on Orange Box.

[2024-4-29. : 4:36 pm]

Oh_Man -- anyone play Outside the Box yet? it was a fun time

[2024-4-29. : 12:52 pm]

Vrael -- if you're gonna link that shit at least link some quality shit: https://www.youtube.com/watch?v=uUV3KvnvT-w

[2024-4-29. : 11:17 am]

Zycorax -- :wob:

[2024-4-27. : 9:38 pm]

NudeRaider -- Ultraviolet

Ultraviolet shouted: NudeRaider sing it brother

trust me, you don't wanna hear that. I defer that to the pros.

[2024-4-27. : 7:56 pm]

Ultraviolet -- NudeRaider

NudeRaider shouted: "War nie wirklich weg" 🎵

sing it brother

[2024-4-27. : 6:24 pm]

NudeRaider -- "War nie wirklich weg" 🎵

Please log in to shout.

Members Online:

Roy