Chris Paulson

String pulling:- Imagine a 2d square grid and you did a path from one point to another, the path would have zig zags in if you used the centre of each square. String pulling smooths out the zig zags. To help with this, imagine a string tied to a peg and it works its way between lots of other pegs in a loose zig zag way. Now imagine pulling the string so the string is tight against all the pegs. Ta da - string pulling.

Sorry forgot to mention A* is used for walking any sort of graph, the graph could be representing lots of different things such as:- Navmesh Waypoint graph Motion graphs Covermaps Anywhere where you have a node with a link to another node and you can calc getting from A to B using a cost heuristic. Check out http://theory.stanford.edu/~amitp/GameProgramming/ for a good explanation.

Hi, I know I like a sound like a stuck record.... but recast has the A* algorithm in it so this is already done. I've also written a version that worked with my own abandoned navmesh stuff which is in blitzmax. Along with a A* algorithm you usally need a string pulling algorithm, which again is in recast and I've also wrote in blitz. If you want all the info on navmesh's A* etc read this blog http://digestingduck.blogspot.com/ it will have all you'll ever want to know. Or/and read this PDF:- https://8655380626601746424-a-1802744773732722657-s-sites.googlegroups.com/site/recastnavigation/MikkoMononen_RecastSlides.pdf?attachauth=ANoY7co69z1vjPcvn42QIdX2cYY6w5Qp9HYA8pZiMXS7sWSGoe--OONRdNsxY8F9UUIFFHf2HUBKaYOtxGrfWN6EboojcXsXjnxVyFF-bm2wHBe4tHsq_wYbEYudxkhsiDgEYHQ7biqhOAlawYp6hMP9bwawtKkAw2Qy-gXWs32P0Iym3dkL3TM4ebWiGynr2OU7n1bh6ws1c3xt2ABTT3mQXm94_z0IE8a07kiLoQV4z6_SnZFLLOY%3D&attredirects=0

I've tried doing this in the past but I failed. The problems I encounted is: - 1) Performance over a long distance 2) Complicated enviroment with dead ends - you'll search down a dead end and have to come back 3) Complicated enviroments with stairs door etc. You said :- Hand placing is an old fashioned approach which no current games do. .... Just trying to save you going down blind alleys.

Very impressed with video, as a non artist I'm a fan of the sketchup type interface.

I am interested in this project but I won't join as it would be unfair to everyone as I am unreliable with the amount of time I can commit. As my personal code base improves though the community is welcome to use/copy/learn from. Hope this helps Chris

After the load scene is done I feed in all the polygon data (verts/tris) from the terrain and models into recast. Like I say look use my code as a leg up, I've done a fair amount of work on it, I beleive Davris has managed to use my code. It also copes with dynamically updating the navmesh with dynamic objects, such as a barrel moving. I have not yet written the streaming of the static mesh out but I'll do this when I've finished my current project. I beleive the most recent version of recast may already have this in (but my code does work with the latest version yet). My code should be in the downloads section, "my game.zip". It also has behaviour tree stuff in which is a better way of doing stuff than FSMs. It also has opensteer in for agent steering. The code is messy as it's all WIP - but it is free.

There is more to AI then simple "if then" code. For example: - Cover point analyse for FP shooters.. Motion graphs (animation) Pathfinding graphs Etc etc AI for a descent FP shooter is doing a lot of maths working on a large amount of data. Speed matters! Thats why AAA titles have to run AI in mutiple threads/cell processors etc.

I've posted all my code which interfaces with recast. You might not like my code but it will give you a leg up.

You'll get different answers from people about speed and whether it matters depending on how far down the road of development they are. Beleive me once you got: - Pathfinding Motion graphs/blend trees AI (FSM, HFSM, BTs) Lots of physics IK animation Lots of line picks Agent Steering Cover maps etc (all the things you need to make a half decent game) you'll start noticing a BIG difference and you'll be looking to squeeze every ms you can. There is more to a game other than shaders, pretty lights, fluffy cloads and waves...

You already can with the GMF library stuff.

Looks like the white lines are just part of the grid displayed by the editor showing through the terrain. How did you add the grass? Is it a model?

Hi, I've updating my blog with a video of the IK and the source code. Enjoy... Blog: - http://leadwerks.com/werkspace/index.php?app=blog&module=display&section=blog&blogid=19

