Godot 4 Support

[JamDoggie]

IDK if this project is being actively worked on currently, but a Godot 4 update would be nice. I've had some issues myself porting this correctly.

[pixeljammed]

Please do it I'm too stupid for godot's file handling. forgot how it works

[Btan2]

Sorry for the delay guys. Life has been rough for me because the Australian government legitimately hates its own citizens. I'll aim for having it ported in 2 weeks.

[pixeljammed]

all good mate hopefully its alright down under man <3

[pixeljammed]

dont wanna bother you but is it happening? if you dont have time thats fully understandable

[Btan2]

I have next week off so I'll get to working on it. Sorry for the delays, I am pretty keen on getting this fixed and working myself.

[pixeljammed]

i will paypal you 50 quid right now if it gets fixed

[Btan2]

Thanks for the incentive haha.

Ok, so there appears to be a lot of inaccuracies with 4.1's iteration of move_and_slide() and the CharacterBody3D in general.

I'd tried my best, but there are way too many jiggles to iron out. So I'm gonna write my own collision detection routine. The thing that is causing collision resolution problems (i.e. jiggles) is the fact that collision normals that are returned are not from the tris of the colliding mesh, but instead calculated in regards to the collision shape. So the player is sliding off surfaces that technically don't exist. This is what causes buggy movement when walking over/along sharp edges. Getting the correct surface requires grabbing the vertices of the mesh, converting them to tris and then performing multiple intersection tests with the player's collision shape.

I managed to successfully retrieve sphere/tri intersections last night, I added q_move (I should say Quake) acceleration and friction functions to calculate velocity, and it seems to be pretty damn smooth!

The next step is expanding the sphere into either a capsule or cylinder to emulate the player's body. I will go with capsules for now since as cylinders require different intersection alogrithms, however I plan on switching to cylinders later down the track since they offer better ground detection due to the flat bottom.

I'll try to keep you updated as I go and I'll be setting aside more time this week. Successfully detecting those damn tris and seeing the sphere correctly slide along them has been very motivating!

[ChotoTheBright]

Thank you for the update!

[pixeljammed]

you're awesome but can we take the paypal offer down to 20 pounds (like 40 aud) love u so much bro thanks one day I'll be as smart as you sir :-)

[Btan2]

Good news. Got it working.

https://github.com/Btan2/Q_Move/assets/17605586/17faceee-e1af-4a12-9288-08c1043310a6

Before I release, there are still a few things I need to do:

1. Optimise the triangle fetching methods to handle meshes with high poly counts. The script currently tests for collisions against all triangles in the mesh. If the collider is touching half a dozen spheres performance will probably take a hit because it's performing collision tests against thousands of triangles, multiple times per frame. I need to implement an AABB Octree that returns batches of triangles that are closest to the capsule collider. I already created one in Unity several years ago, so I'll need to dig through that code.

2. Figure out how to orient triangle vectors correctly. Godot's method of retrieving mesh vertices doesn't return global co-ordinates correctly. If you rotate an object in the editor the vertices that are returned are not rotated which causes incorrect collision detection.

3. Test for more edge cases and "difficult" geometry to make sure velocity is behaving itself.

At the moment I'm using C# since the execution time is supposedly much faster than GDScript. I plan on converting them back to GD for those that are not using the mono build.

[pixeljammed]

Btan2 for president

[Btan2]

Quick update: I Managed to orient the vertices of the triangles correctly. For those interested -> meshInstance.ToGlobal(vertex). I made the mistake of calling ToGlobal() from the player's node instead of the meshInstance node, so no wonder the orientation was all messed up!

Lastly, I am in the process figuring out how to add triangles to the octree. Now this can be done by simply adding triangles to whichever AABB the triangle intersects with. The problem is that if a triangle intersects with multiple AABBs the octree will contain duplicate triangles. This is not good because it can drastically increase the number of tri objects and consume lots of memory.

At the moment I am writing a function which clips an intersecting triangle to the AABB. This involves calculating the intersected shape of a tri/AABB and then splitting the shape it into subsequent triangles. Ironically this also increases the original number of tris, but if the depth of the octree is not too deep then things should be ok?

The intersection shape of a box and triangle: (triangle has not been split yet)

Other solutions include inflating the AABB the tri collides with so it surrounds the tri completely, or simply using only AABBs that completely surround the tri and stop the insertion process then and there. This next step will take a bit of trial and error.

[ChotoTheBright]

Appreciate the update! Thank you again so much for your continued hard work on this 8]

[pixeljammed]

i'm not gay but i would do anything for Btan2. ily bro

[Btan2]

I ended up programming a BVH for spatial partitioning. It is slightly inaccurate as I'm using a rather simple splitting method, but the memory footprint is low and easier to manage. The goal is to reduce the number of tris to check rather than confine them to ultra specific boundaries, so it think it should be ok.

I'm using this brilliant guide, which has additional articles on how to improve performance, so that's likely something I'll do later: https://jacco.ompf2.com/2022/04/13/how-to-build-a-bvh-part-1-basics/

I will try to get it to work with the character controller this weekend and see how it performs.

[ChotoTheBright]

I'd love to give that guide a read myself! Very interested to see what could come from it. Thanks again for the update! :)

[Btan2]

