Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
gggmork

has anyone attempted doom playing ai?

Recommended Posts

Just wondering for curiosity's sake. Considering how the darpa grand challenge (getting robot cars to drive automated) was likely.. challening (hence the name 'challenge'), maybe this would be way too hard (like making ai play doom/record an automated demo at doomgod skill).

Share this post


Link to post

There's been discussion on that in the demo forum, and as far as I understand, knowledgeable people concluded there's so many parameters in Doom it'd be too hard. I'm sure you can find the topic if you make a search about "TAS".

Share this post


Link to post

Uhm, there are bots. That is AI that is playing the game. The bots in Doom aren't very advanced however. But if you look at games like Q3 and Unreal Tournament, you can find bots that actually can move around and use strategy on the map. If you want to see them play just spec them.

Yeah, this is obviously not SP. But making SP playing bots should be even easier than making DM playing.

Question is how to balance your bot though. Since you can give it every ability that humans can't have. Like very strong rocket prediction. 100% aim. 0 time reflexes.

Share this post


Link to post

Can it be set to "cheat" by knowing what all the nearby monsters are going to do, by predicting their pseudorandom number hits?

EDIT: 0 time reaction, perfect aim (whether leaded, predicted or not) are what the computer's about, to compensate for its limited creativity.

Share this post


Link to post

Of course. You can make it know where every monster and item are on the map at all times.

EDIT: Yes, the lack of cognitive thinking processes and ability to improvise can be made up for with superhuman abilities in aim and movement.

Share this post


Link to post

Yeah I know imps and stuff have ai, but its retarded like 'walk toward doomguy, even if into a wall, and shoot randomly if you see him'. Never played deathmatch, so didn't even know there were cpu controlled doomguys but suspect they're equally stupid.
And yeah, it seems like computer vision and hard stuff like that might not matter so much because the ai could know all the internal data without having to 'see' (maybe afaik) and even know the pseudorandom numbers.
I don't play many modern games, but remember people saying gears of war had good ai but that was mostly the same simple enemy behavior except they occasionally hid behind stuff (imo doom behavior and gameplay in general is far more fun than that).
It would be hard to make the ai figure out a fast route for any map thrown at it.. probably have to use heuristics for that instead of explicitly telling it what to do. Other hard things would be maximizing infighting, generally navigating around to avoid stuff, choosing which enemies to kill first (like pain elementals/viles/hitscanners maybe) and strategy can vary from map to map, even things like using vile blasts to reach higher areas quicker. There was one map where you could not shoot whenever you saw an evil eye thing on the screen or viles would warp; it'd probably fail playing such a map.
Maybe with genetic programming or reinforcement learning or something like that so the bot 'evolves' its tactics/strategy on its own. I'm just a novice programmer.

Share this post


Link to post

Yeah, this is obviously not SP. But making SP playing bots should be even easier than making DM playing.


Nah. Making AI for SP is much, much harder than DM. In any game, DM is very predictable and repetitive, you fight the same opponents in the same map everytime, the only goal is to kill opponents. Move, pick up weapons, pick up powerups as soon as possible, shoot at your foes. It's relatively straightforward.

Compare with SP where you have to define an optimal route, taking not only layout in consideration, but monster, ammo and health placement, possible glides, AV jumps, pressing switches/opening doors in specific order, target prioritization, risk management... There's much more things at work.

There's tons of bots who can rival with players in DM games, yet no SP AI ever competes with good humans in FPS... Closest that I've seen to working SP AI would be L4D (using console to make them play as an all-bot survivor team), even then they're still far below any decent player in skill level.

Share this post


Link to post

Shows how much you know about playing DM.

Also, the AI used for friendly AI in games like HL2 and L4D is hardly comparable to that of Dueling games in sophistication. Even if the bots are pretty stupid in Q3 and QL, they are still have leaps and bounds better AI than the friendlies in source games, which are just regular monsters with a few added abilities like the uncanny ability to block your way when you're in a narrow staircase.

Share this post


Link to post

