TerrainBlock structure for pathnode generation

#1 I'm not sure if this helps, but to answer a question in your code (if you haven't figured that out already):

Dirt->getHeight(Point2F(NodePos.x,NodePos.y),&NodePos.z);
// hm, this return totally different (higher) values: WHY?
//NodePos.z = Dirt->getHeight(NodePos.x, NodePos.y);

getHeight(NodePos.x, NodePos.y) is returning the height of the terrain as it is contained in the heightmap (it actually accesses the heightmap), the x and y-coords are the (U32) coords of the corresponding "pixel" in the heightmap.

getHeigth(Point2F(NodePos.x,NodePos.y),&NodePos.z) however calculates an interpolated height value from the 4 corner vertices of the corresponding terrain GridSquare / the 4 corner pixels of the heightmap

These two methods might thus produce different height values for the same coords (actually they're not the same, since getHeight(NodePos.x, NodePos.y) uses U32 parameters, and getHeigth(Point2F(NodePos.x,NodePos.y),&NodePos.z) uses F32 parameters and rounds/scales them internally).

I'm not sure if that is the reason for your problem, however, I hope this helps anyways.

Stefan.

#2 Stefan, thanks a lot!
That makes perfect sense, yes... although it doesn't solve my problem, I fear...
I should be okay then using
"getHeigth(Point2F(NodePos.x,NodePos.y),&NodePos.z)",
I think... but somehow the scale/orientation/whatever of my grid still doesn't match my terrain structure... :(
So there must be some other general problem with the TerrainBlock size or something I guess... any ideas? :)

#3 I don't think that squareSize of TerrainBlock::BlockSize is the problem, since if there was something wrong with them, your grid should be correct but maybe not large enough and the density of the path nodes could be not the way you wanted it to be. As far as I understand TerrainBlock::BlockSize, it is just the width of the TerrainBlock (the number of TerrainSquares / width of the heightmap in pixels) and the squareSize is just the width of a single square in world units. From what I can see, you use it just like that. So either we both misunderstand something, or the error must be something else.

Does the ConsoleMethod of TerrainBlock getTerrainHeight return the same height values for the same coords? I noticed that it subtracts some offset from the coords (don't know any details, I just had a quick look).

Are there errors with every terrain you try? The first of your pictures seems to show a correct grid.

Stefan.

#4 FYI, we figured this out. Just letting you know so no one mulls over it. Beffy may post the code here, I dont know :)

-jared

#5 Heh, yeah, Stefan, you were on the right track with that offset calculation in the getHeight() console function... and thanks to Jafa we have solved this issue - kudos and a big thanks to him!! :D
So here is the *working* code to place nodes on the terrain:

Point3F pos = Dirt->getPosition(); // Grab the position of the terrain block
	Point3F terrainOffset;
	Dirt->getTransform().getColumn(3, &terrainOffset); // From world origin, what is the terrain's offset?
	const F32 dirtLength = F32(TerrainBlock::BlockSize * Dirt->getSquareSize());
	// How large is this terrain block (X, Y)

	RectI &area = RectI(pos.x, pos.y, pos.x + dirtLength, pos.y + dirtLength);
	// This rectangle represents the terrain block

	const S32 GridSize = 40;
	Point2F GridStart(area.point.x, area.point.y); //Start location for our grid

	F32 xStep = dirtLength / GridSize; //How much do we want to increment each step?
	F32 yStep = dirtLength / GridSize;


	Point2F tempPos(0.0f, 0.0f);
	Point3F worldPoint(0.0f,0.0f,0.0f);
	S32 GridX,GridY = 0;
	F32 tempX, tempY, tempZ = 0.0f;

	cNode *NodeGrid[GridSize][GridSize];

	for (GridY = 0; GridY < GridSize; GridY++){
		for (GridX = 0; GridX < GridSize; GridX++) {

			tempX = GridStart.x + (xStep * GridX) - terrainOffset.x; //Get our temp Xlocation in relation to the terrain's (0,0) corner
			tempY = GridStart.y + (yStep * GridY) - terrainOffset.y; //Same for the Y
			tempZ = 0;

			tempPos = Point2F(tempX, tempY); //Build up a temporary point, just to be clean
			Dirt->getHeight(tempPos, &tempZ);

			Point3F worldPoint(tempX + terrainOffset.x, tempY + terrainOffset.y, tempZ + terrainOffset.z); //Find where this point is in world coords

			
			//Con::errorf("NODE HEIGHT at (%f,%f): %f -- getHeight() would return: %i", worldPoint.x,worldPoint.y,worldPoint.z, Dirt->getHeight(worldPoint.x, worldPoint.y));
			char nameBuffer[256];
			dSprintf(nameBuffer, 255, "Grid(%d,%d)", GridX,GridY);
			cNode *ONode = new cNode();
			ONode->mName= StringTable->insert(nameBuffer);
			ONode->mPos=worldPoint;//NodePos;
			ONode->ID=0;
			NodeGrid[GridX][GridY] = ONode;
		}
	}

And here are some pics!
Yay! :)

