• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

Archived

This topic is now archived and is closed to further replies.

Zeus_

A 3D environment; BSP trees?

6 posts in this topic

Im sitting here programming every wall in my 3d environment manually; its annoying. How can I "load" a level from a file? Or better yet, what the hell is a BSP tree? Im really concerned with collision detection too if you have any tutorials. thanks!
0

Share this post


Link to post
Share on other sites
1. To load levels or models from a 3d mesh try using this...
http://lib3ds.sourceforge.net/
It can load .3ds files which can be made in 3D Studio Max including textures....

2. For BSP trees.. try doing a search on them or try Botmans Half-Life Map viewer which supports Half-Life map .bsp trees in OpenGL...( you can get the source for it too)
http://www.planethalflife.com/botman/bsp_tool.shtml

3. For collision detection i recommed...
ColDet - 3D Collision Detection Library
http://photoneffect.com/coldet/
Which by the way *seemlessly* intergrates with OpenGL... there are even some examples of modified NeHe source that work with it.
0

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
1. To load levels or models from a 3d mesh try using this...
http://lib3ds.sourceforge.net/

2. For BSP trees.. try doing a search on them or try Botmans Half-Life Map viewer which supports Half-Life map .bsp trees in OpenGL...( you can get the source for it too)
http://www.planethalflife.com/botman/bsp_tool.shtml

3. For collision detection i recommed...
ColDet - 3D Collision Detection Library
http://photoneffect.com/coldet/
Which by the way *seemlessly* intergrates with OpenGL..



ouh fuck above 2) for BS-trees try to find some map-viewer sources supports that OpenGL and that ... i can''t stand... errr, maybe you should before that read some information about BS-trees, lol. That''s very funny, IT''S not NEVER right way to take others SRC and use it, RIGHT WAY is learn stuffs and implement them fully on your *OWN*.

and 3) ouh fuck... PLEASE, learn little bit 3d-programming and you can implement cd your own, common way is that simple: concanate camera system +SPHERE(for your camera) - TRIANGLE intersection algorithm +calc pushback vector if intersection is happened.

sorry, but i can''t stand above anonymous sender. maybe he tried to help you, but definitely wrong way.
0

Share this post


Link to post
Share on other sites
I have to agree with rickpeek. I understand that the Anonymous Poster was just trying to help, but what he was recommending is certainly not the way to go about making anything decent.

First, let me clarify some things. There are *.bsp format files, which contain the maps for games based on the Quake I, II, and III engines. A BSP tree is not a file format. Although *.bsp files contain a BSP tree, they also contain additional information.

What IS a BSP tree then? Think of it this way. You have a world. Find a face (wall, ceiling, etc) in it, and divide the world in half along that plane. Now you have two areas. Find a face in each of these, dividing them. Now you have 4. Continue splitting the world into sections by its faces until each section has no more faces that can be split against. As you can see, there is one master "parent" in this tree, and that is the whole world. It has two "children," which are the areas on either side of the first splitting plane. Each of these two areas (which are called "nodes" in the tree) in turn has children, and so on. Now picture these relationships expressed in a family tree. That is a BSP tree.

Now what the heck is a BSP tree useful for? It''s a way of sorting your level front-to-back. Its based on the principle that nothing on the far side of a plane can be in front of anything on the near side of the plane. That''s a pretty common-sense idea! But as you split the world into smaller and smaller sections, eventually you can draw the entire world back-to-front perfectly. This, however, isn''t what they''re used for nowadays. Now, if anything, they''re used to draw the world front-to-back. The reason for this is that, since the graphics card checks to see if the pixel its about to draw is behind the oneon the screen before drawing it, you can avoid drawing a great many pixels that way, instead of drawing pixels on top of pixels on top of pixels.

Even this isn''t the primary purpose of a BSP tree nowadays though. Now, what is done is this: For each leaf node, it is calculated what other leaf nodes can be seen from it, and this information is stored in a file (like the *.bsp files I mentioned earlier). Then, as you run through a map, only the areas that are potentially visible from where you are are even considered. If a map has two rooms connected by twisting hallways, then, if you''re in one room, the other room won''t be drawn. This is called occlusion culling. In this case, it is precalculated.

There''s a good article on BSP trees here: http://www-2.cs.cmu.edu/afs/andrew/scs/cs/15-463/pub/www/notes/bsp_tutorial.pdf

If you want to be able to walk through large levels with any efficiency, then you''ll need to have some kind of data structure for sorting your world geometry. If not a BSP tree, then an octree, or even a uniform grid. (Or for terrains, a quadtree)


Now, about collision-detection. First, you need to realize something. All OpenGL does is draw stuff. The end. If, by "programming every wall in your 3d environment manually" you mean writing lots of glVertex3f(...) commands, then there''s no practical way for you to do collision detection. All OpenGL does is draw stuff!! What you need is a data structure of some sort - it can be something as simple as an array of triangles - that you draw using OpenGL. If you have such a data structure, then you can do collision detection. The better your structure, the faster it will be.

There''s a really simple method of storing a world that dates back to the days of Wolfenstein. Store it as a 2d array of blocks. There are two kinds of blocks, solid and empty. Empty blocks are rendered just as a ceiling and floor; solid blocks also have walls. Your level is stored in a grid. I''m sure you can figure out collision detection with this system!! You can even do simple occlusion culling very easily with such a system. On top of all that, you can make maps in an image editor, jut using black and white pixels to represent blocks and emty space.

A more vesataile system, which is in some ways more complicated and in some ways simpler, is just to have, as I mentioned before, an array of triangles, something like this:
  
struct vertex
{
float x, y, z;
};
struct triangle
{
vertex verts[3];
};
triangle * map = new triangle[NUMBER_OF_TRIS_IN_MAP];


How do you do collision detection with this second technique? You need to iterate through each triangle, and test to see if the sphere representing your camera and it intersect. The simplest way to do that is to find the intersection of that sphere and the plane containing that triangle, and then checking to see if that intersection point is within the three verteces.

Both methods are simple. The first is too constraining to really look good, but is efficient. The second is too inefficient to run well, but can hold any geometry. If you were doing anything serious, you would have to use a better system, like a BSP tree or octree.

I hope that helps.
0

Share this post


Link to post
Share on other sites
Thank you for your help so far.

That first example from above is much like the world that I was creating; ALSO inspired by Wolfenstein. I had a 2D array, and a function that would scan the array for a 1 and draw a block. (it was composed of 0's and 1's)

ANYWAY! Enough off topic crap from me. =) I understand what BSP trees are, and now they make for sense. No wonder my game would lag so much; It was drawing so much!

Now what else was there; Ah yes. I have concluded by many tutorials that collision detection is best used with object collision detection. Like, erecting a sphere around my camera, then checking if it collides with something, right?

Well, with blocks, it sounds like it would be fairly easy. But what about something else? Can you give an example? By something else, I am referring to, well, anything.

The basics steps, as described in a tutorial on the opengl.org site, are the following:

1. Record the coordinates of the camera
2. record the coordinates of the object
3. if(camera_coords=object_coords) then stop movement

Yes? no? It sounds right, I guess...

But I just don't get how I would detect smacking into something. There is one height for my camera, so would I just run through an array of data and say that if ever the camera coords are equal to any coords in the big array of wall positions, then stop?

Oy vey, maybe I should get some coffee...

Thanks again to all who are posting to help my poor little mind, especially TerranFury.


Edited by - zeus_ on November 25, 2001 1:33:57 PM
0

Share this post


Link to post
Share on other sites
Oh also; You mentioned a method that allows OpenGL to only draw what you see (in a sense)... Is there an order of functions that enable that? Or is that one of those long and difficult things that I should read a tutorial to learn about?

Thanks again!
0

Share this post


Link to post
Share on other sites
uhm, well, i was wundering about that too and I havent found any good examples. so if anyone could show me. that would be nice. thanks
0

Share this post


Link to post
Share on other sites