synched with trunk at revision 34793
[blender-staging.git] / source / gameengine / Ketsji / KX_NavMeshObject.cpp
1 /**
2 * $Id$ 
3 * ***** BEGIN GPL LICENSE BLOCK *****
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * as published by the Free Software Foundation; either version 2
8 * of the License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 *
19 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
20 * All rights reserved.
21 *
22 * The Original Code is: all of this file.
23 *
24 * Contributor(s): none yet.
25 *
26 * ***** END GPL LICENSE BLOCK *****
27 */
28
29 #include "KX_NavMeshObject.h"
30 #include "RAS_MeshObject.h"
31
32 #include "DNA_mesh_types.h"
33 #include "DNA_meshdata_types.h"
34
35 extern "C" {
36 #include "BKE_scene.h"
37 #include "BKE_customdata.h"
38 #include "BKE_cdderivedmesh.h"
39 #include "BKE_DerivedMesh.h"
40 #include "BLI_math_vector.h"
41
42 #include "ED_navmesh_conversion.h"
43 }
44
45 #include "KX_PythonInit.h"
46 #include "KX_PyMath.h"
47 #include "Value.h"
48 #include "Recast.h"
49 #include "DetourStatNavMeshBuilder.h"
50 #include "KX_ObstacleSimulation.h"
51
52 static const int MAX_PATH_LEN = 256;
53 static const float polyPickExt[3] = {2, 4, 2};
54
55 static void calcMeshBounds(const float* vert, int nverts, float* bmin, float* bmax)
56 {
57         bmin[0] = bmax[0] = vert[0];
58         bmin[1] = bmax[1] = vert[1];
59         bmin[2] = bmax[2] = vert[2];
60         for (int i=1; i<nverts; i++)
61         {
62                 if (bmin[0]>vert[3*i+0]) bmin[0] = vert[3*i+0];
63                 if (bmin[1]>vert[3*i+1]) bmin[1] = vert[3*i+1];
64                 if (bmin[2]>vert[3*i+2]) bmin[2] = vert[3*i+2];
65
66                 if (bmax[0]<vert[3*i+0]) bmax[0] = vert[3*i+0];
67                 if (bmax[1]<vert[3*i+1]) bmax[1] = vert[3*i+1];
68                 if (bmax[2]<vert[3*i+2]) bmax[2] = vert[3*i+2];
69         }
70 }
71
72 inline void flipAxes(float* vec)
73 {
74         std::swap(vec[1],vec[2]);
75 }
76 KX_NavMeshObject::KX_NavMeshObject(void* sgReplicationInfo, SG_Callbacks callbacks)
77 :       KX_GameObject(sgReplicationInfo, callbacks)
78 ,       m_navMesh(NULL)
79 {
80         
81 }
82
83 KX_NavMeshObject::~KX_NavMeshObject()
84 {
85         if (m_navMesh)
86                 delete m_navMesh;
87 }
88
89 CValue* KX_NavMeshObject::GetReplica()
90 {
91         KX_NavMeshObject* replica = new KX_NavMeshObject(*this);
92         replica->ProcessReplica();
93         return replica;
94 }
95
96 void KX_NavMeshObject::ProcessReplica()
97 {
98         KX_GameObject::ProcessReplica();
99
100         BuildNavMesh();
101         KX_Scene* scene = KX_GetActiveScene();
102         KX_ObstacleSimulation* obssimulation = scene->GetObstacleSimulation();
103         if (obssimulation)
104                 obssimulation->AddObstaclesForNavMesh(this);
105
106 }
107
108 bool KX_NavMeshObject::BuildVertIndArrays(float *&vertices, int& nverts,
109                                                                            unsigned short* &polys, int& npolys, unsigned short *&dmeshes,
110                                                                            float *&dvertices, int &ndvertsuniq, unsigned short *&dtris, 
111                                                                            int& ndtris, int &vertsPerPoly)
112 {
113         DerivedMesh* dm = mesh_create_derived_no_virtual(KX_GetActiveScene()->GetBlenderScene(), GetBlenderObject(), 
114                                                                                                         NULL, CD_MASK_MESH);
115         int* recastData = (int*) dm->getFaceDataArray(dm, CD_RECAST);
116         if (recastData)
117         {
118                 int *dtrisToPolysMap=NULL, *dtrisToTrisMap=NULL, *trisToFacesMap=NULL;
119                 int nAllVerts = 0;
120                 float *allVerts = NULL;
121                 buildNavMeshDataByDerivedMesh(dm, vertsPerPoly, nAllVerts, allVerts, ndtris, dtris,
122                         npolys, dmeshes, polys, dtrisToPolysMap, dtrisToTrisMap, trisToFacesMap);
123
124                 unsigned short *verticesMap = new unsigned short[nAllVerts];
125                 memset(verticesMap, 0xffff, sizeof(unsigned short)*nAllVerts);
126                 int curIdx = 0;
127                 //vertices - mesh verts
128                 //iterate over all polys and create map for their vertices first...
129                 for (int polyidx=0; polyidx<npolys; polyidx++)
130                 {
131                         unsigned short* poly = &polys[polyidx*vertsPerPoly*2];
132                         for (int i=0; i<vertsPerPoly; i++)
133                         {
134                                 unsigned short idx = poly[i];
135                                 if (idx==0xffff)
136                                         break;
137                                 if (verticesMap[idx]==0xffff)
138                                 {
139                                         verticesMap[idx] = curIdx++;
140                                 }
141                                 poly[i] = verticesMap[idx];
142                         }
143                 }
144                 nverts = curIdx;
145                 //...then iterate over detailed meshes
146                 //transform indices to local ones (for each navigation polygon)
147                 for (int polyidx=0; polyidx<npolys; polyidx++)
148                 {
149                         unsigned short *poly = &polys[polyidx*vertsPerPoly*2];
150                         int nv = polyNumVerts(poly, vertsPerPoly);
151                         unsigned short *dmesh = &dmeshes[4*polyidx];
152                         unsigned short tribase = dmesh[2];
153                         unsigned short trinum = dmesh[3];
154                         unsigned short vbase = curIdx;
155                         for (int j=0; j<trinum; j++)
156                         {
157                                 unsigned short* dtri = &dtris[(tribase+j)*3*2];
158                                 for (int k=0; k<3; k++)
159                                 {
160                                         int newVertexIdx = verticesMap[dtri[k]];
161                                         if (newVertexIdx==0xffff)
162                                         {
163                                                 newVertexIdx = curIdx++;
164                                                 verticesMap[dtri[k]] = newVertexIdx;
165                                         }
166
167                                         if (newVertexIdx<nverts)
168                                         {
169                                                 //it's polygon vertex ("shared")
170                                                 int idxInPoly = polyFindVertex(poly, vertsPerPoly, newVertexIdx);
171                                                 if (idxInPoly==-1)
172                                                 {
173                                                         printf("Building NavMeshObject: Error! Can't find vertex in polygon\n");
174                                                         return false;
175                                                 }
176                                                 dtri[k] = idxInPoly;
177                                         }
178                                         else
179                                         {
180                                                 dtri[k] = newVertexIdx - vbase + nv;
181                                         }
182                                 }
183                         }
184                         dmesh[0] = vbase-nverts; //verts base
185                         dmesh[1] = curIdx-vbase; //verts num
186                 }
187
188                 vertices = new float[nverts*3];
189                 ndvertsuniq = curIdx - nverts;
190                 if (ndvertsuniq>0)
191                 {
192                         dvertices = new float[ndvertsuniq*3];
193                 }
194                 for (int vi=0; vi<nAllVerts; vi++)
195                 {
196                         int newIdx = verticesMap[vi];
197                         if (newIdx!=0xffff)
198                         {
199                                 if (newIdx<nverts)
200                                 {
201                                         //navigation mesh vertex
202                                         memcpy(vertices+3*newIdx, allVerts+3*vi, 3*sizeof(float));
203                                 }
204                                 else
205                                 {
206                                         //detailed mesh vertex
207                                         memcpy(dvertices+3*(newIdx-nverts), allVerts+3*vi, 3*sizeof(float));
208                                 }                               
209                         }
210                 }
211         }
212         else
213         {
214                 //create from RAS_MeshObject (detailed mesh is fake)
215                 RAS_MeshObject* meshobj = GetMesh(0);
216                 vertsPerPoly = 3;
217                 nverts = meshobj->m_sharedvertex_map.size();
218                 if (nverts >= 0xffff)
219                         return false;
220                 //calculate count of tris
221                 int nmeshpolys = meshobj->NumPolygons();
222                 npolys = nmeshpolys;
223                 for (int p=0; p<nmeshpolys; p++)
224                 {
225                         int vertcount = meshobj->GetPolygon(p)->VertexCount();
226                         npolys+=vertcount-3;
227                 }
228
229                 //create verts
230                 vertices = new float[nverts*3];
231                 float* vert = vertices;
232                 for (int vi=0; vi<nverts; vi++)
233                 {
234                         const float* pos = !meshobj->m_sharedvertex_map[vi].empty() ? meshobj->GetVertexLocation(vi) : NULL;
235                         if (pos)
236                                 copy_v3_v3(vert, pos);
237                         else
238                         {
239                                 memset(vert, NULL, 3*sizeof(float)); //vertex isn't in any poly, set dummy zero coordinates
240                         }
241                         vert+=3;                
242                 }
243
244                 //create tris
245                 polys = new unsigned short[npolys*3*2];
246                 memset(polys, 0xff, sizeof(unsigned short)*3*2*npolys);
247                 unsigned short *poly = polys;
248                 RAS_Polygon* raspoly;
249                 for (int p=0; p<nmeshpolys; p++)
250                 {
251                         raspoly = meshobj->GetPolygon(p);
252                         for (int v=0; v<raspoly->VertexCount()-2; v++)
253                         {
254                                 poly[0]= raspoly->GetVertex(0)->getOrigIndex();
255                                 for (size_t i=1; i<3; i++)
256                                 {
257                                         poly[i]= raspoly->GetVertex(v+i)->getOrigIndex();
258                                 }
259                                 poly += 6;
260                         }
261                 }
262                 dmeshes = NULL;
263                 dvertices = NULL;
264                 ndvertsuniq = 0;
265                 dtris = NULL;
266                 ndtris = npolys;
267         }
268         dm->release(dm);
269         
270         return true;
271 }
272
273
274 bool KX_NavMeshObject::BuildNavMesh()
275 {
276         if (m_navMesh)
277         {
278                 delete m_navMesh;
279                 m_navMesh = NULL;
280         }
281
282         if (GetMeshCount()==0)
283         {
284                 printf("Can't find mesh for navmesh object: %s \n", m_name);
285                 return false;
286         }
287
288         float *vertices = NULL, *dvertices = NULL;
289         unsigned short *polys = NULL, *dtris = NULL, *dmeshes = NULL;
290         int nverts = 0, npolys = 0, ndvertsuniq = 0, ndtris = 0;        
291         int vertsPerPoly = 0;
292         if (!BuildVertIndArrays(vertices, nverts, polys, npolys, 
293                                                         dmeshes, dvertices, ndvertsuniq, dtris, ndtris, vertsPerPoly ) 
294                         || vertsPerPoly<3)
295         {
296                 printf("Can't build navigation mesh data for object:%s \n", m_name);
297                 return false;
298         }
299         
300         MT_Point3 pos;
301         if (dmeshes==NULL)
302         {
303                 for (int i=0; i<nverts; i++)
304                 {
305                         flipAxes(&vertices[i*3]);
306                 }
307                 for (int i=0; i<ndvertsuniq; i++)
308                 {
309                         flipAxes(&dvertices[i*3]);
310                 }
311         }
312
313         buildMeshAdjacency(polys, npolys, nverts, vertsPerPoly);
314         
315         float cs = 0.2f;
316
317         if (!nverts || !npolys)
318                 return false;
319
320         float bmin[3], bmax[3];
321         calcMeshBounds(vertices, nverts, bmin, bmax);
322         //quantize vertex pos
323         unsigned short* vertsi = new unsigned short[3*nverts];
324         float ics = 1.f/cs;
325         for (int i=0; i<nverts; i++)
326         {
327                 vertsi[3*i+0] = static_cast<unsigned short>((vertices[3*i+0]-bmin[0])*ics);
328                 vertsi[3*i+1] = static_cast<unsigned short>((vertices[3*i+1]-bmin[1])*ics);
329                 vertsi[3*i+2] = static_cast<unsigned short>((vertices[3*i+2]-bmin[2])*ics);
330         }
331
332         // Calculate data size
333         const int headerSize = sizeof(dtStatNavMeshHeader);
334         const int vertsSize = sizeof(float)*3*nverts;
335         const int polysSize = sizeof(dtStatPoly)*npolys;
336         const int nodesSize = sizeof(dtStatBVNode)*npolys*2;
337         const int detailMeshesSize = sizeof(dtStatPolyDetail)*npolys;
338         const int detailVertsSize = sizeof(float)*3*ndvertsuniq;
339         const int detailTrisSize = sizeof(unsigned char)*4*ndtris;
340
341         const int dataSize = headerSize + vertsSize + polysSize + nodesSize +
342                 detailMeshesSize + detailVertsSize + detailTrisSize;
343         unsigned char* data = new unsigned char[dataSize];
344         if (!data)
345                 return false;
346         memset(data, 0, dataSize);
347
348         unsigned char* d = data;
349         dtStatNavMeshHeader* header = (dtStatNavMeshHeader*)d; d += headerSize;
350         float* navVerts = (float*)d; d += vertsSize;
351         dtStatPoly* navPolys = (dtStatPoly*)d; d += polysSize;
352         dtStatBVNode* navNodes = (dtStatBVNode*)d; d += nodesSize;
353         dtStatPolyDetail* navDMeshes = (dtStatPolyDetail*)d; d += detailMeshesSize;
354         float* navDVerts = (float*)d; d += detailVertsSize;
355         unsigned char* navDTris = (unsigned char*)d; d += detailTrisSize;
356
357         // Store header
358         header->magic = DT_STAT_NAVMESH_MAGIC;
359         header->version = DT_STAT_NAVMESH_VERSION;
360         header->npolys = npolys;
361         header->nverts = nverts;
362         header->cs = cs;
363         header->bmin[0] = bmin[0];
364         header->bmin[1] = bmin[1];
365         header->bmin[2] = bmin[2];
366         header->bmax[0] = bmax[0];
367         header->bmax[1] = bmax[1];
368         header->bmax[2] = bmax[2];
369         header->ndmeshes = npolys;
370         header->ndverts = ndvertsuniq;
371         header->ndtris = ndtris;
372
373         // Store vertices
374         for (int i = 0; i < nverts; ++i)
375         {
376                 const unsigned short* iv = &vertsi[i*3];
377                 float* v = &navVerts[i*3];
378                 v[0] = bmin[0] + iv[0] * cs;
379                 v[1] = bmin[1] + iv[1] * cs;
380                 v[2] = bmin[2] + iv[2] * cs;
381         }
382         //memcpy(navVerts, vertices, nverts*3*sizeof(float));
383
384         // Store polygons
385         const unsigned short* src = polys;
386         for (int i = 0; i < npolys; ++i)
387         {
388                 dtStatPoly* p = &navPolys[i];
389                 p->nv = 0;
390                 for (int j = 0; j < vertsPerPoly; ++j)
391                 {
392                         if (src[j] == 0xffff) break;
393                         p->v[j] = src[j];
394                         p->n[j] = src[vertsPerPoly+j]+1;
395                         p->nv++;
396                 }
397                 src += vertsPerPoly*2;
398         }
399
400         header->nnodes = createBVTree(vertsi, nverts, polys, npolys, vertsPerPoly,
401                                                                 cs, cs, npolys*2, navNodes);
402         
403         
404         if (dmeshes==NULL)
405         {
406                 //create fake detail meshes
407                 for (int i = 0; i < npolys; ++i)
408                 {
409                         dtStatPolyDetail& dtl = navDMeshes[i];
410                         dtl.vbase = 0;
411                         dtl.nverts = 0;
412                         dtl.tbase = i;
413                         dtl.ntris = 1;
414                 }
415                 // setup triangles.
416                 unsigned char* tri = navDTris;
417                 for(size_t i=0; i<ndtris; i++)
418                 {
419                         for (size_t j=0; j<3; j++)
420                                 tri[4*i+j] = j;
421                 }
422         }
423         else
424         {
425                 //verts
426                 memcpy(navDVerts, dvertices, ndvertsuniq*3*sizeof(float));
427                 //tris
428                 unsigned char* tri = navDTris;
429                 for(size_t i=0; i<ndtris; i++)
430                 {
431                         for (size_t j=0; j<3; j++)
432                                 tri[4*i+j] = dtris[6*i+j];
433                 }
434                 //detailed meshes
435                 for (int i = 0; i < npolys; ++i)
436                 {
437                         dtStatPolyDetail& dtl = navDMeshes[i];
438                         dtl.vbase = dmeshes[i*4+0];
439                         dtl.nverts = dmeshes[i*4+1];
440                         dtl.tbase = dmeshes[i*4+2];
441                         dtl.ntris = dmeshes[i*4+3];
442                 }               
443         }
444
445         m_navMesh = new dtStatNavMesh;
446         m_navMesh->init(data, dataSize, true);  
447
448         delete [] vertices;
449         delete [] polys;
450         if (dvertices)
451         {
452                 delete [] dvertices;
453         }
454
455         return true;
456 }
457
458 dtStatNavMesh* KX_NavMeshObject::GetNavMesh()
459 {
460         return m_navMesh;
461 }
462
463 void KX_NavMeshObject::DrawNavMesh(NavMeshRenderMode renderMode)
464 {
465         if (!m_navMesh)
466                 return;
467         MT_Vector3 color(0.f, 0.f, 0.f);
468         
469         switch (renderMode)
470         {
471         case RM_POLYS :
472         case RM_WALLS : 
473                 for (int pi=0; pi<m_navMesh->getPolyCount(); pi++)
474                 {
475                         const dtStatPoly* poly = m_navMesh->getPoly(pi);
476
477                         for (int i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j = i++)
478                         {       
479                                 if (poly->n[j] && renderMode==RM_WALLS) 
480                                         continue;
481                                 const float* vif = m_navMesh->getVertex(poly->v[i]);
482                                 const float* vjf = m_navMesh->getVertex(poly->v[j]);
483                                 MT_Point3 vi(vif[0], vif[2], vif[1]);
484                                 MT_Point3 vj(vjf[0], vjf[2], vjf[1]);
485                                 vi = TransformToWorldCoords(vi);
486                                 vj = TransformToWorldCoords(vj);
487                                 KX_RasterizerDrawDebugLine(vi, vj, color);
488                         }
489                 }
490                 break;
491         case RM_TRIS : 
492                 for (int i = 0; i < m_navMesh->getPolyDetailCount(); ++i)
493                 {
494                         const dtStatPoly* p = m_navMesh->getPoly(i);
495                         const dtStatPolyDetail* pd = m_navMesh->getPolyDetail(i);
496
497                         for (int j = 0; j < pd->ntris; ++j)
498                         {
499                                 const unsigned char* t = m_navMesh->getDetailTri(pd->tbase+j);
500                                 MT_Point3 tri[3];
501                                 for (int k = 0; k < 3; ++k)
502                                 {
503                                         const float* v;
504                                         if (t[k] < p->nv)
505                                                 v = m_navMesh->getVertex(p->v[t[k]]);
506                                         else
507                                                 v =  m_navMesh->getDetailVertex(pd->vbase+(t[k]-p->nv));
508                                         float pos[3];
509                                         vcopy(pos, v);
510                                         flipAxes(pos);
511                                         tri[k].setValue(pos);
512                                 }
513
514                                 for (int k=0; k<3; k++)
515                                         tri[k] = TransformToWorldCoords(tri[k]);
516
517                                 for (int k=0; k<3; k++)
518                                         KX_RasterizerDrawDebugLine(tri[k], tri[(k+1)%3], color);
519                         }
520                 }
521                 break;
522         }
523 }
524
525 MT_Point3 KX_NavMeshObject::TransformToLocalCoords(const MT_Point3& wpos)
526 {
527         MT_Matrix3x3 orientation = NodeGetWorldOrientation();
528         const MT_Vector3& scaling = NodeGetWorldScaling();
529         orientation.scale(scaling[0], scaling[1], scaling[2]);
530         MT_Transform worldtr(NodeGetWorldPosition(), orientation); 
531         MT_Transform invworldtr;
532         invworldtr.invert(worldtr);
533         MT_Point3 lpos = invworldtr(wpos);
534         return lpos;
535 }
536
537 MT_Point3 KX_NavMeshObject::TransformToWorldCoords(const MT_Point3& lpos)
538 {
539         MT_Matrix3x3 orientation = NodeGetWorldOrientation();
540         const MT_Vector3& scaling = NodeGetWorldScaling();
541         orientation.scale(scaling[0], scaling[1], scaling[2]);
542         MT_Transform worldtr(NodeGetWorldPosition(), orientation); 
543         MT_Point3 wpos = worldtr(lpos);
544         return wpos;
545 }
546
547 int KX_NavMeshObject::FindPath(const MT_Point3& from, const MT_Point3& to, float* path, int maxPathLen)
548 {
549         if (!m_navMesh)
550                 return 0;
551         MT_Point3 localfrom = TransformToLocalCoords(from);
552         MT_Point3 localto = TransformToLocalCoords(to); 
553         float spos[3], epos[3];
554         localfrom.getValue(spos); flipAxes(spos);
555         localto.getValue(epos); flipAxes(epos);
556         dtStatPolyRef sPolyRef = m_navMesh->findNearestPoly(spos, polyPickExt);
557         dtStatPolyRef ePolyRef = m_navMesh->findNearestPoly(epos, polyPickExt);
558
559         int pathLen = 0;
560         if (sPolyRef && ePolyRef)
561         {
562                 dtStatPolyRef* polys = new dtStatPolyRef[maxPathLen];
563                 int npolys;
564                 npolys = m_navMesh->findPath(sPolyRef, ePolyRef, spos, epos, polys, maxPathLen);
565                 if (npolys)
566                 {
567                         pathLen = m_navMesh->findStraightPath(spos, epos, polys, npolys, path, maxPathLen);
568                         for (int i=0; i<pathLen; i++)
569                         {
570                                 flipAxes(&path[i*3]);
571                                 MT_Point3 waypoint(&path[i*3]);
572                                 waypoint = TransformToWorldCoords(waypoint);
573                                 waypoint.getValue(&path[i*3]);
574                         }
575                 }
576         }
577
578         return pathLen;
579 }
580
581 float KX_NavMeshObject::Raycast(const MT_Point3& from, const MT_Point3& to)
582 {
583         if (!m_navMesh)
584                 return 0.f;
585         MT_Point3 localfrom = TransformToLocalCoords(from);
586         MT_Point3 localto = TransformToLocalCoords(to); 
587         float spos[3], epos[3];
588         localfrom.getValue(spos); flipAxes(spos);
589         localto.getValue(epos); flipAxes(epos);
590         dtStatPolyRef sPolyRef = m_navMesh->findNearestPoly(spos, polyPickExt);
591         float t=0;
592         static dtStatPolyRef polys[MAX_PATH_LEN];
593         m_navMesh->raycast(sPolyRef, spos, epos, t, polys, MAX_PATH_LEN);
594         return t;
595 }
596
597 void KX_NavMeshObject::DrawPath(const float *path, int pathLen, const MT_Vector3& color)
598 {
599         MT_Vector3 a,b;
600         for (int i=0; i<pathLen-1; i++)
601         {
602                 a.setValue(&path[3*i]);
603                 b.setValue(&path[3*(i+1)]);
604                 KX_RasterizerDrawDebugLine(a, b, color);
605         }
606 }
607
608
609 #ifndef DISABLE_PYTHON
610 //----------------------------------------------------------------------------
611 //Python
612
613 PyTypeObject KX_NavMeshObject::Type = {
614         PyVarObject_HEAD_INIT(NULL, 0)
615         "KX_NavMeshObject",
616         sizeof(PyObjectPlus_Proxy),
617         0,
618         py_base_dealloc,
619         0,
620         0,
621         0,
622         0,
623         py_base_repr,
624         0,
625         0,
626         0,
627         0,0,0,0,0,0,
628         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE,
629         0,0,0,0,0,0,0,
630         Methods,
631         0,
632         0,
633         &KX_GameObject::Type,
634         0,0,0,0,0,0,
635         py_base_new
636 };
637
638 PyAttributeDef KX_NavMeshObject::Attributes[] = {
639         { NULL }        //Sentinel
640 };
641
642 //KX_PYMETHODTABLE_NOARGS(KX_GameObject, getD),
643 PyMethodDef KX_NavMeshObject::Methods[] = {
644         KX_PYMETHODTABLE(KX_NavMeshObject, findPath),
645         KX_PYMETHODTABLE(KX_NavMeshObject, raycast),
646         KX_PYMETHODTABLE(KX_NavMeshObject, draw),
647         KX_PYMETHODTABLE(KX_NavMeshObject, rebuild),
648         {NULL,NULL} //Sentinel
649 };
650
651 KX_PYMETHODDEF_DOC(KX_NavMeshObject, findPath,
652                                    "findPath(start, goal): find path from start to goal points\n"
653                                    "Returns a path as list of points)\n")
654 {
655         PyObject *ob_from, *ob_to;
656         if (!PyArg_ParseTuple(args,"OO:getPath",&ob_from,&ob_to))
657                 return NULL;
658         MT_Point3 from, to;
659         if (!PyVecTo(ob_from, from) || !PyVecTo(ob_to, to))
660                 return NULL;
661         
662         float path[MAX_PATH_LEN*3];
663         int pathLen = FindPath(from, to, path, MAX_PATH_LEN);
664         PyObject *pathList = PyList_New( pathLen );
665         for (int i=0; i<pathLen; i++)
666         {
667                 MT_Point3 point(&path[3*i]);
668                 PyList_SET_ITEM(pathList, i, PyObjectFrom(point));
669         }
670
671         return pathList;
672 }
673
674 KX_PYMETHODDEF_DOC(KX_NavMeshObject, raycast,
675                                    "raycast(start, goal): raycast from start to goal points\n"
676                                    "Returns hit factor)\n")
677 {
678         PyObject *ob_from, *ob_to;
679         if (!PyArg_ParseTuple(args,"OO:getPath",&ob_from,&ob_to))
680                 return NULL;
681         MT_Point3 from, to;
682         if (!PyVecTo(ob_from, from) || !PyVecTo(ob_to, to))
683                 return NULL;
684         float hit = Raycast(from, to);
685         return PyFloat_FromDouble(hit);
686 }
687
688 KX_PYMETHODDEF_DOC(KX_NavMeshObject, draw,
689                                    "draw(mode): navigation mesh debug drawing\n"
690                                    "mode: WALLS, POLYS, TRIS\n")
691 {
692         int arg;
693         NavMeshRenderMode renderMode = RM_TRIS;
694         if (PyArg_ParseTuple(args,"i:rebuild",&arg) && arg>=0 && arg<RM_MAX)
695                 renderMode = (NavMeshRenderMode)arg;
696         DrawNavMesh(renderMode);
697         Py_RETURN_NONE;
698 }
699
700 KX_PYMETHODDEF_DOC_NOARGS(KX_NavMeshObject, rebuild,
701                                                   "rebuild(): rebuild navigation mesh\n")
702 {
703         BuildNavMesh();
704         Py_RETURN_NONE;
705 }
706
707 #endif // DISABLE_PYTHON