Terrain Grid project

#1 Man, that is pretty much an identical solution to the one that I've come up with for the demo I'm working on. Here's what we do, and it works pretty well for us:

We currently parse the terrain at level-load time, on the server, to generate the node information. This only takes a few milliseconds to do, so we are not currently saving/loading this info to/from a file.

Instead of parsing each pixel of the 256x256 height map, we only parse the terrain that lies within the mission area as defined by the .mis file, with nodes spaced 'x' units apart. We sample the normals of the terrain surrounding each node, and store an average of this value in the node. This then gives us the 'steepness' of the terrain beneath the node, so we can limit the movement of different units to different slope values.

We use our own implementation of an A* pathfinder to navigate through the node network, using a combination of terrain slope, water, and building placement to control the path.


In that image, yellow dots represent reachable nodes for the unit calling the pathfinder, red represents nodes that are too steep to pass, and the blue line is the resulting path.

We also check to see if a node lies in water, and mark them accordingly.


Building placement causes the nodes beneath the building to be marked as being built upon, and building destruction unmarks the node. We don't currently treat trees as obstacles.


For the pathfinder, we have implemented two levels of complexity. When a player clicks on a destination, the pathfinder first does a quick straight line check to see if the destination can be reached directly, and if so, the unit moves there. This is pretty much what you're suggesting too, and works fine on sparse, mainly flat maps. If a straight line path does not exist, we then feed the path request to the A* pathfinder to find a route. Some of the maps we've been working with can have over 100,000 nodes, so to keep everything working in real time, we distribute the A* calculations over multiple ticks, and this allows us to pathfind for many tens of units with no slowdown.

So, I'd say you were on the right track :)

#2 Wow, that looks awesome, I love the way you have the nodes visible in the editor, though I have a question about pathfinding,

In the first screenshot at the top, I see a path leading up to a mountain, and it took a left turn to get around the mountain, what made it know that that was the best choice, and not to take a right (Which would be a much longer route)? It's hard to imagine how to program a blind computer to see :)

#3 For my attempt at implementing this I'm alread y having trouble with the simple stuff, Raycast syntax:

Trying to figure out the syntax, I decided to convert TDN Raycast Example to a simple function, for practice.

Point3F castARay(Point3F myPoint.x, Point3F myPoint.y)
// Setup the currentContainer to either the server container or the client container.
// In your code you might know if you are on the server or not already. In which case you
// could use the gClientContainer or gServerContainer directly
Container * currentContainer;
if(isClientObject()) // Client object.
{
currentContainer = &gClientContainer;
}
else // Server object.
{
currentContainer = &gServerContainer;
}

RayInfo rInfo; // Will return info on what the castRay found including object information.
Point3F start, end;
Point3F myPoint; // Init this to the point which you want to goto

start.x = end.x = myPoint.x; //some x (whatever value you want)
start.y = end.y = myPoint.y; //some y (whatever value you want)
start.z = 2000; // Really high, might be over kill
end.z = -2000; // really low, might be overkill

// Look for flags set for pretty much everything.
// Note: An object could have more than one flag set
if(currentContainer->castRay(start, end,
StaticObjectType |
InteriorObjectType |
WaterObjectType |
ShapeBaseObjectType |
StaticShapeObjectType |
ItemObjectType |
TerrainObjectType |
StaticTSObjectType
, &rInfo))
{
return myPoint.z = rInfo.point.z;
}
else
{
// didn't find anything, no TerrainObjectType or anything...
// you decide how to handle this error
}

}

As expected, I got errors


