DYNAMIC FREERUNNING - Optimizing and memory issues!

Greetings ladies and gentlemen, I'll try to be short this time.

I wanted to make a freerunning system like the one in games like the Assassins Creed franchise and Dying Light, in unity. I have just started researching and planning, and it turned out as more difficult than I originally thought. I assume it works with finding edges on meshes and calculate distances, but I honestly have no idea where to start. I know this is possible with unity. Assassins Creed Identity did it for iOS (https://www.facebook.com/AssassinsCreedIdentity) so I assume it doesn't impact performance much.

Can someone please explain how they did it, and how we can recreate it?

 

You could use triggers I guess.

Place triggers on the parts of the level you want to be grab-able? Give them a type so you know if its the top of a ledge etc.

 

I could do that, but that would be so much more work in the long run.
If I can make a dynamic freerunning system, I can use it in all my future games.
If I use triggers or tags or anything where you have to manually define all the places where the player can parkour, it means you have to spend ages places them on a small/medium sized map.

 

I agree, the most straight forward solution is probably by adding invisible gameobjects to the scene. Probably on a layer of their own to facilitate ray/sphere/etc casting to detect them.
There will probably need to be different versions to help you decide which control scheme to use (forward key means climb on pipe, nothing while grabbing a ledge (unless there is a ledge above), and run while on a beam etc)
Figuring out the players intention, and sychronizing animations/movements etc will probably be the tricky part.

Scanning a complex scene to find these handlholds and climbable places automagically based on raycasts and surfacenormals, area and world placement etc, will probably take to long even for a load screen to cover..

but who knows maybe you can come up with a method, perhaps the unity navmesh baking method might be a place to start researching, beams and handholds and climbable objects are essentially offmesh links in some way.. =)

 

@Brominion I like that idea. Is is possible to get the length of an offmesh link? But what about things like climbing along a ledge, you would still need some triggers or something wouldn't you?

Loading time doesn't matter, so is there a way to scan an entire scene like this and store info? It would come in handy with the AI Im working on aswell (will talk about that later). How would one do that? Im asuming it can be done almost purely with mathematics and raycast?

Im bad at explaining, but: If loading time is seriously long, could one do a scan of each map and store all the info somewhere, then save that info in unity so there would only need to be 1 scan for each scene, done in the editor instead of ingame behind a loading screen? Something like that?

 

Hey Lahzar,

I recently did something similar to this to replicate the edge grabbing in Super Mario 64. I didn't want to manually place invisible triggers everywhere so I did everything at runtime. I would go through a few steps to make sure Mario was next to a wall he could climb. First I would check the normal of a wall he was colliding with (and compare it to his normal to see if he was facing it). Then I would calculate his "end-position" of the climb (on top of the surface) and check to see if it was flat enough to stand on (through a raycast).

 

@Iron-Warrior That sounds like a great start! (btw, I checked your supermario project, and it looks great!)
How did you calculate his end position? I get how you could check if there is enough height and if it is flat enough, however, how can I check if there is enough space? I dont want the player to run into crevices that they dont fit in...
I was thinking raycasting + box collider, but I have no idea.




The system I want works like this:
- The movement buttons (WASD) together works on a 8 directions. (W + S = NE etc) What direction the player is moving decides what freerunning moves the player will do. (Climb up if W | Wallrun if W+S)
- Parkour up/down is an axis, so you cant go up and down at the same time.
- Up is default bound to sprint. When the player is holding the button, the player will parkour, if possible, in the direction of the movement buttons, using only the upwards animations.
- Down is default bound to crouch. When the player is holding this button, the player will drop down, if possible, in the direction of the movement buttons.
- There are different stages/states of the parkour:
0. The player is running along a flat surface.
1. The player starts the first parkour animation
2. The player is mid parkour
3. The player starts the second animation

Lemme explain the last bit. This works for all the moves, except jumping.
Example 1: leaping over a cube
1. The player holds the forward button and parkour up button and runs at a cube. Player leaps over the cube normaly.
2. The player leaps over a cube, holding the edge of the cube. The player lets go of the parkour up button after first animation started and before the second one starts, and changes animation, so the player stops ontop of the cube.
3. The player changes direction while in state 2, and therefore changes direction in the air.

