Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 


Submitted by Alex J. Champandard, posted on October 02, 2001




Image Description, by Alex J. Champandard



This engine is a Quake 2 level renderer, based on BSP. It's a bit old admittedly... It was developed by a small company in Texas called Id Software, by a guy some of you may have heard of called John Carmack. That's nothing new, I just wanted to get that out of the way before I start mentioning the cool stuff ;)

The two levels are from a pack named Gothic Revolution, both very good looking even by today's standards, which just goes to show it's all about content. They're not by me either.

So what are you looking at? If you look really closely at the bots, you will see a very small neural network! (I'm kidding by the way... you don't have to squint at the monitor ;) The neural net is used to guide the bot around. In the screen shot on top, the bots are evolved to avoid walls with genetic algorithms. The basic idea is to cut open the bot's brain with a scalpel, and delicately insert the NN. In green you'll see the distance sensors working: these are the inputs for the neural network. Then its just a case of locking the speed at maximum (I don't always treat bots this badly), and seeing what happens.

At first the neural network goes "Whoops, how the hell do I control this thing? ... ka punk!" Every time the bot hits a wall during a trial, he is punished (deduced fitness points). The performance of the bots increases quickly over time, as the best bots are mated together to produce potentially fitter ofspring. It takes about 40 generations of 8 bots each to have a pretty much perfect obstacle avoidance, by which time the neural networks is begging: "Is there any way of boosting the speed of this thing? These corners are pretty easy..."

In the screenshot, the bot running down stairs doesn't in fact make it fully intact. He runs into the wall at the corner, turns and over compensates, thereby falling off the stairs into the small pool. It took him about 6 more generations to make it. You have no idea how pleased I was when those things actually ran up-stairs: it was quite a feeling of pride (close, I can imagine to the first steps of a child - virtually ;)

The image at the bottom shows a few waypoints - those horrible pyramid type things connected by green lines. They were placed by an automated way-pointing system as I ran around the level. The algorithm is something new I came up with, and I call it the "Hansel and Grettel" algorithm. If that's not self explanatory, then tough... I won't go into the details here, since it will be covered in detail very soon in the Robot Navigation tutorial on a newly created site called the Artificial Intelligence Depot.

Anyway, back to the bots in the bottom image. They're given the same basic information as the bots on top, plus the position of the target waypoint. The target is the one linked to the bot with a green line (Quake 2 doesn't have any colour options!). Again, it takes about 50 generations for the bots to be able to follow a randomly chosen path, AND avoid obstacles. This is all done by the neural network, marvellous things...

Right, that's about it. No flames please, I admit this is a shameless plug! I'm going to be doing a lot more development work and academic research on the subject, and I'm looking for people potentially interested in this technology. If you'd like more information, don't hesitate to contact me.


[prev]
Image of the Day Gallery
www.flipcode.com

[next]

 
Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Matt

October 02, 2001, 10:23 AM

That's *very* cool. Have you got them to circle-strafe jump/bunny-hop yet? :)
Any chance of a demo?

 
Krylar

October 02, 2001, 10:30 AM

That's pretty impressive! I've always wanted to get into AI, but never have...so I can't wait to check out your tutorial on this!

Would also like to see a demo!

-Krylar

 
XenoPhage

October 02, 2001, 10:30 AM

Very cool. I'm taking a course in AI now. Tons and tons to learn. It's a self-taught kinda thing (Kennedy Western University) and it's very interesting... Not to mention, tough... Goes from the early beginnings of AI to current stuff like Neural Networks... Covers all sorts of stuff. I'm learning a lot about BinTrees right now... (Bintrees in relation to AI, that is)

I've added your site to my list of course helpers... *grin*

 
=[Scarab]=

October 02, 2001, 11:10 AM

That's sooo phat. You just grab a rendering engine and some levels from the net, create some neural net bot code and then let the AI create itself. That's the way to go! :P

And those levels are indeed very nice! Pity you didn't make them eh? ;D

 
Phil Carlisle

October 02, 2001, 11:27 AM

Nice work Alex! :)

Looking forward to seeing your stuff for the AI gems book. Mine is still in progress (fixing grammer and such).

That might be a good site, I wouldnt mind posting some research there sometime too.

