Closest body

[Julio Jerez]

Ok, if you are ok with those condition then it si not really that difficult conceptually.

here are the steps you need to do. you can use Newton ot you can use any code.

1- have a linear the location of all bodies you want to process, later you can also add point that can represent obstacle and even information from you map, like for example mountain, buildings rooms or even moving parts. but that is after you are familiar with the method.
2- Lift each 2d point from 2d space to the 3d space but using the parabolic functions projection.
3- build the 3d convex hull of the array of point of 3d point from the previous step
4- the for any point you want the closest neighbor you just read the list of the adjacent points to that node.

as you can see each step if fairly simple. the only par that may be complex to you is getting the Delaney triangulation or the voronoi diagram.
The reason why this works is because etch voronoi diagram is by definition the set all the sectors that are closet the one sector than any other sector.
if this is true, then if you want to know the set of all point closer to one point than any other point all you need to do is build the voronoi diagram for that set of point and read what points are part of the. closer sectors.

Now we reduce the problem for a search to how to build the voronoi diagram.

There are several method for doing that, whoever I do not like any of them because seethe do no extent to higher dimensions and almost all of them are prone to numerical error.
the only method that I like is one discovered by a man named Seidel, and it goes like this
The Delaney triangulation of a set of point is the lower convex hull of the set of point obtained by liftin each point to a parabolic space.
that is for each point

Q(i).x = P(i).x,
Q(i).y = P(i).y,
Q(i).z = P(i).x * P(i).x + P(i).y * P(i).y.


You can read some of the properties of the Delaunay triangulation and Voronoi diagram here.
If you notice that I talk about Delany triangulation when what we need is the Verona diagram,
the is because we will use another property of them that say a Voronoi diagram is the dual of teh Delaney triangulation, that mean that if you represent the Delaunay triangulation as a graph where the vertex are the nodes and the edges from the triangles, then if you build a graph where each point of the Delaunay graph is an edge of the Voronoi graph and each edge of the Delaunay is a node of the Voroni.

It may be good that you check this link out for some of the properties and also so that you understand what I am talking about.
http://en.wikipedia.org/wiki/Delaunay_triangulation

As it turns out one we have the Delany triangulation if you have a good data structure there is not need to build the Voronoi diagrams, that converse is also true.
The reason I mention Delany triangulation is that they are easier to build than Voronoi diagram, but is the Voronoi diagram property that demonstrate the all nearest neighbor property.
On the liek abobe you cna see graphuicslly hwo the deleany trigulation of the pointe ste is the real one and unique solution to teh problem.
look at the triangulation of the 100 randome point in the image and you can see that to get the set of all closet neighborgs to any point,
all you need to do is to read the points that are directly connected to that point via one direct edge.
you can see how any AI strategy cna be buidl buy just walki teh diagram using any king of heuritic.

you can also see that with good data structure this point can be read in constact time, an dtha is where Netwon comes in.

In the next post I will go over each step

[Julio Jerez]

Ok one way to implement this is you have a class that encapsulate the functionality.
say something like this:

Code: Select all

class MyClosestNode
{
     
   MyClosestNode ( );

   void BuildDataBase (Vector pointList, int count);
   int GetClosestPoints (int* const array);
};

you use like this:

Code: Select all

void GameMainLoop()
{
   MyClosestNode nearestNeighborg;
   while(1)
   {
      nearestNeighborg. BuildDataBase ();


      for (i = 0; i < pointCount; i ++) {
                                   int indexArray[128];
           
                                   int count =  nearestNeighborg.GetClosestPoints(indexArray);

            Object obj1 = ObjList[i];
           // for each point in indexArray do you AI stuff
                                  for (j = 0; j < count;   j ++) {
                                         Object obj2 = ObjList[indexArray]
                                        // do you AI stuff on this pair
                                       DoAI (obj1, obj2);
                                   }
                   }   
   }
}

is this clear so far?
In fact that engine should work even with brute force, checking having
GetClosestPoints(indexArray);
finding the n closest points, within a radius, now all we need to do is implement the body of those two functions.
I asume you already have somethong similar.

Next I will post teh code to make the Delanay triangulation.
I will take teh newton conve hull and adapte for that. so stha you can use independenly of the engine
The reason is that the newton convex Hull is optimized for collsiion and for that it order teh point array,
It will work, but since we know the delanay all points are part of the Hull, them that step is not nessesary.