..\engine\core\mndObject.cc(181) : error C2146: syntax error : missing ';' before identifier 'castARay'
..\engine\core\mndObject.cc(181) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(181) : error C2146: syntax error : missing ')' before identifier 'myPoint'
..\engine\core\mndObject.cc(181) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(181) : error C2059: syntax error : ')'
..\engine\core\mndObject.cc(186) : error C2059: syntax error : 'if'
..\engine\core\mndObject.cc(187) : error C2143: syntax error : missing ';' before '{'
..\engine\core\mndObject.cc(187) : error C2447: '{' : missing function header (old-style formal list?)
..\engine\core\mndObject.cc(190) : error C2059: syntax error : 'else'
..\engine\core\mndObject.cc(191) : error C2143: syntax error : missing ';' before '{'
..\engine\core\mndObject.cc(191) : error C2447: '{' : missing function header (old-style formal list?)
..\engine\core\mndObject.cc(195) : error C2146: syntax error : missing ';' before identifier 'rInfo'
..\engine\core\mndObject.cc(195) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(195) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(196) : error C2146: syntax error : missing ';' before identifier 'start'
..\engine\core\mndObject.cc(196) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(196) : error C2086: 'int Point3F' : redefinition
..\engine\core\mndObject.cc(181) : see declaration of 'Point3F'
..\engine\core\mndObject.cc(196) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(196) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(197) : error C2146: syntax error : missing ';' before identifier 'myPoint'
..\engine\core\mndObject.cc(197) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(197) : error C2086: 'int Point3F' : redefinition
..\engine\core\mndObject.cc(181) : see declaration of 'Point3F'
..\engine\core\mndObject.cc(197) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(199) : error C2143: syntax error : missing ';' before '.'
..\engine\core\mndObject.cc(199) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(199) : error C2086: 'int start' : redefinition
..\engine\core\mndObject.cc(196) : see declaration of 'start'
..\engine\core\mndObject.cc(200) : error C2143: syntax error : missing ';' before '.'
..\engine\core\mndObject.cc(200) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(200) : error C2086: 'int start' : redefinition
..\engine\core\mndObject.cc(196) : see declaration of 'start'
..\engine\core\mndObject.cc(201) : error C2143: syntax error : missing ';' before '.'
..\engine\core\mndObject.cc(201) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(201) : error C2086: 'int start' : redefinition
..\engine\core\mndObject.cc(196) : see declaration of 'start'
..\engine\core\mndObject.cc(202) : error C2143: syntax error : missing ';' before '.'
..\engine\core\mndObject.cc(202) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
..\engine\core\mndObject.cc(202) : error C2086: 'int end' : redefinition
..\engine\core\mndObject.cc(196) : see declaration of 'end'
..\engine\core\mndObject.cc(206) : error C2059: syntax error : 'if'
..\engine\core\mndObject.cc(216) : error C2143: syntax error : missing ';' before '{'
..\engine\core\mndObject.cc(216) : error C2447: '{' : missing function header (old-style formal list?)
..\engine\core\mndObject.cc(219) : error C2059: syntax error : 'else'
..\engine\core\mndObject.cc(220) : error C2143: syntax error : missing ';' before '{'
..\engine\core\mndObject.cc(220) : error C2447: '{' : missing function header (old-style formal list?)
..\engine\core\mndObject.cc(225) : error C2059: syntax error : '}'
..\engine\core\mndObject.cc(225) : error C2143: syntax error : missing ';' before '}'
..\engine\core\mndObject.cc(225) : error C2059: syntax error : '}'

I have a feeling one of the errors(And I know there are many others besides this) is that I set the castARay functions datatype to Point3F, I'm not sure if that's valid. Another thing on datatypes, I'm still confused on how some end in asterisks*, and I'm not sure what that signifies. For example, that variable "currentContainer" initializes as a Container* datatype
Is it saying that this is a special in-game object? Right now whenever i come to an error with datatypes, I just use variants of asterisk and no asterisks to see if I can come up with one that works. That strategy doesn't work so good...

#4 I have no idea on the whole pathfinding idea, but I think I can help you with the ray casting.