Example 2: running up a wall
1. The player runs up a wall and stops ontop.
2. The first animation is running up and grabbing the top edge of the wall. The second is the player pulling themselves up the wall. The player stops holding parkour up before the second animation starts, and therefor he just hangs there. From here he can climb left and right along the edge using just the movement buttons.
3. The player changes direction while in state 2, the player plays a longer second animation that includes a combat roll to the direction they are holding.

Example 3: going from wallclimb to holding a pole.
1. The player plays animation 1, but presses jump during state 2. The player turns around and jumps of the wall after animation 1 finishes playing. The state is now 2 again, because the jump is a different move. During the new state 2, the player hits a horizontal pole. The player plays the poles animation 1, and therefor sets the state back to 1/2, to hang from the pole. The player presses parkour up during the new new state 2 and climbs up the pole.
2. Same example, but the player holds parkour down instead of up in the last state 2. The player drops down instead of climbing up the pole.

My problem atm is finding the (nearest) edge over the collions of the mesh the player is colliding with. If I can just figure out how to find the position of that edge, then I can check if the player can reach it. Then Ill worry about calculating the end positions. @Iron-Warrior , how did you acheive this?
If you, just like me, think I am bad explaining stuff, and there is something you dont understand, please just ask.

 

TLDR;
So far Ive made a script that uses

Code (CSharp):

1. OnControllerColliderHit()

to detect collisions. Then Ive used

Code (CSharp):

1. ControllerColliderHit.moveDirection

to find the angle between the players movement and the normal of the mesh that is collided with. Then Ive used the "Horizontal" and "Vertical" axes to find out which direction the player is moving, and which freerunning moves are available.

What I need help with: If you look at the image I made in paint You can see the player and a cube. The red X is where the player will collide with the cube. That part is done. I need help with finding the GREEN X. I have no idea how to do this! Please help ASAP!

The blue cube on the image is the minimum space the player needs to get up onto the cube. Will worry about that later!

Spoiler: Explaining Image

 

There are clever ways you could find the nearest edge on the surface of a mesh but they're fairly complex. Instead, you can do something much simpler. Take the point at the red x (a vector3) and add to it the maximum height the player can "grab" onto the ledge. Once you have this point you can move it slightly inward onto the surface and then raycast directly downwards. This will give you a point on the surface of the box he is trying to climb onto.

I show it below with m being your maximum grab height, and r being the raycast direction.

 

You should have a look at this system

 

So I have paused my ongoing extensive AI project while I wait for my Game AI Pro books to arrive. So I read a question, found here: http://answers.unity3d.com/questions/1004445/find-edgesurface-of-mesh.html and it resparked my interrest in this topic. So could we find a reasonable solution to this problem in a two weeks time?