[Julio Jerez]

are you still there?

[KingSnail]

Hey, I was a bit busy today, will try to implement it tommorow.
I read it what you wrote and it kinda makes sense but its way too advanced for me hehe.
I understand some parts of it though, I will certainly try my best to implement it.
So your method is incremental? because before you said incremental diagram is better

[Julio Jerez]

the method can be incremental, however sicen you are doing thsio for all bodies.
I believe it is better to do as an update function and will be cheaper.

depend how much activity. if all bodies moves from frame to frame or if only few bodies moves you can use one strategy of another
but you can do that later, for now let us have a working version.

[KingSnail]

Ok I added your code but now im stuck.

This is what I have so far

Code: Select all

nearestNeighborg.BuildDatabase(&PlayerCoords[0], PlayerCoords.size());
      for(int k = 0; k < PlayersInZoneManager::GetInstance().PlayersInZone.size(); ++k)
      {
            int indexArray[128];
            int count =  nearestNeighborg.GetClosestPoints(indexArray);

            Object obj1 = ObjList[i]; //Whats this??
           // for each point in indexArray do you AI stuff
         for(j = 0; j < count; ++j)
         {
             Object obj2 = ObjList[indexArray]
            // do you AI stuff on this pair
            DoAI (obj1, obj2); //I only need to know if body is within range of another for now
         }
        }


[Julio Jerez]

I have not forgotten I will do ove the weekend

I will make a small VS porojet with a main and test it with a set of randon numbers,
tah way you sodul be able to just take teh class an usin it as it

[KingSnail]

great
Maybe you can even add it to the samples folder.

[Julio Jerez]

so that you know I have not forgotten aboput this, I could not do it lat weekeng bu nwo that I am a stable poiunt I will try it.
I too am intrigued about the end result.

[KingSnail]

Any luck so far?

[Julio Jerez]

I moved this to the souce code forum.

Ok I almost have it ready, I am making a smalll modification to teh convex hull routine so that it preserve the vertex order, that way
It can be used for this rather than copying and past to make a new one.

It should be ready some time today.

[Julio Jerez]

Ok this is the code, I test with a regual grid and also with randome point

Code: Select all

// VoronoiDemo.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "dg.h"

class ClosestNeighborg: public dgConvexHull3d
{
   class FaceList: public dgList<dgConvexHull3d::dgListNode*>
   {
      public:
      FaceList (dgMemoryAllocator* const allocator)
         :dgList<dgConvexHull3d::dgListNode*>(allocator)
      {
      }
   };

   class FaceMap: public dgTree<FaceList, int>
   {
      public:
      FaceMap (dgMemoryAllocator* const allocator)
         :dgTree<FaceList, int>(allocator)
      {
      }
   };

   public:
   ClosestNeighborg(dgMemoryAllocator* const allocator, dgBigVector* const points, dgInt32 count)
      :dgConvexHull3d (allocator)
      ,m_lru(0)
      ,m_faceMap (allocator)
      ,m_mask(256, allocator)
   {
      for (dgInt32 i = 0; i < count; i ++) {
         points[i].m_z = points[i].m_x * points[i].m_x + points[i].m_y * points[i].m_y;
         points[i].m_w = i;
      }
      m_mask[count - 1] = 0;
      memset (&m_mask[0], 0, sizeof (unsigned));

      BuildHUll (&points[0].m_x, sizeof (dgBigVector), count, 0.0, 0x7fffffff);
   }

   int GetClosestPoints (int index, int* const arrayOut, int maxCount)
   {
      FaceMap::dgTreeNode* const faceMapNode = m_faceMap.Find(index);
      _ASSERTE (faceMapNode);

      int count = 0;
      m_lru ++;
      unsigned* markIndex = &m_mask[0];
      markIndex[index] = m_lru;
      FaceList& faceList = faceMapNode->GetInfo();      
      for (FaceList::dgListNode* faceNode = faceList.GetFirst(); faceNode; faceNode = faceNode->GetNext()) {
         dgConvexHull3DFace* const face = &faceNode->GetInfo()->GetInfo();
         if (IsLowerHull (face)) {
            for (int i = 0; i < 3; i ++) {
               int k = face->m_index[i];
               const dgBigVector& vertex = GetVertex(k);
               k = int (vertex.m_w);
               if (markIndex[k] != m_lru) {
                  arrayOut[count] = k;
                  markIndex[k] = m_lru;
                  count ++;
                  _ASSERTE (count < maxCount);

               }
            }
         }
      }
      return count;
   }

