I'm working on a caveman fps / rpg / simulator game.

because its a simulator, you can accelerate time, like in a flight simulator, or a submarine simulator, to skip past the dull stuff.

the game currently supports real time, 2x, 900x, and 5400x game speeds. Unlike waiting in Oblivion, you can do this with potential hostiles nearby. It automatically drops out of accelerated time if anything tries to attack you.

in the game, you can interact with the environment and perform actions (like in The SIMs) such as gathering resources and making weapons.

when performing an action such as making a wood spear, which takes 4 game hours, it runs fast with no active targets, and slow with a herd of 20 antelope mulling about. with no active targets, at 900x normal speed, making a spear takes 4 seconds (in real world time). with 20 active targets, at 900x normal speed, it takes 22 seconds (in real world time).

so i'm looking for ways to speedup the AI so it still does (or approximates) what it does in real time combat, but runs faster at 900x and 5400x normal speed.

so far i've gone to selecting target (which requires a range check to every active target) once every 5 seconds, and made the animals steer based on a desired heading calculated every 5 seconds (which requires a call to atan). these calculations are performed on every 15th target in succession over 15 frames. IE: if ( target_number % 15 == frame_number ) do_AI_stuff.

i'm using a fast RISC style 2d bounding box distance calculation for the range check when selecting target.

i tried an atan lookup function, but the math coprocessor is faster.

the amount of time between target selections is the amount of lag in response the targets exhibit. if an antelope is programmed to run when you get within 50 feet, it can take up to 5 seconds for it to target you, decide you're too close, and start running. So selecting targets even less frequently doesn't seem to be an option.

everything else in the AI except the range check to all targets and the atan call is fast simple code, mostly ADDs and COMPs.

however it does do a check once per second for being "cornered", which requires moving 4 points in 2d (4 sins and 4 cos's) and 4 collision checks (point vs axis aligned bounding boxes).

i can spread out the target and heading calculations so i'm only doing it for one target per frame, but i'd still be doing it for all targets over 5 seconds of game time. this would reduce per frame overhead to a maximum of one set of target calculations per frame, but not overall overhead.

i can do the "cornered" check every 5 or 10 seconds, that will get me a little something, but other than that, I'm not sure what to try next.

faking it? is that the answer? when all else fails, fake it?

Profile it.

yeah, unfortunately, there's not much left to slice out. i'm afraid that all profiling will tell me is that range checks to every active target take time, calculation heading with atan takes a little time, but is not done often, and all the rest is sort of spread out evenly across code that changes animal AI state (hunting/eating, wandering, standing, flocking, etc), adds stuff together, and checks if a > b kind of thing. while this still needs to be confirmed with timing tests, I suspect some "approximation" approach may be required, so i was sort of thinking ahead.

What are you using atan for? If it's a bottleneck, you may have luck replacing it with vector math (ex: dot products and cross products can handle the majority of gameplay logic relating to angles).

calculating compass heading in degrees from x1,z1 to x2,z2 in the x,z plane in world space.

hadn't occurred to me to try using vectors as a speedup.

but this get into the whole "how to store an orientation" question. and the whole issue of having to possibly convert a given method of storing orientation (unit direction vector) into something the graphics engine can take as input (Euler angles, etc).

the title uses a shooter interface, so orientations are stored as Euler angles (x,y,z rot), and the player is limited to two degrees of rotational freedom (xrot and yrot).

the graphics engine is based off of directx 9 fixed function pipeline for maximum compatibility as i recall, that API only supports Euler angles, rotation matrices, and quaternions as input. so any ugly math avoided by using vector stuff you eventually have to use to convert it into something the graphics engine can take as input.

however, if there's a lot of ugly math done before drawing, it may be faster to avoid the ugly math before drawing, and take the hit of one bit of ugly math to convert to graphics engine format.

have to think about that one, it may be a better way to do the whole "movement / orientation / graphics engine input format" thing.

first step, what input formats does the graphics engine support?

well, it takes a transformation matrix, and has a bunch of helper functions for creating matrices (D3DxMatrixRotationX, etc).

so, you store orientation as a direction vector. player can't rotate around Z axis, so don't need a rotation angle, so its not a quaternion, just a dir vector. so then you want to turn, and you have a desired direction vector. I dunno, maybe i'm just locked into trig thinking. I got an A in Linear at OSU but recall almost none of it (i can't even do a linear combination anymore, forgot how!). so i'd be calculatng angles based on projections, and determining whether my desired vector is left or right of my current vector, and by how much. just seems like the wrong kind of numbers to me. vectors are more about translation than rotation. but as i said, i recall almost zero linear, so there may be a way that i don't remember

really the way to do might be with a quat, since they can do it all, then simply limit the degrees of freedom for the game in question. but this may be overkill. i've only contemplated using quats in games with 3 degrees of rotational freedom.

