Platformer systemic edge grabing

Hello everybody!

I have recently learn to use BLITZ3D and it's amazing how efficient and fast it is to make 3D game with, it's even easier than making 2D game as it handle anything fundamental like animation, camera and collision with breeze!

That's how i have start to code a 3D plateformer in the like of Mario 64. So far so good, after 2 weeks of work i have even done more thant previously plan without prior knowledge in 3D game making.

Now i start to increase my ambition, from a "showcase" prototype i want to do a fully playable game but still educational for me. My goal is to implement nearly all the mario move in the game. The game woud be a pure and simple platformer, only platforms, the character and collectible.

But the things i didn't expect is that i have no idea how to do "grab edge" efficiently in 3D. I mean without tagging the level prior to the play, i want it systemic so the player can thrust his ability and not read the designer's thought.

Anyone have an idea, did this idea was discuss before in another topic?

Summary
What i want to do is "viable edge detection for grabbing onto an arbitrary mesh in runtime" :) of course the viability of edge is decide by parameter to tweak.
Remember i want to "snap" the correct edge

Well, theoretically, you would be checking for a flat or fairly flat (i.e. almost or exactly aligned to a plane of 0 Y/X or Y/Z inclination, with one of its vertices facing the player or almost facing the player (i.e the Normal tangent to the vertex would be pointing almost or exactly at the player)

The limits of what's too 'steep' an inclination, or too obtuse/acute the normal tangent are up to you of course, but it's gonna generally be the trig in finding these out which will form the basis of 'checking for edge-viability'

Well, that's a tough one tbh, as i'd imagine most edges for grabbing would be set up in an editor of some sort. It realy depends on your geometry for your level. Is it all square edges?

You know, I can't find ANY material about that matter. It seems it's like a....secret....
I guess you could save the indexes of every pair of vertices that form a grabable edge (the level mesh would have to be whole, not made of smaller bits). Then you'd check the perpendicular distance between a pivot close to the characters neck or head and the coordinates of the line\edge formed by those two vertices, and see if that distance is such that, if the character is in the air, not touching the ground, then, if he is lower or higher than a certain value he won't grab the edge. Only if he's around a certain value would he grab the edge. That value, being customizable even real-time for debugging, would kinda be your viability or at least some sort of controlling edge-grabbing more artistically.

One thing I tremendously suggest is that you play games where you can hold on edges (I particularly like to point out Rayman 2: The great Escape and Castlevania, both for the Nintendo 64, and of course, both where you can grab onto edges very nicely). That way you can study it better and come up with ways to improve my suggestion or at least be technically secure enough to implement it.

EDIT: Something like this

You'd save all the grabable pair of vertices through their index, and have a function that checks the character's position and perp. distance every frame. Also, a suggestion of distance to use would be the model's arm reach. Also, a good position for that pivot I mentioned, the one you'd be checking the perp. distance, would be right in the middle of the shoulders, just where the neck ends and the chest starts.
Problems that might come up:
1º) When the edges are very small, the characters arms may fly in the air.
2º) When there's more than one grabable edge at the same viable distance and height from the character, he might "flicker" in position as your algorithm thinks "this edge is ok to hold, but this one is too".

I think that might be the way forward there kryzon. Again, you'd need to do this in an editor though. I really don't see any practical way of doing this any other way.

I could be wrong but I suspect that most games that allow edge grabbing have the edges defined in the editor/level data somehow, and don't calculate it dynamically at runtime. This would seem to be an easier approach to me, unless you have a pretty complex dynamic/destructible level.

Once you've designed your level, it would be pretty quick/simple to define the edges by placing quads (or possibly elongated cubes) where the edges are, in a separate mesh, for example.

Thank you, Ross C. Yeah an editor would definately be the way to go, because in softwares like 3DS Max you can just select a vertex and it will tell it's "number" (which would be the index inside Blitz3D, IMO).

my suggestion is...simply create trigger and check is there collision with it or not(hand bones)..its working like a charm in my game what has motion like Lara Croft..

In most editors you can change a vertex's colour and read that back in blitz. Maybe colour all verts that can be hung from as red?

