• Create Account

# Terrain generation in 3D Tile Based Game

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

11 replies to this topic

### #1Mr. Big  Members   -  Reputation: 109

Like
0Likes
Like

Posted 23 April 2013 - 07:37 AM

Hello everyone. First time XNA project here, so still learning the ropes.

My first idea for a starter project was to make a tile based game. Each movable terrain square would be one quad (or 2 triangles).

Then use some method to determine which tile the mouse is over and clicking it moves the player there.

So what would be the ideal way to do this in XNA? My first thought was to create a triangle strip and a text file with all the vertices and heights and load it in and draw it.

Any other suggestions?

### #2VladR  Members   -  Reputation: 722

Like
0Likes
Like

Posted 23 April 2013 - 08:15 AM

You do not want to mess with Tri Strips.

You may have read somewhere the incorrect notion that Tri Strips are more efficient then Tri Lists in terrain rendering, but that is simply not true, since with TriStrips, the best ration of actual vertex shader transforms against count of vertices is, at best, 1.00

However, with Tri Lists, it is possible to create a shape of indices that actually results in a 0.56 ratio - by making sure the indices go in such a special way that makes most use of post-transform vertex cache.

But it's something you don't have to worry about these days due to the simple fact that today's cards can churn out millions of triangles per frame. Unless, of course, you want to.

So, just stay with basic Indexed Triangles - it will make your debugging sessions shorter compared to TriStrips, since it can prove pretty hard to find that missing degenerate triangle that just broke your rendering...

VladR    My 3rd person action RPG on GreenLight:    http://steamcommunity.com/sharedfiles/filedetails/?id=92951596

### #3Burnt_Fyr  Members   -  Reputation: 1229

Like
0Likes
Like

Posted 23 April 2013 - 08:27 AM

I'm not familiar with XNA, so have no code but do have some input.

1) procedurally generate a grid of vertices such that there are m+1 * n+1 verts, where m and n are the dimensions of your terrain in quads.

2) Why strips over lists? While strips make sense as a performance standpoint, that has really not been an issue for years.I use lists for everything.

3) As long as your terrain doesn't include overhangs, a simple height map is all that is required.(use a gray scale texture with same dimensions as your grid))

4) Use your heightmap to get the height at each vertices.

5) picking is what your looking for( how to determine what your mouse is clicking) use the mouse coords, unproject them to crate a ray from camera position. Intersect that ray with your triangles, that tells you which tile is hit, and which tile your unit should move to.

There is a long road ahead, but it's been done by others before, keep at it and you will succeed!

### #4VladR  Members   -  Reputation: 722

Like
0Likes
Like

Posted 23 April 2013 - 08:45 AM

2) Why strips over lists? While strips make sense as a performance standpoint,

No. They don't. They are actually horribly inefficient in terrain rendering.

Think about it. With strips, you are always reusing last two vertices for current triangle.

With a triangle list of the terrain heightmap, it is possible (I know, because I implemented it) to create a shape that for a 100x100 grid (20,000 tris) executes Vertex Shader only 056*20,000 times - simply because it reuses the vertices that are in post-transform vertex cache and keeps the cache warm with last 24 vertices all the time. The variant with 0.67*20,000 is easier to code, though.

With TriStrip, the best you can get is  1.01 *20,0000

VladR    My 3rd person action RPG on GreenLight:    http://steamcommunity.com/sharedfiles/filedetails/?id=92951596

### #5Mr. Big  Members   -  Reputation: 109

Like
0Likes
Like

Posted 23 April 2013 - 09:53 PM

Ok cheers for the tips. I only chose triangle strip because I thought it was more efficient at drawing triangles. That was what they taught us at university anyway, but that was a long time ago. Haven't really done any game programming since I finished - this is my first foot back in the water.

Are there any tutorials on drawing triangle lists? Or some jumping-in-to-xna guides? I tried following the MSDN tutorials but they seem to miss out key important parts to get things done that a fresh person to XNA wouldn't have any idea about.

Edit: This is what I've come up with so far but its not drawing anything.

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;
using Microsoft.Xna.Framework.Net;
using Microsoft.Xna.Framework.Storage;

