3d Game Map

[/\/\isanThr0p]

Well I have read many people have done 3d games here.
I am wondering what you guys use for your map files?
do you use X files? Or just a vertex buffer saved to a txt file? Or do you use something like tilemaps?

Has anyone ever used X files for this and it was efficient?

[Zaei]

Do you mean terrain, or say, a level (as in halflife/quake/UT, etc)?

For terrains, most people use a heightmap, which is a greyscale bitmap. The height is represented by the value of the red(or blue, or green) value of each pixel. Those values are then processed into vertices on a regular rectangular gird. Some people will simply render out this data, With a method called "Brute Force Terrain Rendering", while most people have been experimenting with various Level of Detail algorithms so that terrain close to the camera is very high in detail, and terrain that is far away is less detailed.

For levels, you generally have a set of geometry, walls, floors, etc, which are loaded in, and processed into some sort of partitioning sceme (Binary Trees, Oct Trees, Portals, etc), which can then be rendered as fast as possible.

Z.

[/\/\isanThr0p]

Alright I hoped you'd answer Zaei
well a hight map does not work for me.
Basically I want Rooms to walk around. For this I made some simple tileengine kind of thing. I don't want to use this though, I believe it was a really bad/beginners idea...
Iwould like to be able to add some stairs and stuff like that.
The second thing you mentioned is more interesting...
what is the speciality of an oct tree? (I might know it under a different name)nd what are portals (I do not know those structures I believe)

I will post further information soon, I don't have the time right now.

Thanks for answering

[Zaei]

Ok, for actual levels in 3D, most people out there are going to be using oct trees. You asked what those are, so here ya go. First, lets start in 2D, with quad trees. A quad tree is quite simple. Imagine a square. Now, split that square into 4 smaller squares. Split those into 4 squares each. The original square is the root node. The first subdivision are the child nodes of the root node. The second subdivision are children of the first subdivision. So, you end up with a class like this:

Public Child1 As Node
Public Child2 As Node
Public Child3 As Node
Public Child4 As Node

So each node has 4 children (the four smaller squares). Get it? Quad trees are quite usful for partitioning objects in 2d space. You simply find the node that covers the smallest area that is visible, and render all of the objects in the space.

Now, Oct trees are quad trees, except in 3d space. Instead of squares, you have cubes, and each node has EIGHT children. For rendering, you simply traverse the tree, until you either find that the node is not onscreen, or you find a leaf node. If you find a leaf, you render the contents of that leaf.

Portals are another method of space partitioning, that are especially good for rooms. Imagine 3 rooms that are connected in an L shape, so that the only way from the end rooms is through the middle room. Each doorway is a portal. The idea is that it is only possible to see the current sector, as well as any secotrs that are connected to the current sector by portals.

That is pretty much a basic crash course. You should be able to easily find some more info on www.gamedev.net , www.flipcode.com , and of course, google.

Z.

[/\/\isanThr0p]

alright thanks a lot!!
I understand the tree thing, but I really have to think about how to make a map from this...

