Sorted array/stack structures - advice please.

Hi,

(I'm really sorry to have ask another question about arrays - I promise I have searched the forums and read the many, many existing threads!)

I'm maintaining a structure similar to a local high score table but, rather than ranking the player's performance between successive games, I'm ranking the performance of the computer-controlled enemies within the current game. As the game progresses, new enemy instances are created based on the properties of the previously highest-performing instances. It's a kind of simple genetic evolutionary progression, in that I hope the "fittest" (i.e. best performing) enemies in each level pass on their behaviours to create more successful future generations of enemies.

Let's say for the sake of argument that my enemies have two properties - their movement speed and their rate of fire. And, when each enemy is destroyed I assign a "fitness" score that determines how successful they were (based, say, on how many ticks they stayed alive for).

So, a snapshot of my data might have the following information about enemies that have died so far:

Movement_Speed | Rate_Of_Fire | Stayed_alive_for

30             |     2        |    10

20             |     1        |     8

5              |     8        |    30

1              |     6        |    25

...

As enemies are destroyed, a new row is added to the table. Each level has a fixed number of enemies, so the maximum number of rows is known.

However, the number of columns may vary in the future (let's say I also decide to record the "Armour" property of each enemy in another column).

I need to be able to sort the data but only based on one key (how long they stayed alive for), in order to be able to select the best-performing parents from which to derive better enemies in the next generation. In fact, I'd quite like the table be maintained as a sorted list so that I could pick off the highest scoring enemy to date as at any time.

So, my question is, how would you best achieve this using the structures available in C2? I've considered various combinations of multiple 1d arrays - one for each property (but I couldn't work out how to sort them all based on the keys in one array?), a 2d array containing only the fitness score and an ID that points to a dictionary entry maintaining the other properties (but I couldn't work out how to push() onto a 2d array).... and I've rewritten my code so many times that it's got scraps of different ideas all over the place now.

Hoping that some of you brainy and helpful let might save me from this dirge of code spaghetti! Thanks in advance.

With a 2d array push() only sets Array.At(Array.Width-1, 0). You have to set the values at Array.At(Array.Width-1, 1), Array.At(Array.Width-1, 2), etc... manually with other actions.

So a 2d array could be used to store the data, all that's left is to implement a way to sort it.

Hi R0j0jound,

"With a 2d array push() only sets Array.At(Array.Width-1, 0)"

• Thanks for confirming that, which was the behaviour I was experiencing, although wasn't sure if it was something I was doing wrong! I couldn't find that limitation documented anywhere - it would be nice if the push() method documentation included the fact it only works with 1D. (Who do I suggest documentation edits to?)

"You have to set the values at Array.At(Array.Width-1, 1), Array.At(Array.Width-1, 2), etc... manually."

• Thanks. So, combining this with an Array -> Set size to (Array.Width+1, Array.Height, Array.Depth) action, I can simulate a push() onto 2d arrays.

"All that's left is to implement a way to sort it"

• Ah, I had glanced through the Array documentation and seen the Sort method, assuming this would already do what I wanted. Reading more closely, and experimenting a bit, I see that it doesn't! (i.e. there's no inbuilt method to sort an array by a key contained in an arbitrary X/Y row/column). Ok, well, my array is not too long, so even if I implement a naive sorting algorithm in O(n2) time, that should do fine.

Thanks again for your help.

tanoshimi, since it appears you only need the one set of data (the highest tick count and the corresponding configuration data), wouldn't it be possible to just maintain only the latest data with the highest tick count?

For instance, create the necessary instance variables in the enemy object, then only update the variables when the current tick rate is higher that the last recorded tick rate.

Wastrel - thanks for your suggestion.

The problem is that, rather than being strict copies of the best performing enemies from previous generations, enemies will mutate slightly between each generation as well, so there is very unlikely to have ever been a previous enemy with exactly the same configuration as this one. Therefore I don't think I can simply update a fixed array but need to insert new values.

I think I've got it working now. I just need to tidy up a few bits and bobs and then I'll post the whole .CAPX so you can see what I'm trying to achieve ;)

The problem is that, rather than being strict copies of the best performing enemies from previous generations, enemies will mutate slightly between each generation...

Understood. Keeping a history would be important for later analysis.

I look forward to seeing the .capx!

Another way to see it, it that, if you have to sort all your data, you'll have to manually swap each value (movement, rate of fire, etc)

I would use two arrays:

one with the data

one for sorting.

An also, if you want so use push, you can serialize your data in one string

here's how I would do it:

scoreData.capx

just input data like that:

100 0.5 20.4

(being movementSpeed, rateOfFire, stayedAliveFor)

tanoshimi

To clarify, pushing onto a 2d array will look like this:

Push back A on X axis

Set value at (self.Width-1, 1) to B

Set value at (self.Width-1, 2) to C

http://dl.dropbox.com/u/5426011/examples16/sorted_runs.capx