namespace RO3
{

/// <summary>
/// This is the main type for your game
/// </summary>
public class Game1 : Microsoft.Xna.Framework.Game
{
Matrix worldMatrix;
Matrix viewMatrix;
Matrix projectionMatrix;

GraphicsDeviceManager graphics;
SpriteBatch spriteBatch;
GraphicsDevice device;
Effect basicEffect;

VertexPositionColor[] primitiveList;

int points = 8;
short[] triangleListIndices;

public Game1()
{
graphics = new GraphicsDeviceManager(this);
Content.RootDirectory = "Content";
}

protected override void Initialize()
{
graphics.PreferredBackBufferWidth = 1000;
graphics.PreferredBackBufferHeight = 1000;
graphics.IsFullScreen = false;
graphics.ApplyChanges();
Window.Title = "RO3";

InitializeTransform();
InitializeTriangleList();

base.Initialize();
}

{
device = graphics.GraphicsDevice;
}

private void InitializeTransform()
{
worldMatrix = Matrix.CreateTranslation(new Vector3(-1.5f, -0.5f, 0.0f));

viewMatrix = Matrix.CreateLookAt(
new Vector3(0.0f, 0.0f, 1.0f),
Vector3.Zero,
Vector3.Up
);

projectionMatrix = Matrix.CreateOrthographicOffCenter(
0,
(float)GraphicsDevice.Viewport.Width,
(float)GraphicsDevice.Viewport.Height,
0,
1.0f, 1000.0f);
}

private void InitializeTriangleList()
{
primitiveList = new VertexPositionColor[points];

for (int x = 0; x < points / 2; x++)
{
for (int y = 0; y < 2; y++)
{
primitiveList[(x * 2) + y] = new VertexPositionColor(new Vector3(x * 100, y * 100, 0), Color.White);
}
}

triangleListIndices = new short[18] { 0, 1, 2, 2, 1, 3, 2, 3, 4, 4, 3, 5, 4, 5, 6, 6, 5, 7 };
}

{
// TODO: Unload any non ContentManager content here
}

protected override void Update(GameTime gameTime)
{
base.Update(gameTime);
}

protected override void Draw(GameTime gameTime)
{
device.Clear(Color.DarkSlateBlue);

foreach (EffectPass pass in basicEffect.CurrentTechnique.Passes)
{
pass.Apply();

}

RasterizerState rs = new RasterizerState();
rs.CullMode = CullMode.None;
device.RasterizerState = rs;

//drawing code goes after this

DrawTriangleList();

base.Draw(gameTime);
}

private void DrawTriangleList()
{
GraphicsDevice.DrawUserIndexedPrimitives<VertexPositionColor>(
PrimitiveType.TriangleList,
primitiveList,
0,   // vertex buffer offset to add to each element of the index buffer
8,   // number of vertices to draw
triangleListIndices,
0,   // first index element to read
6    // number of primitives to draw
);
}
}
}



Edited by Mr. Big, 24 April 2013 - 05:19 AM.

### #6VladR  Members   -  Reputation: 722

Like
1Likes
Like

Posted 24 April 2013 - 09:14 AM

This is where you can find code samples, tutorials and forums on everything XNA-related: http://xbox.create.msdn.com/en-US/education/catalog/

There are lots and lots of samples. Browse through them, open them in VisualStudio and have fun.

As for the Triangle Lists - there are two ways how you can render them

1. Non-Indexed : You need just VertexBuffer (for Vertices)

2. Indexed - you need both VertexBuffer (for vertices) and IndexBuffer (for indices)

Start with the Non-Indexed - basically you just fill the vertexBuffer with all vertices of all triangles. It does not get any simpler than that.

Indexed are faster, because it is only when using the indices that the HW's post-transform cache gets used, but at the very beginning you do not have to mess with that. Get something on screen first, and only then figure out how to make it faster.

VladR    My 3rd person action RPG on GreenLight:    http://steamcommunity.com/sharedfiles/filedetails/?id=92951596

### #7Burnt_Fyr  Members   -  Reputation: 1229

Like
1Likes
Like

Posted 24 April 2013 - 11:50 AM

2) Why strips over lists? While strips make sense as a performance standpoint,

No. They don't. They are actually horribly inefficient in terrain rendering.

