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.

31 files changed, 1973 insertions, 19 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);