Best thing to do is look up how they did it in assasins creed. I think they did it in the editor by hainvg hidden pivot points (nulls) that were used as grabs, not the actual visual model.

Nice idea boomboom.

This is settings im using and its really working incredible and very accurate..practically same as Tomb raider doing..set up trigger box on the edge i want to be 'grabable' and thats it..just check for intersection..soon as its happen proceed with climb or whatever should be appropriate..


and this code should be a good start

; Sphere-Box Intersection Routine

; Blitz version by si@..., based on code found at http://www.acm.org/tog/GraphicsGems/gems/BoxSphere.c
; See also http://www.realtimerendering.com/int/ and http://www.magic-software.com/Intersection.html for some more
; (non-Blitz flavoured) intersection routines

; This routine is a fast, accurate way of testing to see whether a solid sphere intersects a solid axis-aligned box.
; Useful to act as an activation zone in games - i.e. if sphere is in invisible zone then activate event.

; Use mouse to rotate camera, left and right mouse buttons to move camera forward/backward
; Move sphere by using cursor keys and r/f for rise/fall
; When the sphere touches the box, a 'collision' message should appear in the top-left hand corner of the screen

; Initialise
width=640
height=480

Graphics3D width,height,0,2
SetBuffer BackBuffer()

MoveMouse width/2,height/2

cam=CreateCamera()
PositionEntity cam,0,100,-100
RotateEntity cam,30,0,0

light=CreateLight()

; Set dimensions for box/sphere, then create them using these dimensions
bx#=0 ; box x
by#=0 ; box y
bz#=0 ; box z
bw#=50 ; box width
bh#=50 ; box height
bd#=50 ; box depth
sx#=0 ; sphere x
sy#=0 ; sphere y
sz#=0 ; sphere z
sr#=15 ; sphere radius

box=CreateCube()
EntityColor box,255,255,0
FitMesh box,0,0,0,bw,bd,bh
PositionEntity box,bx,by,bz

sphere=CreateSphere()
EntityColor sphere,255,0,0
ScaleEntity sphere,sr,sr,sr

PositionEntity sphere,sx#,sy#,sz#

While Not KeyDown(1)

; Move camera
mxs=mxs+MouseXSpeed()
mys=mys+MouseYSpeed()

RotateEntity cam,mys,-mxs,0
MoveEntity cam,0,0,MouseDown(1)-MouseDown(2)

; Move sphere
If KeyDown(203) Then sx#=sx#-1
If KeyDown(205) Then sx#=sx#+1
If KeyDown(19) Then sy#=sy#+1
If KeyDown(33) Then sy#=sy#-1
If KeyDown(200) Then sz#=sz#+1
If KeyDown(208) Then sz#=sz#-1

sx#=sx#+mx#
sy#=sy#+my#
sz#=sz#+mz#

PositionEntity sphere,sx#,sy#,sz#

RenderWorld