Think about it. With strips, you are always reusing last two vertices for current triangle.

With a triangle list of the terrain heightmap, it is possible (I know, because I implemented it) to create a shape that for a 100x100 grid (20,000 tris) executes Vertex Shader only 056*20,000 times - simply because it reuses the vertices that are in post-transform vertex cache and keeps the cache warm with last 24 vertices all the time. The variant with 0.67*20,000 is easier to code, though.

With TriStrip, the best you can get is  1.01 *20,0000

As the OP said, I'm just reiterating what I have been told in the past. Paraphrasing here: "Strips are faster than lists, but in today's hardware, the difference is negligible."

Not to derail the OP's thread, but I was assuming the use of indexed geometry, and after reading your other reply, I thought that may have been the sticking point. As you said, using indexed geometry enables the post transform cache, reusing 2 vertices results in only a single xecution of the vertex shader for each triangle after the first, per row of quads. However upon doing the math, I see 202 shader executions per row of quads by 100 rows = 20200, or as you put it, 1.01 * 20000.

After unfurrowing my brow, I end up with the same count for lists. Could you explain a bit more in depth how lists are faster than strips, specifically how you arrived at the other 2 figures you gave for the naive and optimized list method?

### #8VladR  Members   -  Reputation: 722

Like
0Likes
Like

Posted 25 April 2013 - 08:14 AM

After unfurrowing my brow, I end up with the same count for lists. Could you explain a bit more in depth how lists are faster than strips, specifically how you arrived at the other 2 figures you gave for the naive and optimized list method?

Certainly, the naive - brute-force, if I may -  indexation in lists will not yield anything over the strips. Like, at all.

However, if you take into account the fact that the cards have (at least had, at the time I implemented it), usually, 24 vertices in post-transform vertex cache, you can come up with a "shape", how to traverse the 2D Grid of the heightmap that reuses all of those 24 vertices for multiple triangles.

Remember, at any time, the inner vertices in the heightmap, are common to 4 quads - that is 8 triangles.

I really don't want to give any more spoilers. Actually, I think I gave away too much already, but perhaps you can still enjoy the joy of discovery - just take a piece of paper and start drawing and counting - which ones can be grabbed from cache and which one not - just use colors, or make dots to mark them.

Note, that when I implemented it first time, I got a result of 0.67. Later,also on paper,  I came up with yet-another shape that gives the ratio of 0.57 - I just couldn't be bothered to implement that one (the difference was not worth it for me), but on paper it works just like the 0.67 one did - it's just a more crazy shape.

Now, of course, you may ask - how do I know those exact vertices are fetched from the post-transform cache. Since I was immensely curious, I also implemented a method with a SW queue that emulated the cache to make sure the shape really results in a working (e.g. non-broken) heightmap.

I tested that and the max amount of triangles in scene rose because of this technique. That was pretty exciting to see the HW boundary be pushed.

Back in the day, this was one of the few ways you could actually pull outrageous amounts of triangles on screen, that you simply could not otherwise, if they were all separate vertices and you would have to pay the transform cost for each of them.

It's still a fun excercise today, even if it does not make sense these days (since now you waste all performance not on vertices, but post-processing garbage effects like Bokeh et al...

VladR    My 3rd person action RPG on GreenLight:    http://steamcommunity.com/sharedfiles/filedetails/?id=92951596

### #9zalzane  Members   -  Reputation: 191

Like
0Likes
Like

Posted 25 April 2013 - 09:51 AM

Triangle strips are a major pain in the ass, especially when you're programatically generating geometry. Don't use them.

Depending on how you generate the terrain, it may be faster to just generate it each time the game loads rather than loading it from a file. I have a demo that uses opencl to generate terrain, and it can generate terrain an order of magnitude faster than it would take to load said terrain from disk.

For figuring out which triangle the mouse is mousing over, check this out.

http://xbox.create.msdn.com/en-US/education/catalog/sample/picking_triangle

You can basically copypaste their code for it.

### #10Mr. Big  Members   -  Reputation: 109

Like
0Likes
Like

Posted 25 April 2013 - 11:50 PM

The plan was to draw a 256x256 map, and have a "portal" somewhere on the map that leads to another map. So loading all the maps when the game loads is out of the question.

