BGE: merge Recast & Detour branch (sock-2010-nicks).

Add navigation mesh capability to the BGE, both by logic bricks and python.
Add tools to creation navigation mesh in the creator:
- manualy
- automatically from existing mesh with "object.create_navmesh" operator
- automatically from existing mesh with "Navigation mesh" modifier
Editing navigation mesh is possible via special modifier edit mode.
Creation and modification of Navigation mesh is also possible at runtime in the BGE.

Documentation at http://wiki.blender.org/index.php/User:Nicks/Gsoc2010/Docs

Warning: No upgrade is provided for blend files created under the branch.
         If you load a blend with navigation data created with a branch
         build, it will likely crash blender or behave incorrectly.

56 files changed, 4831 insertions, 44 deletions

diff --git a/source/blender/blenkernel/intern/customdata.c b/source/blender/blenkernel/intern/customdata.c
index c342bbc917f..883f67c3061 100644
--- a/source/blender/blenkernel/intern/customdata.c
+++ b/source/blender/blenkernel/intern/customdata.c
@@ -867,7 +867,9 @@ static const LayerTypeInfo LAYERTYPEINFO[CD_NUMTYPES] = {
 	{sizeof(MCol)*4, "MCol", 4, "TexturedCol", NULL, NULL, layerInterp_mcol,
 	 layerSwap_mcol, layerDefault_mcol},
 	/* 23: CD_CLOTH_ORCO */
-	{sizeof(float)*3, "", 0, NULL, NULL, NULL, NULL, NULL, NULL}
+	{sizeof(float)*3, "", 0, NULL, NULL, NULL, NULL, NULL, NULL},
+	/* 24: CD_RECAST */
+	{sizeof(MRecast), "MRecast", 1,"Recast",NULL,NULL,NULL,NULL}
 };
 
 static const char *LAYERTYPENAMES[CD_NUMTYPES] = {
@@ -875,7 +877,7 @@ static const char *LAYERTYPENAMES[CD_NUMTYPES] = {
 	/*   5-9 */ "CDMTFace", "CDMCol", "CDOrigIndex", "CDNormal", "CDFlags",
 	/* 10-14 */ "CDMFloatProperty", "CDMIntProperty","CDMStringProperty", "CDOrigSpace", "CDOrco",
 	/* 15-19 */ "CDMTexPoly", "CDMLoopUV", "CDMloopCol", "CDTangent", "CDMDisps",
-	/* 20-23 */"CDWeightMCol", "CDIDMCol", "CDTextureMCol", "CDClothOrco"
+	/* 20-24 */"CDWeightMCol", "CDIDMCol", "CDTextureMCol", "CDClothOrco", "CDMRecast"
 };
 
 const CustomDataMask CD_MASK_BAREMESH =
@@ -883,14 +885,14 @@ const CustomDataMask CD_MASK_BAREMESH =
 const CustomDataMask CD_MASK_MESH =
 	CD_MASK_MVERT | CD_MASK_MEDGE | CD_MASK_MFACE |
 	CD_MASK_MSTICKY | CD_MASK_MDEFORMVERT | CD_MASK_MTFACE | CD_MASK_MCOL |
-	CD_MASK_PROP_FLT | CD_MASK_PROP_INT | CD_MASK_PROP_STR | CD_MASK_MDISPS;
+	CD_MASK_PROP_FLT | CD_MASK_PROP_INT | CD_MASK_PROP_STR | CD_MASK_MDISPS | CD_MASK_RECAST;
 const CustomDataMask CD_MASK_EDITMESH =
 	CD_MASK_MSTICKY | CD_MASK_MDEFORMVERT | CD_MASK_MTFACE |
-	CD_MASK_MCOL|CD_MASK_PROP_FLT | CD_MASK_PROP_INT | CD_MASK_PROP_STR | CD_MASK_MDISPS;
+	CD_MASK_MCOL|CD_MASK_PROP_FLT | CD_MASK_PROP_INT | CD_MASK_PROP_STR | CD_MASK_MDISPS | CD_MASK_RECAST;
 const CustomDataMask CD_MASK_DERIVEDMESH =
 	CD_MASK_MSTICKY | CD_MASK_MDEFORMVERT | CD_MASK_MTFACE |
 	CD_MASK_MCOL | CD_MASK_ORIGINDEX | CD_MASK_PROP_FLT | CD_MASK_PROP_INT | CD_MASK_CLOTH_ORCO |
-	CD_MASK_PROP_STR | CD_MASK_ORIGSPACE | CD_MASK_ORCO | CD_MASK_TANGENT | CD_MASK_WEIGHT_MCOL;
+	CD_MASK_PROP_STR | CD_MASK_ORIGSPACE | CD_MASK_ORCO | CD_MASK_TANGENT | CD_MASK_WEIGHT_MCOL | CD_MASK_RECAST;
 const CustomDataMask CD_MASK_BMESH = 
 	CD_MASK_MSTICKY | CD_MASK_MDEFORMVERT | CD_MASK_PROP_FLT | CD_MASK_PROP_INT | CD_MASK_PROP_STR;
 const CustomDataMask CD_MASK_FACECORNERS =
diff --git a/source/blender/blenkernel/intern/object.c b/source/blender/blenkernel/intern/object.c
index 0dc83084c90..898cec7fa55 100644
--- a/source/blender/blenkernel/intern/object.c
+++ b/source/blender/blenkernel/intern/object.c
@@ -1082,6 +1082,7 @@ Object *add_only_object(int type, const char *name)
 	ob->state=1;
 	/* ob->pad3 == Contact Processing Threshold */
 	ob->m_contactProcessingThreshold = 1.;
+	ob->obstacleRad = 1.;
 	
 	/* NT fluid sim defaults */
 	ob->fluidsimFlag = 0;
diff --git a/source/blender/blenkernel/intern/sca.c b/source/blender/blenkernel/intern/sca.c
index 0d523599598..d529a6d94c9 100644
--- a/source/blender/blenkernel/intern/sca.c
+++ b/source/blender/blenkernel/intern/sca.c
@@ -396,6 +396,7 @@ void init_actuator(bActuator *act)
 	bObjectActuator *oa;
 	bRandomActuator *ra;
 	bSoundActuator *sa;
+	bSteeringActuator *sta;
 	
 	if(act->data) MEM_freeN(act->data);
 	act->data= NULL;
@@ -470,6 +471,16 @@ void init_actuator(bActuator *act)
 	case ACT_ARMATURE:
 		act->data = MEM_callocN(sizeof( bArmatureActuator ), "armature act");
 		break;
+	case ACT_STEERING:
+		act->data = MEM_callocN(sizeof( bSteeringActuator), "steering act");
+		sta = act->data;
+		sta->acceleration = 3.f;
+		sta->turnspeed = 120.f;
+		sta->dist = 1.f;
+		sta->velocity= 3.f;
+		sta->flag = ACT_STEERING_AUTOMATICFACING;
+		sta->facingaxis = 1;
+		break;
 	default:
 		; /* this is very severe... I cannot make any memory for this        */
 		/* logic brick...                                                    */
@@ -595,6 +606,11 @@ void set_sca_new_poins_ob(Object *ob)
 				bPropertyActuator *pa= act->data;
 				ID_NEW(pa->ob);
 			}
+			else if(act->type==ACT_STEERING) {
+				bSteeringActuator *sta = act->data;
+				ID_NEW(sta->navmesh);
+				ID_NEW(sta->target);
+			}
 		}
 		act= act->next;
 	}
diff --git a/source/blender/blenkernel/intern/scene.c b/source/blender/blenkernel/intern/scene.c
index d6003a44a7d..1454b3f0ce3 100644
--- a/source/blender/blenkernel/intern/scene.c
+++ b/source/blender/blenkernel/intern/scene.c
@@ -514,6 +514,23 @@ Scene *add_scene(const char *name)
 	sce->gm.flag = GAME_DISPLAY_LISTS;
 	sce->gm.matmode = GAME_MAT_MULTITEX;
 
+	sce->gm.obstacleSimulation= OBSTSIMULATION_NONE;
+	sce->gm.levelHeight = 2.f;
+
+	sce->gm.recastData.cellsize = 0.3f;
+	sce->gm.recastData.cellheight = 0.2f;
+	sce->gm.recastData.agentmaxslope = M_PI/2;
+	sce->gm.recastData.agentmaxclimb = 0.9f;
+	sce->gm.recastData.agentheight = 2.0f;
+	sce->gm.recastData.agentradius = 0.6f;
+	sce->gm.recastData.edgemaxlen = 12.0f;
+	sce->gm.recastData.edgemaxerror = 1.3f;
+	sce->gm.recastData.regionminsize = 50.f;
+	sce->gm.recastData.regionmergesize = 20.f;
+	sce->gm.recastData.vertsperpoly = 6;
+	sce->gm.recastData.detailsampledist = 6.0f;
+	sce->gm.recastData.detailsamplemaxerror = 1.0f;
+
 	sound_create_scene(sce);
 
 	return sce;
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index eb5d6a6fbcb..316999df6f6 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -3896,6 +3896,11 @@ static void lib_link_object(FileData *fd, Main *main)
 					arma->target= newlibadr(fd, ob->id.lib, arma->target);
 					arma->subtarget= newlibadr(fd, ob->id.lib, arma->subtarget);
 				}
+				else if(act->type==ACT_STEERING) {
+					bSteeringActuator *steeringa = act->data; 
+					steeringa->target = newlibadr(fd, ob->id.lib, steeringa->target);
+					steeringa->navmesh = newlibadr(fd, ob->id.lib, steeringa->navmesh);
+				}
 				act= act->next;
 			}
 			
@@ -11615,6 +11620,23 @@ static void do_versions(FileData *fd, Library *lib, Main *main)
 		}
 	}
 	
+	// init facing axis property of steering actuators
+	{					
+		Object *ob;
+		for(ob = main->object.first; ob; ob = ob->id.next) {
+			bActuator *act;
+			for(act= ob->actuators.first; act; act= act->next) {
+				if(act->type==ACT_STEERING) {
+					bSteeringActuator* stact = act->data;
+					if (stact->facingaxis==0)
+					{
+						stact->facingaxis=1;
+					}						
+				}
+			}
+		}
+	}
+	
 	if (main->versionfile < 256) {
 		bScreen *sc;
 		ScrArea *sa;
@@ -12018,6 +12040,43 @@ static void do_versions(FileData *fd, Library *lib, Main *main)
 
 	}
 
+	//set defaults for obstacle avoidance, recast data
+	{
+		Scene *sce;
+		for(sce = main->scene.first; sce; sce = sce->id.next)
+		{
+			if (sce->gm.levelHeight == 0.f)
+				sce->gm.levelHeight = 2.f;
+
+			if(sce->gm.recastData.cellsize == 0.0f)
+				sce->gm.recastData.cellsize = 0.3f;
+			if(sce->gm.recastData.cellheight == 0.0f)
+				sce->gm.recastData.cellheight = 0.2f;
+			if(sce->gm.recastData.agentmaxslope == 0.0f)
+				sce->gm.recastData.agentmaxslope = M_PI/4;
+			if(sce->gm.recastData.agentmaxclimb == 0.0f)
+				sce->gm.recastData.agentmaxclimb = 0.9f;
+			if(sce->gm.recastData.agentheight == 0.0f)
+				sce->gm.recastData.agentheight = 2.0f;
+			if(sce->gm.recastData.agentradius == 0.0f)
+				sce->gm.recastData.agentradius = 0.6f;
+			if(sce->gm.recastData.edgemaxlen == 0.0f)
+				sce->gm.recastData.edgemaxlen = 12.0f;
+			if(sce->gm.recastData.edgemaxerror == 0.0f)
+				sce->gm.recastData.edgemaxerror = 1.3f;
+			if(sce->gm.recastData.regionminsize == 0.0f)
+				sce->gm.recastData.regionminsize = 50.f;
+			if(sce->gm.recastData.regionmergesize == 0.0f)
+				sce->gm.recastData.regionmergesize = 20.f;
+			if(sce->gm.recastData.vertsperpoly<3)
+				sce->gm.recastData.vertsperpoly = 6;
+			if(sce->gm.recastData.detailsampledist == 0.0f)
+				sce->gm.recastData.detailsampledist = 6.0f;
+			if(sce->gm.recastData.detailsamplemaxerror == 0.0f)
+				sce->gm.recastData.detailsamplemaxerror = 1.0f;
+		}			
+	}
+	
 	/* WATCH IT!!!: pointers from libdata have not been converted yet here! */
 	/* WATCH IT 2!: Userdef struct init has to be in editors/interface/resources.c! */
 
@@ -12922,6 +12981,11 @@ static void expand_object(FileData *fd, Main *mainvar, Object *ob)
 			bArmatureActuator *arma= act->data;
 			expand_doit(fd, mainvar, arma->target);
 		}
+		else if(act->type==ACT_STEERING) {
+			bSteeringActuator *sta= act->data;
+			expand_doit(fd, mainvar, sta->target);
+			expand_doit(fd, mainvar, sta->navmesh);
+		}
 		act= act->next;
 	}
 
diff --git a/source/blender/blenloader/intern/writefile.c b/source/blender/blenloader/intern/writefile.c
index 3b736e8aeae..e92ec5dbe6e 100644
--- a/source/blender/blenloader/intern/writefile.c
+++ b/source/blender/blenloader/intern/writefile.c
@@ -1146,6 +1146,9 @@ static void write_actuators(WriteData *wd, ListBase *lb)
 		case ACT_ARMATURE:
 			writestruct(wd, DATA, "bArmatureActuator", 1, act->data);
 			break;
+		case ACT_STEERING:
+			writestruct(wd, DATA, "bSteeringActuator", 1, act->data);
+			break;
 		default:
 			; /* error: don't know how to write this file */
 		}