Phil.

 
Duncan

October 02, 2001, 11:28 AM

Very nifty, perhaps even snazzy.

 
Mattman

October 02, 2001, 12:25 PM

You spelled "grammar" incorrectly :-P

 
Orkin

October 02, 2001, 12:50 PM

Cool!

I've dabbled in bot coding in the past (anyone remember a game called Jedi Knight?). Mine was very primitive, pre-programmed paths, fixed response stuff though. Nothing nearly as advanced as this. It was fun though.

I can't wait to read your tutorial on this, it looks extrememly interesting!

 
FireFoX

October 02, 2001, 01:17 PM


I like your humor :)

 
wyldeling

October 02, 2001, 02:58 PM

A couple of questions: 1) Are the green lines just eye candy, or are they required so that the NN will work with quake2? 2) What algorithm did you use to breed the bots together? Just curious.

 
MK42

October 02, 2001, 03:05 PM

The green lines are just a visualization ... how would 'eye candy' affect a bot? Unless you would give each bot a rendered view and use that to do your AI.

- Marco

 
MK42

October 02, 2001, 03:10 PM

This looks nice and it sounds really, really cool. I can't wait for the article/tutorial?

What inputs does your neural net have ... just the sensors (five inputs)? ... now that would be really sweet (very small input set => fast AI).

You now have one more person who'll be checking out your site on a regular basis ...

- Marco

 
Craig Rennie

October 02, 2001, 03:47 PM

Just one question... do they learn when to duck and jump?

 
Stefan Karlsson

October 02, 2001, 04:15 PM

can you get them to fuck? :)

 
FireFoX

October 02, 2001, 04:38 PM

ROFL

 
James Matthews

October 02, 2001, 04:58 PM

That's really cool Alex...you've inspired to dig up my old code for the Quake2 AI add-on I made. It did some pretty cool stuff and I've learnt a lot in the past 2 years since I stopped working on it.

Later,

James.

 
DrTopaz

October 02, 2001, 05:52 PM

Yeah, me too.
I had done something similar as well back in 1998 for a company called endorproductions. This was before Half Life came out and it was based on BFS and A* searching. There was also some scripting in the AI; it turned out characters learned how to duck, hide, ambush, jump, etc. There is a deathmatch demo between two bots somewhere on that page, here is the link:

QUAKE 2 Neural Network Engine

-Topaz

 
[-WD40-]

October 02, 2001, 06:02 PM

How about using more inputs arranged in a sphere shape? that way maybe the bot would be able to tell if there are stairs instead of walls.

I don't know how your algorythm works (I know the basic of NN but not much) so I don't know if this would be possible...

just a suggestion...

 
disableddan

October 02, 2001, 07:41 PM

I'm not sure I understood anything you said here, but nice work anyway! I'm sure once I get it I'll appreciate it! :)

 
lxnyce

October 02, 2001, 10:25 PM

Best laugh I have had in a while.

 
ubermuffin

October 02, 2001, 11:50 PM

Coolest IOTD I've seen in a while!

-ubermuffin

 
DirtyPunk

October 03, 2001, 02:50 AM

Looks cool. Interesting to see how this would stack up against pure hand programmed collision avoidance algorithms.

 
Nieuw

October 03, 2001, 03:35 AM

Great! As a newbie to AI, this shows me very well how to use GA with NN in practice

 
noisecrime

October 03, 2001, 08:32 AM

Looks cool.

I've never been a fan of NN, but I'm always open to being converted ;)

BTW if the "Hansel and Grettel" algorithm is what I think it is, then its nothing new, but it is a very cool, simple and useful method.

I don't know if there is an official term for it, but it reminds me of Ants and pheromones. Ants drop these little scent packs to allow other ants to follow them or find there way back to the nest.

 
Jesse Krebs

October 03, 2001, 08:39 AM

Way cool. I've done some reading on NNs, but no implementation. Your results inspire me to pursue them further. Very nice work!

 
Jesse Krebs

October 03, 2001, 08:40 AM

Way cool. I've done some reading on NNs, but no implementation. Your results inspire me to pursue them further. Very nice work!

 
Alex J. Champandard