I've been playing DM on Doom, Quake, Q3, Tribes 1 and 2, ET:QW, FEAR, Crysis and a few korean games you've most likely never heard of. I'm also not clear on what exactly my experience or supposed lack thereof in playing DM has to do with comparing AI programming and efficiency between DM and SP, although if I had to guess I'd suppose you've misinterpreted my reply as "DM doesn't require much thought" and got butthurt by that - either this, or it was just a completely offtopic retort because you're mad I don't agree with your opinion.

The AI in L4D hasn't much to do with the AI in HL², which had a very simple "follow player, shoot at enemies" routine. To compare the two shows you haven't even done research on the topic (or consider just playing the game superficially to be "research"), as L4D AI is much more advanced than that, with complex decision making on the fly regarding pretty much everything. It's far from perfect for sure, but certainly the best effort I've seen personally, and many big names in the industry share that opinion.

Judging by your aggressive tone, I can tell you're not looking for discussion and are going to troll until you get the last word, so I'll just stop here. It's not like I'm an expert myself anyway, but I am interested in the topic enough to know the basics - and frankly, anyone who does wouldn't make the claims you do.

Rest assured that while silent, I'll be looking forward to either your Doom AI program that will concur with the best DSDA times or the bullshit excuses you'll make up to justify not doing something that is, according to your own words, "even easier than DM".

Share this post


Link to post

Someone made some coop bots for Skulltag here - http://skulltag.net/forum/viewtopic.php?t=10618.

But these only follow the player around. So the main thing missing is a pathing algorithm, which can figure out where the exit is, and how to get there. I'm not aware of anyone having made something like that, but it's likely easier in DOOM than full 3D games, because you only have to calculate the path on a 2-dimensional grid (as opposed to a 3-dimensional grid)

Share this post


Link to post
Phml said:

stuff

I certainly don't want to argue. But absurd statements where you claim that DM is more predictable than SP makes me believe you don't know what you're talking about.

Outsmarting an actual player that knows what he's doing is a whole lot harder than to play an SP map/game any day of the week. In particular in a game like Doom where you can predict the monsters movement down to a tee. It should be a whole lot easier to make a bot able to do the same predictions of the AI in Doom than to do it of an actual player in Quake3. Just because you've played a bunch of games against other people doesn't mean that you played anyone difficult, or even went into learning the ropes.

Now I am not a pro at DM by any means, but I've spent a lot of time watching and sometimes playing pros, reading about strategies and movement tricks, etc.
Unlike you I don't have an large array of different games that I claim to have reached any greater understanding of. It's basically only Doom, Quake3/Live and ETQW that I've spent any real considerable time getting to learn the games and players. But I doubt that is what you've done in either of the games you've played. Just playing the game a while doesn't make you understand it. You can play a game for years without actually getting anywhere because you don't push yourself to reach something more. And honestly, I doubt you have done that in either of the cases you listed.

As for L4D, I never played it. It's wrong of me to assume anything about the AI in a game I never played. But the whole premise seem extremely dull to me.

Share this post


Link to post
kristus said:

Outsmarting an actual player that knows what he's doing is a whole lot harder than to play an SP map/game any day of the week.

It's not necessary, though. Bots can simply use their instant reaction speed to dodge almost any incoming projectiles, and their perfect aim to shoot the player perfectly with hitscan weapons. Projectile awareness has been implemented in Quake bots, but not DOOM bots, so they seem relatively weak in comparison. The gap between a properly implemented bot with a perfect aim and reaction speed, and a human with a ~200 millisecond reaction speed, is so large that strategy isn't even necessary to defeat a human. As I'm sure you know, reaction speed plays a role in both aim and dodging, so its effect is multiplied.


The difficulty with a Single Player bot is analyzing the map and understanding how to get to the exit, rather than being able to defeat enemies.

Share this post


Link to post

There's a big difference between single-player-like AI and deathmatch-like AI. Unless, I suppose, there are some people out there who enjoy having their deathmatch staggered by keyhunts and switch puzzles. Doesn't Doom deathmatch give you all the keys, though?

Single-play is objective-oriented: go there, do that, and follow the list of objectives until the mission is complete and you can exit the map. Deathmatch is fight-oriented, it doesn't matter where you go or what you do as long as you dodge attacks and frag your enemies.