; Test to see if sphere intersects box
If SphereBoxIntersection(sx#,sy#,sz#,sr#,bx#,by#,bz#,bw#,bh#,bd#)=True Then Text 0,0,"Collision"

Flip

Wend


Function SphereBoxIntersection(sx#,sy#,sz#,sr#,bx#,by#,bz#,bw#,bh#,bd#)

; sx#,sy#,sz# = sphere x,y,z centre co-ordinates
; sr# = sphere radius
; bx#,by#,bz# = box x,y,z corner co-ordinates
; bw#,bh#,bd# = box width,height,depth

Local dmin#=0
Local sr2#=sr*sr

; x axis
If sx < bx

dmin=dmin+((sx-bx)*(sx-bx))

Else If sx>(bx+bw)

dmin=dmin+(((sx-(bx+bw)))*((sx-(bx+bw))))

EndIf

; y axis
If sy < by

dmin=dmin+((sy-by)*(sy-by))

Else If sy>(by+bh)

dmin=dmin+(((sy-(by+bh)))*((sy-(by+bh))))

EndIf

; z axis
If sz < bz

dmin=dmin+((sz-bz)*(sz-bz))

Else If sz>(bz+bd)

dmin=dmin+(((sz-(bz+bd)))*((sz-(bz+bd))))

EndIf

If dmin#<=sr2# Then Return True Else Return False

End Function

Thanks for the input, it's thoughtful and i really consider some options you made, i have to think a little more about them.

Yes there is much to feed us in term of documentation :)

But before continuing the discussion i will made some clarification about why i go that way

Context

I have worked in the industry on a canned AAA plateform game, but i'm no programmer...
I know most game do it on editor. But that mean than the player cannot thrust the game world and should read the designer's mind... That's why i was seeking something more systemic.

In assassin's creed they raycast, a lot but they seek defined "gameplay element" they have something like 3 different element they constantly raycast to adapt the IK animated character (not actual geometry i know)

Splinter cell it's all done by hand, i have made once a mod for pandora tomorow multi player and you have to put all the edge by hand on actual geometry.

The game i have work on (there was a talk about it at 2008 GDC), totems from elsewhere use the concept of "block" basically it's 3D tiling. A block it's a unit of gameplay space which is the same time a skin, a gameplay element and have a specific collision mesh, you can only edit level on a certain grid within a zone, the system look up the grid to define what's next and edge was a particular kind of block.

Another solution is to compile level before into gameplay with an automated tagging process.

BUT

Older game like mario seems systemic, i mean you could go and do things the designer doesn't necessairly anticipate, making a ground for sequence breaking and speed running. For exemple, rotating blocks was grabable in the correct orientation of the face. Old zelda 64 also seems systemic but i can says than twiligth is not to my despair since i have often try obvious path the game didn't let me go :(. But these game use a collision mesh, in mario 64 if you try to go at the top of the castle, you will pass through the roof because there is no collision mesh (i have play that game a lot :) )


Research

Here some sample of the video i have review for analysis, a quick search with test level or beta level on youtube will get you more:

http://www.youtube.com/watch?v=vgEFqIcyrnA&feature=channel_page
http://www.youtube.com/watch?v=Rb1ULJktjvE&feature=channel_page
http://www.youtube.com/watch?v=Z8cGsZttvC0&feature=channel_page

And this is essentially the movement and control i want to replicate as an exercise (i'm a designer but i want to do my game, i need to understand the nuance of control)

The problematic

There is also another consideration, having done level design on editor, i can say than tagging takes a lot of time, and bad tagging can break a game. Then finding an automated systemic design for grabbing is a way to reduce cost and time to focus on what really matter: making a good game :)

cool naugthy alien :) great code!

I think doing it all in code, as you say in mario, would be far more complex, and as you say, allow the player to do things maybe he wasn't supposed to do, and at a critically important part of your game, possibly getting the player stuck, and have to restart a level.

Been there with alot of AAA games... not much fun :o)

