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