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