diff options
Diffstat (limited to 'source/gameengine')
24 files changed, 2857 insertions, 26 deletions
diff --git a/source/gameengine/Converter/BL_BlenderDataConversion.cpp b/source/gameengine/Converter/BL_BlenderDataConversion.cpp index af768050bb6..4b475a4b5e7 100644 --- a/source/gameengine/Converter/BL_BlenderDataConversion.cpp +++ b/source/gameengine/Converter/BL_BlenderDataConversion.cpp @@ -180,6 +180,9 @@ extern Material defmaterial; /* material.c */ #include "BL_ArmatureObject.h" #include "BL_DeformableGameObject.h" +#include "KX_NavMeshObject.h" +#include "KX_ObstacleSimulation.h" + #ifdef __cplusplus extern "C" { #endif @@ -1743,7 +1746,14 @@ static KX_GameObject *gameobject_from_blenderobject( // needed for python scripting kxscene->GetLogicManager()->RegisterMeshName(meshobj->GetName(),meshobj); - + + if (ob->gameflag & OB_NAVMESH) + { + gameobj = new KX_NavMeshObject(kxscene,KX_Scene::m_callbacks); + gameobj->AddMesh(meshobj); + break; + } + gameobj = new BL_DeformableGameObject(ob,kxscene,KX_Scene::m_callbacks); // set transformation @@ -2713,6 +2723,46 @@ void BL_ConvertBlenderObjects(struct Main* maggie, converter->RegisterWorldInfo(worldinfo); kxscene->SetWorldInfo(worldinfo); + //create object representations for obstacle simulation + KX_ObstacleSimulation* obssimulation = kxscene->GetObstacleSimulation(); + if (obssimulation) + { + for ( i=0;i<objectlist->GetCount();i++) + { + KX_GameObject* gameobj = static_cast<KX_GameObject*>(objectlist->GetValue(i)); + struct Object* blenderobject = gameobj->GetBlenderObject(); + if (blenderobject->gameflag & OB_HASOBSTACLE) + { + obssimulation->AddObstacleForObj(gameobj); + } + } + } + + //process navigation mesh objects + for ( i=0; i<objectlist->GetCount();i++) + { + KX_GameObject* gameobj = static_cast<KX_GameObject*>(objectlist->GetValue(i)); + struct Object* blenderobject = gameobj->GetBlenderObject(); + if (blenderobject->type==OB_MESH && (blenderobject->gameflag & OB_NAVMESH)) + { + KX_NavMeshObject* navmesh = static_cast<KX_NavMeshObject*>(gameobj); + navmesh->SetVisible(0, true); + navmesh->BuildNavMesh(); + if (obssimulation) + obssimulation->AddObstaclesForNavMesh(navmesh); + } + } + for ( i=0; i<inactivelist->GetCount();i++) + { + KX_GameObject* gameobj = static_cast<KX_GameObject*>(inactivelist->GetValue(i)); + struct Object* blenderobject = gameobj->GetBlenderObject(); + if (blenderobject->type==OB_MESH && (blenderobject->gameflag & OB_NAVMESH)) + { + KX_NavMeshObject* navmesh = static_cast<KX_NavMeshObject*>(gameobj); + navmesh->SetVisible(0, true); + } + } + #define CONVERT_LOGIC #ifdef CONVERT_LOGIC // convert logic bricks, sensors, controllers and actuators diff --git a/source/gameengine/Converter/CMakeLists.txt b/source/gameengine/Converter/CMakeLists.txt index 6cfd8c9b42b..fcb608a5830 100644 --- a/source/gameengine/Converter/CMakeLists.txt +++ b/source/gameengine/Converter/CMakeLists.txt @@ -57,6 +57,7 @@ set(INC ../../../source/blender/gpu ../../../source/blender/ikplugin ../../../extern/bullet2/src + ../../../extern/recastnavigation/Detour/Include ) set(INC_SYS diff --git a/source/gameengine/Converter/KX_ConvertActuators.cpp b/source/gameengine/Converter/KX_ConvertActuators.cpp index 01516a24182..a8d5ab0b2ff 100644 --- a/source/gameengine/Converter/KX_ConvertActuators.cpp +++ b/source/gameengine/Converter/KX_ConvertActuators.cpp @@ -67,6 +67,7 @@ #include "KX_SCA_ReplaceMeshActuator.h" #include "KX_ParentActuator.h" #include "KX_SCA_DynamicActuator.h" +#include "KX_SteeringActuator.h" #include "KX_Scene.h" #include "KX_KetsjiEngine.h" @@ -94,6 +95,7 @@ #include "BL_ActionActuator.h" #include "BL_ShapeActionActuator.h" #include "BL_ArmatureActuator.h" +#include "RNA_access.h" /* end of blender include block */ #include "BL_BlenderDataConversion.h" @@ -1026,6 +1028,45 @@ void BL_ConvertActuators(char* maggiename, baseact = tmparmact; break; } + case ACT_STEERING: + { + bSteeringActuator *stAct = (bSteeringActuator *) bact->data; + KX_GameObject *navmeshob = NULL; + if (stAct->navmesh) + { + PointerRNA settings_ptr; + RNA_pointer_create((ID *)stAct->navmesh, &RNA_GameObjectSettings, stAct->navmesh, &settings_ptr); + if (RNA_enum_get(&settings_ptr, "physics_type") == OB_BODY_TYPE_NAVMESH) + navmeshob = converter->FindGameObject(stAct->navmesh); + } + KX_GameObject *targetob = converter->FindGameObject(stAct->target); + + int mode = KX_SteeringActuator::KX_STEERING_NODEF; + switch(stAct->type) + { + case ACT_STEERING_SEEK: + mode = KX_SteeringActuator::KX_STEERING_SEEK; + break; + case ACT_STEERING_FLEE: + mode = KX_SteeringActuator::KX_STEERING_FLEE; + break; + case ACT_STEERING_PATHFOLLOWING: + mode = KX_SteeringActuator::KX_STEERING_PATHFOLLOWING; + break; + } + + bool selfTerminated = (stAct->flag & ACT_STEERING_SELFTERMINATED) !=0; + bool enableVisualization = (stAct->flag & ACT_STEERING_ENABLEVISUALIZATION) !=0; + short facingMode = (stAct->flag & ACT_STEERING_AUTOMATICFACING) ? stAct->facingaxis : 0; + bool normalup = (stAct->flag & ACT_STEERING_NORMALUP) !=0; + KX_SteeringActuator *tmpstact + = new KX_SteeringActuator(gameobj, mode, targetob, navmeshob,stAct->dist, + stAct->velocity, stAct->acceleration, stAct->turnspeed, + selfTerminated, stAct->updateTime, + scene->GetObstacleSimulation(), facingMode, normalup, enableVisualization); + baseact = tmpstact; + break; + } default: ; /* generate some error */ } diff --git a/source/gameengine/Converter/SConscript b/source/gameengine/Converter/SConscript index 9cfc3410748..edcd40e23ff 100644 --- a/source/gameengine/Converter/SConscript +++ b/source/gameengine/Converter/SConscript @@ -20,6 +20,7 @@ incs += ' #source/blender/misc #source/blender/blenloader #source/blender/gpu' incs += ' #source/blender/windowmanager' incs += ' #source/blender/makesrna' incs += ' #source/blender/ikplugin' +incs += ' #extern/recastnavigation/Detour/Include' incs += ' ' + env['BF_BULLET_INC'] diff --git a/source/gameengine/GameLogic/SCA_IActuator.h b/source/gameengine/GameLogic/SCA_IActuator.h index bfcec983e2a..d2a8de32895 100644 --- a/source/gameengine/GameLogic/SCA_IActuator.h +++ b/source/gameengine/GameLogic/SCA_IActuator.h @@ -90,6 +90,7 @@ public: KX_ACT_SHAPEACTION, KX_ACT_STATE, KX_ACT_ARMATURE, + KX_ACT_STEERING, }; SCA_IActuator(SCA_IObject* gameobj, KX_ACTUATOR_TYPE type); diff --git a/source/gameengine/Ketsji/CMakeLists.txt b/source/gameengine/Ketsji/CMakeLists.txt index a6339439bea..b32fd9e7a44 100644 --- a/source/gameengine/Ketsji/CMakeLists.txt +++ b/source/gameengine/Ketsji/CMakeLists.txt @@ -57,6 +57,9 @@ set(INC set(INC_SYS ${GLEW_INCLUDE_PATH} + ../../../extern/recastnavigation/Recast/Include + ../../../extern/recastnavigation/Detour/Include + ../../../source/blender/editors/include ) set(SRC @@ -88,9 +91,11 @@ set(SRC KX_MeshProxy.cpp KX_MotionState.cpp KX_MouseFocusSensor.cpp + KX_NavMeshObject.cpp KX_NearSensor.cpp KX_ObColorIpoSGController.cpp KX_ObjectActuator.cpp + KX_ObstacleSimulation.cpp KX_OrientationInterpolator.cpp KX_ParentActuator.cpp KX_PhysicsObjectWrapper.cpp @@ -118,6 +123,7 @@ set(SRC KX_SceneActuator.cpp KX_SoundActuator.cpp KX_StateActuator.cpp + KX_SteeringActuator.cpp KX_TimeCategoryLogger.cpp KX_TimeLogger.cpp KX_TouchEventManager.cpp @@ -159,9 +165,11 @@ set(SRC KX_MeshProxy.h KX_MotionState.h KX_MouseFocusSensor.h + KX_NavMeshObject.h KX_NearSensor.h KX_ObColorIpoSGController.h KX_ObjectActuator.h + KX_ObstacleSimulation.h KX_OrientationInterpolator.h KX_ParentActuator.h KX_PhysicsEngineEnums.h @@ -191,6 +199,7 @@ set(SRC KX_SceneActuator.h KX_SoundActuator.h KX_StateActuator.h + KX_SteeringActuator.h KX_TimeCategoryLogger.h KX_TimeLogger.h KX_TouchEventManager.h diff --git a/source/gameengine/Ketsji/KX_GameObject.cpp b/source/gameengine/Ketsji/KX_GameObject.cpp index 47d83c16659..d4ef462fb27 100644 --- a/source/gameengine/Ketsji/KX_GameObject.cpp +++ b/source/gameengine/Ketsji/KX_GameObject.cpp @@ -73,6 +73,7 @@ typedef unsigned long uint_ptr; #include "SCA_ISensor.h" #include "SCA_IController.h" #include "NG_NetworkScene.h" //Needed for sendMessage() +#include "KX_ObstacleSimulation.h" #include "PyObjectPlus.h" /* python stuff */ @@ -107,7 +108,8 @@ KX_GameObject::KX_GameObject( m_pGraphicController(NULL), m_xray(false), m_pHitObject(NULL), - m_isDeformable(false) + m_isDeformable(false), + m_pObstacleSimulation(NULL) #ifdef WITH_PYTHON , m_attr_dict(NULL) #endif @@ -154,6 +156,12 @@ KX_GameObject::~KX_GameObject() { delete m_pGraphicController; } + + if (m_pObstacleSimulation) + { + m_pObstacleSimulation->DestroyObstacleForObj(this); + } + #ifdef WITH_PYTHON if (m_attr_dict) { PyDict_Clear(m_attr_dict); /* incase of circular refs or other weird cases */ @@ -355,6 +363,14 @@ void KX_GameObject::ProcessReplica() m_pClient_info->m_gameobject = this; m_state = 0; + KX_Scene* scene = KX_GetActiveScene(); + KX_ObstacleSimulation* obssimulation = scene->GetObstacleSimulation(); + struct Object* blenderobject = GetBlenderObject(); + if (obssimulation && (blenderobject->gameflag & OB_HASOBSTACLE)) + { + obssimulation->AddObstacleForObj(this); + } + #ifdef WITH_PYTHON if(m_attr_dict) m_attr_dict= PyDict_Copy(m_attr_dict); diff --git a/source/gameengine/Ketsji/KX_GameObject.h b/source/gameengine/Ketsji/KX_GameObject.h index 50fbebe1341..2ea6e9552a2 100644 --- a/source/gameengine/Ketsji/KX_GameObject.h +++ b/source/gameengine/Ketsji/KX_GameObject.h @@ -64,6 +64,7 @@ class KX_IPhysicsController; class PHY_IGraphicController; class PHY_IPhysicsEnvironment; struct Object; +class KX_ObstacleSimulation; #ifdef WITH_PYTHON /* utility conversion function */ @@ -112,7 +113,9 @@ protected: SG_Node* m_pSGNode; MT_CmMatrix4x4 m_OpenGL_4x4Matrix; - + + KX_ObstacleSimulation* m_pObstacleSimulation; + public: bool m_isDeformable; @@ -795,6 +798,16 @@ public: } m_bSuspendDynamics = false; } + + void RegisterObstacle(KX_ObstacleSimulation* obstacleSimulation) + { + m_pObstacleSimulation = obstacleSimulation; + } + + void UnregisterObstacle() + { + m_pObstacleSimulation = NULL; + } KX_ClientObjectInfo* getClientInfo() { return m_pClient_info; } diff --git a/source/gameengine/Ketsji/KX_KetsjiEngine.cpp b/source/gameengine/Ketsji/KX_KetsjiEngine.cpp index 1b35219a36d..eef543e629c 100644 --- a/source/gameengine/Ketsji/KX_KetsjiEngine.cpp +++ b/source/gameengine/Ketsji/KX_KetsjiEngine.cpp @@ -81,6 +81,8 @@ #include "DNA_world_types.h" #include "DNA_scene_types.h" +#include "KX_NavMeshObject.h" + // If define: little test for Nzc: guarded drawing. If the canvas is // not valid, skip rendering this frame. //#define NZC_GUARDED_OUTPUT @@ -1337,7 +1339,7 @@ void KX_KetsjiEngine::PostRenderScene(KX_Scene* scene) #ifdef WITH_PYTHON scene->RunDrawingCallbacks(scene->GetPostDrawCB()); #endif - m_rasterizer->FlushDebugLines(); + m_rasterizer->FlushDebugShapes(); } void KX_KetsjiEngine::StopEngine() diff --git a/source/gameengine/Ketsji/KX_NavMeshObject.cpp b/source/gameengine/Ketsji/KX_NavMeshObject.cpp new file mode 100644 index 00000000000..499cbae85e9 --- /dev/null +++ b/source/gameengine/Ketsji/KX_NavMeshObject.cpp @@ -0,0 +1,708 @@ +/** +* $Id$ +* ***** BEGIN GPL LICENSE BLOCK ***** +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License +* as published by the Free Software Foundation; either version 2 +* of the License, or (at your option) any later version. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software Foundation, +* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +* +* The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. +* All rights reserved. +* +* The Original Code is: all of this file. +* +* Contributor(s): none yet. +* +* ***** END GPL LICENSE BLOCK ***** +*/ + +#include "BLI_math_vector.h" +#include "KX_NavMeshObject.h" +#include "RAS_MeshObject.h" + +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" + +extern "C" { +#include "BKE_scene.h" +#include "BKE_customdata.h" +#include "BKE_cdderivedmesh.h" +#include "BKE_DerivedMesh.h" + + +#include "ED_navmesh_conversion.h" +} + +#include "KX_PythonInit.h" +#include "KX_PyMath.h" +#include "Value.h" +#include "Recast.h" +#include "DetourStatNavMeshBuilder.h" +#include "KX_ObstacleSimulation.h" + +static const int MAX_PATH_LEN = 256; +static const float polyPickExt[3] = {2, 4, 2}; + +static void calcMeshBounds(const float* vert, int nverts, float* bmin, float* bmax) +{ + bmin[0] = bmax[0] = vert[0]; + bmin[1] = bmax[1] = vert[1]; + bmin[2] = bmax[2] = vert[2]; + for (int i=1; i<nverts; i++) + { + if (bmin[0]>vert[3*i+0]) bmin[0] = vert[3*i+0]; + if (bmin[1]>vert[3*i+1]) bmin[1] = vert[3*i+1]; + if (bmin[2]>vert[3*i+2]) bmin[2] = vert[3*i+2]; + + if (bmax[0]<vert[3*i+0]) bmax[0] = vert[3*i+0]; + if (bmax[1]<vert[3*i+1]) bmax[1] = vert[3*i+1]; + if (bmax[2]<vert[3*i+2]) bmax[2] = vert[3*i+2]; + } +} + +inline void flipAxes(float* vec) +{ + std::swap(vec[1],vec[2]); +} +KX_NavMeshObject::KX_NavMeshObject(void* sgReplicationInfo, SG_Callbacks callbacks) +: KX_GameObject(sgReplicationInfo, callbacks) +, m_navMesh(NULL) +{ + +} + +KX_NavMeshObject::~KX_NavMeshObject() +{ + if (m_navMesh) + delete m_navMesh; +} + +CValue* KX_NavMeshObject::GetReplica() +{ + KX_NavMeshObject* replica = new KX_NavMeshObject(*this); + replica->ProcessReplica(); + return replica; +} + +void KX_NavMeshObject::ProcessReplica() +{ + KX_GameObject::ProcessReplica(); + + BuildNavMesh(); + KX_Scene* scene = KX_GetActiveScene(); + KX_ObstacleSimulation* obssimulation = scene->GetObstacleSimulation(); + if (obssimulation) + obssimulation->AddObstaclesForNavMesh(this); + +} + +bool KX_NavMeshObject::BuildVertIndArrays(float *&vertices, int& nverts, + unsigned short* &polys, int& npolys, unsigned short *&dmeshes, + float *&dvertices, int &ndvertsuniq, unsigned short *&dtris, + int& ndtris, int &vertsPerPoly) +{ + DerivedMesh* dm = mesh_create_derived_no_virtual(KX_GetActiveScene()->GetBlenderScene(), GetBlenderObject(), + NULL, CD_MASK_MESH); + int* recastData = (int*) dm->getFaceDataArray(dm, CD_RECAST); + if (recastData) + { + int *dtrisToPolysMap=NULL, *dtrisToTrisMap=NULL, *trisToFacesMap=NULL; + int nAllVerts = 0; + float *allVerts = NULL; + buildNavMeshDataByDerivedMesh(dm, vertsPerPoly, nAllVerts, allVerts, ndtris, dtris, + npolys, dmeshes, polys, dtrisToPolysMap, dtrisToTrisMap, trisToFacesMap); + + unsigned short *verticesMap = new unsigned short[nAllVerts]; + memset(verticesMap, 0xffff, sizeof(unsigned short)*nAllVerts); + int curIdx = 0; + //vertices - mesh verts + //iterate over all polys and create map for their vertices first... + for (int polyidx=0; polyidx<npolys; polyidx++) + { + unsigned short* poly = &polys[polyidx*vertsPerPoly*2]; + for (int i=0; i<vertsPerPoly; i++) + { + unsigned short idx = poly[i]; + if (idx==0xffff) + break; + if (verticesMap[idx]==0xffff) + { + verticesMap[idx] = curIdx++; + } + poly[i] = verticesMap[idx]; + } + } + nverts = curIdx; + //...then iterate over detailed meshes + //transform indices to local ones (for each navigation polygon) + for (int polyidx=0; polyidx<npolys; polyidx++) + { + unsigned short *poly = &polys[polyidx*vertsPerPoly*2]; + int nv = polyNumVerts(poly, vertsPerPoly); + unsigned short *dmesh = &dmeshes[4*polyidx]; + unsigned short tribase = dmesh[2]; + unsigned short trinum = dmesh[3]; + unsigned short vbase = curIdx; + for (int j=0; j<trinum; j++) + { + unsigned short* dtri = &dtris[(tribase+j)*3*2]; + for (int k=0; k<3; k++) + { + int newVertexIdx = verticesMap[dtri[k]]; + if (newVertexIdx==0xffff) + { + newVertexIdx = curIdx++; + verticesMap[dtri[k]] = newVertexIdx; + } + + if (newVertexIdx<nverts) + { + //it's polygon vertex ("shared") + int idxInPoly = polyFindVertex(poly, vertsPerPoly, newVertexIdx); + if (idxInPoly==-1) + { + printf("Building NavMeshObject: Error! Can't find vertex in polygon\n"); + return false; + } + dtri[k] = idxInPoly; + } + else + { + dtri[k] = newVertexIdx - vbase + nv; + } + } + } + dmesh[0] = vbase-nverts; //verts base + dmesh[1] = curIdx-vbase; //verts num + } + + vertices = new float[nverts*3]; + ndvertsuniq = curIdx - nverts; + if (ndvertsuniq>0) + { + dvertices = new float[ndvertsuniq*3]; + } + for (int vi=0; vi<nAllVerts; vi++) + { + int newIdx = verticesMap[vi]; + if (newIdx!=0xffff) + { + if (newIdx<nverts) + { + //navigation mesh vertex + memcpy(vertices+3*newIdx, allVerts+3*vi, 3*sizeof(float)); + } + else + { + //detailed mesh vertex + memcpy(dvertices+3*(newIdx-nverts), allVerts+3*vi, 3*sizeof(float)); + } + } + } + } + else + { + //create from RAS_MeshObject (detailed mesh is fake) + RAS_MeshObject* meshobj = GetMesh(0); + vertsPerPoly = 3; + nverts = meshobj->m_sharedvertex_map.size(); + if (nverts >= 0xffff) + return false; + //calculate count of tris + int nmeshpolys = meshobj->NumPolygons(); + npolys = nmeshpolys; + for (int p=0; p<nmeshpolys; p++) + { + int vertcount = meshobj->GetPolygon(p)->VertexCount(); + npolys+=vertcount-3; + } + + //create verts + vertices = new float[nverts*3]; + float* vert = vertices; + for (int vi=0; vi<nverts; vi++) + { + const float* pos = !meshobj->m_sharedvertex_map[vi].empty() ? meshobj->GetVertexLocation(vi) : NULL; + if (pos) + copy_v3_v3(vert, pos); + else + { + memset(vert, NULL, 3*sizeof(float)); //vertex isn't in any poly, set dummy zero coordinates + } + vert+=3; + } + + //create tris + polys = new unsigned short[npolys*3*2]; + memset(polys, 0xff, sizeof(unsigned short)*3*2*npolys); + unsigned short *poly = polys; + RAS_Polygon* raspoly; + for (int p=0; p<nmeshpolys; p++) + { + raspoly = meshobj->GetPolygon(p); + for (int v=0; v<raspoly->VertexCount()-2; v++) + { + poly[0]= raspoly->GetVertex(0)->getOrigIndex(); + for (size_t i=1; i<3; i++) + { + poly[i]= raspoly->GetVertex(v+i)->getOrigIndex(); + } + poly += 6; + } + } + dmeshes = NULL; + dvertices = NULL; + ndvertsuniq = 0; + dtris = NULL; + ndtris = npolys; + } + dm->release(dm); + + return true; +} + + +bool KX_NavMeshObject::BuildNavMesh() +{ + if (m_navMesh) + { + delete m_navMesh; + m_navMesh = NULL; + } + + if (GetMeshCount()==0) + { + printf("Can't find mesh for navmesh object: %s \n", m_name); + return false; + } + + float *vertices = NULL, *dvertices = NULL; + unsigned short *polys = NULL, *dtris = NULL, *dmeshes = NULL; + int nverts = 0, npolys = 0, ndvertsuniq = 0, ndtris = 0; + int vertsPerPoly = 0; + if (!BuildVertIndArrays(vertices, nverts, polys, npolys, + dmeshes, dvertices, ndvertsuniq, dtris, ndtris, vertsPerPoly ) + || vertsPerPoly<3) + { + printf("Can't build navigation mesh data for object:%s \n", m_name); + return false; + } + + MT_Point3 pos; + if (dmeshes==NULL) + { + for (int i=0; i<nverts; i++) + { + flipAxes(&vertices[i*3]); + } + for (int i=0; i<ndvertsuniq; i++) + { + flipAxes(&dvertices[i*3]); + } + } + + buildMeshAdjacency(polys, npolys, nverts, vertsPerPoly); + + float cs = 0.2f; + + if (!nverts || !npolys) + return false; + + float bmin[3], bmax[3]; + calcMeshBounds(vertices, nverts, bmin, bmax); + //quantize vertex pos + unsigned short* vertsi = new unsigned short[3*nverts]; + float ics = 1.f/cs; + for (int i=0; i<nverts; i++) + { + vertsi[3*i+0] = static_cast<unsigned short>((vertices[3*i+0]-bmin[0])*ics); + vertsi[3*i+1] = static_cast<unsigned short>((vertices[3*i+1]-bmin[1])*ics); + vertsi[3*i+2] = static_cast<unsigned short>((vertices[3*i+2]-bmin[2])*ics); + } + + // Calculate data size + const int headerSize = sizeof(dtStatNavMeshHeader); + const int vertsSize = sizeof(float)*3*nverts; + const int polysSize = sizeof(dtStatPoly)*npolys; + const int nodesSize = sizeof(dtStatBVNode)*npolys*2; + const int detailMeshesSize = sizeof(dtStatPolyDetail)*npolys; + const int detailVertsSize = sizeof(float)*3*ndvertsuniq; + const int detailTrisSize = sizeof(unsigned char)*4*ndtris; + + const int dataSize = headerSize + vertsSize + polysSize + nodesSize + + detailMeshesSize + detailVertsSize + detailTrisSize; + unsigned char* data = new unsigned char[dataSize]; + if (!data) + return false; + memset(data, 0, dataSize); + + unsigned char* d = data; + dtStatNavMeshHeader* header = (dtStatNavMeshHeader*)d; d += headerSize; + float* navVerts = (float*)d; d += vertsSize; + dtStatPoly* navPolys = (dtStatPoly*)d; d += polysSize; + dtStatBVNode* navNodes = (dtStatBVNode*)d; d += nodesSize; + dtStatPolyDetail* navDMeshes = (dtStatPolyDetail*)d; d += detailMeshesSize; + float* navDVerts = (float*)d; d += detailVertsSize; + unsigned char* navDTris = (unsigned char*)d; d += detailTrisSize; + + // Store header + header->magic = DT_STAT_NAVMESH_MAGIC; + header->version = DT_STAT_NAVMESH_VERSION; + header->npolys = npolys; + header->nverts = nverts; + header->cs = cs; + header->bmin[0] = bmin[0]; + header->bmin[1] = bmin[1]; + header->bmin[2] = bmin[2]; + header->bmax[0] = bmax[0]; + header->bmax[1] = bmax[1]; + header->bmax[2] = bmax[2]; + header->ndmeshes = npolys; + header->ndverts = ndvertsuniq; + header->ndtris = ndtris; + + // Store vertices + for (int i = 0; i < nverts; ++i) + { + const unsigned short* iv = &vertsi[i*3]; + float* v = &navVerts[i*3]; + v[0] = bmin[0] + iv[0] * cs; + v[1] = bmin[1] + iv[1] * cs; + v[2] = bmin[2] + iv[2] * cs; + } + //memcpy(navVerts, vertices, nverts*3*sizeof(float)); + + // Store polygons + const unsigned short* src = polys; + for (int i = 0; i < npolys; ++i) + { + dtStatPoly* p = &navPolys[i]; + p->nv = 0; + for (int j = 0; j < vertsPerPoly; ++j) + { + if (src[j] == 0xffff) break; + p->v[j] = src[j]; + p->n[j] = src[vertsPerPoly+j]+1; + p->nv++; + } + src += vertsPerPoly*2; + } + + header->nnodes = createBVTree(vertsi, nverts, polys, npolys, vertsPerPoly, + cs, cs, npolys*2, navNodes); + + + if (dmeshes==NULL) + { + //create fake detail meshes + for (int i = 0; i < npolys; ++i) + { + dtStatPolyDetail& dtl = navDMeshes[i]; + dtl.vbase = 0; + dtl.nverts = 0; + dtl.tbase = i; + dtl.ntris = 1; + } + // setup triangles. + unsigned char* tri = navDTris; + for(size_t i=0; i<ndtris; i++) + { + for (size_t j=0; j<3; j++) + tri[4*i+j] = j; + } + } + else + { + //verts + memcpy(navDVerts, dvertices, ndvertsuniq*3*sizeof(float)); + //tris + unsigned char* tri = navDTris; + for(size_t i=0; i<ndtris; i++) + { + for (size_t j=0; j<3; j++) + tri[4*i+j] = dtris[6*i+j]; + } + //detailed meshes + for (int i = 0; i < npolys; ++i) + { + dtStatPolyDetail& dtl = navDMeshes[i]; + dtl.vbase = dmeshes[i*4+0]; + dtl.nverts = dmeshes[i*4+1]; + dtl.tbase = dmeshes[i*4+2]; + dtl.ntris = dmeshes[i*4+3]; + } + } + + m_navMesh = new dtStatNavMesh; + m_navMesh->init(data, dataSize, true); + + delete [] vertices; + delete [] polys; + if (dvertices) + { + delete [] dvertices; + } + + return true; +} + +dtStatNavMesh* KX_NavMeshObject::GetNavMesh() +{ + return m_navMesh; +} + +void KX_NavMeshObject::DrawNavMesh(NavMeshRenderMode renderMode) +{ + if (!m_navMesh) + return; + MT_Vector3 color(0.f, 0.f, 0.f); + + switch (renderMode) + { + case RM_POLYS : + case RM_WALLS : + for (int pi=0; pi<m_navMesh->getPolyCount(); pi++) + { + const dtStatPoly* poly = m_navMesh->getPoly(pi); + + for (int i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j = i++) + { + if (poly->n[j] && renderMode==RM_WALLS) + continue; + const float* vif = m_navMesh->getVertex(poly->v[i]); + const float* vjf = m_navMesh->getVertex(poly->v[j]); + MT_Point3 vi(vif[0], vif[2], vif[1]); + MT_Point3 vj(vjf[0], vjf[2], vjf[1]); + vi = TransformToWorldCoords(vi); + vj = TransformToWorldCoords(vj); + KX_RasterizerDrawDebugLine(vi, vj, color); + } + } + break; + case RM_TRIS : + for (int i = 0; i < m_navMesh->getPolyDetailCount(); ++i) + { + const dtStatPoly* p = m_navMesh->getPoly(i); + const dtStatPolyDetail* pd = m_navMesh->getPolyDetail(i); + + for (int j = 0; j < pd->ntris; ++j) + { + const unsigned char* t = m_navMesh->getDetailTri(pd->tbase+j); + MT_Point3 tri[3]; + for (int k = 0; k < 3; ++k) + { + const float* v; + if (t[k] < p->nv) + v = m_navMesh->getVertex(p->v[t[k]]); + else + v = m_navMesh->getDetailVertex(pd->vbase+(t[k]-p->nv)); + float pos[3]; + vcopy(pos, v); + flipAxes(pos); + tri[k].setValue(pos); + } + + for (int k=0; k<3; k++) + tri[k] = TransformToWorldCoords(tri[k]); + + for (int k=0; k<3; k++) + KX_RasterizerDrawDebugLine(tri[k], tri[(k+1)%3], color); + } + } + break; + } +} + +MT_Point3 KX_NavMeshObject::TransformToLocalCoords(const MT_Point3& wpos) +{ + MT_Matrix3x3 orientation = NodeGetWorldOrientation(); + const MT_Vector3& scaling = NodeGetWorldScaling(); + orientation.scale(scaling[0], scaling[1], scaling[2]); + MT_Transform worldtr(NodeGetWorldPosition(), orientation); + MT_Transform invworldtr; + invworldtr.invert(worldtr); + MT_Point3 lpos = invworldtr(wpos); + return lpos; +} + +MT_Point3 KX_NavMeshObject::TransformToWorldCoords(const MT_Point3& lpos) +{ + MT_Matrix3x3 orientation = NodeGetWorldOrientation(); + const MT_Vector3& scaling = NodeGetWorldScaling(); + orientation.scale(scaling[0], scaling[1], scaling[2]); + MT_Transform worldtr(NodeGetWorldPosition(), orientation); + MT_Point3 wpos = worldtr(lpos); + return wpos; +} + +int KX_NavMeshObject::FindPath(const MT_Point3& from, const MT_Point3& to, float* path, int maxPathLen) +{ + if (!m_navMesh) + return 0; + MT_Point3 localfrom = TransformToLocalCoords(from); + MT_Point3 localto = TransformToLocalCoords(to); + float spos[3], epos[3]; + localfrom.getValue(spos); flipAxes(spos); + localto.getValue(epos); flipAxes(epos); + dtStatPolyRef sPolyRef = m_navMesh->findNearestPoly(spos, polyPickExt); + dtStatPolyRef ePolyRef = m_navMesh->findNearestPoly(epos, polyPickExt); + + int pathLen = 0; + if (sPolyRef && ePolyRef) + { + dtStatPolyRef* polys = new dtStatPolyRef[maxPathLen]; + int npolys; + npolys = m_navMesh->findPath(sPolyRef, ePolyRef, spos, epos, polys, maxPathLen); + if (npolys) + { + pathLen = m_navMesh->findStraightPath(spos, epos, polys, npolys, path, maxPathLen); + for (int i=0; i<pathLen; i++) + { + flipAxes(&path[i*3]); + MT_Point3 waypoint(&path[i*3]); + waypoint = TransformToWorldCoords(waypoint); + waypoint.getValue(&path[i*3]); + } + } + } + + return pathLen; +} + +float KX_NavMeshObject::Raycast(const MT_Point3& from, const MT_Point3& to) +{ + if (!m_navMesh) + return 0.f; + MT_Point3 localfrom = TransformToLocalCoords(from); + MT_Point3 localto = TransformToLocalCoords(to); + float spos[3], epos[3]; + localfrom.getValue(spos); flipAxes(spos); + localto.getValue(epos); flipAxes(epos); + dtStatPolyRef sPolyRef = m_navMesh->findNearestPoly(spos, polyPickExt); + float t=0; + static dtStatPolyRef polys[MAX_PATH_LEN]; + m_navMesh->raycast(sPolyRef, spos, epos, t, polys, MAX_PATH_LEN); + return t; +} + +void KX_NavMeshObject::DrawPath(const float *path, int pathLen, const MT_Vector3& color) +{ + MT_Vector3 a,b; + for (int i=0; i<pathLen-1; i++) + { + a.setValue(&path[3*i]); + b.setValue(&path[3*(i+1)]); + KX_RasterizerDrawDebugLine(a, b, color); + } +} + + +#ifndef DISABLE_PYTHON +//---------------------------------------------------------------------------- +//Python + +PyTypeObject KX_NavMeshObject::Type = { + PyVarObject_HEAD_INIT(NULL, 0) + "KX_NavMeshObject", + sizeof(PyObjectPlus_Proxy), + 0, + py_base_dealloc, + 0, + 0, + 0, + 0, + py_base_repr, + 0, + 0, + 0, + 0,0,0,0,0,0, + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, + 0,0,0,0,0,0,0, + Methods, + 0, + 0, + &KX_GameObject::Type, + 0,0,0,0,0,0, + py_base_new +}; + +PyAttributeDef KX_NavMeshObject::Attributes[] = { + { NULL } //Sentinel +}; + +//KX_PYMETHODTABLE_NOARGS(KX_GameObject, getD), +PyMethodDef KX_NavMeshObject::Methods[] = { + KX_PYMETHODTABLE(KX_NavMeshObject, findPath), + KX_PYMETHODTABLE(KX_NavMeshObject, raycast), + KX_PYMETHODTABLE(KX_NavMeshObject, draw), + KX_PYMETHODTABLE(KX_NavMeshObject, rebuild), + {NULL,NULL} //Sentinel +}; + +KX_PYMETHODDEF_DOC(KX_NavMeshObject, findPath, + "findPath(start, goal): find path from start to goal points\n" + "Returns a path as list of points)\n") +{ + PyObject *ob_from, *ob_to; + if (!PyArg_ParseTuple(args,"OO:getPath",&ob_from,&ob_to)) + return NULL; + MT_Point3 from, to; + if (!PyVecTo(ob_from, from) || !PyVecTo(ob_to, to)) + return NULL; + + float path[MAX_PATH_LEN*3]; + int pathLen = FindPath(from, to, path, MAX_PATH_LEN); + PyObject *pathList = PyList_New( pathLen ); + for (int i=0; i<pathLen; i++) + { + MT_Point3 point(&path[3*i]); + PyList_SET_ITEM(pathList, i, PyObjectFrom(point)); + } + + return pathList; +} + +KX_PYMETHODDEF_DOC(KX_NavMeshObject, raycast, + "raycast(start, goal): raycast from start to goal points\n" + "Returns hit factor)\n") +{ + PyObject *ob_from, *ob_to; + if (!PyArg_ParseTuple(args,"OO:getPath",&ob_from,&ob_to)) + return NULL; + MT_Point3 from, to; + if (!PyVecTo(ob_from, from) || !PyVecTo(ob_to, to)) + return NULL; + float hit = Raycast(from, to); + return PyFloat_FromDouble(hit); +} + +KX_PYMETHODDEF_DOC(KX_NavMeshObject, draw, + "draw(mode): navigation mesh debug drawing\n" + "mode: WALLS, POLYS, TRIS\n") +{ + int arg; + NavMeshRenderMode renderMode = RM_TRIS; + if (PyArg_ParseTuple(args,"i:rebuild",&arg) && arg>=0 && arg<RM_MAX) + renderMode = (NavMeshRenderMode)arg; + DrawNavMesh(renderMode); + Py_RETURN_NONE; +} + +KX_PYMETHODDEF_DOC_NOARGS(KX_NavMeshObject, rebuild, + "rebuild(): rebuild navigation mesh\n") +{ + BuildNavMesh(); + Py_RETURN_NONE; +} + +#endif // DISABLE_PYTHON
\ No newline at end of file diff --git a/source/gameengine/Ketsji/KX_NavMeshObject.h b/source/gameengine/Ketsji/KX_NavMeshObject.h new file mode 100644 index 00000000000..78e9488ad1c --- /dev/null +++ b/source/gameengine/Ketsji/KX_NavMeshObject.h @@ -0,0 +1,83 @@ +/** +* $Id$ +* +* ***** BEGIN GPL LICENSE BLOCK ***** +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License +* as published by the Free Software Foundation; either version 2 +* of the License, or (at your option) any later version. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software Foundation, +* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +* +* The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. +* All rights reserved. +* +* The Original Code is: all of this file. +* +* Contributor(s): none yet. +* +* ***** END GPL LICENSE BLOCK ***** +*/ +#ifndef __KX_NAVMESHOBJECT +#define __KX_NAVMESHOBJECT +#include "DetourStatNavMesh.h" +#include "KX_GameObject.h" +#include "PyObjectPlus.h" +#include <vector> + +class RAS_MeshObject; +class MT_Transform; + +class KX_NavMeshObject: public KX_GameObject +{ + Py_Header; + +protected: + dtStatNavMesh* m_navMesh; + + bool BuildVertIndArrays(float *&vertices, int& nverts, + unsigned short* &polys, int& npolys, unsigned short *&dmeshes, + float *&dvertices, int &ndvertsuniq, unsigned short* &dtris, + int& ndtris, int &vertsPerPoly); + +public: + KX_NavMeshObject(void* sgReplicationInfo, SG_Callbacks callbacks); + ~KX_NavMeshObject(); + + virtual CValue* GetReplica(); + virtual void ProcessReplica(); + + + bool BuildNavMesh(); + dtStatNavMesh* GetNavMesh(); + int FindPath(const MT_Point3& from, const MT_Point3& to, float* path, int maxPathLen); + float Raycast(const MT_Point3& from, const MT_Point3& to); + + enum NavMeshRenderMode {RM_WALLS, RM_POLYS, RM_TRIS, RM_MAX}; + void DrawNavMesh(NavMeshRenderMode mode); + void DrawPath(const float *path, int pathLen, const MT_Vector3& color); + + MT_Point3 TransformToLocalCoords(const MT_Point3& wpos); + MT_Point3 TransformToWorldCoords(const MT_Point3& lpos); +#ifndef DISABLE_PYTHON + /* --------------------------------------------------------------------- */ + /* Python interface ---------------------------------------------------- */ + /* --------------------------------------------------------------------- */ + + KX_PYMETHOD_DOC(KX_NavMeshObject, findPath); + KX_PYMETHOD_DOC(KX_NavMeshObject, raycast); + KX_PYMETHOD_DOC(KX_NavMeshObject, draw); + KX_PYMETHOD_DOC_NOARGS(KX_NavMeshObject, rebuild); +#endif +}; + +#endif //__KX_NAVMESHOBJECT + diff --git a/source/gameengine/Ketsji/KX_ObstacleSimulation.cpp b/source/gameengine/Ketsji/KX_ObstacleSimulation.cpp new file mode 100644 index 00000000000..9bca98d7fde --- /dev/null +++ b/source/gameengine/Ketsji/KX_ObstacleSimulation.cpp @@ -0,0 +1,869 @@ +/** +* Simulation for obstacle avoidance behavior +* +* $Id$ +* +* ***** BEGIN GPL LICENSE BLOCK ***** +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License +* as published by the Free Software Foundation; either version 2 +* of the License, or (at your option) any later version. The Blender +* Foundation also sells licenses for use in proprietary software under +* the Blender License. See http://www.blender.org/BL/ for information +* about this. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software Foundation, +* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +* +* The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. +* All rights reserved. +* +* The Original Code is: all of this file. +* +* Contributor(s): none yet. +* +* ***** END GPL LICENSE BLOCK ***** +*/ + +#include "KX_ObstacleSimulation.h" +#include "KX_NavMeshObject.h" +#include "KX_PythonInit.h" +#include "DNA_object_types.h" +#include "BLI_math.h" + +namespace +{ + inline float perp(const MT_Vector2& a, const MT_Vector2& b) { return a.x()*b.y() - a.y()*b.x(); } + + inline float sqr(float x) { return x*x; } + inline float lerp(float a, float b, float t) { return a + (b-a)*t; } + inline float clamp(float a, float mn, float mx) { return a < mn ? mn : (a > mx ? mx : a); } + + inline float vdistsqr(const float* a, const float* b) { return sqr(b[0]-a[0]) + sqr(b[1]-a[1]); } + inline float vdist(const float* a, const float* b) { return sqrtf(vdistsqr(a,b)); } + inline void vcpy(float* a, const float* b) { a[0]=b[0]; a[1]=b[1]; } + inline float vdot(const float* a, const float* b) { return a[0]*b[0] + a[1]*b[1]; } + inline float vperp(const float* a, const float* b) { return a[0]*b[1] - a[1]*b[0]; } + inline void vsub(float* v, const float* a, const float* b) { v[0] = a[0]-b[0]; v[1] = a[1]-b[1]; } + inline void vadd(float* v, const float* a, const float* b) { v[0] = a[0]+b[0]; v[1] = a[1]+b[1]; } + inline void vscale(float* v, const float* a, const float s) { v[0] = a[0]*s; v[1] = a[1]*s; } + inline void vset(float* v, float x, float y) { v[0]=x; v[1]=y; } + inline float vlensqr(const float* v) { return vdot(v,v); } + inline float vlen(const float* v) { return sqrtf(vlensqr(v)); } + inline void vlerp(float* v, const float* a, const float* b, float t) { v[0] = lerp(a[0], b[0], t); v[1] = lerp(a[1], b[1], t); } + inline void vmad(float* v, const float* a, const float* b, float s) { v[0] = a[0] + b[0]*s; v[1] = a[1] + b[1]*s; } + inline void vnorm(float* v) + { + float d = vlen(v); + if (d > 0.0001f) + { + d = 1.0f/d; + v[0] *= d; + v[1] *= d; + } + } +} +inline float triarea(const float* a, const float* b, const float* c) +{ + return (b[0]*a[1] - a[0]*b[1]) + (c[0]*b[1] - b[0]*c[1]) + (a[0]*c[1] - c[0]*a[1]); +} + +static void closestPtPtSeg(const float* pt, + const float* sp, const float* sq, + float& t) +{ + float dir[2],diff[3]; + vsub(dir,sq,sp); + vsub(diff,pt,sp); + t = vdot(diff,dir); + if (t <= 0.0f) { t = 0; return; } + float d = vdot(dir,dir); + if (t >= d) { t = 1; return; } + t /= d; +} + +static float distPtSegSqr(const float* pt, const float* sp, const float* sq) +{ + float t; + closestPtPtSeg(pt, sp,sq, t); + float np[2]; + vlerp(np, sp,sq, t); + return vdistsqr(pt,np); +} + +static int sweepCircleCircle(const MT_Vector3& pos0, const MT_Scalar r0, const MT_Vector2& v, + const MT_Vector3& pos1, const MT_Scalar r1, + float& tmin, float& tmax) +{ + static const float EPS = 0.0001f; + MT_Vector2 c0(pos0.x(), pos0.y()); + MT_Vector2 c1(pos1.x(), pos1.y()); + MT_Vector2 s = c1 - c0; + MT_Scalar r = r0+r1; + float c = s.length2() - r*r; + float a = v.length2(); + if (a < EPS) return 0; // not moving + + // Overlap, calc time to exit. + float b = MT_dot(v,s); + float d = b*b - a*c; + if (d < 0.0f) return 0; // no intersection. + tmin = (b - sqrtf(d)) / a; + tmax = (b + sqrtf(d)) / a; + return 1; +} + +static int sweepCircleSegment(const MT_Vector3& pos0, const MT_Scalar r0, const MT_Vector2& v, + const MT_Vector3& pa, const MT_Vector3& pb, const MT_Scalar sr, + float& tmin, float &tmax) +{ + // equation parameters + MT_Vector2 c0(pos0.x(), pos0.y()); + MT_Vector2 sa(pa.x(), pa.y()); + MT_Vector2 sb(pb.x(), pb.y()); + MT_Vector2 L = sb-sa; + MT_Vector2 H = c0-sa; + MT_Scalar radius = r0+sr; + float l2 = L.length2(); + float r2 = radius * radius; + float dl = perp(v, L); + float hl = perp(H, L); + float a = dl * dl; + float b = 2.0f * hl * dl; + float c = hl * hl - (r2 * l2); + float d = (b*b) - (4.0f * a * c); + + // infinite line missed by infinite ray. + if (d < 0.0f) + return 0; + + d = sqrtf(d); + tmin = (-b - d) / (2.0f * a); + tmax = (-b + d) / (2.0f * a); + + // line missed by ray range. + /* if (tmax < 0.0f || tmin > 1.0f) + return 0;*/ + + // find what part of the ray was collided. + MT_Vector2 Pedge; + Pedge = c0+v*tmin; + H = Pedge - sa; + float e0 = MT_dot(H, L) / l2; + Pedge = c0 + v*tmax; + H = Pedge - sa; + float e1 = MT_dot(H, L) / l2; + + if (e0 < 0.0f || e1 < 0.0f) + { + float ctmin, ctmax; + if (sweepCircleCircle(pos0, r0, v, pa, sr, ctmin, ctmax)) + { + if (e0 < 0.0f && ctmin > tmin) + tmin = ctmin; + if (e1 < 0.0f && ctmax < tmax) + tmax = ctmax; + } + else + { + return 0; + } + } + + if (e0 > 1.0f || e1 > 1.0f) + { + float ctmin, ctmax; + if (sweepCircleCircle(pos0, r0, v, pb, sr, ctmin, ctmax)) + { + if (e0 > 1.0f && ctmin > tmin) + tmin = ctmin; + if (e1 > 1.0f && ctmax < tmax) + tmax = ctmax; + } + else + { + return 0; + } + } + + return 1; +} + +static bool inBetweenAngle(float a, float amin, float amax, float& t) +{ + if (amax < amin) amax += (float)M_PI*2; + if (a < amin-(float)M_PI) a += (float)M_PI*2; + if (a > amin+(float)M_PI) a -= (float)M_PI*2; + if (a >= amin && a < amax) + { + t = (a-amin) / (amax-amin); + return true; + } + return false; +} + +static float interpolateToi(float a, const float* dir, const float* toi, const int ntoi) +{ + for (int i = 0; i < ntoi; ++i) + { + int next = (i+1) % ntoi; + float t; + if (inBetweenAngle(a, dir[i], dir[next], t)) + { + return lerp(toi[i], toi[next], t); + } + } + return 0; +} + +KX_ObstacleSimulation::KX_ObstacleSimulation(MT_Scalar levelHeight, bool enableVisualization) +: m_levelHeight(levelHeight) +, m_enableVisualization(enableVisualization) +{ + +} + +KX_ObstacleSimulation::~KX_ObstacleSimulation() +{ + for (size_t i=0; i<m_obstacles.size(); i++) + { + KX_Obstacle* obs = m_obstacles[i]; + delete obs; + } + m_obstacles.clear(); +} +KX_Obstacle* KX_ObstacleSimulation::CreateObstacle(KX_GameObject* gameobj) +{ + KX_Obstacle* obstacle = new KX_Obstacle(); + obstacle->m_gameObj = gameobj; + + vset(obstacle->vel, 0,0); + vset(obstacle->pvel, 0,0); + vset(obstacle->dvel, 0,0); + vset(obstacle->nvel, 0,0); + for (int i = 0; i < VEL_HIST_SIZE; ++i) + vset(&obstacle->hvel[i*2], 0,0); + obstacle->hhead = 0; + + gameobj->RegisterObstacle(this); + m_obstacles.push_back(obstacle); + return obstacle; +} + +void KX_ObstacleSimulation::AddObstacleForObj(KX_GameObject* gameobj) +{ + KX_Obstacle* obstacle = CreateObstacle(gameobj); + struct Object* blenderobject = gameobj->GetBlenderObject(); + obstacle->m_type = KX_OBSTACLE_OBJ; + obstacle->m_shape = KX_OBSTACLE_CIRCLE; + obstacle->m_rad = blenderobject->obstacleRad; +} + +void KX_ObstacleSimulation::AddObstaclesForNavMesh(KX_NavMeshObject* navmeshobj) +{ + dtStatNavMesh* navmesh = navmeshobj->GetNavMesh(); + if (navmesh) + { + int npoly = navmesh->getPolyCount(); + for (int pi=0; pi<npoly; pi++) + { + const dtStatPoly* poly = navmesh->getPoly(pi); + + for (int i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j = i++) + { + if (poly->n[j]) continue; + const float* vj = navmesh->getVertex(poly->v[j]); + const float* vi = navmesh->getVertex(poly->v[i]); + + KX_Obstacle* obstacle = CreateObstacle(navmeshobj); + obstacle->m_type = KX_OBSTACLE_NAV_MESH; + obstacle->m_shape = KX_OBSTACLE_SEGMENT; + obstacle->m_pos = MT_Point3(vj[0], vj[2], vj[1]); + obstacle->m_pos2 = MT_Point3(vi[0], vi[2], vi[1]); + obstacle->m_rad = 0; + } + } + } +} + +void KX_ObstacleSimulation::DestroyObstacleForObj(KX_GameObject* gameobj) +{ + for (size_t i=0; i<m_obstacles.size(); ) + { + if (m_obstacles[i]->m_gameObj == gameobj) + { + KX_Obstacle* obstacle = m_obstacles[i]; + obstacle->m_gameObj->UnregisterObstacle(); + m_obstacles[i] = m_obstacles.back(); + m_obstacles.pop_back(); + delete obstacle; + } + else + i++; + } +} + +void KX_ObstacleSimulation::UpdateObstacles() +{ + for (size_t i=0; i<m_obstacles.size(); i++) + { + if (m_obstacles[i]->m_type==KX_OBSTACLE_NAV_MESH || m_obstacles[i]->m_shape==KX_OBSTACLE_SEGMENT) + continue; + + KX_Obstacle* obs = m_obstacles[i]; + obs->m_pos = obs->m_gameObj->NodeGetWorldPosition(); + obs->vel[0] = obs->m_gameObj->GetLinearVelocity().x(); + obs->vel[1] = obs->m_gameObj->GetLinearVelocity().y(); + + // Update velocity history and calculate perceived (average) velocity. + vcpy(&obs->hvel[obs->hhead*2], obs->vel); + obs->hhead = (obs->hhead+1) % VEL_HIST_SIZE; + vset(obs->pvel,0,0); + for (int j = 0; j < VEL_HIST_SIZE; ++j) + vadd(obs->pvel, obs->pvel, &obs->hvel[j*2]); + vscale(obs->pvel, obs->pvel, 1.0f/VEL_HIST_SIZE); + } +} + +KX_Obstacle* KX_ObstacleSimulation::GetObstacle(KX_GameObject* gameobj) +{ + for (size_t i=0; i<m_obstacles.size(); i++) + { + if (m_obstacles[i]->m_gameObj == gameobj) + return m_obstacles[i]; + } + + return NULL; +} + +void KX_ObstacleSimulation::AdjustObstacleVelocity(KX_Obstacle* activeObst, KX_NavMeshObject* activeNavMeshObj, + MT_Vector3& velocity, MT_Scalar maxDeltaSpeed,MT_Scalar maxDeltaAngle) +{ +} + +void KX_ObstacleSimulation::DrawObstacles() +{ + if (!m_enableVisualization) + return; + static const MT_Vector3 bluecolor(0,0,1); + static const MT_Vector3 normal(0.,0.,1.); + static const int SECTORS_NUM = 32; + for (size_t i=0; i<m_obstacles.size(); i++) + { + if (m_obstacles[i]->m_shape==KX_OBSTACLE_SEGMENT) + { + MT_Point3 p1 = m_obstacles[i]->m_pos; + MT_Point3 p2 = m_obstacles[i]->m_pos2; + //apply world transform + if (m_obstacles[i]->m_type == KX_OBSTACLE_NAV_MESH) + { + KX_NavMeshObject* navmeshobj = static_cast<KX_NavMeshObject*>(m_obstacles[i]->m_gameObj); + p1 = navmeshobj->TransformToWorldCoords(p1); + p2 = navmeshobj->TransformToWorldCoords(p2); + } + + KX_RasterizerDrawDebugLine(p1, p2, bluecolor); + } + else if (m_obstacles[i]->m_shape==KX_OBSTACLE_CIRCLE) + { + KX_RasterizerDrawDebugCircle(m_obstacles[i]->m_pos, m_obstacles[i]->m_rad, bluecolor, + normal, SECTORS_NUM); + } + } +} + +static MT_Point3 nearestPointToObstacle(MT_Point3& pos ,KX_Obstacle* obstacle) +{ + switch (obstacle->m_shape) + { + case KX_OBSTACLE_SEGMENT : + { + MT_Vector3 ab = obstacle->m_pos2 - obstacle->m_pos; + if (!ab.fuzzyZero()) + { + MT_Vector3 abdir = ab.normalized(); + MT_Vector3 v = pos - obstacle->m_pos; + MT_Scalar proj = abdir.dot(v); + CLAMP(proj, 0, ab.length()); + MT_Point3 res = obstacle->m_pos + abdir*proj; + return res; + } + } + case KX_OBSTACLE_CIRCLE : + default: + return obstacle->m_pos; + } +} + +static bool filterObstacle(KX_Obstacle* activeObst, KX_NavMeshObject* activeNavMeshObj, KX_Obstacle* otherObst, + float levelHeight) +{ + //filter obstacles by type + if ( (otherObst == activeObst) || + (otherObst->m_type==KX_OBSTACLE_NAV_MESH && otherObst->m_gameObj!=activeNavMeshObj) ) + return false; + + //filter obstacles by position + MT_Point3 p = nearestPointToObstacle(activeObst->m_pos, otherObst); + if ( fabs(activeObst->m_pos.z() - p.z()) > levelHeight) + return false; + + return true; +} + +///////////*********TOI_rays**********///////////////// +KX_ObstacleSimulationTOI::KX_ObstacleSimulationTOI(MT_Scalar levelHeight, bool enableVisualization) +: KX_ObstacleSimulation(levelHeight, enableVisualization), + m_maxSamples(32), + m_minToi(0.0f), + m_maxToi(0.0f), + m_velWeight(1.0f), + m_curVelWeight(1.0f), + m_toiWeight(1.0f), + m_collisionWeight(1.0f) +{ +} + + +void KX_ObstacleSimulationTOI::AdjustObstacleVelocity(KX_Obstacle* activeObst, KX_NavMeshObject* activeNavMeshObj, + MT_Vector3& velocity, MT_Scalar maxDeltaSpeed, MT_Scalar maxDeltaAngle) +{ + int nobs = m_obstacles.size(); + int obstidx = std::find(m_obstacles.begin(), m_obstacles.end(), activeObst) - m_obstacles.begin(); + if (obstidx == nobs) + return; + + vset(activeObst->dvel, velocity.x(), velocity.y()); + + //apply RVO + sampleRVO(activeObst, activeNavMeshObj, maxDeltaAngle); + + // Fake dynamic constraint. + float dv[2]; + float vel[2]; + vsub(dv, activeObst->nvel, activeObst->vel); + float ds = vlen(dv); + if (ds > maxDeltaSpeed || ds<-maxDeltaSpeed) + vscale(dv, dv, fabs(maxDeltaSpeed/ds)); + vadd(vel, activeObst->vel, dv); + + velocity.x() = vel[0]; + velocity.y() = vel[1]; +} + +///////////*********TOI_rays**********///////////////// +static const int AVOID_MAX_STEPS = 128; +struct TOICircle +{ + TOICircle() : n(0), minToi(0), maxToi(1) {} + float toi[AVOID_MAX_STEPS]; // Time of impact (seconds) + float toie[AVOID_MAX_STEPS]; // Time of exit (seconds) + float dir[AVOID_MAX_STEPS]; // Direction (radians) + int n; // Number of samples + float minToi, maxToi; // Min/max TOI (seconds) +}; + +KX_ObstacleSimulationTOI_rays::KX_ObstacleSimulationTOI_rays(MT_Scalar levelHeight, bool enableVisualization): + KX_ObstacleSimulationTOI(levelHeight, enableVisualization) +{ + m_maxSamples = 32; + m_minToi = 0.5f; + m_maxToi = 1.2f; + m_velWeight = 4.0f; + m_toiWeight = 1.0f; + m_collisionWeight = 100.0f; +} + + +void KX_ObstacleSimulationTOI_rays::sampleRVO(KX_Obstacle* activeObst, KX_NavMeshObject* activeNavMeshObj, + const float maxDeltaAngle) +{ + MT_Vector2 vel(activeObst->dvel[0], activeObst->dvel[1]); + float vmax = (float) vel.length(); + float odir = (float) atan2(vel.y(), vel.x()); + + MT_Vector2 ddir = vel; + ddir.normalize(); + + float bestScore = FLT_MAX; + float bestDir = odir; + float bestToi = 0; + + TOICircle tc; + tc.n = m_maxSamples; + tc.minToi = m_minToi; + tc.maxToi = m_maxToi; + + const int iforw = m_maxSamples/2; + const float aoff = (float)iforw / (float)m_maxSamples; + + size_t nobs = m_obstacles.size(); + for (int iter = 0; iter < m_maxSamples; ++iter) + { + // Calculate sample velocity + const float ndir = ((float)iter/(float)m_maxSamples) - aoff; + const float dir = odir+ndir*M_PI*2; + MT_Vector2 svel; + svel.x() = cosf(dir) * vmax; + svel.y() = sinf(dir) * vmax; + + // Find min time of impact and exit amongst all obstacles. + float tmin = m_maxToi; + float tmine = 0; + for (int i = 0; i < nobs; ++i) + { + KX_Obstacle* ob = m_obstacles[i]; + bool res = filterObstacle(activeObst, activeNavMeshObj, ob, m_levelHeight); + if (!res) + continue; + + float htmin,htmax; + + if (ob->m_shape == KX_OBSTACLE_CIRCLE) + { + MT_Vector2 vab; + if (vlen(ob->vel) < 0.01f*0.01f) + { + // Stationary, use VO + vab = svel; + } + else + { + // Moving, use RVO + vab = 2*svel - vel - ob->vel; + } + + if (!sweepCircleCircle(activeObst->m_pos, activeObst->m_rad, + vab, ob->m_pos, ob->m_rad, htmin, htmax)) + continue; + } + else if (ob->m_shape == KX_OBSTACLE_SEGMENT) + { + MT_Point3 p1 = ob->m_pos; + MT_Point3 p2 = ob->m_pos2; + //apply world transform + if (ob->m_type == KX_OBSTACLE_NAV_MESH) + { + KX_NavMeshObject* navmeshobj = static_cast<KX_NavMeshObject*>(ob->m_gameObj); + p1 = navmeshobj->TransformToWorldCoords(p1); + p2 = navmeshobj->TransformToWorldCoords(p2); + } + if (!sweepCircleSegment(activeObst->m_pos, activeObst->m_rad, svel, + p1, p2, ob->m_rad, htmin, htmax)) + continue; + } + + if (htmin > 0.0f) + { + // The closest obstacle is somewhere ahead of us, keep track of nearest obstacle. + if (htmin < tmin) + tmin = htmin; + } + else if (htmax > 0.0f) + { + // The agent overlaps the obstacle, keep track of first safe exit. + if (htmax > tmine) + tmine = htmax; + } + } + + // Calculate sample penalties and final score. + const float apen = m_velWeight * fabsf(ndir); + const float tpen = m_toiWeight * (1.0f/(0.0001f+tmin/m_maxToi)); + const float cpen = m_collisionWeight * (tmine/m_minToi)*(tmine/m_minToi); + const float score = apen + tpen + cpen; + + // Update best score. + if (score < bestScore) + { + bestDir = dir; + bestToi = tmin; + bestScore = score; + } + + tc.dir[iter] = dir; + tc.toi[iter] = tmin; + tc.toie[iter] = tmine; + } + + if (vlen(activeObst->vel) > 0.1) + { + // Constrain max turn rate. + float cura = atan2(activeObst->vel[1],activeObst->vel[0]); + float da = bestDir - cura; + if (da < -M_PI) da += (float)M_PI*2; + if (da > M_PI) da -= (float)M_PI*2; + if (da < -maxDeltaAngle) + { + bestDir = cura - maxDeltaAngle; + bestToi = min(bestToi, interpolateToi(bestDir, tc.dir, tc.toi, tc.n)); + } + else if (da > maxDeltaAngle) + { + bestDir = cura + maxDeltaAngle; + bestToi = min(bestToi, interpolateToi(bestDir, tc.dir, tc.toi, tc.n)); + } + } + + // Adjust speed when time of impact is less than min TOI. + if (bestToi < m_minToi) + vmax *= bestToi/m_minToi; + + // New steering velocity. + activeObst->nvel[0] = cosf(bestDir) * vmax; + activeObst->nvel[1] = sinf(bestDir) * vmax; +} + +///////////********* TOI_cells**********///////////////// + +static void processSamples(KX_Obstacle* activeObst, KX_NavMeshObject* activeNavMeshObj, + KX_Obstacles& obstacles, float levelHeight, const float vmax, + const float* spos, const float cs, const int nspos, float* res, + float maxToi, float velWeight, float curVelWeight, float sideWeight, + float toiWeight) +{ + vset(res, 0,0); + + const float ivmax = 1.0f / vmax; + + float adir[2], adist; + vcpy(adir, activeObst->pvel); + if (vlen(adir) > 0.01f) + vnorm(adir); + else + vset(adir,0,0); + float activeObstPos[2]; + vset(activeObstPos, activeObst->m_pos.x(), activeObst->m_pos.y()); + adist = vdot(adir, activeObstPos); + + float minPenalty = FLT_MAX; + + for (int n = 0; n < nspos; ++n) + { + float vcand[2]; + vcpy(vcand, &spos[n*2]); + + // Find min time of impact and exit amongst all obstacles. + float tmin = maxToi; + float side = 0; + int nside = 0; + + for (int i = 0; i < obstacles.size(); ++i) + { + KX_Obstacle* ob = obstacles[i]; + bool res = filterObstacle(activeObst, activeNavMeshObj, ob, levelHeight); + if (!res) + continue; + float htmin, htmax; + + if (ob->m_shape==KX_OBSTACLE_CIRCLE) + { + float vab[2]; + + // Moving, use RVO + vscale(vab, vcand, 2); + vsub(vab, vab, activeObst->vel); + vsub(vab, vab, ob->vel); + + // Side + // NOTE: dp, and dv are constant over the whole calculation, + // they can be precomputed per object. + const float* pa = activeObstPos; + float pb[2]; + vset(pb, ob->m_pos.x(), ob->m_pos.y()); + + const float orig[2] = {0,0}; + float dp[2],dv[2],np[2]; + vsub(dp,pb,pa); + vnorm(dp); + vsub(dv,ob->dvel, activeObst->dvel); + + const float a = triarea(orig, dp,dv); + if (a < 0.01f) + { + np[0] = -dp[1]; + np[1] = dp[0]; + } + else + { + np[0] = dp[1]; + np[1] = -dp[0]; + } + + side += clamp(min(vdot(dp,vab)*2,vdot(np,vab)*2), 0.0f, 1.0f); + nside++; + + if (!sweepCircleCircle(activeObst->m_pos, activeObst->m_rad, vab, ob->m_pos, ob->m_rad, + htmin, htmax)) + continue; + + // Handle overlapping obstacles. + if (htmin < 0.0f && htmax > 0.0f) + { + // Avoid more when overlapped. + htmin = -htmin * 0.5f; + } + } + else if (ob->m_shape == KX_OBSTACLE_SEGMENT) + { + MT_Point3 p1 = ob->m_pos; + MT_Point3 p2 = ob->m_pos2; + //apply world transform + if (ob->m_type == KX_OBSTACLE_NAV_MESH) + { + KX_NavMeshObject* navmeshobj = static_cast<KX_NavMeshObject*>(ob->m_gameObj); + p1 = navmeshobj->TransformToWorldCoords(p1); + p2 = navmeshobj->TransformToWorldCoords(p2); + } + float p[2], q[2]; + vset(p, p1.x(), p1.y()); + vset(q, p2.x(), p2.y()); + + // NOTE: the segments are assumed to come from a navmesh which is shrunken by + // the agent radius, hence the use of really small radius. + // This can be handle more efficiently by using seg-seg test instead. + // If the whole segment is to be treated as obstacle, use agent->rad instead of 0.01f! + const float r = 0.01f; // agent->rad + if (distPtSegSqr(activeObstPos, p, q) < sqr(r+ob->m_rad)) + { + float sdir[2], snorm[2]; + vsub(sdir, q, p); + snorm[0] = sdir[1]; + snorm[1] = -sdir[0]; + // If the velocity is pointing towards the segment, no collision. + if (vdot(snorm, vcand) < 0.0f) + continue; + // Else immediate collision. + htmin = 0.0f; + htmax = 10.0f; + } + else + { + if (!sweepCircleSegment(activeObstPos, r, vcand, p, q, ob->m_rad, htmin, htmax)) + continue; + } + + // Avoid less when facing walls. + htmin *= 2.0f; + } + + if (htmin >= 0.0f) + { + // The closest obstacle is somewhere ahead of us, keep track of nearest obstacle. + if (htmin < tmin) + tmin = htmin; + } + } + + // Normalize side bias, to prevent it dominating too much. + if (nside) + side /= nside; + + const float vpen = velWeight * (vdist(vcand, activeObst->dvel) * ivmax); + const float vcpen = curVelWeight * (vdist(vcand, activeObst->vel) * ivmax); + const float spen = sideWeight * side; + const float tpen = toiWeight * (1.0f/(0.1f+tmin/maxToi)); + + const float penalty = vpen + vcpen + spen + tpen; + + if (penalty < minPenalty) + { + minPenalty = penalty; + vcpy(res, vcand); + } + } +} + +void KX_ObstacleSimulationTOI_cells::sampleRVO(KX_Obstacle* activeObst, KX_NavMeshObject* activeNavMeshObj, + const float maxDeltaAngle) +{ + vset(activeObst->nvel, 0.f, 0.f); + float vmax = vlen(activeObst->dvel); + + float* spos = new float[2*m_maxSamples]; + int nspos = 0; + + if (!m_adaptive) + { + const float cvx = activeObst->dvel[0]*m_bias; + const float cvy = activeObst->dvel[1]*m_bias; + float vmax = vlen(activeObst->dvel); + const float vrange = vmax*(1-m_bias); + const float cs = 1.0f / (float)m_sampleRadius*vrange; + + for (int y = -m_sampleRadius; y <= m_sampleRadius; ++y) + { + for (int x = -m_sampleRadius; x <= m_sampleRadius; ++x) + { + if (nspos < m_maxSamples) + { + const float vx = cvx + (float)(x+0.5f)*cs; + const float vy = cvy + (float)(y+0.5f)*cs; + if (vx*vx+vy*vy > sqr(vmax+cs/2)) continue; + spos[nspos*2+0] = vx; + spos[nspos*2+1] = vy; + nspos++; + } + } + } + processSamples(activeObst, activeNavMeshObj, m_obstacles, m_levelHeight, vmax, spos, cs/2, + nspos, activeObst->nvel, m_maxToi, m_velWeight, m_curVelWeight, m_collisionWeight, m_toiWeight); + } + else + { + int rad; + float res[2]; + float cs; + // First sample location. + rad = 4; + res[0] = activeObst->dvel[0]*m_bias; + res[1] = activeObst->dvel[1]*m_bias; + cs = vmax*(2-m_bias*2) / (float)(rad-1); + + for (int k = 0; k < 5; ++k) + { + const float half = (rad-1)*cs*0.5f; + + nspos = 0; + for (int y = 0; y < rad; ++y) + { + for (int x = 0; x < rad; ++x) + { + const float vx = res[0] + x*cs - half; + const float vy = res[1] + y*cs - half; + if (vx*vx+vy*vy > sqr(vmax+cs/2)) continue; + spos[nspos*2+0] = vx; + spos[nspos*2+1] = vy; + nspos++; + } + } + + processSamples(activeObst, activeNavMeshObj, m_obstacles, m_levelHeight, vmax, spos, cs/2, + nspos, res, m_maxToi, m_velWeight, m_curVelWeight, m_collisionWeight, m_toiWeight); + + cs *= 0.5f; + } + vcpy(activeObst->nvel, res); + } +} + +KX_ObstacleSimulationTOI_cells::KX_ObstacleSimulationTOI_cells(MT_Scalar levelHeight, bool enableVisualization) +: KX_ObstacleSimulationTOI(levelHeight, enableVisualization) +, m_bias(0.4f) +, m_adaptive(true) +, m_sampleRadius(15) +{ + m_maxSamples = (m_sampleRadius*2+1)*(m_sampleRadius*2+1) + 100; + m_maxToi = 1.5f; + m_velWeight = 2.0f; + m_curVelWeight = 0.75f; + m_toiWeight = 2.5f; + m_collisionWeight = 0.75f; //side_weight +}
\ No newline at end of file diff --git a/source/gameengine/Ketsji/KX_ObstacleSimulation.h b/source/gameengine/Ketsji/KX_ObstacleSimulation.h new file mode 100644 index 00000000000..d926e8deb71 --- /dev/null +++ b/source/gameengine/Ketsji/KX_ObstacleSimulation.h @@ -0,0 +1,145 @@ +/** +* Simulation for obstacle avoidance behavior +* (based on Cane Project - http://code.google.com/p/cane by Mikko Mononen (c) 2009) +* +* +* $Id$ +* +* ***** BEGIN GPL LICENSE BLOCK ***** +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License +* as published by the Free Software Foundation; either version 2 +* of the License, or (at your option) any later version. The Blender +* Foundation also sells licenses for use in proprietary software under +* the Blender License. See http://www.blender.org/BL/ for information +* about this. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software Foundation, +* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +* +* The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. +* All rights reserved. +* +* The Original Code is: all of this file. +* +* Contributor(s): none yet. +* +* ***** END GPL LICENSE BLOCK ***** +*/ + +#ifndef __KX_OBSTACLESIMULATION +#define __KX_OBSTACLESIMULATION + +#include <vector> +#include "MT_Point2.h" +#include "MT_Point3.h" + +class KX_GameObject; +class KX_NavMeshObject; + +enum KX_OBSTACLE_TYPE +{ + KX_OBSTACLE_OBJ, + KX_OBSTACLE_NAV_MESH, +}; + +enum KX_OBSTACLE_SHAPE +{ + KX_OBSTACLE_CIRCLE, + KX_OBSTACLE_SEGMENT, +}; + +#define VEL_HIST_SIZE 6 +struct KX_Obstacle +{ + KX_OBSTACLE_TYPE m_type; + KX_OBSTACLE_SHAPE m_shape; + MT_Point3 m_pos; + MT_Point3 m_pos2; + MT_Scalar m_rad; + + float vel[2]; + float pvel[2]; + float dvel[2]; + float nvel[2]; + float hvel[VEL_HIST_SIZE*2]; + int hhead; + + + KX_GameObject* m_gameObj; +}; +typedef std::vector<KX_Obstacle*> KX_Obstacles; + +class KX_ObstacleSimulation +{ +protected: + KX_Obstacles m_obstacles; + + MT_Scalar m_levelHeight; + bool m_enableVisualization; + + KX_Obstacle* CreateObstacle(KX_GameObject* gameobj); +public: + KX_ObstacleSimulation(MT_Scalar levelHeight, bool enableVisualization); + virtual ~KX_ObstacleSimulation(); + + void DrawObstacles(); + //void DebugDraw(); + + void AddObstacleForObj(KX_GameObject* gameobj); + void DestroyObstacleForObj(KX_GameObject* gameobj); + void AddObstaclesForNavMesh(KX_NavMeshObject* navmesh); + KX_Obstacle* GetObstacle(KX_GameObject* gameobj); + void UpdateObstacles(); + virtual void AdjustObstacleVelocity(KX_Obstacle* activeObst, KX_NavMeshObject* activeNavMeshObj, + MT_Vector3& velocity, MT_Scalar maxDeltaSpeed,MT_Scalar maxDeltaAngle); + +}; +class KX_ObstacleSimulationTOI: public KX_ObstacleSimulation +{ +protected: + int m_maxSamples; // Number of sample steps + float m_minToi; // Min TOI + float m_maxToi; // Max TOI + float m_velWeight; // Sample selection angle weight + float m_curVelWeight; // Sample selection current velocity weight + float m_toiWeight; // Sample selection TOI weight + float m_collisionWeight; // Sample selection collision weight + + virtual void sampleRVO(KX_Obstacle* activeObst, KX_NavMeshObject* activeNavMeshObj, + const float maxDeltaAngle) = 0; +public: + KX_ObstacleSimulationTOI(MT_Scalar levelHeight, bool enableVisualization); + virtual void AdjustObstacleVelocity(KX_Obstacle* activeObst, KX_NavMeshObject* activeNavMeshObj, + MT_Vector3& velocity, MT_Scalar maxDeltaSpeed,MT_Scalar maxDeltaAngle); +}; + +class KX_ObstacleSimulationTOI_rays: public KX_ObstacleSimulationTOI +{ +protected: + virtual void sampleRVO(KX_Obstacle* activeObst, KX_NavMeshObject* activeNavMeshObj, + const float maxDeltaAngle); +public: + KX_ObstacleSimulationTOI_rays(MT_Scalar levelHeight, bool enableVisualization); +}; + +class KX_ObstacleSimulationTOI_cells: public KX_ObstacleSimulationTOI +{ +protected: + float m_bias; + bool m_adaptive; + int m_sampleRadius; + virtual void sampleRVO(KX_Obstacle* activeObst, KX_NavMeshObject* activeNavMeshObj, + const float maxDeltaAngle); +public: + KX_ObstacleSimulationTOI_cells(MT_Scalar levelHeight, bool enableVisualization); +}; + +#endif diff --git a/source/gameengine/Ketsji/KX_PythonInit.cpp b/source/gameengine/Ketsji/KX_PythonInit.cpp index c8a6ae5a6d0..f984538fa5b 100644 --- a/source/gameengine/Ketsji/KX_PythonInit.cpp +++ b/source/gameengine/Ketsji/KX_PythonInit.cpp @@ -87,6 +87,8 @@ extern "C" { #include "KX_GameActuator.h" #include "KX_ParentActuator.h" #include "KX_SCA_DynamicActuator.h" +#include "KX_SteeringActuator.h" +#include "KX_NavMeshObject.h" #include "SCA_IInputDevice.h" #include "SCA_PropertySensor.h" @@ -180,6 +182,13 @@ void KX_RasterizerDrawDebugLine(const MT_Vector3& from,const MT_Vector3& to,cons gp_Rasterizer->DrawDebugLine(from,to,color); } +void KX_RasterizerDrawDebugCircle(const MT_Vector3& center, const MT_Scalar radius, const MT_Vector3& color, + const MT_Vector3& normal, int nsector) +{ + if (gp_Rasterizer) + gp_Rasterizer->DrawDebugCircle(center, radius, color, normal, nsector); +} + #ifdef WITH_PYTHON static PyObject *gp_OrigPythonSysPath= NULL; @@ -1628,6 +1637,16 @@ PyObject* initGameLogic(KX_KetsjiEngine *engine, KX_Scene* scene) // quick hack KX_MACRO_addTypesToDict(d, ROT_MODE_ZXY, ROT_MODE_ZXY); KX_MACRO_addTypesToDict(d, ROT_MODE_ZYX, ROT_MODE_ZYX); + /* Steering actuator */ + KX_MACRO_addTypesToDict(d, KX_STEERING_SEEK, KX_SteeringActuator::KX_STEERING_SEEK); + KX_MACRO_addTypesToDict(d, KX_STEERING_FLEE, KX_SteeringActuator::KX_STEERING_FLEE); + KX_MACRO_addTypesToDict(d, KX_STEERING_PATHFOLLOWING, KX_SteeringActuator::KX_STEERING_PATHFOLLOWING); + + /* KX_NavMeshObject render mode */ + KX_MACRO_addTypesToDict(d, RM_WALLS, KX_NavMeshObject::RM_WALLS); + KX_MACRO_addTypesToDict(d, RM_POLYS, KX_NavMeshObject::RM_POLYS); + KX_MACRO_addTypesToDict(d, RM_TRIS, KX_NavMeshObject::RM_TRIS); + // Check for errors if (PyErr_Occurred()) { diff --git a/source/gameengine/Ketsji/KX_PythonInit.h b/source/gameengine/Ketsji/KX_PythonInit.h index 1b172c35eff..d76e8f913df 100644 --- a/source/gameengine/Ketsji/KX_PythonInit.h +++ b/source/gameengine/Ketsji/KX_PythonInit.h @@ -72,6 +72,9 @@ class KX_KetsjiEngine* KX_GetActiveEngine(); #include "MT_Vector3.h" void KX_RasterizerDrawDebugLine(const MT_Vector3& from,const MT_Vector3& to,const MT_Vector3& color); +void KX_RasterizerDrawDebugCircle(const MT_Vector3& center, const MT_Scalar radius, const MT_Vector3& color, + const MT_Vector3& normal, int nsector); + #endif //__KX_PYTHON_INIT diff --git a/source/gameengine/Ketsji/KX_PythonInitTypes.cpp b/source/gameengine/Ketsji/KX_PythonInitTypes.cpp index 1c4a17e31fc..49a08135c38 100644 --- a/source/gameengine/Ketsji/KX_PythonInitTypes.cpp +++ b/source/gameengine/Ketsji/KX_PythonInitTypes.cpp @@ -68,6 +68,7 @@ #include "KX_SCA_ReplaceMeshActuator.h" #include "KX_SceneActuator.h" #include "KX_StateActuator.h" +#include "KX_SteeringActuator.h" #include "KX_TrackToActuator.h" #include "KX_VehicleWrapper.h" #include "KX_VertexProxy.h" @@ -99,6 +100,7 @@ #include "SCA_PythonController.h" #include "SCA_RandomActuator.h" #include "SCA_IController.h" +#include "KX_NavMeshObject.h" static void PyType_Attr_Set(PyGetSetDef *attr_getset, PyAttributeDef *attr) { @@ -217,9 +219,11 @@ void initPyTypes(void) PyType_Ready_Attr(dict, KX_SCA_EndObjectActuator, init_getset); PyType_Ready_Attr(dict, KX_SCA_ReplaceMeshActuator, init_getset); PyType_Ready_Attr(dict, KX_Scene, init_getset); + PyType_Ready_Attr(dict, KX_NavMeshObject, init_getset); PyType_Ready_Attr(dict, KX_SceneActuator, init_getset); PyType_Ready_Attr(dict, KX_SoundActuator, init_getset); PyType_Ready_Attr(dict, KX_StateActuator, init_getset); + PyType_Ready_Attr(dict, KX_SteeringActuator, init_getset); PyType_Ready_Attr(dict, KX_TouchSensor, init_getset); PyType_Ready_Attr(dict, KX_TrackToActuator, init_getset); PyType_Ready_Attr(dict, KX_VehicleWrapper, init_getset); diff --git a/source/gameengine/Ketsji/KX_Scene.cpp b/source/gameengine/Ketsji/KX_Scene.cpp index 28dc660037c..5e0e46026df 100644 --- a/source/gameengine/Ketsji/KX_Scene.cpp +++ b/source/gameengine/Ketsji/KX_Scene.cpp @@ -87,6 +87,7 @@ #include "BL_ModifierDeformer.h" #include "BL_ShapeDeformer.h" #include "BL_DeformableGameObject.h" +#include "KX_ObstacleSimulation.h" #ifdef USE_BULLET #include "KX_SoftBodyDeformer.h" @@ -213,6 +214,19 @@ KX_Scene::KX_Scene(class SCA_IInputDevice* keyboarddevice, m_bucketmanager=new RAS_BucketManager(); + bool showObstacleSimulation = scene->gm.flag & GAME_SHOW_OBSTACLE_SIMULATION; + switch (scene->gm.obstacleSimulation) + { + case OBSTSIMULATION_TOI_rays: + m_obstacleSimulation = new KX_ObstacleSimulationTOI_rays((MT_Scalar)scene->gm.levelHeight, showObstacleSimulation); + break; + case OBSTSIMULATION_TOI_cells: + m_obstacleSimulation = new KX_ObstacleSimulationTOI_cells((MT_Scalar)scene->gm.levelHeight, showObstacleSimulation); + break; + default: + m_obstacleSimulation = NULL; + } + #ifdef WITH_PYTHON m_attr_dict = PyDict_New(); /* new ref */ m_draw_call_pre = NULL; @@ -235,6 +249,9 @@ KX_Scene::~KX_Scene() this->RemoveObject(parentobj); } + if (m_obstacleSimulation) + delete m_obstacleSimulation; + if(m_objectlist) m_objectlist->Release(); @@ -1526,6 +1543,10 @@ void KX_Scene::LogicEndFrame() obj->Release(); RemoveObject(obj); } + + //prepare obstacle simulation for new frame + if (m_obstacleSimulation) + m_obstacleSimulation->UpdateObstacles(); } @@ -1953,6 +1974,8 @@ PyMethodDef KX_Scene::Methods[] = { KX_PYMETHODTABLE(KX_Scene, replace), KX_PYMETHODTABLE(KX_Scene, suspend), KX_PYMETHODTABLE(KX_Scene, resume), + KX_PYMETHODTABLE(KX_Scene, drawObstacleSimulation), + /* dict style access */ KX_PYMETHODTABLE(KX_Scene, get), @@ -2277,6 +2300,16 @@ KX_PYMETHODDEF_DOC(KX_Scene, resume, Py_RETURN_NONE; } +KX_PYMETHODDEF_DOC(KX_Scene, drawObstacleSimulation, + "drawObstacleSimulation()\n" + "Draw debug visualization of obstacle simulation.\n") +{ + if (GetObstacleSimulation()) + GetObstacleSimulation()->DrawObstacles(); + + Py_RETURN_NONE; +} + /* Matches python dict.get(key, [default]) */ KX_PYMETHODDEF_DOC(KX_Scene, get, "") { diff --git a/source/gameengine/Ketsji/KX_Scene.h b/source/gameengine/Ketsji/KX_Scene.h index 367bf0b82da..26dec2d612b 100644 --- a/source/gameengine/Ketsji/KX_Scene.h +++ b/source/gameengine/Ketsji/KX_Scene.h @@ -88,6 +88,7 @@ class SCA_JoystickManager; class btCollisionShape; class KX_BlenderSceneConverter; struct KX_ClientObjectInfo; +class KX_ObstacleSimulation; #ifdef WITH_CXX_GUARDEDALLOC #include "MEM_guardedalloc.h" @@ -292,6 +293,9 @@ protected: struct Scene* m_blenderScene; RAS_2DFilterManager m_filtermanager; + + KX_ObstacleSimulation* m_obstacleSimulation; + public: KX_Scene(class SCA_IInputDevice* keyboarddevice, class SCA_IInputDevice* mousedevice, @@ -577,6 +581,8 @@ public: void Update2DFilter(vector<STR_String>& propNames, void* gameObj, RAS_2DFilterManager::RAS_2DFILTER_MODE filtermode, int pass, STR_String& text); void Render2DFilters(RAS_ICanvas* canvas); + KX_ObstacleSimulation* GetObstacleSimulation() {return m_obstacleSimulation;}; + #ifdef WITH_PYTHON /* --------------------------------------------------------------------- */ /* Python interface ---------------------------------------------------- */ @@ -589,6 +595,8 @@ public: KX_PYMETHOD_DOC(KX_Scene, suspend); KX_PYMETHOD_DOC(KX_Scene, resume); KX_PYMETHOD_DOC(KX_Scene, get); + KX_PYMETHOD_DOC(KX_Scene, drawObstacleSimulation); + /* attributes */ static PyObject* pyattr_get_name(void* self_v, const KX_PYATTRIBUTE_DEF *attrdef); diff --git a/source/gameengine/Ketsji/KX_SteeringActuator.cpp b/source/gameengine/Ketsji/KX_SteeringActuator.cpp new file mode 100644 index 00000000000..a0a2e148c1e --- /dev/null +++ b/source/gameengine/Ketsji/KX_SteeringActuator.cpp @@ -0,0 +1,630 @@ +/** +* Add steering behaviors +* +* $Id$ +* +* ***** BEGIN GPL LICENSE BLOCK ***** +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License +* as published by the Free Software Foundation; either version 2 +* of the License, or (at your option) any later version. The Blender +* Foundation also sells licenses for use in proprietary software under +* the Blender License. See http://www.blender.org/BL/ for information +* about this. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software Foundation, +* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +* +* The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. +* All rights reserved. +* +* The Original Code is: all of this file. +* +* Contributor(s): none yet. +* +* ***** END GPL LICENSE BLOCK ***** +*/ + +#include "BLI_math.h" +#include "KX_SteeringActuator.h" +#include "KX_GameObject.h" +#include "KX_NavMeshObject.h" +#include "KX_ObstacleSimulation.h" +#include "KX_PythonInit.h" +#include "KX_PyMath.h" +#include "Recast.h" + +/* ------------------------------------------------------------------------- */ +/* Native functions */ +/* ------------------------------------------------------------------------- */ + +KX_SteeringActuator::KX_SteeringActuator(SCA_IObject *gameobj, + int mode, + KX_GameObject *target, + KX_GameObject *navmesh, + float distance, + float velocity, + float acceleration, + float turnspeed, + bool isSelfTerminated, + int pathUpdatePeriod, + KX_ObstacleSimulation* simulation, + short facingmode, + bool normalup, + bool enableVisualization) : + SCA_IActuator(gameobj, KX_ACT_STEERING), + m_mode(mode), + m_target(target), + m_distance(distance), + m_velocity(velocity), + m_acceleration(acceleration), + m_turnspeed(turnspeed), + m_isSelfTerminated(isSelfTerminated), + m_pathUpdatePeriod(pathUpdatePeriod), + m_updateTime(0), + m_isActive(false), + m_simulation(simulation), + m_enableVisualization(enableVisualization), + m_facingMode(facingmode), + m_normalUp(normalup), + m_obstacle(NULL), + m_pathLen(0), + m_wayPointIdx(-1), + m_steerVec(MT_Vector3(0, 0, 0)) +{ + m_navmesh = static_cast<KX_NavMeshObject*>(navmesh); + if (m_navmesh) + m_navmesh->RegisterActuator(this); + if (m_target) + m_target->RegisterActuator(this); + + if (m_simulation) + m_obstacle = m_simulation->GetObstacle((KX_GameObject*)gameobj); + KX_GameObject* parent = ((KX_GameObject*)gameobj)->GetParent(); + if (m_facingMode>0 && parent) + { + m_parentlocalmat = parent->GetSGNode()->GetLocalOrientation(); + } + else + m_parentlocalmat.setIdentity(); +} + +KX_SteeringActuator::~KX_SteeringActuator() +{ + if (m_navmesh) + m_navmesh->UnregisterActuator(this); + if (m_target) + m_target->UnregisterActuator(this); +} + +CValue* KX_SteeringActuator::GetReplica() +{ + KX_SteeringActuator* replica = new KX_SteeringActuator(*this); + // replication just copy the m_base pointer => common random generator + replica->ProcessReplica(); + return replica; +} + +void KX_SteeringActuator::ProcessReplica() +{ + if (m_target) + m_target->RegisterActuator(this); + if (m_navmesh) + m_navmesh->RegisterActuator(this); + SCA_IActuator::ProcessReplica(); +} + + +bool KX_SteeringActuator::UnlinkObject(SCA_IObject* clientobj) +{ + if (clientobj == m_target) + { + m_target = NULL; + return true; + } + else if (clientobj == m_navmesh) + { + m_navmesh = NULL; + return true; + } + return false; +} + +void KX_SteeringActuator::Relink(CTR_Map<CTR_HashedPtr, void*> *obj_map) +{ + void **h_obj = (*obj_map)[m_target]; + if (h_obj) { + if (m_target) + m_target->UnregisterActuator(this); + m_target = (KX_GameObject*)(*h_obj); + m_target->RegisterActuator(this); + } + + h_obj = (*obj_map)[m_navmesh]; + if (h_obj) { + if (m_navmesh) + m_navmesh->UnregisterActuator(this); + m_navmesh = (KX_NavMeshObject*)(*h_obj); + m_navmesh->RegisterActuator(this); + } +} + +bool KX_SteeringActuator::Update(double curtime, bool frame) +{ + if (frame) + { + double delta = curtime - m_updateTime; + m_updateTime = curtime; + + if (m_posevent && !m_isActive) + { + delta = 0; + m_pathUpdateTime = -1; + m_updateTime = curtime; + m_isActive = true; + } + bool bNegativeEvent = IsNegativeEvent(); + if (bNegativeEvent) + m_isActive = false; + + RemoveAllEvents(); + + if (!delta) + return true; + + if (bNegativeEvent || !m_target) + return false; // do nothing on negative events + + KX_GameObject *obj = (KX_GameObject*) GetParent(); + const MT_Point3& mypos = obj->NodeGetWorldPosition(); + const MT_Point3& targpos = m_target->NodeGetWorldPosition(); + MT_Vector3 vectotarg = targpos - mypos; + MT_Vector3 vectotarg2d = vectotarg; + vectotarg2d.z() = 0; + m_steerVec = MT_Vector3(0, 0, 0); + bool apply_steerforce = false; + bool terminate = true; + + switch (m_mode) { + case KX_STEERING_SEEK: + if (vectotarg2d.length2()>m_distance*m_distance) + { + terminate = false; + m_steerVec = vectotarg; + m_steerVec.normalize(); + apply_steerforce = true; + } + break; + case KX_STEERING_FLEE: + if (vectotarg2d.length2()<m_distance*m_distance) + { + terminate = false; + m_steerVec = -vectotarg; + m_steerVec.normalize(); + apply_steerforce = true; + } + break; + case KX_STEERING_PATHFOLLOWING: + if (m_navmesh && vectotarg.length2()>m_distance*m_distance) + { + terminate = false; + + static const MT_Scalar WAYPOINT_RADIUS(0.25); + + if (m_pathUpdateTime<0 || (m_pathUpdatePeriod>=0 && + curtime - m_pathUpdateTime>((double)m_pathUpdatePeriod/1000))) + { + m_pathUpdateTime = curtime; + m_pathLen = m_navmesh->FindPath(mypos, targpos, m_path, MAX_PATH_LENGTH); + m_wayPointIdx = m_pathLen > 1 ? 1 : -1; + } + + if (m_wayPointIdx>0) + { + MT_Vector3 waypoint(&m_path[3*m_wayPointIdx]); + if ((waypoint-mypos).length2()<WAYPOINT_RADIUS*WAYPOINT_RADIUS) + { + m_wayPointIdx++; + if (m_wayPointIdx>=m_pathLen) + { + m_wayPointIdx = -1; + terminate = true; + } + else + waypoint.setValue(&m_path[3*m_wayPointIdx]); + } + + m_steerVec = waypoint - mypos; + apply_steerforce = true; + + + if (m_enableVisualization) + { + //debug draw + static const MT_Vector3 PATH_COLOR(1,0,0); + m_navmesh->DrawPath(m_path, m_pathLen, PATH_COLOR); + } + } + + } + break; + } + + if (apply_steerforce) + { + bool isdyna = obj->IsDynamic(); + if (isdyna) + m_steerVec.z() = 0; + if (!m_steerVec.fuzzyZero()) + m_steerVec.normalize(); + MT_Vector3 newvel = m_velocity*m_steerVec; + + //adjust velocity to avoid obstacles + if (m_simulation && m_obstacle /*&& !newvel.fuzzyZero()*/) + { + if (m_enableVisualization) + KX_RasterizerDrawDebugLine(mypos, mypos + newvel, MT_Vector3(1.,0.,0.)); + m_simulation->AdjustObstacleVelocity(m_obstacle, m_mode!=KX_STEERING_PATHFOLLOWING ? m_navmesh : NULL, + newvel, m_acceleration*delta, m_turnspeed/180.0f*M_PI*delta); + if (m_enableVisualization) + KX_RasterizerDrawDebugLine(mypos, mypos + newvel, MT_Vector3(0.,1.,0.)); + } + + HandleActorFace(newvel); + if (isdyna) + { + //temporary solution: set 2D steering velocity directly to obj + //correct way is to apply physical force + MT_Vector3 curvel = obj->GetLinearVelocity(); + newvel.z() = curvel.z(); + obj->setLinearVelocity(newvel, false); + } + else + { + MT_Vector3 movement = delta*newvel; + obj->ApplyMovement(movement, false); + } + } + else + { + if (m_simulation && m_obstacle) + { + m_obstacle->dvel[0] = 0.f; + m_obstacle->dvel[1] = 0.f; + } + + } + + if (terminate && m_isSelfTerminated) + return false; + } + + return true; +} + +const MT_Vector3& KX_SteeringActuator::GetSteeringVec() +{ + static MT_Vector3 ZERO_VECTOR(0, 0, 0); + if (m_isActive) + return m_steerVec; + else + return ZERO_VECTOR; +} + +inline float vdot2(const float* a, const float* b) +{ + return a[0]*b[0] + a[2]*b[2]; +} +static bool barDistSqPointToTri(const float* p, const float* a, const float* b, const float* c) +{ + float v0[3], v1[3], v2[3]; + vsub(v0, c,a); + vsub(v1, b,a); + vsub(v2, p,a); + + const float dot00 = vdot2(v0, v0); + const float dot01 = vdot2(v0, v1); + const float dot02 = vdot2(v0, v2); + const float dot11 = vdot2(v1, v1); + const float dot12 = vdot2(v1, v2); + + // Compute barycentric coordinates + float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01); + float u = (dot11 * dot02 - dot01 * dot12) * invDenom; + float v = (dot00 * dot12 - dot01 * dot02) * invDenom; + + float ud = u<0.f ? -u : (u>1.f ? u-1.f : 0.f); + float vd = v<0.f ? -v : (v>1.f ? v-1.f : 0.f); + return ud*ud+vd*vd ; +} + +inline void flipAxes(float* vec) +{ + std::swap(vec[1],vec[2]); +} + +static bool getNavmeshNormal(dtStatNavMesh* navmesh, const MT_Vector3& pos, MT_Vector3& normal) +{ + static const float polyPickExt[3] = {2, 4, 2}; + float spos[3]; + pos.getValue(spos); + flipAxes(spos); + dtStatPolyRef sPolyRef = navmesh->findNearestPoly(spos, polyPickExt); + if (sPolyRef == 0) + return false; + const dtStatPoly* p = navmesh->getPoly(sPolyRef-1); + const dtStatPolyDetail* pd = navmesh->getPolyDetail(sPolyRef-1); + + float distMin = FLT_MAX; + int idxMin = -1; + for (int i = 0; i < pd->ntris; ++i) + { + const unsigned char* t = navmesh->getDetailTri(pd->tbase+i); + const float* v[3]; + for (int j = 0; j < 3; ++j) + { + if (t[j] < p->nv) + v[j] = navmesh->getVertex(p->v[t[j]]); + else + v[j] = navmesh->getDetailVertex(pd->vbase+(t[j]-p->nv)); + } + float dist = barDistSqPointToTri(spos, v[0], v[1], v[2]); + if (dist<distMin) + { + distMin = dist; + idxMin = i; + } + } + + if (idxMin>=0) + { + const unsigned char* t = navmesh->getDetailTri(pd->tbase+idxMin); + const float* v[3]; + for (int j = 0; j < 3; ++j) + { + if (t[j] < p->nv) + v[j] = navmesh->getVertex(p->v[t[j]]); + else + v[j] = navmesh->getDetailVertex(pd->vbase+(t[j]-p->nv)); + } + MT_Vector3 tri[3]; + for (size_t j=0; j<3; j++) + tri[j].setValue(v[j][0],v[j][2],v[j][1]); + MT_Vector3 a,b; + a = tri[1]-tri[0]; + b = tri[2]-tri[0]; + normal = b.cross(a).safe_normalized(); + return true; + } + + return false; +} + +void KX_SteeringActuator::HandleActorFace(MT_Vector3& velocity) +{ + if (m_facingMode==0 && (!m_navmesh || !m_normalUp)) + return; + KX_GameObject* curobj = (KX_GameObject*) GetParent(); + MT_Vector3 dir = m_facingMode==0 ? curobj->NodeGetLocalOrientation().getColumn(1) : velocity; + if (dir.fuzzyZero()) + return; + dir.normalize(); + MT_Vector3 up(0,0,1); + MT_Vector3 left; + MT_Matrix3x3 mat; + + if (m_navmesh && m_normalUp) + { + dtStatNavMesh* navmesh = m_navmesh->GetNavMesh(); + MT_Vector3 normal; + MT_Vector3 trpos = m_navmesh->TransformToLocalCoords(curobj->NodeGetWorldPosition()); + if (getNavmeshNormal(navmesh, trpos, normal)) + { + + left = (dir.cross(up)).safe_normalized(); + dir = (-left.cross(normal)).safe_normalized(); + up = normal; + } + } + + switch (m_facingMode) + { + case 1: // TRACK X + { + left = dir.safe_normalized(); + dir = -(left.cross(up)).safe_normalized(); + break; + }; + case 2: // TRACK Y + { + left = (dir.cross(up)).safe_normalized(); + break; + } + + case 3: // track Z + { + left = up.safe_normalized(); + up = dir.safe_normalized(); + dir = left; + left = (dir.cross(up)).safe_normalized(); + break; + } + + case 4: // TRACK -X + { + left = -dir.safe_normalized(); + dir = -(left.cross(up)).safe_normalized(); + break; + }; + case 5: // TRACK -Y + { + left = (-dir.cross(up)).safe_normalized(); + dir = -dir; + break; + } + case 6: // track -Z + { + left = up.safe_normalized(); + up = -dir.safe_normalized(); + dir = left; + left = (dir.cross(up)).safe_normalized(); + break; + } + } + + mat.setValue ( + left[0], dir[0],up[0], + left[1], dir[1],up[1], + left[2], dir[2],up[2] + ); + + + + KX_GameObject* parentObject = curobj->GetParent(); + if(parentObject) + { + MT_Point3 localpos; + localpos = curobj->GetSGNode()->GetLocalPosition(); + MT_Matrix3x3 parentmatinv; + parentmatinv = parentObject->NodeGetWorldOrientation ().inverse (); + mat = parentmatinv * mat; + mat = m_parentlocalmat * mat; + curobj->NodeSetLocalOrientation(mat); + curobj->NodeSetLocalPosition(localpos); + } + else + { + curobj->NodeSetLocalOrientation(mat); + } + +} + +#ifndef DISABLE_PYTHON + +/* ------------------------------------------------------------------------- */ +/* Python functions */ +/* ------------------------------------------------------------------------- */ + +/* Integration hooks ------------------------------------------------------- */ +PyTypeObject KX_SteeringActuator::Type = { + PyVarObject_HEAD_INIT(NULL, 0) + "KX_SteeringActuator", + sizeof(PyObjectPlus_Proxy), + 0, + py_base_dealloc, + 0, + 0, + 0, + 0, + py_base_repr, + 0,0,0,0,0,0,0,0,0, + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, + 0,0,0,0,0,0,0, + Methods, + 0, + 0, + &SCA_IActuator::Type, + 0,0,0,0,0,0, + py_base_new +}; + +PyMethodDef KX_SteeringActuator::Methods[] = { + {NULL,NULL} //Sentinel +}; + +PyAttributeDef KX_SteeringActuator::Attributes[] = { + KX_PYATTRIBUTE_INT_RW("behaviour", KX_STEERING_NODEF+1, KX_STEERING_MAX-1, true, KX_SteeringActuator, m_mode), + KX_PYATTRIBUTE_RW_FUNCTION("target", KX_SteeringActuator, pyattr_get_target, pyattr_set_target), + KX_PYATTRIBUTE_RW_FUNCTION("navmesh", KX_SteeringActuator, pyattr_get_navmesh, pyattr_set_navmesh), + KX_PYATTRIBUTE_FLOAT_RW("distance", 0.0f, 1000.0f, KX_SteeringActuator, m_distance), + KX_PYATTRIBUTE_FLOAT_RW("velocity", 0.0f, 1000.0f, KX_SteeringActuator, m_velocity), + KX_PYATTRIBUTE_FLOAT_RW("acceleration", 0.0f, 1000.0f, KX_SteeringActuator, m_acceleration), + KX_PYATTRIBUTE_FLOAT_RW("turnspeed", 0.0f, 720.0f, KX_SteeringActuator, m_turnspeed), + KX_PYATTRIBUTE_BOOL_RW("selfterminated", KX_SteeringActuator, m_isSelfTerminated), + KX_PYATTRIBUTE_BOOL_RW("enableVisualization", KX_SteeringActuator, m_enableVisualization), + KX_PYATTRIBUTE_RO_FUNCTION("steeringVec", KX_SteeringActuator, pyattr_get_steeringVec), + KX_PYATTRIBUTE_SHORT_RW("facingMode", 0, 6, true, KX_SteeringActuator, m_facingMode), + KX_PYATTRIBUTE_INT_RW("pathUpdatePeriod", -1, 100000, true, KX_SteeringActuator, m_pathUpdatePeriod), + { NULL } //Sentinel +}; + +PyObject* KX_SteeringActuator::pyattr_get_target(void *self, const struct KX_PYATTRIBUTE_DEF *attrdef) +{ + KX_SteeringActuator* actuator = static_cast<KX_SteeringActuator*>(self); + if (!actuator->m_target) + Py_RETURN_NONE; + else + return actuator->m_target->GetProxy(); +} + +int KX_SteeringActuator::pyattr_set_target(void *self, const struct KX_PYATTRIBUTE_DEF *attrdef, PyObject *value) +{ + KX_SteeringActuator* actuator = static_cast<KX_SteeringActuator*>(self); + KX_GameObject *gameobj; + + if (!ConvertPythonToGameObject(value, &gameobj, true, "actuator.object = value: KX_SteeringActuator")) + return PY_SET_ATTR_FAIL; // ConvertPythonToGameObject sets the error + + if (actuator->m_target != NULL) + actuator->m_target->UnregisterActuator(actuator); + + actuator->m_target = (KX_GameObject*) gameobj; + + if (actuator->m_target) + actuator->m_target->RegisterActuator(actuator); + + return PY_SET_ATTR_SUCCESS; +} + +PyObject* KX_SteeringActuator::pyattr_get_navmesh(void *self, const struct KX_PYATTRIBUTE_DEF *attrdef) +{ + KX_SteeringActuator* actuator = static_cast<KX_SteeringActuator*>(self); + if (!actuator->m_navmesh) + Py_RETURN_NONE; + else + return actuator->m_navmesh->GetProxy(); +} + +int KX_SteeringActuator::pyattr_set_navmesh(void *self, const struct KX_PYATTRIBUTE_DEF *attrdef, PyObject *value) +{ + KX_SteeringActuator* actuator = static_cast<KX_SteeringActuator*>(self); + KX_GameObject *gameobj; + + if (!ConvertPythonToGameObject(value, &gameobj, true, "actuator.object = value: KX_SteeringActuator")) + return PY_SET_ATTR_FAIL; // ConvertPythonToGameObject sets the error + + if (!PyObject_TypeCheck(value, &KX_NavMeshObject::Type)) + { + PyErr_Format(PyExc_TypeError, "KX_NavMeshObject is expected"); + return PY_SET_ATTR_FAIL; + } + + if (actuator->m_navmesh != NULL) + actuator->m_navmesh->UnregisterActuator(actuator); + + actuator->m_navmesh = static_cast<KX_NavMeshObject*>(gameobj); + + if (actuator->m_navmesh) + actuator->m_navmesh->RegisterActuator(actuator); + + return PY_SET_ATTR_SUCCESS; +} + +PyObject* KX_SteeringActuator::pyattr_get_steeringVec(void *self, const struct KX_PYATTRIBUTE_DEF *attrdef) +{ + KX_SteeringActuator* actuator = static_cast<KX_SteeringActuator*>(self); + const MT_Vector3& steeringVec = actuator->GetSteeringVec(); + return PyObjectFrom(steeringVec); +} + +#endif // DISABLE_PYTHON + +/* eof */ + diff --git a/source/gameengine/Ketsji/KX_SteeringActuator.h b/source/gameengine/Ketsji/KX_SteeringActuator.h new file mode 100644 index 00000000000..4f8303107f7 --- /dev/null +++ b/source/gameengine/Ketsji/KX_SteeringActuator.h @@ -0,0 +1,130 @@ +/** +* Add steering behaviors +* +* +* $Id$ +* +* ***** BEGIN GPL LICENSE BLOCK ***** +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License +* as published by the Free Software Foundation; either version 2 +* of the License, or (at your option) any later version. The Blender +* Foundation also sells licenses for use in proprietary software under +* the Blender License. See http://www.blender.org/BL/ for information +* about this. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software Foundation, +* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +* +* The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. +* All rights reserved. +* +* The Original Code is: all of this file. +* +* Contributor(s): none yet. +* +* ***** END GPL LICENSE BLOCK ***** +*/ + +#ifndef __KX_STEERINGACTUATOR +#define __KX_STEERINGACTUATOR + +#include "SCA_IActuator.h" +#include "SCA_LogicManager.h" +#include "MT_Matrix3x3.h" + +class KX_GameObject; +class KX_NavMeshObject; +struct KX_Obstacle; +class KX_ObstacleSimulation; +const int MAX_PATH_LENGTH = 128; + +class KX_SteeringActuator : public SCA_IActuator +{ + Py_Header; + + /** Target object */ + KX_GameObject *m_target; + KX_NavMeshObject *m_navmesh; + int m_mode; + float m_distance; + float m_velocity; + float m_acceleration; + float m_turnspeed; + KX_ObstacleSimulation* m_simulation; + + KX_Obstacle* m_obstacle; + double m_updateTime; + bool m_isActive; + bool m_isSelfTerminated; + bool m_enableVisualization; + short m_facingMode; + bool m_normalUp; + float m_path[MAX_PATH_LENGTH*3]; + int m_pathLen; + int m_pathUpdatePeriod; + double m_pathUpdateTime; + int m_wayPointIdx; + MT_Matrix3x3 m_parentlocalmat; + MT_Vector3 m_steerVec; + void HandleActorFace(MT_Vector3& velocity); +public: + enum KX_STEERINGACT_MODE + { + KX_STEERING_NODEF = 0, + KX_STEERING_SEEK, + KX_STEERING_FLEE, + KX_STEERING_PATHFOLLOWING, + KX_STEERING_MAX + }; + + KX_SteeringActuator(class SCA_IObject* gameobj, + int mode, + KX_GameObject *target, + KX_GameObject *navmesh, + float distance, + float velocity, + float acceleration, + float turnspeed, + bool isSelfTerminated, + int pathUpdatePeriod, + KX_ObstacleSimulation* simulation, + short facingmode, + bool normalup, + bool enableVisualization); + virtual ~KX_SteeringActuator(); + virtual bool Update(double curtime, bool frame); + + virtual CValue* GetReplica(); + virtual void ProcessReplica(); + virtual void Relink(CTR_Map<CTR_HashedPtr, void*> *obj_map); + virtual bool UnlinkObject(SCA_IObject* clientobj); + const MT_Vector3& GetSteeringVec(); + +#ifndef DISABLE_PYTHON + + /* --------------------------------------------------------------------- */ + /* Python interface ---------------------------------------------------- */ + /* --------------------------------------------------------------------- */ + + /* These are used to get and set m_target */ + static PyObject* pyattr_get_target(void *self, const struct KX_PYATTRIBUTE_DEF *attrdef); + static int pyattr_set_target(void *self, const struct KX_PYATTRIBUTE_DEF *attrdef, PyObject *value); + static PyObject* pyattr_get_navmesh(void *self, const struct KX_PYATTRIBUTE_DEF *attrdef); + static int pyattr_set_navmesh(void *self, const struct KX_PYATTRIBUTE_DEF *attrdef, PyObject *value); + static PyObject* pyattr_get_steeringVec(void *self, const struct KX_PYATTRIBUTE_DEF *attrdef); + + +#endif // DISABLE_PYTHON + +}; /* end of class KX_SteeringActuator : public SCA_PropertyActuator */ + +#endif + diff --git a/source/gameengine/Ketsji/SConscript b/source/gameengine/Ketsji/SConscript index 08642262724..11dd0e5a4bf 100644 --- a/source/gameengine/Ketsji/SConscript +++ b/source/gameengine/Ketsji/SConscript @@ -19,6 +19,8 @@ incs += ' #source/gameengine/GameLogic #source/gameengine/Expressions #source/ga incs += ' #source/gameengine/SceneGraph #source/gameengine/Physics/common' incs += ' #source/gameengine/Physics/Dummy' incs += ' #source/blender/misc #source/blender/blenloader #extern/glew/include #source/blender/gpu' +incs += ' #extern/recastnavigation/Recast/Include #extern/recastnavigation/Detour/Include' +incs += ' #source/blender/editors/include' incs += ' ' + env['BF_BULLET_INC'] incs += ' ' + env['BF_OPENGL_INC'] diff --git a/source/gameengine/Rasterizer/RAS_IRasterizer.h b/source/gameengine/Rasterizer/RAS_IRasterizer.h index 305e2bca756..142eb88c7c7 100644 --- a/source/gameengine/Rasterizer/RAS_IRasterizer.h +++ b/source/gameengine/Rasterizer/RAS_IRasterizer.h @@ -393,7 +393,9 @@ public: virtual void SetPolygonOffset(float mult, float add) = 0; virtual void DrawDebugLine(const MT_Vector3& from,const MT_Vector3& to,const MT_Vector3& color)=0; - virtual void FlushDebugLines()=0; + virtual void DrawDebugCircle(const MT_Vector3& center, const MT_Scalar radius, const MT_Vector3& color, + const MT_Vector3& normal, int nsector)=0; + virtual void FlushDebugShapes()=0; diff --git a/source/gameengine/Rasterizer/RAS_OpenGLRasterizer/RAS_OpenGLRasterizer.cpp b/source/gameengine/Rasterizer/RAS_OpenGLRasterizer/RAS_OpenGLRasterizer.cpp index 23e0a50ed6f..59710b69fc0 100644 --- a/source/gameengine/Rasterizer/RAS_OpenGLRasterizer/RAS_OpenGLRasterizer.cpp +++ b/source/gameengine/Rasterizer/RAS_OpenGLRasterizer/RAS_OpenGLRasterizer.cpp @@ -55,6 +55,10 @@ #include "BKE_DerivedMesh.h" +#ifndef M_PI +#define M_PI 3.14159265358979323846 +#endif + /** * 32x32 bit masks for vinterlace stereo mode */ @@ -350,9 +354,9 @@ void RAS_OpenGLRasterizer::ClearCachingInfo(void) m_materialCachingInfo = 0; } -void RAS_OpenGLRasterizer::FlushDebugLines() +void RAS_OpenGLRasterizer::FlushDebugShapes() { - if(!m_debugLines.size()) + if(!m_debugShapes.size()) return; // DrawDebugLines @@ -364,29 +368,67 @@ void RAS_OpenGLRasterizer::FlushDebugLines() if(light) glDisable(GL_LIGHTING); if(tex) glDisable(GL_TEXTURE_2D); + //draw lines glBegin(GL_LINES); - for (unsigned int i=0;i<m_debugLines.size();i++) + for (unsigned int i=0;i<m_debugShapes.size();i++) { - glColor4f(m_debugLines[i].m_color[0],m_debugLines[i].m_color[1],m_debugLines[i].m_color[2],1.f); - const MT_Scalar* fromPtr = &m_debugLines[i].m_from.x(); - const MT_Scalar* toPtr= &m_debugLines[i].m_to.x(); - + if (m_debugShapes[i].m_type != OglDebugShape::LINE) + continue; + glColor4f(m_debugShapes[i].m_color[0],m_debugShapes[i].m_color[1],m_debugShapes[i].m_color[2],1.f); + const MT_Scalar* fromPtr = &m_debugShapes[i].m_pos.x(); + const MT_Scalar* toPtr= &m_debugShapes[i].m_param.x(); glVertex3dv(fromPtr); glVertex3dv(toPtr); } glEnd(); + //draw circles + for (unsigned int i=0;i<m_debugShapes.size();i++) + { + if (m_debugShapes[i].m_type != OglDebugShape::CIRCLE) + continue; + glBegin(GL_LINE_LOOP); + glColor4f(m_debugShapes[i].m_color[0],m_debugShapes[i].m_color[1],m_debugShapes[i].m_color[2],1.f); + + static const MT_Vector3 worldUp(0.,0.,1.); + MT_Vector3 norm = m_debugShapes[i].m_param; + MT_Matrix3x3 tr; + if (norm.fuzzyZero() || norm == worldUp) + { + tr.setIdentity(); + } + else + { + MT_Vector3 xaxis, yaxis; + xaxis = MT_cross(norm, worldUp); + yaxis = MT_cross(xaxis, norm); + tr.setValue(xaxis.x(), xaxis.y(), xaxis.z(), + yaxis.x(), yaxis.y(), yaxis.z(), + norm.x(), norm.y(), norm.z()); + } + MT_Scalar rad = m_debugShapes[i].m_param2.x(); + int n = (int) m_debugShapes[i].m_param2.y(); + for (int j = 0; j<n; j++) + { + MT_Scalar theta = j*M_PI*2/n; + MT_Vector3 pos(cos(theta)*rad, sin(theta)*rad, 0.); + pos = pos*tr; + pos += m_debugShapes[i].m_pos; + const MT_Scalar* posPtr = &pos.x(); + glVertex3dv(posPtr); + } + glEnd(); + } + if(light) glEnable(GL_LIGHTING); if(tex) glEnable(GL_TEXTURE_2D); - m_debugLines.clear(); + m_debugShapes.clear(); } void RAS_OpenGLRasterizer::EndFrame() { - - - FlushDebugLines(); + FlushDebugShapes(); glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE); diff --git a/source/gameengine/Rasterizer/RAS_OpenGLRasterizer/RAS_OpenGLRasterizer.h b/source/gameengine/Rasterizer/RAS_OpenGLRasterizer/RAS_OpenGLRasterizer.h index 54fab906049..a494c577512 100644 --- a/source/gameengine/Rasterizer/RAS_OpenGLRasterizer/RAS_OpenGLRasterizer.h +++ b/source/gameengine/Rasterizer/RAS_OpenGLRasterizer/RAS_OpenGLRasterizer.h @@ -49,10 +49,15 @@ using namespace std; #define RAS_MAX_TEXCO 8 // match in BL_Material #define RAS_MAX_ATTRIB 16 // match in BL_BlenderShader -struct OglDebugLine +struct OglDebugShape { - MT_Vector3 m_from; - MT_Vector3 m_to; + enum SHAPE_TYPE{ + LINE, CIRCLE + }; + SHAPE_TYPE m_type; + MT_Vector3 m_pos; + MT_Vector3 m_param; + MT_Vector3 m_param2; MT_Vector3 m_color; }; @@ -254,18 +259,32 @@ public: virtual void SetPolygonOffset(float mult, float add); - virtual void FlushDebugLines(); + virtual void FlushDebugShapes(); - virtual void DrawDebugLine(const MT_Vector3& from,const MT_Vector3& to,const MT_Vector3& color) + virtual void DrawDebugLine(const MT_Vector3& from,const MT_Vector3& to,const MT_Vector3& color) { - OglDebugLine line; - line.m_from = from; - line.m_to = to; + OglDebugShape line; + line.m_type = OglDebugShape::LINE; + line.m_pos= from; + line.m_param = to; line.m_color = color; - m_debugLines.push_back(line); + m_debugShapes.push_back(line); + } + + virtual void DrawDebugCircle(const MT_Vector3& center, const MT_Scalar radius, const MT_Vector3& color, + const MT_Vector3& normal, int nsector) + { + OglDebugShape line; + line.m_type = OglDebugShape::CIRCLE; + line.m_pos= center; + line.m_param = normal; + line.m_color = color; + line.m_param2.x() = radius; + line.m_param2.y() = (float) nsector; + m_debugShapes.push_back(line); } - std::vector <OglDebugLine> m_debugLines; + std::vector <OglDebugShape> m_debugShapes; virtual void SetTexCoordNum(int num); virtual void SetAttribNum(int num); |