The mikeBot Project Times


Developer notes June 30, 1997 $1.50 Sundays

Mike Writes Developer Notes

[ May 11, 1997, mikeBot press ] After weeks of memo-writing and email-sending, we were finally able to track down Project leader Mike and convince him (mostly through large sums of money) to write Developer Notes for aspiring client-side quake bot developers.

If you would like to see something here, please tell mike

and he'll see what he can do. If you find any errors, he has asked us to please tell him.

Also, it should be noted these don't really fall into any sort of order and are more random interesting things to do with bot development. The pseudo-code is sorta C++-ish, in case that isn't obvious. Have fun!


Available Articles


Predictive Firecontrol Iterative Method

the problem:

How do I predict where to shoot without fancy math?

the solution: Taken partially from the Stooge Bot pages.

The soluction basically involves "guessing" where the target will be when your projectile hits it, calculating how far off you are (error) and repeating until the error is within acceptable bounds.


#include <math.h>

#define ERROR_TOLERANCE  0.01
#define LOOP_MAXIMUM     10

vector predictTargetPosition( vector targetPosition, vector myPosition,
                              vector targetVelocity, float projectileSpeed,
                              float latency )
{
  float time = 0.0;		// time for projectile to reach target
  float timeEstimate;		// estimated time for projectile arrival
  float error;			// error in target location
  int loopCount=0;		// number of times through loop
  vector targetLocation = targetVelocity;

  do {
    loopCount++;
    targetLocation = time * targetVelocity + targetLocation;
    timeEstimate = ((myPosition - targetLocation).length() / projectileSpeed) + latency;
    error = fabs( timeEstimate - time );
    time = timeEstimate;
  } while( error > ERROR_TOLERANCE && loopCount < LOOP_MAXIMUM );

  return targetLocation;
}

Testing with mikeBot indicated that the loop never executed more than 6 times (depending on what the ERROR_TOLERANCE was set to...)

A good ERROR_TOLERANCE seems to be around 0.01, which gives fairly accurate results with minimal loop-execution (the above-mentioned 6 was attained with tolerance set to 0.01).

The latency variable is the number of seconds of latency*, which can be used to also compensate for lag along with the the target's motion. For shotguns (whose speed is infinite), simply make the timeEstimate the latency (which is intuitivly, if not mathematically, correct).

Also, be sure to check out the other solution to this problem, which uses direct calculation instead of a loop.

* Latency refers to the one-way trip to the server, whereas ping is the round-trip. Therefore, if your ping is 200ms, your latency is 0.100 seconds.

Point in polygon.

the problem:

How can I tell if a point is inside a polygon?

Assumptions:

the solution

the algorithm

Imagine standing inside the polygon. As you look from the first vertex to the second and all the way around (back to the first one), you spin 360 degrees. If you are outside the polygon, you will turn one way, then back again; you will not have rotated 360 degrees.

Determining the angle between two vectors is based on the definition of the dot product:

u . v = ||u|| ||v|| cos t
Where t is the angle between the vector, so:
t = arccos( (u . v) / (||u|| ||v||) )

the pseudocode

bool pointInPolygon( polygon & p, vector & v )
{
	vector fv = p[0]-v, lv;
	vector first=fv;
	float angle=0.0;

	if( p.numVertices < 3 )			// Must be at least a triangle
		return FALSE;

	for( int i=1; i < p.numVertices; i++ )
	{
		lv = p[i] - v;
		angle += acos( (fv * lv) / (fv.length() * lv.length()) );
		fv = lv;
	}

	lv = p[0] - v;                            // go back to first vertex
	angle += acos( (fv * lv) / (fv.length() * lv.length()) );

	if( angle > 3.141 && angle < 3.142 )      // margin of error
		return TRUE;

	return FALSE;
}
What are the RGB values of player colours?

the problem:

What are the RGB values of the different player colours in quake?

the solution

I got these values from the Quake Network Protocol page by a.oliber.

numberRGB (decimal; max is 255)colour
0123 123 123 
1 83 59 27 
2 79 79 115  
3 55 55 7  
4 71 0 0  
5 95 71 7  
6 143 67 51  
7 127 83 63  
8 87 55 67  
9 95 51 63  
10 107 87 71  
11 47 67 55  
12 123 99 7  
13 47 47 127  

Determining if a line hits the BSP tree

the problem:

Does a line from A to B intersect a wall in the BSP-tree?

note that the following C++ pseudo-code makes some assumptions about the way the .BSP file was loaded; please email any ambiguities...

the solution:

The following pseudo-code was converted (basically) from the Terminator source.

