svn merge -r40075:40104 https://svn.blender.org/svnroot/bf-blender/trunk/blender

38 files changed, 2123 insertions, 133 deletions

diff --git a/source/blender/blenkernel/intern/customdata.c b/source/blender/blenkernel/intern/customdata.c
index f47e38f6d17..fe10fffb665 100644
--- a/source/blender/blenkernel/intern/customdata.c
+++ b/source/blender/blenkernel/intern/customdata.c
@@ -1098,15 +1098,19 @@ static const LayerTypeInfo LAYERTYPEINFO[CD_NUMTYPES] = {
 	{sizeof(MLoopCol), "MLoopCol", 1, "WeightLoopCol", NULL, NULL, layerInterp_mloopcol, NULL,
 	 layerDefault_mloopcol, layerEqual_mloopcol, layerMultiply_mloopcol, layerInitMinMax_mloopcol,
 	 layerAdd_mloopcol, layerDoMinMax_mloopcol, layerCopyValue_mloopcol},
+	/* 24: CD_RECAST */
+	{sizeof(MRecast), "MRecast", 1,"Recast",NULL,NULL,NULL,NULL}
 };
 
+/* note, numbers are from trunk and need updating for bmesh */
+
 static const char *LAYERTYPENAMES[CD_NUMTYPES] = {
-	"CDMVert", "CDMSticky", "CDMDeformVert", "CDMEdge", "CDMFace", "CDMTFace",
-	"CDMCol", "CDOrigIndex", "CDNormal", "CDFlags","CDMFloatProperty",
-	"CDMIntProperty","CDMStringProperty", "CDOrigSpace", "CDOrco", "CDMTexPoly", "CDMLoopUV",
-	"CDMloopCol", "CDTangent", "CDMDisps", "CDWeightMCol", "CDMPoly", 
-	"CDMLoop", "CDMClothOrco", "CDMLoopCol", "CDIDCol", "CDTextureCol",
-	"CDShapeKeyIndex", "CDShapeKey", "CDBevelWeight", "CDSubSurfCrease"
+	/*   0-4 */ "CDMVert", "CDMSticky", "CDMDeformVert", "CDMEdge", "CDMFace", "CDMTFace",
+	/*   5-9 */ "CDMCol", "CDOrigIndex", "CDNormal", "CDFlags","CDMFloatProperty",
+	/* 10-14 */ "CDMIntProperty","CDMStringProperty", "CDOrigSpace", "CDOrco", "CDMTexPoly", "CDMLoopUV",
+	/* 15-19 */ "CDMloopCol", "CDTangent", "CDMDisps", "CDWeightMCol", "CDMPoly", 
+	/* 20-24 */ "CDMLoop", "CDMClothOrco", "CDMLoopCol", "CDIDCol", "CDTextureCol",
+	/* ?-? */ "CDShapeKeyIndex", "CDShapeKey", "CDBevelWeight", "CDSubSurfCrease", "CDMRecast"
 };
 
 
@@ -1117,18 +1121,18 @@ const CustomDataMask CD_MASK_MESH =
 	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_MLOOPUV | CD_MASK_MLOOPCOL | CD_MASK_MPOLY | CD_MASK_MLOOP |
-	CD_MASK_MTEXPOLY | CD_MASK_NORMAL | CD_MASK_MDISPS;
+	CD_MASK_MTEXPOLY | CD_MASK_NORMAL | CD_MASK_MDISPS | CD_MASK_RECAST;
 const CustomDataMask CD_MASK_EDITMESH =
 	CD_MASK_MSTICKY | CD_MASK_MDEFORMVERT | CD_MASK_MTFACE | CD_MASK_MLOOPUV |
 	CD_MASK_MLOOPCOL | CD_MASK_MTEXPOLY | CD_MASK_SHAPE_KEYINDEX |
 	CD_MASK_MCOL|CD_MASK_PROP_FLT | CD_MASK_PROP_INT | CD_MASK_PROP_STR |
-	CD_MASK_MDISPS | CD_MASK_SHAPEKEY;
+	CD_MASK_MDISPS | CD_MASK_SHAPEKEY | 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_MLOOPUV | CD_MASK_MLOOPCOL | CD_MASK_MTEXPOLY | CD_MASK_WEIGHT_MLOOPCOL |
 	CD_MASK_PROP_STR | CD_MASK_ORIGSPACE | CD_MASK_ORCO | CD_MASK_TANGENT | 