October 03, 2001, 08:46 AM

Perfect timing for the IOTD... i've just arrived in Edinburgh, and settled down enough to be able to access the web! So sorry for the lack of replies so far...

Scarab: Although it's very interesting to code a FPS engine, it takes a lot of time to get it polished enough for the AI part... it made perfect sense to use one of the most polished out there (and not too graphics heavy either).

Phil: Your gem seems to have a lot of potential too, looking forward to reading it!

Orkin: The Obstacle Avoidance (Basics) tutorial is nearly ready, but 'cos I haven't touched a keyboard for 5 days, it's going to need a couple more. It'll be anounced!

FireFox: Come to england ;)

Wyldeling: Yes, eye candy makes no difference. The bots can't see. The method used to breed them is called a genetic algorithm. You have a population of individuals (based on genes) and you pick the fittest and mix them together. The next tutorial - Obstacle Avoidanced (Advanced) will cover that (a week and a half away or so).

MK42: There's in fact 6 inputs... it's a little trick i've introduced and discussed in the AI Wisdom book. I feed the previous output of the NN back into it, to get a sense of state, allowing more human behaviour... works great, and once again it'll be discussed in the next tut! It could be faster by having only two inputs using one variable angle sensor (i.e. one that scans distances at random angles). You need more state variables to do that though.

Matt and Craig: NO, they do not know how to hop and duck. It shouldn't be too difficult to train 3 different networks to do all three tasks, but I'm trying to combine all that into one. Gas-nets are showing signs of potential in that respect, so i'll let you know. But so far, the NN doesn't even control the speed, that is something that needs more thought, and is be done by the path-guiding module.

Stefan: Yeah, they can... there's one part of the level with flashing red lights, and they disappear of for about 3'47"... they come back out with a little offspring. It didn't take me a lot of convincing to get them to do that...

WD40: That's a possibility... may be a bit more expensive. But my distance sensors take stairs and ramps into account automatically, using the in-game physics. Those can't be ignored as the entire movement is based on that.

Noisecrime: I've spent ages researching that idea, as i was convinced someone may have come up with it... but to no avail. What makes my approach different is that it's not a linear sequence of pebbles... one can link to any other: i.e. eventually building a graph of the level. That's not been done before to my knowledge... (if so, please let me know, it'd be good to read up on a different approach!)

There will be a demo with the tutorial, but that's possibly a few weeks away. I'm trying to make it as polished as possible, and trying to find a point to it: it seems useless to have bots running around for nothing!!

And thanks for the support guys!

 
Matt Everett

October 03, 2001, 09:41 AM

Congrats... good NN model approach to the cool problem of realistic AI (at least in the land of playing video games). This approach does also remind me of the ant & food model, to a degree, they are both different problems though. What interests me in this area of AI, is the protential to create complexity from simple laws/rules. The example of the ant & food model uses I believe only four rules, and from these rules complexity developes, displaying a sort of hive mind to the ants approach at gathering food.

It would be interesting to see what approaches your bots developed to interacting with other bots, using simplistic rules, for instance, a lesser bot could follow an more experencied bot, thus improving by direction. (monkey see, monkey do ;)).

Remember more ruthless AI would use an other agents weaknesses to their advantage. For example, a cleaver bot could use others as human shields, or could fire-off neron pathways by triggering off inputs of other bots, thus unbalancing (wrong word) the target bot (in the sense of input overload), in order to take advantage of their weaknesses. This is shown (though abstractly different topics) in terra-like AI & ALife programs, through parsite & host, where the parasite would force instructions in the host to be processed, usually to allow reproduction of the parsite through the host.

An important point is that complexity is deveried from simple means.

Look forward to seeing more...

 
Chilliwilli

October 03, 2001, 10:01 AM

I never realised you were English. To think I've been reading your articles/tutorials for all this time.

Where abouts in england are you based?

 
=[Scarab]=

October 03, 2001, 10:33 AM

I am sorry if my post sounded more sarcastical than I intended to. I have the greatest respect for bot coders and your Neural Net approach seems very good. (Good results with few imputs.)

 
This thread contains 36 messages.
First Previous ( To view more messages, select a page: 0 1 ... out of 1) Next Last
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.