Tamago, I have a small idea on how to implement the edge detection as a small mesh pre-processing step, but I don't think it's the best way to do it (but at least it's the easier I can think of, given my limited knowledge of 3D maths).

Basically all you need to do is iterate through all the triangles and test their Y normal component against a threshold value to determine wether if the triangle is a wall or ground (An Y normal component of 1 means it's flat ground, 0.5 may mean it's a steep slope, etc. Depending on your need use whatever you want. Something like 0.75 should be alright). After doing so, do the same test to the neighbor triangles (the ones sharing the vertexes used by that triangle), and determine if they're ground triangles. If so, then you know that the shared triangle edge you're testing is in fact an edge.

Generate the proper bounding box (not axis aligned if you want decent accuracy) for said edge and just do as mentioned above by Naughty Alien. The code should be something along these lines:

Function CalculateEdges()
    ; Iterate through all surfaces and triangles
    For each Surface
        For each Triangle
            ; Get current triangle y normal component
            NormalY# = GetTriangleNormalY(Surface, Triangle)

            ; Test to know if it's a ground
            If (NormalY# > GROUND_THRESHOLD_VALUE#) Then
                ; Oh, hey, this is a ground, let's check for the
                ; neighbor triangles.
                For each Neighbor Surface
                    For each Neighbor Triangle
                        
                        ; Get neighbors y normal component
                        OtherNormalY# = GetTriangleNormalY(NeighborSurface, NeighborTriangle)

                        ; Test if it ISN'T ground
                        If (NormalY# <= GROUND_THRESHOLD_VALUE#) Then
                            ; Seems there's an edge neighbor to the
                            ; tested triangle! Let's create it's bounding
                            ; box!
                            Edge = FindSharedEdge(Triangle, NeighborTriangle) ; (Actually, the two shared vertexes, but meh).
                            GenerateEdgeBoundingBox(Edge)
                        End If

                    Next
                Next

            End If

        Next
    Next

    ; Horray! Done!
    Return
End Function

Rudimentary, yet it should work.

Thank you for yours awesome insight, the truth is my first aproach was a little bit silly. I was planning for a simple low poly game with style and i thought that because of low poly it could be ok to search through the mesh, and even if i wanted to discriminate thanks to finding nearest mesh then surface and end with triangle (plus the collision mesh is generally have a lower count) but tagging IS simpler no matter how you think about it, i think automated tagging at "compile time" for the level is the best...

Since there is little doc about the subject i will try to post my study and experiement if it's useful... But i'm learning to code i don't know how to organize it well...

Yeah AAA game crumble on their own weight with soo many people doing them, especially when you have case where the designer fight with the artist, the result is that their opinion about what to do diverge BUT they are BOTH RIGHT... That's why you end stuck, because the artist obtain that we NEED that "chaos" to make the game look better and not crappy design art, but "chaos" blend rarely with good game design obsess with grid and metrics that make for "crappy looking", the compromise is stupid invisible wall...
add any other people in the equation... you end with safe design by commeetee... (and I even touch the problem of decision holder such as finacial and marketing part), but i'm being out of subject...


Oh, el gigante de yeso of sonic blitz3D (dami/mark engine) fame?

Yeah, I was one of the coders of that. But... fame? What's that? Fangame?

Fame is for famous, no? English is not my first langage so i apologize for any mistake... I ve seen this expression many time i have just use it back >.>

However i have done this little study to see case for a tagging at level compilation time.


[url=http://imageshack.us][img=http://img89.imageshack.us/img89/5413/grabedge3cc3.jpg][/url]

But we must assume close mesh, with self intersection , and without fan...
An interesting edgy problem is the fan, the double sided and "folded" triangle

Naughty, do you do edge shimmy-ing, or just grabbing? If so, how do you transfer onto an edge not flush with the one your on?

Posting so I can refer back to this.

@Ross C
What is the edge shimmy-ing?

Actually i'm still evaluating the problem, it's an exercise to learn whatever i can on edge grabbing, so if you have some concern about the problem just post it for revision, it might interest me.

Since i'm researching arbitrary mesh any kind of concern may help me

Edge shimmy-ing. Where your character moves left or right whilst holding onto a ledge/edge. If you move to where two egdes, of different angles meet, you will have to traverse this change of direction somehow...

@Ross C
..i do have edge shimmy-ing..practically I do have all motion similar to one seen in Tomb Raider, except climbing over bumps like Lara do in Underworld...other than that, I do have all motions, and they are all controlled with loads of trigger boxes, each trigger box disabling/enabling specific set of animations/moves, regarding is it ledge/edge, swimming, jump/grab and so on..

Hmm, interesting. Thanks for your insight :o)

Hello here is some latest research result:

here is an answer from David Neubelt on Gamedev, who have apparently work on daxter psp.



And i have ask more question about the raycasting:



I have already check splinter cell pandora tomorow, and lately mario64 et tomb raider

Tomb raider level editor tutorial:
http://www.skribblerz.com/tutorials.htm
Does not seem to feature edge tagging but the level are structured and edited in a rigid ways with grid, so it must happen in compilation time or in realtime since the level geometry is "readable".

http://www.youtube.com/watch?v=yGeggw7qVrg&feature=channel_page

Interestingly looking at this video we can se that it cover more case i previously thought (grab after a slope with a vertical wall)

Mario 64 level hack editor:
http://jul.rustedlogic.net/thread.php?id=419
I have browse the tools and the forum to see if there is some hint, it seems that the only things which is important is the collision mesh, no tagging per see

I wonder how many game that feature grabing have a level editor, so we can find hint from editing ?