Here is what I know:
- How to find the quad that the player hits when colliding with a mesh (see my answer at http://answers.unity3d.com/questions/1004445/find-edgesurface-of-mesh.html) NOTE: Quad must be near perfect, with a difference margin of .5!
- How to check if there is enough space for our player to stand ontop of a edge
- How to check if there is something to stand ontop of on beforementioned location
- We should do something with Inverse Kinematics and animations.
- We know several ways of doing simple parkour. What we are going for now is a dynamic climbing system like the one in the assassins creed franchise!

I am thinking that we calculate what edges are climbable on static objects while the scene is loading and on dynamic objects when the player is almost within reach. Actually generating IK points wont be very difficult when we have all the suitable edges.

I found out how to get the top edge of a quad, but its far from perfected. The code is messy and inefficient, it only works on perfect quads etc etc. So how do we get ALL the correct edges of a mesh? Correct being all the edges that are horizontal, and do not have any triangles above it.

Here is the theory behind it in a simple diagram: https://docs.google.com/drawings/d/1Ljg5Bm85_GuYekbXUplUIeJtMEL1XDE2CthUvxspoF0/edit?usp=sharing
All I need is to find correct edges! Any help before I waste the next 2 weeks of my life? Thanks in advance.

- Lahzar

 

So I made a simple version of IK generation based on mesh edges. Its just a proof of concept so its really really inefficient and buggy, but it works, so yeah. With some optimization and clever programming/planning we could use this for dynamic objects aswell!

Now the problem is actually selecting which IK points to target! I tried getting the closest one(s), but I ran out of memory all the time! Thing is there are hundreds of IK points in my simple scene, especially on this one mesh. So if we get the closest point in realtime the game will quickly run out of memory, and if we do it in for example OnControllerColliderHit the game takes a slight blow to the performance AND memory. I don't know how to solve this memory problem!

Here is the IK Generation Proof of Concept! Any suggstions of where to start optimizing it aswell would be good!

Spoiler: Unoptimized IK Generation based on mesh edges of static objects

Code (CSharp):

1. using UnityEngine;
2. using System.Collections;
3.  
4. //Generating IK points on edges of static objects
5. //Proof of concept by Imre Angelo aka Lahzar @ the unity forums! Enjoy.
6. public class GenerateIK : MonoBehaviour {    //NOTE: Objects must be read/write enabled
7.     public float IKdistance;
8.     public MeshCollider[] objs;
9.     private Vector3[] edges;
10.  
11.     void Awake()    {
12.         objs = (MeshCollider[])Resources.FindObjectsOfTypeAll(typeof(MeshCollider));
13.         for(int i = 0; i < objs.Length; i++)    {
14.             if(objs[i].gameObject.isStatic)    {
15.                 StartCoroutine(GetEdgesOfMesh(objs[i]));
16.             }
17.         }
18.     }
19.  
20.     void Update()    {
21.         if(!Input.GetKeyUp(KeyCode.O))
22.             return;
23.        
24.         objs = (MeshCollider[])Resources.FindObjectsOfTypeAll(typeof(MeshCollider));
25.        
26.         for(int i = 0; i < objs.Length; i++)    {
27.             StartCoroutine(GetEdgesOfMesh(objs[i]));
28.         }
29.     }
30.  
31.     IEnumerator GetEdgesOfMesh(MeshCollider meshCollider)    {
32.         if(meshCollider == null)
33.             yield break;
34.  
35.         if (meshCollider.sharedMesh == null)
36.             yield break;
37.        
38.         Mesh mesh = meshCollider.sharedMesh;
39.         Vector3[] vertices = mesh.vertices;
40.         int[] triangles = mesh.triangles;
41.         Transform hitTransform = meshCollider.transform;
42.  
43.         for(int t = 0; t < triangles.Length; t++)    {
44.             yield return new WaitForFixedUpdate();
45.             Vector3 p0 = vertices[triangles[t * 3 + 0]];
46.             Vector3 p1 = vertices[triangles[t * 3 + 1]];
47.             Vector3 p2 = vertices[triangles[t * 3 + 2]];
48.             p0 = hitTransform.TransformPoint(p0);
49.             p1 = hitTransform.TransformPoint(p1);
50.             p2 = hitTransform.TransformPoint(p2);
51.  
52.             float dist = 0;
53.  
54.             #region Rinse edges
55.             float acc = 0.0045f;
56.  
57.             #region p0 to p1
58.             Vector3 pointA = p0;
59.             Vector3 pointB = p1;
60.             Vector3 avg = (pointA+pointB)/2;
61.             if(pointA.y <= pointB.y + acc && pointA.y >= pointB.y - acc)    {
62.                 if(!Physics.CheckSphere(new Vector3(avg.x, avg.y + acc*2, avg.z), acc))    {
63.                     if(Physics.CheckSphere(avg, acc))    {
64.                         if(Physics.CheckSphere(avg-Vector3.up*(acc*2), acc))    {
65.                             Debug.DrawLine(pointA, pointB, Color.green, 30);
66.  
67.                             float d = (pointA-pointB).magnitude;
68.                             Vector3 newPos = pointA;
69.                             for(float i = 0; i < d; i += IKdistance)    {
70.                                 yield return new WaitForFixedUpdate();
71.                                 #region Spawn IK
72.                                 GameObject obj = new GameObject("IK Point");
73.                                 obj.tag = "IKPoint";
74.  
75.                                 if(hitTransform.FindChild("IKs") != null)    {
76.                                     obj.transform.parent = hitTransform.FindChild("IKs");
77.                                 } else {
78.                                     GameObject newIK = new GameObject("IKs");
79.                                     newIK.transform.position = hitTransform.position;
80.                                     newIK.transform.parent = hitTransform;
81.                                     obj.transform.parent = newIK.transform;
82.                                 }
83.                                 #endregion
84.  
85.                                 #region Set IK position
86.                                 obj.transform.position = newPos;
87.                                 newPos = Vector3.MoveTowards(newPos, pointB, IKdistance);
88.  
89.                                 if(i >= d)    {
90.                                     obj.transform.position = pointB;
91.                                 }
92.                                   #endregion
93.                             }
94.                         }
95.                     }
96.                 }
97.             }
98.             #endregion
99.             #region p1 to p2
100.             pointA = p1;
101.             pointB = p2;
102.             avg = (pointA+pointB)/2;
103.             if(pointA.y <= pointB.y + acc && pointA.y >= pointB.y - acc)    {
104.                 if(!Physics.CheckSphere(new Vector3(avg.x, avg.y + acc*2, avg.z), acc))    {
105.                     if(Physics.CheckSphere(avg, acc))    {
106.                         if(Physics.CheckSphere(avg-Vector3.up*(acc*2), acc))    {
107.                             Debug.DrawLine(pointA, pointB, Color.green, 30);
108.  
109.                             float d = (pointA-pointB).magnitude;
110.                             Vector3 newPos = pointA;
111.                             for(float i = 0; i < d; i += IKdistance)    {
112.                                 yield return new WaitForFixedUpdate();
113.                                 #region Spawn IK
114.                                 GameObject obj = new GameObject("IK Point");
115.                                 obj.tag = "IKPoint";
116.                                
117.                                 if(hitTransform.FindChild("IKs") != null)    {
118.                                     obj.transform.parent = hitTransform.FindChild("IKs");
119.                                 } else {
120.                                     GameObject newIK = new GameObject("IKs");
121.                                     newIK.transform.position = hitTransform.position;
122.                                     newIK.transform.parent = hitTransform;
123.                                     obj.transform.parent = newIK.transform;
124.                                 }
125.                                 #endregion
126.                                
127.                                 #region Set IK position
128.                                 obj.transform.position = newPos;
129.                                 newPos = Vector3.MoveTowards(newPos, pointB, IKdistance);
130.  
131.                                 if(i >= d)    {
132.                                     obj.transform.position = pointB;
133.                                 }
134.                                 #endregion
135.                             }
136.                         }
137.                     }
138.                 }
139.             }
140.             #endregion
141.             #region p2 to p0
142.             pointA = p2;
143.             pointB = p0;
144.             avg = (pointA+pointB)/2;
145.             if(pointA.y <= pointB.y + acc && pointA.y >= pointB.y - acc)    {
146.                 if(!Physics.CheckSphere(new Vector3(avg.x, avg.y + acc*2, avg.z), acc))    {
147.                     if(Physics.CheckSphere(avg, acc))    {
148.                         if(Physics.CheckSphere(avg-Vector3.up*(acc*2), acc))    {
149.                             Debug.DrawLine(pointA, pointB, Color.green, 10);
150.  
151.                             float d = (pointA-pointB).magnitude;
152.                             Vector3 newPos = pointA;
153.                             for(float i = 0; i < d; i += IKdistance)    {
154.                                 yield return new WaitForFixedUpdate();
155.                                 #region Spawn IK
156.                                 GameObject obj = new GameObject("IK Point");
157.                                 obj.tag = "IKPoint";
158.                                
159.                                 if(hitTransform.FindChild("IKs") != null)    {
160.                                     obj.transform.parent = hitTransform.FindChild("IKs");
161.                                 } else {
162.                                     GameObject newIK = new GameObject("IKs");
163.                                     newIK.transform.position = hitTransform.position;
164.                                     newIK.transform.parent = hitTransform;
165.                                     obj.transform.parent = newIK.transform;
166.                                 }
167.                                 #endregion
168.                                
169.                                 #region Set IK position
170.                                 obj.transform.position = newPos;
171.                                 newPos = Vector3.MoveTowards(newPos, pointB, IKdistance);
172.  
173.                                 if(i >= d)    {
174.                                     obj.transform.position = pointB;
175.                                 }
176.                                 #endregion
177.                             }
178.                         }
179.                     }
180.                 }
181.             }  
182.             #endregion
183.  
184.             #endregion
185.         }
186.  
187.         yield return true;
188.     }
189. }

 

Bump? I am going away for vacation. 5 days, hopefully someone has some answers by then