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

October 03, 2001, 10:40 AM

Where abouts in england are you based?

um, how about york? just look into his profile...

 
IainC

October 03, 2001, 11:25 AM

Hi Alex, welcome to Edinburgh! I live in Broughton, just near the St James Centre. Are you working round here? There's a fair few industry folk round here. www.machinima.com on Leith Walk, who are thoroughly nice people, come to mind but there's definately more...

 
William van der Sterren

October 03, 2001, 03:17 PM

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!)

A couple of bots for Quake1, Quake2 and Half-Life use a pebble like system, and learn the map on the fly. Most of them heavily rely on the player (who also automatically drops pebbles), and items (also denoting reachable locations). Many of them use a simple wall following algorithm to explore the map until they have spawned a good enough pebble graph.
Famous examples include the Reaperbot for Q1 (by Steven Polge, now at Epic), and the Eraser bot for Q2 (by Ryan Feltrin, still at Xatrix?). Both bots use such an approach, but their authors never published the details.

Unrelated to pathfinding, but to using NNs: have a look at the NeuralBot for Q2, a university project by Ono Sendai. His site offers a nice presentation of the strengths and weakness of a bot solely using NN's and GA's: http://botepidemic.com/neuralbot/index.shtml.

William

 
Alex J. Champandard

October 04, 2001, 05:04 AM

William,

I know about the system used by Eraser. It's based on routes, or at least that's what the author calls them. They're quite densly placed markers that form a route, and rely entirely on the player to place them. He has to go back to the start of a route as soon as possible (as discribed in the README), which implies that the graph is complex and not fully representative of the level. The .rtz files are also big, some over 6k compressed, which also leads to think that the pebble graph is far from being optimal.

As for the reaperbot, it's good, on paper ;) In practice it has a small number of flaws in the navigation. Nothing major, but many little details that could be improved upon.

Maybe I'm just wasting my time...

I welcome suggestions for a change of focus ;)

Alex

 
William van der Sterren

October 04, 2001, 07:35 AM

Hi Alex,

(something I've should mentioned in the previous post:
Hurrah! Finally some AI in IOTD. And you have great taste for levels).

Obviously Eraser and even more Reaperbot (implemented in QuakeC that lacked any useful container mechanism and user-defined types) have their limitations. If Eraser doesn't automatically link up markers/pebbles outside a linear path, that's pretty dumb.

Having developed (pebble based) pathfinding and (traditional) movement/obstacle avoidance myself, I think of a few reasons why these AIs heavily rely on player movement to build a representation of the level.

Even the starting level in Quake2 (base1) has a few paths that are pretty complex for the AI interpret (let alone learn).
Near the single player start spot, there's a stack of crates, requiring a sequence of jumps and turns to mount it. There's a ladder positioned in the center of a room that needs to be mounted on one side to get upstairs, and should be regarded as an obstacle from the other 3 sides.
In another room is a hole in the floor in which the AI would need to drop and then crouch to move underneath the floor. That space underneath the floor also can be reached from the water, but requires a swift 'jump up'-'crouch' sequence to get out of the water and then duck to get under the floor.
Finally, the room with the elevator leading to the exit of the level has a nice ambush spot: there's a small ledge above the door to that room that can be jumped to.
(Yes, I've spent some weeks developing and debugging movement code on this map).

I myself don't have much a clue how to get an AI to learn this moves by itself without having to resort to trying numerous combinations of jumps, turns and duck-moves.

On big .rtz graphs not being optimal: size often isn't an important issue for waypoint graphs. What matters is the kind of AI reasoning to be supported by the terrain representation, and how well the representation succeeds in doing so.
If dynamic path-finding is the major concern, terrain representations with few waypoints are preferred. If environment sampling is most expensive, you might prefer numerous densily spaced waypoints (to reduce the need for environment sampling). If line-of-sight/fire becomes an issue and you use precomputed tables describing cover/concealment, you want the waypoints to properly cover all useful cover locations.

IMO, today's games tackle navigation and movement in so many ways because of the strong influence of requirements other than navigation and movement. But perhaps, we'll someday see the Microsoft DirectX13a Pathfinding API.

Thanks for the 'blast-from-the-past' pointers to the ReaperBot discussions.

William

 
iMalc

October 05, 2001, 03:24 AM

Awesome!
I bet they can't jump over ditches though.
Some really fine work man.

 
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.