You are wanting castARay to be a function, correct? In that case, there were a couple of things that caused the error:
1. There should be an open brackets after the function declaration.
2. When passing in the arguments, if you want to pass the variables of type Point3F then you would just pass myPoint (but since you are passing two arguments in, they both can't be the same name. If you only wanted to pass in the x or y variable of a point, you would change the Point3F to F32, and have to rename the variables.
3. If you wanted to return just the z position of the colliding object, that would be of type F32 instead of Point3F, and there is no reason to assign it to myPoint.z before you return it.

So, with all that said, this should work (I put my changes in bold):

[b]F32 castARay(Point3F firstPoint, Point3F secondPoint)
{[/b]
	// Setup the currentContainer to either the server container or the client container.
	// In your code you might know if you are on the server or not already. In which case you
	// could use the gClientContainer or gServerContainer directly
	Container * currentContainer;
	if(isClientObject()) // Client object.
	{
		currentContainer = &gClientContainer;
	}
	else // Server object.
	{
		currentContainer = &gServerContainer;
	}

	RayInfo rInfo; // Will return info on what the castRay found including object information.
	Point3F start, end;

	start.x = end.x = [b]firstPoint.x[/b]; //some x (whatever value you want)
	start.y = end.y = [b]secondPoint.y[/b]; //some y (whatever value you want)
	start.z = 2000; // Really high, might be over kill
	end.z = -2000; // really low, might be overkill

	// Look for flags set for pretty much everything.
	// Note: An object could have more than one flag set
	if(currentContainer->castRay(start, end,
                                                                       StaticObjectType |
                                                                       InteriorObjectType |
                                                                       WaterObjectType |
                                                                       ShapeBaseObjectType |
                                                                       StaticShapeObjectType |
                                                                       ItemObjectType |
                                                                       TerrainObjectType |
                                                                       StaticTSObjectType, 
                                                                       &rInfo))
	{
		[b]return rInfo.point.z;[/b]
	}
	else
	{
		[b]return 9999; // Don't want to return 0 since that could be valid.  Chances are, 9999 is an invalid number.[/b]
	}
}

Alternatively, you could have done (bold represents new changes, I didn't copy the whole function):

F32 castARay([b]F32 firstPoint, F32 secondPoint[/b])
{
	// Setup the currentContainer to either the server container or the client container.
	// In your code you might know if you are on the server or not already. In which case you
	// could use the gClientContainer or gServerContainer directly
	Container * currentContainer;
	if(isClientObject()) // Client object.
	{
		currentContainer = &gClientContainer;
	}
	else // Server object.
	{
		currentContainer = &gServerContainer;
	}

	RayInfo rInfo; // Will return info on what the castRay found including object information.
	Point3F start, end;

	start.x = end.x = [b]firstPoint;[/b] //some x (whatever value you want)
	start.y = end.y = [b]secondPoint;[/b] //some y (whatever value you want)
	start.z = 2000; // Really high, might be over kill
	end.z = -2000; // really low, might be overkill
 
       ...
}

#5 A* summed up is it finds the adjacent node closest in distance to the goal and the starting point. Of course that has problems navigating round U shapes.

#6 I assume air units ignore all ground collision, since they fly over it, but what about water units?

Instead of accessable and unaccessable, you'd need to have it where amphibeous and water units can pass over water without problems. And if a hill is too steep for most units, what if there is a special unit that can climb steep hills? Such as the spider bot in Total Annihilation.

Also, what about being able to hide units in buildings? The peasants rush and hide in the nearest guard tower or town hall, the soldiers occupy the bunker or guard tower to shoot from, etc.

Just more lines of classification, right?

Normal land unit hits water or steep cliff. Knows its impassible to them, and acts as it normally would, finding a path around it.
Cliff climbing unit hits steep cliff, and decides the fastest way to the other side is directly over it.
Boat hits land with his straightest path to destination, and decides to then plot a course around the coast to where its going.
Hovercraft goes around impassible steep mountains, but all other terrain is fine, wet or dry.
And air unit flies over them all laughing merrily as it rains down death upon them. ;)

#7 Hi guys,

I am thinking about implementing a pathing system too but i am already stuck with the basics of how to setting up a terrain graph.

Ok the size of the terrain is in the mis file i can chop that up to get the nodes but then my problem starts.

How do i access the terrain information like height and normals at that certain point?

Would be very thankful for any hints on where i could read up on this.

Thanks a lot to anyone who has some information for me:-9

#8 TerrData.cc there is array mHeightMap[i] thet is the data about height of the terrain.
with for loop you can go throught all points on the terrain and take height information.

class TerrainFile

declaration of array
U16 mHeightMap[TerrainBlock::BlockSize * TerrainBlock::BlockSize];