Author Topic: 3D world collision check theory (for writing a 3D car game)  (Read 4398 times)

Offline FutureCow

  • HelpEditor
  • Prof. Inline
  • ******
  • Posts: 680
    • View Profile
I didn't post in the GLBasic forum as it's more a theory question "how would you do this" rather than "here's some code".

After I finish my board game entry, I'm thinking of (maybe) trying a basic 3D car sim of some description.

Having done a bit of thinking about it, the first thing I'm trying to work out is how you turn a track created in a track creator into something you can drive on. In a track creator, you assemble individual meshes so they butt up against each other to make a track. That part I should be able to handle.

What I haven't figured out yet is how to make lots of separate meshes into a driveable track. Lets talk a 2D track at the moment (so we don't have to worry about checking each wheel's height, it's collision on various objects to pick up when the front of the car is going up a hill etc, just assume the "car" is a "Box"). If you do bounding-box to object collisions to see if the car is on the track you'd need a collision check for every different track mesh. In a game loop it would quickly become unplayable once you had more than a few track pieces and were doing lots of collision checks each turn. Besides which, it's not sensible to be checking at the start of a track for a collision between the car (err box) and a track piece near the end of the track.

So the solution I see at this point is that you have to take all the individual track piece meshes and merge them into one big mesh to do a collision check (car/box to big track mesh) on each frame.

If you go that way, you will end up with a huge mesh encompassing your whole track / city etc, so that doesn't seem right either as the size of the mesh would seriously bog your computer down.

So it seems it should be individual meshes, but how then do you do your collision checks without doing 1 per object in the game world every fram? Anyone have brilliant ideas?

Offline Moru

  • Administrator
  • Prof. Inline
  • *******
  • Posts: 1792
    • View Profile
    • Homepage
I'm no good with 3D but what I would do is store the objects with the coordinates in a type-array and go thru it checking the coordinates first before I bother with collision-check. If the player is too far away from the object, there will not be a collision-check. Store the central point for each object and the distance to it you want to begin the check.

Offline Kitty Hello

  • code monkey
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 10760
  • here on my island the sea says 'hello'
    • View Profile
    • http://www.glbasic.com
For a racing game I (personally) would write a function that gives you the x,y,z, direction and width of a track at a given "length of track" function. Then write a function that can reverse that (track length from point x,y,z). With these, you can easily decide if you're out of bounds and such...

Just an Idea. Might be stupid.
Another option might be to use a low poly model for the collision, that you don't show.

Offline bigsofty

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 2702
    • View Profile
Divide and conquer.

Slice the track up into 'sections'(every 30 foot for example), find the centre, of each section, give each section a radius which covers the section.

Give your car a radius, double it to be safe when moving at speed.

Use circle to circle (fast, can be done in one line) to select which section (or sections) are under the car. (Cars are not planes, the chances are they are either on the same one, the next or previous on the list of circles, so only check these)

Use this result to select what sections to examine in more detail. At this stage, use a simplified (not used for onscreen rendering as Gernot suggested) track section polygon to check if wheel(s) off track.

There are other methods, quadtrees for example to partition space etc... but this may be OTT for a simple racer collision but may improve rendering speed via culling selection.
« Last Edit: 2009-Dec-09 by bigsofty »
Cheers,

Ian.

“It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration.”
(E. W. Dijkstra)

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1645
  • Particle Hawk
    • View Profile
I use this to check how high(altitude) above the world object my helicopter is, it points straight down at the world object and returns the distance:

rALT = X_COLLISIONRAY(Objects_Ground1, 0,  x, y, z , 0,-1,0)

Its fast enough, i dont need to worry about performance here.
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

Offline FutureCow

  • HelpEditor
  • Prof. Inline
  • ******
  • Posts: 680
    • View Profile
Thanks for the replies all! It seems a fair bit of testing (and rewriting from scratch!)  is likely to be in order. I might have to find something that talks about how they do FPS's (they seem popular on the internet for people writing games) and maybe take some ideas from that. If they start getting into things like
Quote
quadtrees to partition space
I'm going to be seriously out of my depth though  :giveup:

Offline FutureCow

  • HelpEditor
  • Prof. Inline
  • ******
  • Posts: 680
    • View Profile
Ow my sore head! It was a mistake to go looking at pages on how Quake/Doom were implemented...  :help:

Offline bigsofty

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 2702
    • View Profile
Ooh, I feel I put you off! :(

My advice, give it a go, forget about 3D, get a 2D game up and running (ala Supersprint), take on the 3D aspect later, optimisation later...  :S
Cheers,

Ian.

“It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration.”
(E. W. Dijkstra)

Offline Kitty Hello

  • code monkey
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 10760
  • here on my island the sea says 'hello'
    • View Profile
    • http://www.glbasic.com
Supersprint FTW! :whip:

Offline FutureCow

  • HelpEditor
  • Prof. Inline
  • ******
  • Posts: 680
    • View Profile
No, you didn't put me off, it's all those really smart $*%$&'s who know a lot about 3D who did that!  :D

 I'm not making any promises as something else may take my fancy in the meantime, but I would like to have a go at just getting the basics working - a 3D car moving over a terrain with gravity. I'd be over the moon to get a "simple" version of a Stunt Car Racer (the 1989 game) track working. But hey, I'm only just learning this 3D stuff and trying to do physics as well?! Is anyone seeing me biting off more than I can chew? *laugh*

Or possibly Supersprint....

I'll worry about it post board game completion.
« Last Edit: 2009-Dec-11 by FutureCow »

Hatonastick

  • Guest
How about a remake of Interstate 76? :)