About Store Forum Documentation Contact



Post Reply 
Possible Pathfinding Bug
Author Message
fatcoder Offline
Member

Post: #1
Possible Pathfinding Bug
I believe I've found an issue with pathfinding.

I'm using Game::World.path().find(...) to find a path in the world between two points. I'm then using VI to draw lines between the returned points in the path. You can see this in the attached screenshot.

The problem is that the pathfinder appears to be detecting an "invisible" obstacle at the intersection of the game world areas. In the screen shot you can see the feint grey lines of the nav mesh. These lines all converge on the intersection of the 4 neighbouring areas. When trying to find a path near this intersection, the pathfinder returns the path shown in the screen shot, when in fact it should be a straight line.


Attached File(s) Image(s)
   
11-09-2011 01:22 PM
Find all posts by this user Quote this message in a reply
Esenthel Offline
Administrator

Post: #2
RE: Possible Pathfinding Bug
it's possibly between multiple nav meshes connections
it's issue in recast (not EE)
11-09-2011 01:41 PM
Find all posts by this user Quote this message in a reply
fatcoder Offline
Member

Post: #3
RE: Possible Pathfinding Bug
Does each world area use a separate nav mesh?
11-09-2011 02:17 PM
Find all posts by this user Quote this message in a reply
Esenthel Offline
Administrator

Post: #4
RE: Possible Pathfinding Bug
yes - 1 PathMesh for each Area
11-09-2011 05:30 PM
Find all posts by this user Quote this message in a reply
fatcoder Offline
Member

Post: #5
RE: Possible Pathfinding Bug
Recast must be detecting a tiny gap between the the nav meshes that causes a problem at the corners. Perhaps it is possible to overlap the nav meshes at the joins by a very small amount?

Or, perhaps the pathfinding algorithm could ignore any generated waypoints in the path that occur at exactly the intersection between 4 neighbouring areas?
11-10-2011 12:49 AM
Find all posts by this user Quote this message in a reply
Esenthel Offline
Administrator

Post: #6
RE: Possible Pathfinding Bug
you can try reporting the issue on recast site, http://code.google.com/p/recastnavigation/
11-10-2011 12:53 AM
Find all posts by this user Quote this message in a reply
fatcoder Offline
Member

Post: #7
RE: Possible Pathfinding Bug
I have reported the issue on the recast site and have been in discussion with Mikko (recast developer).

Anyway, I have done some further testing and found that the problem only seems to exist with my test world. I'm not sure if my test world is just corrupted and needs to be rebuilt from scratch, or if it just happens to be exposing a bug in a certain way.

I have attached my test world to this email, which you can load with a fresh install of the SDK. I then modified the World tutorial in the Game Basics folder like this below. This will load the test world and then you can perform ray casts in the world by holding down the left mouse button and dragging the mouse. It will ray cast between your start position and the mouse position and draw a line. If the line is white, then the ray cast passed. If it is red, then the ray cast failed.

Try doing a ray cast from one area to another above the rocks in the test world. You will see that it fails as soon as it cross the boundary between one area and the other. I have also noticed, that if you load the test world in the Editor and remove the three rocks, then all the ray casts work properly again. Even after putting the rocks back in, they still work correctly.

So this issue only seems to be happening with this test world exactly the way it is???

Code:
/******************************************************************************/
#include "stdafx.h"
/******************************************************************************

    When writing applications with worlds, you need to additionaly include all the Headers generated by the World Editor
    these Headers are stored in the "enum/_enums.h" file in your Game Data folder
    for more information about Enums and Headers please check World Editor documentation.

/******************************************************************************/
#include "../../../../../data/enum/_enums.h"
/******************************************************************************/
Game::ObjMemx<Game::Static> Statics; // container for static    objects
Game::ObjMemx<Game::Item  > Items;   // container for item      objects
Game::ObjMemx<Game::Chr   > Chrs;    // container for character objects
Vec start,end,hit_pos;
/******************************************************************************/
void InitPre()
{
   App.name("World Manager");
   App.flag=APP_FULL_TOGGLE;
   DataPath("../data");
   Paks.add("engine.pak");

   D.full(false).sync(true).hpRt(true).hdr(true);

   Cam.dist =10;
   Cam.yaw  =-PI_4;
   Cam.pitch=-0.5f;
   Cam.at.set(16,0,16);
}
/******************************************************************************/
Bool Init()
{
   Physics.create(CSS_NONE, true, "../Installation/PhysX");

   Sun.image=Images("gfx/sky/sun.gfx");
   Sky.atmospheric();

   Game::World.init(); // initialize world, optionally you can change default parameters here

   // once the world is initialized, we need to tell the world 'which class handles which type'
   // this is done by assigning memory containers to certain Object Types defined in Game Enums (which were used in the World Editor)
   Game::World.setObjType(Statics, OBJ_STATIC)  // set 'Statics' memory container for 'OBJ_STATIC' objects
              .setObjType(Items  , OBJ_ITEM  )  // set 'Items'   memory container for 'OBJ_ITEM'   objects
              .setObjType(Chrs   , OBJ_PLAYER); // set 'Chrs'    memory container for 'OBJ_PLAYER' objects

   // now when the engine is set up properly we can start a 'new game' with a builded world
   Game::World.New("world/test.world"); // create the world by giving path to builded world

   // when the world is loaded it doesn't actually load all the terrain and objects into memory
   // it loads only information about them
   // you need to tell the world which terrain and objects you need to use at the moment
   // to do that call:
   Game::World.update(Cam.at); // which updates world to use only terrain and objects at given position, here camera position is used

   return true;
}
/******************************************************************************/
void Shut()
{
}
/******************************************************************************/
Bool Update()
{
   if(Kb.bp(KB_ESC))return false;
   CamHandle(0.1f, 100, CAMH_ZOOM|(Ms.b(1)?CAMH_ROT:0));

   Game::World.update(Cam.at); // update the world to given position

   if(Ms.bp(0))
   {
      PhysHit physHit;
      Vec screenPos, screenDir;
      ScreenToPosDir(Ms.pos(),screenPos,screenDir);
      if(Physics.ray(screenPos,screenDir*D.viewRange(),&physHit,IndexToFlag(AG_TERRAIN)))
         start = end = physHit.plane.pos;
   }
   else if(Ms.b(0))
   {
      PhysHit physHit;
      Vec screenPos, screenDir;
      ScreenToPosDir(Ms.pos(),screenPos,screenDir);
      if(Physics.ray(screenPos,screenDir*D.viewRange(),&physHit,IndexToFlag(AG_TERRAIN)))
         end = physHit.plane.pos;

      Flt hit_frac;
      Vec hit_normal;
      hit_pos.zero();
      Game::World.path().ray(start,end,&hit_frac,&hit_pos,&hit_normal);
   }

   return true;
}
/******************************************************************************/
void Render()
{
   Game::World.draw(); // draw world (this is done outside of 'switch(Renderer())' because world automatically detects active rendering mode)
}
void Draw()
{
   Renderer(Render);

   Game::World.path().draw(64,0.1f);

   if(Ms.b(0))
   {
      D.clearZ();
      if(end == hit_pos)
         D.line(WHITE,start,end);
      else
         D.line(RED,start,end);
   }
}
/******************************************************************************/


