GMLscripts.com

Discuss and collaborate on GML scripts
Invert

You are not logged in.

#1 2010-08-29 12:50:19

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

CHALLENGE: Avoidance AI

I was going to post this thing I was working on but I thought maybe it would make a good topic for an AI challenge.

Mission:
Construct an AI for objAvoider to avoid objEnemy while also attempting to stay on the screen. A collision counter has been provided. You may use as many or as few objEnemy instances as your AI can handle. By default, 30 are created by the room. No other alterations should be made. The AI does not need to be perfect, it should just be interesting and moderately effective. objAvoider may not exceed a speed of 4 pixels per step. The AI is given 3 seconds to get objAvoider to a safe starting position.

With 30 enemy instances, a stationary avoider averages about 30 collision per minute. You're AI should try to do better. wink

Project Template:
link.png

Tentative Deadline: September 15th

Anybody up for it?

UPDATE!

Jalb has been kind enough to make an 4 round elimination tournament arena where all entrants compete against each other at the same time. Super, super cool!
http://www.gmlscripts.com/forums/viewto … 2506#p2506

Last edited by xot (2010-09-18 04:51:25)


Abusing forum power since 1986.

Offline

#2 2010-08-31 13:58:48

OpticalLiam
Member
Registered: 2007-10-11
Posts: 8

Re: CHALLENGE: Avoidance AI

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?

Last edited by OpticalLiam (2010-08-31 14:40:24)

Offline

#3 2010-08-31 14:41:09

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: CHALLENGE: Avoidance AI

Yeah, the video is my solution. I had a stupidly simple idea for how to do this and it worked decently after an hour of tweaking. I can see a lot potential with the technique, although quirks with Game Maker (and other factors), limit how much you can use it. With some changes to the GM engine, it could probably run much faster. I think some other interesting behaviors might be possible with very few changes (eg. following, leading, attacking from certain relative angles).

Haven't given much thought to judging. I'm not really looking for "winners" although I'm not opposed to the idea. Collisions per minute is a fair criteria, with penalties for leaving the screen. I'm mostly interested in just seeing different working solutions, which is why I'm flexible about the number of enemies. Dodging the default 30 enemies may not be a trivial task! I want this to be fun and productive, not be impossible and frustrating.

I suppose if picking a winner is absolutely necessary, it could be whichever AI handles the most enemies while staying below a certain threshold of collisions per minute. Other criteria could be adjusted to increase the challenge as well, such as increasing enemy speed, or decreasing avoider speed, or reducing the acceptable area the avoider can move within. If someone with a great solution wants to up the ante like that, I'm all for it.


Abusing forum power since 1986.

Offline

#4 2010-09-01 10:53:45

OpticalLiam
Member
Registered: 2007-10-11
Posts: 8

Re: CHALLENGE: Avoidance AI

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?

Last edited by OpticalLiam (2010-09-01 11:04:28)

Offline

#5 2010-09-01 14:13:43

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: CHALLENGE: Avoidance AI

I was leaving the testing up to you. You can submit as many demos as you like, but one of them should just be the AI in the default set up, which is the one that will be ranked.

My plan was to create a suite of different tests to evaluate the AIs on equal ground (eg. seeded random numbers, special configurations). The exact nature of those tests should be a bit of a mystery, but I'm totally open to suggestions. If anyone provides some interesting demos or test templates, I'll probably appropriate them.

If you want to post your AI now, that's perfectly fine. If you do, I'll probably post mine as well. I was planning on tweaking it some more, I just haven't had the time. 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.

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.


Abusing forum power since 1986.

Offline

#6 2010-09-01 20:06:17

OpticalLiam
Member
Registered: 2007-10-11
Posts: 8

Re: CHALLENGE: Avoidance AI

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...

Offline

#7 2010-09-01 20:41:44

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: CHALLENGE: Avoidance AI

I was running the room around 200 fps to do my tests. I used a frame counter to track "time". 200 fps was as fast as I could run, but I should be able to improve that with some small changes.

When I say under 1 per minute, I mean just barely. Some tests were way over, some way under. I was surprised to see such large variances over runs of those lengths. Definitely need to run extended and repeated trials to get good performance estimates.


Abusing forum power since 1986.

Offline

#8 2010-09-02 07:17:42

OpticalLiam
Member
Registered: 2007-10-11
Posts: 8

