Author Topic: Randomizing Starting Locations  (Read 2030 times)

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4955
Randomizing Starting Locations
« on: March 05, 2009, 02:45:54 AM »
Quote
Hey Hooman,

I was looking through OP2Helper to see how you handled randomized starting locations so I could do it myself, but it seems that it needs a lot of info that would be established in BaseData.h to work (I was hoping to copy/paste it and eliminate all the BaseData-related stuff, but I wasn't even sure where to begin).  Think you could help me make my own base randomization function?

Thanks.

Randomization
There are three functions in OP2Helper that all basically do the same thing. Here's the most "basic" version of the algorithm. It randomizes a list of int values, rather than a list of pointers to base structs, or a list of pointers to beacon info. They are all basically copy/paste with data type changes. None of this actually depends on the data type. (Should probably have written it as a template).

Code: [Select]
// Note: Uses TethysGame::GetRand();
void RandomizeList(int numItems, int list[])
{
int i;
int next;
int temp;

// Randomly reorder the list (backwards)
for (i = numItems-1; i; i--)
{
  // Determine which item to place next in list
  next = TethysGame::GetRand(i+1);
  // Swap the 'next' item into place
  temp = list[i];
  list[i] = list[next];
  list[next] = temp;
}
}
All it does, is randomly reorder the list, in such a way that each number should have an equal probability of landing in any given slot. (Assuming the Random Number Generator is sufficiently "random", and produces a uniform distribution).

It works in a loop. It basically looks at how many items are left in the list at any given point, and generates a random number of that range. (Note that i = numItems - 1 when initializing the loop, so i+1 is used in the GetRand call so the range does end up being the number of items left in the list. This is done to get the indexing and loop termination conditions simpler). It then places that item first in the output array, and does the same thing on the list that's now one item smaller. It also optimizes the process by reusing the input array for the output. It can do this by swapping items rather than just writing them to the output array.

Ex:
The outer {} repesents the bounds of the array, and the inner {} represent the concept of the two lists, which actually share the same memory space. Note that indexes are 0-based, and GetRand(X) returns a number in the range 0..(X-1). That is, a list with 6 items, has indexes 0-5, and GetRand(6) returns numbers in the range 0-5. The first item is item 0, not item 1.
Step 0: {{0, 1, 2, 3, 4, 5}, {}}    // Input list is full, Output list is empty
Step 1: {{0, 5, 2, 3, 4}, {1}}      // GetRand(6) -> 1  (Swap pos 1 and 5)
Step 2: {{0, 5, 2, 3}, {4, 1}}      // GetRand(5) -> 4 (Swap pos 4 and 4)
Step 3: {{0, 3, 2}, {5, 4, 1}}      // GetRand(4) -> 1 (Swap pos 1 and 3)
Step 4: {{0, 3}, {2, 5, 4, 1}}      // GetRand(3) -> 2 (Swap pos 2 and 2)
Step 5: {{3}, {0, 2, 5, 4, 1}}      // GetRand(2) -> 0 (Swap pos 0 and 1)
Step 6: {{}, {3, 0, 2, 5, 4, 1}}    // Technically, this step is not executed, as the loop has already finished with everything in place. Indeed, it's be pointless to generate a "random" number with a range of 1. (It wouldn't be random).



Edit: Forum keeps eating my post. =(
It seems to be size related.
« Last Edit: March 05, 2009, 03:02:45 AM by Hooman »

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4955
Randomizing Starting Locations
« Reply #1 on: March 05, 2009, 03:04:23 AM »
Why This Is Useful
Suppose you have 6 players, and 6 bases, that are both somehow indexed. Now let's say the default game setup, would assign Player X to Base X. You can think of this as a rather simple set of pairs. (A "mapping" actually, in the mathematical sense).
F = { (Player 0, Base 0), (Player 1, Base 1), (Player 2, Base 2), (Player 3, Base 3), (Player 4, Base 4), (Player 5, Base 5) }
But, a mapping is just a 1-1, and onto function. So, if we write it in a functional form, it would look like:
{ F(Player 0) = Base 0, F(Player 1) = Base 1, F(Player 2) = Base 2, F(Player 3) = Base 3, F(Player 4) = Base 4, F(Player 5) = Base 5 }
Now, in a more computer science like way, let's implement the function using a lookup table:
int f[] = {0, 1, 2, 3, 4, 5};
Then to compute the function F, we simply index into the lookup table.

So, to see which base (number) a player (number) is associated with, we just index like so:
Code: [Select]
for (playerNum = 0; playerNum < numPlayers; playerNum++)
{
  baseNum = f[playerNum];
  // Insert code to create the identified base here (for the current player)
  CreateBase(playerNum, baseNum);
}

Now to randomize those locations, it's as easy as randomizing that lookup table.
Code: [Select]
int f[] = { 0, 1, 2, 3, 4, 5 };
const int numElementsInF = sizeof(f) / sizeof(*f);  // Byte size of array / byte size of 1 element

RandomizeList(numElementsInF, f);
for (playerNum = 0; playerNum < numPlayers; playerNum++)
{
  baseNum = f[playerNum];
  // Insert code to create the identified base here (for the current player)
  CreateBase(playerNum, baseNum);
}


Of course, the typical usage of this is with an array from 0..X, so why bother creating such a trivial array in those cases? That's where the other two functions in OP2Helper come in. The easiest way to create the bases is to have the base data specified in some sort of data structure, and then use identical code to create all the bases. To create the right base, you just pass a pointer to the right data structure (and a player number to create the base for). As there is already an array of base data in this case, that array is randomized directly, rather than creating a dummy mapping array. Using this idea, we get RandomizeBases() and RandomizeResources() (for beacons) in OP2Helper.


Advanced Uses
What if you only want to randomize some bases? Perhaps there is an AI that must always appear in the center. Or maybe there is a team game where the first 3 players are against the last 3 players, and you want to put teammates together.

This can be done using array slicing. Actually, that's mostly what it would be called in some other languages. In C/C++ arrays and pointers are type equivalent, and arrays tend to not have a size directly associated with them, so what we're doing is maybe a little lower level, and perhaps more error prone. (It's also the reason why there is a difference between delete and delete[]). But, the finer points of why type equivalence between arrays and pointers is probably a bad idea aside, let's see how this is done.
Code: [Select]
int a;
int b[]  = {1, 2, 3};

// Assume function f() takes an array size, and a pointer to the array
f(1, &a);  // Pass address of single variable 'a', and treat it as an array of size 1
f(3, b);  // Pass address of array b, giving it's full size of 3
f(2, b);  // Pass address of array b, giving only a partial size of 2
f(1, &b[1]);  // Pass address of the second element in b, and treat as an array of size 1
f(2, &b[1]);  // Pass address of the second element in b, and treat as an array of size 2

Basically, an array is a group of consecutive memory cells, and we're just being explicit about which ones to use as a new array/subarray. To apply this to the AI-out example above, we might write the randomize code like this:
Code: [Select]
int f[] = { 0, 1, 2, 3, 4, 5 };  // Note: Array of size 6. The last entry, Player 5 is the AI
RandomizeList(5, f);  // Note: Using 5 instead of 6 for the array size. That is, randomize the subarray consisting of the first 5 elements, but not the 6th (Player 5).

If instead, we want to group team members, in two groups of three people, we could do something like this:
Code: [Select]
RandomizeList(3, f);       // Randomize first 3 players  (Note: could have used &f[0] instead of just f)
RandomizeList(3, &f[3]);  // Randomize last 3 players

This of course generalizes, so we might want to randomize three teams of two players each like so:
Code: [Select]
RandomizeList(2, f);        // Players 0, 1
RandomizeList(2, &f[2]);  // Players 2, 3
RandomizeList(2, &f[4]);  // Players 4, 5
Note that these solutions above will exchange players withing the team slots, but won't change the order of the teams. So say, the first team is always at the top of the map, while the second team is always at the bottom of the map.

Now, what if you want to randomize the team locations as well. For this we could use a two level index structure.
Code: [Select]
// Note: **Untested**  Array syntax might be a bit off here
int teamIndex[] = { 0, 1, 2 };
int baseIndex[3][] = { {0, 1}, {2, 3}, {4, 5} };

RandomizeList(3, teamIndex);  // Randomize where to place teams
RandomizeList(2, baseIndex[0]);  // Randomize players on first team
RandomizeList(2, baseIndex[1]);  // Randomize players on second team
RandomizeList(2, baseIndex[2]);  // Randomize players on third team

for (playerNum = 0; playerNum < numPlayers; playerNum++)
{
  teamNum = playerNum / 2;  // Note: Rounds down, so Player (0, 1) -> Team 0, Player (2, 3) -> Team 1, Player (4, 5) -> Team 2
  teamBaseNum = playerNum % 2 // Index within a team, Players (0, 2, 4) -> 0, Players (1, 2, 5) -> 1
  // Remap player's team location, and then the base within that team's location
  baseNum = baseIndex[teamIndex[teamNum], teamBaseNum];
  // Insert code to create the base here
  CreateBase(playerNum, baseNum);
}
This would randomly place the 3 teams, each of which contain two base locations, and then randomly swap the players among those two base locations.


Finally, what if we want to have more possible team locations, and more possible player locations than can ever be filled at once? Well, we use something rather similar to array slicing here too. Let's say we have 5 possible team locations, with 3 possible base locations for 4 of the teams, and 2 possible base locations for 1 of the teams.
Code: [Select]
// Note: **Untested**  Array syntax might be a bit off here
int teamIndex[] = { 0, 1, 2, 3, 4 };
int baseIndex[5][] = { {0, 1, 2 }, {3, 4, 5}, {6, 7, 8}, { 9, 10, 11}, {12, 13} }; // Note: This will zero fill until the array is "rectangular" (It creates a 5 x 3 array if we use this notation)

RandomizeList(5, teamIndex);  // Randomize where to place teams
RandomizeList(3, baseIndex[0]);  // Randomize players on first team
RandomizeList(3, baseIndex[1]);  // Randomize players on second team
RandomizeList(3, baseIndex[2]);  // Randomize players on third team
RandomizeList(3, baseIndex[3]);  // Randomize players on fourth team
RandomizeList(2, baseIndex[4]);  // Randomize players on fifth team (only 2 slots)

for (playerNum = 0; playerNum < numPlayers; playerNum++)
{
  teamNum = playerNum / 2;  // Player (0, 1) -> Team 0, Player (2, 3) -> Team 1, Player (4, 5) -> Team 2
  teamBaseNum = playerNum % 2 // Index within a team, Players (0, 2, 4) -> 0, Players (1, 2, 5) -> 1
  // Remap player's team location, and then the base within that team's location
  baseNum = baseIndex[teamIndex[teamNum], teamBaseNum];
  // Insert code to create the base here
  CreateBase(playerNum, baseNum);
}

Note that the only thing that changed between this example and the previous, was the arrays, and the randomizing of those arrays. The loop didn't change. What happens, is the first 3 teams in the randomized team array are selected (the rest are ignored), and the first 2 base locations in the randomized base location lists are selected, and the rest (if it "exists") is ignored.

An example might look like this after randomization:

teamIndex[] = { 3, 2, 0, 4, 1 };  // Team locations (3, 2, 0) are used (4, 1) are ignored
baseIndex[5][] = { {1, 0, 2}, {who cares?}, {8, 7, 6}, {10, 9, 11}, {who cares?} };  // Bases (10, 9), (8, 7), (1, 0) are used (in that order), the rest are ignored



Other Uses and Generalizations
Pretty much anything that's like shuffling a deck of cards can be handled this way. Base locations is the most obvious one. Resource randomization was another obvious one. For things that are less specific, you can use the integer shuffling routine, and do the indexing yourself, like I've done in the above examples. Perhaps you could shuffle the turrets on a few combat vehicles.

You can also extend beyond the two level indexing. Maybe some base locations for a team overlap, and you want to partition them into disjoint sets of bases that don't overlap. A third level index could be used here to achieve this. Perhaps select a general location for each team, then select a layout of non-overlapping base locations, and then shuffle the players between each of the locations. You might also experiment with reusing some of the same places (numbers) in the final array. Something like: { { {0, 1, 2}, {0, 3, 4}, {5, 1, 6}, ... /* Other team layouts*/}, ... /* Other team locations */ }. Here is might be that base 0 and 5 are shifted by half a base size, and so they overlap. Same perhaps for bases 1 and 3, or 2 and 4. There's no reason you can't reuse the information for base 0 if the only difference in the layout is the shifting of locations of bases 1 and 2 (to 3 and 4). Or perhaps reuse base location 1 if you're shifting base locations 0 and 2 (to 5 and 6).

For these more deeply nested shufflings, you probably want to form a hierarchy, where you shuffle the order of sets independently of the contents of those sets. The ordering of the shuffle isn't particularly important. Maybe shuffle the largest set first, and then each of the contained sets, or you could start at the inside, shuffling the elements within a set, and then shuffling a set of sets. (Or really just do it in any "random" order).

Just pay attention to the indexing as you increase the depth. Generally, you use % to pull out the lower order index value and / to pull out the higher order index value, from some larger external index (such as a player num).
Code: [Select]
int array[7][5][6];  // Where the last [] is the innermost set
// Assume we want to slice it to have [3][1][2] (say 3 teams, 1 layout per team, 2 base locations selected per layout)
restOfIndex = playerNum;  // For illustration purposes
baseNum = restOfIndex % 2;  // Within a team
restOfIndex = restOfIndex / 2;
layoutNum = restOfIndex % 1; // Quite useless for 1 really, since you can only get 0
restOfIndex = restOfIndex / 1;  // Also quite useless for 1
teamNum = restOfIndex % 3;  // Actually the % ususally isn't needed for the outmost index, since the value should be less than what you would mod by
//restOfIndex = restOfIndex / 3;  // Useless, as you don't need to index past where we already were, but try to convince yourself that this value is 0. (Assuming you don't try to index past the end of the output array of what you're slicing)

Of course you'll probably want to optimize that a little, or at least write it nicer.
 

Offline Sirbomber

  • Hero Member
  • *****
  • Posts: 3238
Randomizing Starting Locations
« Reply #2 on: March 05, 2009, 07:33:37 AM »
While you did a very nice job of describing the technical aspects of randomizing bases, Hooman, I still have absolutely no idea of how to actually implement any of this.  For starters, which variables do what, and what should I assign to them?  Is numItems the number of bases available, or is that list?  Should I give the maximum number of players, or just the number actually in the game?

I'm sure I'll want to know more later, but this is all I can think of for now.
"As usual, colonist opinion is split between those who think the plague is a good idea, and those who are dying from it." - Outpost Evening Star

Outpost 2 Coding 101 Tutorials

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4955
Randomizing Starting Locations
« Reply #3 on: March 07, 2009, 12:30:49 PM »
Code: [Select]
void RandomizeList(int numItems, int list[])
The numItems parameter, is how many items are in the list. If your list consists of base locations, then yes, that would be the number of base locations. It's just the size of whatever array you're passing to the function. Compare that function to the base specific one.
Code: [Select]
void RandomizeStartingLocations(int numLocations, struct StartLocation location[])

You generally want to randomize the list independently of the number of players in the game. If you have 4 possible base locations, and you only randomized the first two because there were only two players, then you could never start in the last two base locations in a 2 player game. The number of players actually in the game is only used when creating the bases. Whichever ended up first in the randomized list are used. Look at the for loop code. [playerNum vs. numPlayers]
Code: [Select]
for (playerNum = 0; playerNum < numPlayers; playerNum++)


You still of course have to figure out how to map those base numbers to actual bases. Aside from a passing comment, I didn't really discuss that part. That is, with knowledge that player 0 gets base 3, and player 1 gets base 5, how to actually build those bases. I suggested a data structure approach, like that used in OP2Helper as it has many advantages. Although, you could also have written as a bunch of functions and a big switch statements. Kind of ugly, and uses more code than it needs, and perhaps not as easy to relocate bases, but it would work. You'd just have to write functions like: void CreateBase3(int playerNum); etc.
 

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4955
Randomizing Starting Locations
« Reply #4 on: March 08, 2009, 04:43:16 PM »
I templated the function so it can be used to randomly reorder a list of any data type.
Code: [Select]
// Note: Uses TethysGame::GetRand();
template <class ListItemType>
void RandomizeList(int numItems, ListItemType list[])
{
int next;
ListItemType temp;

// Randomly reorder the list (backwards)
for (numItems--; numItems; numItems--)
{
  // Determine which of the remaining locations to place next in the list
  next = TethysGame::GetRand(numItems+1);
  // Swap current item with next item
  temp = list[numItems];
  list[numItems] = list[next];
  list[next] = temp;
}
}

It will of course be slow if you pass it an array of large objects, as it will construct/destruct a lot of temporary objects during the swapping. In that case, you should really be passing it an array of pointers to those large objects. Of course that's only an issue really if you try to do something new with this. The existing uses will work exactly the same. I even added some macros so the template can be used when trying to call the old functions by their distinct names.

Code: [Select]
//void RandomizeResources(int numItems, struct BeaconInfo resources[]);
//void RandomizeStartingLocations(int numLocations, struct StartLocation location[]);

#define RandomizeResources RandomizeList
#define RandomizeStartingLocations RandomizeList

It will know how to instantiate the template based on the type of the array at the point of call.


So yes, like I said earlier. There was nothing in the code that really depends on the data type in the array. The reordering function can randomly reorder a list of any data type.