The BVH was problematic; I may have done something wrong. I instead used an octree but incorporated the optimisation techniques from the BVH. Copying triangle objects can be expensive memory wise, so instead we can copy the index of a triangle within the triangle array, so each leaf node of the octree contains a integer array instead of an array of triangle objects. This means we can store duplicate triangles without worrying too much about memory usage since we are only storing integers. I am also using a HashSet when returning arrays from the octree in order to remove duplicates during an octree search; we do not want to repeat collision tests so duplicate triangles must be removed when performing a search.

In the following scene, the box (blue) will only test 9% of the sphere's triangles at its current position. Memory usage sits around 62mb for this scene.

I also found a robust AABB/Triangle intersection test to ensure the triangles of complex geometry are captured correctly. I left the code under the comments section of the following link: https://gist.github.com/zvonicek/fe73ba9903f49d57314cf7e8e0f05dcf

[Btan2]

Almost there! I imported the first level from Quake into Blender, exported to glb and then imported that into Godot as a test level. Here is E1M1 from Quake working with my collision detection system:

Aside from Area3D nodes which are used to determine which mesh objects to grab triangles from, no engine physics (Godot or Bullet) are being used to detect and resolve collisions with the player's body.

I was worried that generating the AABB octree would take a long time, however it seems to be very quick. I haven't recorded compile time metrics yet, but from the start of the video when the Godot logo is displayed to when I start running around is how long it took to generate spatial partitioning. Pretty neat, huh? That being said, I only imported/exported about 1/2 of the E1M1 map just to be safe. Buttons, doors and entities are obviously not included here, but no additional optimizations were done in Blender, so the level is using its original brush geometry. I believe my collision detection system could work with Qodot, but I am not yet familiar with that addon.

It shouldn't be too long now, I just need to iron out player movement when moving up and along steps, as well as fix velocity redirection when touching multiple sharp surfaces.

[pixeljammed]

btan i fucking love you ur a legend

On Tue, 28 Nov 2023 at 18:01, Btan @.***> wrote:

Almost there! I imported the first level from Quake into Blender, exported to glb and then imported that into Godot as a test level. Here is E1M1 from Quake working with my collision detection system:

output2.gif (view on web) https://github.com/Btan2/Q_Move/assets/17605586/3e15c163-fcde-4c85-91a6-8c9dc91fb99d

Aside from Area3D nodes which are used to determine which mesh objects to grab triangles from, no engine physics (Godot or Bullet) are being used to detect and resolve collisions with the player's body.

I was worried that generating the AABB octree would take a long time, however it seems to be very quick. I haven't recorded compile time metrics yet, but from the start of the video when the Godot logo is displayed to when I start running around is how long it took to generate spatial partitioning. Pretty neat, huh? That being said, I only imported/exported about 1/2 of the E1M1 map just to be safe. Buttons, doors and entities are obviously not included here, but no additional optimizations were done in Blender, so the level is using its original brush geometry. I believe my collision detection system could work with Qodot, but I am not yet familiar with that addon.

It shouldn't be too long now, I just need to iron out player movement when moving up and along steps, as well as fix velocity redirection when touching multiple sharp surfaces.

— Reply to this email directly, view it on GitHub https://github.com/Btan2/Q_Move/issues/6#issuecomment-1830399880, or unsubscribe https://github.com/notifications/unsubscribe-auth/APYBWWFLWMP56QBLG576ADLYGYRGLAVCNFSM6AAAAAAZ7YAVN6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQMZQGM4TSOBYGA . You are receiving this because you commented.Message ID: @.***>

[ChotoTheBright]

Very very exciting to see! Thank you again for everything you've put into this, Btan :D

[sinewavey]

Hi- I've been working on porting this over as well, and am preparing a public release as I get closer to a working project. That in mind, I used Jolt to go back to a cylinder controller.

I'm impressed at this, and I hope to see what magic you did for your own move and slide re-write. I'm still dealing with a few small issues regarding sloped stairs to other sloped stairs, though. Ultimately, I made use of move_and_collide, test_move and cast_motion where appropriate.

I would love to work more on this together if you are interested as I consider it a core requirement of my game, and have looked at various other implementations, re-wrote Q3's myself, and many other solutions. Ultimately, yours came the closest to a balance of verbosity and function quality, and served as a great reference to write my own. Depending on how things go, I'd be interested in incentivizing more financially as well.

Eager to see the release and hopefully improve my own - but your video's looking amazing.

Update, as of 12/29/23- I have a public math library available where I'll be adding a version of this algorithm for GD4 with Jolt soon

[Btan2]

Thanks for the comment @sinewavey, it means a lot that I can help you out. I'm currently caught up with a bit of irl work at the moment, but I aim to finish this off hopefully by the end of the month. Coincidentally I've been building my own math library over the past year or so. It's mostly 3d vector math stuff; I figured I'd save useful algorithms for future use e.g. triangle intersection tests, SAT algorithms, sorting vertices based on angular distance and so on. I'm keen to collab with like-minded people, so add me on discord if you want: btan2_57506

[DeepDarkDweller]

I second @sinewavey's sentiments. I would love to contribute to this project however I can. I first discovered your work through your "How to Climb a Staircase Properly" article and got excited when I saw you were working on a Godot implementation. I've been working on a Quake-like game myself for the better part of a year now and I've been disappointed with many of the currently available solutions for a good Quake-style player controller. This Q_move project seems to be exactly what I've been looking for and I'd love to help however I can. Either by making code contributions or monetary donations.