Re: CHALLENGE: Avoidance AI

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.

Last edited by OpticalLiam (2010-09-02 07:30:42)

Offline

#9 2010-09-02 17:29:09

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: CHALLENGE: Avoidance AI

The default template does not use a randomization seed, so it produces a different sequence each time it is run. That's why the tests can vary. I'm just surprised they vary so much. I haven't yet tried any extended runs.

We discussed the quality of GM's PRNG in this old topic at the GMC forums. It appears that it's actually pretty decent. I can't speak to the newer seeded version, but I suspect it uses the same algorithm.

http://gmc.yoyogames.com/index.php?showtopic=159882

In your linked article, I was especially interested to read about periodicity problems with low order bits. That shouldn't be a problem if Game Maker uses the (alleged) Delphi algorithm (and I have every expectation that it does) since it only returns the top 32 bits. That said, if a person were using random_get_seed() for random integers, that does demonstrate apparent periodicity (eg. the returned values alternate between even and odd).


Abusing forum power since 1986.

Offline

#10 2010-09-10 08:51:09

~Dannyboy~
~hoqhuue(|~
From: Melbourne, Australia
Registered: 2009-10-02
Posts: 21
Website

Re: CHALLENGE: Avoidance AI

Ooh, I think I'll give this a shot. I whipped up something really quick but I'll improve it before I post. The basic idea of my strategy is to:

Spoiler

Identify the most immediate threat (currently using instance nearest) and avoid it (currently using motion_add in the opposite direction). Also it tries to go towards the centre whenever it can. Simple.

It's better than sitting still but definitely needs improving before it could compete with yours! cool

EDIT: What sort of useless spoiler tag is that??? tongue

Last edited by ~Dannyboy~ (2010-09-10 08:53:20)

Offline

#11 2010-09-10 15:27:20

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: CHALLENGE: Avoidance AI

A Challenger Appears!

I must have broken the spoiler tag when I upgraded the forum software. Sorry about that. Should be fixed now, but may require refreshing or clearing your browser cache for the CSS change to kick in.

Looking forward to seeing your results.


Abusing forum power since 1986.

Offline

#12 2010-09-10 21:06:00

~Dannyboy~
~hoqhuue(|~
From: Melbourne, Australia
Registered: 2009-10-02
Posts: 21
Website

Re: CHALLENGE: Avoidance AI

Alright, I've now made a more accurate threat-o-meter to detect which enemy is the greatest threat, also I've made the evasive action to move away from the point of closest approach rather directly away from the enemy. With these improvements I ran the test for 3 minutes, 6 collisions for the first minute, 3 for the second and 4 for the third... I've got a long way to go yet!

Now that I have a decent method of detecting and avoiding threats I think I might try a weighted average rather than just focusing on a single threat, I'll let you know how it goes.

EDIT: Weighted average results so far: 7 collisions in 5 minutes. I'm catching up!

Last edited by ~Dannyboy~ (2010-09-10 21:53:32)

Offline

#13 2010-09-10 21:58:37

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: CHALLENGE: Avoidance AI

You should state the move method should be motion add maybe... I was getting good results with mp_potential_step

Offline

#14 2010-09-11 04:00:27

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: CHALLENGE: Avoidance AI

~Dannyboy~ wrote:

EDIT: Weighted average results so far: 7 collisions in 5 minutes. I'm catching up!

Impressive. It sounds like you're taking the approach I initially considered.

icuurd12b42 wrote:

You should state the move method should be motion add maybe... I was getting good results with mp_potential_step

I am using motion_add myself. I never considered the motion planning functions for this. I didn't expect they would work very well. Just how good are these results? Embarrassingly good?


Abusing forum power since 1986.

Offline

#15 2010-09-11 05:52:01

~Dannyboy~
~hoqhuue(|~
From: Melbourne, Australia
Registered: 2009-10-02
Posts: 21
Website

Re: CHALLENGE: Avoidance AI

After fixing a stupid mistake with the evasion code, the direction was wrong, I don't know how it was working... And a bit more tweaking I've managed to get it down to about 0.4-0.8 collisions per minute, averaged over a full hour, I ramped the room speed up a little wink. I think that's about as good as I'm going to get from this method. I'm going to have to think up a new method to get any better.

Some things I've noticed so far:
1) Your method is much smoother than mine. Yours manages to move towards the quiet spots somehow. Mine is much more jerky, jumping out of the way at the last moment. I'm curious as to how you managed it.
2) Tweaking is annoying difficult. The values I get could be different by double or half when tested over times as long as 10 minutes. I wonder if there's a better, more stable, method to assess the performance than just collisions / time.

Last edited by ~Dannyboy~ (2010-09-11 05:56:24)

Offline

#16 2010-09-11 11:45:02

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: CHALLENGE: Avoidance AI

Wow, amazing results!

I've had similar experiences to you with tweaking. My method is really finicky at the moment, which I consider a major fault. It doesn't tune itself well. I have to play with the magic numbers to get it to perform well depending on the number of enemies. When I get some time to play around with it again I'll see if I can improve that. There are some other flaws that need to be fixed as well. My biggest problem is keeping the avoider on the screen and recovering when it wanders off.

I'm having strong doubts that I can get the collision rate as low as yours without employing a hybrid method.


Abusing forum power since 1986.

Offline

#17 2010-09-11 21:11:50

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: CHALLENGE: Avoidance AI

combined with fiddling the enemy scale up (2-3) prior and scaling them back (to 1) after mp_step... not bad. but the moment I add the need to go center, it starts to fail especially if the movement needed is too small. the AI stops and dont avoid anything, letting itself get hit when ther is every chance of avoidance.

Last edited by icuurd12b42 (2010-09-11 21:12:32)

Offline

#18 2010-09-14 00:41:56

jalb
Member
From: Texas
Registered: 2010-09-14
Posts: 12
Website

Re: CHALLENGE: Avoidance AI

Decided to jump on board since there's only two days left (almost one).

I managed to get something working (not pretty to look at but it works).  Recorded for 2 minutes and had 2 collisions.

Though I gave up once GM started acting weird.  Wasn't applying any changes I had made once I clicked "Run the game"; had to export an executable and run it that way instead (persisted even after restarting GM, dunno what the deal is).

Got nothing better to do, so I suppose I should explain how it works.  Basically it checks 36 different directions (i=0; i<360; i+=10), and for each direction it checks how many steps it'll take in that direction to not be in the path of an enemy (up to 50 pixels in front of them).  Then out of all the directions it'll pick the one with the fewest steps to take to be out of harm's way.  If it's already out of harm's way it'll try to make its way towards the middle of the screen (to avoid going out of the screen).  Also, it moves at 4 pixels/step, and averages at 30 FPS when nothing is near and can drop down to about 26 FPS when surrounded by enemies.

Last edited by jalb (2010-09-14 00:53:55)

Offline

#19 2010-09-14 01:07:31

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: CHALLENGE: Avoidance AI

Cool! Thanks for jumping in, jalb, and welcome to the forums.

Nice video. Your AI does pretty good. I can't wait to dump it into the torture chamber I'm making.

That's a weird GM problem you're having. I think I've heard that reported before, but I don't recall if there was a solution. I seem to remember it being one of those "fixed itself" problems. hmmm

EDIT:

Ahh, I see you had more to say. Thanks for the explanation, that's an interesting approach. Mine works similarly -- but is also very different. I'm thinking you could probably get a good boost in speed with faster collision checking. The range_finder script posted here might be just the thing. Then again, that might not be the part that's slow since I'm not really sure how you've coded it, or how you do the "fewest steps" check. I guess I'll know soon enough. smile

Last edited by xot (2010-09-14 01:15:39)


Abusing forum power since 1986.

Offline

#20 2010-09-14 01:42:02

jalb
Member
From: Texas
Registered: 2010-09-14
Posts: 12
Website

Re: CHALLENGE: Avoidance AI

xot wrote:

That's a weird GM problem you're having. I think I've heard that reported before, but I don't recall if there was a solution. I seem to remember it being one of those "fixed itself" problems. hmmm

And that's just what it did.  Weird, I didn't even restart GM, just let it set for a while and now it works.

xot wrote:

The range_finder script posted here might be just the thing.

Thanks for the script, but I didn't need it.  Made a few adjustments and now not only is the movement much smoother, but I've had slightly better results (2 hits in 6 minutes, but that could be coincidence), and I run at constant 30 FPS even with loads of enemies nearby. smile

Meant to go to bed early but when I saw this I couldn't resist.  Dammit. laugh

Offline

Board footer

Powered by FluxBB