Re: Question about development of prototyping tools.

Hehe...I actually worked on that specific code and it was a bit of a pain to
get right. Here is what I ended up doing:

In general, the Banjo Kazooie collosion was done like this:

The whole map was divided into equal sized 3D cubes with each cube pointing
to a list of indices. The indices indexed into the map array of vertices
(the 3D triangles). Overlapping triangles (triangles in more than one cube)
would be stored in each cube it overlapped. This indirection was done to
save memory.

You could of course have used a KD tree or something else but the cube way
of doing it was fast and simple to implement. And triangles were duplicated
if overlapping more than one cube because cutting map triangles is a very
bad idea (you can easily end up with super thin triangles that the float
math precision won't work well with and it uses a lot more memory).

The N64 only had 4MB total so we used the cartridge as "virtual memory"
swapping models in as needed and dropping models no longer visible. In Banjo
Kazooie literally all graphics behind the camera is no longer in memory and
as you turn around it is swapped in again from the cartridge and graphics
that is now behind you is dropped. You wouldn't be able to do that with a
DVD drive but the N64 cartridge was very fast :)

Anyway...on top of the map structure I added simple collision code for lines
and spheres:

Lines: You could take a line (from,to) hand it to the collision code, and it
would return zero or more collision points ordered in from->to sequence.
With each collision it would also return the TYPE of triangle the ray was
hitting (ground, water etc.) This was stored as a simple array of bytes with
one byte per triangle (a bit indicating water for example). This information
was used to switch the main character from running to swimming or running to
falling for example. Using the map cubes for fast indexing made this run
very fast. Usually only a few triangles needed detailed testing per frame.

Spheres: With a sphere, the collosion code would return a vector pointing in
the direction you want to move to get away from hitting triangles. So the
system easily handled spheres penetrating triangles. Instead of trying to
find the accurate collision point it simply needed to "push" you away from
the collision. Doing it this way removed a number of complicated corner
cases and it worked great with low precision float math.

The character vs. map collision was done using a line test for the feet and
a few spheres roughly covering the body. We just experimented with a
different number of spheres and sphere pos/sizes until it worked. I think we
ended up using just 2 sphere for the main character so collision was super
fast.

Character vs. character collision was done using spheres. We simply attached
a number of spheres to the character animation skeletons and update the
sphere positions each animation frame. With a single fixed size bounding
sphere as a quick initial test.

Character vs. large characters collisions (the whale for example) was done
in the same way as the map: A 3D cube surrounding the character subdivided
into 3D cells, with each cell holding a group of triangles to be tested. The
skeleton animation would then directly update each vertex and the cube
indexing was used to minimize the number of vertices tested.

This worked well for the whole game EXCEPT for the tail of the whale. The
problem was that the tail was moving far enough that some of the triangles
would move outside of the 3D cubes => sometimes triangles underneath the
main character wouldn't be tested => character falling "inside" the whale
tail. That I fixed by simply making the cubes bigger (or just having one big
cube for the whale? I can't remember).

The next problem was that the main character didn't move with the moving
tail. That was solved by remembering the index of the triangle it was
standing on and its (du,dv) in triangle coordinates. In other words, if the
character lands on the whale, du := dot(triangle_edge_0to1, char.pos -
triangle_vertex[0]) and dv := dot(triangle_edge_0to2, char.pos -
triangle_vertex[0]) was calculated and stored. And in the next frame, before
the character movement update, the character position would be set relative
to the (now animated and moved) triangle with character.pos.x =
triangle_vertex[0] + du * triangle_edge_0to1 + dv * triangle_edge_0to2.

So yeah nothing complicated.

We did it this way because in practice to make a game fast you really need
to handle each case separately instead of trying to do "one mother of all
collision algorithms". It makes the code simpler and faster. So main
character vs. map was handled differently from main character vs. other
characters and vs. large characters. And only the whale (I think?) used the
(du,dv) solution so the rest of the game didn't pay the cost of that math.
It was only triggered and used by the whale object. The whale directly set
the position of the main character when the main character was on top of it.
Purists will probably feel ill reading this but hey it worked well ;)

Heh...one think I remember: the lens flare is a post-process (simply a
number of 2D triangles rendered on top of the 3D view). In order to switch
the lens flare on and off depending on whether the sun was visible, I used a
line test form the camera to a point outside the map in the direction of the
sun. However it was too slow because it could easily visit a large number of
3D cubes to test for collision. The solution was to test part of the line
every frame. So over (10 frames? I can't remember exactly how many) it would
test part of the line between the camera and the sun to find out if the lens
flare should be visible. We just played around with the number of "ticks"
per full test until we got the best balance between performance and
visibility.

Morten

-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of Juan
Linietsky
Sent: Saturday, 23 April 2011 2:22 PM
To: [email protected]
Subject: Re: [Sweng-Gamedev] Question about development of prototyping
tools.


I'm sorry that this is sightly offtopic, but given that banjo kazooie was
one of the games that inspired me the most to be a game programmer when I
was young, I hope you don't mind if I ask a simple question.. (Of course if
you can answer it)

How is collision detection done in bk? I noticed there is a stage whith a
giant whale floating in a sewer. The whale is fully animated, wiggles its
tail and banjo can still walk over it and moves with the whale. Can it be
that in games from that time, when a character was over a floor it would
disable phisics and just move over the manifold as long as the surface
normal allowed?

I am really amazed, since recently I implemented that kind of interaction on
a physics engine for skinned geometry, obtaining back linear and angular
velocity.. And was thinking "how did they do this  on a n64...". I'm sure
there's so many neat tricks like that that will be lost to time given how
greater processing power allows more and more general purpose algorithms..


-----Original Message-----
From: "Morten Brodersen" <[email protected]>
Sender: [email protected]: Thu, 21 Apr 2011
15:16:59 
To: <[email protected]>
Reply-To: [email protected]
Subject: Re: [Sweng-Gamedev] Question about development of prototyping
tools.

_______________________________________________
Sweng-Gamedev mailing list [email protected]
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

_______________________________________________
Sweng-Gamedev mailing list [email protected]
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

_______________________________________________
Sweng-Gamedev mailing list
[email protected]
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com