Randomized lists

Discuss programming in the QuakeC language.
Post Reply
mankrip
Posts: 924
Joined: Fri Jul 04, 2008 3:02 am

Randomized lists

Post by 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.
Ph'nglui mglw'nafh mankrip Hell's end wgah'nagl fhtagn.
==-=-=-=-=-=-=-=-=-=-==
Dev blog / Twitter / YouTube
Spike
Posts: 2914
Joined: Fri Nov 05, 2004 3:12 am
Location: UK
Contact:

Re: Randomized lists

Post by 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
Posts: 133
Joined: Mon Aug 30, 2010 3:29 pm
Location: Australia

Re: Randomized lists

Post by andrewj »

Has nobody ever made a decent QC implementation of a list datatype?
Spike
Posts: 2914
Joined: Fri Nov 05, 2004 3:12 am
Location: UK
Contact:

Re: Randomized lists

Post by 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
Posts: 2292
Joined: Sat Jan 12, 2008 1:38 am

Re: Randomized lists

Post by 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);
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
mankrip
Posts: 924
Joined: Fri Jul 04, 2008 3:02 am

Re: Randomized lists

Post by 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.
Ph'nglui mglw'nafh mankrip Hell's end wgah'nagl fhtagn.
==-=-=-=-=-=-=-=-=-=-==
Dev blog / Twitter / YouTube
andrewj
Posts: 133
Joined: Mon Aug 30, 2010 3:29 pm
Location: Australia

Re: Randomized lists

Post by andrewj »

Spike wrote: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...
Post Reply