Game Development Community

Automatic A* node generation (need assistance)

by Peter Simard · in Torque Game Engine · 07/05/2006 (10:52 pm) · 7 replies

Hey everyone. I am working on a system to automatically generate navigation nodes throughout a level for basic objects (trees, fences, rocks, etc). I am currently stuck on a bit of 3D math. I am trying to get a list of the 4 points around an objects bounding box. The getWorldBox() command returns the min and max size of the box, but unfortunately it is not accurate if you rotate the object (see screenshot).

Can anyone provide some pseudocode to get these 4 points? I took a look at the bounding box rendering code for shapebase, but I was unable to convert it into anything useful.

I would like to get the extents of the red box, instead of the yellow:
www.crownsofpower.com/images/boundsBox.jpg
NextNext Thread
PrevPrevious Thread
More from Torque Game Engine


Associate Orion Elenzil
Real Life Plus
#1
07/05/2006 (11:56 pm)
I feel like this info is more or less sitting there in engine code,
but i'm not sure. i'll try to look into it tomorrow.

good luck, orion.

Associate Stefan Beffy Moises
#2
07/06/2006 (12:36 am)
Hey, I had that problem once, too:
www.garagegames.com/blogs/8239/5917
Here's some example code how to use the local/object space of an object:
// check for blockers
   Vector<NavMeshBlocker*> objects;
   U32 mask = AIBlockerObjectType;
   gServerContainer.findObjects(mask, AINavGraphFindObjectsCallback, &objects);

   for(int i = 0; i < objects.size(); i++)
   {
      Point3F blockerPos = objects[i]->getPosition();// gets the center!
      Box3F blockerBox = objects[i]->getObjBox();
      // do the check in objectspace!
      Point3F localNodePos = pos;
      // transform the pos to local space
      objects[i]->getWorldTransform().mulP(localNodePos);
      // if the object is scaled
      localNodePos.convolveInverse(objects[i]->getScale());
      if(blockerBox.isContained(localNodePos))
      {
         // filter it
         return true;
      }
   }
Not exactly what you need I guess, but maybe it gives you an idea for your problem...

Torque 3D Owner Peter Simard
Default Studio Name
#3
07/06/2006 (12:37 pm)
Thanks for the reply. Ive been trying to work with the Obj box and World box but Im still comming up short. I tried this bit of code.. it seemed to come close but its still not working. Any help would be appreciated.

%worldBoxCenter = %obj.getWorldBoxCenter();
     %objBox = %obj.getObjectBox();
     %objBox_min = vectorAdd(getWords(%objBox, 0, 2), %worldBoxCenter);
     %objBox_max = vectorAdd(getWords(%objBox, 3, 5), %worldBoxCenter);

Torque 3D Owner Peter Simard
Default Studio Name
#4
07/07/2006 (7:52 pm)
*bump*

Associate Ben Garney
#5
07/08/2006 (12:15 am)
C'mon, can't wait 7 hours for an answer? :)

The world box is the axis aligned bounds of the object. The object box is the object-aligned bounds (often expressed relative to object center, too).

That code snippet won't work as you're adding the bounds to the center - so getting an axis aligned bounding box of the min/max point of the object box, which is way wrong!

You're better off just dealing with worldbox if you can, it's going to work a lot better with any axis-aligned processing you're doing and in general the overhead isn't too bad. YMMV of course.

Torque 3D Owner Peter Simard
Default Studio Name
#6
07/08/2006 (1:24 am)
Thanks for the reply Ben. I will be processing the nodes only once at run time so speed is not an issue. I think I understand why its not working.. but I am still lost in how to get it working. Sounds like it should be a rather trivial task, but I have a lot of trouble working with 3D math. Any input on a solution would be greatly appreciated. Thanks


P.S. To be fair it was 31 hours not 7 :)

Associate Ben Garney
#7
07/08/2006 (1:27 am)
Hey, you're right. My bad. :)

What I've done is just cast rays to see what I'm hitting. So I don't even need to know bounds for lots of stuff.