GMLscripts.com

Discuss and collaborate on GML scripts
Invert

You are not logged in.

#1 Re: GML Creations » CHALLENGE: Conway's Game of Life » 2011-04-29 15:58:33

The code is seemingly convoluted because GM is so restrictive when it comes to image manipulation, and we have to use hacks to achieve simple filters such as thresholding.

Xot provided great commentary on his code, but I will give a shorter more abstract summary for those who are still puzzled. The method is actually quite simple, but clever - there are three key processes.

First is the neighbour accumulation, where the sums of the number of neighbours are calculated on a surface by performing a 2 x 2 box-blur. In GM we do this by additively drawing the surface 9 times at offsets [(-1,-1), (0,-1), (1,-1) ...].

Then for each of the rules of the game of life, we use threshold filters to remove pixels that are lower than a certain intensity.

In GM we do threshold filtering by first drawing a surface (here it's the neighbour accumulation surface) with a certain gray-value color  - the default is c_white, but we instead use some lower gray-value, which has the effect of adjusting the intensity of all pixels in preparation for the next stage. We then contrast-ramp the surface up by drawing the surface to its self many times (for our purposes we need 8 passes) with a special contrast blend mode, which has the effect of intensifying the pixels we want to keep (making them whiter) and reducing the ones we don't (making them blacker). So, the value of gray used before ramping essentially sets the threshold level that the ramping stage works on (and might tricky to choose, I just used experimentation).

In my implementation, each rule has its own surface, to store the result of the rule and requires other temporary surfaces (reusing others) to generate them.

The under-population rule just requires a single threshold pass and will be additive in the final stage.
The over-population rule requires a single threshold pass, and a mask, but will be subtractive.
The birth rule is a bit trickier, and requires two thresholds (lower and upper) merged together, and naturally the result is also additive.

Then the final stage is to correctly merge each rule together, which is adding and subtracting the above rule surfaces as required. This is done on the main surface, which is then fed as the seed in the next step.

Hope that clears it up a bit more!

#2 Re: GML Creations » CHALLENGE: Conway's Game of Life » 2011-04-28 16:23:52

Awesome, I compared xot's with mine and they work in almost exactly the same way overall, only his is a tiny bit faster (and uses one less surface, I was lazy with my reuse!).

xot wrote:

I do something naughty, which is draw a surface to itself.

Yeah, this technique is useful for quite a lot of other interesting things I've done in the past (maybe I'll post them around here soon).

xot wrote:

The significance of this is that this CA engine is in some ways three times as fast as it appears; it can run three different patterns simultaneously (red, green, and blue) without any impact on performance.

Aha, so that's what that was about, I didn't really think of that. A neat by-product of the method, though I'm not sure if it can be put to too much use (other than novelty).

xot wrote:

Although I've foregone improvements, I have spent some time working out (on paper) some other CAs running with this same technique. If I get them going, I'll post the results here.

I've also (briefly) thought about how these methods can be generalised to create other rules and other CAs, I might have a go at that too later on. In fact, during my experimentation I ended up with many awesomely weird CAs, some that spread like blobs and even some that generated mazes.

I still think it may be possible to reduce a lot of the drawing in our solutions, and get huge speed increases, anyone up to trying?

#3 Re: GML Creations » CHALLENGE: Conway's Game of Life » 2011-04-28 13:27:23

Here is my surface-based solution:

GMK, EXE

A 575 x 525 simulation is running at about 220fps on my machine. I have no idea how well this will work on other machines, it's pretty graphics memory and fill-rate heavy. It's also probably far from the best way of going about it, as I was only able to spend a few hours on it (due to my dissertation, damn you for telling me about this challenge, xot!). It was made in a pretty experimental way so I didn't really calculate anything properly. It could probably be made much more efficient by someone smarter than me!

Cheers.

#4 Re: GML Creations » CHALLENGE: Avoidance AI » 2010-09-14 20:05:47

Here's my entry:

http://dl.dropbox.com/u/1672291/avoider-challenge.gmk

I've not really had much time to test it, but it does fairly well. Here's how it works:

Spoiler

This solution simply models the enemies as applying a repulsive spring-like force on the avoider, which is accumulated over every enemy and then the resultant force applied to the avoider. In practice this works pretty well, although it is fairly naive. It could probably be improved by changing the force model to something more exponential, but during my short time playing with it I couldn't come up with a function that worked better than the current one.

#5 Re: GML Creations » CHALLENGE: Avoidance AI » 2010-09-02 07:17:42

Definitely need to run extended and repeated trials to get good performance estimates.

Yeah I thought this too. Theoretically it should make no difference how many times you restart the test, compared to just running it constantly, as test conditions should not change. That said, I'm doubtful as to how good GM's random generator is, as I imagine that's where the problem lies. I think Delphi uses a basic Linear congruential generator.

#6 Re: GML Creations » CHALLENGE: Avoidance AI » 2010-09-01 20:06:17

I do think delaying your post might be good. I'd like to give potential entrants a chance to come up with something without being unduly influenced by other solutions.

I agree, I'll hold it back for a while then.

How about posting some claims first? For instance, I claim my AI can handle 30 enemies in the default setup at a collision rate of less than 1 per minute averaged over six runs of ten minutes each.

That's pretty good actually. I just ran mine default for 5 minutes and it came out bang on 3 per minute. It just occurred to me that I can simply whack up the room speed to simulate the same amount of time, I think...

#7 Re: GML Creations » CHALLENGE: Avoidance AI » 2010-09-01 10:53:45

Well I didn't mean there needs to be a winner, I just think there should be a way of testing the performance of our solutions. If you built some tests / stats into the GMK it might also help people see how certain changes improve or worsen their avoider's performance (or maybe you're just leaving that to us!). Oh and I think there should probably be some benchmark, such as the average collisions per minute for an avoider that doesn't avoid at all. I was thinking, too, that currently this situation is in some respects (not all) 'perfectly' solvable (read: best possible solution, situation allowing) by brute force search - i.e. the motion of the enemies is predictable. Not that it's necessarily a bad thing, and it's obviously impractical, but maybe someone will go down that road to some extent...

Anyway, I've finished with my solution for now - shall I just post it here or?

#8 Re: GML Creations » CHALLENGE: Avoidance AI » 2010-08-31 13:58:48

I've just come up with a quick naive solution that works fairly good. I'm intrigued - is the video your solution? It appears to work pretty well!
How are you going to judge / test the solutions? I say maybe run each one for 5 minutes and work out the collisions per second or something.
I imagine you'll also test what happens when you ramp up the number of enemies and the speed they move?

Board footer

Powered by FluxBB