Platformer systemic edge grabing
Blitz3D Forums/Blitz3D Programming/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". Last edited 2011 |
| ||
| 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 FunctionRudimentary, 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? |
| ||
| 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. When our studio created Daxter, a 3d platformer, we first created a system that automatically detected which edges should be 'edge grabs'. We moved away from that system in the end because it allowed the player to get to places where he shouldn't be. The artist and designers wanted more control. The system we put in place was a tagging system. We would tag geometry as wall climbable, death, floor, normal collision and a few other random game specific tags. When the level geometry was processed during the build stage it would create the 'edge grab' list. It would determine which one were 'grabbable' by checking if adjacent floor geometry was a wall. If it was then you could grab on to it. Of course, Daxter's hands had to get close enough to the geometry to grab onto it so any wierd geometry cases that you were drawing out wouldn't happen because of his body's 'collision geometry' wouldn't allow him to get close enough. When Daxter's hands were close enough, and a few ray casts would tell us that info, we snap his hands to the ledge. I don't know how Mario 64 did it but I know of a few more commercial titles that do it that way as well. I think the method works very well unless you have procedural or user created content - only then would you have to automatically determine which parts of the geometry are edge grabs. -= Dave And i have ask more question about the raycasting: Daxter would shoot a ray from his chest in a direction that was computed from his velocity. If the ray collided with a polygon it would check the polygon to see if any of its edges were tagged as an edge grab. If the edge was an appropriate edge to grab then it would snap its hands to the position. The scheme worked well because Daxter's hands were close together it wont work if the players hands are far apart then you have to take into account two ray casts. -= Dave 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 ? |
   |