well the portal thing I thought about before... this is very useful in order to find out what to render (without to much math ) and what to keep in memory (if I am really going to do this, it is going to be really simple, no action taking place in rooms that I am not in right now so I don't have to keep those rooms in memory)

but what I was really aiming at was how to store a level in a file and how to do collision detection on it later on...
what I did before was, on program with a hightmap (where you could walk everywhere) and a tilemap kind of thing which was a fun idea, but wasn't flexible at all and did not allow anything but wall or floor

well I will take a look at those pages...
I am having my wisdomtooth taken out tomorrow so I will have some time on my hands...

[/\/\isanThr0p]

by the way...
I know you do your stuff in C..
I finally feel ready for learning C(++) since I had to learn some (limited) java... now when I read through C code I understand it much better, but I still don't know how to start...
any advice.. is there any tutorial kind of thing that takes me right to game programming?? (something like david Brebners Page for C `???)

[Zaei]

When working with levels and such, you end up having to do collision detection against all of the geometry in your level. This is the second bonus of using a space partitioning system, as it reduces the amount of geometry that you have to check against drastically.

Yes, I do most all of my code in C++, but I dont know of any resource that can take you from total newbie to game programmer. Most books will give you a rough go over of C++, just enough to get you started, but I wouldnt recommend that. I WOULD recommed learning the language from the ground up, so that you KNOW how to use it, including classes, pointers, memory managment, etc. Once you've got all of that down, then you can start thinking about game programming. Ask around in the C/C++ forum for some pointers.

Z.

[/\/\isanThr0p]

Well that's kind of what I expected. Of course it makes sense to start all from the beginning and get a good base at something.
I just hoped there would be a way to skip over some of those steps, since in university I learned Java (classes, value-semantic (pointers(which they say they don't have any in Java )/values/overloading/polymorphism), some assembler and with assembler memory management of course.

[edit]
What C compiler do you use or recommend? I guess most people use MS V C++... Is there any reason why I shouldn't use this one? And when I program with VC will another C compiler be able to compile it too?
[/edit]

Well I will have a look right after my operation.

Thanks

[plenderj]

Something that may be of intrest to you.
The "Delta Force" games by Novalogic use a Voxel approach for terrain generation, and then put properly rendered buildings on top of those terrains.

[/\/\isanThr0p]

yeah I saw that... I really don't feel like doing something like this though... I want to do rooms...
(can't write more just had the operation...)

[plenderj]

Well Novalogic can put large complicated buildings on top of the terrain.
Only problem is lining up the structure on top of the ground, because you tend to get gaps under the floor of the object if you're not careful

[Zaei]

Well, with C++, you really have to do a lot more manual memory management (when you create an object, you have to remember to delete it), and pointers are probably going to be a bit different, as well as some syntax, and such.

I use MSVC. Most people will agree that it is the best Windows compiler availible.

The Microsoft compiler has some interesting quirks that are not standard, but if you are careful to avoid them, you can write standard code that will compile on most compilers.

Z.

[/\/\isanThr0p]

thanks
I know C is gonna be much harder, but I think I still should learn it since it will be of great value for me.

What do you think about the Dot Net? Today I went to a bookstore, but there I got doubts wether I should get a book about VC++ or C++.Net...
is VC++ going to be supported in the future or is everything on windows just going to be Dot Net??

[Zaei]

Buy a book on C++, not VC++. A VC++ book will NOT teach you C++ programming, but will teach you about MFC, and the other various technologies that MS has.

From what I have heard, the .NET C++ compiler is even better then the MSVC6 compiler.

Z.

[/\/\isanThr0p]

well that's interesting...

About the C++ instead of VC++: I was told Windowsprogramming was incredibly hard without Mfc... especially if I want to do OOP...

this is really getting cofusing ...

Hm well I will look into getting a C++ book then... A friend just borrowed me a VC++ 5.0 book... since it's free, I will definetly have a look at this book too though, (on page 100 only 700 more to go )

[/\/\isanThr0p]

well about my initial question:

The portal thing seems to be just right for me, since my 'game' will only use rooms, most likely...
so you said earlier I will have to run collision detection against all my geometry.. so basically I could just use an X file now and try for collision with every single triangle in my X file?
I think this is gonna be hard, especially figuring out how to react to collision (walking stairs or bouncing of for example). I guess it would be much easier if I would just keep everything to one level, but that's to easy then...

[Zaei]

The idea of using some partitioning algorithm is to reduce the amount of collision detection you have to do. When using portals, you would only calculate collisions with the geometry in the current sector, for instance.

Whoever told you that Windows programming without MFC is hard has it backwards. Its very hard to program in MFC if you dont know how to program Windows without it.

Z.

[/\/\isanThr0p]

Alright I will tell him this...

The next problem will be how to react to the collision... should this be saved to a file too or all be calculated in game?

let's say I collide with a small box, will I stand on it or will I just be stuck before it... this is gonna take a long time coding I think... well I guess I should use a bounding box for my actor to simplify it..

[Zaei]

Most commercial engines use several collision detection routines. First, Sphere-Triangle collisions are tested for for all relevent geometry. If a collision is detected, a bounding box-triangle collision detection routine is run on the relevent geometry(the triangle instersected by the sphere). If a collision is again detected, there are lots of variations here. If, say, the game was a first person shooter, each model bone would have a bounding box or cylinder, which would all be tseted against the intersected triangle. After that step, if more detail is needed, a full triangle-triangle intersection would occur between any geometry attached to the bone, and the level geometry. To simplify:

|Sphere-Triangle
|--BB-Triangle
   |--Skeleton-Triangle
      |--Triangle-Triangle

It is easiest to start with the simple sphere-triangle detection, and implement the others later.

All of the collisions are computer on the fly, since your level file would be huge if you tried to pre-calculate it.

As to what would happen when you collide with something... that is up to you to decide.

Z.

[/\/\isanThr0p]

alright thanks
I will look into that..
it seems to me that that will all be a pain...
But I had the vision of walking around in some buildings that actually exist... (they would only remind roughly from shape not all detailed and textured of course) So I really need to add stairs... with a flat ground it would be all so much easier...

[Zaei]

Simple enough. That is collision detection response. When you find a collision, figure out what object you have collided with, and if it is smaller then say 0.2 units, then you move on top of it. Thus, if every step in your stair is smaller then 0.2 units, you will walk up them.

For rooms and such, I think that you would be best off with bounding box collision. Anything deeper at this point would be rediculous.

Z.