#6 Yeehaa!

#7 Note that Stefan uses a cNode class object for his stuff. When I was testing it I simply made an array of Point3Fs, and had it load an fxRenderObject at the points I received. The visual results are the same :)

See?

#8 Hm, got a rather strange problem here if I increase the "GridSize" var...
e.g. setting it to 50 or 60, which should increase the node count and decrease the distance between them, which it seems to do (see this pic), BUT, it doesnt seem to render my fxRenderObjects for all of them (see this pic) - looks like only about 1 half gets rendered...
now what's really strange is, the pathfinding doesnt work anymore ... it works for GridSize = 40; (see this pic), but not for 50 or 60 (although there *should* be more nodes now and pathfinding should work *better*...
So... did I hit some Torque limit with my 50x50 grid? (but I didnt even turn on the fxRenderObjects, I've only instantiated my Node objects at each grid point... they aren't derived from SimObject or anything...
any ideas? Jafa, maybe you can try to change the GridSize, too, to see if that changes anything for you?
Thanks a lot! :)
Here is the "Node" class, if that matters... :)

class cNode
{

public:
	Vector<cAIPathNodeList*> mPathList;
	Vector<cEdge* >	m_edgeList; // All outgoing edges from this node
	S32				m_idx; // Index into AI Manager's list...
	F32			m_fCost; // used in shortest path
	bool			m_bVisited;
	cNode*			m_pPrev; // previous node in the shortest path
	S32 ID;

	StringTableEntry mName;
	Point3F			mPos;

	cNode(Point3F loc ) 
	:mPos( loc )
	{
	mPathList.clear();
	m_edgeList.clear();
	}

	cNode();
	~cNode() {m_edgeList.clear();};
	void Relax();

	void AddOutgoingEdge( cEdge* edge )
	{
		m_edgeList.push_back( edge );
	}

	void AddDualEdge(cNode* to, F32 distance);
	void AddEdge(cNode* to, F32 distance);
	void AddPath(cAIPathNodeList *Path);
	bool FindPath(cAIPathNodeList *Path, S32 Dest);

	friend class cEdge;

};

Here is the cNodeList class, which keeps track of all the "connected" Nodes:

class cNodeList
{
public:
	cNodeList();
	~cNodeList();
	Vector<cNode*> Nodes;

	bool bShowFinalPath;
	bool bShowConsideredNodes;