   // for incremental update wne a point move, but let us see hwo tehis work first.
   void AddPoint(int point)
   {
   }

   void RemovePoint(int point)
   {

   }

   void DebugRender()
   {
      for (ClosestNeighborg::dgListNode* node = GetFirst(); node; node = node->GetNext()) {
         dgConvexHull3DFace* const face = &node->GetInfo();
         if (IsLowerHull (face)) {
            dgVector vertex0 (GetVertex(face->m_index[0]));
            dgVector vertex1 (GetVertex(face->m_index[1]));
            dgVector vertex2 (GetVertex(face->m_index[2]));

            vertex0.m_z = 0.0f;
            vertex1.m_z = 0.0f;
            vertex2.m_z = 0.0f;

            // Render this triangle (vertex0, vertex1, vertex2);
         }
      }
   }

   private:
   virtual dgListNode* AddFace (dgInt32 i0, dgInt32 i1, dgInt32 i2)
   {
      dgListNode* const face = dgConvexHull3d::AddFace(i0, i1, i2);

      const dgBigVector& vertex0 = GetVertex(i0);
      const dgBigVector& vertex1 = GetVertex(i1);
      const dgBigVector& vertex2 = GetVertex(i2);

      int index[3];
      index[0] = int (vertex0.m_w);
      index[1] = int (vertex1.m_w);
      index[2] = int (vertex2.m_w);
      for (int i = 0; i < 3; i ++) {
         FaceMap::dgTreeNode* node = m_faceMap.Find(index[i]);
         if (!node) {
            FaceList faceList (GetAllocator());
            node = m_faceMap.Insert(faceList, index[i]);
         }
         FaceList& faceList = node->GetInfo();
         faceList.Append(face);
      }
      return face;
   }

   virtual void DeleteFace (dgListNode* const node)
   {
      dgConvexHull3DFace* const face = &node->GetInfo();

      for (int i = 0; i < 3; i ++) {
         int index = face->m_index[i];
         const dgBigVector& vertex = GetVertex(index);
         index = int (vertex.m_w);

         FaceMap::dgTreeNode* const mapNode = m_faceMap.Find(index);
         _ASSERTE (mapNode);

         FaceList& faceList = mapNode->GetInfo();
         for (FaceList::dgListNode* faceNode = faceList.GetFirst(); faceNode; faceNode = faceNode->GetNext()) {
            if (faceNode->GetInfo() == node) {
               faceList.Remove(faceNode);
               _ASSERTE (faceList.GetCount());
               break;
            }
         }
      }

      dgConvexHull3d::DeleteFace(node);
   }

   bool IsLowerHull (dgConvexHull3DFace* const face) const
   {
      const dgBigVector& vertex0 = GetVertex(face->m_index[0]);
      const dgBigVector& vertex1 = GetVertex(face->m_index[1]);
      const dgBigVector& vertex2 = GetVertex(face->m_index[2]);

      dgBigVector e0 (vertex1 - vertex0);
      dgBigVector e1 (vertex2 - vertex0);
      dgBigVector n (e0 * e1);
      return (n.m_z < 0.0f);
   }

   int m_lru;
   FaceMap m_faceMap;
   dgArray<unsigned> m_mask;

};


int _tmain(int argc, _TCHAR* argv[])
{
   dgMemoryAllocator allocator;

   dgInt32 count = 0;
   dgBigVector points[1000];

   // populated the map with point representing the entities
   while (count < sizeof (points)/ sizeof (points[0])) {
      // make sure no point is duplicated
      dgBigVector p (100.0f * (float (rand()) / RAND_MAX - 1.0f), 100.0f * (float (rand()) / RAND_MAX - 1.0f), 0, 0) ;
      int i = 0;
      for (; i < count; i ++) {
         dgBigVector dist (p - points[i]);
         if ((dist % dist) < 1.0e-6) {
            break;
         }
      }
      if (i == count) {
         points[count] = p;
         count ++;
      }
   }

   // how to use it
   ClosestNeighborg closertNighborg (&allocator, points, count);
   for (int i = 0; i < 20; i ++) {
      int arrayOut[20];
      int index = rand () % (sizeof (points) / sizeof (points[0]));
      int count = closertNighborg.GetClosestPoints (index, arrayOut, sizeof (arrayOut) / sizeof (arrayOut[0]));

      count *=1;
   }

   return 0;
}


