[TI ASM/pseudo] General algorithms

coelurus · Post by **coelurus** » Mon 28 May, 2007 4:11 pm

Be careful with trig tables, they can be useful on calcs/portables/similar but they they are actually slower than the builtin sin/cos functions on the common PC (unless you make the whole shebang in fixed point with no over- or underflows, but uhm...). Plus sin/cos has better precision and are periodic. Generally, reading from memory is a hog these days, LUTs are only applicable for very complex calculations.

King Harold · Post by **King Harold** » Mon 28 May, 2007 6:01 pm

This is periodic. *points at %*
It's meant for your calc really. It does the same as the build-in sine function but you have some control over the precision etc.

coelurus · Post by **coelurus** » Mon 28 May, 2007 11:14 pm

Not really, it overflows unless the LUT is N+1 big. Picky, I know

Btw, do you really need lerped trigs on the calc?

King Harold · Post by **King Harold** » Tue 29 May, 2007 9:04 am

Alright alright you need 1 more element.. But it's still periodic (with a little gap..)
And no you don't really, but what if you wanted to use some anyway? The calc's sin( function is extremely slow, so I wouldn't use that if speed is even a bit important. One Sin( call could destroy the effect of every bit of optimization you did..
A good thing about a custom sine routine is that you can optimize it the way you want, for speed, for size, or even both, which will make it fit into the context of your program better.

coelurus · Post by **coelurus** » Tue 29 May, 2007 2:23 pm

Gemini did fairly well with a one-sample LU and that game required some precision. And to make use of a really stupid pun, using Sin( is a real... You get the idea :p

King Harold · Post by **King Harold** » Tue 29 May, 2007 3:33 pm

lol yes, with 8bit arithmetic the lerp isn't really that much work, a sub, a mult and an add, you wouldnt even have to AND [somenumber] if you use a full 256-byte table (or is it 257?) - BUT with 8bit numbers you won't need to lerp at all. For Floats you would, though, and the bcall - that is really.. yea you know

Halifax · Post by **Halifax** » Wed 30 May, 2007 11:29 pm

King Harold wrote:The same way as on 2D, just extend it to go into the 3rd dimension aswell, forexample: instead of checking all 8 squares around you, check all 26 cubes around you, all coordinates will - ofcourse - have to contain a 3rd element.
The amount of memory really explodes when adding dimensions, you won't want to try a 4th or 5th in a real-time game (it's not like you'll need them anyway though).
Many 3D games use pre-calculated paths which are stored with the maps, and do not do any pathfinding at all (units sometimes get stuck in those games), and there are a lot of 3D games in which you can only walk on the ground anyway - then pathfinding is just 2D.

I am guessing CryENGINE 2.0 doesn't use that precalculated method since you can program the AI to go to just about any point in the entire test level. It actually looks like it is using Bezier curves to calculate where the AI should walk to make a smooth transition of walking with the mesh blending. Hmm I could be wrong though because I don't know how you would you bezier curves if he hits something. Oh well I will have to research this more.

coelurus · Post by **coelurus** » Thu 31 May, 2007 6:30 am

Crytek uses waypoints for some tasks such as patrolling, but I guess they also use 'em indoors (haven't seen a lot of indoors action, the houses tend to break in the gameplay vids

). Since the game is heavily based on outside heightfields, it shouldn't be overly complex to map a route for an object with respect to obstacles without waypoints (create a "wide" polygonal path from A to B without hitting anything and then do a catmull-rom spline or sumthin').