Submitted by , posted on 02 October 2001

Image Description, by

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.

Image of the Day Gallery



Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.