# GMLscripts.com

Discuss and collaborate on GML scripts

You are not logged in.

## #21 2010-09-14 12:35:34

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

### Re: CHALLENGE: Avoidance AI

My modem got fried and I got real sick. Now my modem is fixed, but not me. Here a few methods

Offline

## #22 2010-09-14 14:25:17

xot
Registered: 2007-08-18
Posts: 1,201

### Re: CHALLENGE: Avoidance AI

Great! I was afraid you weren't going to be participating, icuurd12b42.

Looks like you've submitted not one, but four different AIs. Fantastic! I've tried them out but I haven't examined them.

I still don't have GM8 Pro. Since you used data structures I had to convert your project to an earlier version of Game Maker using LateralGM. I hope this doesn't somehow affect the results. That's something I hadn't considered until now.

Just a reminder to everyone else:

Abusing forum power since 1986.

Offline

## #23 2010-09-14 18:16:04

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

### Re: CHALLENGE: Avoidance AI

Weird, I used GM7, really. I got a real wicked flue. I'm afraid I wont have a chance. But I liked experimenting with various metods.

The grid method makes hills in a grid... or waves. the ai just flows down the hill

Last edited by icuurd12b42 (2010-09-14 18:16:23)

Offline

## #24 2010-09-14 18:47:17

xot
Registered: 2007-08-18
Posts: 1,201

### Re: CHALLENGE: Avoidance AI

You're right, of course. It loads fine in GM7. The problem was it loaded automatically in GM8 because that's the last version I used. I've had to convert so many GM8 projects lately, I automatically assumed yours needed it as well. Dumb me.

icuurd12b42 wrote:

The grid method makes hills in a grid... or waves. the ai just flows down the hill

Flows down the hill, eh? Very, very interesting.

Get well soon.

Abusing forum power since 1986.

Offline

## #25 2010-09-14 20:05:47

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

### Re: CHALLENGE: Avoidance AI

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.

Offline

## #26 2010-09-14 23:08:44

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

Neat

Offline

## #27 2010-09-14 23:40:16

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

### Re: CHALLENGE: Avoidance AI

Here's mine.  It's GM8 but I'm pretty sure it should work once converted to GM7.

I also didn't have a lot of time to clean up the code but it's pretty easy to understand (I also added lotsa comments).

Last edited by jalb (2010-09-15 06:23:10)

Offline

## #28 2010-09-15 02:59:54

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

### Re: CHALLENGE: Avoidance AI

Here's mine. It's GM8, should run on lite no problems.

And here's a version of it with some tacked on overlay stuff I used for debugging, just in case you're interested.

The grid method makes hills in a grid... or waves. the ai just flows down the hill

That's sounds really close to one of my ideas... I just couldn't be bothered trying to make it work, I'm glad someone did!

Don't miss out on the deadline xot!

Last edited by ~Dannyboy~ (2010-09-15 03:17:35)

Offline

## #29 2010-09-15 17:42:30

xot
Registered: 2007-08-18
Posts: 1,201

### Re: CHALLENGE: Avoidance AI

OK, here's mine:

It requires GM7 Pro because it uses sprite creation and surfaces. If you have GM8, you'll have to modify the sprite creation code. Sorry. Just find that line and remove two of the "false" arguments.

Based on what he's said, I believe it works very, very much like icuurd12b42's grid solution, if I understand it correctly.

Solution:
Treat each enemy as a potential field and compute the gradient of the local area to find the direction to the nearest minima. If I knew calculus this might be done more simply and accurately. Not sure if it would be any faster. I used an image based approach drawing each enemy as a blob on a surface with an additive blend. Local pixel intensity is measured to compute the gradient. Pixel sampling is pretty slow, but generating the surface data is very fast, so I hope it's an overall gain. The main problem with using surfaces is that they can only hold integer data in a finite range. When too many enemies are in one area, the data plateaus and it is impossible to compute a gradient. I sample at random radii to mitigate ambiguous cases like these and to vary the locality when searching for minimas.

Hold Shift to see the surface used to compute the gradient.

I didn't get a chance to tweak this some more like I wanted to. This is essentially the same as the one used to create the original video. Improvements could probably be made by changing the sampling area to a circle rather than a rectangle, as well as tweaking a few magic numbers and changing the character of the "blob" sprite. I planned to do this but something came up at the last minute and I ran out of time to work on it.