all you need to do is to add librar Core as a dependency to you project, and Badbin Badabum you completeley perfect closet point to and body.
be happy you are getting and algorithm that many many PHD fall, in fatc to oeth algorthm si better that this, teh sui teh abs9oulet best, fatser and more elgant of all.

I did not implemented the function Add Point and Remove point yet, because I have to make a small modifcationt to the core library to support that.
but you have enought to go on, see how that goes.

I also added a Debug function so that you can see in real time how the point set is triangulated.
basically if you render the triangulated you will see that the point set in triangulated optimal triangulation, in the sence that each triangle has the largest possible area.

there are ton of cool things you can add, like recursive search for Path finding, and get almost human like path finding.
BTW there is a Path finding in the Core library too.

[KingSnail]

Thanks a lot, I will post my results here when I have it working.

[KingSnail]

Ok I am working with this now.
I am having trouble to understand:
closertNighborg.GetClosestPoints(...);
that gets closest points but how close?
If I have 2 players and they are apart like 100000 units.
If I query cloest points for player 1 does that mean that it
will give me the player that was 100000 units away? since he is closest?

Do I still have to check distance? or does this algorithm incorporate it.
I havent compiled it yet, just trying now.

Edit: This code is concurrency unsafe? I guess so cos it just crashed.
I guess I will try to run it after NewtonUpdate on the same thread.
Does it need NewtonCriticalSection?

Edit: Cant get it to stop crashing even on same thread as newton. Allways crashes here:


Inside the loop that goes through every player (5 players total) but BigVector is still [1000];

Code: Select all

dgBigVector point(indexx + 12, indexx +22, 0.0f, 0.0f); //Test values, I tried with real values as well
BigVector[indexx] = point;


GetClosestPoint function:

Code: Select all

extern dgBigVector BigVector[1000];
dgMemoryAllocator allocator;
   dgInt32 count = 5; //tried 0, still crash but elsewhere
   ClosestNeighborg closertNighborg(&allocator, BigVector, count);
   for(int i = 0; i < 5; ++i)
   {
      int arrayOut[2];
      int count = closertNighborg.GetClosestPoints(i, arrayOut, sizeof (arrayOut) / sizeof (arrayOut[0]));
      count *=1;
      std::cout << "arrayOut[0] = : " << arrayOut[0] << " " << "arrayOut[1] = : " << arrayOut[1] << " " << "count = " << count << std::endl;
   }


[Julio Jerez]

closertNighborg.GetClosestPoints(...);
that gets closest points but how close?
If I have 2 players and they are apart like 100000 units.
If I query cloest points for player 1 does that mean that it
will give me the player that was 100000 units away? since he is closest?

Do I still have to check distance? or does this algorithm incorporate it.
I havent compiled it yet, just trying now.

This is correct, it is what I was explaing to you before, closest point does not means the point within a radius.
Point within a radius is the wrong thing to do, and it is what lead to bugus AI in games all the time.

if you have a set of players and one player is a 100000 kylometer away, there will be a sub group of players closer than the one than any other
they will be far away but it will be the closer.
if you want the bodies in a radius, you still can do it by simplest test if the set of closet point found by the function are inside a radius.
But the algorithm is still the same, and it is still efficient.

Here is example the can lead to Catastrofic consecuences if you treat it like Game programers solve problems.

Say you are an astromer in charge to detereminig what Askeroid post a Thread to the Planet.
Say you make yor observation and you use a computr to find out what ponit of the possibble observed asteroid are Cloaser to the planer
in your argorithm you use for the closer point with in say the distance from earth to the the planet Venus, and you neglet all others.
but guess what, you find a -0.5 mile rock and you sonud the alarm, bu you did not even realised that there was just a rock 100 mile wide rock just 1 mile away just outside the radius,
but you did not even include in your search becaus eteh comuter was instrute to serach for rocks with it some radius.
you will be the scienties reponsable you the destruction of the planet, because given enough time that 100 mile asteroid could be deflected,
but instead we deflected an insiginifican 0.5 Rock.
how is that for Game AI programming AI?