diff --git a/source/blender/editors/include/ED_navmesh_conversion.h b/source/blender/editors/include/ED_navmesh_conversion.h
new file mode 100644
index 00000000000..28922142f5c
--- /dev/null
+++ b/source/blender/editors/include/ED_navmesh_conversion.h
@@ -0,0 +1,96 @@
+/**
+* $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 NAVMESH_CONVERSION_H
+#define NAVMESH_CONVERSION_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct DerivedMesh;
+
+/* navmesh_conversion.cpp */
+bool buildNavMeshDataByDerivedMesh(DerivedMesh *dm, int& vertsPerPoly, 
+								   int &nverts, float *&verts,
+								   int &ndtris, unsigned short *&dtris,
+								   int& npolys, unsigned short *&dmeshes,
+								   unsigned short*& polys, int *&dtrisToPolysMap,
+								   int *&dtrisToTrisMap, int *&trisToFacesMap);
+
+bool buildRawVertIndicesData(DerivedMesh* dm, int &nverts, float *&verts, 
+				int &ntris, unsigned short *&tris, int *&trisToFacesMap,
+				int *&recastData);
+
+bool buildNavMeshData(const int nverts, const float* verts, 
+					  const int ntris, const unsigned short *tris, 
+					  const int* recastData, const int* trisToFacesMap,
+					  int &ndtris, unsigned short *&dtris,
+					  int &npolys, unsigned short *&dmeshes, unsigned short *&polys,
+					  int &vertsPerPoly, int *&dtrisToPolysMap, int *&dtrisToTrisMap);
+
+bool buildPolygonsByDetailedMeshes(const int vertsPerPoly, const int npolys, 
+				unsigned short* polys, const unsigned short* dmeshes, 
+				const float* verts, const unsigned short* dtris, 
+				const int* dtrisToPolysMap);
+
+int polyNumVerts(const unsigned short* p, const int vertsPerPoly);
+bool polyIsConvex(const unsigned short* p, const int vertsPerPoly, const float* verts);
+int polyFindVertex(const unsigned short* p, const int vertsPerPoly, unsigned short vertexIdx);
+float distPointToSegmentSq(const float* point, const float* a, const float* b);
+
+
+inline int bit(int a, int b)
+{
+	return (a & (1 << b)) >> b;
+}
+
+inline void intToCol(int i, float* col)
+{
+	int	r = bit(i, 0) + bit(i, 3) * 2 + 1;
+	int	g = bit(i, 1) + bit(i, 4) * 2 + 1;
+	int	b = bit(i, 2) + bit(i, 5) * 2 + 1;
+	col[0] = 1 - r*63.0f/255.0f;
+	col[1] = 1 - g*63.0f/255.0f;
+	col[2] = 1 - b*63.0f/255.0f;
+}
+
+inline float area2(const float* a, const float* b, const float* c)
+{
+	return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]);
+}
+inline bool left(const float* a, const float* b, const float* c)
+{
+	return area2(a, b, c) < 0;
+}
+
+#ifdef __cplusplus
+}
+#endif
+#endif //NAVMESH_CONVERSION_H
\ No newline at end of file
diff --git a/source/blender/editors/object/CMakeLists.txt b/source/blender/editors/object/CMakeLists.txt
index 14b40d55f11..de74a0321c7 100644
--- a/source/blender/editors/object/CMakeLists.txt
+++ b/source/blender/editors/object/CMakeLists.txt
@@ -33,6 +33,7 @@ set(INC
 	../../render/extern/include
 	../../windowmanager
 	../../../../intern/guardedalloc
+	../../../../extern/recastnavigation/Recast/Include
 )
 
 set(INC_SYS
@@ -48,6 +49,7 @@ set(SRC
 	object_hook.c
 	object_lattice.c
 	object_modifier.c
+	object_navmesh.cpp
 	object_ops.c
 	object_relations.c
 	object_select.c
diff --git a/source/blender/editors/object/SConscript b/source/blender/editors/object/SConscript
index ca048cb59f9..900c96044a5 100644
--- a/source/blender/editors/object/SConscript
+++ b/source/blender/editors/object/SConscript
@@ -1,12 +1,13 @@
 #!/usr/bin/python
 Import ('env')
 
-sources = env.Glob('*.c')
+sources = env.Glob('*.c') + env.Glob('*.cpp')
 
 incs = '../include ../../blenlib ../../blenkernel ../../makesdna ../../imbuf'
 incs += ' ../../windowmanager #/intern/guardedalloc ../../blenloader'
 incs += ' ../../makesrna ../../python ../../ikplugin'
 incs += ' ../../render/extern/include ../../gpu' # for object_bake.c
+incs += ' #extern/recastnavigation/Recast/Include'
 
 defs = []
 
diff --git a/source/blender/editors/object/object_intern.h b/source/blender/editors/object/object_intern.h
index c308d36f838..3da0723ec18 100644
--- a/source/blender/editors/object/object_intern.h
+++ b/source/blender/editors/object/object_intern.h
@@ -223,5 +223,10 @@ void OBJECT_OT_group_remove(struct wmOperatorType *ot);
 /* object_bake.c */
 void OBJECT_OT_bake_image(wmOperatorType *ot);
 
+/* object_navmesh.cpp */
+void OBJECT_OT_create_navmesh(struct wmOperatorType *ot);
+void OBJECT_OT_assign_navpolygon(struct wmOperatorType *ot);
+void OBJECT_OT_assign_new_navpolygon(struct wmOperatorType *ot);
+
 #endif /* ED_OBJECT_INTERN_H */
 
diff --git a/source/blender/editors/object/object_navmesh.cpp b/source/blender/editors/object/object_navmesh.cpp
new file mode 100644
index 00000000000..8ee63296c70
--- /dev/null
+++ b/source/blender/editors/object/object_navmesh.cpp
@@ -0,0 +1,629 @@
+/**
+* $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) 2004 by Blender Foundation
+* All rights reserved.
+*
+* The Original Code is: all of this file.
+*
+* Contributor(s): none yet.
+*
+* ***** END GPL LICENSE BLOCK *****
+*/
+
+#include <math.h>
+#include "Recast.h"
+
+extern "C"
+{
+#include "MEM_guardedalloc.h"
+
+#include "DNA_scene_types.h"
+#include "DNA_object_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_modifier_types.h"
+#include "DNA_ID.h"
+
+#include "BKE_library.h"
+#include "BKE_depsgraph.h"
+#include "BKE_context.h"
+#include "BKE_mesh.h"
+#include "BKE_modifier.h"
+#include "BKE_scene.h"
+#include "BKE_DerivedMesh.h"
+#include "BKE_cdderivedmesh.h"
+#include "BLI_editVert.h"
+#include "BLI_listbase.h"
+#include "BLI_utildefines.h"
+#include "ED_object.h"
+#include "BLI_math_vector.h"
+
+#include "RNA_access.h"
+
+#include "ED_mesh.h"
+
+/*mesh/mesh_intern.h */
+extern struct EditVert *addvertlist(EditMesh *em, float *vec, struct EditVert *example);
+extern struct EditFace *addfacelist(EditMesh *em, struct EditVert *v1, struct EditVert *v2, struct EditVert *v3, struct EditVert *v4, struct EditFace *example, struct EditFace *exampleEdges);
+extern void free_vertlist(EditMesh *em, ListBase *edve);
+extern void free_edgelist(EditMesh *em, ListBase *lb);
+extern void free_facelist(EditMesh *em, ListBase *lb);
+
+#include "WM_api.h"
+#include "WM_types.h"
+
+static void createVertsTrisData(bContext *C, LinkNode* obs, int& nverts, float*& verts, int &ntris, int*& tris)
+{
+	MVert *mvert;
+	int nfaces = 0, *tri, i, curnverts, basenverts, curnfaces;
+	MFace *mface;
+	float co[3], wco[3];
+	Object *ob;
+	LinkNode *oblink, *dmlink;
+	DerivedMesh *dm;
+	Scene* scene = CTX_data_scene(C);
+	LinkNode* dms = NULL;
+
+	nverts = 0;
+	ntris = 0;
+	//calculate number of verts and tris
+	for (oblink = obs; oblink; oblink = oblink->next) 
+	{
+		ob = (Object*) oblink->link;	
+		DerivedMesh *dm = mesh_create_derived_no_virtual(scene, ob, NULL, CD_MASK_MESH);
+		BLI_linklist_append(&dms, (void*)dm);
+
+		nverts += dm->getNumVerts(dm);
+		nfaces = dm->getNumFaces(dm);
+		ntris += nfaces;
+
+		//resolve quad faces
+		mface = dm->getFaceArray(dm);
+		for (i=0; i<nfaces; i++)
+		{
+			MFace* mf = &mface[i];
+			if (mf->v4)
+				ntris+=1;
+		}
+	}
+
+	//create data
+	verts = (float*) MEM_mallocN(sizeof(float)*3*nverts, "verts");
+	tris = (int*) MEM_mallocN(sizeof(int)*3*ntris, "faces");
+
+	basenverts = 0;
+	tri = tris;
+	for (oblink = obs, dmlink = dms; oblink && dmlink; 
+			oblink = oblink->next, dmlink = dmlink->next)
+	{
+		ob = (Object*) oblink->link;
+		dm = (DerivedMesh*) dmlink->link;
+
+		curnverts = dm->getNumVerts(dm);
+		mvert = dm->getVertArray(dm);
+		//copy verts	
+		for (i=0; i<curnverts; i++)
+		{
+			MVert *v = &mvert[i];
+			copy_v3_v3(co, v->co);
+			mul_v3_m4v3(wco, ob->obmat, co);
+			verts[3*(basenverts+i)+0] = wco[0];
+			verts[3*(basenverts+i)+1] = wco[2];
+			verts[3*(basenverts+i)+2] = wco[1];
+		}
+
+		//create tris
+		curnfaces = dm->getNumFaces(dm);
+		mface = dm->getFaceArray(dm);
+		for (i=0; i<curnfaces; i++)
+		{
+			MFace* mf = &mface[i]; 
+			tri[0]= basenverts + mf->v1; tri[1]= basenverts + mf->v3;	tri[2]= basenverts + mf->v2; 
+			tri += 3;
+			if (mf->v4)
+			{
+				tri[0]= basenverts + mf->v1; tri[1]= basenverts + mf->v4; tri[2]= basenverts + mf->v3; 
+				tri += 3;
+			}
+		}
+		basenverts += curnverts;
+	}
+
+	//release derived mesh
+	for (dmlink = dms; dmlink; dmlink = dmlink->next)
+	{
+		dm = (DerivedMesh*) dmlink->link;
+		dm->release(dm);
+	}
+	BLI_linklist_free(dms, NULL);
+}
+
+static bool buildNavMesh(const RecastData& recastParams, int nverts, float* verts, int ntris, int* tris,
+								 rcPolyMesh*& pmesh, rcPolyMeshDetail*& dmesh)
+{
+	float bmin[3], bmax[3];
+	rcHeightfield* solid;
+	unsigned char *triflags;
+	rcCompactHeightfield* chf;
+	rcContourSet *cset;
+
+	rcCalcBounds(verts, nverts, bmin, bmax);
+
+	//
+	// Step 1. Initialize build config.
+	//
+	rcConfig cfg;
+	memset(&cfg, 0, sizeof(cfg));
+	{
+/*
+		float cellsize = 0.3f;
+		float cellheight = 0.2f;
+		float agentmaxslope = M_PI/4;
+		float agentmaxclimb = 0.9f;
+		float agentheight = 2.0f;
+		float agentradius = 0.6f;
+		float edgemaxlen = 12.0f;
+		float edgemaxerror = 1.3f;
+		float regionminsize = 50.f;
+		float regionmergesize = 20.f;
+		int vertsperpoly = 6;
+		float detailsampledist = 6.0f;
+		float detailsamplemaxerror = 1.0f;
+		cfg.cs = cellsize;
+		cfg.ch = cellheight;
+		cfg.walkableSlopeAngle = agentmaxslope/M_PI*180.f;
+		cfg.walkableHeight = (int)ceilf(agentheight/ cfg.ch);
+		cfg.walkableClimb = (int)floorf(agentmaxclimb / cfg.ch);
+		cfg.walkableRadius = (int)ceilf(agentradius / cfg.cs);
+		cfg.maxEdgeLen = (int)(edgemaxlen/cellsize);
+		cfg.maxSimplificationError = edgemaxerror;
+		cfg.minRegionSize = (int)rcSqr(regionminsize);
+		cfg.mergeRegionSize = (int)rcSqr(regionmergesize);
+		cfg.maxVertsPerPoly = vertsperpoly;
+		cfg.detailSampleDist = detailsampledist< 0.9f ? 0 : cellsize * detailsampledist;
+		cfg.detailSampleMaxError = cellheight * detailsamplemaxerror;
+*/
+		cfg.cs = recastParams.cellsize;
+		cfg.ch = recastParams.cellheight;
+		cfg.walkableSlopeAngle = recastParams.agentmaxslope/((float)M_PI)*180.f;
+		cfg.walkableHeight = (int)ceilf(recastParams.agentheight/ cfg.ch);
+		cfg.walkableClimb = (int)floorf(recastParams.agentmaxclimb / cfg.ch);
+		cfg.walkableRadius = (int)ceilf(recastParams.agentradius / cfg.cs);
+		cfg.maxEdgeLen = (int)(recastParams.edgemaxlen/recastParams.cellsize);
+		cfg.maxSimplificationError = recastParams.edgemaxerror;
+		cfg.minRegionSize = (int)rcSqr(recastParams.regionminsize);
+		cfg.mergeRegionSize = (int)rcSqr(recastParams.regionmergesize);
+		cfg.maxVertsPerPoly = recastParams.vertsperpoly;
+		cfg.detailSampleDist = recastParams.detailsampledist< 0.9f ? 0 : 
+								recastParams.cellsize * recastParams.detailsampledist;
+		cfg.detailSampleMaxError = recastParams.cellheight * recastParams.detailsamplemaxerror;
+
+	}
+
+	// Set the area where the navigation will be build.
+	vcopy(cfg.bmin, bmin);
+	vcopy(cfg.bmax, bmax);
+	rcCalcGridSize(cfg.bmin, cfg.bmax, cfg.cs, &cfg.width, &cfg.height);
+
+	//
+	// Step 2. Rasterize input polygon soup.
+	//
+	// Allocate voxel heightfield where we rasterize our input data to.
+	solid = new rcHeightfield;
+	if (!solid)
+		return false;
+
+	if (!rcCreateHeightfield(*solid, cfg.width, cfg.height, cfg.bmin, cfg.bmax, cfg.cs, cfg.ch))
+		return false;
+
+	// Allocate array that can hold triangle flags.
+	triflags = (unsigned char*) MEM_mallocN(sizeof(unsigned char)*ntris, "triflags");
+	if (!triflags)
+		return false;
+	// Find triangles which are walkable based on their slope and rasterize them.
+	memset(triflags, 0, ntris*sizeof(unsigned char));
+	rcMarkWalkableTriangles(cfg.walkableSlopeAngle, verts, nverts, tris, ntris, triflags);
+	rcRasterizeTriangles(verts, nverts, tris, triflags, ntris, *solid);
+	MEM_freeN(triflags);
+	MEM_freeN(verts);
+	MEM_freeN(tris);
+
+	//
+	// Step 3. Filter walkables surfaces.
+	//
+	rcFilterLedgeSpans(cfg.walkableHeight, cfg.walkableClimb, *solid);
+	rcFilterWalkableLowHeightSpans(cfg.walkableHeight, *solid);
+
+	//
+	// Step 4. Partition walkable surface to simple regions.
+	//
+
+	chf = new rcCompactHeightfield;
+	if (!chf)
+		return false;
+	if (!rcBuildCompactHeightfield(cfg.walkableHeight, cfg.walkableClimb, RC_WALKABLE, *solid, *chf))
+		return false;
+
+	delete solid; 
+
+	// Prepare for region partitioning, by calculating distance field along the walkable surface.
+	if (!rcBuildDistanceField(*chf))
+		return false;
+
+	// Partition the walkable surface into simple regions without holes.
+	if (!rcBuildRegions(*chf, cfg.walkableRadius, cfg.borderSize, cfg.minRegionSize, cfg.mergeRegionSize))
+		return false;
+
+	//
+	// Step 5. Trace and simplify region contours.
+	//
+	// Create contours.
+	cset = new rcContourSet;
+	if (!cset)
+		return false;
+
+	if (!rcBuildContours(*chf, cfg.maxSimplificationError, cfg.maxEdgeLen, *cset))
+		return false;
+
+	//
+	// Step 6. Build polygons mesh from contours.
+	//
+	pmesh = new rcPolyMesh;
+	if (!pmesh)
+		return false;
+	if (!rcBuildPolyMesh(*cset, cfg.maxVertsPerPoly, *pmesh))
+		return false;
+
+
+	//
+	// Step 7. Create detail mesh which allows to access approximate height on each polygon.
+	//
+
+	dmesh = new rcPolyMeshDetail;
+	if (!dmesh)
+		return false;
+
+	if (!rcBuildPolyMeshDetail(*pmesh, *chf, cfg.detailSampleDist, cfg.detailSampleMaxError, *dmesh))
+		return false;
+
+	delete chf;
+	delete cset;
+
+	return true;
+}
+
+static Object* createRepresentation(bContext *C, rcPolyMesh*& pmesh, rcPolyMeshDetail*& dmesh, Base* base)
+{
+	float co[3], rot[3];
+	EditMesh *em;
+	int i,j, k, polyverts;
+	unsigned short* v;
+	int face[3];
+	Main *bmain = CTX_data_main(C);
+	Scene *scene= CTX_data_scene(C);
+	Object* obedit;
+	int createob = base==NULL;
+	zero_v3(co);
+	zero_v3(rot);
+	if (createob)
+	{
+		//create new object
+		obedit = ED_object_add_type(C, OB_MESH, co, rot, FALSE, 1);
+	}
+	else
+	{
+		obedit = base->object;
+		scene_select_base(scene, base);
+		copy_v3_v3(obedit->loc, co);
+		copy_v3_v3(obedit->rot, rot);
+	}
+
+	ED_object_enter_editmode(C, EM_DO_UNDO|EM_IGNORE_LAYER);
+	em = BKE_mesh_get_editmesh(((Mesh *)obedit->data));
+
+	if (!createob)
+	{
+		//clear
+		if(em->verts.first) free_vertlist(em, &em->verts);
+		if(em->edges.first) free_edgelist(em, &em->edges);
+		if(em->faces.first) free_facelist(em, &em->faces);
+		if(em->selected.first) BLI_freelistN(&(em->selected));
+	}
+
+	//create verts for polygon mesh
+	for(i = 0; i < pmesh->nverts; i++) {
+		v = &pmesh->verts[3*i];
+		co[0] = pmesh->bmin[0] + v[0]*pmesh->cs;
+		co[1] = pmesh->bmin[1] + v[1]*pmesh->ch;
+		co[2] = pmesh->bmin[2] + v[2]*pmesh->cs;
+		SWAP(float, co[1], co[2]);
+		addvertlist(em, co, NULL);
+	}
+	polyverts = pmesh->nverts;
+
+	//create custom data layer to save polygon idx
+	CustomData_add_layer_named(&em->fdata, CD_RECAST, CD_CALLOC, NULL, 0, "recastData");
+
+	//create verts and faces for detailed mesh
+	for (i=0; i<dmesh->nmeshes; i++)
+	{
+		int uniquevbase = em->totvert;
+		unsigned short vbase = dmesh->meshes[4*i+0];
+		unsigned short ndv = dmesh->meshes[4*i+1];
+		unsigned short tribase = dmesh->meshes[4*i+2];
+		unsigned short trinum = dmesh->meshes[4*i+3];
+		const unsigned short* p = &pmesh->polys[i*pmesh->nvp*2];
+		int nv = 0;
+		for (j = 0; j < pmesh->nvp; ++j)
+		{
+			if (p[j] == 0xffff) break;
+			nv++;
+		}
+		//create unique verts 
+		for (j=nv; j<ndv; j++)
+		{
+			copy_v3_v3(co, &dmesh->verts[3*(vbase + j)]);
+			SWAP(float, co[1], co[2]);
+			addvertlist(em, co, NULL);
+		}
+
+		EM_init_index_arrays(em, 1, 0, 0);
+		
+		//create faces
+		for (j=0; j<trinum; j++)
+		{
+			unsigned char* tri = &dmesh->tris[4*(tribase+j)];
+			EditFace* newFace;
+			for (k=0; k<3; k++)
+			{
+				if (tri[k]<nv)
+					face[k] = p[tri[k]]; //shared vertex
+				else
+					face[k] = uniquevbase+tri[k]-nv; //unique vertex
+			}
+			newFace = addfacelist(em, EM_get_vert_for_index(face[0]), EM_get_vert_for_index(face[2]), 
+									EM_get_vert_for_index(face[1]), NULL, NULL, NULL);
+
+			//set navigation polygon idx to the custom layer
+			int* polygonIdx = (int*)CustomData_em_get(&em->fdata, newFace->data, CD_RECAST);
+			*polygonIdx = i+1; //add 1 to avoid zero idx
+		}
+		
+		EM_free_index_arrays();
+	}
+
+	delete pmesh; pmesh = NULL;
+	delete dmesh; dmesh = NULL;
+
+	BKE_mesh_end_editmesh((Mesh*)obedit->data, em);
+	
+	DAG_id_tag_update((ID*)obedit->data, OB_RECALC_DATA);
+	WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
+
+
+	ED_object_exit_editmode(C, EM_FREEDATA); 
+	WM_event_add_notifier(C, NC_OBJECT|ND_DRAW, obedit);
+
+	if (createob)
+	{
+		obedit->gameflag &= ~OB_COLLISION;
+		obedit->gameflag |= OB_NAVMESH;
+		obedit->body_type = OB_BODY_TYPE_NAVMESH;
+		rename_id((ID *)obedit, "Navmesh");
+	}
+	
+	ModifierData *md= modifiers_findByType(obedit, eModifierType_NavMesh);
+	if (!md)
+	{
+		ED_object_modifier_add(NULL, bmain, scene, obedit, NULL, eModifierType_NavMesh);
+	}
+
+	return obedit;
+}
+
+static int create_navmesh_exec(bContext *C, wmOperator *op)
+{
+	Scene* scene = CTX_data_scene(C);
+	int nverts, ntris;
+	float* verts;
+	int* tris;
+	rcPolyMesh* pmesh;
+	rcPolyMeshDetail* dmesh;
+	LinkNode* obs = NULL;
+	Base* navmeshBase = NULL;
+	//CTX_DATA_BEGIN(C, Base*, base, selected_editable_bases) //expand macros to avoid error in convertion from void*
+	{
+		ListBase ctx_data_list;
+		CollectionPointerLink *ctx_link;
+		CTX_data_selected_editable_bases(C, &ctx_data_list);
+		for(ctx_link = (CollectionPointerLink *)ctx_data_list.first; 
+				ctx_link; ctx_link = (CollectionPointerLink *)ctx_link->next) {
+		Base* base= (Base*)ctx_link->ptr.data;
+	{
+		if (base->object->body_type==OB_BODY_TYPE_NAVMESH)
+		{
+			if (!navmeshBase || base==CTX_data_active_base(C))
+				navmeshBase = base;
+		}
+		else
+			BLI_linklist_append(&obs, (void*)base->object);
+	}
+	CTX_DATA_END;
+	createVertsTrisData(C, obs, nverts, verts, ntris, tris);
+	BLI_linklist_free(obs, NULL);
+	buildNavMesh(scene->gm.recastData, nverts, verts, ntris, tris, pmesh, dmesh);
+	createRepresentation(C, pmesh, dmesh, navmeshBase);
+
+	return OPERATOR_FINISHED;
+}
+
+void OBJECT_OT_create_navmesh(wmOperatorType *ot)
+{
+	/* identifiers */
+	ot->name= "Create navigation mesh";
+	ot->description= "Create navigation mesh for selected objects";
+	ot->idname= "OBJECT_OT_create_navmesh";
+
+	/* api callbacks */
+	ot->exec= create_navmesh_exec;
+
+	/* flags */
+	ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
+}
+
+static int assign_navpolygon_poll(bContext *C)
+{
+	Object *ob= (Object *)CTX_data_pointer_get_type(C, "object", &RNA_Object).data;
+	if (!ob || !ob->data)
+		return 0;
+	return (((Mesh*)ob->data)->edit_mesh != NULL);
+}
+
+static int assign_navpolygon_exec(bContext *C, wmOperator *op)
+{
+	Object *obedit= CTX_data_edit_object(C);
+	EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
+
+	//do work here
+	int targetPolyIdx = -1;
+	EditFace *ef, *efa;
+	efa = EM_get_actFace(em, 0);
+	if (efa) 
+	{
+		if (CustomData_has_layer(&em->fdata, CD_RECAST))
+		{
+			targetPolyIdx = *(int*)CustomData_em_get(&em->fdata, efa->data, CD_RECAST);
+			targetPolyIdx = targetPolyIdx>=0? targetPolyIdx : -targetPolyIdx;
+			if (targetPolyIdx>0)
+			{
+				//set target poly idx to other selected faces
+				ef = (EditFace*)em->faces.last;
+				while(ef) 
+				{
+					if((ef->f & SELECT )&& ef!=efa) 
+					{
+						int* recastDataBlock = (int*)CustomData_em_get(&em->fdata, ef->data, CD_RECAST);
+						*recastDataBlock = targetPolyIdx;
+					}
+					ef = ef->prev;
+				}
+			}
+		}		
+	}
+	
+	DAG_id_tag_update((ID*)obedit->data, OB_RECALC_DATA);
+	WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
+
+	BKE_mesh_end_editmesh((Mesh*)obedit->data, em);
+	return OPERATOR_FINISHED;
+}
+
+void OBJECT_OT_assign_navpolygon(struct wmOperatorType *ot)
+{
+	/* identifiers */
+	ot->name= "Assign polygon index ";
+	ot->description= "Assign polygon index to face by active face";
+	ot->idname= "OBJECT_OT_assign_navpolygon";
+
+	/* api callbacks */
+	ot->poll = assign_navpolygon_poll;
+	ot->exec= assign_navpolygon_exec;
+
+	/* flags */
+	ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
+}
+
+static int compare(const void * a, const void * b){  
+	return ( *(int*)a - *(int*)b );
+}
+static int findFreeNavPolyIndex(EditMesh* em)
+{
+	//construct vector of indices
+	int numfaces = em->totface;
+	int* indices = new int[numfaces];
+	EditFace* ef = (EditFace*)em->faces.last;
+	int idx = 0;
+	while(ef) 
+	{
+		int polyIdx = *(int*)CustomData_em_get(&em->fdata, ef->data, CD_RECAST);
+		indices[idx] = polyIdx;
+		idx++;
+		ef = ef->prev;
+	}
+	qsort(indices, numfaces, sizeof(int), compare);
+	//search first free index
+	int freeIdx = 1;
+	for (int i=0; i<numfaces; i++)
+	{
+		if (indices[i]==freeIdx)
+			freeIdx++;
+		else if (indices[i]>freeIdx)
+			break;
+	}
+	delete indices;
+	return freeIdx;
+}
+
+static int assign_new_navpolygon_exec(bContext *C, wmOperator *op)
+{
+	Object *obedit= CTX_data_edit_object(C);
+	EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
+
+	EditFace *ef;
+	if (CustomData_has_layer(&em->fdata, CD_RECAST))
+	{
+		int targetPolyIdx = findFreeNavPolyIndex(em);
+		if (targetPolyIdx>0)
+		{
+			//set target poly idx to selected faces
+			ef = (EditFace*)em->faces.last;
+			while(ef) 
+			{
+				if(ef->f & SELECT ) 
+				{
+					int* recastDataBlock = (int*)CustomData_em_get(&em->fdata, ef->data, CD_RECAST);
+					*recastDataBlock = targetPolyIdx;
+				}
+				ef = ef->prev;
+			}
+		}
+	}		
+
+	DAG_id_tag_update((ID*)obedit->data, OB_RECALC_DATA);
+	WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
+
+	BKE_mesh_end_editmesh((Mesh*)obedit->data, em);
+	return OPERATOR_FINISHED;
+}
+
+void OBJECT_OT_assign_new_navpolygon(struct wmOperatorType *ot)
+{
+	/* identifiers */
+	ot->name= "Assign new polygon index ";
+	ot->description= "Assign new polygon index to face";
+	ot->idname= "OBJECT_OT_assign_new_navpolygon";
+
+	/* api callbacks */
+	ot->poll = assign_navpolygon_poll;
+	ot->exec= assign_new_navpolygon_exec;
+
+	/* flags */
+	ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
+}
+}
diff --git a/source/blender/editors/object/object_ops.c b/source/blender/editors/object/object_ops.c
index 8f00f923b84..29d536c1dab 100644
--- a/source/blender/editors/object/object_ops.c
+++ b/source/blender/editors/object/object_ops.c
@@ -212,6 +212,10 @@ void ED_operatortypes_object(void)
 
 	WM_operatortype_append(OBJECT_OT_bake_image);
 	WM_operatortype_append(OBJECT_OT_drop_named_material);
+
+	WM_operatortype_append(OBJECT_OT_create_navmesh);
+	WM_operatortype_append(OBJECT_OT_assign_navpolygon);
+	WM_operatortype_append(OBJECT_OT_assign_new_navpolygon);
 }
 
 void ED_operatormacros_object(void)
diff --git a/source/blender/editors/space_logic/logic_window.c b/source/blender/editors/space_logic/logic_window.c
index 20b001965aa..43a8747e942 100644
--- a/source/blender/editors/space_logic/logic_window.c
+++ b/source/blender/editors/space_logic/logic_window.c
@@ -718,6 +718,8 @@ static const char *actuator_name(int type)
 		return "State";
 	case ACT_ARMATURE:
 		return "Armature";
+	case ACT_STEERING:
+		return "Steering";		
 	}
 	return "unknown";
 }
@@ -4345,6 +4347,48 @@ static void draw_actuator_visibility(uiLayout *layout, PointerRNA *ptr)
 	uiItemR(row, ptr, "apply_to_children", 0, NULL, ICON_NONE);
 }
 