Sure, the combat-related AI has to be better for deathmatch, since -- at least in Doom... -- players are a lot more mobile than monsters, and of course more unpredictable and tactically savvy than the dumb Doom monsters. But the pathfinding process is actually much harder.

The easy way out is to script the bots. You put special nodes and markers in the map that tell the bots that here they can do this or should do that. You won't have bots coming up on their own with stuff like rocket-jumping onto a decorative ledge then straferun from that to a platform and shoot a switch through a window during your fall so that a door gets opened by the time they lit on the ground for just enough time for them to go through it. Players might, but bots won't, unless you script that sequence in; which isn't going to happen if this example was actually a sequence break that the map author never thought of.

On the other hand, the combat AI of a coop bot can afford to be a lot simpler, since the combat AI of a Doom monster basically amounts to "walk randomly around, stop, stand still while firing, goto 10".

Share this post


Link to post
Gez said:

The easy way out is to script the bots. You put special nodes and markers in the map that tell the bots that here they can do this or should do that. You won't have bots coming up on their own with stuff like rocket-jumping onto a decorative ledge then straferun from that to a platform and shoot a switch through a window during your fall so that a door gets opened by the time they lit on the ground for just enough time for them to go through it. Players might, but bots won't, unless you script that sequence in; which isn't going to happen if this example was actually a sequence break that the map author never thought of.

Of course, this won't work if you make bots that are supposed to work with any map. :P Even automating the node-placement process is a difficult problem. Where as you can easily make a Deathmatch bot that can work with most standard maps.

Share this post


Link to post

This is something I've thought about from time to time and I think it would be a really fun project to try and make a SP bot that could play levels that it had never encountered before.

One question is, how exactly would the bot interface with the game? If you were to take it to an extreme, you could have a standard copy of Doom running, then capture all the video and audio output and send it to a bot running as a separate program. It would then analyse the input and take action by sending simulated mouse movement and key presses back to the game. A bot like this would have to perform some serious image and audio analysis just to have even the most basic interaction with the game, and realistically speaking, it'd just be way too hard.

Instead, you'd have to provide a simplified, somewhat more integrated interface between the bot and the game. So you might send an update every tic, in which you provide the bot's position in 3D space, plus an enumeration of all the walls, floors and entities within its field of vision. But what other information do you provide? Do you supply the damage types of floors? The vector of projectiles? Do you restrict the depth of view in dark areas? By how much? Do you indicate line specials? The more information you provide, the easier it would be to write a bot, but the less "pure" the bot would be.

If you were to define this interface, then you could really have some fun. You could set up a server running a modified version of Doom and let people submit bots, written in some specially designed interpreted programming language, that would be place in randomly selected levels. The bots could then be scored based on the number of enemies they destroyed, the levels they completed, etc, and you could have leaderboards of the best AI. I know similar things have been done for Mario and some other games, but Doom would be especially fun.

Share this post


Link to post
Jonathan said:

But what other information do you provide? Do you supply the damage types of floors? The vector of projectiles? Do you restrict the depth of view in dark areas? By how much? Do you indicate line specials? The more information you provide, the easier it would be to write a bot, but the less "pure" the bot would be.

The bot needs to know everything a player does. So, not the damage type of the floor, but the floor texture used, so that it can compare it to its database and guess whether it might be damaging or not. E.g., "nukage and lava are practically always damaging, blood usually is but not always, those glowing blue flats are nearly never damaging but it happens, grass is not damaging unless the level maker was a kind of a jerk." It should also be able to identify teleport textures and the like. The textures on walls need to be given as well, so that it may likewise guess if it's a switch or a door. Might also look for subtle secret clues such as misaligning or abrupt change to a different yet similar texture (e.g. E1M1 secret tunnel to courtyard). The "EXIT" texture is important to recognize too, as well as the DOORBLU/RED/YEL/etc. textures, and actors like the Heretic orb statues that serve the same purpose. You'd probably have to use a neural network system so that the bot can experiment and learn.

And of course it would have to be told the position and movement of any visible actor, including projectiles; players can dodge them can't they?

It would be a pretty sweet project for an AI specialist.

Share this post


Link to post

This mario ai is quite impressive to me:



I only read half of the 'super mario evolution' pdf here so far:
http://julian.togelius.com/
looks like reinforcement learning (reward/punishment I think) and artificial evolution was used.

Share this post


Link to post

I wrote an experimental Doom Artificial Intelligence that could complete certain Doom levels to a certain extent. I wrote it around 2 years ago using flawed methods and no knowledge of any Calculus. I also wasn't that experienced with the Doom Engine as I am now. It worked to a certain extent but it didn't really work.

Of Deathmatch:

http://sites.google.com/site/ghostlydeath/gdvbots2.zip?attredirects=0&d=1
http://sites.google.com/site/ghostlydeath/gdvbots.zip?attredirects=0&d=1
http://sites.google.com/site/ghostlydeath/gdbots.zip?attredirects=0&d=1

Of Solo/Coop:

https://sites.google.com/site/kaptinkurk/m01clip.lmp?attredirects=0&d=1 (Google reports Nov 24, 2009 2:59 PM but this is really the Pages -> Sites transition date for my pages site), this is a clip of a bot trying to gather the clip in the exit room in Map 01.

This was all just a hack and I now know how to do it all efficiently and correctly.

EDIT: I should add that these bots figured out where to go on their own (kinda, if you remove me coding this functionality) to where the bot will build a path to it's wanted target. This meant that bots could go around corners and such as seen in the clip demo.

EDIT: You might not think the bot is running around trying to gather that single clip as it looks like it's running around in circles. It's just redetermining it's path since the opposing object could no longer be obtained with the current path. Also the path selection was very shitty, I was using BFS and nothing like A* or whatever. So in short the path was found but it wasn't the best. As I said, it's all for testing nothing release worthy.

Share this post


Link to post

Interesting doom2 map 1 solo lmp. bfs = Breadth-first search?
I would barely even know where to begin (I'd have quite a hard time just making a tetris/pacman game) and it seems like lots of knowledge about the doom code and how to interact with it would be required, and that alone would take me forever to figure out, not to mention creating the ai itself.

Share this post


Link to post

I too experimented with bot stuff, including a "puzzle solver" for handling keyed doors (pretty basic stuff in retrospect), and using A* on GL subsectors for pathing.

Making a bot traverse a path _smoothly_ (like a human would) is actually a lot harder than you'd think. Other difficulties include "jump overs" like going to the red key in MAP02 of DOOM2, I never solved that problem and still don't have a good conceptualisation on how to handle it.

It's one of those things that after a while you achieve what you wanted to see (like a bot traversing a level), and then you're done with it. Good co-op bots, to accompany a human player, don't really need to solve the puzzles anyway, they mainly need to stick with the player (without getting in his/her way) and help fight the monsters.

Share this post


Link to post

Hey,
Sorry for resurrecting the thread, but I also started some basic level traverse implementation recently. I was out of Doom community for many years and didn't even know how many interesting things are happening around. Just recently I found some time to do the implementation, but the idea spawned in my head long time ago.

I am also done with switches and keys and can fully agree with andrewj that once you see the bot solving few levels it's hard to find motivation for more complicated stuff like jumps or navigating around blocking things (barrels, pillars, etc.).

Here's the most recent video:
https://www.youtube.com/watch?v=wrMVck3TyQM

And here are links to E1M1, MAP01 and MAP10:
https://www.youtube.com/watch?v=26KWpSCiQAM
https://www.youtube.com/watch?v=Cqb5qBh2cVw
https://www.youtube.com/watch?v=hXaya_21uC0

Share this post


Link to post

@mgr_inz_rafal Those bot videos were interesting. My guess is that making a bot able to "solve" Doom levels in the general case (and not just simple test maps) must be at least as hard as making a perfect chess-playing computer, if not more.

I presume your bot has however at least a "perfect" knowledge of a level (e.g. it knows beforehand by "peeking" at the map data which switch activates which object/door, it knows where various items and key are etc.), compared to a human player. If it had to acquire that knowledge as it went on or by trying to reason through visual cues, that would be much harder to code.

In addition, as you said, the hard part will be coming up with heuristics that will allow it to negotiate difficult terrain, jumps, etc. but in theory, once done, it should have the performance of an extreme TAS player, automatically choosing the shortest path, exploiting heuristics, performing perfect SR50 movement all the time etc.

A bot that's also able to combat monsters would be another challenge as well: it would need much more than just a repurposed monster AI. It would need a new AI that would allow it to exploit its extreme mobility, dodge projectiles, tyson with impunity while "dancing" around monsters, having a perfect knowledge of his opponents timing and attack patterns etc.

Again, if both aspects were combined (navigation and combat), you'd have quite a sight.

Ages ago, I had proposed a design architecture for such a bot, which would rely on map sectors as "goals" and use elements of recursion and dynamic programming to efficiently identify and repeat subgoals it already achieved (e.g. "finding the yellow key" as a goal would actually have a subgoal of "find a way to the sector containing the yellow key". In turn, that would have recursive subgoals of "find a way to the accessible sector(s) adjacent to the one containing the yellow key etc.), and once the solution to a goal was found it could be repeated or "patched" into other subgoals.

Mutual sector accessibility would be an important element, too, as essentially the bot would always try to find the answer to "is sector A accessible from sector B?" or put more simply "Is there a way from sector A to B?" and there would be accessibility criteria such as the presence of teleporters, elevators, jumps, drops etc.

Share this post


Link to post
Maes said:

My guess is that making a bot able to "solve" Doom levels in the general case (and not just simple test maps) must be at least as hard as making a perfect chess-playing computer, if not more.

If we want to be precise about it, Doom levels are at least NP-hard, and probably PSPACE-hard.

Share this post


Link to post
Linguica said:

If we want to be precise about it, Doom levels are at least NP-hard, and probably PSPACE-hard.

Glad that I didn't know that before I started coding :)


@Maes
You're right, bot utilizes its knowledge about the entire level, so it immediately knows where to go. The problem is to find out "how" to reach the destination. It's not an AI at all, just a pathfinder based on Doom segs. Anyway, I still like to look at it wandering through the levels :)

Maybe one day we'll have a perfect bot: https://www.newscientist.com/article/2076552-google-deepmind-ai-navigates-a-doom-like-3d-maze-just-by-looking/

Share this post


Link to post

My preference is for a "realistic" bot that actually plays the level as a human might. It can be done, efficiently, without giving the bot knowledge of the level at the start. You need good pathfinding, both a*, and "bfs" (Dijkstra's algorithm), which you update as the bot "sees" the rooms, using the auto-map line reveal feature. Therefore, the bot must run a rendering pass, which identifies visible walls, and things. The bot will need to remember walls and things seen.

You'd probably want to help it a little at first, by telling it which walls are non-hidden doors, so the bot doesn't have to wall-hump the whole level.

Each few tics or so, you enumerate your list of goals...
. Find weapons/ammo
. Increase health/armor
. Find keys
. Shoot monsters
. Stay alive!
. Find locked doors/switches
. Find the exit
. Explore all areas
. Find secrets

...and you calculate an empirical score for each goal, to tell the bot which action is currently most important. You do this by evaluating the bot's current situation:

. Am I under attack?
. Is my health too low?
. Is there an area I haven't seen yet?

This score should give precedence to things like "Stay alive!". The way the score is calculated is built empirically, and will need to be tweaked until perfected. Once scores for all possible actions are calculated, the bot takes the action with the highest score.

The scoring methods can also change over time. You could maintain a "number_of_tries" variable, so if the bot has tried to make a complex jump a few times and failed, the score lessens, and the bot gives up and moves on.

Unfortunately, this leaves you with a pretty smart but limited bot. This bot cannot find secrets, and cannot use lifts operated by switches, for example. Because of this, the bot code is gradually allowed to cheat a little. Basically, the engine slowly gives the bot info, like which switch opens which door. Yes, I know this is not the ultimate "realistic" bot. But, it's super difficult to program the bot to "learn" how to control, for example, a switch around the corner from the lift it operates. I wouldn't want to attempt to try to build such logic. Besides, the bot needs to run at least 35 fps, so it cannot be stuck in a deep "neural-net" situation.

So, you gradually leak info about switches, lifts, and even secrets. Maybe you wait until the bot has determined that it is stuck. The "discovery" pathfinding (Dijkstra's algorithm) will tell you this, as will the goal scoring, as it will gravitate to "find exit", "explore", etc.

This description of bot AI is complex, but has some very nice features, which I'll summarize:

1. This bot will "look" realistic in action. Instead of making a bee-line to each goal, it will look around and discover the map as it unfolds.

2. The bot will appear to "change its mind" like a human might. For example, during battle, the bot might run away to gather more ammo or health.

3. The bot will not get "stuck" as easily. It might try to jump and grab a special item a few times, but eventually give up and move on, if it's not a critical item.

4. Goals can be added to the code gradually, without disturbing what's already working. For example, you might add the ability for a bot to find cover behind a pillar.

5. Bots will not have to wallhump the whole level, but they will also not run directly towards secrets as soon as they enter the room.

6. This AI is as "fair" as easily possible: The bot must learn how to play the level (almost). The AI will eventually leak info to the bot, which might be considered "unfair", but this relieves the programmer from having to write some very difficult puzzle-solving logic which may not even be possible to do, or may not maintain a good frame rate.

7. You can easily build "personalities" for the bots, by adjusting the scoring calculations, to give you bots that are aggressive, defensive, balanced, 100% kills, etc. Also you can provide adjustments for sharp-shooting ability, dodging capabilities, etc.

8. Another note is that you don't have to evaluate the bot's situation/goals/score each tic - you can do it each 5 or 10 tics, for example. Or even longer. A human does not change his or her mind 35 times/sec, so why should the bot? This will also make it run more efficiently, and simulate a human-like reaction time.

Wow, I wrote a book...

Share this post


Link to post
kb1 said:

A human does not change his or her mind 35 times/sec, so why should the bot?


After seeing some (allegedly non-TAS) demos by ToD, I'd be inclined to disagree ;-)

Share this post


Link to post

Well, now I have AutoDoom, which can be downloaded from this thread. It's based on Eternity and can solve several Doom 1 levels. It has access to all game data. Does the bot shown here have access to game data?

In the future I want to make my bot more easily accessible to users for download, with auto-update included.

Interesting that my previous post here was before I ever started on a bot.

Share this post


Link to post
printz said:

Well, now I have AutoDoom, which can be downloaded from this thread. It's based on Eternity and can solve several Doom 1 levels. It has access to all game data. Does the bot shown here have access to game data?

In the future I want to make my bot more easily accessible to users for download, with auto-update included.

Interesting that my previous post here was before I ever started on a bot.

AutoDoom! Very nice! I'll be checking out the source in detail, when I get a chance. Wow, you've been very busy with Doom lately, huh? Awesome. Yes, an automatic level generator bolted on would make an excellent, ever-changing screensaver as well! Does your bot do ok as a coop buddy? If you didn't add specific coop support, I imagine it would hog all the pickups, right? That's tricky to handle. It would be nice to be able to "talk to" the bot: "Leave me some health", "Get over here", "Get away".
Watching the posted video, it's interesting to see the bot aim towards a monster on a high ledge, while riding up a lift, even before the monster is visible :) Anyway, it's very interesting and entertaining.
Another very different use for this is an automated level checker. Run without the rendering or the frame delay, it could blaze through the level looking for all kinds of problems, or just gathering statistics about a level, in a way no other approach can. And, with the renderer running, it could search for HOM, visplane overflows, etc. It could make sure the level is actually finishable, for example.

Share this post


Link to post

@printz
AutoDoom looks outstanding, indeed! Gonna read through the dedicated thread.

Yes, my bot has access to all level data. Currently it runs outside of DooM engine - it's just a separate program which reads a MAP and creates path that is later executed by DooM engine (zDoom, to be precise). It was good for a proof of concept, but in order to respond to dynamic changes in environment I need to embed the pathfinders and logic directly into the game port, as you did.

Share this post


Link to post

Solving a level in -nomonsters conditions is one thing. With monsters roaming around, pressuring, attacking, blocking the way etc. as well as the existence of hazards, timing-dependent puzzles, traps, one-way actions etc. it would be a whole different story.

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×