Abusing forum power since 1986.

Offline

## #30 2010-09-15 19:44:58

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

### Re: CHALLENGE: Avoidance AI

That's a really creative solution xot! Showing the surface really helps to visualise what's going on. One thing I did notice which I thought was a little odd was that it seems that you're treating the area behind the enemies as dangerous as the area in front, wouldn't it be better to have a less symmetrical mask for the enemies?

Offline

## #31 2010-09-15 21:27:20

xot
Registered: 2007-08-18
Posts: 1,201

### Re: CHALLENGE: Avoidance AI

Yeah, that's one of the things I wanted to experiment with some more.

I started with a beam-shaped gradient that extended ahead and behind the enemies. Like you, I noticed the pointlessness of avoiding enemies that had already passed. I changed it so that the beam only projected to the front, but still it seemed pointless to avoid enemies that were completely across the screen. Also the popping effect when an enemy suddenly jumped to the opposite side of the screen was causing problems.

Next I localized the effect by changing the beam to a wedge-shaped gradient. That was an improvement, but the discontinuity of the hard edges at the rear of all these shapes seemed to cause problems.

That's when I switched to the ball shape which has no sharp edges. That worked so much better I stuck with it, although what I really wanted was a teardrop with a smooth transition all the way around it. I never got around to making it.

Abusing forum power since 1986.

Offline

## #32 2010-09-15 22:26:12

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

### Re: CHALLENGE: Avoidance AI

There you go. that is my method too. I did not punch a bowl though.. I was too ill to think how to do this on the grid so I just hacked in a move center call... Using the surface as a grid is smart, even if get_pixel is slow (too slow)

So, I won? LOL...

Remember how you helped fixing my tank explosion? You could have made your surface the size you wanted in the same way.

Can you explain this

t = 1+speed;
repeat (7) t += random(1);
for (i=0; i<9; i+=1) p[i] = 0;
for (s=t; s<=3*t; s+=t)

Last edited by icuurd12b42 (2010-09-15 22:35:43)

Offline

## #33 2010-09-15 23:28:16

xot
Registered: 2007-08-18
Posts: 1,201

### Re: CHALLENGE: Avoidance AI

Remember how you helped fixing my tank explosion? You could have made your surface the size you wanted in the same way.

Yeah, that could be a major improvement. I never considered it because I never got to a point where I was ready to optimize, and I was spending most of my time examining the the entire potential field to see how it behaved while trying to control the saturation and dynamic range of the limited precision accumulator surface.

As for the code, it's pretty ad hoc. The radius of the detection rings increases with the speed of the avoider to give it a better chance of seeing what's ahead of it. Randomization seemed to help it evaluate the situation with greater apparent resolution than would otherwise be practical, while reducing the chances of things slipping between rigidly spaced detection rings. Without it I often had problems with the avoider straddling peaks instead of seeking valleys. I use multiple scales because a fixed radius always seemed to have certain cases where the avoider would get confused or miss something it should have seen either nearby or far.

t = 1+speed; // This is the base radius in pixels. The faster the avoider is moving, the greater the radius and "look ahead".
repeat (7) t += random(1); // This adds between 0 and 7 pixels to the base radius, with approximately normal distribution about 3.5
for (i=0; i<9; i+=1) p[i] = 0; // Sets the sample accumulators to zero because I'm doing add-and-assign in the inner loops
for (s=t; s<=3*t; s+=t); // This loop sets the sampling radius at 1x, 2x, and 3x the base size.

Abusing forum power since 1986.

Offline

## #34 2010-09-16 00:37:19

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

### Re: CHALLENGE: Avoidance AI

Not sure if the random really helps though, but I hear even we do this with our eye, twitches, it helps.

The grid I had the idea from this
http://host-a.net/icuurd12b42/WeigthedTiles.gmk

which is a concept I thought of helping out for a tron game AI... It stems from an idea I had for a multilevel pinball table, hard to believe where things get started.

Offline

## #35 2010-09-18 01:50:27

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

### Re: CHALLENGE: Avoidance AI