+static void draw_actuator_steering(uiLayout *layout, PointerRNA *ptr)
+{
+	uiLayout *row;
+	uiLayout *col;
+
+	uiItemR(layout, ptr, "mode", 0, NULL, 0);
+	uiItemR(layout, ptr, "target", 0, NULL, 0);
+	uiItemR(layout, ptr, "navmesh", 0, NULL, 0);	
+
+	row = uiLayoutRow(layout, 0);
+	uiItemR(row, ptr, "distance", 0, NULL, 0);
+	uiItemR(row, ptr, "velocity", 0, NULL, 0);
+	row = uiLayoutRow(layout, 0);
+	uiItemR(row, ptr, "acceleration", 0, NULL, 0);
+	uiItemR(row, ptr, "turn_speed", 0, NULL, 0);
+
+	row = uiLayoutRow(layout, 0);
+	col = uiLayoutColumn(row, 0);
+	uiItemR(col, ptr, "facing", 0, NULL, 0);
+	col = uiLayoutColumn(row, 0);
+	uiItemR(col, ptr, "facing_axis", 0, NULL, 0);
+	if (!RNA_boolean_get(ptr, "facing"))
+	{
+		uiLayoutSetActive(col, 0);
+	}
+	col = uiLayoutColumn(row, 0);
+	uiItemR(col, ptr, "normal_up", 0, NULL, 0);
+	if (!RNA_pointer_get(ptr, "navmesh").data)
+	{
+		uiLayoutSetActive(col, 0);
+	}
+
+	row = uiLayoutRow(layout, 0);
+	uiItemR(row, ptr, "self_terminated", 0, NULL, 0);
+	if (RNA_enum_get(ptr, "mode")==ACT_STEERING_PATHFOLLOWING)
+	{
+		uiItemR(row, ptr, "update_period", 0, NULL, 0);	
+		row = uiLayoutRow(layout, 0);
+	}
+	uiItemR(row, ptr, "show_visualization", 0, NULL, 0);	
+}
+
 static void draw_brick_actuator(uiLayout *layout, PointerRNA *ptr, bContext *C)
 {
 	uiLayout *box;
@@ -4406,6 +4450,8 @@ static void draw_brick_actuator(uiLayout *layout, PointerRNA *ptr, bContext *C)
 		case ACT_VISIBILITY:
 			draw_actuator_visibility(box, ptr);
 			break;
+		case ACT_STEERING:
+			draw_actuator_steering(box, ptr);
 	}
 }
 