-	CD_MASK_WEIGHT_MCOL | CD_MASK_NORMAL | CD_MASK_SHAPEKEY;
+	CD_MASK_WEIGHT_MCOL | CD_MASK_NORMAL | CD_MASK_SHAPEKEY | CD_MASK_RECAST;
 const CustomDataMask CD_MASK_BMESH = CD_MASK_MLOOPUV | CD_MASK_MLOOPCOL | CD_MASK_MTEXPOLY |
 	CD_MASK_MSTICKY | CD_MASK_MDEFORMVERT | CD_MASK_PROP_FLT | CD_MASK_PROP_INT | 
 	CD_MASK_PROP_STR | CD_MASK_SHAPEKEY | CD_MASK_SHAPE_KEYINDEX | CD_MASK_MDISPS;
diff --git a/source/blender/blenkernel/intern/object.c b/source/blender/blenkernel/intern/object.c
index 3bd508af4e2..08c36d76b8e 100644
--- a/source/blender/blenkernel/intern/object.c
+++ b/source/blender/blenkernel/intern/object.c
@@ -1083,6 +1083,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 acb4c0a617f..36048cef5b8 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -3962,6 +3962,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;
 			}
 			
@@ -11681,6 +11686,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;
@@ -12084,6 +12106,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! */
 