Just use direction vector and your up vector to construct a matrix for the object. 2 of the rows will be the direction and up vector and the other one will be the cross product of those (need to normalise it if up and facing aren't perpendicular after doing the cross product).

Just use direction vector and your up vector to construct a matrix for the object. 2 of the rows will be the direction and up vector and the other one will be the cross product of those (need to normalise it if up and facing aren't perpendicular after doing the cross product).

I used a similar approach in my starship flight sim, but it had up, right, and forward unit vectors, as it had 3 degrees of rotational freedom.

to turn it, i'd rotate the three points around x,y,and z, then gram-shmidt. the engine was a p-correct t-mapped poly engine i wrote myself when MS bought rend386 and took it off the market, and before they released it as DirectX 1.0. Thee engine used euler angles for input, so I still had to do projections to extract the euler angles for drawing. it worked great, starships would swoop, dive, roll, etc.

right now i'm working on an airship flight sim. but again, its a 2 degrees of rotational freedom game, so it uses xrot and yrot for orientation.

before doing that, i tested storing orientation as a 4x4 matrix, and using gram-shmidt. its ok, at 1600x900, but not pixel perfect.

i really need to break down and learn quats. but that's not required until the next version of Gamma Wing or SIMSpace, or if i get motivated to do a WW1 fighter sim (like red barron 2).

i guess the idea with a quat is you can rotate the direction vector with a rotation matrix to turn on two of your axes, and simply increment or decrement zrot to rotate around local z.

Just use direction vector and your up vector to construct a matrix for the object. 2 of the rows will be the direction and up vector and the other one will be the cross product of those (need to normalise it if up and facing aren't perpendicular after doing the cross product).

ok, but how do you figure out which way to turn and climb/dive, given a current direction unit vector, and a desired direction unit vector?

calculating the displacement vector in each plane would just be SUBs, nice and fast, can do that 40,000 times a frame, no prob.

but that only gets you direction (left/rght) and final position (displacement, left or right), you'd still have to back solve to get the rotation amount.

the problem i'm trying to solve is this:

i'm a critter in the game. i have a current direction (yrot or current_direction_unit_vector). i have a current position x1,z1.

i have a target (another critter) at x2,z2. whats the direction to the target?

from this i can determine the relative heading to the target, by subtracting my heading from the heading to the target: rel_heading = heading to tgt - my yrot.

this tells me whether to turn left or right, and by how much, and if my target is in an "arc of fire" in front of me. arc of fire is used to turn attacking critters towards their target until abs(relheading) < 15 degrees, before they start to run towards the target, so they don't run in big circles. abs(relheading) < 45 degrees is used for testing if a target is "in strike zone" in melee combat.

the game used to pre-calculate relative heading to target once every frame for every active critter. calculating heading requires atan. basically atan dx/dz, trapping out the 4 cardinal point cases, and watching your signs and numerators and denominators, depending on the quadrant.

this was sufficient for real time, and 2x speed, but not for 900x and 5400x speeds.

i finished reorganizing the AI into nice modules, and making everything select target once every 5 seconds, and calculate heading to target when it selects target, and as needed when it changes AI state, such as an animal returning to a location its supposed to defend, and needing to calculate the heading to the nearest threat, now that is "back at its post" again. range to target is pre-calculated once per frame.

i re-ordered the checks in the loops that select a target, so that on average it will skip critters that should not be targeted sooner. no major speed up there. the select target routine used the most was already in optimal order.

other than finding a substitute for atan, abut the only other thing i can think of is speeding up the search for select target. its a loop that searches a static array of structs.

right now it searches the entire list (200 structs), even though there many only be 20 or so active. i was thinking of keeping track of the last active struct, and stopping the loop there. the list is un-ordered. after skipping inactive, dead, friendly, etc targets, is does a bbox range check. but once the simulation gets close to 200 active targets, that will be about 40,000 range checks each time targets are selected. at once every 5 game seconds, with a completion time of 4 game hours to make a woods spear, that works out to about 115.2 million range checks while the player sits and watches an animation of their caveperson making a wood spear (whats planned), or watches the world run at high speed in the background while a message displays progress (what it does now). 900x game speed draws one frame every game minute. 5400x speed draws one frame every game hour. so the effect right now with the progress message is like watching time lapse photography. if the game didn't have 3rd person view, i might not do the animations at all.

one speedup i though of (inspired by the displacement vector idea):

instead of calculating heading(x1,z1,x2,z2) using atan:

dx=x2-x1

dz=z2-z1

by checking for dz or dz = 0 you get the 4 cardinal directions

by checking dx > dz and dx < dz, you get the 45 degree cases, and can pin everything else down to an octet (22.5 degrees). by checking for things like dx > 2*dz you can get it down narrower than an octet. this may be a good enough approximation.and requires no atan, just SUBs, COMPs, and maybe some MULs.