To get nice locomotion and not have NPC walking with feet stuck in the terrain or hovering in the air you need to place the feet to match the terrain, coping with slopes etc. Leadwerks has forward kinematics but not inverse (which is needed to do this). Because of this I have written (with help) an IK solver. Thanks to Tyler for supplying the code as a starting point. Here's a video of it working: - Here's the code (I actually ended up doing 2 solvers) #include "IKSimple.h" #include "engine.h" float IKSolver::positionAccuracy = 0.001f; int IKSimple::maxIterations = 100; float IKSimple::calcBonesLength() { boneLength.resize(bones.size()-1); float totalLength = 0.0f; for (int j = 0; j < (bones.size() - 1); j++) { Vector3 vector = bones[j + 1].localPosition() - bones[j].localPosition(); boneLength[j] = vector.Magnitude(); totalLength += boneLength[j]; } this->positionAccuracy = totalLength * 0.001f; return totalLength; } void IKSimple::Solve( TEntity entity, std::vector<Transform> pbones, Vector3 target) { /// Local Variables /////////////////////////////////////////////////////////// Vector3 rootPos,curEnd,desiredEnd,targetVector,curVector,crossResult; double cosAngle,turnAngle,turnDeg; int link,tries; Quaternion aquat; /////////////////////////////////////////////////////////////////////////////// // START AT THE LAST LINK IN THE CHAIN bones = pbones; startBone = &pbones[0]; endBone = &pbones[pbones.size() - 1]; link = pbones.size() - 1; tries = 0; // LOOP COUNTER SO I KNOW WHEN TO QUIT do { // THE COORDS OF THE X,Y,Z POSITION OF THE ROOT OF THIS BONE IS IN THE MATRIX // TRANSLATION PART WHICH IS IN THE 12,13,14 POSITION OF THE MATRIX rootPos = pbones[link].localPosition(); // POSITION OF THE END EFFECTOR curEnd = endBone->localPosition(); // DESIRED END EFFECTOR POSITION desiredEnd = target; // SEE IF I AM ALREADY CLOSE ENOUGH if ( curEnd.DistanceSquared(desiredEnd) > positionAccuracy) { // CREATE THE VECTOR TO THE CURRENT EFFECTOR POS curVector = curEnd - rootPos; // CREATE THE DESIRED EFFECTOR POSITION VECTOR targetVector = target - rootPos; // NORMALIZE THE VECTORS (EXPENSIVE, REQUIRES A SQRT) curVector.Normalize(); targetVector.Normalize(); // THE DOT PRODUCT GIVES ME THE COSINE OF THE DESIRED ANGLE cosAngle = targetVector.Dot( curVector); // IF THE DOT PRODUCT RETURNS 1.0, I DON'T NEED TO ROTATE AS IT IS 0 DEGREES if (cosAngle < 0.99999) { // USE THE CROSS PRODUCT TO CHECK WHICH WAY TO ROTATE crossResult = curVector.Cross(targetVector); crossResult.Normalize(); turnAngle = acos((float)cosAngle); // GET THE ANGLE turnDeg = rad2deg(turnAngle); // COVERT TO DEGREES // DAMPING turnDeg *= pbones[link].m_damper; aquat = Quaternion::Quaternion(crossResult, turnDeg ); aquat = pbones[link].boneLocalRotation() * aquat; pbones[link].setLocalRotation( aquat ); } if (--link < 0) link = pbones.size() - 1; // START OF THE CHAIN, RESTART } // QUIT IF I AM CLOSE ENOUGH OR BEEN RUNNING LONG ENOUGH } while (tries++ < maxIterations && curEnd.DistanceSquared( desiredEnd) > positionAccuracy); } void IKSimple::calcCurrentBones( ) { rotateArray.resize(bones.size()-2); angles.resize(bones.size()-2); quaternionArray.resize(bones.size()-2); // Work out where current bones are for (int i = 0; i < (bones.size() - 2); i++) { rotateArray[i] = (bones[i + 1].localPosition() - bones[i].localPosition()).Cross(bones[i + 2].localPosition() - bones[i + 1].localPosition()); rotateArray[i] = (Vector3) ((bones[i].localRotation().Inverse()) * rotateArray[i]); rotateArray[i].Normalize(); angles[i] = (bones[i + 1].localPosition() - bones[i].localPosition() ).Angle(bones[i + 1].localPosition() - bones[i + 2].localPosition() ); quaternionArray[i] = bones[i + 1].localRotation(); } } void IKSimple::SolveRelative( TEntity entity, std::vector<Transform> pbones, Vector3 target) { float doLow; float doHigh; bones = pbones; startBone = &bones[0]; endBone = &bones[bones.size() - 1]; // Work out length of bones float totalLength = calcBonesLength(); Vector3 curdis = endBone->localPosition() - startBone->localPosition(); float currentDistance = curdis.Magnitude(); Vector3 vtarget = target - startBone->localPosition(); float targetDistance = vtarget.Magnitude(); bool minFound = false; bool moreToDo = false; if (targetDistance > currentDistance) { minFound = true; doHigh = 1.0f; doLow = 0.0f; } else { moreToDo = true; doHigh = 1.0f; doLow = 0.0f; } int currentIter = 0; while ((abs((float) (currentDistance - targetDistance)) > this->positionAccuracy) && (currentIter < this->maxIterations)) { float newBend; currentIter++; if (!minFound) newBend = doHigh; else newBend = (doLow + doHigh) / 2.0f; for (int i = 0; i < (bones.size() - 2); i++) { float calcAngle; if (!moreToDo) { calcAngle = math::Lerp(180.0f, angles[i], newBend); } else { calcAngle = (angles[i] * (1.0f - newBend)) + ((angles[i] - 30.0f) * newBend); } float angleDiff = angles[i] - calcAngle; Quaternion newRot = Quaternion::Quaternion(rotateArray[i], angleDiff ); newRot = quaternionArray[i] * newRot; bones[i + 1].setLocalRotation( newRot ); } Vector3 totalLen = endBone->localPosition() - startBone->localPosition(); currentDistance = totalLen.Magnitude(); if (targetDistance > currentDistance) minFound = true; if (minFound) { if (targetDistance > currentDistance) doHigh = newBend; else doLow = newBend; if (doHigh < 0.01f) break; } else { doLow = doHigh; doHigh++; } } // Change master bone (if we was doing a leg this would be the hip) float hipAngle = (endBone->localPosition() - startBone->localPosition()).Angle(target - startBone->localPosition()); Vector3 hipAxis = (endBone->localPosition() - startBone->localPosition()).Cross(target - startBone->localPosition()); AngleAxis hipAngleAxis = AngleAxis( hipAxis, hipAngle ); Quaternion hipRot = startBone->localRotation() * Quaternion::Quaternion( hipAngleAxis ); startBone->setLocalRotation( hipRot ); } Here's the transform object which controls the bones. It was a little bit tricky to do because LE annoyingly does local rotation relative to the parent bone not relative to the model. #ifndef TRANSFORM_H #define TRANSFORM_H /// @file locomotion\tranform.h /// @brief This is the transform object which handles rotation/positioning of bones /// for the IK solver /// #include "SVector3.h" #include "SQuaternion.h" class Transform { public: Transform() {}; Transform(TEntity parent, TEntity entity) : m_parent(parent) { m_entity = entity; TVec3 v; v = EntityScale(entity); m_scale = Vector3(v.X,v.Y,v.Z); v = Vec3(0,1,0); v = TFormVector(v, entity, NULL); m_up = Vector3(v.X,v.Y,v.Z); v = Vec3(0,0,1); v = TFormVector(v, entity, NULL); m_forward = Vector3(v.X,v.Y,v.Z); v = Vec3(1,0,0); v = TFormVector(v, entity, NULL); m_right = Vector3(v.X,v.Y,v.Z); m_damper = 1; m_minRotation = Vector3(-360,-360,-360); m_maxRotation = Vector3(360,360,360); } inline Quaternion boneLocalRotation() { TVec3 v; v = EntityRotation(m_entity,0); Quaternion q = Quaternion( Vector3(v) ); return q; } inline Quaternion localRotation() { TVec3 v; TEntity par = GetParent( m_entity ); EntityParent( m_entity, m_parent ); v = EntityRotation(m_entity,0); EntityParent( m_entity, par ); Quaternion q = Quaternion( Vector3(v) ); return q; } inline Quaternion rotation() { TVec3 v; v = EntityRotation(m_entity,1); Quaternion q1 = Quaternion(Vector3(v)); return q1; } inline void alignToVector( Vector3 v, int axis = 3, int rate = 1, int roll = 0 ) { AlignToVector( m_entity, v.vec3(), axis, rate, 0); } inline void setLocalRotation( Quaternion rot ) { Vector3 vrot; vrot = rot.eulerAngles(); vrot.X = __max( vrot.X, m_minRotation.X ); vrot.Y = __max( vrot.Y, m_minRotation.Y ); vrot.Z = __max( vrot.Z, m_minRotation.Z ); vrot.X = __min( vrot.X, m_maxRotation.X ); vrot.Y = __min( vrot.Y, m_maxRotation.Y ); vrot.Z = __min( vrot.Z, m_maxRotation.Z ); RotateEntity( m_entity, vrot.vec3(), 0); } inline void setRotation( Quaternion rot ) { Vector3 vrot; vrot = rot.eulerAngles(); RotateEntity( m_entity, vrot.vec3(), 1); } inline Vector3 position() { TVec3 v; v = EntityPosition(m_entity,1); v = TFormPoint(v ,NULL, m_parent); return Vector3( v ); } inline Vector3 localPosition() { TVec3 v; v = EntityPosition(m_entity, 1); v = TFormPoint(v, NULL, m_parent); return Vector3( v ); } TEntity m_entity; Vector3 m_minRotation; Vector3 m_maxRotation; float m_damper; private: TEntity m_parent; Vector3 m_scale; Vector3 m_up; Vector3 m_forward; Vector3 m_right; }; #endif Just ask if you want me to supply the Vector3 and Quaternion math code if you need it.

