Sign in to follow this  
Deckards

3D RTS Terrain data structure

Recommended Posts

Hi, I have tried several 3D RTS map editors from Warcraft 3, C&C Generals, Lords of Everquest, Ground Control, AOM and the likes... I was wondering how the 3D terrain was stored in memory. I think there are 2 different ways: -The terrain is stored as a regular heightmap and the units tiles separately like in 2D RTS. -The terrain and the units info are stored in each tiles of the map array and the terrain vertices are duplicated at the edges. How do you think those games manage their 3D terrain?

Share this post


Link to post
Share on other sites
I've been thinking about this lately too, I'm writing my own level editor for an RTS game.

Really... they probably all very quite a bit, just do it in a way that seems organized to you. For example:

have a 2D array of nodes & a 2D array of squares
the catch is, the nodes are NOT duplicated ANYWHERE, the square classes just have pointers to the already existing nodes.

-you could have a vector of vectors of nodes (heightmap points)

-you could then generate a vector of vectors of tiles (each square has pointers to its 4 nodes)

-you can then generate 2 tries inside each of those tiles (each with its own normal vector)

-you can then step through the squars & extract your list of tris & construct your VBO or display list, perhaps with indexes (haven't done this yet in mine, heard about it)

make sense? however, any good design decision IMHO will NEVER EVER duplicate 2 isntances of the same vertice, just point to an already existing vertice. that way when your functions modify the nodes for one square, they are automatically modified for the squares that share that same node [vertice].

feedback? :)

Luke

Share this post


Link to post
Share on other sites
I would like to see an RTS where you can actually use multiple levels of play -- i e, real 3D. In that, you could store the terrain as a mesh, just like in any other 3D game, and use mesh node pathfinding. It'd be interesting to design gameplay and a UI that works well for such a world...

Share this post


Link to post
Share on other sites
do you know of some good resources that "teach" about mesh-node-pathfinding??? I think this is the route I'm headed towards, maybe not.

are you think about explicit or implicit graphs of nodes? Either way... are node graphs constructed upon creating/saving/loading of the terrain?

perhaps mesh node path-finding would look ok if you simple had real small distances between the nodes. however... that could become costly in terms of tree-searching.

Share this post


Link to post
Share on other sites
I use modified A* which works incredibly well for the type of thing you are trying to do. We do it when saving and loading and also when a new object is put on the map. It breaks it down into quads so that real-time editing is possible.
-Greg

Share this post


Link to post
Share on other sites
Quote:
have a 2D array of nodes & a 2D array of squares
the catch is, the nodes are NOT duplicated ANYWHERE, the square classes just have pointers to the already existing nodes.

It looks like the design of Dungeon Siege. There was a paper by Gas Powered Games from a GDC explaining how a node-based map was designed for more flexibility with full 3D engine and non equal tiles.

It looks a bit complicated for 3D RTS wich use equally dimensioned tiles.

Share this post


Link to post
Share on other sites
depends on what you mean by equal dimension tiles, because of there is a decent amount of slope between some of the nodes of a tile... then there is a larger distance between those nodes than of nodes on an equal plane.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
doesn't warcraft 3 have slopes in it? its not a completely flat grid world is it? if it does have slopes, than perhaps you mean squares of equal size in the XY plane, but if there is any deviation in the Z plane (slope), then the square with the most slope is actually the largest square in 3d space.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I have made a 3D RTS editor for one of my games, but all it can do so far is render the tiles.

What I did, was basically the same thing I did for a 2D tiled game like a RPG or a RTS game. I have a 2d array, and with each array item specifying details like texture, animation frame, and then Y points 1 to 4. The Y points will determin the Y values for each four points of the time. The reason for this instead of using a hieghtmap table, is that for example, you wouldn't always want to use smooth mountain like terrain, so this way will let you do sharp cliff like edges.

For an example (in Visual Basic):

Dim dwWidth As Long, dwHeight As Long, aTiles() As TILE_DESC

Public Type TILE_DESC
Texture As Direct3DSurface8
YPoint(0 to 3) As Single
End Type

Public Sub Main()
dwWidth = 5
dwHeight = 5
ReDim aTiles(dwWidth * dwHeight) As TILE_DESC
End Sub

Public Sub SetTile(ByVal X As Long, ByVal Y As Long, Texture As Direct3DSurface8, ByVal YPoint1 As Single, ByVal YPoint2 As Single, ByVal YPoint3 As Single, ByVal YPoint4 As Single)
Dim dwAddress As Long
dwAddress = ((Y - 1) * dwWidth) + (X - 1)

With aTiles(dwAddress)
Set .Texture = Texture
.YPoint(0) = YPoint1
.YPoint(1) = YPoint2
.YPoint(2) = YPoint3
.YPoint(3) = YPoint4
End With
End Sub

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this