Hi, I'm planning to realize to game GTA style where the player can visit a huge map. My question are: 1) Which method shall I use to build such map ? BSP trees ? Portals ? 2) Which collision methos is best for such a huge map ? Thank you,

There isn't a single way to do this. I'd recommend reading up on Dungeon Siege:

http://www.drizzle.com/~scottb/gdc/

Personally, I'd try something like BSPs for what Dungeon Siege calls nodes and portals for what Dungeon Siege calls doors (they just link nodes).

Reading about Dungeon Siege should give you an idea of the problems you could discover.

Collision methods depend on what you want (Dungeon Siege does a 2D projection apparently). There are plenty of ways to collide with BSP quickly.

Whew, that's quite a project you're going to take on!

The first thing you should note. GTA does not keep all of the map in memory at once. It streams (read: loads from disk) the sections that it needs and discards the sections that it doesn't need. All in realtime.

So, if you're going to do something similar any data structures that you design will need to be designed around this kind of system.

For example, if you're going to stream a world that is BSP'd, you need some way of making sure your BSP tree will remain useful when large chunks of it get streamed out. For this reason, it's probably not a good idea to use a single BSP tree for the entire world.

The main thing to notice is that this is a moderately complex system to get working properly. It has many components
* streaming system
* LOD system
* collision system.
* rendering pipelines
* occlusion
And that isn't even including things like game-object management and world-immersion (adding things like newspapers blowing around, animation, day-night transitions etc...)

For each of these systems, you need to consider how the components will interlink (try and minimise coupling if you want components to be easily dropped and replaced)

I am not going to talk about all these issues, I'm just going to give you a hint..

I assume the way they do it in GTA is that they break their world up into manageable segments (probably just cube-like segments). Each segment knows which other segments are the neighbours of that segment. Each segment will also have several LOD levels associated with it, a BSP tree for collision.
Then each of the segments can be managed within an octree type structure for rendering and collision.

The streaming issue can be solved by writing another thread that
processes a loading queue and pulls in segments whenever they are requested. As for determining which segments to load, there are several techniques. The neighbours of the segment that the player is currently in should always be in memory. Maybe this will give you some hints as about how to go about doing this...

Hope that helps

Quote:Original post by FReY
For example, if you're going to stream a world that is BSP'd, you need some way of making sure your BSP tree will remain useful when large chunks of it get streamed out.

So shall I use BSP tree ? And for collisions ? Bounding box, bound sphere ? Or what else ?

Thank you, you have been many exaustive !

IIRC, GTA used a map made of tiles. That's not a really huge load on the memory (although keeping track of everything on the map can be hard on the CPU) when compared to textures for instance.

Besides, tilemaps make for easy frustum culling.

Quote:Original post by sit
[a rectangular prism building occluder....] if necessary.

Mmm, it sounds interesting. Could you give more hints ? Thank you.

Quote:
I'd suggest you don't use a bsp tree

I agree completely. Managing a dynamically updating BSP tree would be a nightmare. Don't use a *single* BSP tree.

The BSP however is still very useful for collisions on a single world segment (what ToohrVyk called a tile), so I'd suggest creating a BSP for each world-segment.

Quote:
So shall I use BSP tree ? And for collisions ? Bounding box, bound sphere ? Or what else ?

Use vertex-arrays for rendering. You can put the geometry for a single segment into a vertex-array. In fact, you will have a vertex-array for each LOD in each world-segment.

Don't bother using BSP's for rendering - most hardware has a zbuffer. You should however, use a BSP for collision on that world-segment.

So, to summarize, each world segment (or tile) has the following characteristics
* bsp tree for collision
* vertex array for each LOD level (terrain)
* a list of objects within the segment(eg. buildings, fences, street lights etc...)
* a list of neighbouring segments.
* a world-space bounding box (for testing whether the player is in the segment or not)

The general streaming algorithm is this:

initialization:
1.) put the player in a starting world segment.

in your update loop somewhere (updates streaming state)
2.) check which segment the player is in.
3.) if the current segment's neighbours are not loaded (or not in the loading queue), add them to the loading queue.
4.) check all the currently loaded segments. If a loaded segment is not a neighbour of the current one, destroy it.

Of course, for rendering there are many techniques you can use. If a segment is loaded, it can potentially be rendered.

The simplest method of culling is to simply check if the segment bounding box is touching the camera view-frustum. If not, don't render it. If yes, render it.

Additionally, if the segment has passed the frustum check, you can select it's LOD level based on the distance from the camera.

Also, you can easily add simple occlusion checks on the objects in your segment. For example, you can extrude a volume from one of your objects (eg. a building) away from the camera. If any segment object (eg. street light) falls completely inside the volume, it is occluded and should therefore not be rendered. There are other methods (eg. Zhang's Hierarchical occlusion maps) of course, but this is probably the easiest to implement, but far less effective than other methods that take into account fusing of occluders.

Care needs to be taken though that your occlusion algorithm will not just take more time than brute-force rendering all your objects. If you are CPU bound, an occlusion algorithm will make performance worse.

For collision, you would simply figure out which segment the object you want to collide is within, and perform a walk of the BSP tree for that object. You could use any kind of geometry for walking the tree: sphere, box, swept-sphere, point. Whatever, if you design things general enough you can use many techniques.

Sorry, I can only describe things in very general terms here. I hope you get the idea...:D

EDIT: I apologize if I've taken this off topic for the forum. I didn't actually realize this was in the 'Maths/Physics' forum when I replied!

Thank you all guys for your replies. I apologize for posting in the wrong forum, I thought that talking about collision Math / Physyic was suitable ! Sorry.