Well last night I got it working. I need to improve the joint constraints and pick the spaghetti out of my code and I'll post it. Watch this space.

True, but for a: - hip, knee, ankle, toe you are solving mutiple rotations which is where it gets tricky (for me at least). Hopefully in a couple of days I'll have it working and I'll post all the code.

I thought I'd chuck my views to this. I spent several weeks investigating UDK as it's got so many more features than LE. However I came back to LE because I found myself banging my head against a brick wall in UDK and not having fun. I do the stuff in LE for fun, no other reason at the moment. If I was going to pick features from UDK I'd like to see in LE these would be them: - 1) >5 terrain layers 2) Fracture tool (having to do doing this by hand is a lot of work) 3) Emitters (UDKs emitters are strong, LE's are weak in comparison) 4) CSG (Useful for filling over gaps in levels) These things below I have done in LE but come as standard in UDK 5) Navmesh (without this you have no AI starting point for a modern game) 6) Locomotion 7) Complex animation blending There's lots of other stuff in UDK that I'd like to see in LE but I don't won't to overload Josh and make him think I'm a whinging git.

I've now got the IK working as long as the model is not rotated. Just need to handle rotations now.

Thought I'd post a progress update on this as I'm still trying to get this to work... The quaternion class did need to convert to/from radian/degrees. The class needed a new method for converting the quaternion to eualer angles. I wish you could get/set quaternions in LE (at present there's only a get). Somewhere in the code there is a math error because it's not IK'ing properly. If anyone is best mates with Pythagoras or his brother Trig feel free to pitch in...

Josh could probably answer this best but I'll have a go. My experience is also that occlusion culling is off on most things other than animated models. I believe you can turn it on with a function call. I haven't got the editor to hand but isn't there a new option for this to in the properties? I guess other things that might help are a combinations of: - DOF Merged into Fog With draw distance.

I'm struggling to get this to work. My code is:- void ikRanger( TVec3 position, TModel npc ) { TEntity lhip = FindChild( npc, "Frame3_figure_v05_Layer35"); TEntity lknee = FindChild( npc, "R_Knee"); TEntity lfoot = FindChild( npc, "R_Foot"); Transform thip( lhip ); Transform tknee( lknee ); Transform tfoot( lfoot ); vector<Transform> bones; bones.push_back( thip ); bones.push_back( tknee ); bones.push_back( tfoot ); IKSimple iknpc; iknpc.Solve( bones, Vector3( position.X, position.Y, position.Z )); Vector3 rot = thip.localRotation.ToAngleAxis().Axis; RotateEntity( lhip, Vec3( rot.X, rot.Y, rot.Z ) ); rot = tknee.localRotation.ToAngleAxis().Axis; RotateEntity( lknee, Vec3( rot.X, rot.Y, rot.Z ) ); rot = tfoot.localRotation.ToAngleAxis().Axis; RotateEntity( lfoot, Vec3( rot.X, rot.Y, rot.Z ) ); /* RotateEntity( lhip, Vec3( rad2deg(rot.X), rad2deg(rot.Y), rad2deg(rot.Z) ) ); rot = tknee.localRotation.ToAngleAxis().Axis; RotateEntity( lknee, Vec3( rad2deg(rot.X), rad2deg(rot.Y), rad2deg(rot.Z) ) ); rot = tfoot.localRotation.ToAngleAxis().Axis; RotateEntity( lfoot, Vec3( rad2deg(rot.X), rad2deg(rot.Y), rad2deg(rot.Z) ) ); */ } Is "thip.localRotation.ToAngleAxis().Axis" the correct thing to get back the rotations with? The transform class does: - v = EntityRotation(entity,1); this->rotation = Quaternion(Vector3(v.X,v.Y,v.Z)); Isn't EntityRotation in degrees and Quaternion in rads? Should there not be a conversion? Pity thrown at someone as bad at maths as me would be appreciated.

Thanks, I'll try this out tonight against my model. I guess the bones I pass in as transforms are: - Hip, Knee, Foot(Ankle) PS I wish I was better at math , you make it look easy.

Yes please for the zip. I must have be replying when you did the seconds post.

I recognise that code.... Looks like your getting there before me. Your using classes like Vector3 etc where do they come from? Could I put my begging bowl out and ask for a code share...

The good news:- I got a animated model moving it's limbs in sync with the physics bodies. The bad news:- I think this is a dead end as the physics solves the IK too slow and if you try to speed it up it oscillates. I think I need to write a proper IK solves, it will probably be easier than flogging the physics to death.