I had about 6 hours to kill today, so I threw all of our entries into one game (only one of icuurd's, the one who performed best as far as I could tell).  I originally uploaded a video of it and posted it, but there was some technical difficulties and the video was only halfway processed (can't have that now can we; you'd never know who won!).  So for now, you can download it here: http://upurload.com/dl/?n=3951

May or may not be bothered to try getting the video up again (really not that important).

Edit: I accidentally left the create event as the step event (did that while recording).  If you're stuck on the 'intro' room, just go to objIntro and change the Space Event to the Create Event.  Or hit space and wait a few seconds.

Also some other changes (from the original engine): Since there's multiple avoider objects now, each avoider object has immunity from getting hit twice in a row (for up to a second), and each avoider can get hit by an orange enemy (but not a green, which I added, meaning that it was recently created).  If an avoider object leaves the room (completely) then they're automatically destroyed (in that game) and a fun little "Poof!" pops up for a sec.  Also as mentioned by xot below, there's an awesome new 'dramatic zoom-in' feature when something gets hit.  The easiest way to disable that is to delete objControl's draw event.

And as a side note, I did this all rather hastily so the programming is sloppy and I changed things up so many times that it may seem inconsistent sometimes.  I'm not normally that sloppy!

Last edited by jalb (2010-09-18 05:21:25)

Offline

## #36 2010-09-18 04:26:40

xot
Registered: 2007-08-18
Posts: 1,201

### Re: CHALLENGE: Avoidance AI

Dude! That's awesome! Thank you so much for making that. It's so cool seeing them compete together. I really like the dramatic zoom-in when one of the avoiders gets hit.  Watching it go is surprisingly exciting.

I've converted it to a GM7 version if any cheapskates like me need it. Also corrected the Create Event problem. I also couldn't resist putting our initials on each AI sprite and adding a speed control. Press "S" to increase room speed by 30 (up to 300).

Noooooooooo! Eliminated in round 3. Suspiciously, jalb is the winner. I suspect foul play.

Congrats and thanks again. I'll get you next time!

Last edited by xot (2010-09-18 05:44:18)

Abusing forum power since 1986.

Offline

## #37 2010-09-18 04:38:50

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

### Re: CHALLENGE: Avoidance AI

xot wrote:

Dude! That's awesome! Thank you so much for making that.

Thanks, and you're welcome.

xot wrote:

Watching it go is surprisingly exciting.

I know, isn't that sad?   I was getting all into it while recording.  "Go yellow!! Yeaahh!!"

I think the whole idea of it is pretty awesome.  It's like a whole new way to play video games.  Instead of pressing keys to control your player, you program him and pit him against other programmed AI.

We must do this again sometime, it's been pretty darn fun.  I look forward to the next challenge.

Offline

## #38 2010-09-18 05:41:26

xot
Registered: 2007-08-18
Posts: 1,201

### Re: CHALLENGE: Avoidance AI

I think there is a rare bug in your tournament. If the final two avoiders in the match are eliminated at the same time, the match doesn't end. At least, I think that's what happened.

Also noticed after increasing the room speed (objControl::Draw) that your AI is definitely the slow poke of the bunch. Seems to be worth it, because it performs well. It looks like my AI is usually done in by its dedication to graceful elegance. We all must suffer for our art.

My Tourny Results Thus Far:
5 Dannyboy
1 jalb
0 xot
0 icuurd12b42
0 OpticalLiam

Dannyboy's wins are adding up pretty convincingly. The ranks shown here are reflective of the overall standings across all runs. There has been almost no variation except jalb and Dannyboy being swapped once, and icuurd12b42 and OpticalLiam being swapped once. I absolutely OWN third place, baby.

Last edited by xot (2010-09-18 06:10:51)

Abusing forum power since 1986.

Offline

## #39 2010-09-18 06:23:57

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

### Re: CHALLENGE: Avoidance AI

You're liking this way more than I had expected.  You'll be glad to know I've fixed that bug you mentioned, as well the bug in objIntro, and I added a few more fun features.

In objScore's Create Event there's now 6 variables that you can change.  I haven't tested my changes thoroughly so there could be some bugs.

You'll also be glad to know that I've taken the extra few seconds to convert to GM7.  So here's the new downloads:
GM7 Version
GM8 Version

Offline

## #40 2010-09-18 06:45:32

xot
Registered: 2007-08-18
Posts: 1,201

### Re: CHALLENGE: Avoidance AI

Haha, I love this thing. Changes look nice, but I have to put this away for now. I've got way too much work to do this morning.

The GM7 version just needs one tiny change. The "poof!" sprite isn't converted properly because of a lack of alpha support.

Abusing forum power since 1986.

Offline