Attached File(s)
.zip  test.world.zip (Size: 227.32 KB / Downloads: 3)
11-24-2011 08:07 AM
Find all posts by this user Quote this message in a reply
fatcoder Offline
Member

Post: #8
RE: Possible Pathfinding Bug
OK, after more testing I have finally worked out that the problem can also be reproduced with a brand new world. It is not just limited to my test world attached in the previous post.

You can create the problem by creating a new world and inserting one rock object into the world. Then move the rock object down a little so that it is sitting in the terrain (partially under the terrain).

Then test the world using the code from my previous post. You will notice that the ray cast fails when trying to cross the border between some areas. Not all, only some, and it seems to be random which ones fail.

You can do pretty much anything else with the rock object. You can move it around on the terrain or up in the air. You can scale it or rotate it without a problem. It is only when you try to lower the rock down slightly into the terrain that you hit this bug.

If this is not an EE bug, but a recast bug, can you please post any useful info to the thread I started on the recast site to help get this problem fixed as it greatly impacts my current project that I have been working on for a long time now.

http://code.google.com/p/recastnavigatio...&start=100
11-24-2011 03:08 PM
Find all posts by this user Quote this message in a reply
Esenthel Offline
Administrator

Post: #9
RE: Possible Pathfinding Bug
I'll look into this in a couple of days (right now super busy grin )
11-24-2011 11:21 PM
Find all posts by this user Quote this message in a reply
fatcoder Offline
Member

Post: #10
RE: Possible Pathfinding Bug
Thanks Esenthel. Much appreciated. smile
11-25-2011 12:27 AM
Find all posts by this user Quote this message in a reply
Esenthel Offline
Administrator

Post: #11
RE: Possible Pathfinding Bug
Why did you set MaxClimb to 0 ? pfft
it's causing the issues, I've discovered it after heavy debugging (neighbour tiles couldn't connect because of too small max climb value)
please notify the recast issue thread that the problem is gone after setting valid max climb.
11-30-2011 12:10 AM
Find all posts by this user Quote this message in a reply
fatcoder Offline
Member

Post: #12
RE: Possible Pathfinding Bug
Wow, I didn't even think of that! Sorry you had to spend so much time debugging. I'll report this on the recast thread.

I'll adjust maxClimb up a little. After your debugging, did you happen to work out what would be the lowest possible value I could use for maxClimb and have it still work correctly? My agents have no ability to climb or step up steps, I want to force them to stay on flat ground.
11-30-2011 12:57 AM
Find all posts by this user Quote this message in a reply
Esenthel Offline
Administrator

Post: #13
RE: Possible Pathfinding Bug
next SDK will have the climb height clamped to min value of 0.1 (cell height) which seemed to work correctly
11-30-2011 01:03 AM
Find all posts by this user Quote this message in a reply
Demostenes2 Offline
Member

Post: #14
RE: Possible Pathfinding Bug
I dont know if this is related to this issue, but I made simple terrain, put some trees, etc...and character (your default) is sometimes stucked against invisible barrier. No matter if flying 20m above ground, or just walking.
12-12-2011 02:14 AM
Find all posts by this user Quote this message in a reply
Esenthel Offline
Administrator

Post: #15
RE: Possible Pathfinding Bug
if stuck then it means it's physics issue, please attach screen from world, and include physics view (/ key)
12-12-2011 09:42 PM
Find all posts by this user Quote this message in a reply
Post Reply