Client / Server Architecture | Weapon Control | Navigation | Dodging | Artificial Intelligence | Miscellaneous |
Client /Server
Architecture
Before any fancy AI programming,
navigation, or weapon control can be made, the very first thing that must
be completed is the network Client / Server (C/S) architecture. We
are talking about a program witch connects to a remote machine, so it first
must know how to connect to and communicate with the server. This
is a large but important part of the bot. In my case, creating the
C/S architecture probably has taken about half the total time that I have
spent working on the bot!!
In order to simply connect to a Quake server, you need to know something about the Quake Network Protocol (see QuakeBot Links). After you know all the details of simply connecting, you can start sending movement messages - sounds easy, eh? Wrong!! That's not all! In order to "see" what you are doing you need to take care of the server messages that are sent upon connection (large packets) as well as the updates (small packets) which are sent every 50ms or so (depending on the sys_ticrate setting of the server). There are many (35+) server messages to know how to handle, some of which are quite complicated. These important messages are actually the same as what is contained in the demo (.DEM) file formats. The .DEM files are actually recordings of the messages sent between the server and client.
Some bots also come with a proxy server. This allows human players to connect to the bot and see through its eyes or even play the game with the help of the bot. This involves quite a bit more programming because now you also must know both ends of the Quake Network Protocol, as well as how to send server updates and messages! There are varied opinions on using proxy bots (as well as bots themselves). Personally, I don't mind people using them, as long as they don't try to take credit for their excellent performance. There is a lot of fun to be had at a battle of the proxies - where everyone uses a proxy bot!
Weapon
Control
Being an engineer, Weapon
Control was one of the first tasks I completed after the bot networking
was completed (well, it still isn't complete, I am always working
on it). Tracking moving objects is simple (or maybe complex)
geometry and adding a few kinematic equations allows for target prediction. Using
some of these equations took me way back to my days in high school and
my grade 10-11 physics class. However, some weapons are easier to
use than others.
Axe
This is a fun weapon for a bot to use. However,
it is a little difficult to use. It requires coordination between
navigation and weapon control (you have to get close to someone before
you can Axe-Murder them)! Aiming is not crucial here, just face the
target. The best way to do this is use the shotgun
aiming algorithm (quick and reusable).
Shotgun and Double-Barreled
Shotgun
These, by far are the simplest weapons
to use. The shotgun pellets travel at an infinite speed, hitting
their target instantly. Thus, no prediction is needed - just point
and shoot. It is simple geometry. Translate the coordinate
system so that you are at the origin. Then convert the target's (x,y,z)
coordinates to spherical (distance, yaw, tilt) coordinates and fire! Since
the shotgun has infinite range as well, the distance is irrelevant and
does not need to be calculated.
Nailgun and Super-Nailgun
Quite difficult. These
projectiles move at a finite speed which makes hitting a moving target
hard. Of course if you don't want to worry about hitting anything
that is moving you could always use the shotgun aiming algorithm for everything!
But if you actually want to connect with your target, you will need
to perform some sort of prediction.
For second order prediction, the equations are
a bit complex. For a moving target with a known acceleration,
a, velocity, v, and initial position, p0,
the position with respect to time is given by
p = (1/2) a t2 + vp t + p0
where p, v, and a, are vectors containing the x, y, and z components. Then, knowing that the nails travel at a constant velocity, we have for the nail
n = vn t + n0
Now, in order to do some damage, we want both the target and the nail to have the same position at the same time. Thus, we have two equations and two unknowns. Easy, eh? Well, not exactly. We do not know the x, y, and z velocity components of the nail. However, with some experimentation you can find out the speed of the projectile (speed is different than velocity, remember?). So you do know that
s = |vn|
where |vn| is the Euclidean norm of the nail's velocity. Now, it can be solved. However, that doesn't mean you will want to solve it. When trying to solve this, it turns out to be a 5th order equation in t. There does exist a general formula for the solution of a 5th order equation, but let me assure you, by the time you would calculate the solutions to all 5 roots, your target would be long gone!
To simplify things a lot, you can assume the acceleration of the target is zero. This then becomes a quadratic equation and can easily be solved. You should look out for negative solutions for t. You cannot shoot someone backwards through time.
There is another way of indirectly solving these equations. You can calculate the target's future position using small increments in time. Then for each predicted position, determine if the nail can hit that spot at that time. For targets that are far away, this could involve many iterations, and again, the target may move before the targeting calculation can be done.
Grenade Launcher
By far, this is the most difficult weapon
to use. It should be a weapon of last resort for the bot to use.
The same equations as the nail gun can be used, except the grenade
does not travel with a constant velocity - it has acceleration too. This
results in a 6th order equation in t to solve. Fun, fun. Also,
there is an offset added to the firing angle of the grenade launcher which
has to be found using experimentation. The only way to reduce the
equations to something manageable, is to assume a stationary target. This
will result in a quadratic equation, but will also result in no prediction.
I am still trying to find a 'good' way for Itchy to use this weapon.
Rocket Launcher
For aiming of this weapon see the discussion
given on the Nailgun and Super-Nailgun. The
rocket launcher is exactly the same (even the rocket speed matches the
nail speed). However, it is different in the fact that firing too
close to a target, can result in injury to the bot. So, check your
distance before firing!
Lightning Gun
The basic aiming of the lightning gun
is the same as for the shotgun. However, it
does have a limited range. Also, you must avoid discharging
into water (unless you are invulnerable :) ).
Editorial: One thing that annoys me most about QuakeBots is the fact that they are too accurate (especially when using the shotgun). When trying to have a good game with some real players, I get real mad when a bot is running around pecking away at you with a shotgun. The purpose of designing a bot is to have a good opponent but not an annoying opponent. This also goes for random abuse that some bot spout out. The best bot is the most human bot. 'Nuff said.
I guess I should mention something about line-of-sight. In Quake, the client receives updates for every entity within his current node's visibility list (see BSP tree). It does not guarantee that the entity actually visible, the target may be partially, or fully blocked by some terrain feature. So before firing, the BSP tree should be traversed in order to determine if there exists a line-of-sight between the target and the bot. This will avoid wasting ammunition as well as possible damage to the bot (firing a rocket into a nearby wall is never a good thing).
At the moment, I am working on the problem of bot navigation. This is probably one of the most challenging (i.e. hard) problems I have encountered. Since the level is described by a BSP tree, there isn't a nice "map" for the bot to use in order to move around. The navigation problem becomes one of navigating through a BSP tree (or trees). To my knowledge there does not exist an algorithm out there for doing this. This would be very useful to have, not just for a QuakeBot but for any game manufacturer. Just think of the intelligent monsters you could have if they could chase you properly with out running into walls, etc.
So, until I get well on my way to a good BSP navigation scheme, I will not have much to report here. If you do find a good algorithm, please drop me a line! If you want some good ideas, you may want to look at -=mike=-'s Lair of the QuakeBot for some info on how he does navigation (I believe the movement paths have to be learned and cannot be pre-calculated for each level).
Dodging is one of the skills that make a bot great. Human reflexes just aren't fast enough sometimes to move out of the way of a rocket or nail. A dodging sub-system of the QuakeBot can be running all the time with no regards as to what the bot is doing. This way damage can be avoided when persuing, retreating, aquiring, attacking, camping, or whatever. Dodging, however, is closely linked to Navigation. You don't want your bot to move out of the way of a missile and into a lava pit! This makes it just as difficult to implement as Navigation, as the bot must know the level "map" (BSP tree).
Projectiles are not the only things that need to be dodged. Shotgun blasts can also be avoided by keeping out of the direct line of sight from other players. This way damage from the shotgun (whos pellets have infinite speed) can be avoided.
Dodging can also be used in order to pick up items which lie close to the bot's position or the path being traveled. A quick "dodge" to pick up a rocket launcher could help out a lot!
Artificial Intelligence (AI) is where the most fun can be had with a bot. However, it is usually the last thing to be implemented (if at all). The AI of the bot is the "brains" of the operation. It can decide to attack, retreat, gather, camp (if you want), etc. It also can be responsible for who to attack, where to gather, what to say, or anything else you wish. The possibilities are endless! AI can make a bot seem (almost) human.
There exists many AI methods, such as Neural Networks or Genetic Algorithms. This is left up entirely to the programmer. But, with most AI methods, some learning is required, so I guess it is not left entirely up to the programmer! See my QuakeBot Links to get some AI ideas.
This section contains some information that I have compiled for my usage. It may or may not help you. It does not deal directly with bot programming but some general Quake info.
Quake Shirt/Pants colors
0 - white
1 - brown
2 - powder blue
3 - green
4 - red
5 - amber
6 - gold
7 - pink
8 - purple
9 - dark purple
10 - grey
11 - aquamarine
12 - yellow
13 - blue
Quake Fonts
Click Here for the GIF file containing the extended character set and the corresponding hex and octal codes used for all Quake messages and player names.
Copyright © 1997 Chad Dreveny
All rights reserved.