int doesLineHitWall( vector A, vector B )
{
	stack< vector > vstack;
	stack< bspNode > nstack;

	vector start, end;
	bspNode startNode,endNode,node;
	float e,s;

	start = A;
	end = B;
	node = bspRoot();

	while( 1 )
	{
		if( !node.isLeaf() )
		{
			e = distanceToPlane( end, node.splitPlane.normal );
			s = distanceToPlane( start, node.splitPlane.normal );
			if( e > 0.0 )
				endNode = node.front();
			else
				endNode = node.back();
			if( s > 0.0 )
				startNode = node.front();
			else
				startNode = node.back();

			if( endNode != startNode && s != e )   // note rounding error on floats
			{
				nstack.push( endNode );
				vstack.push( end );
				end = (s*end - e*start) / (s-e);  // intersection of start-end and split plane
			}	
			node = startNode;
		}
		else
		{
			if( node.type == node::wall )
				return TRUE;
			start = end;
			if( vstack.isEmpty() )
				break;
			end = vstack.pop();
			node = nstack.pop();
		}
	}

	return FALSE;
}

			
	

	



Finding which leaf in the BSP I'm in

the problem:

How do i know which leaf of the BSP tree I'm in?

note that the following C++ pseudo-code makes some assumptions about the way the .BSP file was loaded; please email any ambiguities...

the solution:

The following pseudo-code will determine which leaf you are in. It was converted (basically) from the Terminator source.


leaf whereInBSPtreeAmI( vector position )
{
	bspNode node;
	float dist;

	if( bsp.mapNotLoaded() )
		return Nothing;

	node = bsp.root();

	while( !node.isLeaf() )
	{
		// dist = distance from position to split plane			

		dist = (normal . position) - distance;
		if( dist > 0.0 )
			node = node->front();
		else
			node = node->back();
	}

	return node;

}

seperating firecontrol and navigation

the problem:

Given a vector representing the direction you are facing (call it A) and a vector representing where you want to go (call it B), and a velocity, what are the lengths of vectors A and C parrallel and perpendicular, respectivly, to A (i.e forward speed and side speed). (see the diagram...)

the solution: (by Iikka Paavolainen)


If ua and uc are the unit vectors in the directions of A and C
then

|A| = uax*Bx + uay*By

|C| = ucx*Bx + ucy*By

i.e. the dot products of ua and B, and uc and B.

If B just points in the direction you want to move but its size is not v,
then first adjust it using B = B/|B| * v.

Alternatively, and more simply, if you know the angle (ang) between A and
B:

|A| = v*cos(ang)

|C| = v*sin(ang)

(This can be derived with trigonometry, by considering two triangles.)

** Iikka Paavolainen
** ipaavola@cc.hut.fi

predictive firecontrol

the problem

Projectiles such as rockets are slow; how do i know where to fire in order to "lead" a target? What are the velocities of spikes/rockets etc.?

the solution: (by Iikka Paavolainen)


pdx,pdy,pdz = position of enemy relative to firer's position
vex,vey,vez = velocity vector of enemy
vmx,vmy,vmz = velocity vector of projectile (undefined at first)
v = speed (scalar) of projectile
t = time taken for projectile to reach enemy

We have:

pdx+vex*t=vmx*t
pdy+vey*t=vmy*t
pdz+vez*t=vmz*t

and

v^2=vmx^2+vmy^2+vmz^2

The three position equations above can be put in the form:

vmx^2=(pdx/t+vex)^2
vmy^2=(pdy/t+vey)^2
vmz^2=(pdz/t+vez)^2

Summing these together and substituting the v^2 equation we get:

v^2=(pdx/t+vex)^2+(pdy/t+vey)^2+(pdz/t+vez)^2

Expanding the powers, multiplying both sides by t^2 and collecting terms
yields:

(vex^2+vey^2+vez^2-v^2)*t^2+2(pdx*vex+pdy*vey+pdz*vez)*t+
(pdx^2+pdy^2+pdz^2)=0

Hence,

a=vex^2+vey^2+vez^2-v^2
b=pdx^vex+pdy^vey+pdz^vez
c=pdx^2+pdy^2+pdz^2

And then we find the solution for the quadratic equation

at^2+bt+c=0

using these values.

Only the solution with -sqrt(...) is applicable as +sqrt(...)
will yield negative values for t.
The solution is defined for all v^2 > vex^2+vey^2+vez^2,
ie. the velocity of the projectile must be higher than the velocity
of the enemy (or otherwise the projectile could never catch the enemy).

** Iikka Paavolainen
** ipaavola@cc.hut.fi

The following table sumarizes experimental results for projectile speed of various weapons (if any are wrong, tell me):

weaponmodelvelocity (quake units / second)
SG/SSGnoneinfinite
nailgunspike.mdl?1000.0 QU/sec, 500.0 QU/sec
SNGs_spike.mdl1000.0 QU/sec
RLmissle.mdl1000.0 QU/sec
GLgrenade.mdl? fastest i've seen is 320.0

I've seen spike.mdls travelling at both 500.0 and 1000.0...


Fully-autonomous
mikeBot Now
client-side quake bot
Best experienced with
Microsoft Internet Explorer
Click here to start.
Proud member of
Bot Author's Guild
The Bot Author's Guild