My plan was to have a text file for each map with a whole bunch of vertices, followed by objects on the map with a position to draw it at.

map1.map, "Home Town";

0,1,0,3,1,0,0,4,3,5,6,2,0,2,3,8,4,2,0,28,169,474,935,742,42,36;

"House.obj", 56,0,56;
"Car.obj", 56,0,80;



I have absolutely no idea how XNA loads objects, but this was my thought on how to do it.

Edit: Oh, and didn't need collision detection as I was just going to define each tile as walkable or not-walkable.

Does this sound like a reasonable, efficient way to draw a map?

Edit2: Actually, since the maps will all be 256x256, there's really no point in storing the x and z vertices in a text file since they will all be quads (tiles). The only thing that needs to be stored is the height of each group of 3 vertices. Which I suppose could be done with a height map image?

Edited by Mr. Big, 26 April 2013 - 12:36 AM.

### #11VladR  Members   -  Reputation: 722

Like
0Likes
Like

Posted 26 April 2013 - 02:33 PM

I would definitely start with using the heightmap image, since it is something you can easily draw yourself, let alone download one of the thousands heightmaps from the internet.

You do not need to store the X,Z coords, but they need to be available during rendering anyway, so it is up to you, if you just calculate them inside the shader, or precompute at startup.

The other way is to have some small base chunk (say, 32x32) have precomputed the X,Z coordinates (and perhaps some UV channel) and just bind it as a separate vertex stream - since lots of stuff will be reuse across multiple terrain chunks (which you will slice the huge heightmap into anyway for the purposes of LOD, frustum, texturing, ...).

VladR    My 3rd person action RPG on GreenLight:    http://steamcommunity.com/sharedfiles/filedetails/?id=92951596

### #12Burnt_Fyr  Members   -  Reputation: 1229

Like
0Likes
Like

Posted 26 April 2013 - 03:53 PM

After unfurrowing my brow, I end up with the same count for lists. Could you explain a bit more in depth how lists are faster than strips, specifically how you arrived at the other 2 figures you gave for the naive and optimized list method?

Certainly, the naive - brute-force, if I may -  indexation in lists will not yield anything over the strips. Like, at all.

However, if you take into account the fact that the cards have (at least had, at the time I implemented it), usually, 24 vertices in post-transform vertex cache, you can come up with a "shape", how to traverse the 2D Grid of the heightmap that reuses all of those 24 vertices for multiple triangles.

Remember, at any time, the inner vertices in the heightmap, are common to 4 quads - that is 8 triangles.

I really don't want to give any more spoilers. Actually, I think I gave away too much already, but perhaps you can still enjoy the joy of discovery - just take a piece of paper and start drawing and counting - which ones can be grabbed from cache and which one not - just use colors, or make dots to mark them.

Note, that when I implemented it first time, I got a result of 0.67. Later,also on paper,  I came up with yet-another shape that gives the ratio of 0.57 - I just couldn't be bothered to implement that one (the difference was not worth it for me), but on paper it works just like the 0.67 one did - it's just a more crazy shape.

Now, of course, you may ask - how do I know those exact vertices are fetched from the post-transform cache. Since I was immensely curious, I also implemented a method with a SW queue that emulated the cache to make sure the shape really results in a working (e.g. non-broken) heightmap.

I tested that and the max amount of triangles in scene rose because of this technique. That was pretty exciting to see the HW boundary be pushed.

Back in the day, this was one of the few ways you could actually pull outrageous amounts of triangles on screen, that you simply could not otherwise, if they were all separate vertices and you would have to pay the transform cost for each of them.

It's still a fun excercise today, even if it does not make sense these days (since now you waste all performance not on vertices, but post-processing garbage effects like Bokeh et al...

I've yet to even begin with post processing effects, as i'm still struggling with my pipeline management(which was still based on 9.0c. In fact, i've yet to even implement HDR(though i'm confident i'll manage).

After posting previously, it had occured to me that perhaps moving to a more equilateral shape, as opposed to a high aspect one, would allow for better reuse of cache, so off to pen and paper i go. Coincedently I had to use the same technique to find out how to procedurally generate a proper list based grid my first time. Now to do it better!

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS