New Bot AI Progress

[jitspoe]

I've added in some long-overdue debug drawing functions, as I'm sure they'll become useful if not necessary when debugging the pathfinding.  For now, I've drawn the player path as an experiment.

I spent most of the day researching some different learning AI (neural nets, genetic algorithms, etc.) to see if they would be at all feasible for letting a bot "learn" to jump around a map, but, from what I've seen, AI research still has a long way to go.  As much as I'd love to play around with that stuff, it just doesn't seem practical.  I might be able to use some kind of learning algorithm to try to reach an unobstructed point at a specific angle and velocity, but it would probably take less time to figure out the algorithm to do that than have something learn it.

On a side note, this was probably the most interesting talk I found: http://www.youtube.com/watch?v=AyzOUbkUf3M

[SuperMAn]

I've added in some long-overdue debug drawing functions, as I'm sure they'll become useful if not necessary when debugging the pathfinding.  For now, I've drawn the player path as an experiment.

I spent most of the day researching some different learning AI (neural nets, genetic algorithms, etc.) to see if they would be at all feasible for letting a bot "learn" to jump around a map, but, from what I've seen, AI research still has a long way to go.  As much as I'd love to play around with that stuff, it just doesn't seem practical.  I might be able to use some kind of learning algorithm to try to reach an unobstructed point at a specific angle and velocity, but it would probably take less time to figure out the algorithm to do that than have something learn it.

On a side note, this was probably the most interesting talk I found: http://www.youtube.com/watch?v=AyzOUbkUf3M

Jitspoe:  Instead of building an AI from scratch, would it be possible to just modify an existing Quake2 AI such as JABOT?  http://www.quake.ie/blogs/rawshark/working-quake-2-bot-linux.php.

JABot Q2 is a Quake 2 AI. Originally based in ACEbot is almost a total rewrite of it, while still keeps the ACEbot states machine design. JABot more flashy features are: - A* pathing in realtime - MoveType based pathing: The AI will only find paths using movements its ai class can perform - AI support for BOTs and MONSTERs. Through the use of ai classes. - weighted goal system. - Jump movement/movetype support for Bots class. - Bot roams support (using a item_botroam entity, or dropping it from console). - Many other improvements in every aspect of the code. Unsupported: - Bot chat and bot messages have been removed. JABotQ2, while usable for players as a standard DM bot, is written for Q2 modders to be used as base for new monsters/bots/actors, allowing to create a modern AI for their mods. Direct Download (Win 32 bin & src) Direct Download (Linux port by qudos)

The path lines look very nice btw =).

[not_payl_obviously]

Jitspoe:  Instead of building an AI from scratch, would it be possible to just modify an existing Quake2 AI such as JABOT?  http://www.quake.ie/blogs/rawshark/working-quake-2-bot-linux.php.

I already suggested that jitspoe should take a look at compatible (license-wise) bots, look what they can and can't, pros/cons and then maybe base on them. This will surely help make those bots better.

[jitspoe]

I haven't been able to find any really decent bots.  JABot is just a modified ACEBot and still uses a (more advanced, but still limited) waypoint system.  Plus this is kind of a learning experience for me.  I've always wanted to try writing good AI.

Now I'm trying to figure out if I should try to do something where I load the map collision data and try to build some sort of spacial awareness... something like the Quake3 AAS files.  At the very least, I'd like to build something that can define open areas where the bots can freely strafe jump around.

[BASEBALLDUDE]

Nobody's perfect, so neither should the bots be. Make sure the bots also learn some "failed" paths, aka trying to do a jump but messing up somewhere, and make that a part of the bot's program, especially for "easy" bots.

And good luck, jitspoe! Keep making progress!

[omni]

I think it would be hard to make bots that would be able to match top players ability at all, never mind making the bots too good for humans, I don't know.

@Jitspoe: do you know whether there will be different difficulty levels at this stage?

All in all looking brilliant so far, new bots should be good for the newer players

[JMR]

Message removed.

[Superchu]

hmmmm... i would have bots judge distance... that way, they can head whichever way is the most open, by testing 360 degrees, so a bot can 'learn' a map, then it tries to strafe the distance path. this would be limited, but a place to start.

[jitspoe]

hmmmm... i would have bots judge distance... that way, they can head whichever way is the most open, by testing 360 degrees, so a bot can 'learn' a map, then it tries to strafe the distance path. this would be limited, but a place to start.

That's sort of how the wandering works, but there are generally a lot of obstacles, narrow, zig-zagging passages, slopes, etc. that make this not work well.

[Superchu]

I thought wandering worked by just rnging an inital direction, then bounging off walls at 45 degree angles, untill it sees a target, then something snaps, and the bot becomes a fully realized painting machine O.o

[not_payl_obviously]

I thought wandering worked by just rnging an inital direction, then bounging off walls at 45 degree angles, untill it sees a target, then something snaps, and the bot becomes a fully realized painting machine O.o

Fully realized as lol, sometimes as it shoots and jumps it lose eye contact with you and turns around to be shot in ass.
I too think that bot just random direction and then moves for x meters. Still, even choosing longest path wouldn't help achieve any strategy. I think jitspoe is really into it, so I think letting him decide what works best for him is best option.
Jitspoe: Just so you don't forget: Initial work is not most important, long balanced work is important.

[Superchu]

Forgive me if this has already been discussed, but the way i was proposing is more like echolocation, the bot sends out distance traces so it can 'see' walls and doors. using an rng, you could force it to attempt a different path on a new generation.the trouble is having the bot find switches and ladders. in order to keep the bot from back tracking, it could only trace what is in front of it while moving. once it maps out a path, the bot could jump around a little on the path, trying to go faster. eventually, the rng will force it to try to deviate from that path in order to find a new path.

[jitspoe]

The new bots do this better, but the old ones, if something like this did not exist, would be running into walls constantly.

[not_payl_obviously]

if something like this did not exist, would be running into walls constantly.

Well, maybe your bots are smarter than mine, because for me they always run into walls. I think there is little heuristics (if you don't move, rerandom angle), but they still move halfway into wall and are unable to spot enemy.
I think both approaches have same common problem: bots will fastly end up going low path all the time because they fall. I.e. shazam33, they will just go mid-low, it's impossible they make it across bridge.

[jitspoe]

I tried an experiment where I gave the bots a bunch of random-ish input to select from (different turn speeds, forward/left/jump/etc. randomly pressed), tested each one, then picked the fastest one.  This was the result.

On the plus side, it allowed the bots to sort of dynamically figure out mediocre-average strafe jumping paths dynamically.  On the minus side, it's extremely CPU intensive.  I was noticing significant framerate hits with just 4 bots.

Of course, things could be done to optimize this, but depending on the obstacles in the map, the dynamic strafe jumping may or may not be effective without doing lots of actual physics casts (slow!).

I think, for now, I'm going to focus on using player recorded positions and paths, but try to make the bots follow them in a more dynamic manner.

[not_payl_obviously]

On the minus side, it's extremely CPU intensive.  I was noticing significant framerate hits with just 4 bots.

If this happens on fast machine, I would say this is not acceptable.

I think, for now, I'm going to focus on using player recorded positions and paths, but try to make the bots follow them in a more dynamic manner.

Hybrid between two methods can be good, it would use both some player recorded data and follow it in less static manner, it's a good idea. Then it could try to aim without aborting following player recorded path. This will both allow bots to aim while moving and also do some more crazy jumps that are specific for map.
Also: I think right now bots are like trying to figure out how to strafe, you should give them a bit more knowledge about how to do that, this will surely help reduce CPU usage.

[jitspoe]

I've made progress on dynamic waypoint placement.  Basically, it observes player movement and places waypoints while they're on the ground up until a hardcoded limit.  Once the waypoint limit is reached, it "randomly" deletes and reconnects existing waypoints, favoring removal of waypoints that are clustered together (no sense keeping a bunch of waypoints that are right next to each other).

It actually... works a little better than I expected:







3 shots of the same area as I've walked around it a bunch with a waypoint cap of 100.

This will be primarily for supporting beginner players as well as just providing general pathfinding for non-strafejumping paths.

[Ace]

How is it on the CPU compared to the random one you were doing earlier?

[jitspoe]

This isn't for strafe jumping - it's just for walkable area, though maybe I can figure out a way to make it work for strafe jumping.  I don't actually have the bots following the paths yet.  I'm just looking for a way to build them dynamically.

[not_payl_obviously]

I think you should test it on much more complex map, jitspoe, probably with more nodes. I wonder how it would look on some more complex map, because for now those look quite promising. Then only you should add parts where bot can just repeat player input (for hard jumps) and learn them strafing. This would be acceptable already.