	void AddNode(cNode *nn) {Nodes.push_back(nn);}
	void RemoveNode(cNode *nn) {Nodes.erase(&nn);};
	void AddList(cNodeList *list);
	bool ShortestPath( cAIPath* pPath, S32 FromIdx, S32 ToIdx);
	bool ShortestPath( cAIPath* pPath, StringTableEntry NodeFrom, StringTableEntry NodeTo );
	cNode* FindCheapestNode();
	void InitShortestPath();
	Point3F getLocation(StringTableEntry N2);
	S32 getNodeIndex(StringTableEntry N);
	S32 getNodeIndex(S32 ID, StringTableEntry N);
	StringTableEntry getNodeName(S32 idx);
	void Relink(cNodeList *list, S32 NodeID);
	cNode* FindNewLink(S32 idx, cNodeList *list);
	void ReLinkNode(S32 nIdx, S32 lIdx, cNodeList *list);
};

After I've gone over the terrain grid I do a little "selection" pass and connect the nodes that are in LOS to each other... nodes that don't link at all all discarded and the rest of the nodes are stored in that very NodeList:

// LOS tests here
...
S32 ZeroLinks;
ZeroLinks = 0;
for (GridY = 0; GridY < NodeDensity; GridY++)
{
	for (GridX = 0; GridX < NodeDensity; GridX++)
	{
	if (NodeGrid[GridX][GridY]->m_edgeList.size() == 0)
		{
		ZeroLinks++;
		continue;
		}
	NodeGrid[GridX][GridY]->m_idx=AINodes->Nodes.size();
	AINodes->AddNode(NodeGrid[GridX][GridY]);
	Con::errorf("Node added: %s at (%f,%f,%f)", NodeGrid[GridX][GridY]->mName,NodeGrid[GridX][GridY]->mPos.x,NodeGrid[GridX][GridY]->mPos.y,NodeGrid[GridX][GridY]->mPos.z);
	}
}

Con::errorf("Eleminated %d nodes (did not link)",ZeroLinks);

Does anybody see any problem? :/

#9 hm, that is really strange... the Nodes seem to be all over the terrain file all the time, but if I increase the GridSize, they are only rendered up to certain points... you can see it on these two pics: www.beffy.de/beffyjsp/suck.jsp?param=http://tork.zenkel.com/uploads/pics/grid&lo...
both were taken with GridSize=40, the upper pic shows that the nodes/fxRenderObjects are only rendered up to the middle tree you see there, the lower pic shows that the Nodes *should* be going on above that middle tree - at least they seem to be there - (if I set GridSize to 30, they go on above that, if I set it to 50, the rendering even stops below that - see the upper pic)...

And, as I've mentioned, even stranger, the bot doesnt seem to be able to use the "invisible" nodes, it can't find a path if I set the GridSize above 40 (cause then there aren't enough Nodes between startpoint and targetpoint it seems...)
Does this make any sense? Do I have any stupid error in my grid setup loop or is there something really strange going on?
Jafa, where are you? ;)

#10 Alrighty, as it turned out, the problem with not rendering all the "node markers" I am using (fxRenderObjects by Melv) seems to be the limit of ghostable objects in Torque (1024), so the maximum number of rendered objects in Torque seems to be 1024 (at least that is what I've found in some thread).
Sad, but not a real problem, I don't need all my nodes to be rendered...
And the problem with the bots not finding a path when using a 50*50 or 60*60 grid seems to be the distribution of nodes then... our pathfinder isn't very intelligent yet, so he simply coulnd't find a path (here are the nodes it examined with 50*50 nodes) - it works fine if the grid is 40*40 (really not otimal, but it found a path around that building), 70*70, 80*80 or up (although 80*80 already is kind of an overhead I think) ...
Now on to optimization and extension (better weighting functions, taking terrain type, slope, etc. into account, realistic turning between the nodes, etc. etc.)

#11 hm, okay, now I've got another little problem, there are way too many nodes discarded by my raycast which I use to connect every 4 nodes together...
The red dots on these pics show the discarded nodes only, and the most of them shouldnt be discarded at all...
here is the function I am using:

bool AIManager::NodeRay(Point3F src, Point3F dest)
{
RayInfo dummy;
        // "Dirt" is the TerrainBlock
	if (!Dirt->getContainer()->castRay(src,dest,
		InteriorObjectType | StaticShapeObjectType | StaticObjectType , &dummy ) ) 
		{
		Con::warnf("dangit! RAYCAST failed!! Points: (%f,%f,%f) - (%f,%f,%f)", src.x,src.y,src.z,dest.x,dest.y,dest.z);
  		return false;
		}
return true;
}

Anyone see any problems with this?
I call it for the 3 "neighbours" of a node like this:

if (!NodeRay(NodeGrid[NodeX][NodeY]->mPos,NodeGrid[NodeX+1][NodeY]->mPos) ) 
		{
		Point3F DistVec = NodeGrid[NodeX][NodeY]->mPos - NodeGrid[NodeX+1][NodeY]->mPos;
		F32 Distance = DistVec.len();
		// TEST beffy: add height difference, too:
		Distance += GetSlopeBetweenNodes(NodeGrid[NodeX][NodeY], NodeGrid[NodeX+1][NodeY]);
		NodeGrid[NodeX][NodeY]->AddDualEdge( NodeGrid[NodeX+1][NodeY],Distance);
		}
	
	if (!NodeRay(NodeGrid[NodeX][NodeY]->mPos,NodeGrid[NodeX+1][NodeY+1]->mPos) ) 
		{
		Point3F DistVec = NodeGrid[NodeX][NodeY]->mPos - NodeGrid[NodeX+1][NodeY+1]->mPos;
		F32 Distance = DistVec.len();
		// TEST beffy: add height difference, too:
		Distance += GetSlopeBetweenNodes(NodeGrid[NodeX][NodeY], NodeGrid[NodeX+1][NodeY+1]);
		NodeGrid[NodeX][NodeY]->AddDualEdge( NodeGrid[NodeX+1][NodeY+1],Distance);
		}	
	
	if (!NodeRay(NodeGrid[NodeX][NodeY]->mPos,NodeGrid[NodeX][NodeY+1]->mPos) ) 
		{
		Point3F DistVec = NodeGrid[NodeX][NodeY]->mPos - NodeGrid[NodeX][NodeY+1]->mPos;
		F32 Distance = DistVec.len();
		// TEST beffy: add height difference, too:
		Distance += GetSlopeBetweenNodes(NodeGrid[NodeX][NodeY], NodeGrid[NodeX][NodeY+1]);
		NodeGrid[NodeX][NodeY]->AddDualEdge( NodeGrid[NodeX][NodeY+1],Distance);
		}
	}

#12 Hooooray!! :D
Guess what... it works:)
This is the path I get from completely auto-generated nodes: tork.zenkel.com/uploads/pics/grid27.jpg
I can also add nodes to the graph manually, which gives me tha ability to generate a very nice, almost perfece path: The "fix" for the raycast was easy, although I dont understand the reason really... it seems that the terrain collided with "itself"...
I've only raised the 2 points a bit, now it works great:

bool AIManager::NodeRay(Point3F src, Point3F dest)
{
RayInfo dummy;

	// hokay, we gotta correct the height value of the nodes,
	// cause otherwise the terrain is stupid enough to collide with itself :P
	F32 zAdd = 0.8;
	Point3F start(src.x,src.y,src.z+zAdd);
	Point3F end(dest.x,dest.y,dest.z+zAdd);
	if (!Dirt->getContainer()->castRay(start,end,
		InteriorObjectType | StaticShapeObjectType | StaticObjectType , &dummy ) ) 
		{
		Con::warnf("dangit! RAYCAST failed!! Points: (%f,%f,%f) - (%f,%f,%f)", src.x,src.y,src.z,dest.x,dest.y,dest.z);
  		return false;
		}
return true;
}

After that, only very few nodes are discarded:
tork.zenkel.com/uploads/pics/grid26.jpg
Cheers!