diff --git a/source/blender/editors/util/CMakeLists.txt b/source/blender/editors/util/CMakeLists.txt
index 72f13c14f5d..da6e1990622 100644
--- a/source/blender/editors/util/CMakeLists.txt
+++ b/source/blender/editors/util/CMakeLists.txt
@@ -24,6 +24,7 @@ set(INC
 	../../blenkernel
 	../../blenlib
 	../../blenloader
+	../../../../extern/recastnavigation/Recast/Include
 	../../makesdna
 	../../makesrna
 	../../windowmanager
@@ -39,6 +40,7 @@ set(SRC
 	editmode_undo.c
 	numinput.c
 	undo.c
+	navmesh_conversion.cpp
 	crazyspace.c
 
 	util_intern.h
@@ -62,6 +64,7 @@ set(SRC
 	../include/ED_markers.h
 	../include/ED_mball.h
 	../include/ED_mesh.h
+	../include/ED_navmesh_conversion.h
 	../include/ED_node.h
 	../include/ED_numinput.h
 	../include/ED_object.h
diff --git a/source/blender/editors/util/SConscript b/source/blender/editors/util/SConscript
index a694b211ca4..0ee64fbf9f2 100644
--- a/source/blender/editors/util/SConscript
+++ b/source/blender/editors/util/SConscript
@@ -1,11 +1,12 @@
 #!/usr/bin/python
 Import ('env')
 
-sources = env.Glob('*.c')
+sources = env.Glob('*.c') + env.Glob('*.cpp')
 
 incs = '../include ../../blenlib ../../blenkernel ../../makesdna ../../imbuf'
 incs += ' ../../windowmanager #/intern/guardedalloc #/extern/glew/include'
 incs += ' ../../makesrna'
+incs += ' #extern/recastnavigation/Recast/Include'
 incs += ' ../../blenloader'
 
-env.BlenderLib ( 'bf_editors_util', sources, Split(incs), [], libtype=['core'], priority=[130] )
+env.BlenderLib ( 'bf_editors_util', sources, Split(incs), [], libtype=['core','player'], priority=[130,210] )
diff --git a/source/blender/editors/util/navmesh_conversion.cpp b/source/blender/editors/util/navmesh_conversion.cpp
new file mode 100644
index 00000000000..873660baa13
--- /dev/null
+++ b/source/blender/editors/util/navmesh_conversion.cpp
@@ -0,0 +1,444 @@
+/**
+* $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 <math.h>
+#include "Recast.h"
+
+
+extern "C"{
+#include "ED_navmesh_conversion.h"
+
+#include "DNA_meshdata_types.h"
+#include "BKE_cdderivedmesh.h"
+#include "BLI_math.h"
+}
+
+int polyNumVerts(const unsigned short* p, const int vertsPerPoly)
+{
+	int nv = 0;
+	for (int i=0; i<vertsPerPoly; i++)
+	{
+		if (p[i]==0xffff)
+			break;
+		nv++;
+	}
+	return nv;
+}
+
+bool polyIsConvex(const unsigned short* p, const int vertsPerPoly, const float* verts)
+{
+	int nv = polyNumVerts(p, vertsPerPoly);
+	if (nv<3)
+		return false;
+	for (int j=0; j<nv; j++)
+	{
+		const float* v = &verts[3*p[j]];
+		const float* v_next = &verts[3*p[(j+1)%nv]];
+		const float* v_prev = &verts[3*p[(nv+j-1)%nv]];
+		if (!left(v_prev, v, v_next))
+			return false;
+
+	}
+	return true;
+}
+
+float distPointToSegmentSq(const float* point, const float* a, const float* b)
+{
+	float abx[3], dx[3];
+	vsub(abx, b,a);
+	vsub(dx, point,a);
+	float d = abx[0]*abx[0]+abx[2]*abx[2];
+	float t = abx[0]*dx[0]+abx[2]*dx[2];
+	if (d > 0)
+		t /= d;
+	if (t < 0)
+		t = 0;
+	else if (t > 1)
+		t = 1;
+	dx[0] = a[0] + t*abx[0] - point[0];
+	dx[2] = a[2] + t*abx[2] - point[2];
+	return dx[0]*dx[0] + dx[2]*dx[2];
+}
+
+bool buildRawVertIndicesData(DerivedMesh* dm, int &nverts, float *&verts, 
+									int &ntris, unsigned short *&tris, int *&trisToFacesMap,
+									int *&recastData)
+{
+	nverts = dm->getNumVerts(dm);
+	if (nverts>=0xffff)
+	{
+		printf("Converting navmesh: Error! Too many vertices. Max number of vertices %d\n", 0xffff);
+		return false;
+	}
+	verts = new float[3*nverts];
+	dm->getVertCos(dm, (float(*)[3])verts);
+
+	//flip coordinates
+	for (int vi=0; vi<nverts; vi++)
+	{
+		SWAP(float, verts[3*vi+1], verts[3*vi+2]);
+	}
+
+	//calculate number of tris
+	int nfaces = dm->getNumFaces(dm);
+	MFace *faces = dm->getFaceArray(dm);
+	ntris = nfaces;
+	for (int fi=0; fi<nfaces; fi++)
+	{
+		MFace* face = &faces[fi];
+		if (face->v4)
+			ntris++;
+	}
+
+	//copy and transform to triangles (reorder on the run)
+	trisToFacesMap = new int[ntris];
+	tris = new unsigned short[3*ntris];
+	unsigned short* tri = tris;
+	int triIdx = 0;
+	for (int fi=0; fi<nfaces; fi++)
+	{
+		MFace* face = &faces[fi];
+		tri[3*triIdx+0] = (unsigned short) face->v1;
+		tri[3*triIdx+1] = (unsigned short) face->v3;
+		tri[3*triIdx+2] = (unsigned short) face->v2;
+		trisToFacesMap[triIdx++]=fi;
+		if (face->v4)
+		{
+			tri[3*triIdx+0] = (unsigned short) face->v1;
+			tri[3*triIdx+1] = (unsigned short) face->v4;
+			tri[3*triIdx+2] = (unsigned short) face->v3;
+			trisToFacesMap[triIdx++]=fi;
+		}
+	}
+
+	//carefully, recast data is just reference to data in derived mesh
+	recastData = (int*)CustomData_get_layer(&dm->faceData, CD_RECAST);
+	return true;
+}
+
+bool buildPolygonsByDetailedMeshes(const int vertsPerPoly, const int npolys, 
+										  unsigned short* polys, const unsigned short* dmeshes, 
+										  const float* verts, const unsigned short* dtris, 
+										  const int* dtrisToPolysMap)
+{
+	bool res = false;
+	int capacity = vertsPerPoly;
+	unsigned short* newPoly =  new unsigned short[capacity];
+	memset(newPoly, 0xff, sizeof(unsigned short)*capacity);
+	for (int polyidx=0; polyidx<npolys; polyidx++)
+	{
+		int nv = 0;
+		//search border 
+		int btri = -1;
+		int bedge = -1;
+		int dtrisNum = dmeshes[polyidx*4+3];
+		int dtrisBase = dmeshes[polyidx*4+2];
+		unsigned char *traversedTris = new unsigned char[dtrisNum];
+		memset(traversedTris, 0, dtrisNum*sizeof(unsigned char));
+		for (int j=0; j<dtrisNum && btri==-1;j++)
+		{
+			int curpolytri = dtrisBase+j;
+			for (int k=0; k<3; k++)
+			{
+				unsigned short neighbortri = dtris[curpolytri*3*2+3+k];
+				if ( neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
+				{
+					btri = curpolytri;
+					bedge = k;
+					break;
+				}
+			}							
+		}
+		if (btri==-1 || bedge==-1)
+		{
+			//can't find triangle with border edge
+			return false;
+		}
+
+		newPoly[nv++] = dtris[btri*3*2+bedge];
+		int tri = btri;
+		int edge = (bedge+1)%3;
+		traversedTris[tri-dtrisBase] = 1;
+		while (tri!=btri || edge!=bedge)
+		{
+			int neighbortri = dtris[tri*3*2+3+edge];
+			if (neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
+			{
+				if (nv==capacity)
+				{
+					capacity += vertsPerPoly;
+					unsigned short* newPolyBig =  new unsigned short[capacity];
+					memset(newPolyBig, 0xff, sizeof(unsigned short)*capacity);
+					memcpy(newPolyBig, newPoly, sizeof(unsigned short)*nv);
+					delete newPoly;
+					newPoly = newPolyBig;			
+				}
+				newPoly[nv++] = dtris[tri*3*2+edge];
+				//move to next edge					
+				edge = (edge+1)%3;
+			}
+			else
+			{
+				//move to next tri
+				int twinedge = -1;
+				for (int k=0; k<3; k++)
+				{
+					if (dtris[neighbortri*3*2+3+k] == tri)
+					{
+						twinedge = k;
+						break;
+					}
+				}
+				if (twinedge==-1)
+				{
+					printf("Converting navmesh: Error! Can't find neighbor edge - invalid adjacency info\n");
+					goto returnLabel;					
+				}
+				tri = neighbortri;
+				edge = (twinedge+1)%3;
+				traversedTris[tri-dtrisBase] = 1;
+			}
+		}
+
+		unsigned short* adjustedPoly = new unsigned short[nv];
+		int adjustedNv = 0;
+		for (size_t i=0; i<(size_t)nv; i++)
+		{
+			unsigned short prev = newPoly[(nv+i-1)%nv];
+			unsigned short cur = newPoly[i];
+			unsigned short next = newPoly[(i+1)%nv];
+			float distSq = distPointToSegmentSq(&verts[3*cur], &verts[3*prev], &verts[3*next]);
+			static const float tolerance = 0.001f;
+			if (distSq>tolerance)
+				adjustedPoly[adjustedNv++] = cur;
+		}
+		memcpy(newPoly, adjustedPoly, adjustedNv*sizeof(unsigned short));
+		delete adjustedPoly;
+		nv = adjustedNv;
+
+		bool allBorderTraversed = true;
+		for (size_t i=0; i<(size_t)dtrisNum; i++)
+		{
+			if (traversedTris[i]==0)
+			{
+				//check whether it has border edges
+				int curpolytri = dtrisBase+i;
+				for (int k=0; k<3; k++)
+				{
+					unsigned short neighbortri = dtris[curpolytri*3*2+3+k];
+					if ( neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
+					{
+						allBorderTraversed = false;
+						break;
+					}
+				}
+			}				
+		}
+
+		if (nv<=vertsPerPoly && allBorderTraversed)
+		{
+			for (int i=0; i<nv; i++)
+			{
+				polys[polyidx*vertsPerPoly*2+i] = newPoly[i];
+			}
+		}
+	}
+	res = true;
+
+returnLabel:
+	delete newPoly;
+	return true;
+}
+
+struct SortContext
+{
+	const int* recastData;
+	const int* trisToFacesMap;
+};
+static int compareByData(void* data, const void * a, const void * b){
+	SortContext* context = (SortContext*)data;
+	return ( context->recastData[context->trisToFacesMap[*(int*)a]] - 
+		context->recastData[context->trisToFacesMap[*(int*)b]] );
+}
+
+bool buildNavMeshData(const int nverts, const float* verts, 
+							 const int ntris, const unsigned short *tris, 
+							 const int* recastData, const int* trisToFacesMap,
+							 int &ndtris, unsigned short *&dtris,
+							 int &npolys, unsigned short *&dmeshes, unsigned short *&polys,
+							 int &vertsPerPoly, int *&dtrisToPolysMap, int *&dtrisToTrisMap)
+
+{
+	if (!recastData)
+	{
+		printf("Converting navmesh: Error! Can't find recast custom data\n");
+		return false;
+	}
+
+	//sort the triangles by polygon idx
+	int* trisMapping = new int[ntris];
+	for (int i=0; i<ntris; i++)
+		trisMapping[i]=i;
+	SortContext context;
+	context.recastData = recastData;
+	context.trisToFacesMap = trisToFacesMap;
+	qsort_s(trisMapping, ntris, sizeof(int), compareByData, &context);
+
+	//search first valid triangle - triangle of convex polygon
+	int validTriStart = -1;
+	for (int i=0; i< ntris; i++)
+	{
+		if (recastData[trisToFacesMap[trisMapping[i]]]>0)
+		{
+			validTriStart = i;
+			break;
+		}
+	}
+
+	if (validTriStart<0)
+	{
+		printf("Converting navmesh: Error! No valid polygons in mesh\n");
+		delete trisMapping;
+		return false;
+	}
+
+	ndtris = ntris-validTriStart;
+	//fill dtris to faces mapping
+	dtrisToTrisMap = new int[ndtris];
+	memcpy(dtrisToTrisMap, &trisMapping[validTriStart], ndtris*sizeof(int));
+	delete trisMapping; trisMapping=NULL;
+
+	//create detailed mesh triangles  - copy only valid triangles
+	//and reserve memory for adjacency info
+	dtris = new unsigned short[3*2*ndtris];
+	memset(dtris, 0xffff, sizeof(unsigned short)*3*2*ndtris);
+	for (int i=0; i<ndtris; i++)
+	{
+		memcpy(dtris+3*2*i, tris+3*dtrisToTrisMap[i], sizeof(unsigned short)*3);
+	}
+	//create new recast data corresponded to dtris and renumber for continuous indices
+	int prevPolyIdx=-1, curPolyIdx, newPolyIdx=0;
+	dtrisToPolysMap = new int[ndtris];
+	for (int i=0; i<ndtris; i++)
+	{
+		curPolyIdx = recastData[trisToFacesMap[dtrisToTrisMap[i]]];
+		if (curPolyIdx!=prevPolyIdx)
+		{
+			newPolyIdx++;
+			prevPolyIdx=curPolyIdx;
+		}
+		dtrisToPolysMap[i] = newPolyIdx;
+	}
+
+
+	//build adjacency info for detailed mesh triangles
+	buildMeshAdjacency(dtris, ndtris, nverts, 3);
+
+	//create detailed mesh description for each navigation polygon
+	npolys = dtrisToPolysMap[ndtris-1];
+	dmeshes = new unsigned short[npolys*4];
+	memset(dmeshes, 0, npolys*4*sizeof(unsigned short));
+	unsigned short *dmesh = NULL;
+	int prevpolyidx = 0;
+	for (int i=0; i<ndtris; i++)
+	{
+		int curpolyidx = dtrisToPolysMap[i];
+		if (curpolyidx!=prevpolyidx)
+		{
+			if (curpolyidx!=prevpolyidx+1)
+			{
+				printf("Converting navmesh: Error! Wrong order of detailed mesh faces\n");
+				return false;
+			}
+			dmesh = dmesh==NULL ? dmeshes : dmesh+4;
+			dmesh[2] = (unsigned short)i;	//tbase
+			dmesh[3] = 0;	//tnum
+			prevpolyidx = curpolyidx;
+		}
+		dmesh[3]++;
+	}
+
+	//create navigation polygons
+	vertsPerPoly = 6;
+	polys = new unsigned short[npolys*vertsPerPoly*2];
+	memset(polys, 0xff, sizeof(unsigned short)*vertsPerPoly*2*npolys);
+
+	buildPolygonsByDetailedMeshes(vertsPerPoly, npolys, polys, dmeshes, verts, dtris, dtrisToPolysMap);
+
+	return true;
+}
+
+
+bool buildNavMeshDataByDerivedMesh(DerivedMesh *dm, int& vertsPerPoly, 
+										  int &nverts, float *&verts,
+										  int &ndtris, unsigned short *&dtris,
+										  int& npolys, unsigned short *&dmeshes,
+										  unsigned short*& polys, int *&dtrisToPolysMap,
+										  int *&dtrisToTrisMap, int *&trisToFacesMap)
+{
+	bool res = true;
+	int ntris =0, *recastData=NULL;
+	unsigned short *tris=NULL;
+	res = buildRawVertIndicesData(dm, nverts, verts, ntris, tris, trisToFacesMap, recastData);
+	if (!res)
+	{
+		printf("Converting navmesh: Error! Can't get vertices and indices from mesh\n");
+		goto exit;
+	}
+
+	res = buildNavMeshData(nverts, verts, ntris, tris, recastData, trisToFacesMap,
+		ndtris, dtris, npolys, dmeshes,polys, vertsPerPoly, 
+		dtrisToPolysMap, dtrisToTrisMap);
+	if (!res)
+	{
+		printf("Converting navmesh: Error! Can't get vertices and indices from mesh\n");
+		goto exit;
+	}
+
+exit:
+	if (tris)
+		delete tris;
+
+	return res;
+}
+
+int polyFindVertex(const unsigned short* p, const int vertsPerPoly, unsigned short vertexIdx)
+{
+	int res = -1;
+	for(int i=0; i<vertsPerPoly; i++)
+	{
+		if (p[i]==0xffff)
+			break;
+		if (p[i]==vertexIdx)
+		{
+			res = i;
+			break;
+		}
+	}
+	return res;
+}
\ No newline at end of file
diff --git a/source/blender/makesdna/DNA_actuator_types.h b/source/blender/makesdna/DNA_actuator_types.h
index 93db8340aac..239903208ec 100644
--- a/source/blender/makesdna/DNA_actuator_types.h
+++ b/source/blender/makesdna/DNA_actuator_types.h
@@ -230,6 +230,20 @@ typedef struct bArmatureActuator {
 	struct Object *subtarget;
 } bArmatureActuator;
 
+typedef struct bSteeringActuator {
+	char pad[5];
+	char flag;
+	short facingaxis;
+	int type;		/* 0=seek, 1=flee, 2=path following */
+	float dist;
+	float velocity;
+	float acceleration;
+	float turnspeed;
+	int updateTime;
+	struct Object *target;
+	struct Object *navmesh;
+} bSteeringActuator;
+
 typedef struct bActuator {
 	struct bActuator *next, *prev, *mynew;
 	short type;
@@ -295,6 +309,7 @@ typedef struct bActuator {
 #define ACT_SHAPEACTION 21
 #define ACT_STATE		22
 #define ACT_ARMATURE	23
+#define ACT_STEERING    24
 
 /* actuator flag */
 #define ACT_SHOW		1
@@ -511,6 +526,16 @@ typedef struct bActuator {
 #define ACT_CAMERA_X		(float)'x'
 #define ACT_CAMERA_Y		(float)'y'
 
+/* steeringactuator->type */
+#define ACT_STEERING_SEEK   0
+#define ACT_STEERING_FLEE   1
+#define ACT_STEERING_PATHFOLLOWING   2
+/* steeringactuator->flag */
+#define ACT_STEERING_SELFTERMINATED   1
+#define ACT_STEERING_ENABLEVISUALIZATION   2
+#define ACT_STEERING_AUTOMATICFACING   4
+#define ACT_STEERING_NORMALUP  8
+
 #endif
 
 
diff --git a/source/blender/makesdna/DNA_customdata_types.h b/source/blender/makesdna/DNA_customdata_types.h
index cdfcf465c6c..b721dc60e73 100644
--- a/source/blender/makesdna/DNA_customdata_types.h
+++ b/source/blender/makesdna/DNA_customdata_types.h
@@ -92,7 +92,8 @@ typedef struct CustomData {
 #define CD_ID_MCOL		21
 #define CD_TEXTURE_MCOL	22
 #define CD_CLOTH_ORCO	23
-#define CD_NUMTYPES		24
+#define CD_RECAST		24
+#define CD_NUMTYPES		25
 
 /* Bits for CustomDataMask */
 #define CD_MASK_MVERT		(1 << CD_MVERT)
@@ -117,6 +118,7 @@ typedef struct CustomData {
 #define CD_MASK_MDISPS		(1 << CD_MDISPS)
 #define CD_MASK_WEIGHT_MCOL	(1 << CD_WEIGHT_MCOL)
 #define CD_MASK_CLOTH_ORCO	(1 << CD_CLOTH_ORCO)
+#define CD_MASK_RECAST		(1 << CD_RECAST)
 
 /* CustomData.flag */
 
diff --git a/source/blender/makesdna/DNA_meshdata_types.h b/source/blender/makesdna/DNA_meshdata_types.h
index e3510b3a25a..61c4a660992 100644
--- a/source/blender/makesdna/DNA_meshdata_types.h
+++ b/source/blender/makesdna/DNA_meshdata_types.h
@@ -184,6 +184,10 @@ typedef struct PartialVisibility {
 	unsigned int totface, totedge, totvert, pad;
 } PartialVisibility;
 
+typedef struct MRecast{
+	int		i;
+} MRecast;
+
 /* mvert->flag (1=SELECT) */
 #define ME_SPHERETEST		2
 #define ME_VERT_TMP_TAG		4
diff --git a/source/blender/makesdna/DNA_modifier_types.h b/source/blender/makesdna/DNA_modifier_types.h
index d09e56a5708..3ba7fbd711f 100644
--- a/source/blender/makesdna/DNA_modifier_types.h
+++ b/source/blender/makesdna/DNA_modifier_types.h
@@ -71,6 +71,7 @@ typedef enum ModifierType {
 	eModifierType_Solidify,
 	eModifierType_Screw,
 	eModifierType_Warp,
+	eModifierType_NavMesh,
 	eModifierType_WeightVGEdit,
 	eModifierType_WeightVGMix,
 	eModifierType_WeightVGProximity,
@@ -749,6 +750,10 @@ typedef struct ScrewModifierData {
 #define MOD_SCREW_OBJECT_OFFSET	(1<<2)
 // #define MOD_SCREW_OBJECT_ANGLE	(1<<4)
 
+typedef struct NavMeshModifierData {
+	ModifierData modifier;
+} NavMeshModifierData;
+
 typedef struct WarpModifierData {
 	ModifierData modifier;
 
diff --git a/source/blender/makesdna/DNA_object_types.h b/source/blender/makesdna/DNA_object_types.h
index ffa82092ef1..8750ee9e906 100644
--- a/source/blender/makesdna/DNA_object_types.h
+++ b/source/blender/makesdna/DNA_object_types.h
@@ -189,6 +189,8 @@ typedef struct Object {
 	float max_vel; /* clamp the maximum velocity 0.0 is disabled */
 	float min_vel; /* clamp the maximum velocity 0.0 is disabled */
 	float m_contactProcessingThreshold;
+	float obstacleRad;
+	char pad0[4];
 	
 	short rotmode;		/* rotation mode - uses defines set out in DNA_action_types.h for PoseChannel rotations... */
 	
@@ -473,6 +475,8 @@ typedef struct DupliObject {
 #define OB_SOFT_BODY	0x20000
 #define OB_OCCLUDER		0x40000
 #define OB_SENSOR		0x80000
+#define OB_NAVMESH		0x100000
+#define OB_HASOBSTACLE	0x200000
 
 /* ob->gameflag2 */
 #define OB_NEVER_DO_ACTIVITY_CULLING	1
@@ -493,6 +497,7 @@ typedef struct DupliObject {
 #define OB_BODY_TYPE_SOFT			4
 #define OB_BODY_TYPE_OCCLUDER		5
 #define OB_BODY_TYPE_SENSOR			6
+#define OB_BODY_TYPE_NAVMESH		7
 
 /* ob->scavisflag */
 #define OB_VIS_SENS		1
diff --git a/source/blender/makesdna/DNA_scene_types.h b/source/blender/makesdna/DNA_scene_types.h
index be2a78ac774..be44b87d48e 100644
--- a/source/blender/makesdna/DNA_scene_types.h
+++ b/source/blender/makesdna/DNA_scene_types.h
@@ -426,6 +426,23 @@ typedef struct GameFraming {
 #define SCE_GAMEFRAMING_EXTEND 1
 #define SCE_GAMEFRAMING_SCALE  2
 
+typedef struct RecastData
+{
+	float cellsize;
+	float cellheight;
+	float agentmaxslope;
+	float agentmaxclimb;
+	float agentheight;
+	float agentradius;
+	float edgemaxlen;
+	float edgemaxerror;
+	float regionminsize;
+	float regionmergesize;
+	int vertsperpoly;
+	float detailsampledist;
+	float detailsamplemaxerror;
+} RecastData;
+
 typedef struct GameData {
 
 	/* physics (it was in world)*/
@@ -440,10 +457,13 @@ typedef struct GameData {
 	 * bit 3: (gameengine): Activity culling is enabled.
 	 * bit 5: (gameengine) : enable Bullet DBVT tree for view frustrum culling
 	*/
-	short mode, flag, matmode, pad[3];
+	short mode, flag, matmode, pad[2];
 	short occlusionRes;		/* resolution of occlusion Z buffer in pixel */
 	short physicsEngine;
 	short ticrate, maxlogicstep, physubstep, maxphystep;
+	short obstacleSimulation;
+	float levelHeight;
+
 
 	/*  standalone player */
 	struct GameFraming framing;
@@ -455,6 +475,7 @@ typedef struct GameData {
 	short stereoflag, stereomode;
 	short pad2, pad3;
 	float eyeseparation, pad1;
+	RecastData recastData;
 } GameData;
 
 #define STEREO_NOSTEREO		1
@@ -478,6 +499,11 @@ typedef struct GameData {
 #define WOPHY_ODE		4
 #define WOPHY_BULLET	5
 
+/* obstacleSimulation */
+#define OBSTSIMULATION_NONE		0
+#define OBSTSIMULATION_TOI_rays		1
+#define OBSTSIMULATION_TOI_cells	2
+
 /* GameData.flag */
 #define GAME_RESTRICT_ANIM_UPDATES			(1 << 0)
 #define GAME_ENABLE_ALL_FRAMES				(1 << 1)
@@ -494,6 +520,7 @@ typedef struct GameData {
 #define GAME_IGNORE_DEPRECATION_WARNINGS	(1 << 12)
 #define GAME_ENABLE_ANIMATION_RECORD		(1 << 13)
 #define GAME_SHOW_MOUSE						(1 << 14)
+#define GAME_SHOW_OBSTACLE_SIMULATION		(1 << 15)
 #define GAME_GLSL_NO_COLOR_MANAGEMENT		(1 << 15)
 /* Note: GameData.flag is a short (max 16 flags). To add more flags, GameData.flag needs to be an int */
 
diff --git a/source/blender/makesrna/intern/rna_actuator.c b/source/blender/makesrna/intern/rna_actuator.c
index 3d0e177c94e..3214d31a53c 100644
--- a/source/blender/makesrna/intern/rna_actuator.c
+++ b/source/blender/makesrna/intern/rna_actuator.c
@@ -60,6 +60,7 @@ EnumPropertyItem actuator_type_items[] ={
 	{ACT_SOUND, "SOUND", 0, "Sound", ""},
 	{ACT_STATE, "STATE", 0, "State", ""},
 	{ACT_VISIBILITY, "VISIBILITY", 0, "Visibility", ""},
+	{ACT_STEERING, "STEERING", 0, "Steering", ""},
 	{0, NULL, 0, NULL, NULL}};
 
 #ifdef RNA_RUNTIME
@@ -103,6 +104,8 @@ static StructRNA* rna_Actuator_refine(struct PointerRNA *ptr)
 			return &RNA_StateActuator;
 		case ACT_ARMATURE:
 			return &RNA_ArmatureActuator;
+		case ACT_STEERING:
+			return &RNA_SteeringActuator;
 		default:
 			return &RNA_Actuator;
 	}
@@ -435,6 +438,7 @@ EnumPropertyItem *rna_Actuator_type_itemf(bContext *C, PointerRNA *ptr, Property
 	RNA_enum_items_add_value(&item, &totitem, actuator_type_items, ACT_PROPERTY);
 	RNA_enum_items_add_value(&item, &totitem, actuator_type_items, ACT_RANDOM);
 	RNA_enum_items_add_value(&item, &totitem, actuator_type_items, ACT_SCENE);
+	RNA_enum_items_add_value(&item, &totitem, actuator_type_items, ACT_STEERING);
 
 	RNA_enum_items_add_value(&item, &totitem, actuator_type_items, ACT_SOUND);
 	RNA_enum_items_add_value(&item, &totitem, actuator_type_items, ACT_STATE);
@@ -480,6 +484,18 @@ static void rna_Actuator_Armature_update(Main *bmain, Scene *scene, PointerRNA *
 	constraint[0] = 0;
 }
 
+static void rna_SteeringActuator_navmesh_set(PointerRNA *ptr, PointerRNA value)
+{
+	bActuator *act = (bActuator*)ptr->data;
+	bSteeringActuator *sa = (bSteeringActuator*) act->data;
+
+	Object* obj = value.data;
+	if (obj && obj->body_type==OB_BODY_TYPE_NAVMESH)
+		sa->navmesh = obj;
+	else
+		sa->navmesh = NULL;
+}
+
 /* note: the following set functions exists only to avoid id refcounting */
 static void rna_Actuator_editobject_mesh_set(PointerRNA *ptr, PointerRNA value)
 {
@@ -1900,6 +1916,108 @@ static void rna_def_armature_actuator(BlenderRNA *brna)
 	RNA_def_property_update(prop, NC_LOGIC, NULL);
 }
 
+static void rna_def_steering_actuator(BlenderRNA *brna)
+{
+	StructRNA *srna;
+	PropertyRNA *prop;
+
+	static EnumPropertyItem prop_type_items[] ={
+		{ACT_STEERING_SEEK, "SEEK", 0, "Seek", ""},
+		{ACT_STEERING_FLEE, "FLEE", 0, "Flee", ""},
+		{ACT_STEERING_PATHFOLLOWING, "PATHFOLLOWING", 0, "Path following", ""},
+		{0, NULL, 0, NULL, NULL}};
+
+	static EnumPropertyItem facingaxis_items[] ={
+		{1, "X", 0, "X", ""},
+		{2, "Y", 0, "Y", ""},
+		{3, "Z", 0, "Z", ""},
+		{4, "-X", 0, "-X", ""},
+		{5, "-Y", 0, "-Y", ""},
+		{6, "-Z", 0, "-Z", ""},
+		{0, NULL, 0, NULL, NULL}};
+
+	srna= RNA_def_struct(brna, "SteeringActuator", "Actuator");
+	RNA_def_struct_ui_text(srna, "Steering Actuator", "");
+	RNA_def_struct_sdna_from(srna, "bSteeringActuator", "data");
+
+	prop= RNA_def_property(srna, "mode", PROP_ENUM, PROP_NONE);
+	RNA_def_property_enum_sdna(prop, NULL, "type");
+	RNA_def_property_enum_items(prop, prop_type_items);
+	RNA_def_property_ui_text(prop, "Behavior", "");
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+
+	prop= RNA_def_property(srna, "velocity", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "velocity");
+	RNA_def_property_range(prop, 0.0, 1000.0);
+	RNA_def_property_ui_text(prop, "Velocity", "Velocity magnitude");
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+
+	prop= RNA_def_property(srna, "acceleration", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "acceleration");
+	RNA_def_property_range(prop, 0.0, 1000.0);
+	RNA_def_property_ui_text(prop, "Acceleration", "Max acceleration");
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+
+	prop= RNA_def_property(srna, "turn_speed", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "turnspeed");
+	RNA_def_property_range(prop, 0.0, 720.0);
+	RNA_def_property_ui_text(prop, "Turn Speed", "Max turn speed");
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+
+	prop= RNA_def_property(srna, "distance", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "dist");
+	RNA_def_property_range(prop, 0.0, 1000.0);
+	RNA_def_property_ui_text(prop, "Dist", "Relax distance");
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+
+	prop= RNA_def_property(srna, "target", PROP_POINTER, PROP_NONE);
+	RNA_def_property_struct_type(prop, "Object");
+	RNA_def_property_pointer_sdna(prop, NULL, "target");
+	RNA_def_property_flag(prop, PROP_EDITABLE);
+	RNA_def_property_ui_text(prop, "Target Object", "Set target object");
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+
+	prop= RNA_def_property(srna, "self_terminated", PROP_BOOLEAN, PROP_NONE);
+	RNA_def_property_boolean_sdna(prop, NULL, "flag", ACT_STEERING_SELFTERMINATED);
+	RNA_def_property_ui_text(prop, "Self Terminated", "Terminate when target is reached");
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+
+	prop= RNA_def_property(srna, "show_visualization", PROP_BOOLEAN, PROP_NONE);
+	RNA_def_property_boolean_sdna(prop, NULL, "flag", ACT_STEERING_ENABLEVISUALIZATION);
+	RNA_def_property_ui_text(prop, "Visualize", "Enable debug visualization");
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+
+	prop= RNA_def_property(srna, "update_period", PROP_INT, PROP_NONE);
+	RNA_def_property_int_sdna(prop, NULL, "updateTime");
+	RNA_def_property_ui_range(prop, -1, 100000, 1, 1);
+	RNA_def_property_ui_text(prop, "Update period", "Path update period");
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+
+	prop= RNA_def_property(srna, "navmesh", PROP_POINTER, PROP_NONE);
+	RNA_def_property_struct_type(prop, "Object");
+	RNA_def_property_pointer_sdna(prop, NULL, "navmesh");
+	RNA_def_property_flag(prop, PROP_EDITABLE);
+	RNA_def_property_ui_text(prop, "NavMesh Object", "Navigation mesh");
+	RNA_def_property_pointer_funcs(prop, NULL, "rna_SteeringActuator_navmesh_set", NULL, NULL);
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+
+	prop= RNA_def_property(srna, "facing", PROP_BOOLEAN, PROP_NONE);
+	RNA_def_property_boolean_sdna(prop, NULL, "flag", ACT_STEERING_AUTOMATICFACING);
+	RNA_def_property_ui_text(prop, "Facing", "Enable automatic facing");
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+
+	prop= RNA_def_property(srna, "facing_axis", PROP_ENUM, PROP_NONE);
+	RNA_def_property_enum_sdna(prop, NULL, "facingaxis");
+	RNA_def_property_enum_items(prop, facingaxis_items);
+	RNA_def_property_ui_text(prop, "Axis", "Axis for automatic facing");
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+
+	prop= RNA_def_property(srna, "normal_up", PROP_BOOLEAN, PROP_NONE);
+	RNA_def_property_boolean_sdna(prop, NULL, "flag", ACT_STEERING_NORMALUP);
+	RNA_def_property_ui_text(prop, "N", "Use normal of the navmesh to set \"UP\" vector");
+	RNA_def_property_update(prop, NC_LOGIC, NULL);
+}
+
 void RNA_def_actuator(BlenderRNA *brna)
 {
 	rna_def_actuator(brna);
@@ -1921,6 +2039,7 @@ void RNA_def_actuator(BlenderRNA *brna)
 	rna_def_shape_action_actuator(brna);
 	rna_def_state_actuator(brna);
 	rna_def_armature_actuator(brna);
+	rna_def_steering_actuator(brna);
 }
 
 #endif
diff --git a/source/blender/makesrna/intern/rna_modifier.c b/source/blender/makesrna/intern/rna_modifier.c
index 07967103a40..f6c96c2594c 100644
--- a/source/blender/makesrna/intern/rna_modifier.c
+++ b/source/blender/makesrna/intern/rna_modifier.c
@@ -96,6 +96,7 @@ EnumPropertyItem modifier_type_items[] ={
 	{eModifierType_Smoke, "SMOKE", ICON_MOD_SMOKE, "Smoke", ""},
 	{eModifierType_Softbody, "SOFT_BODY", ICON_MOD_SOFT, "Soft Body", ""},
 	{eModifierType_Surface, "SURFACE", ICON_MOD_PHYSICS, "Surface", ""},
+	{eModifierType_NavMesh, "NAVMESH", ICON_MOD_PHYSICS, "Navigation mesh", ""},
 	{0, NULL, 0, NULL, NULL}};
 
 #ifdef RNA_RUNTIME
@@ -188,6 +189,8 @@ static StructRNA* rna_Modifier_refine(struct PointerRNA *ptr)
 			return &RNA_ScrewModifier;
 		case eModifierType_Warp:
 			return &RNA_WarpModifier;
+		case eModifierType_NavMesh:
+			return &RNA_NavMeshModifier;
 		case eModifierType_WeightVGEdit:
 			return &RNA_VertexWeightEditModifier;
 		case eModifierType_WeightVGMix:
@@ -2487,6 +2490,17 @@ static void rna_def_modifier_screw(BlenderRNA *brna)
 	RNA_def_property_update(prop, 0, "rna_Modifier_update");*/
 }
 
+static void rna_def_modifier_navmesh(BlenderRNA *brna)
+{
+	StructRNA *srna;
+	PropertyRNA *prop;
+
+	srna= RNA_def_struct(brna, "NavMeshModifier", "Modifier");
+	RNA_def_struct_ui_text(srna, "NavMesh Modifier", "NavMesh modifier");
+	RNA_def_struct_sdna(srna, "NavMeshModifierData");
+	RNA_def_struct_ui_icon(srna, ICON_MOD_DECIM);
+}
+
 static void rna_def_modifier_weightvg_mask(BlenderRNA *brna, StructRNA *srna)
 {
 	static EnumPropertyItem weightvg_mask_tex_map_items[] = {
@@ -2878,6 +2892,7 @@ void RNA_def_modifier(BlenderRNA *brna)
 	rna_def_modifier_smoke(brna);
 	rna_def_modifier_solidify(brna);
 	rna_def_modifier_screw(brna);
+	rna_def_modifier_navmesh(brna);
 	rna_def_modifier_weightvgedit(brna);
 	rna_def_modifier_weightvgmix(brna);
 	rna_def_modifier_weightvgproximity(brna);
diff --git a/source/blender/makesrna/intern/rna_object.c b/source/blender/makesrna/intern/rna_object.c
index 83efd9d1a9f..571f8d36305 100644
--- a/source/blender/makesrna/intern/rna_object.c
+++ b/source/blender/makesrna/intern/rna_object.c
@@ -858,6 +858,8 @@ static int rna_GameObjectSettings_physics_type_get(PointerRNA *ptr)
 	if (!(ob->gameflag & OB_COLLISION)) {
 		if (ob->gameflag & OB_OCCLUDER) {
 			ob->body_type = OB_BODY_TYPE_OCCLUDER;
+		} else if (ob->gameflag & OB_NAVMESH){
+			ob->body_type = OB_BODY_TYPE_NAVMESH;
 		} else {
 			ob->body_type = OB_BODY_TYPE_NO_COLLISION;
 		}
@@ -887,31 +889,35 @@ static void rna_GameObjectSettings_physics_type_set(PointerRNA *ptr, int value)
 	switch (ob->body_type) {
 	case OB_BODY_TYPE_SENSOR:
 		ob->gameflag |= OB_SENSOR|OB_COLLISION|OB_GHOST;
-		ob->gameflag &= ~(OB_OCCLUDER|OB_DYNAMIC|OB_RIGID_BODY|OB_SOFT_BODY|OB_ACTOR|OB_ANISOTROPIC_FRICTION|OB_DO_FH|OB_ROT_FH|OB_COLLISION_RESPONSE);
+		ob->gameflag &= ~(OB_OCCLUDER|OB_DYNAMIC|OB_RIGID_BODY|OB_SOFT_BODY|OB_ACTOR|OB_ANISOTROPIC_FRICTION|OB_DO_FH|OB_ROT_FH|OB_COLLISION_RESPONSE|OB_NAVMESH);
 		break;
 	case OB_BODY_TYPE_OCCLUDER:
 		ob->gameflag |= OB_OCCLUDER;
-		ob->gameflag &= ~(OB_SENSOR|OB_COLLISION|OB_DYNAMIC);
+		ob->gameflag &= ~(OB_SENSOR|OB_COLLISION|OB_DYNAMIC|OB_NAVMESH);
+		break;
+	case OB_BODY_TYPE_NAVMESH:
+		ob->gameflag |= OB_NAVMESH;
+		ob->gameflag &= ~(OB_SENSOR|OB_COLLISION|OB_DYNAMIC|OB_OCCLUDER);
 		break;
 	case OB_BODY_TYPE_NO_COLLISION:
-		ob->gameflag &= ~(OB_SENSOR|OB_COLLISION|OB_OCCLUDER|OB_DYNAMIC);
+		ob->gameflag &= ~(OB_SENSOR|OB_COLLISION|OB_OCCLUDER|OB_DYNAMIC|OB_NAVMESH);
 		break;
 	case OB_BODY_TYPE_STATIC:
 		ob->gameflag |= OB_COLLISION;
-		ob->gameflag &= ~(OB_DYNAMIC|OB_RIGID_BODY|OB_SOFT_BODY|OB_OCCLUDER|OB_SENSOR);
+		ob->gameflag &= ~(OB_DYNAMIC|OB_RIGID_BODY|OB_SOFT_BODY|OB_OCCLUDER|OB_SENSOR|OB_NAVMESH);
 		break;
 	case OB_BODY_TYPE_DYNAMIC:
 		ob->gameflag |= OB_COLLISION|OB_DYNAMIC|OB_ACTOR;
-		ob->gameflag &= ~(OB_RIGID_BODY|OB_SOFT_BODY|OB_OCCLUDER|OB_SENSOR);
+		ob->gameflag &= ~(OB_RIGID_BODY|OB_SOFT_BODY|OB_OCCLUDER|OB_SENSOR|OB_NAVMESH);
 		break;
 	case OB_BODY_TYPE_RIGID:
 		ob->gameflag |= OB_COLLISION|OB_DYNAMIC|OB_RIGID_BODY|OB_ACTOR;
-		ob->gameflag &= ~(OB_SOFT_BODY|OB_OCCLUDER|OB_SENSOR);
+		ob->gameflag &= ~(OB_SOFT_BODY|OB_OCCLUDER|OB_SENSOR|OB_NAVMESH);
 		break;
 	default:
 	case OB_BODY_TYPE_SOFT:
 		ob->gameflag |= OB_COLLISION|OB_DYNAMIC|OB_SOFT_BODY|OB_ACTOR;
-		ob->gameflag &= ~(OB_RIGID_BODY|OB_OCCLUDER|OB_SENSOR);
+		ob->gameflag &= ~(OB_RIGID_BODY|OB_OCCLUDER|OB_SENSOR|OB_NAVMESH);
 
 		/* assume triangle mesh, if no bounds chosen for soft body */
 		if ((ob->gameflag & OB_BOUNDS) && (ob->boundtype<OB_BOUND_POLYH))
@@ -1343,6 +1349,7 @@ static void rna_def_object_game_settings(BlenderRNA *brna)
 		{OB_BODY_TYPE_SOFT, "SOFT_BODY", 0, "Soft Body", "Soft body"},
 		{OB_BODY_TYPE_OCCLUDER, "OCCLUDE", 0, "Occlude", "Occluder for optimizing scene rendering"},
 		{OB_BODY_TYPE_SENSOR, "SENSOR", 0, "Sensor", "Collision Sensor, detects static and dynamic objects but not the other collision sensor objects"},
+		{OB_BODY_TYPE_NAVMESH, "NAVMESH", 0, "NavMesh", "Navigation mesh"},
 		{0, NULL, 0, NULL, NULL}};
 
 	srna= RNA_def_struct(brna, "GameObjectSettings", NULL);
@@ -1512,6 +1519,15 @@ static void rna_def_object_game_settings(BlenderRNA *brna)
 	RNA_def_property_pointer_sdna(prop, NULL, "bsoft");
 	RNA_def_property_ui_text(prop, "Soft Body Settings", "Settings for Bullet soft body simulation");
 
+	prop= RNA_def_property(srna, "create_obstacle", PROP_BOOLEAN, PROP_NONE);
+	RNA_def_property_boolean_sdna(prop, NULL, "gameflag", OB_HASOBSTACLE);
+	RNA_def_property_ui_text(prop, "Create obstacle", "Create representation for obstacle simulation");
+
+	prop= RNA_def_property(srna, "obstacle_radius", PROP_FLOAT, PROP_NONE|PROP_UNIT_LENGTH);
+	RNA_def_property_float_sdna(prop, NULL, "obstacleRad");
+	RNA_def_property_range(prop, 0.0, 1000.0);
+	RNA_def_property_ui_text(prop, "Obstacle Radius", "Radius of object representation in obstacle simulation");
+	
 	/* state */
 
 	prop= RNA_def_property(srna, "states_visible", PROP_BOOLEAN, PROP_LAYER_MEMBER);
diff --git a/source/blender/makesrna/intern/rna_scene.c b/source/blender/makesrna/intern/rna_scene.c
index 8c2f473c65e..197ddd2ba06 100644
--- a/source/blender/makesrna/intern/rna_scene.c
+++ b/source/blender/makesrna/intern/rna_scene.c
@@ -39,6 +39,7 @@
 #include "DNA_particle_types.h"
 #include "DNA_scene_types.h"
 #include "DNA_userdef_types.h"
+#include "BLI_math.h"
 
 /* Include for Bake Options */
 #include "RE_pipeline.h"
@@ -1669,6 +1670,96 @@ void rna_def_render_layer_common(StructRNA *srna, int scene)
 	else RNA_def_property_clear_flag(prop, PROP_EDITABLE);
 }
 
+static void rna_def_scene_game_recast_data(BlenderRNA *brna)
+{
+	StructRNA *srna;
+	PropertyRNA *prop;
+
+	srna= RNA_def_struct(brna, "SceneGameRecastData", NULL);
+	RNA_def_struct_sdna(srna, "RecastData");
+	RNA_def_struct_nested(brna, srna, "Scene");
+	RNA_def_struct_ui_text(srna, "Recast Data", "Recast data for a Game datablock");
+
+	prop= RNA_def_property(srna, "cell_size", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "cellsize");
+	RNA_def_property_ui_range(prop, 0.1, 1, 1, 2);
+	RNA_def_property_ui_text(prop, "Cell Size", "Rasterized cell size");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "cell_height", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "cellheight");
+	RNA_def_property_ui_range(prop, 0.1, 1, 1, 2);
+	RNA_def_property_ui_text(prop, "Cell Height", "Rasterized cell height");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "agent_height", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "agentheight");
+	RNA_def_property_ui_range(prop, 0.1, 5, 1, 2);
+	RNA_def_property_ui_text(prop, "Agent Height", "Minimum height where the agent can still walk");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "agent_radius", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "agentradius");
+	RNA_def_property_ui_range(prop, 0.1, 5, 1, 2);
+	RNA_def_property_ui_text(prop, "Agent Radius", "Radius of the agent");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "max_climb", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "agentmaxclimb");
+	RNA_def_property_ui_range(prop, 0.1, 5, 1, 2);
+	RNA_def_property_ui_text(prop, "Max Climb", "Maximum height between grid cells the agent can climb");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "max_slope", PROP_FLOAT, PROP_ANGLE);
+	RNA_def_property_float_sdna(prop, NULL, "agentmaxslope");
+	RNA_def_property_range(prop, 0, M_PI/2);
+	RNA_def_property_ui_text(prop, "Max Slope", "Maximum walkable slope angle in degrees");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+
+	prop= RNA_def_property(srna, "region_min_size", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "regionminsize");
+	RNA_def_property_ui_range(prop, 0, 150, 1, 2);
+	RNA_def_property_ui_text(prop, "Min Region Size", "Minimum regions size. Smaller regions will be deleted");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "region_merge_size", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "regionmergesize");
+	RNA_def_property_ui_range(prop, 0, 150, 1, 2);
+	RNA_def_property_ui_text(prop, "Merged Region Size", "Minimum regions size. Smaller regions will be merged");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "edge_max_len", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "edgemaxlen");
+	RNA_def_property_ui_range(prop, 0, 50, 1, 2);
+	RNA_def_property_ui_text(prop, "Max Edge Length", "Maximum contour edge length");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "edge_max_error", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "edgemaxerror");
+	RNA_def_property_ui_range(prop, 0.1, 3.0, 1, 2);
+	RNA_def_property_ui_text(prop, "Max Edge Error", "Maximum distance error from contour to cells");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "verts_per_poly", PROP_INT, PROP_NONE);
+	RNA_def_property_int_sdna(prop, NULL, "vertsperpoly");
+	RNA_def_property_ui_range(prop, 3, 12, 1, 0);
+	RNA_def_property_ui_text(prop, "Verts Per Poly", "Max number of vertices per polygon");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "sample_dist", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "detailsampledist");
+	RNA_def_property_ui_range(prop, 0.0, 16.0, 1, 2);
+	RNA_def_property_ui_text(prop, "Sample Distance", "Detail mesh sample spacing");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "sample_max_error", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_float_sdna(prop, NULL, "detailsamplemaxerror");
+	RNA_def_property_ui_range(prop, 0.0, 16.0, 1, 2);
+	RNA_def_property_ui_text(prop, "Max Sample Error", "Detail mesh simplification max sample error");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+}
+
 static void rna_def_scene_game_data(BlenderRNA *brna)
 {
 	StructRNA *srna;
@@ -1718,6 +1809,12 @@ static void rna_def_scene_game_data(BlenderRNA *brna)
 		{GAME_MAT_GLSL, "GLSL", 0, "GLSL", "OpenGL shading language shaders"},
 		{0, NULL, 0, NULL, NULL}};
 
+	static EnumPropertyItem obstacle_simulation_items[] = {
+		{OBSTSIMULATION_NONE, "NONE", 0, "None", ""},
+		{OBSTSIMULATION_TOI_rays, "RVO (rays)", 0, "RVO (rays)", ""},
+		{OBSTSIMULATION_TOI_cells, "RVO (cells)", 0, "RVO (cells)", ""},
+		{0, NULL, 0, NULL, NULL}};
+
 	srna= RNA_def_struct(brna, "SceneGameData", NULL);
 	RNA_def_struct_sdna(srna, "GameData");
 	RNA_def_struct_nested(brna, srna, "Scene");
@@ -1970,6 +2067,33 @@ static void rna_def_scene_game_data(BlenderRNA *brna)
 	RNA_def_property_boolean_negative_sdna(prop, NULL, "flag", GAME_GLSL_NO_EXTRA_TEX);
 	RNA_def_property_ui_text(prop, "GLSL Extra Textures", "Use extra textures like normal or specular maps for GLSL rendering");
 	RNA_def_property_update(prop, NC_SCENE|NA_EDITED, "rna_Scene_glsl_update");
+
+	/* obstacle simulation */
+	prop= RNA_def_property(srna, "obstacle_simulation", PROP_ENUM, PROP_NONE);
+	RNA_def_property_enum_sdna(prop, NULL, "obstacleSimulation");
+	RNA_def_property_enum_items(prop, obstacle_simulation_items);
+	RNA_def_property_ui_text(prop, "Obstacle simulation", "Simulation used for obstacle avoidance in the game engine");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "level_height", PROP_FLOAT, PROP_ACCELERATION);
+	RNA_def_property_float_sdna(prop, NULL, "levelHeight");
+	RNA_def_property_range(prop, 0.0f, 200.0f);
+	RNA_def_property_ui_text(prop, "Level height", "Max difference in heights of obstacles to enable their interaction");
+	RNA_def_property_update(prop, NC_SCENE, NULL);
+
+	prop= RNA_def_property(srna, "show_obstacle_simulation", PROP_BOOLEAN, PROP_NONE);
+	RNA_def_property_boolean_sdna(prop, NULL, "flag", GAME_SHOW_OBSTACLE_SIMULATION);
+	RNA_def_property_ui_text(prop, "Visualization", "Enable debug visualization for obstacle simulation");
+
+	/* Recast Settings */
+	prop= RNA_def_property(srna, "recast_data", PROP_POINTER, PROP_NONE);
+	RNA_def_property_flag(prop, PROP_NEVER_NULL);
+	RNA_def_property_pointer_sdna(prop, NULL, "recastData");
+	RNA_def_property_struct_type(prop, "SceneGameRecastData");
+	RNA_def_property_ui_text(prop, "Recast Data", "");
+
+	/* Nestled Data  */
+	rna_def_scene_game_recast_data(brna);
 }
 
 static void rna_def_scene_render_layer(BlenderRNA *brna)
diff --git a/source/blender/modifiers/CMakeLists.txt b/source/blender/modifiers/CMakeLists.txt
index f374de3fd17..d06ada737ee 100644
--- a/source/blender/modifiers/CMakeLists.txt
+++ b/source/blender/modifiers/CMakeLists.txt
@@ -34,12 +34,16 @@ set(INC
 	../makesdna
 	../makesrna
 	../render/extern/include
+	../editors/include
+	../gpu
 	../../../intern/elbeem/extern
 	../../../intern/guardedalloc
+	../../../extern/recastnavigation/Recast/Include
 )
 
 set(INC_SYS
 	${ZLIB_INCLUDE_DIRS}
+        ${GLEW_INCLUDE_PATH}
 )
 
 set(SRC
@@ -64,6 +68,7 @@ set(SRC
 	intern/MOD_meshdeform.c
 	intern/MOD_mirror.c
 	intern/MOD_multires.c
+	intern/MOD_navmesh.cpp
 	intern/MOD_none.c
 	intern/MOD_particleinstance.c
 	intern/MOD_particlesystem.c
diff --git a/source/blender/modifiers/MOD_modifiertypes.h b/source/blender/modifiers/MOD_modifiertypes.h
index 0ba906a433b..0ae9768c0e6 100644
--- a/source/blender/modifiers/MOD_modifiertypes.h
+++ b/source/blender/modifiers/MOD_modifiertypes.h
@@ -72,6 +72,7 @@ extern ModifierTypeInfo modifierType_ShapeKey;
 extern ModifierTypeInfo modifierType_Solidify;
 extern ModifierTypeInfo modifierType_Screw;
 extern ModifierTypeInfo modifierType_Warp;
+extern ModifierTypeInfo modifierType_NavMesh;
 extern ModifierTypeInfo modifierType_WeightVGEdit;
 extern ModifierTypeInfo modifierType_WeightVGMix;
 extern ModifierTypeInfo modifierType_WeightVGProximity;
diff --git a/source/blender/modifiers/SConscript b/source/blender/modifiers/SConscript
index 66dd00f0248..f90e637d151 100644
--- a/source/blender/modifiers/SConscript
+++ b/source/blender/modifiers/SConscript
@@ -1,12 +1,14 @@
 #!/usr/bin/python
 Import ('env')
 
-sources = env.Glob('intern/*.c')
+sources = env.Glob('intern/*.c') + env.Glob('intern/*.cpp')
 
 incs = '. ./intern'
-incs += ' #/intern/guardedalloc #/intern/decimation/extern #/intern/bsp/extern #/intern/elbeem/extern'
+incs += ' #/intern/guardedalloc #/intern/decimation/extern #/intern/bsp/extern #/intern/elbeem/extern #/extern/glew/include'
 incs += ' ../render/extern/include ../blenloader'
 incs += ' ../include ../blenlib ../makesdna ../makesrna ../blenkernel ../blenkernel/intern'
+incs += ' ../editors/include ../gpu'
+incs += ' #extern/recastnavigation/Recast/Include'
 
 incs += ' ' + env['BF_ZLIB_INC']
 
diff --git a/source/blender/modifiers/intern/MOD_navmesh.cpp b/source/blender/modifiers/intern/MOD_navmesh.cpp
new file mode 100644
index 00000000000..888da7ba985
--- /dev/null
+++ b/source/blender/modifiers/intern/MOD_navmesh.cpp
@@ -0,0 +1,269 @@
+/*
+* $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) 2005 by the Blender Foundation.
+* All rights reserved.
+*
+* Contributor(s): 
+*
+* ***** END GPL LICENSE BLOCK *****
+*
+*/
+#include <math.h>
+#include "Recast.h"
+
+extern "C"{
+#include "ED_navmesh_conversion.h"
+
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+#include "BLI_math.h"
+#include "BKE_cdderivedmesh.h"
+#include "BKE_mesh.h"
+#include "BKE_modifier.h"
+#include "BKE_particle.h"
+#include "BKE_customdata.h"
+#include "MEM_guardedalloc.h"
+#include "BIF_gl.h"
+#include "GPU_buffers.h"
+#include "GPU_draw.h"
+#include "UI_resources.h"
+
+static void initData(ModifierData *md)
+{
+	NavMeshModifierData *nmmd = (NavMeshModifierData*) md;
+}
+
+static void copyData(ModifierData *md, ModifierData *target)
+{
+	NavMeshModifierData *nmmd = (NavMeshModifierData*) md;
+	NavMeshModifierData *tnmmd = (NavMeshModifierData*) target;
+
+	//.todo - deep copy
+}
+
+/*
+static void (*drawFacesSolid_original)(DerivedMesh *dm, float (*partial_redraw_planes)[4],
+					   int fast, int (*setMaterial)(int, void *attribs)) = NULL;*/
+
+static void drawNavMeshColored(DerivedMesh *dm)
+{
+	int a, glmode;
+	MVert *mvert = (MVert *)CustomData_get_layer(&dm->vertData, CD_MVERT);
+	MFace *mface = (MFace *)CustomData_get_layer(&dm->faceData, CD_MFACE);
+	int* polygonIdx = (int*)CustomData_get_layer(&dm->faceData, CD_RECAST);
+	if (!polygonIdx)
+		return;
+	const float BLACK_COLOR[3] = {0.f, 0.f, 0.f};
+	float col[3];
+	/*
+	//UI_ThemeColor(TH_WIRE);
+	glDisable(GL_LIGHTING);
+	glLineWidth(2.0);
+	dm->drawEdges(dm, 0, 1);
+	glLineWidth(1.0);
+	glEnable(GL_LIGHTING);*/
+
+	glDisable(GL_LIGHTING);
+	if(GPU_buffer_legacy(dm) ) {
+		DEBUG_VBO( "Using legacy code. drawNavMeshColored\n" );
+		//glShadeModel(GL_SMOOTH);
+		glBegin(glmode = GL_QUADS);
+		for(a = 0; a < dm->numFaceData; a++, mface++) {
+			int new_glmode = mface->v4?GL_QUADS:GL_TRIANGLES;
+			int polygonIdx = *(int*)CustomData_get(&dm->faceData, a, CD_RECAST);
+			if (polygonIdx<=0)
+				memcpy(col, BLACK_COLOR, 3*sizeof(float));
+			else
+				intToCol(polygonIdx, col);
+
+			if(new_glmode != glmode) {
+				glEnd();
+				glBegin(glmode = new_glmode);
+			}
+			glColor3fv(col);
+			glVertex3fv(mvert[mface->v1].co);
+			glVertex3fv(mvert[mface->v2].co);
+			glVertex3fv(mvert[mface->v3].co);
+			if(mface->v4) {
+				glVertex3fv(mvert[mface->v4].co);
+			}
+		}
+		glEnd();
+	}
+	glEnable(GL_LIGHTING);
+}
+
+static void navDM_drawFacesTex(DerivedMesh *dm, int (*setDrawOptions)(MTFace *tface, MCol *mcol, int matnr))
+{
+	drawNavMeshColored(dm);
+}
+
+static void navDM_drawFacesSolid(DerivedMesh *dm,
+								float (*partial_redraw_planes)[4],
+								int fast, int (*setMaterial)(int, void *attribs))
+{
+	//drawFacesSolid_original(dm, partial_redraw_planes, fast, setMaterial);
+	drawNavMeshColored(dm);
+}
+
+static DerivedMesh *createNavMeshForVisualization(NavMeshModifierData *mmd,DerivedMesh *dm)
+{
+	DerivedMesh *result;
+	int maxFaces = dm->getNumFaces(dm);
+
+	result = CDDM_copy(dm);
+	if (!CustomData_has_layer(&result->faceData, CD_RECAST)) 
+	{
+		int *sourceRecastData = (int*)CustomData_get_layer(&dm->faceData, CD_RECAST);
+		CustomData_add_layer_named(&result->faceData, CD_RECAST, CD_DUPLICATE, 
+			sourceRecastData, maxFaces, "recastData");
+	}
+	int *recastData = (int*)CustomData_get_layer(&result->faceData, CD_RECAST);
+	result->drawFacesTex =  navDM_drawFacesTex;
+	result->drawFacesSolid = navDM_drawFacesSolid;
+	
+	
+	//process mesh
+	int vertsPerPoly=0, nverts=0, ndtris=0, npolys=0; 
+	float* verts=NULL;
+	unsigned short *dtris=NULL, *dmeshes=NULL, *polys=NULL;
+	int *dtrisToPolysMap=NULL, *dtrisToTrisMap=NULL, *trisToFacesMap=NULL;
+
+	bool res  = buildNavMeshDataByDerivedMesh(dm, vertsPerPoly, nverts, verts, ndtris, dtris,
+										npolys, dmeshes, polys, dtrisToPolysMap, dtrisToTrisMap,
+										trisToFacesMap);
+	if (res)
+	{
+		//invalidate concave polygon
+		for (size_t polyIdx=0; polyIdx<(size_t)npolys; polyIdx++)
+		{
+			unsigned short* poly = &polys[polyIdx*2*vertsPerPoly];
+			if (!polyIsConvex(poly, vertsPerPoly, verts))
+			{
+				//set negative polygon idx to all faces
+				unsigned short *dmesh = &dmeshes[4*polyIdx];
+				unsigned short tbase = dmesh[2];
+				unsigned short tnum = dmesh[3];
+				for (unsigned short ti=0; ti<tnum; ti++)
+				{
+					unsigned short triidx = dtrisToTrisMap[tbase+ti];
+					unsigned short faceidx = trisToFacesMap[triidx];
+					if (recastData[faceidx]>0)
+						recastData[faceidx] = -recastData[faceidx];
+				}				
+			}
+		}
+
+	}
+	else
+	{
+		printf("Error during creation polygon infos\n");
+	}
+
+	//clean up
+	if (verts!=NULL)
+		delete verts;
+	if (dtris!=NULL)
+		delete dtris;
+	if (dmeshes!=NULL)
+		delete dmeshes;
+	if (polys!=NULL)
+		delete polys;
+	if (dtrisToPolysMap!=NULL)
+		delete dtrisToPolysMap;
+	if (dtrisToTrisMap!=NULL)
+		delete dtrisToTrisMap;	
+	if (trisToFacesMap!=NULL)
+		delete trisToFacesMap;		
+
+	return result;
+}
+
+/*
+static int isDisabled(ModifierData *md, int useRenderParams)
+{
+	NavMeshModifierData *amd = (NavMeshModifierData*) md;
+	return false; 
+}*/
+
+
+
+static DerivedMesh *applyModifier(ModifierData *md, Object *ob, DerivedMesh *derivedData,
+								  int useRenderParams, int isFinalCalc)
+{
+	DerivedMesh *result = NULL;
+	NavMeshModifierData *nmmd = (NavMeshModifierData*) md;
+	bool hasRecastData = CustomData_has_layer(&derivedData->faceData, CD_RECAST)>0;
+	if (ob->body_type!=OB_BODY_TYPE_NAVMESH || !hasRecastData )
+	{
+		//convert to nav mesh object:
+		//1)set physics type
+		ob->gameflag &= ~OB_COLLISION;
+		ob->gameflag |= OB_NAVMESH;
+		ob->body_type = OB_BODY_TYPE_NAVMESH;
+		//2)add and init recast data layer
+		if (!hasRecastData)
+		{
+			Mesh* obmesh = (Mesh *)ob->data;
+			if (obmesh)
+			{
+				int numFaces = obmesh->totface;
+				CustomData_add_layer_named(&obmesh->fdata, CD_RECAST, CD_CALLOC, NULL, numFaces, "recastData");
+				int* recastData = (int*)CustomData_get_layer(&obmesh->fdata, CD_RECAST);
+				for (int i=0; i<numFaces; i++)
+				{
+					recastData[i] = i+1;
+				}
+				CustomData_add_layer_named(&derivedData->faceData, CD_RECAST, CD_REFERENCE, recastData, numFaces, "recastData");
+			}
+		}
+	}
+
+	result = createNavMeshForVisualization(nmmd, derivedData);
+	
+	return result;
+}
+
+
+ModifierTypeInfo modifierType_NavMesh = {
+	/* name */              "NavMesh",
+	/* structName */        "NavMeshModifierData",
+	/* structSize */        sizeof(NavMeshModifierData),
+	/* type */              eModifierTypeType_Constructive,
+	/* flags */             (ModifierTypeFlag) (eModifierTypeFlag_AcceptsMesh
+							| eModifierTypeFlag_Single),
+	/* copyData */          copyData,
+	/* deformVerts */       0,
+	/* deformMatrices */    0,
+	/* deformVertsEM */     0,
+	/* deformMatricesEM */  0,
+	/* applyModifier */     applyModifier,
+	/* applyModifierEM */   0,
+	/* initData */          initData,
+	/* requiredDataMask */  0,
+	/* freeData */          0,
+	/* isDisabled */        0,
+	/* updateDepgraph */    0,
+	/* dependsOnTime */     0,
+	/* foreachObjectLink */ 0,
+	/* foreachIDLink */     0,
+};
+
+};
\ No newline at end of file
diff --git a/source/blender/modifiers/intern/MOD_util.c b/source/blender/modifiers/intern/MOD_util.c
index 26e9d48cd0a..a2fe947a523 100644
--- a/source/blender/modifiers/intern/MOD_util.c
+++ b/source/blender/modifiers/intern/MOD_util.c
@@ -295,6 +295,7 @@ void modifier_type_init(ModifierTypeInfo *types[])
 	INIT_TYPE(Solidify);
 	INIT_TYPE(Screw);
 	INIT_TYPE(Warp);
+	INIT_TYPE(NavMesh);
 	INIT_TYPE(WeightVGEdit);
 	INIT_TYPE(WeightVGMix);
 	INIT_TYPE(WeightVGProximity);
diff --git a/source/creator/CMakeLists.txt b/source/creator/CMakeLists.txt
index bf2808ba4c0..243f51f04db 100644
--- a/source/creator/CMakeLists.txt
+++ b/source/creator/CMakeLists.txt
@@ -797,6 +797,7 @@ endif()
 		bf_intern_smoke
 		extern_minilzo
 		extern_lzma
+		extern_recastnavigation
 		ge_logic_ketsji
 		ge_phys_common
 		ge_logic
diff --git a/source/gameengine/Converter/BL_BlenderDataConversion.cpp b/source/gameengine/Converter/BL_BlenderDataConversion.cpp
index fcfc07e631e..d4b43cd7ac1 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
@@ -1741,7 +1744,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
@@ -2710,6 +2720,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 3a217ce9d74..039f454e870 100644
--- a/source/gameengine/Converter/CMakeLists.txt
+++ b/source/gameengine/Converter/CMakeLists.txt
@@ -56,6 +56,7 @@ set(INC
 	../../../intern/guardedalloc
 	../../../intern/moto/include
 	../../../intern/string
+	../../../extern/recastnavigation/Detour/Include
 )
 
 set(INC_SYS
diff --git a/source/gameengine/Converter/KX_ConvertActuators.cpp b/source/gameengine/Converter/KX_ConvertActuators.cpp
index 6ba178cbb2f..a14e5fb5449 100644
--- a/source/gameengine/Converter/KX_ConvertActuators.cpp
+++ b/source/gameengine/Converter/KX_ConvertActuators.cpp
@@ -72,6 +72,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"
@@ -100,6 +101,7 @@
 #include "BL_ActionActuator.h"
 #include "BL_ShapeActionActuator.h"
 #include "BL_ArmatureActuator.h"
+#include "RNA_access.h"
 #include "BL_Action.h"
 /* end of blender include block */
 
@@ -1064,6 +1066,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 0ae22d548c5..e155677e522 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 += ' #extern/Eigen2'
 
 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 99c9fb25a65..6846da5b019 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
@@ -90,9 +93,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
@@ -120,6 +125,7 @@ set(SRC
 	KX_SceneActuator.cpp
 	KX_SoundActuator.cpp
 	KX_StateActuator.cpp
+	KX_SteeringActuator.cpp
 	KX_TimeCategoryLogger.cpp
 	KX_TimeLogger.cpp
 	KX_TouchEventManager.cpp
@@ -167,9 +173,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
@@ -199,6 +207,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 6adaea2d6ad..ae8d7094015 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 "BL_ActionManager.h"
 
@@ -110,7 +111,8 @@ KX_GameObject::KX_GameObject(
       m_xray(false),
       m_pHitObject(NULL),
       m_actionManager(NULL),
-      m_isDeformable(false)
+      m_isDeformable(false),
+      m_pObstacleSimulation(NULL)
 #ifdef WITH_PYTHON
     , m_attr_dict(NULL)
 #endif
@@ -157,6 +159,12 @@ KX_GameObject::~KX_GameObject()
 	{
 		delete m_pGraphicController;
 	}
+
+	if (m_pObstacleSimulation)
+	{
+		m_pObstacleSimulation->DestroyObstacleForObj(this);
+	}
+
 	if (m_actionManager)
 	{
 		KX_GetActiveScene()->RemoveAnimatedObject(this);
@@ -428,6 +436,14 @@ void KX_GameObject::ProcessReplica()
 		m_actionManager = new BL_ActionManager(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 6e79914172b..655bc9ff080 100644
--- a/source/gameengine/Ketsji/KX_GameObject.h
+++ b/source/gameengine/Ketsji/KX_GameObject.h
@@ -65,6 +65,7 @@ class PHY_IGraphicController;
 class PHY_IPhysicsEnvironment;
 class BL_ActionManager;
 struct Object;
+class KX_ObstacleSimulation;
 struct bAction;
 
 #ifdef WITH_PYTHON
@@ -115,6 +116,9 @@ protected:
 
 	MT_CmMatrix4x4						m_OpenGL_4x4Matrix;
 
+	KX_ObstacleSimulation*				m_pObstacleSimulation;
+
+
 	// The action manager is used to play/stop/update actions
 	BL_ActionManager*				m_actionManager;
 
@@ -864,6 +868,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 ca67333166c..db919b7bc5a 100644
--- a/source/gameengine/Ketsji/KX_KetsjiEngine.cpp
+++ b/source/gameengine/Ketsji/KX_KetsjiEngine.cpp
@@ -84,6 +84,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
@@ -1343,7 +1345,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 f14d73cb990..7ddaa97770b 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"
@@ -181,6 +183,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;
@@ -1655,6 +1664,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);
+
 	/* BL_Action play modes */
 	KX_MACRO_addTypesToDict(d, KX_ACTION_MODE_PLAY, BL_Action::ACT_MODE_PLAY);
 	KX_MACRO_addTypesToDict(d, KX_ACTION_MODE_LOOP, BL_Action::ACT_MODE_LOOP);
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 7c76ab01e93..bdc30810b9e 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"
@@ -214,6 +215,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;
@@ -236,6 +250,9 @@ KX_Scene::~KX_Scene()
 		this->RemoveObject(parentobj);
 	}
 
+	if (m_obstacleSimulation)
+		delete m_obstacleSimulation;
+
 	if(m_objectlist)
 		m_objectlist->Release();
 
@@ -1545,6 +1562,10 @@ void KX_Scene::LogicEndFrame()
 		obj->Release();
 		RemoveObject(obj);
 	}
+
+	//prepare obstacle simulation for new frame
+	if (m_obstacleSimulation)
+		m_obstacleSimulation->UpdateObstacles();
 }
 
 
@@ -1977,6 +1998,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),
@@ -2301,6 +2324,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 499861bce50..5954d5465ba 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"
@@ -293,6 +294,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,
@@ -585,6 +589,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 ---------------------------------------------------- */
@@ -597,6 +603,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 c5509dd7de8..7c9785c24e7 100644
--- a/source/gameengine/Ketsji/SConscript
+++ b/source/gameengine/Ketsji/SConscript
@@ -20,6 +20,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 c46ebf742a0..877a7219a1c 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 50d034a5a5a..6ad9e591474 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
  */
@@ -354,9 +358,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
@@ -368,29 +372,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 61568df91eb..c0e02f6df77 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;
 };
 
@@ -256,18 +261,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);