Randomized lists

[mankrip]

When calling random() multiple times, there's no guarantee that it won't return similar results. Also, it gets more complicated when we want to randomize a list of values while ensuring that none of the values in the list gets repeated.

So, I've created this:

Code: Select all

// random listing
// entities should have their .listname set before RandomizeList is called
// TODO: allow entities to be featured in multiple lists, using float(.string fieldname, string s)RandomizeList?
.string
   listname
   ;
.float
   listcount
,   listindex
,   listused
   ;
.entity
   listhead // first item
,   listprev
,   listcurr // current item, must be accessed from .listhead only
,   listnext
   ;
float (string s) RandomizeList =
{
   entity
      e
      ;
   float
      c
   ,   i
      ;
   e = find (world, listname, s);
   if (e == world)
      return 0;
   // counts items
   c = 0;
   while (e != world)
   {
      c = c + 1;
      e.listused = FALSE;
      e = find (e, listname, s);
   }
   // randomize their indexes
   i = c;
   do
   {
      e = find (world, listname, s);
      if (e == world)
         e = find (e, listname, s);
   //   if ( (e.listused == FALSE && random () <= (1 / c)) || i < 2) // todos os itens igualmente randomizados
      if (e.listused == FALSE && random () <= (1 / i)) // randomização decrescente
      {
         e.listused = TRUE;
         // fazendo assim, o listindex/listcount do primeiro item sempre será zero, e o do último item será 1
      //   e.listcount = c - 1; // last index (total number of items, minus this one)
      //   e.listindex = i - 1; // indexes starts from zero
         // fazendo assim, listindex/listcount retornará 50% para o item 1 duma lista contendo 2
         e.listcount = c; // total number of items
         e.listindex = i; // indexes starts from 1

         i = i - 1;
      }
   } while (i > 0);
   // returns the amount of items
   return c;
}
entity (string s, float c) MakeList =
{
   entity
      e
      ;
   e = find (world, listname, s);
   if (e != world)
   {
      bprint ("MakeList: list \""); bprint (s); bprint ("\" already exists\n");
   }
   else
   {
      // creates items
      entity
         p
         ;
      float
         i
         ;
      i = c;
      while (i)
      {
         e = spawn ();
         e.listname = s;
         e.listused = FALSE;
         e.listcount = c; // total number of items
         e.listindex = c - i + 1; // indexes starts from 1
         if (i == c) // first item
            e.listhead = e;
         else
         {
            e.listhead = p.listhead;
            e.listprev = p;
            p.listnext = e;
         }
         p = e;
         i = i - 1;
      }
      // last item
      e.listnext = e.listhead;
      e.listhead.listprev = e;
      // current item
      e.listhead.listcurr = e.listhead;
   }
   return e.listhead;
}
entity (string s) NextListItem =
{
   entity
      e
      ;
   e = find (world, listname, s);
   if (e == world)
   {
      bprint ("NextListItem: list \""); bprint (s); bprint ("\" doesn't exist\n");
   }
   else
   {
      e = e.listhead.listcurr = e.listhead.listcurr.listnext;
      if (e == e.listhead)
         RandomizeList (s);
   }
   return e;
}

The code isn't 100% polished, and some of the comments aren't in English, but it works.

The problem is that randomizing (in my case, a list of 19) items can very often make the QC loop counter exceeds the 100 (or 1000, can't remember) cycles, thus crashing the game to the console. And even when it works, it's almost always too slow, freezing the whole engine for many seconds.

For some reason I feel that there may be a way to get the same results (randomizing a whole list of sequential values, with no repetitions), without calling random() more than once. Maybe not possible in QC, but in a new built-in function.

[Spike]

if each must be unique, can you not just generate a list of (slot/numslots) and then randomly reorder that list instead? either way it might be faster to scan a sorted list for duplicates.

but yeah, there's far to much find()ing going on.

[andrewj]

Has nobody ever made a decent QC implementation of a list datatype?

[Spike]

data type? what's that? :s
QC doesn't have datatypes. It has entities. It has floats. It has strings. It has vectors. It has fields. It has functions. And that's it.

[mh]

I'd vote for hacking around this engine-side rather than QC-side myself; QC is just not really good at all at this kind of code.

To randomize an arbitrary list like this, you add a new member to your type struct - let's call it a key. Each time you wish to randomize the list you first assign each key a random number, then after that you sort the list on that key (hopefully using something better than bubble sort - qsort is sufficient for this kind of runtime sorting provided you don't overdo it). That gives you a guaranteed each-item-appears-only-once behaviour with no messy (and slow) checking. If you want to restore the original order you add another new member storing the item's slot number in the original order, and resort based on that. Pseudocode:

Code: Select all

for (int i = 0; i < numitems; i++)
{
    items[i].key = rand ();
    items[i].baseorder = i;
}

// sort by key for random order
qsort (items, key);

// restore original order
qsort (items, baseorder);

[mankrip]

Well, I've fixed it. Now it only uses random() once for each item:

Code: Select all

float (string s) RandomizeList =
{
   entity
      e
      ;
   float
      c
   ,   i
      ;
   e = find (world, listname, s);
   if (e == world)
      return 0;
   e = e.listhead;
   do
   {
      e.listused = FALSE;
      e = e.listnext;
   }
   while (e != e.listhead);

   c = e.listcount;

   // randomizes indexes
   do
   {
      for (i = random () * c ; i >= 0 ; i--)
         e = e.listnext;
      while (e.listused == TRUE)
         e = e.listnext;
      e.listused = TRUE;
      e.listindex = c;
      c--;
   } while (c > 0);

   // returns the amount of items
   return e.listcount;
}

It can be optimized a bit more still, but for now it's good enough.

I've also realized that probably the only way to use random() only once for the whole list would be to precalculate all possible variations of the list, and index those variations in another list; a list of lists. That would consume too much memory, and precalculating the lists would be exponentially slower.

I'm trying to not touch on the engine code before I get most of the other work (including the QC code) done.

[andrewj]

QC doesn't have datatypes. It has entities. It has floats. It has strings. It has vectors. It has fields. It has functions. And that's it.

I know all that.

I'm talking about a nice little QC library to handle lists:

Code: Select all

entity() list_create = ...
entity(entity L) list_head = ...
entity(entity L) list_tail = ...
entity(entity L, float index) list_access_at = ...
entity(entity L, entity N) list_add_head = ...
entity(entity L, entity N) list_add_tail = ...
entity(entity L, entity N) list_remove = ...
entity(entity L, float index) list_remove_at = ...
// et cetera... et cetera...