@@ -12988,6 +13047,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 4ae7a44a0db..2b0e4ddf024 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/collada/AnimationExporter.cpp b/source/blender/collada/AnimationExporter.cpp
index 498ccb5709d..2ea10111bb9 100644
--- a/source/blender/collada/AnimationExporter.cpp
+++ b/source/blender/collada/AnimationExporter.cpp
@@ -58,7 +58,7 @@ void AnimationExporter::operator() (Object *ob)
 {
 	FCurve *fcu;
 	char * transformName ;
-	bool isMatAnim = false;
+	/* bool isMatAnim = false; */ /* UNUSED */
 
 	//Export transform animations
 	if(ob->adt && ob->adt->action)
@@ -125,7 +125,7 @@ void AnimationExporter::operator() (Object *ob)
 		if (!ma) continue;
 		if(ma->adt && ma->adt->action)
 		{
-			isMatAnim = true;
+			/* isMatAnim = true; */
 			fcu = (FCurve*)ma->adt->action->curves.first;
 			while (fcu) {
 				transformName = extract_transform_name( fcu->rna_path );
diff --git a/source/blender/collada/ArmatureImporter.cpp b/source/blender/collada/ArmatureImporter.cpp
index 19fa54c5044..ae25d343d36 100644
--- a/source/blender/collada/ArmatureImporter.cpp
+++ b/source/blender/collada/ArmatureImporter.cpp
@@ -576,7 +576,7 @@ void ArmatureImporter::set_pose ( Object * ob_arm ,  COLLADAFW::Node * root_node
    float obmat[4][4];
 
 	float ax[3];
-	float angle = NULL;
+	float angle = 0.0f;
 	
 	// object-space
 	get_node_mat(obmat, root_node, NULL, NULL);
diff --git a/source/blender/collada/SceneExporter.cpp b/source/blender/collada/SceneExporter.cpp
index 5109df0bb6a..a561d18c6e3 100644
--- a/source/blender/collada/SceneExporter.cpp
+++ b/source/blender/collada/SceneExporter.cpp
@@ -126,7 +126,7 @@ void SceneExporter::writeNodes(Object *ob, Scene *sce)
 		if((ob->transflag & OB_DUPLIGROUP) == OB_DUPLIGROUP && ob->dup_group) {
 			GroupObject *go = NULL;
 			Group *gr = ob->dup_group;
-			printf("group detected %u\n", gr);
+			/* printf("group detected '%s'\n", gr->id.name+2); */
 			for(go = (GroupObject*)(gr->gobject.first); go; go=go->next) {
 				printf("\t%s\n", go->ob->id.name);
 			}
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..71b60cc4e4a
--- /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
diff --git a/source/blender/editors/include/ED_object.h b/source/blender/editors/include/ED_object.h
index 2cda5e070d3..5a2a4765c74 100644
--- a/source/blender/editors/include/ED_object.h
+++ b/source/blender/editors/include/ED_object.h
@@ -139,8 +139,8 @@ void ED_setflagsLatt(struct Object *obedit, int flag);
 /* object_modifier.c */
 enum {
 	MODIFIER_APPLY_DATA=1,
-	MODIFIER_APPLY_SHAPE,
-} eModifier_Apply_Mode;
+	MODIFIER_APPLY_SHAPE
+};
 
 struct ModifierData *ED_object_modifier_add(struct ReportList *reports, struct Main *bmain, struct Scene *scene, struct Object *ob, const char *name, int type);
 int ED_object_modifier_remove(struct ReportList *reports, struct Main *bmain, struct Scene *scene, struct Object *ob, struct ModifierData *md);
diff --git a/source/blender/editors/interface/interface_widgets.c b/source/blender/editors/interface/interface_widgets.c
index c06e26eecaa..d9d75c34a94 100644
--- a/source/blender/editors/interface/interface_widgets.c
+++ b/source/blender/editors/interface/interface_widgets.c
@@ -79,10 +79,10 @@
 /* it has outline, back, and two optional tria meshes */
 
 typedef struct uiWidgetTrias {
-	int tot;
+	unsigned int tot;
 	
 	float vec[32][2];
-	int (*index)[3];
+	unsigned int (*index)[3];
 	
 } uiWidgetTrias;
 
@@ -146,7 +146,7 @@ static float jit[8][2]= {{0.468813 , -0.481430}, {-0.155755 , -0.352820},
 static float num_tria_vert[3][2]= { 
 {-0.352077, 0.532607}, {-0.352077, -0.549313}, {0.330000, -0.008353}};
 
-static int num_tria_face[1][3]= {
+static unsigned int num_tria_face[1][3]= {
 {0, 1, 2}};
 
 static float scroll_circle_vert[16][2]= {
@@ -155,7 +155,7 @@ static float scroll_circle_vert[16][2]= {
 {-0.382683, -0.923880}, {0.000000, -1.000000}, {0.382684, -0.923880}, {0.707107, -0.707107},
 {0.923880, -0.382684}, {1.000000, -0.000000}, {0.923880, 0.382683}, {0.707107, 0.707107}};
 
-static int scroll_circle_face[14][3]= {
+static unsigned int scroll_circle_face[14][3]= {
 {0, 1, 2}, {2, 0, 3}, {3, 0, 15}, {3, 15, 4}, {4, 15, 14}, {4, 14, 5}, {5, 14, 13}, {5, 13, 6}, 
 {6, 13, 12}, {6, 12, 7}, {7, 12, 11}, {7, 11, 8}, {8, 11, 10}, {8, 10, 9}};
 
@@ -163,13 +163,13 @@ static float menu_tria_vert[6][2]= {
 {-0.41, 0.16}, {0.41, 0.16}, {0, 0.82}, 
 {0, -0.82}, {-0.41, -0.16}, {0.41, -0.16}};
 
-static int menu_tria_face[2][3]= {{2, 0, 1}, {3, 5, 4}};
+static unsigned int menu_tria_face[2][3]= {{2, 0, 1}, {3, 5, 4}};
 
 static float check_tria_vert[6][2]= {
 {-0.578579, 0.253369}, 	{-0.392773, 0.412794}, 	{-0.004241, -0.328551}, 
 {-0.003001, 0.034320}, 	{1.055313, 0.864744}, 	{0.866408, 1.026895}};
 
-static int check_tria_face[4][3]= {
+static unsigned int check_tria_face[4][3]= {
 {3, 2, 4}, {3, 4, 5}, {1, 0, 3}, {0, 2, 3}};
 
 GLubyte checker_stipple_sml[32*32/8] =
@@ -533,12 +533,9 @@ static void widget_scroll_circle(uiWidgetTrias *tria, rcti *rect, float triasize
 static void widget_trias_draw(uiWidgetTrias *tria)
 {
 	glEnableClientState(GL_VERTEX_ARRAY);
-	glEnableClientState(GL_INDEX_ARRAY);
-	glIndexPointer(GL_INT, 0, tria->index);
 	glVertexPointer(2, GL_FLOAT, 0, tria->vec);
-	glDrawArrays(GL_TRIANGLES, 0, tria->tot*3);
+	glDrawElements(GL_TRIANGLES, tria->tot*3, GL_UNSIGNED_INT, tria->index);
 	glDisableClientState(GL_VERTEX_ARRAY);
-	glDisableClientState(GL_INDEX_ARRAY);
 }
 
 static void widget_menu_trias(uiWidgetTrias *tria, rcti *rect)
diff --git a/source/blender/editors/object/CMakeLists.txt b/source/blender/editors/object/CMakeLists.txt
index 58496a914cb..27308bc9e07 100644
--- a/source/blender/editors/object/CMakeLists.txt
+++ b/source/blender/editors/object/CMakeLists.txt
@@ -34,6 +34,7 @@ set(INC
 	../../render/extern/include
 	../../windowmanager
 	../../../../intern/guardedalloc
+	../../../../extern/recastnavigation/Recast/Include
 )
 
 set(INC_SYS
@@ -59,8 +60,18 @@ set(SRC
 	object_intern.h
 )
 
+if(WITH_GAMEENGINE)
+	list(APPEND SRC
+		object_navmesh.cpp
+	)
+endif()
+
 if(WITH_PYTHON)
 	add_definitions(-DWITH_PYTHON)
 endif()
 
+if(WITH_GAMEENGINE)
+	add_definitions(-DWITH_GAMEENGINE)
+endif()
+
 blender_add_lib(bf_editor_object "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/source/blender/editors/object/SConscript b/source/blender/editors/object/SConscript
index d3e7df92471..4607cc4b1bf 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 ../../bmesh'
 incs += ' ../../render/extern/include ../../gpu' # for object_bake.c
+incs += ' #extern/recastnavigation/Recast/Include'
 
 defs = []
 
@@ -19,5 +20,8 @@ if env['OURPLATFORM'] in ('win32-vc', 'win32-mingw', 'linuxcross', 'win64-vc'):
 
 if env['WITH_BF_PYTHON']:
     defs.append('WITH_PYTHON')
+  
+if env['WITH_BF_GAMEENGINE']:
+    defs.append('WITH_GAMEENGINE')
 
 env.BlenderLib ( 'bf_editors_object', sources, Split(incs), defs, libtype=['core'], priority=[35] )
diff --git a/source/blender/editors/object/object_intern.h b/source/blender/editors/object/object_intern.h
index efcb618b868..44cf3adcd32 100644
--- a/source/blender/editors/object/object_intern.h
+++ b/source/blender/editors/object/object_intern.h
@@ -224,5 +224,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..d0768d30236
--- /dev/null
+++ b/source/blender/editors/object/object_navmesh.cpp
@@ -0,0 +1,628 @@
+/**
+* $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;
+	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);
+	}
+
+	//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 11d64882f29..7cfc7618415 100644
--- a/source/blender/editors/object/object_ops.c
+++ b/source/blender/editors/object/object_ops.c
@@ -215,6 +215,11 @@ void ED_operatortypes_object(void)
 
 	WM_operatortype_append(OBJECT_OT_test_multires);
 
+#ifdef WITH_GAMEENGINE
+	WM_operatortype_append(OBJECT_OT_create_navmesh);
+	WM_operatortype_append(OBJECT_OT_assign_navpolygon);
+	WM_operatortype_append(OBJECT_OT_assign_new_navpolygon);
+#endif
 }
 
 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/space_view3d/drawarmature.c b/source/blender/editors/space_view3d/drawarmature.c
index ecf5df4af7c..4aec1a8e61c 100644
--- a/source/blender/editors/space_view3d/drawarmature.c
+++ b/source/blender/editors/space_view3d/drawarmature.c
@@ -85,7 +85,7 @@ enum {
 	PCHAN_COLOR_SPHEREBONE_BASE,	/* for the 'stick' of sphere (envelope) bones */
 	PCHAN_COLOR_SPHEREBONE_END,		/* for the ends of sphere (envelope) bones */
 	PCHAN_COLOR_LINEBONE			/* for the middle of line-bones */
-};	
+};
 
 /* This function sets the color-set for coloring a certain bone */
 static void set_pchan_colorset (Object *ob, bPoseChannel *pchan)
@@ -437,43 +437,64 @@ static void draw_bonevert_solid(void)
 	glCallList(displist);
 }
 
+static float bone_octahedral_verts[6][3]= {
+    { 0.0f, 0.0f,  0.0f},
+    { 0.1f, 0.1f,  0.1f},
+    { 0.1f, 0.1f, -0.1f},
+    {-0.1f, 0.1f, -0.1f},
+    {-0.1f, 0.1f,  0.1f},
+    { 0.0f, 1.0f,  0.0f}
+};
+
+static unsigned int bone_octahedral_wire_sides[8]= {0, 1, 5, 3, 0, 4, 5, 2};
+static unsigned int bone_octahedral_wire_square[8]= {1, 2, 3, 4, 1};
+
+static unsigned int bone_octahedral_solid_tris[8][3]= {
+    {2, 1, 0}, /* bottom */
+    {3, 2, 0},
+    {4, 3, 0},
+    {1, 4, 0},
+
+    {5, 1, 2}, /* top */
+    {5, 2, 3},
+    {5, 3, 4},
+    {5, 4, 1}
+};
+
+/* aligned with bone_octahedral_solid_tris */
+static float bone_octahedral_solid_normals[8][3]= {
+    { 0.70710683f, -0.70710683f,  0.00000000f},
+    {-0.00000000f, -0.70710683f, -0.70710683f},
+    {-0.70710683f, -0.70710683f,  0.00000000f},
+    { 0.00000000f, -0.70710683f,  0.70710683f},
+    { 0.99388373f,  0.11043154f, -0.00000000f},
+    { 0.00000000f,  0.11043154f, -0.99388373f},
+    {-0.99388373f,  0.11043154f,  0.00000000f},
+    { 0.00000000f,  0.11043154f,  0.99388373f}
+};
+
 static void draw_bone_octahedral(void)
 {
 	static GLuint displist=0;
 	
 	if (displist == 0) {
-		float vec[6][3];	
-		
 		displist= glGenLists(1);
 		glNewList(displist, GL_COMPILE);
-		
-		vec[0][0]= vec[0][1]= vec[0][2]= 0.0f;
-		vec[5][0]= vec[5][2]= 0.0f; vec[5][1]= 1.0f;
-		
-		vec[1][0]= 0.1f; vec[1][2]= 0.1f; vec[1][1]= 0.1f;
-		vec[2][0]= 0.1f; vec[2][2]= -0.1f; vec[2][1]= 0.1f;
-		vec[3][0]= -0.1f; vec[3][2]= -0.1f; vec[3][1]= 0.1f;
-		vec[4][0]= -0.1f; vec[4][2]= 0.1f; vec[4][1]= 0.1f;
-		
+
 		/*	Section 1, sides */
-		glBegin(GL_LINE_LOOP);
-		glVertex3fv(vec[0]);
-		glVertex3fv(vec[1]);
-		glVertex3fv(vec[5]);
-		glVertex3fv(vec[3]);
-		glVertex3fv(vec[0]);
-		glVertex3fv(vec[4]);
-		glVertex3fv(vec[5]);
-		glVertex3fv(vec[2]);
-		glEnd();
-		
+		glEnableClientState(GL_VERTEX_ARRAY);
+		glVertexPointer(3, GL_FLOAT, 0, bone_octahedral_verts);
+		glDrawElements(GL_LINE_LOOP,
+		               sizeof(bone_octahedral_wire_sides)/sizeof(*bone_octahedral_wire_sides),
+		               GL_UNSIGNED_INT,
+		               bone_octahedral_wire_sides);
+
 		/*	Section 1, square */
-		glBegin(GL_LINE_LOOP);
-		glVertex3fv(vec[1]);
-		glVertex3fv(vec[2]);
-		glVertex3fv(vec[3]);
-		glVertex3fv(vec[4]);
-		glEnd();
+		glDrawElements(GL_LINE_LOOP,
+		               sizeof(bone_octahedral_wire_square)/sizeof(*bone_octahedral_wire_square),
+		               GL_UNSIGNED_INT,
+		               bone_octahedral_wire_square);
+		glDisableClientState(GL_VERTEX_ARRAY);
 		
 		glEndList();
 	}
@@ -484,59 +505,34 @@ static void draw_bone_octahedral(void)
 static void draw_bone_solid_octahedral(void)
 {
 	static GLuint displist=0;
-	
+
 	if (displist == 0) {
-		float vec[6][3], nor[3];	
-		
+		int i;
+
 		displist= glGenLists(1);
 		glNewList(displist, GL_COMPILE);
-		
-		vec[0][0]= vec[0][1]= vec[0][2]= 0.0f;
-		vec[5][0]= vec[5][2]= 0.0f; vec[5][1]= 1.0f;
-		
-		vec[1][0]= 0.1f; vec[1][2]= 0.1f; vec[1][1]= 0.1f;
-		vec[2][0]= 0.1f; vec[2][2]= -0.1f; vec[2][1]= 0.1f;
-		vec[3][0]= -0.1f; vec[3][2]= -0.1f; vec[3][1]= 0.1f;
-		vec[4][0]= -0.1f; vec[4][2]= 0.1f; vec[4][1]= 0.1f;
-		
-		
-		glBegin(GL_TRIANGLES);
-		/* bottom */
-		normal_tri_v3( nor,vec[2], vec[1], vec[0]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[2]); glVertex3fv(vec[1]); glVertex3fv(vec[0]);
-		
-		normal_tri_v3( nor,vec[3], vec[2], vec[0]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[3]); glVertex3fv(vec[2]); glVertex3fv(vec[0]);
-		
-		normal_tri_v3( nor,vec[4], vec[3], vec[0]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[4]); glVertex3fv(vec[3]); glVertex3fv(vec[0]);
 
-		normal_tri_v3( nor,vec[1], vec[4], vec[0]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[1]); glVertex3fv(vec[4]); glVertex3fv(vec[0]);
+#if 1
+		glBegin(GL_TRIANGLES);
+		for(i= 0; i < 8; i++) {
+			glNormal3fv(bone_octahedral_solid_normals[i]);
+			glVertex3fv(bone_octahedral_verts[bone_octahedral_solid_tris[i][0]]);
+			glVertex3fv(bone_octahedral_verts[bone_octahedral_solid_tris[i][1]]);
+			glVertex3fv(bone_octahedral_verts[bone_octahedral_solid_tris[i][2]]);
+		}
 
-		/* top */
-		normal_tri_v3( nor,vec[5], vec[1], vec[2]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[5]); glVertex3fv(vec[1]); glVertex3fv(vec[2]);
-		
-		normal_tri_v3( nor,vec[5], vec[2], vec[3]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[5]); glVertex3fv(vec[2]); glVertex3fv(vec[3]);
-		
-		normal_tri_v3( nor,vec[5], vec[3], vec[4]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[5]); glVertex3fv(vec[3]); glVertex3fv(vec[4]);
-		
-		normal_tri_v3( nor,vec[5], vec[4], vec[1]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[5]); glVertex3fv(vec[4]); glVertex3fv(vec[1]);
-		
 		glEnd();
-		
+
+#else	/* not working because each vert needs a different normal */
+		glEnableClientState(GL_NORMAL_ARRAY);
+		glEnableClientState(GL_VERTEX_ARRAY);
+		glNormalPointer(GL_FLOAT, 0, bone_octahedral_solid_normals);
+		glVertexPointer(3, GL_FLOAT, 0, bone_octahedral_verts);
+		glDrawElements(GL_TRIANGLES, sizeof(bone_octahedral_solid_tris)/sizeof(unsigned int), GL_UNSIGNED_INT, bone_octahedral_solid_tris);
+		glDisableClientState(GL_NORMAL_ARRAY);
+		glDisableClientState(GL_VERTEX_ARRAY);
+#endif
+
 		glEndList();
 	}
 
diff --git a/source/blender/editors/util/CMakeLists.txt b/source/blender/editors/util/CMakeLists.txt
index 843af272362..c1e618fd4cb 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
 	../../bmesh
 	../../makesdna
 	../../makesrna
@@ -63,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
@@ -89,4 +91,10 @@ set(SRC
 	../include/UI_view2d.h
 )
 
+if(WITH_GAMEENGINE)
+	list(APPEND SRC
+		navmesh_conversion.cpp
+	)
+endif()
+
 blender_add_lib(bf_editor_util "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/source/blender/editors/util/SConscript b/source/blender/editors/util/SConscript
index 2d5ee84333b..04d783e1ee1 100644
--- a/source/blender/editors/util/SConscript
+++ b/source/blender/editors/util/SConscript
@@ -1,11 +1,15 @@
 #!/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 ../../bmesh'
+incs += ' #extern/recastnavigation/Recast/Include'
 incs += ' ../../blenloader'
 
-env.BlenderLib ( 'bf_editors_util', sources, Split(incs), [], libtype=['core'], priority=[130] )
+if not env['WITH_BF_GAMEENGINE']:
+    sources.remove('navmesh_conversion.cpp')
+
+env.BlenderLib ( 'bf_editors_util', sources, Split(incs), [], libtype=['core','player'], priority=[330,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..8b3fee59e1a
--- /dev/null
+++ b/source/blender/editors/util/navmesh_conversion.cpp
@@ -0,0 +1,454 @@
+/**
+* $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)
+{
+	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];
+			}
+		}
+	}
+
+returnLabel:
+	delete newPoly;
+	return true;
+}
+
+struct SortContext
+{
+	const int* recastData;
+	const int* trisToFacesMap;
+};
+#if defined(_MSC_VER)
+static int compareByData(void* data, const void * a, const void * b)
+#elif defined(__APPLE__) || defined(__FreeBSD__)
+static int compareByData(void* data, const void * a, const void * b)
+#else
+static int compareByData(const void * a, const void * b, void* data)
+#endif
+{
+	const SortContext* context = (const 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;
+#if defined(_MSC_VER)
+	qsort_s(trisMapping, ntris, sizeof(int), compareByData, &context);
+#elif defined(__APPLE__) || defined(__FreeBSD__)
+	qsort_r(trisMapping, ntris, sizeof(int), &context, compareByData);
+#else
+	qsort_r(trisMapping, ntris, sizeof(int), compareByData, &context);
+#endif
+	//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;
+}
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 0760ba0542f..eba484b84b7 100644
--- a/source/blender/makesdna/DNA_customdata_types.h
+++ b/source/blender/makesdna/DNA_customdata_types.h
@@ -100,7 +100,8 @@ typedef struct CustomData {
 #define CD_BWEIGHT		28
 #define CD_CREASE		29
 #define CD_WEIGHT_MLOOPCOL	30
-#define CD_NUMTYPES		31
+#define CD_RECAST		31
+#define CD_NUMTYPES		32
 
 /* Bits for CustomDataMask */
 #define CD_MASK_MVERT		(1 << CD_MVERT)
@@ -130,6 +131,7 @@ typedef struct CustomData {
 #define CD_MASK_SHAPE_KEYINDEX	(1 << CD_SHAPE_KEYINDEX)
 #define CD_MASK_SHAPEKEY	(1 << CD_SHAPEKEY)
 #define CD_MASK_CLOTH_ORCO	(1 << CD_CLOTH_ORCO)
+#define CD_MASK_RECAST		(1 << CD_RECAST)
 
 /* derivedmesh wants CustomDataMask for weightpaint too, is not customdata though */
 #define CD_MASK_WEIGHTPAINT	(1 << CD_WEIGHTPAINT)
diff --git a/source/blender/makesdna/DNA_meshdata_types.h b/source/blender/makesdna/DNA_meshdata_types.h
index dade6fbf332..27ebc5e489d 100644
--- a/source/blender/makesdna/DNA_meshdata_types.h
+++ b/source/blender/makesdna/DNA_meshdata_types.h
@@ -209,6 +209,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 2a4eb3d4045..b683da9e256 100644
--- a/source/blender/makesdna/DNA_modifier_types.h
+++ b/source/blender/makesdna/DNA_modifier_types.h
@@ -74,6 +74,9 @@ typedef enum ModifierType {
 	eModifierType_WeightVGEdit,
 	eModifierType_WeightVGMix,
 	eModifierType_WeightVGProximity,
+	eModifierType_NavMesh,
+
+	/* BMESH ONLY - keeps getting bumped by new modifiers in trunk */
 	eModifierType_NgonInterp,
 	NUM_MODIFIER_TYPES
 } ModifierType;
@@ -756,6 +759,10 @@ typedef struct NgonInterpModifierData {
 	int		resolution, pad0;
 } NgonInterpModifierData;
 
+typedef struct NavMeshModifierData {
+	ModifierData modifier;
+} NavMeshModifierData;
+
 typedef struct WarpModifierData {
 	ModifierData modifier;
 	/* keep in sync with MappingInfoModifierData */
diff --git a/source/blender/makesdna/DNA_object_types.h b/source/blender/makesdna/DNA_object_types.h
index 45fe957806f..e70110d2694 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..5f20432d6f8 100644
--- a/source/blender/makesdna/DNA_scene_types.h
+++ b/source/blender/makesdna/DNA_scene_types.h
@@ -426,8 +426,38 @@ 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 {
 
+	/*  standalone player */
+	struct GameFraming framing;
+	short fullscreen, xplay, yplay, freqplay;
+	short depth, attrib, rt1, rt2;
+
+	/* stereo/dome mode */
+	struct GameDome dome;
+	short stereoflag, stereomode;
+	short pad2, pad3;
+	float eyeseparation, pad1;
+	RecastData recastData;
+
+
 	/* physics (it was in world)*/
 	float gravity; /*Gravitation constant for the game world*/
 
@@ -440,21 +470,12 @@ 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;
-
-	/*  standalone player */
-	struct GameFraming framing;
-	short fullscreen, xplay, yplay, freqplay;
-	short depth, attrib, rt1, rt2;
-
-	/* stereo/dome mode */
-	struct GameDome dome;
-	short stereoflag, stereomode;
-	short pad2, pad3;
-	float eyeseparation, pad1;
+	short obstacleSimulation;
+	float levelHeight;
 } 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 ef67b0e684e..2fc9daeabbf 100644
--- a/source/blender/makesrna/intern/rna_modifier.c
+++ b/source/blender/makesrna/intern/rna_modifier.c
@@ -91,6 +91,7 @@ EnumPropertyItem modifier_type_items[] ={
 	{eModifierType_Collision, "COLLISION", ICON_MOD_PHYSICS, "Collision", ""},
 	{eModifierType_Explode, "EXPLODE", ICON_MOD_EXPLODE, "Explode", ""},
 	{eModifierType_Fluidsim, "FLUID_SIMULATION", ICON_MOD_FLUIDSIM, "Fluid Simulation", ""},
+	{eModifierType_NavMesh, "NAVMESH", ICON_MOD_PHYSICS, "Navigation mesh", ""},
 	{eModifierType_ParticleInstance, "PARTICLE_INSTANCE", ICON_MOD_PARTICLES, "Particle Instance", ""},
 	{eModifierType_ParticleSystem, "PARTICLE_SYSTEM", ICON_MOD_PARTICLES, "Particle System", ""},
 	{eModifierType_Smoke, "SMOKE", ICON_MOD_SMOKE, "Smoke", ""},
@@ -191,6 +192,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:
@@ -2490,6 +2493,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; */ /* UNUSED */
+
+	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[] = {
@@ -2900,6 +2914,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 e094a4099fa..fb49d700306 100644
--- a/source/blender/makesrna/intern/rna_object.c
+++ b/source/blender/makesrna/intern/rna_object.c
@@ -859,6 +859,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;
 		}
@@ -888,31 +890,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))
@@ -1344,6 +1350,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);
@@ -1513,6 +1520,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 7742f469944..e89e5906db5 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 "BKE_tessmesh.h"
 
@@ -1671,6 +1672,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;
@@ -1720,6 +1811,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");
@@ -1972,6 +2069,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 04135d5023f..8c58e4f3a33 100644
--- a/source/blender/modifiers/CMakeLists.txt
+++ b/source/blender/modifiers/CMakeLists.txt
@@ -35,12 +35,16 @@ set(INC
 	../makesrna
 	../bmesh
 	../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
@@ -66,6 +70,7 @@ set(SRC
 	intern/MOD_mirror.c
 	intern/MOD_multires.c
 	intern/MOD_ngoninterp.c
+	intern/MOD_navmesh.cpp
 	intern/MOD_none.c
 	intern/MOD_particleinstance.c
 	intern/MOD_particlesystem.c
@@ -116,4 +121,8 @@ if(NOT WITH_MOD_FLUID)
 	add_definitions(-DDISABLE_ELBEEM)
 endif()
 
+if(WITH_GAMEENGINE)
+	add_definitions(-DWITH_GAMEENGINE)
+endif()
+
 blender_add_lib(bf_modifiers "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/source/blender/modifiers/MOD_modifiertypes.h b/source/blender/modifiers/MOD_modifiertypes.h
index c545beba75a..06b116d1e6f 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 bc83700aaa6..d6f1d5108f8 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 ../bmesh'
 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..bc97023a58b
--- /dev/null
+++ b/source/blender/modifiers/intern/MOD_navmesh.cpp
@@ -0,0 +1,279 @@
+/*
+* $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 "BLI_utildefines.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; */ /* UNUSED */
+}
+
+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;*/
+
+#ifdef WITH_GAMEENGINE
+
+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);
+}
+#endif /* WITH_GAMEENGINE */
+
+static DerivedMesh *createNavMeshForVisualization(NavMeshModifierData *mmd,DerivedMesh *dm)
+{
+#ifdef WITH_GAMEENGINE
+	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;
+#else // WITH_GAMEENGINE
+	return dm;
+#endif // WITH_GAMEENGINE
+}
+
+/*
+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,
+};
+
+};
diff --git a/source/blender/modifiers/intern/MOD_util.c b/source/blender/modifiers/intern/MOD_util.c
index 13abaa7058f..85ad559cb0a 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/blender/python/intern/gpu.c b/source/blender/python/intern/gpu.c
index 8d705e44bb8..334bb1f725a 100644
--- a/source/blender/python/intern/gpu.c
+++ b/source/blender/python/intern/gpu.c
@@ -147,7 +147,6 @@ static PyObject* GPU_export_shader(PyObject* UNUSED(self), PyObject *args, PyObj
 	PyObject* pymat;
 	PyObject* as_pointer;
 	PyObject* pointer;
-	PyObject* noargs;
 	PyObject* result;
 	PyObject* dict;
 	PyObject* val;
@@ -170,9 +169,7 @@ static PyObject* GPU_export_shader(PyObject* UNUSED(self), PyObject *args, PyObj
 		(as_pointer = PyObject_GetAttrString(pyscene, "as_pointer")) != NULL &&
 		PyCallable_Check(as_pointer)) {
 		// must be a scene object
-		noargs = PyTuple_New(0);
-		pointer = PyObject_CallObject(as_pointer, noargs);
-		Py_DECREF(noargs);
+		pointer = PyObject_CallObject(as_pointer, NULL);
 		if (!pointer) {
 			PyErr_SetString(PyExc_SystemError, "scene.as_pointer() failed");
 			return NULL;
@@ -192,9 +189,7 @@ static PyObject* GPU_export_shader(PyObject* UNUSED(self), PyObject *args, PyObj
 		(as_pointer = PyObject_GetAttrString(pymat, "as_pointer")) != NULL &&
 		PyCallable_Check(as_pointer)) {
 		// must be a material object
-		noargs = PyTuple_New(0);
-		pointer = PyObject_CallObject(as_pointer, noargs);
-		Py_DECREF(noargs);
+		pointer = PyObject_CallObject(as_pointer, NULL);
 		if (!pointer) {
 			PyErr_SetString(PyExc_SystemError, "scene.as_pointer() failed");
 			return NULL;