Hard Light Productions Forums

Off-Topic Discussion => Programming => Topic started by: Aardwolf on January 02, 2012, 04:41:01 pm

Title: My Game Engine is too Lame
Post by: Aardwolf on January 02, 2012, 04:41:01 pm
I'm making a first-person shooter where you fight giant space bugs!

(http://i93.photobucket.com/albums/l77/Aardwolf001/Quick%20Illustrations/screenshot-2012-0-2-17-38-8.png)

But it's too slow :(



The problem is primarily the AI and the physics. I did a simple experiment, recording the framerates with and without each of these two features.

frames per second
           
AI off
           
AI on
Physics off
           
~30
           
~15
Physics on
           
12-14
           
4-7

I've actually made some changes that make the AI faster since I recorded those data, but you get the gist.




Of course, this only tells me that the physics is taking a lot of my time; it doesn't tell me that I could do it any better than Bullet could, or that I'm even using Bullet as efficiently as I could be. Still, there are a few issues I have with Bullet...

Ragdolls. It's not reflected in the above statistics because I refrained from killing any enemies for that experiment, but just a handful of ragdolls can cause a considerable performance hit. I wish there were a way I could tell Bullet "all of these rigid bodies are parts of a whole, and that whole will never be bigger than some size; thus, you should only check for collisions between the parts of two separate ragdolls if they are near one another" ... But afaik there is no easy way to do it (there are ways, but they aren't easy). Unfortunately, all of my past attempts at implementing ragdoll physics have been miserable failures  :sigh:

Terrain. I don't know if Bullet is putting the triangles of the terrain mesh into some sort of spatial partitioning tree, but it would be profoundly stupid of it not to do so. I recently wrote a system for destructible terrain, and I want to be able to integrate that into this game engine, but the polygon counts this thing produces are much higher than what I have currently. However, the triangle data is already conveniently partitioned into cubic chunks. It would make sense to me to keep track of which physics objects (or game entities) are in which chunks, and consult that to figure out which objects need collision detection... maybe Bullet has something I can use for that, but making it match up with my destructible terrain system may prove difficult.




So yeah, suggestions?
Title: Re: My Game Engine is too Slow
Post by: The E on January 02, 2012, 06:45:02 pm
Okay, stupid question first, have you run a profiler on your program to see where the hotspots in the AI and physics code are?
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on January 02, 2012, 07:23:39 pm
Yes, I have run a profiler (AMD CodeAnalyst)... however, I am thinking about switching to another one, because some of the info I'm getting from this one is bull****.

But anyway, here's the top entries (sorted by "total")...

Name
        Self     Children     Total     
btGjkPairDetector::getClosestPointsNonVirtual3720622099
btMinkowskiPenetrationDepthSolver::getPenetrationDirections4818611909
btDiscreteDynamicsWorld::debugDrawConstraint316881691
btCompoundCollisionAlgorithm::CreateFunc::CreateCollisionAlgorithm310001003

I'm not sure how I managed to not notice it previously, but that third one is quite peculiar, as I never used the debug drawer while I was recording this stuff.

I'm going to double-check that the version of Bullet I'm static-linking with is not a debug build, since lower on the list (10th highest as far as "total") is _wassert, which shouldn't be getting called in a release build  :ick:

Then again, maybe that is related to the bull**** I mentioned I'm getting from AMD CodeAnalyst... for example, it says that CibraryEngine::SkinnedCharacter::UpdatePoses (one of my functions) is being called by __GLeeLink_GL_VERSION_1_2, and that it's calling __GLeeLink_GL_VERSION_1_3... which is complete and utter bull****. The function in question has nothing to do with OpenGL. Similar bull**** exists elsewhere.  :sigh:
Title: Re: My Game Engine is too Slow
Post by: The E on January 02, 2012, 07:33:22 pm
Which version of Visual Studio are you using (if any)? If yes, have you tried the VS profiler?

Another question would be if you are building with all the optimizations switched on, especially the SSE2 options.
Also, which OpenGL version are you developing against? Are you using all the nice little go-faster switches, like Vertex Buffer Objects, non-immediate mode rendering and all that stuff?
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on January 02, 2012, 08:00:20 pm
It turns out it was a debug version of Bullet. I tried again with a release build and it's much faster.

I am using MSVC++ 2010 Express; no I have not tried the VS profiler.

I have not tried SSE2.

OpenGL version... it's a hodge-podge  :ick: I know I ought to pick one and stop using the deprecated features, but I haven't done it. Yes, I'm using VBOs for most things.
Title: Re: My Game Engine is too Crashy
Post by: Aardwolf on January 08, 2012, 03:26:46 pm
Now for another issue with my game engine! It sometimes likes to crash just after loading completes (or just before the game starts, I'm not entirely sure which).

I have occasionally managed to catch this when running a debugger, and the crash is in lua5.1.dll ... however, the call stack is rubbish; the only stack frames it contains are from lua5.1.dll! I don't know what to make of this.

I have a hunch, that maybe it has something to do with my loading screen being multi-threaded?
Title: Re: My Game Engine is too Crashy
Post by: BritishShivans on January 08, 2012, 10:20:26 pm
Those "bugs" look like Shivans. Are you sure they're not baby Sathanases in disguise?  :wtf:
Title: Re: My Game Engine is too Crashy
Post by: The E on January 09, 2012, 08:26:12 am
Hang on. A multi-threaded loading screen? Somehow, that strikes me as a somewhat bad idea, given that most loading involves HDD access, and given that that is usually among the slowest things possible, and not really suitable for multithreading...
Title: Re: My Game Engine is too Crashy
Post by: Nuke on January 09, 2012, 10:52:18 am
i bet hes just running his gui in a thread and loading data in another.
Title: Re: My Game Engine is too Crashy
Post by: Aardwolf on January 09, 2012, 11:55:16 am
i bet hes just running his gui in a thread and loading data in another.

Precisely! It lets me have a cursor which moves around (kinda pointless, but it makes it obvious the game hasn't frozen), and it lets me press Esc to abort mid-load (although it still has to finish whatever operation it was on).

I had to jump through some hoops to make it not fubar the OpenGL stuff... so it still pauses at the very end when it's time to call the OpenGL stuff. But it's better than nothing.
Title: Re: My Game Engine is too Crashy
Post by: The E on January 09, 2012, 11:58:48 am
Ah, Ok. That does sound more sensible indeed.
Title: Re: My Game Engine is too Crashy
Post by: Aardwolf on January 10, 2012, 12:42:57 am
Bleh. Inconsistent crashes are annoying, because you can't tell if they're fixed. And this one is particularly annoying, because the few times I've managed to catch it when I'm running a debug build, the only thing on the call stack has been lua dll stuff :(

I don't know what to do about this!
Title: Re: My Game Engine is too Crashy
Post by: Nuke on January 10, 2012, 11:55:57 am
this is where id load my code with printf()s to see exactly where its happening at.
Title: Re: My Game Engine is too Crashy
Post by: Aardwolf on January 10, 2012, 12:59:03 pm
I suppose I'll have to.

Still, it will be a bit iffy, because there are two threads. And for all I know it could be in a destructor or something (which would make it hard to debug that way).



Edit: Much to my amazement, after some tweakage of my project settings, this error is now giving me a more meaningful call stack!

Code: [Select]
lua5.1.dll!00101212()
[Frames below may be incorrect and/or missing, no symbols loaded for lua5.1.dll]
lua5.1.dll!00113aab()
lua5.1.dll!00114fd1()
lua5.1.dll!001058f2()
lua5.1.dll!0011192d()
msvcr80.dll!63874d83()
Test.exe!_nh_malloc_dbg_impl(unsigned int nSize, int nhFlag, int nBlockUse, const char * szFileName, int nLine, int * errno_tmp)  Line 239 + 0x19 bytes C++
Test.exe!_nh_malloc_dbg(unsigned int nSize, int nhFlag, int nBlockUse, const char * szFileName, int nLine)  Line 302 + 0x1d bytes C++
Test.exe!malloc(unsigned int nSize)  Line 56 + 0x15 bytes C++
Test.exe!operator new(unsigned int size)  Line 59 + 0x9 bytes C++
Test.exe!std::basic_string<char,std::char_traits<char>,std::allocator<char> >::_Copy(unsigned int _Newsize, unsigned int _Oldlen)  Line 1932 + 0x15 bytes C++
00fc63e8()
Test.exe!boost::`anonymous namespace'::create_current_thread_tls_key()  + 0xb bytes C++
Test.exe!boost::call_once<void (*)(void)>()  + 0xe9 bytes C++
Test.exe!boost::detail::thread_data<Test::TestGame::Loader>::run()  Line 62 C++
Test.exe!boost::`anonymous namespace'::thread_start_function()  + 0x63 bytes C++
Test.exe!_callthreadstartex()  Line 314 + 0xf bytes C
Test.exe!_threadstartex(void * ptd)  Line 297 C
kernel32.dll!763e3677()
ntdll.dll!770b9f42()
ntdll.dll!770b9f15()

Why is malloc calling lua? And what's that msvcr80.dll doing in there?  :confused:
Title: Re: My Game Engine is too Crashy
Post by: Aardwolf on January 12, 2012, 12:03:25 am
Gameplay video if anyone is interested:

http://youtu.be/847Vlwl2eBc
Title: Re: My Game Engine is too Crashy
Post by: BritishShivans on January 12, 2012, 01:28:46 am
I'm surprised you didn't see my post asking if the enemies were baby Sathanases in disguise. Too busy?
Title: Re: My Game Engine is too Crashy
Post by: Aardwolf on January 12, 2012, 12:54:43 pm
Eh... I saw it, but it seemed too silly to be worth replying to  :blah: But since I'm less frustrated with my game not working now...

Shivans only have 5 legs, and they're in a weirder arrangement...

At one point (http://www.hard-light.net/forums/index.php?topic=48445.msg1354700#msg1354700) I made an alien that looked more a Sathanas x Zergling (or according to some people, Sathanas x Bunny), but these bugs just look like crabs  :doubt:
Title: Re: My Game Engine is too Crashy
Post by: Aardwolf on February 05, 2012, 05:23:00 pm
I'm still occasionally running into this crash... can anyone help?

Code: [Select]
lua5.1.dll!00251212()
[Frames below may be incorrect and/or missing, no symbols loaded for lua5.1.dll]
lua5.1.dll!00263aab()
lua5.1.dll!00264fd1()
lua5.1.dll!002558f2()
lua5.1.dll!0026192d()
msvcr80.dll!74cb4d83()
Test.exe!_threadstartex(void * ptd)  Line 292 + 0x5 bytes
kernel32.dll!773b339a()
ntdll.dll!77e59ef2()
ntdll.dll!77e59ec5()

The one stack frame that it has source for is the _threadstartex function in threadex.c

I'm still not sure why it's doing anything with msvcr80.dll, as I've tried to get rid of that dependency in as many places as I could think of...

Edit: A little more info, here's MSVC++ 2010's debugger's output. It's not the output that goes with the above stack trace, this is from a successful play of the game.

Code: [Select]
'Test.exe': Loaded 'C:\Programming\C++\MSVCCibraryEngine\Release\Test.exe', Symbols loaded.
'Test.exe': Loaded 'C:\Windows\SysWOW64\ntdll.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\kernel32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\KernelBase.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Program Files\Alwil Software\Avast5\snxhk.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\opengl32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\msvcrt.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\advapi32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\sechost.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\rpcrt4.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\sspicli.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\cryptbase.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\gdi32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\user32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\lpk.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\usp10.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\glu32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\ddraw.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\dciman32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\setupapi.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\cfgmgr32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\oleaut32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\ole32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\devobj.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\dwmapi.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Program Files (x86)\Lua\5.1\lua51.dll', Binary was not built with debug information.
'Test.exe': Loaded 'C:\Program Files (x86)\Lua\5.1\lua5.1.dll', Binary was not built with debug information.
'Test.exe': Loaded 'C:\Windows\winsxs\x86_microsoft.vc80.crt_1fc8b3b9a1e18e3b_8.0.50727.6195_none_d09154e044272b9a\msvcr80.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\ws2_32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\nsi.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\OpenAL32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\winmm.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\imm32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\msctf.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\atioglxx.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\version.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\atiadlxy.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\wintrust.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\crypt32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\msasn1.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\MMDevAPI.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\propsys.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\wdmaud.drv', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\ksuser.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\avrt.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\shlwapi.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\AudioSes.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\msacm32.drv', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\msacm32.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\midimap.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\wrap_oal.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\dsound.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\powrprof.dll', Cannot find or open the PDB file
'Test.exe': Loaded 'C:\Windows\SysWOW64\clbcatq.dll', Cannot find or open the PDB file
The thread 'Win32 Thread' (0x11e4) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0xfb0) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0x768) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0x10dc) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0x12c8) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0xc78) has exited with code 0 (0x0).
'Test.exe': Unloaded 'C:\Windows\SysWOW64\wrap_oal.dll'
'Test.exe': Loaded 'C:\Windows\SysWOW64\wrap_oal.dll', Cannot find or open the PDB file
The thread 'Win32 Thread' (0x12c0) has exited with code 0 (0x0).
WARNING: 0:19: implicit cast from int to float
WARNING: 0:20: implicit cast from int to float
WARNING: 0:21: implicit cast from int to float
WARNING: 0:19: implicit cast from int to float
WARNING: 0:20: implicit cast from int to float
WARNING: 0:21: implicit cast from int to float
WARNING: built-in varying gl_TexCoord [3] defined in Vertex shader and not used in Fragment shader
WARNING: built-in varying gl_TexCoord [4] defined in Vertex shader and not used in Fragment shader
WARNING: 0:19: implicit cast from int to float
WARNING: 0:20: implicit cast from int to float
WARNING: 0:21: implicit cast from int to float
WARNING: built-in varying gl_TexCoord [3] defined in Vertex shader and not used in Fragment shader
WARNING: built-in varying gl_TexCoord [4] defined in Vertex shader and not used in Fragment shader
WARNING: built-in varying gl_TexCoord [0] defined in Vertex shader and not used in Fragment shader
WARNING: built-in varying gl_TexCoord [1] defined in Vertex shader and not used in Fragment shader
WARNING: built-in varying gl_TexCoord [2] defined in Vertex shader and not used in Fragment shader
WARNING: built-in varying gl_TexCoord [3] defined in Vertex shader and not used in Fragment shader
WARNING: built-in varying gl_TexCoord [4] defined in Vertex shader and not used in Fragment shader
WARNING: built-in varying gl_TexCoord [0] defined in Vertex shader and not used in Fragment shader
WARNING: built-in varying gl_TexCoord [1] defined in Vertex shader and not used in Fragment shader
WARNING: built-in varying gl_TexCoord [2] defined in Vertex shader and not used in Fragment shader
WARNING: built-in varying gl_TexCoord [3] defined in Vertex shader and not used in Fragment shader
WARNING: built-in varying gl_TexCoord [4] defined in Vertex shader and not used in Fragment shader
The thread 'Win32 Thread' (0xbdc) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0x1028) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0x1308) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0x1068) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0xfe4) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0x10c0) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0x1344) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0x13e0) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0xca8) has exited with code 0 (0x0).
The thread 'Win32 Thread' (0x1020) has exited with code 0 (0x0).
The program '[5108] Test.exe: Native' has exited with code 0 (0x0).

Ignore the OpenGL warnings, and don't worry too much about C:\Program Files\Alwil Software\Avast5\snxhk.dll - that's just Avast antivirus.

One of the things that I'm concerned about is C:\Windows\winsxs\x86_microsoft.vc80.crt_1fc8b3b9a1e18e3b_8.0.50727.6195_none_d09154e044272b9a\msvcr80.dll ... it's right after the lua DLLs (maybe they are what's loading it?), and the directory it's in has got me seriously :confused:-ing.
Title: Re: My Game Engine is too Crashy
Post by: The E on February 05, 2012, 05:52:15 pm
Welcome to WinSxS (http://en.wikipedia.org/wiki/Winsxs), MS' attempt to alleviate DLL hell. If you do not know what it is, let me explain. Assume you have a program that is compiled against a specific version of a system library, in this case, msvcr80.dll. The problem is that MS will update these libraries periodically. If your program depended on a given behaviour in that version of msvcr80.dll that was around when it was compiled, and that behaviour was changed in the new version, then obviously the behaviour of your program will be affected. To avoid this, the MSVC compiler embeds a manifest in your exe, telling the DLL loading routines which version of the dll to load. In order to keep multiple versions of the same dll around, all of these varying versions are stored in the WinSxS structure (SxS standing for Side-by-Side).

So yeah. Nothing to worry about, just MS protecting you from stupid errors.

As for the crash, well, unless you can find a lua dll that has debug info, there's really nothing you can do. AMong other things, this is why FSO's Windows builds have the lua library statically linked into the exe.
Title: Re: My Game Engine is too Crashy
Post by: Aardwolf on February 05, 2012, 08:48:57 pm
Y'know, I bet if I had googled "WinSxS" I could have found that out. But instead I googled the name of the DLL file, and just found a bunch of error reports for WoW.

I've had the error occur another time today, and this time the call stack is slightly different!

Code: [Select]
lua5.1.dll!00101212()
[Frames below may be incorrect and/or missing, no symbols loaded for lua5.1.dll]
lua5.1.dll!00113aab()
lua5.1.dll!00114fd1()
lua5.1.dll!001058f2()
lua5.1.dll!0011192d()
Test.exe!_read_nolock(int fh, void * inputbuf, unsigned int cnt)  Line 230 + 0x15 bytes
msvcr80.dll!65424d83()
Test.exe!_threadstartex(void * ptd)  Line 292 + 0x5 bytes
kernel32.dll!773b339a()
ntdll.dll!77e59ef2()
ntdll.dll!77e59ec5()

_read_nolock is in read.c

Something to do with reading a file, and multithreading. Bleh.  :(




Edit: Changed something. I won't see if it's fixed, but I'll see if it isn't.  :sigh:

I think the problem was that I was using bools to communicate between threads whether the load had finished, and I should have known better (http://bytes.com/topic/c/answers/649495-boolean-variable-thread-safety-c). So now I made those bools private and I'm using getters and setters which do mutex locks.



Edit II: Wow, I should've at least tested it once before I said "maybe fixed". With the mutex locks it now crashes consistently.
Title: Re: My Game Engine is too Crashy
Post by: Aardwolf on February 20, 2012, 01:46:54 pm
:bump:

Progress report! as if anyone cared

I may have made some progress w.r.t. that inconsistent crash! I don't know why I didn't try this sooner...

I modified the loading screen so that instead of taking me to the game when it finished loading, it just dumped me back into the main menu. This allowed me to sit through the load once, and then just hit the "Create Game..." button repeatedly. And from this I discovered that the crashing is not limited to the first load.

Since the stack trace said the problem was in the lua dll, and the last thing the loading screen would say before crashing was "starting game", that suggested that the problem was in game_start.lua, so my next step was to add debug outputs at the beginning and end of that file... using that, I was able to determine that the error was indeed somewhere in that script!

Furthermore, it was giving me more specific error info, from which I determined that the error had something to do with file I/O. So I put debug outputs before and after the place in game_start.lua where I was calling dofile. When it crashed, the first one printed, but not the second one. So the problem was either with dofile, or with the script dofile was executing. I tried putting debug outputs at the top and bottom of that file as well. When it crashed, neither printed. Solution: no dofile. Now I run the script from C++ instead, and it seems to be fixed... ish.

However, now I sometimes get a crash in the code that handles keyboard/mouse input (possibly related to the part of that which talks to Lua). Le sigh  :sigh:
Title: Re: My Game Engine is too Crashy
Post by: Nuke on February 21, 2012, 11:16:55 am
use require, it does some things that dofile doesnt, like making sure it doesnt run the same code multiple times. for example i have a file that handles the opengl frame, the require statements ensure that the files get run once, but doesnt run them again. using a dofile in this situation will load,compile, and execute them each time the loop runs, which is bad on the file system, especially with multiprocessing going on. its slightly different, you must exclude the .lua extension from the file name, it just wont work with it in there.
Title: Re: My Game Engine is too Crashy
Post by: Aardwolf on February 21, 2012, 09:35:26 pm
I'm almost certain that's not the issue.

Apparently, there were some hoops (http://lua-users.org/wiki/ThreadsTutorial) I was supposed to jump through to get Lua to play nice with my multi-threaded loading screen.

My loading screen now uses lua_newthread to create its own Lua state, but I haven't done any of the stuff that tutorial mentions. I haven't had a crash since I made these changes, but as always I won't know whether it's fixed until I find out it's broken.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on March 11, 2012, 04:05:04 pm
About a month ago I was trying to figure out what exactly was making my game run so slowly, and I did some experimentation. In the experiment, I had 100 enemies in the game, and told them all to die at the 5 second mark, producing 100 ragdolls with 21 bones each.

Here's what I observed:

Test #         Condition     Spheres          No constraints     Framerate
1Always true
2 fps
2Always true
Yes
4 fps
3Always false
20 fps
4Always false
Yes
76 fps
5False if both items are ragdolls         
3 fps
6False if both items are ragdolls
Yes
4 fps
7False if both items are ragdolls
Yes
Yes
5 fps
8False if both items are ragdollsYes
3 fps


Condition: Controls whether a pair of objects can collide with one another. This is implemented as a callback which is called every time two objects are near one another. The values returned by this callback were not cached.
Spheres: In these tests, all bones' collision shapes were replaced with spheres with radius 0.5 meters. Normally they use btMultiSphereShapes---a btMultiSphereShape is a convex hull around a collection of 1 or more spheres, so its surface may consist of parts of spheres, cylinders, cones, and planes.
No constraints: In these tests, the constraints that normally hold the bones of the ragdolls together at the joints were removed.



SIMULATING 2100 BALLS ON A TERRAIN MESH SHOULD RUN FASTER THAN 5 FPS! Especially considering they're not even interacting with each other!

It was settled: Bullet had to go.



That was Feb 14th. In the time since then I've made enough progress with my replacement physics engine to recreate that experiment. Much to my dismay, it only got 4-5 fps! :(

But then I realized there was a problem with my TriangleMeshShape::GetRelevantTriangles(AABB relevance) function! It was using an Octree to figure out what triangles might be relevant, but when it found that a leaf node's AABB intersected the relevance AABB, it accepted all of the triangles contained within that node, even if those triangles' AABBs didn't intersect the relevance AABB!

I made the change, and now it gets 20-30 fps! Awesome! :D
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on April 30, 2012, 08:02:13 pm
Multisphere-multisphere collisions work now!  :D But now I've got to figure out how to prevent objects from being pushed through each other.  :(

Given a graph with rigid bodies as nodes and contact points between them as edges, I need to find what impulses to apply at each contact point in order for it to behave physically.

What I have now is void DoCollisionResponse(const ContactPoint& cp); it works when there's only two objects involved, but that's it. The impulse it applies depends on the relative local velocity at the point of contact, and applying the impulse modifies the relative local velocity used when handling subsequent contact points. The result varies depending on which order the contact points are evaluated in, and is wrong either way.



I don't know how to proceed.
Title: Re: My Game Engine is too Awesome
Post by: z64555 on May 01, 2012, 12:56:27 am
The impulse it applies depends on the relative local velocity at the point of contact, and applying the impulse modifies the relative local velocity used when handling subsequent contact points. The result varies depending on which order the contact points are evaluated in, and is wrong either way.

Some reading is required. http://en.wikipedia.org/wiki/Elastic_collision

Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on May 01, 2012, 02:26:31 pm
Naw man, I know all that stuff already. My DoCollisionResponse function works correctly for a single pair of colliding objects. And I'm not doing perfectly elastic collisions anyway; my game would not be very fun if every floor and wall were covered with repulsion gel. :ick:



The issue is how to deal with multiple objects colliding simultaneously, i.e.:
Given a graph with rigid bodies as nodes and contact points between them as edges, I need to find what impulses to apply at each contact point in order for it to behave physically.

I've made a few more observations since I originally formulated the problem:
Title: Re: My Game Engine is too Awesome
Post by: Tomo on May 01, 2012, 03:20:41 pm
I assume you're just running inelastic collisions with an arbitrary coef. of restitution?

Filling a ball pit is seriously computationally expensive.

Can you assume that an object can only collide with one other movable object and an immovable one in any given simulation step? (not necessarily rendered frame)
- I presume the ground can be safely assumed to be immovable.

If you simplify to assume 'dead relative stop' if a collision is below a certain threshold energy it may simplify the problem enough.
Title: Re: My Game Engine is too Awesome
Post by: z64555 on May 01, 2012, 03:41:06 pm
Naw man, I know all that stuff already. My DoCollisionResponse function works correctly for a single pair of colliding objects. And I'm not doing perfectly elastic collisions anyway; my game would not be very fun if every floor and wall were covered with repulsion gel. :ick:

Ok, so are you trying to do inelastic collisions, elastic collisions with kinetic friction, or some sort of combination?

I think your trying to go after elastic collisions with kinetic friction applied, because even inelastic collisions obey the conservation of momentum... which would mean that the collisions would continue forever.

Given a graph with rigid bodies as nodes and contact points between them as edges, I need to find what impulses to apply at each contact point in order for it to behave physically.

Oh, I think I see your dilemma, when considering the contact point edges can be non-perpendicular and non-radial.  :blah:

Quote
I've made a few more observations since I originally formulated the problem:
  • Done correctly, after all the impulses are applied, no contact point should have an "inward" relative local velocity.
  • It seems like this will be an O(n2) algorithm. Probably.

What do mean by item 1?
Title: Re: My Game Engine is too Awesome
Post by: Nuke on May 01, 2012, 04:40:19 pm
if every object contains a list of everything that it is currently colliding with, it should be easy to go through all those objects' lists to identify groups of interacting objects. you would of course not traverse over anything that is immovable, getting all the objects that are touching the ground wouldn't help you any. the idea is to find systems of colliding objects so they can be collision responded to. you should know whats colliding with what and where by now. its probibly gonna be n^2 or worse, but if you isolate a subset of objects, then at least n will be smallish.

i figure from that point you would need to break the problem down. you might want to use the object with the most collisions as your main object. most of the objects in the group will likely just have a single collision logged. and there may or may not be intermediate objects in the mix as well. so build a collision hierarchy with your most hit object as the root and the one hitters as the leafs. propagate ke through from leaf to root and back again.

objects in firm contact with eachother (multiple colliding points spaced out about a cg and mostly perpendicular to the velocity), and at very low relative velocity may be considered a single object with combined mass, and forces. if another object hits one of them you might (depending on force vector in relation to the objects' cgs) get some energy transfer through this kind of thing. object a hits object b which is in (firm) contact with object c. so the force applied to b will actually get distributed to both b and c objects by some ratio (massA:massB). if a is bouncy, you may also dump some of the ke back into object a.

you also might step ahead in simulation time by one unit (or one frame), retest the group for collisions, and if any occur, you can compare the points with the previous set and fudge the difference, step back to current time and apply it. theres probibly some 4-d crap you can do here that makes my brain hurt to even think about it.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on May 01, 2012, 05:57:44 pm
@Tomo & z64555: Inelastic collisions with arbitrary CoR, and friction. Maybe I'll omit the friction at this stage if it seems like it's too complicated with it.

@Tomo: No, I don't think I can assume anything like that. Yes, the ground is immobile. And I plan to make it possible for things to "sleep" when they get within some threshold of stationary... eventually.

@z64555: Yes, the collisions will go on forever. When an object falls and hits the ground, it should eventually come to rest.




A little more info about the problem... here's what a contact point looks like:

Code: [Select]
struct ContactPoint
{
struct Part
{
RigidBody* obj;
Vec3 pos, norm; // both are world coords

Part() : obj(NULL), pos(), norm() { }
} a, b;
};

For every ContactPoint, my algorithm will have to come up with a Vec3 impulse, which will be applied equally and oppositely to the two objects in contact (unless one of them is immobile). The impulse could hypothetically be decomposed into a component parallel to the contact point's normal vector (restitution) and a component orthogonal to it (friction).




And rather than waste more time explaining with words what my code is doing, I'll explain with code. This is the DoCollisionResponse function:

Code: [Select]
void PhysicsWorld::Imp::DoCollisionResponse(const ContactPoint& cp)
{
RigidBody* ibody = cp.a.obj;
RigidBody* jbody = cp.b.obj;

RigidBody::Imp* iimp = ibody->imp;
RigidBody::Imp* jimp = jbody->imp;

bool j_can_move = jimp->can_move;

float m1 = iimp->mass_info.mass;
float m2 = jimp->mass_info.mass;

if(m1 + m2 > 0)
{
Vec3 i_poi = ibody->GetInvTransform().TransformVec3(cp.a.pos, 1.0f);
Vec3 j_poi = jbody->GetInvTransform().TransformVec3(cp.b.pos, 1.0f);

Vec3 i_v = iimp->GetLocalVelocity(cp.a.pos);
Vec3 j_v = jimp->GetLocalVelocity(cp.b.pos);

Vec3 dv = j_v - i_v;
const Vec3& normal = Vec3::Normalize(cp.a.norm - cp.b.norm);

float nvdot = Vec3::Dot(normal, dv);
if(nvdot < 0.0f)
{
float A, B;
GetUseMass(normal, cp, A, B);

float use_mass = 1.0f / A;
float bounciness = iimp->bounciness * jimp->bounciness;
float impulse_mag = -(1.0f + bounciness) * B * use_mass;

if(impulse_mag < 0)
{
Vec3 impulse = normal * impulse_mag;

if(impulse.ComputeMagnitudeSquared() != 0)
{
ibody->ApplyImpulse(impulse, i_poi);
if(j_can_move)
jbody->ApplyImpulse(-impulse, j_poi);
}

float sfric_coeff = iimp->friction * jimp->friction;
float kfric_coeff = 0.9f * sfric_coeff;

Vec3 t_dv = dv - normal * nvdot;
float t_dv_magsq = t_dv.ComputeMagnitudeSquared();

if(t_dv_magsq > 0.001f) // object is moving; apply kinetic friction
{
float t_dv_mag = sqrtf(t_dv_magsq);

GetUseMass(t_dv / t_dv_mag, cp, A, B);
use_mass = 1.0f / A;

Vec3 fric_impulse = t_dv * min(use_mass, fabs(impulse_mag * kfric_coeff / t_dv_mag));

ibody->ApplyImpulse(fric_impulse, i_poi);
if(j_can_move)
jbody->ApplyImpulse(-fric_impulse, j_poi);
}
else // object isn't moving; apply static friction
{
Vec3 df = jimp->applied_force - iimp->applied_force;
float nfdot = Vec3::Dot(normal, df);

Vec3 t_df = df - normal * nfdot;
float t_df_mag = t_df.ComputeMagnitude();

float fric_i_mag = min(impulse_mag * sfric_coeff, t_df_mag);
if(fric_i_mag > 0)
{
Vec3 fric_impulse = t_df * (-fric_i_mag / t_df_mag);

ibody->ApplyImpulse(fric_impulse, i_poi);
if(j_can_move)
jbody->ApplyImpulse(-fric_impulse, j_poi);
}
}
}
}
}
}

Some explanation of a couple of those other functions:

void ApplyImpulse(Vec3 impulse, Vec3 position); "Impulse" is the impulse to be applied, i.e. the change in linear velocity will be this vector divided by the mass. "Position" is the position where I'm applying the impulse (not necessarily on an axis passing through the CoM).

void GetUseMass(Vec3 direction, ContactPoint cp, float& A, float& B); Could possibly use a better name; it's for preparing the inputs to ApplyImpulse. "Direction" is the direction of the impulse I want to apply, and "cp" is used for its position relative to the CoMs. After the function completes, "A" and "B" contain values such that the magnitude of the impulse I need to apply is -(1.0f + bounciness) * B / A. If "bounciness" is one, the collision is perfectly ellastic. If "bounciness" is zero, it is perfectly inelastic (I think).




@Nuke: I've already come up with something to deal with the immobility of the ground... when there's a ContactPoint between a mobile body and an immobile one, instead of reusing the same node for all ContactPoints that immobile RigidBody has, I give that particular Edge a NULL other_node pointer.

Code: [Select]
struct Edge
{
ContactPoint* cp;
ContactPoint::Part* self;
ContactPoint::Part* other;

Node* other_node;
};

struct Node
{
RigidBody* body;
vector<Edge> edges;
};




Edit: @z64555: by
Quote
Done correctly, after all the impulses are applied, no contact point should have an "inward" relative local velocity.
I mean that if I were to evaluate nvdot (from DoCollisionResponse) again for all of the ContactPoints, it wouldn't be negative for any of them.



Edit II: Well that was easier to solve than I expected.

My old code:
Code: [Select]
for(vector<ContactPoint*>::iterator iter = collision_graph.contact_points.begin(); iter != collision_graph.contact_points.end(); ++iter)
DoCollisionResponse(**iter);

My new code:
Code: [Select]
for(int i = 0; i < MAX_SEQUENTIAL_SOLVER_ITERATIONS; ++i)
{
bool any = false;
for(vector<ContactPoint*>::iterator iter = collision_graph.contact_points.begin(); iter != collision_graph.contact_points.end(); ++iter)
if(DoCollisionResponse(**iter))
any = true;

if(!any)
break;
}

Also DoCollisionResponse now returns a bool, true if nvdot was < 0, false otherwise.

And now it works. Mostly.
Title: Re: My Game Engine is too Awesome
Post by: z64555 on May 01, 2012, 11:03:05 pm
Interesting trick there:
Code: [Select]
float t_dv_magsq = t_dv.ComputeMagnitudeSquared();

if(t_dv_magsq > 0.001f) // object is moving; apply kinetic friction
{
float t_dv_mag = sqrtf(t_dv_magsq);
// ...
}
else // object isn't moving; apply static friction
{
// ...
}

You not only use t_dv_magsq to determine if it's moving or not, but you also use it to determine the non-negative magnitude. What's wrong with using this?

Code: [Select]
float t_dv_mag = t_dv.ComputeMagnitude();

if(t_dv_mag != 0.001f) // object is moving; apply kinetic friction
{
// float t_dv_mag = sqrtf(t_dv_magsq);
// ...
}
else // object isn't moving; apply static friction
{
// ...
}

Are you planning on doing some KE calculations further down the road?

Quote
Quote
Done correctly, after all the impulses are applied, no contact point should have an "inward" relative local velocity.
I mean that if I were to evaluate nvdot (from DoCollisionResponse) again for all of the ContactPoints, it wouldn't be negative for any of them.

Still not quite following. Don't worry though, I'll figure it out once the coffee machine is fixed. :)
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on May 15, 2012, 04:43:10 pm
Progress Update!

I've gone back to working on my destructible terrain stuff, which I'll hopefully be able to integrate into the FPS engine in the not-too-distant future!

Here's some screenshots of the new multi-material feature:

(http://i93.photobucket.com/albums/l77/Aardwolf001/Quick%20Illustrations/screenshot-2012-4-13-16-3-30.png)
(http://i93.photobucket.com/albums/l77/Aardwolf001/Quick%20Illustrations/screenshot-2012-4-13-16-4-18.png)
Ignore the weird artifacts most prominently visible around the sandy patches, that issue has been fixed since I took these screenshots. Also I notice the filenames coming from my screenshot grabber are all a month off.

Next on the agenda: Terrain LODs!





Delayed response to z64555:

That's to save doing a square root. Although the function is named "compute magnitude squared", it's not actually taking the square root and then squaring it. Implementation:

   float Vec3::ComputeMagnitudeSquared() const { return x * x + y * y + z * z; }
   float Vec3::ComputeMagnitude() const { return sqrt(x * x + y * y + z * z); }


But anyway I've got that part working now.
Title: Re: My Game Engine is too Awesome
Post by: CommanderDJ on May 18, 2012, 09:18:22 am
Hey Aardwolf, sorry to (kinda) derail the thread a bit, but I've been following your progress and for a long time have been considering working on my own game engine. The main problem I keep coming across when I start seriously thinking about it is that there's just so much to do. How did you... start? If you don't mind me asking, that is.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on May 18, 2012, 03:31:16 pm
How did I start with this particular engine, or did I start on the game programming path? Assuming the prior...

First steps I took:
Title: Re: My Game Engine is too Awesome
Post by: Nuke on May 26, 2012, 07:01:49 pm
im still at step 4.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on June 04, 2012, 12:57:58 pm
Yesterday I re-did the "drop 2100 rigid bodies onto terrain, with no collisions between them" experiment again with my new engine. Under comparable circumstances in Bullet it got 3 fps, and in my engine a month or so ago it got 20-30 fps (although that was with spheres instead of MultiSphereShapes). Yesterday's experiment got 2 fps. :banghead:

This comes after refactoring my PhysicsWorld class, so that what it used to do is now covered by a PhysicsRegion class, of which PhysicsWorld contains multiple instances. Basically a step toward whole-world spatial partitioning.

Anyway, profiler says it's malloc's fault. I reckon I'll have to go back and do some actual design/engineering to clear up this mess.  :sigh:
Title: Re: My Game Engine is too Awesome
Post by: Tomo on June 04, 2012, 01:59:51 pm
I can well believe it's malloc's fault. The usual mallocs really fall to bits once you start fragmenting memory.

You'll need to profile where the mallocs are coming from - pointless object creation is a very common cause.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on June 04, 2012, 03:13:13 pm
When I said "it's malloc's fault" what I really mean is that according to the profiler I'm using says it's the function with the highest 'total' (i.e. self + children). I think it's probably the memory allocations involved in adding elements to a boost::unordered_set, but really I just need to rethink the problem some.




On the subject of profilers, I've been using AMD CodeAnalyst, and I'm getting rather annoyed with it for a number of reasons:

Really it would be nice if it would record the full call stack, all the way up to main or threadstart for every call stack sample. From what I can tell what Maybe it's going all the way back up to main, but the data it gives me seems to be solely based on the immediate next function down on the stack.



So for example if I were to profile this code...
Code: [Select]
void Eggs() { cout << "Eggs" << endl; }

void Ham() { cout << "Ham" << endl; }

void Seuss(bool eggs)
{
for(int i = 0; i < 10000; ++i)
if(eggs)
Eggs();
else
{
Ham();
Ham();
}
}

void Derp() { Seuss(true); }
void Herp() { Seuss(false); }

int main()
{
Derp();
Herp();

return 0;
}



CodeAnalyst might give me this:

function            self   children   total
main0300301
-      Derp1100101
      Herp1199200
Eggs99099
Ham1980198
Derp1100101
-      Seuss199100
Herp1199200
-      Seuss1198199
Seuss2297299
-      Eggs99099
-      Ham1980198



That much is ok (although I'm not sure CodeAnalyst even does that quite right), but the problem is that if I expand the item Seuss under Herp, it gives me this:

function            self   children   total
Derp1100101
-      Seuss199100
      -      Eggs99099
      -      Ham1980198



That is, it just tells me the info for Seuss in general, instead of specific to when it's being called by Derp... here's how I reckon it ought to look:

function            self   children   total
Derp1100101
-      Seuss199100
      -      Eggs99099




If anyone can suggest for me a better C++ profiler, please do.
Title: Re: My Game Engine is too Awesome
Post by: m!m on June 04, 2012, 04:06:21 pm
The Microsoft profiler does a quite good job but I think it isn't included in the express version so you would need to use one of the expensive versions or for some time you could use the Visual Studio 2012 Release Candidate (http://www.microsoft.com/visualstudio/11/en-us/downloads) which is AFAIK currently available for free until the final release is available so you could use that.
I'm not sure how you're handling the build process but from my (short) experiences it's definitely worth the effort of setting up the build environment.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on June 06, 2012, 06:34:31 pm
Well I'm already using MSVC++ as my IDE... but I'm a cheapskate and I want a more permanent solution than that.

In other news, I learned yet another reason to hate AMD CodeAnalyst:

The symbols it displays aren't saved with the saved session data; it loads them from the executable. I have 15 saved sessions which I just discovered are full of rubbish because it's trying to load the symbols from the current executable, instead of having saved what they were when it initially recorded the data.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on June 18, 2012, 01:58:26 pm
I got ragdoll physics working, sort of! :D So far it's all just simple ball-and-socket joints, with no limitations on how far they can rotate. For what it's supposed to be doing it looks passable; occasionally the bones separate far enough for it to look bad, but I think that's something I can worry about later.

For now, it seems as if I'm going to have to redo the multisphere-multisphere collision detection, because that's where it's taking too long currently. I reckon it shouldn't be hard to do better than 512x(between 3 and 8 vector operations, and 1 to 2 array lookups), right? Because that's what my current solution is. After a little over a month of trying to come up with an analytical solution, I came up with this numerical solution in a single day, and got it mostly working. But it's no longer fast enough for my needs :(

So now I'm trying to come up with a better way to detect whether two multispheres are intersecting, and if they are, to pick a normal vector and center point for the collision. Recall, when I say "multisphere" here I mean "the minimum convex shape which encloses a collection of spheres, not necessarily of equal size", i.e. a bunch of balls in shrink-wrap.

Apparently one fairly common technique is to see if you can prove that they aren't intersecting... i.e. if there exists some plane such that one object is completely on one side of the plane, and the other object is completely on the other side, then they are non-intersecting. And there are ways to come up with a finite set of planes to test, so that if none of the planes in this finite set divide the objects, then no such planes exist. This is what I'm working on now.

There's also something called the Separating Axis Theorem which is a more specific formulation of this, which might be able to get me a normal vector and center point as well.
Title: Re: My Game Engine is too Awesome
Post by: z64555 on July 31, 2012, 02:24:49 pm
Throwing neural nets at my program and hoping it makes it work. So far nothing.

Alright dude, what's going on?
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on July 31, 2012, 09:44:48 pm
Throwing neural nets at my program and hoping it makes it work. So far nothing.

Alright dude, what's going on?

Haha, I was just about to post in here :D



What's been going on since my last post:

The big task for a while now has been getting the character animation and the physics to play nicely together.

I've created a JointConstraint class which does a fairly good job of keeping the same point in two objects together, and can also apply torques to keep them oriented a certain way relative to one another. And I recently added limits on how far it can rotate on each axis. My Doods are held together by these.

So what I've been working on recently is telling the joints what orientations to be in in order to achieve certain tasks... tasks like walking, turning in place, or just not falling over. This is where I'm stuck. If the Dood starts out in its rest pose it will stay upright, but if I try to make him do anything, he falls over.



Here's where neural nets come in:

I was hoping I could train a neural net to operate the leg joints for me. The inputs would be the states of each bone/joint in some form, and the outputs would be the orientations for each joint ... or changes in orientation, or whatever. If I get this working, it would be my first successful attempt to use neural nets.

I've made a NeuralNet struct which basically just stores a matrix. I multiply by the inputs to get the outputs, and then do something like f(x) = x / sqrt(1 + x*x) to keep the range between -1 and 1.  Right now I'm using genetic algorithms to make it "learn", but it's not working very well... if it keeps failing, maybe I will get off my butt and look up how to do back-propagation on the Internets.

In the meantime, I've been trying to simplify the inputs and outputs. I'm thinking about changing stuff to have the following inputs (which is slightly less than what I have now)...


Depending how I set things up, that's anywhere between 65 and 90 inputs. From these inputs, it would determine the orientations for each of those joints. That's 3 degrees of freedom for 5 joints (2 ankles, 2 hips, an the base of the spine), plus 1 degree of freedom for each knee, = 17 outputs. For comparison, the setup I have now has 125 inputs and 21 outputs.

Then I would score the neural net based on how well it kept the placed feet in place, got the moving feet to their destinations at the right time, and with the right amount of average velocity left over. And managed not to fall over.



But I'm probably doing this all wrong :(
Title: Re: My Game Engine is too Awesome
Post by: z64555 on August 01, 2012, 01:55:44 am
Eh, I'm going to have to get back to you on this one. I don't believe neural net's are needed in the application, but I think they'd be fun to play with. Generation training may work well if you can define a criteria to test each generation up against, and then have the program run it for a long while...

During your training/creation of a control system for the legs, make a simplified Dood that has only one spine bone with nothing above it, and have the center of mass at the end of that bone.

Seriously consider using quaternions for the math, back-propagation of linked rotations with them is fantastically easy compared to traditional matrices.

Can you post a pick of the skeleton of one of your dudes?

I'll think about it tomorrow and will edit this post or post anew if necessary.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on August 01, 2012, 11:24:35 am
I'm not confident neural nets will help either  :blah:

I've been trying to simplify the problem by only considering the state of the bones from the pelvis down, or possibly including the first bone of the torso, and only affecting the same joints. But I don't think I get away with removing the load of the torso, arms, and head entirely. For now they're just locked in a rigid pose.

I'm already using Quaternions to store the orientations of each bone.

What I would have done is select a "solution" (basically an array of floats, for the 17 degrees of freedom I mentioned earlier) that would best get it from its current state to the desired state. The problem is that I can't tell what the effect of any particular solution would be without fully simulating it for whatever amount of time. Then again, maybe I could simulate just a little bit, to get a sense of what's moving fastest toward the desired state?

I also thought about using a neural net to predict the outcome of a solution... having a neural net which, once trained, would take the current state + a solution as inputs, and would return info about how the simulation would respond to that. And from a conversation I had yesterday, it sounds like neural nets would be better suited to this problem anyway.
Title: Re: My Game Engine is too Awesome
Post by: z64555 on August 01, 2012, 01:46:44 pm
Then again, maybe I could simulate just a little bit, to get a sense of what's moving fastest toward the desired state?

That, and perhaps make an interactive interface where you can control the position of either foot at any given time... so you could position one foot anywhere you want it and see if your current algorithm can keep your Dood balanced.

Of course, there's the old fashioned way of doing it: turn off physics on Actor's and have them run through keyframe animations.  :nervous:
Title: Re: My Game Engine is too Awesome
Post by: Nuke on August 01, 2012, 05:14:40 pm
time to break out the pid algorithms.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on August 01, 2012, 05:48:32 pm
I'm going to try to implement that idea I mentioned about training a neural net to predict the outcomes of certain outputs. And if that works well, maybe I can even train a neural net to skip that step and jut pick the best outputs. Learning how to do backpropagation now. Apparently this thing I'm making is called a Multilayer Perceptron (http://en.wikipedia.org/wiki/Multilayer_perceptron)  :nod:.

I reckon neural nets will probably be useful for something, even if it doesn't turn out to be this.  :blah:



Of course, there's the old fashioned way of doing it: turn off physics on Actor's and have them run through keyframe animations.  :nervous:

There are a few things that are making me want to avoid that. For example, I want my bullet-dood collisions to be better than ray-AABB. Also, some of the enemies are going to be big enough that they'll have to do per-bone collision with the player. And also just for the sake of awesome.
Title: Re: My Game Engine is too Awesome
Post by: Nuke on August 01, 2012, 06:51:31 pm
problem with neural nets is you got to keep em running, even if you are not using them. i kinda want to see a neural net on chip type processor which does the heavy lifting for you. it would be subdivided into cells, much like an fpga, except instead of being a 1-bit adder/flipflop, it would be a virtual neuron matrix. you could join or divide cells based on the number of independent ais you need, i/o requirements, etc. joining cells makes smarter ais, for robotics applications, divided cells are probibly more suited to games where you need to simulate multiple intelligences. the main advantage is that the chip can run a much higher clock rate than your cpu, since error is tolerable in this application. it would be capable of thinking independent of any command from the cpu, and you only need to bother it when you need to provide stimuli or receive output. main commands would be load matrix, dump matrix, configure, stimulus (input), and reaction (output). the load and dump features would probibly require the device to be digital so that you can save the state of the neural net. but otherwise an analog or mixed device would be preferable. you might be able to do rapid training in software with a teaching program. id really like to see this kind of neural net accelerator.
Title: Re: My Game Engine is too Awesome
Post by: Thaeris on August 01, 2012, 08:00:15 pm
Aardwolf, would it be possible to make a simulation that used the neural network, and then take the output of the simulation and use that as your "locomotion code"? This would allow you to avoid having the network run continually while the game progresses. Applying different code sections to movement depending on the environment ideally would allow for good performance over a wide variety landscapes while minimizing computational draws from the network code, or so I would assume.
Title: Re: My Game Engine is too Awesome
Post by: Tomo on August 02, 2012, 11:38:21 am
I kinda want to see a neural net on chip type processor which does the heavy lifting for you.
GPGPU can do that, and relatively easily - inputs and outputs are textures and/or meshes, and a shader does the computations.

GPUs are massively parallel which suit neural nets very well (unlike some other computations)

Integer computations are a pain, but you don't want those for neural nets anyway.
Title: Re: My Game Engine is too Awesome
Post by: z64555 on August 02, 2012, 12:13:10 pm
Integer computations are a pain, but you don't want those for neural nets anyway.

Huh, what?
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on August 02, 2012, 02:56:56 pm
Idunno where this "you got to keep em running" idea is coming from, but it doesn't sound like it pertains to MLPs (http://en.wikipedia.org/wiki/Multilayer_perceptron) in the slightest. Not sure what integer maths has to do with anything either  :wtf:




Anyway, I've been rethinking the problem on various levels...


If I stick with per-bone physics for everything...

Revising and rephrasing the problem, the inputs are:

From that, I need to come up with poses (relative orientations) for each joint to move toward, so that they reach that pose at the specified time.

The range of possible positions/orientations for the pelvis in order to achieve an acceptable CoM is somwhat constrained; it has to be within a certain horizontal area in order to keep the CoM balanced, and it has to be at a proper elevation so that both feet can reach it*. The problem is that I'll need to compensate for the torques applied at each joint, and I don't really know how to do that.


Or I could just fake it...

I could do per-bone collisions for bullets colliding with anything, and use a simplified shape for collisions between doods and the environment, or collisions between small objects and larger doods (e.g. for the player vs. an artillery bug; the player would use a simplified shape). I would still need IK or something to make sure feet didn't go through the terrain, even if there's no actual physics backing it up.





*Assume that I won't tell it to put the two feet impossibly far apart.


Edit: I just realized something! If I constrain the placed foot to be immobile w.r.t. the ground, I don't have to worry about any net torques or linear acceleration! Unless of course the thing he's standing on isn't immobile, but whatever; this should be good enough. I'm going to try to implement this.
Title: Re: My Game Engine is too Awesome
Post by: z64555 on August 02, 2012, 06:04:11 pm
Edit: I just realized something! If I constrain the placed foot to be immobile w.r.t. the ground, I don't have to worry about any net torques or linear acceleration! Unless of course the thing he's standing on isn't immobile, but whatever; this should be good enough. I'm going to try to implement this.

That might work, to an extent, of course they'll come a time where you'll need to simulate static and kinetic friction.  :P
Title: Re: My Game Engine is too Awesome
Post by: Nuke on August 02, 2012, 07:21:23 pm
I kinda want to see a neural net on chip type processor which does the heavy lifting for you.
GPGPU can do that, and relatively easily - inputs and outputs are textures and/or meshes, and a shader does the computations.

GPUs are massively parallel which suit neural nets very well (unlike some other computations)

Integer computations are a pain, but you don't want those for neural nets anyway.

a purpose build simulated neuron (on a chip) can take up about the same amount of die space than a dram cell. so you could get a denser network that can run faster than anything you could simulate with an array of fpus. a simulated neural net can also only simulate one neuron at a time, so it would take several c/gpu cycles to run one think cycle. and brains dont work in cycles so much in the first place. all neurons operate simultaneously. a purpose built neural net on a chip can be more brain like and be more efficient than simulating the whole thing in software. not to say the gpu couldn't do it. just using an fpu to do the job is kind of like driving a finishing nail with a sledge hammer. to get the most out of a neural net you must abandon binary thinking all together and go pure analog. you want error, you want glitches, you want unpredictable permutations.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on August 02, 2012, 07:37:40 pm
Oh, I've already got friction. And hypothetically my code is set up to deal with either static or kinetic friction... but in practice, the branch for static friction never executes. Maybe I'll look into it sometime.  :blah:



In the meantime, I've got a performance issue that's tolerable now (when there's only one Dood) but may be a problem later...

Code: [Select]
// enforce joint rotation limits
const float inv_foresight = 360.0f;
const float foresight = 1.0f / inv_foresight;

Vec3 proposed_av = current_av - alpha; // proposed angular velocity
Quaternion proposed_ori = a_to_b * Quaternion::FromPYR(proposed_av.x * foresight, proposed_av.y * foresight, proposed_av.z * foresight); // orientation that would result from that velocity; a_to_b is a quat
Vec3 proposed_pyr = oriented_axes * -proposed_ori.ToPYR(); // rotation in the coordinate system the rotation limits are defined in; oriented_axes is a Mat3

bool any_changes = false;
if(proposed_pyr.x < min_extents.x) { proposed_pyr.x = min_extents.x; any_changes = true; }
else if(proposed_pyr.x > max_extents.x) { proposed_pyr.x = max_extents.x; any_changes = true; }
if(proposed_pyr.y < min_extents.y) { proposed_pyr.y = min_extents.y; any_changes = true; }
else if(proposed_pyr.y > max_extents.y) { proposed_pyr.y = max_extents.y; any_changes = true; }
if(proposed_pyr.z < min_extents.z) { proposed_pyr.z = min_extents.z; any_changes = true; }
else if(proposed_pyr.z > max_extents.z) { proposed_pyr.z = max_extents.z; any_changes = true; }

if(any_changes)
{
// at least one rotation limit was violated, so we must recompute alpha
Vec3 actual_pyr = reverse_oriented_axes * proposed_pyr; // comparable to -proposed_ori.ToPYR(); reverse_oriented_axes is a Mat3
Quaternion actual_ori = Quaternion::FromPYR(-actual_pyr); // comparable to proposed_ori
Vec3 actual_av = (b_to_a * actual_ori).ToPYR() * inv_foresight; // comparable to proposed_av

alpha = current_av - actual_av;
}

This gets called a bunch of times every tick of the simulation with many of the variables unchanged. I've tried to compute-once-and-reuse as much as possible, but there's still a lot of computation going on here.

Explanation of a few functions:

Quaternion::FromPYR - returns a quaternion representing a rotation; param vector's direction = axis of rotation, and magnitude = angle of rotation in radians
Quaternion::ToPYR - inverse of the above; Quaternion::FromPYR(vec).ToPYR() will return vec as long as the magnitude of vec is less than pi.

Oh, and the comments about what data type some things are were added just for this excerpt.



So yeah, how can I make this faster?
Title: Re: My Game Engine is too Awesome
Post by: z64555 on August 02, 2012, 08:23:19 pm
Oh, I've already got friction. And hypothetically my code is set up to deal with either static or kinetic friction... but in practice, the branch for static friction never executes. Maybe I'll look into it sometime.  :blah:

I actually had a code snippet for you... but it escaped me at the moment.  :wtf:



eh... There's no way you can optimize the bounds checks... but if many of the variables are unchanged, you may be able to add a previous_state and check those first before you do the bounds checks.
Title: Re: My Game Engine is too Awesome
Post by: Tomo on August 03, 2012, 11:12:45 am
Integer computations are a pain, but you don't want those for neural nets anyway.
Huh, what?
What I meant is that f you want to crunch a lot of floating-point numbers fast and can do it in parallel, the GPU is usually the best place to do it.

However, GPUs are optimised for floating-point, so the same is probably not true for integer calcs.
Title: Re: My Game Engine is too Awesome
Post by: z64555 on August 03, 2012, 12:21:25 pm
Integer computations are a pain, but you don't want those for neural nets anyway.
Huh, what?
What I meant is that f you want to crunch a lot of floating-point numbers fast and can do it in parallel, the GPU is usually the best place to do it.

However, GPUs are optimised for floating-point, so the same is probably not true for integer calcs.

That really depends on the GPU themselves, I've read somewhere that nVidia's Fermi architecture can handle both 32-bit int's and floats easily.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on August 04, 2012, 05:58:55 pm
Well, I discovered and fixed a major bug with the joint constraint rotation limits --- apparently the oriented_axes matrix was wrong, and it resulted in some crazy whip-like motion.



Unfortunately when I re-enabled enemies (20 of them) the game ran at a craptastic 2 frames a second.

Big-picture pseudocode/outline of my how my physics is set up, relevant to question below:
Code: [Select]
execute at PHYSICS_TICK_FREQUENCY hz:
begin populating a "constraint graph"; a graph where nodes = rigid bodies and edges = physics constraints

do collision detection; contact points get added to constraint graph
add other less transient constraints (e.g. joint & placed foot constraints) to the constraint graph

break the constraint graph into subgraphs (static objects don't merge subgraphs)
for each subgraph:
active_constraints = all the edges in that subgraph
repeat MAX_SEQUENTIAL_SOLVER_ITERATIONS times or until active_constraints is empty:
new_active_constraints = empty
for each constraint in active_constraints:
constraint does its thing
if it applies a nonzero force/torque/impulse/whatever:
add all the other edges from the two nodes this edge connected to new_active_constraints
active_constraints = new_active_constraints

So, the amount of work it has to do per second is proportional to PHYSICS_TICK_FREQUENCY * MAX_SEQUENTIAL_SOLVER_ITERATIONS. Recently I had upped PHYSICS_TICK_FREQUENCY from 60 to 360, but now that I'm having performance issues I've changed it back. I also recently increased MAX_SEQUENTIAL_SOLVER_ITERATIONS from something like 30 to 200, but for again performance reasons I can't keep that up.

Anyway, problem is that whenever there's anything more complicated than a single rigid body colliding with a surface, the algorithm doesn't converge fast enough; it ends up going to the full MAX_SEQUENTIAL_SOLVER_ITERATIONS. And most of the time, most or all of the constraints are active each of those 200 iterations. I've tried using a small nonzero threshold to decide whether to apply a force/torque/impulse/whatever (instead of zero) but it didn't seem to make much of a difference.

So my question now is: is there any way I can get this thing to converge faster? I'm open to some minor refactoring of how it tells constraints to do their thing, if it'll help.



Also, I'm working on the code to pick joint orientations to maintain balance given the position of the feet, etc... With 0 or 1 constrained feet, the solution space is basically an AABB in 3*(number of joints) dimensions. But if I constrain the second foot, that invalidates a huge chunk of my solution space. I could possibly do it by minimizing the difference between where one constraint says a bone should be and where the other one says it should be? I'm already planning on scoring configurations based on how well they keep the center of mass over the feet, keep the torso upright and oriented properly, etc., so maybe I could just incorporate "bone xform consistency" as another part of the scoring criteria?
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on August 19, 2012, 10:44:31 pm
I've given up on trying to solve this with "correct" physics, i.e. achieving balance/locomotion using friction between the feet and the ground. Now it cheats and applies a magical force/torque to each bone to make it conform to the desired pose. And it works.

One of the next things I need to do is set up the actual character animation stuff... and I'm revisiting the idea of neural nets!

The inputs would be:

From this it would output:

I would train it with examples of actual walking animations for walking on various surfaces. So it would learn to interpolate/extrapolate for other kinds of surfaces. The same setup would probably work just as well for the bugs' walk animation as for the player.




Anyway, I was confused by maths on http://en.wikipedia.org/wiki/Multilayer_perceptron but apparently it's a goddamn typo. Some idiot wrote:

         phi(yi) = tanh(vi)        and         phi(yi) = (1 + evi)-1

When I'm pretty sure it should have been:

         yi = phi(vi) = tanh(vi)        and         phi(vi) = (1 + evi)-1

But I'm not sure that's right, so I'm not going to edit it. Can someone confirm? Also, does what I'm doing make any sense / seem like a good idea?
Title: Re: My Game Engine is too Awesome
Post by: Mongoose on August 20, 2012, 02:40:35 am
I think you're right, since y is listed as representing the output value.
Title: Re: My Game Engine is too Awesome
Post by: z64555 on August 20, 2012, 03:22:53 am
Um... how is your neural network setup, btw? Do you have like a graph or map of all the nodes?

Seeing as NN's are "on the frontier of science," I'm going to get pretty confused very quickly unless you have some sort of map I can look at. :)
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on August 20, 2012, 01:06:36 pm
It's an MLP :D

Just a bunch of layers. Every node in one layer is connected to every node of the next layer (with a weight). And it's "feed-forward", i.e. one-directional. I haven't decided on how many nodes will be in each layer yet, though, or how many layers there will be.
Title: Re: My Game Engine is too Awesome
Post by: z64555 on August 20, 2012, 02:40:42 pm
Ok... Not entirely sure why Wikipedia uses tanh as the... activation function? (I prefer the term mapping function, b/c that's what it's actually doing). It could have something to do with neuron simulation rather than anything practical like with a fuzzy logic inference engine (FLIE).

The backpropagation formulae (http://en.wikipedia.org/wiki/Multilayer_perceptron#Learning_through_backpropagation) in Wikipedia appears to be right (at least from my experience), although I'm not entirely sure how your going to come up with an equation for dj(n) per node.

I mean, honestly, wtf? dj(n) is most likely vj, or a function thereof? Linear Time-Invarient systems have a desired input, X(s), and an output, Y(s), and typically consists of a controller/compensator in series with a system/plant that it is controlling. Y(s) is the direct output of the plant, and the controller/compensator (usually a PID or something similar) does it's best to make Y(s) match X(s). Whereby, in this sense, dj(n) is analogous of X(s).

...but this is not a LTI system, nor is there a system or plant to be compensated right at that node... it's just the node itself.  :confused:
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on August 20, 2012, 03:48:42 pm
Since it seems like you're not getting it, here's a brief overview of how the MLP would function after it's trained:
Code: [Select]
A = the input layer
Do
{
        B = the next layer after A in the MLP
        For each node J in layer B:
                total = 0
                For each node K in layer A:
                        total += weight[J, K] * value[K]
                value[J] = ActivationFunction(total)
        A = B
} until A is the output layer

Or are you just confused by the particular choice of tanh? It has easy-ish derivatives and ranges from -1 to 1, what's not to like?


Anyway, you train it by giving it inputs and the correct outputs that go with them... dj(n) is the "correct" value for the jth output node when given the nth set of inputs. It's only applicable to the output layer, and you have to know what the correct outputs are in order to do any of this.




Meanwhile, I'm making progress on implementing this. I've just gotta figure out these partial derivatives, and then code up the solution and a few other code thingies, and then test it on something simple.
Title: Re: My Game Engine is too Awesome
Post by: z64555 on August 20, 2012, 08:37:00 pm
Alright, I figured out what was bothering me about that page.

The wiki page says that dj( n ) is the desired output from node j, and yj( n ) is the actual output from that same node... however, it doesn't make any sense to get a value directly from the output of the node, because it's not applied directly to whatever system it's supposed to be controlling. This is like auto-tuning a PID controller to an arbitrary value before even attaching the system it's supposed to be controlling.

Now, going back to animations... it might make sense if dj( n ) was known via an animation frame. I don't know if the NN will interpolate between frames correctly, however, because the sequence of placing one foot in front of another is important.

I also don't think your current input/output set will work for inclines, but I guess we'll see what happens. ;)
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on August 22, 2012, 04:43:11 pm
@z64555: as I said, you have to know what the correct outputs are in order to do any of this. I give it a set of inputs and the correct outputs that go with it, and it learns. Speaking of which...

void MultiLayerPerceptron::Train(float* inputs, float* correct_outputs, float learning_rate); :D


I implemented something! I've been testing it to verify that the method works as intended... and it doesn't. It sometimes kinda works, but there's definitely something wrong with my implementation, and I don't know what. :(

Example test scenario:

Given this:

        float x = Random3D::Rand(-0.75f, 0.75f);
        float inputs[] = { x, 1 };

I am training it to compute this:

        2.0f * x * x - 0.25f


The error almost always decreases initially, and sometimes it will gradually converge to some fairly small value (e.g. starting at 0.6, getting as low 0.04), but other times it will be stupid and increase. And I'm not talking about a small increase between two trials (i.e. what you might expect if the learning rate were too high); I'm talking about the average over 50-trial intervals gradually increasing from something almost-decent like 0.1 up to something horrible like 0.7.



I'll continue to work on this, and maybe post pseudocode/code if I can't make any progress on my own.







Update/Edit!
Yay, I fixed it.  :D It was something stupid. I had a loop which repeated as many times as there were inputs, when it should have repeated as many times as there were outputs.

Edit II: Never mind it's still broken.









Edit III:
Ok, there are 2 things I'm not sure about.





1 I can't just put this inline because it breaks the [list] tags:

Code: [Select]
    Initialize the weights in the network (often randomly)
    Do

        For each example e in the training set

            O = neural-net-output(network, e) ; forward pass
            T = teacher output for e
            Calculate error (T - O) at the output units
            Compute delta_wh for all weights from hidden layer to output layer ; backward pass
            Compute delta_wi for all weights from input layer to hidden layer ; backward pass continued
            Update the weights in the network

    Until all examples classified correctly or stopping criterion satisfied
    Return the network
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on September 10, 2012, 11:58:53 am
Ok, I seriously need to figure out this profiler nonsense. For more info on what sort of bull**** I've had to deal with, look at some of my previous posts in this thread. :banghead:

I either need a better profiler, or changed build options.



What I've tried:

I've been using AMD CodeAnalyst. I've tried a few other free profilers, and all of them had the same problems CodeAnalyst had, with worse interfaces.

I've tried changing some build options, but I haven't managed to get the problems to go away... at least, not without making the simulation run at a snail's pace (i.e. unplayable). And I don't remember whether that actually helped with the profiler output  :doubt:



Possible leads?

I'm wondering if it might have something to do with multithreading. There's really only one part of my program that's multi-threaded, and that's the loading screen... it's multi-threaded so that the GUI doesn't lock up while stuff is loading. I suppose OpenAL is also doing its stuff in its own thread (or its own process?).

Also there's the Lua scripting. I imagine that if the profiler tries to examine the call stack when its going from my code through a Lua script and back into my code, it might not be quite accurate... but that just doesn't seem like it could account for the level of bull**** I'm encountering.



Build options stuff:

I'm using MSVC++ Express 2010. My solution is set up with a static library and a handful of executables that are linked with it (e.g. the FPS, and a test program for the destructible terrain). So when I'm making changes I've got two projects' settings to deal with. I've tried disabling various optimization options (albeit not very scientifically), but to no avail.

Things that didn't do it, at least individually or in the combinations I tried them:






Help!
Title: Re: My Game Engine is too Awesome
Post by: z64555 on September 10, 2012, 03:44:56 pm
Do you have some sort of 3rd party utility that you can use to monitor each core's usage?

If you program is indeed using only a one or two cores, then the utility should be able to show it.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on September 10, 2012, 07:10:19 pm
:confused: It only ever uses 50% of my CPU, i.e. one of the two cores.

There's only one "big" thread running when the profiler is active. The only time I explicitly create another thread is the loading screen, and I only unpause the profiler after the loading screen is finished and the game has started. How could a thread which has already finished be causing problems? Or do you think it's some thread I didn't explicitly create, e.g. if OpenAL decided to create a thread?
Title: Re: My Game Engine is too Awesome
Post by: z64555 on September 10, 2012, 08:07:43 pm
Well I mean when your game engine is running by itself, and with the profile inactive. If the profiler's forcing everything to be in a single thread, that could be a big contributer...
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on September 10, 2012, 08:37:01 pm
 :confused: :confused: :confused: I do not understand this "forcing everything to be in a single thread" business.

My program is mostly single threaded. That's how I set it up. I didn't tell my code to execute on multiple threads except in the loading screen, so it won't be executing on multiple threads. Maybe some code from some library (e.g. my go-to example: openal32.dll) might be running in a separate thread, but my code by design runs in a single thread.

Do you mean that maybe this profiler is too dumb to deal with a multi-threaded program, and is seeing stuff happening in multiple threads and recording the data wrong because it doesn't know about threads?
Title: Re: My Game Engine is too Awesome
Post by: z64555 on September 10, 2012, 08:47:46 pm
Do you mean that maybe this profiler is too dumb to deal with a multi-threaded program, and is seeing stuff happening in multiple threads and recording the data wrong because it doesn't know about threads?

Yep, that's what I mean.
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on September 10, 2012, 11:55:46 pm
Oh, durrr.  :P

Well, I've gone back and looked at the website for AMD CodeAnalyst, and it at least claims to be able to deal with multi-core applications. And considering all the other free profilers I tried had the same or similar bull****, I'm leaning toward it being something with my build options now.

I'll redo the experiment of seeing whether there's any similar bull**** in the debug build... if there isn't, that's progress. If there is, at least I'll know.



Edit: well, apparently there's much less bull**** with the debug build, but there's still some. A few examples:

sqrtf thinks it's calling CibraryEngine::Vec3::operator*=
malloc thinks it's calling boost::unordered_detail::hash_bucket<std::allocator<CibraryEngine::PhysicsConstraint *> >::hash_bucket<std::allocator<CibraryEngine::PhysicsConstraint *> >
CibraryEngine::AABB::AABB thinks it's calling std::allocator<boost::unordered_detail::hash_node<std::allocator<CibraryEngine::RigidBody *>,boost::unordered_detail::ungrouped> >::deallocate
RtlAllocateHeap thinks it's calling CibraryEngine::Octree<CibraryEngine::TriangleMeshShape::NodeData>::ForEach<CibraryEngine::TriangleMeshShape::RelevantTriangleGetter>



And then there's some stuff that I wouldn't quite call "bull****", but which I don't know what to make of. Low-level functions with names like ILT+34825(?_Isnil?$_Tree_valV?$_Tset_traitsPAVPhysicsRegionCibraryEngineU?$lessPAVPhysicsRegionCibraryEnginestdV?$allocatorPAVPhysicsRegionCibraryEngine

I'm getting weighed down by all this bull****... because I don't remember whether I saw that variety of gobbledygook in the release build or not.



Note, the debug build runs at < 1 fps (versus about 16 fps in release).
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on September 15, 2012, 04:12:21 pm
:bump:

I tried using the debugger's pause function and looking at the call stack (which should be sort of how the profiler works), and occasionally it comes up with similar kinds of bull****. Here's an example:

When I paused it, the bottommost things on the call stack were:

Code: [Select]
KeyframeAnimation::UpdatePose(TimingInfo)
free(void*)
_CIexp_pentium4()

In other words, bull****. So I used the debugger's "step out" function to see what was really calling that function, and eventually got to CrabBug::PoseCharacter (i.e. not bull****).



Conclusions: it's not a profiler issue, and evidently it's not a threading issue either...

Apparently that _CIexp_pentium4 function is SSE-related, so maybe that's worth looking into? Please advise!

Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on September 27, 2012, 07:00:47 pm
New gameplay video! (http://youtu.be/JNR5ohuOBHk)
Title: Re: My Game Engine is too Awesome
Post by: z64555 on September 27, 2012, 07:07:55 pm
Looking better!.  :yes:
Title: Re: My Game Engine is too Awesome
Post by: Aardwolf on October 11, 2012, 08:48:15 pm
So I'm still working on this...

I recently started on a sizable bit of refactoring. I've changed things so that rays (or point particles, whatever you want to call them) are no longer just RigidBody objects with a specific type of CollisionShape. Now instead there are two classes, RigidBody and RayCollider, which both extend a new class called DynamicsObject, which in turn extends CollisionObject.

Now I've moved on to the second half of the task, creating another subclass of CollisionObject called CollisionGroup class, which represents a bunch of rigid bodies that are confined within a small volume... the goal is to have a single item in the spatial partitioning system which stores all of the bones of a dood... since the doods are small compared to the cells of the grid, it should work out to be more efficient this way.

I'm just about done coding up the CollisionGroup class, and then it'll be time to make the game actually use it... and debug why it doesn't actually work. (Edit: I got it integrated and working :D)




In other news, I discovered something annoying about the protected keyword in C++ (which IIRC was different in C# and/or Java)...

If I have this:
Code: [Select]
class CollisionObject
{
     protected:
          virtual void DoStuff() { Debug("default behavior"); }
};

class RigidBody : public CollisionObject
{
     protected:
          void DoStuff() { Debug("overridden behavior"); }
};

class CollisionGroup : public CollisionObject
{
     protected:
          vector<RigidBody*> children;
          void DoStuff();                        // various attempted implementations below
};

Note, this is altered a bit from my actual code; I removed the intermediate DynamicsObject class for simplicity.


The following code doesn't compile; the compiler complains that CollisionObject::DoStuff is inaccessible, even though CollisionGroup is derived from CollisionObject!
Code: [Select]
void CollisionGroup::DoStuff()
{
     for(vector<RigidBody*>::iterator iter = children.begin(); iter != children.end(); ++iter)
          (*iter)->DoStuff();
}


This doesn't work either:
Code: [Select]
void CollisionGroup::DoStuff()
{
     for(vector<RigidBody*>::iterator iter = children.begin(); iter != children.end(); ++iter)
          ((CollisionObject*)*iter)->DoStuff();
}


There are two ways to make it work, and they both suck. One is to declare CollisionGroup as a friend class in CollisionObject... which is not a good solution, because it means I can't have additional classes that derive from CollisionObject and want to use their peer's DoStuff method, without modifying the declaration of CollisionObject.

The second way (which is what I'm doing now) is equally horrible:
Code: [Select]
void CollisionGroup::DoStuff()
{
     for(vector<RigidBody*>::iterator iter = children.begin(); iter != children.end(); ++iter)
          ((CollisionGroup*)*iter)->DoStuff();
}




I literally shuddered when that compiled successfully.
Title: Re: My Game Engine is too Slow
Post by: z64555 on October 18, 2012, 06:36:06 pm
That... shouldn't be the case. Derived classes are supposed to inherit every method and member, with the exception of the parent class's constructors/deconstructors.

If you have MSVC, try seeing what is accessible by using the autocomplete... basically just do the (*iter) -> and wait for MSVC to pop out a window with all possible options.

The compiler might be getting confused with all the DoStuff() functions. :P
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on October 19, 2012, 03:14:43 pm
No it shouldn't, but apparently it is. The issue is specifically that I can't access those protected members via a pointer or object... unless the pointer/object's type is the same as the "this" object. IIRC in C# and Java it works "right".

And I've been using MSVC this whole time.

Meanwhile, I downloaded the OpenCL SDK and am looking into using it to hardware-accelerate my "SolveConstraintGraph" function. And also collision detection, but I expect that will be straightforward.



Edit: Some pseudocode for the batcher...

Code: [Select]
given a collection of constraints A // all constraints (or all constraints yet to be added to a batch)

i = 0
while A is not empty

start an empty collection of nodes U // used nodes
start an empty collection of constraints N // constraints which will be processed by some other batch
start an empty collection of constraints B[i] // constraints for this batch

for each constraint C in A
if either of the two nodes of C are in U
add C to N
else
add C to B[i]
add both nodes to U

A = N

increment i

This will guarantee that every constraint gets processed exactly once... but what I think I want to be doing (and what I'm doing currently in my single-threaded pure-CPU implementation) is having each one process at least once, at most some number of times defined by a constant, and quitting early if nothing is "woken up". I think I can manage the first two parts, but I'm not sure I can do a "if nothing is woken up" check without having to pass the data back to the CPU after each batch.

The exact way "waking up" works is like this: when an edge (constraint) processes, if may or may not apply an impulse to the two nodes (rigid bodies) it connects... if it does, any adjacent edges are "awake" for the next iteration1... the edge which just processed may be woken up again by another edge, but it doesn't wake itself up.

Actually now that I think about it, the way I have it set up now might be waking edges up unnecessarily... if one edge wakes up its neighbors, but the neighbors process later in the same iteration, the neighbors can go back to sleep the next iteration. Then again, maybe doing more or less processing of constraints is irrelevant, since more often than not the reason it stops is because it hit the max number of iterations, rather than because the entire subgraph is asleep.




1Iteration as in "process all the constraints, repeatedly", not "process subsequent batches of constraints".
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on October 24, 2012, 02:09:16 pm
:bump:

I've multithreaded both the collision detection and the constraint graph solver! Now the physics is down to 20.8 milliseconds!



I'm thinking OpenGL transform feedback would be a very handy tool, and I should learn how to do it. I've had some code sitting in VertexBuffer.cpp for a while now which was based on an example I found somewhere, but it wasn't going anywhere... probably because I was trying to make something general, and I'm not ready yet. I need to do some prototyping and experimenting and stuff... make a specific thing that uses transform feedback, get it working, then adapt it. Then maybe eventually I can generalize from there.
Title: Re: My Game Engine is too Slow
Post by: z64555 on October 24, 2012, 02:18:27 pm
Awesome. What do you mean by the "OpenGL transform feedback?"
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on October 24, 2012, 04:06:35 pm
It's an extension that became part of core GL in version 3.0... Basically it lets me access the output of a vertex shader (before clipping). Also it lets me skip rasterization... so it's like a primitive compute shader.

Will update this post later with a code snippet I'm working on.

Edit: no code snippet, because it's not presentable. But I managed to get access to the outputs of the vertex shader from c++ :D
Title: Re: My Game Engine is too Slow
Post by: z64555 on November 05, 2012, 08:05:21 am
So now it's the OpenGL code that's giving you trouble? Snippets or it didn't happen! :P
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on November 10, 2012, 10:29:16 pm
Making progress now... I've got most of the "new" stuff taken care of!

I've got a HardwareAcceleratedComputation class, which I construct with a Shader, a map<string, string> to map the outputs of that shader to named members of a VertexBuffer, and a VertexBuffer which serves as a prototype for the output.

I also changed how I'm doing it, so now instead of trying to get the data off of the GPU after every operation, my VertexBuffer wrapper now has an UpdateDataFromGL method. And I disabled some stuff that used query objects to find out how many primitives the shader output, because I know for a fact it's going to output the same number of primitives as I gave it. So that made it faster, too.

But I still don't actually have the physics running on the GPU. I've got it mostly planned out, though. It looks like I'm going to be using what GLSL calls a samplerBuffer, which seems like it's the last "new" thing for me. Everything else is stuff I already know how to do.
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on November 12, 2012, 02:36:34 pm
Aughhh it's horribly un-working and I don't know why :( :( :(




Edit: now it's slightly less horribly un-working! Apparently some unnecessary-looking code which was part of an example I was working from was necessary after all. If I don't use an OpenGL query object to count how many primitives my vertex shader outputs, and then get the result from the query object, the GPU-side computations get borked somehow. So I put that part back in and now that's working again. :)

But now I'm having another problem. I'm using integer-typed vertex attributes, and for some reason the values the vertex shader is seeing aren't the same as the values I give it:
Code: [Select]
0x00000000 --> 0x00000000
0x00000001 --> 0x3F800000
0x00000002 --> 0x40000000
0x00000003 --> 0x40400000
0x00000004 --> 0x40800000
0x00000005 --> 0x40A00000
0x00000006 --> 0x40C00000
0x00000007 --> 0x40E00000
0x00000008 --> 0x41000000
0x00000009 --> 0x41100000
0x0000000A --> 0x41200000
0x0000000B --> 0x41300000
0x0000000C --> 0x41400000
0x0000000D --> 0x41500000
0x0000000E --> 0x41600000
0x0000000F --> 0x41700000
0x00000010 --> 0x41800000
0x00000011 --> 0x41880000
0x00000012 --> 0x41900000

Note, to get these values back I converted through float so there may be roundoff, but the numbers definitely are that big.

I can't tell what the pattern is, help :confused:

Edit II: I figured out what the pattern is! The numbers are being converted to float, then being read as int! (This is separate from the deliberate conversion I did to get them back out.)

I'm not sure why it's doing it, or how to fix it, but the workaround I came up with before I figured out the pattern is working for now: using float instead of int.
Title: Re: My Game Engine is too Slow
Post by: z64555 on November 13, 2012, 11:15:56 pm
Which OGL functions are you using? IIRC, many of them use GLfloat's...
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on November 14, 2012, 02:45:39 am
Hoo boy, there's a bunch. Let's see...


It's weird that it wasn't working, but I'm working around it and I'm getting closer and closer to doing the constraints on the GPU.

Right now I've got a not-quite-MassInfo struct in the constraint eval shader, which is being loaded from a texture. Also the texture has the correct data in it, and as far as I can tell it's being converted properly by the shader. Unlike my C++ struct which has a mass, a CoM, and a 3x3 matrix to store the MoI, the struct in the shader contains the inverse of the mass, the CoM (in world coords), and the inverse of the MoI matrix. But I called it MassInfo anyway  :blah:

Also I've made structs which contain all the other variables the constraints will need, and functions to load them from a specified starting texel of a buffer texture. But I haven't got the data put into that buffer yet. And then I'll still have to actually port the constraints' DoConstraintAction functions to GLSL.

But I'm close :D
Title: Re: My Game Engine is too Slow
Post by: Uchuujinsan on November 15, 2012, 09:45:42 am
That... shouldn't be the case. Derived classes are supposed to inherit every method and member, with the exception of the parent class's constructors/deconstructors.

If you have MSVC, try seeing what is accessible by using the autocomplete... basically just do the (*iter) -> and wait for MSVC to pop out a window with all possible options.

The compiler might be getting confused with all the DoStuff() functions. :P
Actually, it should be the case that this doesn't compile.
DoStuff is protected in RigidBody. CollisionGroup doesn't derive from RigidBody, so it doesn't have access to its protected members. If that's different in java or c#, those two are imho broken.

There is a proper solution:
Code: [Select]
class Foo {
private: //only use protected if it's required to explicitly call this from a base class
   virtual void DoStuff()
   {
      cout<<"foo::DoStuff"<<endl;
   }
public:
   void DoStuffPolymorphic()
   {
      DoStuff();
   }
};

class Bar : public Foo {
protected:
   void DoStuff()
   {
      cout<<"bar::DoStuff"<<endl;
   }
};

class Bar2 : public Foo {
   Foo* b;
public:
   Bar2() {
      b = new Bar();
   }
   void Blubb() {
      b->DoStuffPolymorphic(); //will call Bar:DoStuff
   }
};
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on November 15, 2012, 02:15:36 pm
But... wha :confused: That's even worse, a protected method should not be able to override a private method!

DoStuff is supposed to be protected so that only classes derived from CollisionObject can access it. Making a public DoStuffPolymorphic method wrecks that. And making it protected wouldn't help, because then the derived classes couldn't call it.

 :confused:
Title: Re: My Game Engine is too Slow
Post by: Uchuujinsan on November 21, 2012, 07:08:48 pm
OK, I have to admit I didn't read your original post thoroughly enough. More on that later.

Quote
But... wha :confused: That's even worse, a protected method should not be able to override a private method!
public/private/protected is access control. You are not accessing Foo:DoStuff. By declaring it virtual you explicitly allow it to be overwritten. Extending access control to overwriting virtual functions would make private virtual functions simply impossible.

Quote
DoStuff is supposed to be protected so that only classes derived from CollisionObject can access it. Making a public DoStuffPolymorphic method wrecks that. And making it protected wouldn't help, because then the derived classes couldn't call it.
Uh yeah, that's the part were I didn't read properly.
So, a correction:
Code: [Select]
#include <iostream>

using namespace std;

class Foo {
protected:
   virtual void DoStuff()
   {
      cout<<"foo::DoStuff"<<endl;
   }
protected: //note the protected here
   void DoStuffPolymorphic(Foo* test)
   {
      test->DoStuff();
   }
};

class Bar : public Foo {
private:
   void DoStuff()
   {
      cout<<"bar::DoStuff"<<endl;
   }
};

class Bar2 : public Foo {
   Foo* b;
public:
   Bar2() {
      b = new Bar();
   }
   void Blubb() {
      DoStuffPolymorphic(b); //calls bar::DoStuff()
   }
};

int main()
{
   Bar2 test;
   test.Blubb();
}

[edit]
C-style casts are EVIL btw. ;)
[edit2]
Note that overwriting a private method with a public method still doesn't allow the following:
Code: [Select]
class Foo {
   virtual void DoStuff() {}
};

class Bar : public Foo {
public:
   void DoStuff() {}
};

int main() {
Foo* f = new Bar();
//f->DoStuff(); //error C2248: 'Foo::DoStuff' : cannot access private member declared in class 'Foo'
static_cast<Bar*>(f)->DoStuff(); //ok, Bar::DoStuff is public
}
I'm leaving the deletes out to make the code shorter, btw, I'm not forgetting them. :)
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on November 22, 2012, 02:59:29 pm
@Uchuujinsan: Meh. I'm coming from a C#/Java background, wherein stuff works the way I'd expect. And where private + virtual isn't a thing.



Anyway, gotta make GPU physics go faster :blah:

My original scheme had two shader programs: one which evaluated constraints and output the new linear & angular velocity data for the two rigid bodies involved, and a second which updated a master array of rigid bodies' velocity data, copying from the previous state or from the outputs of the first shader according to an index.

My second and current scheme has one shader program which is kind of a combination of the two shader programs in the first scheme. It updates rigid bodies' entries in the master array, using an index to determine which ones should be copied from the previous state and which ones are changed. But instead of copying the changed ones from another array, it does the computation on the spot. The disadvantage of this is that it has to process each constraint twice... but it was still faster than the first scheme.

I've got an idea for a third scheme which I think might be even faster. It would be just a single shader program, with a geometry shader to evaluate the constraints and emit what are basically RGBA32F pixels/texels... to write a specific vec4 to a specific pixel/texel of the master velocity data array. If the constraint doesn't apply an impulse, it wouldn't emit any pixels. If it applies an impulse, it would write the new linear and angular velocities of the two involved rigid bodies to the appropriate places in the array.


One thing that has been an issue with both of the schemes I've tried, and I believe will still be an issue with the third scheme, is that I can't use the same buffer as both an input and an output. So I've been having to switch back and forth between two buffers instead. I don't know for sure, but I somewhat suspect this is contributing to how long it takes to process.

I have determined that the amount of time it takes is basically proportional to the number of batches processed, i.e. iterations * batches.size() in the snippet below. This seems to be independent of the number of rigid bodies, or the average number of constraints per batch.
Code: [Select]
for(unsigned int i = 0; i < iterations; ++i)
for(unsigned int j = 0; j < batches.size(); ++j)
{
// do constraint shader stuff
glActiveTexture(GL_TEXTURE1);
glBindTexture(GL_TEXTURE_BUFFER, active_vtex);
glTexBufferEXT(GL_TEXTURE_BUFFER, GL_RGBA32F, active_vdata);
glUniform1i(u_velocity_data, 1);

GLDEBUG();

// set up outputs for transform feedback
glBindBufferRange(GL_TRANSFORM_FEEDBACK_BUFFER, 0, inactive_vdata, 0, num_rigid_bodies * 4 * sizeof(float));
glBindBufferRange(GL_TRANSFORM_FEEDBACK_BUFFER, 1, inactive_vdata, num_rigid_bodies * 4 * sizeof(float), num_rigid_bodies * 4 * sizeof(float));

GLDEBUG();

glBeginTransformFeedback(GL_POINTS);

glDrawArrays(GL_POINTS, num_rigid_bodies * j, num_rigid_bodies);

glEndTransformFeedback();

GLDEBUG();

glFlush();

// change which direction the copying is going (back and forth)... can't use one buffer as both input and output or it will be undefined behavior!
swap(active_vdata, inactive_vdata);
swap(active_vtex, inactive_vtex);
}

Little help?



Edit: I was forced to replace glFlush(); with glFinish();, and now it is even slower :( :( :(

Edit II: Apparently I can leave those all as glFlush, and add a glFinish before calling glGetBufferSubData (which is one of the first things I do immediately after the snippet I pasted)... so it's not as bad. But I still need to call glFlush every iteration, and I still need to swap back and forth between two buffers  :blah:
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on December 12, 2012, 10:58:24 pm
So I've shelved the GPU physics idea, because I couldn't get it to be faster than the pure-CPU implementation.

I was like "I want to work on gameplay again!", and so I did... but then I realized I had a serious character animation/physics problem... because my cheaty character physics conserves linear but not angular momentum, it is possible for a bug to be standing with its center of mass floating off the side of a cliff, supported by only one leg, upright, without falling. Which is bad.

Also there are problems when the large artillery bugs... they almost always float with only one or two legs in contact with the ground, and when they turn around the physics causes ridiculous bouncing. Which is also bad.



So I've determined that I need to go back and do physics-based movement... for the bugs, at least.

Here's my plan:




Does that seem like a reasonable way to approach this? Anyone knowledgeable about IK / physics based movement here able to weigh in?
Title: Re: My Game Engine is too Slow
Post by: z64555 on December 14, 2012, 09:00:22 pm
You seem to be going back to your original plan just to go through the madness all over again. I'd say try sticking with the traditional animation sequences that just move the limbs, and have then engine move the whole body system relative to the rate the animation is played.

Essentially, make everything behave like a box that slides across the ground. The box's normal vector is an interpolation of the intersections of the box's floor edges, so if one edge of the box is off a cliff, and the other edge is on something solid, you can calculate torques and rotations on the box's center of mass to make it tilt and then fall off the cliff.

You'll still come across some funny situations, but it'll be a start...
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on December 14, 2012, 10:38:20 pm
But I've been working on per-bone physics all year... I don't want to ditch it to go back to abstracted blobs, or boxes. :(  And it's not just because of how much time I spent working on it, it's also the fact that it works and it's awesome.

...but the cheaty character animation system I put on top of it isn't cutting it for these new, larger bugs. That said, I can't imagine how treating them as boxes would be much better. The goal isn't to make them fall down when they try to stand off to the side of a cliff... that just happens to be one of the most obvious manifestations of the problems my current system has. Rather, the goal is to make them walk properly on varied terrain.

Bleh.



Anyway, I'm going ahead with the plan I posted, and I've finished item #1. So now I've got a severed bug leg with the hip joint frozen in place in mid air, and I'm trying to get it to do a pose. Basically item #2, including the "for chained joints" part. The implementation I came up with almost does it, but it'll be constantly flipping back and forth between two nearly-correct states, instead of smoothly reaching and maintaining the desired pose. And if I give it a shove, it wobbles and takes a while to come to a stop.
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on December 22, 2012, 12:58:21 am
I've determined that rather than try to design a data format capable of representing a generic pose/animation/behavior for a limb, I should do it the OOP way. I'm thinking I'll make a LimbAction class, with subclasses for the different behaviors a limb might have to do.

I've got a setup where I can tell this "robot arm" what orientation I want for each of its bones (in world coords, but I could probably change that), and it computes the torques necessary to do that, starting from the claw end and summing up the torques at each joint... because the torques are applied equally and oppositely to the two constrained bones, every torque I apply at one joint has to be undone (or redone?) at the next joint up in the chain. The setup works, mostly. If I give it a violent enough shove, it will flail wildly and take several seconds to get back to behaving nicely. But I reckon I could just detect for that, and switch to another LimbAction when that happens.

I don't know how I'm going to do "load feedback", but I know I will eventually need something to tell which legs are supporting the weight of a dood. :blah:



Edit:

I've revised the setup so that the desired orientations are specified on a per-joint basis instead of in world coords. Also, I'm using PID controllers! There was a lot of frustration because of transformations being done wrong, but now I've got it so it can get to an arbitrary pose or simple animation, and doesn't flail anymore. So now I can move on to making a LimbAction for stepping, and figuring out load feedback.
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on January 19, 2013, 05:49:56 pm
I'm considering ditching PID-based motor control :(

I tried making a crab bug use 6 of these PID-based Limb things, and it failed miserably. The pair of limbs which the RobotArm was based on were the closest to working, but they weren't working acceptably either. The other two pairs of limbs were flailing wildly, while the "good" pair of limbs was unable to hold the correct pose.

Maybe it's just a matter of tuning the PID coefficients, but there are 3 coefficients for each of 3 (or 5, depending how I treat them) motors for each of 3 unique limbs (3 because paired limbs can safely just use the same coefficients)... and I haven't the slightest idea how to tune them.




A history of the motor control schemes I've tried:

0. Completely non-physical dood animations. Doods were approximated as capsules.


1. As part of the joint constraint, the relative angular velocity of the two bones in a joint are constrained in order to get the relative orientation to a certain value by the next tick.

Problems with this:

2. Cheaty system where each bone has a desired position and orientation, and sets its linear and angular velocity in order to get there, while properly conserving linear momentum.

Problems with this:

3. Current system where I'm using PID controllers to set the torques on each axis of each joint (in a convenient coordinate system).

Problems with this:




So now I'm frustrated again, and as I said at the beginning of this post, I'm thinking about ditching this PID stuff. But I don't know what to do instead. :( Maybe something like scheme 1, but adding per-axis limits on how much torque can be applied? That might fix the issue I had where (I think) positive feedback was resulting in absurdly large impulses.

But I don't know how to fix the "joint fighting" to make it converge faster. The technique I've been using in scheme 3 works by summing the applied torques from the claw end of the limb up to the shoulder... it worked when all I had to deal with was the limb itself, and I could just dump extra torque into the shoulder joint, but I don't think it will work here. The carapace the real limbs attach to is not a torque sink like the shoulder in the RobotArm prototype.



What do?
Title: Re: My Game Engine is too Slow
Post by: z64555 on January 20, 2013, 10:27:25 pm
Try re-working the desired position/velocity controllers, while applying physical limits as to what the servos can accomplish. If the bug's body exceeds any of the maximums, saturate the torques, velocities, and/or positions to their respective maximum those servos can accomplish before feeding them into the physics evaluator.

In systems engineering terms, after you've gotten the output signal of your controllers, pass it through several saturation blocks the reflect the limitations of the servos before passing the signal through the physical model block (which ultimately gives you the "actual output" signal).
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on January 21, 2013, 02:36:34 pm
Eh? The PID-based thing already had limits on how much torque it could apply.

And it sucked balls. It kinda worked when all I had was a single limb, not in contact with the ground, with an immobile shoulder. But not at all when I put six of them together in a bug. Instead it's flopping and flailing around and generally failing, when all I asked it to do was to go to and maintain a constant pose.
Title: Re: My Game Engine is too Slow
Post by: z64555 on January 21, 2013, 03:11:48 pm
Ok, so you'll need to tune each leg to be able to hold at least half of the body weight of the 6-legged bug (since it needs a minumum of 3 points of contact to stay standing).

The flopping around bit is most likely from an improper damping ratio (probably too little) resulting in an under damped system of equations. I dunno, you may have to get math program like MatLab, SciLab, or OpenModelica to plot the response curve of your PID system instead of trying to eyeball it in-game.
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on January 21, 2013, 06:04:23 pm
Hm...

If I do something like the single-limb RobotArm prototype, but instead of a completely immobile shoulder joint I attach it to something that can move but can't rotate, and which has about the mass of the full bug (or half of it?)... maybe that will help.

Another thing that I'm concerned about with this PID thing... maybe some of my issues are arising from the fact that this is a discrete simulation instead of sensors monitoring a continuous real-life phenomenon (even if the sensors were sampling it discretely)... e.g. it may be possible to overshoot the mark in a single tick.

Not sure what you mean by "damping ratio".
Title: Re: My Game Engine is too Slow
Post by: z64555 on January 22, 2013, 01:05:05 am
Another thing that I'm concerned about with this PID thing... maybe some of my issues are arising from the fact that this is a discrete simulation instead of sensors monitoring a continuous real-life phenomenon (even if the sensors were sampling it discretely)... e.g. it may be possible to overshoot the mark in a single tick.

...Which is why I suggested that you try simulating in a math program suite before trying as a discrete time system (DTS). A DTS can, and will, become very unstable if the input signal operates at a frequency greater than what it is sampled at. In realistic terms, this means you can't have the bug accelerating too fast between iterations. The damping ratio is a complex formula that describes how fast the system decays from an initial impulse... just like a shock absorber on a car.

Simulating a single arm is a start, but try a simulation with three legs for a stationary test and four legs for a movement test before going to 6 or more.
[/quote]
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on January 22, 2013, 05:49:59 pm
Simulating a single arm is a start, but try a simulation with three legs for a stationary test and four legs for a movement test before going to 6 or more.

D'oh... why did I even try to get a single leg to stand... way to not do your job, brain.

...Which is why I suggested that you try simulating in a math program suite before trying as a discrete time system (DTS). A DTS can, and will, become very unstable if the input signal operates at a frequency greater than what it is sampled at. In realistic terms, this means you can't have the bug accelerating too fast between iterations.

RE: "simulating in a math program suite": You mean using an existing simulator? Or just for the analysis? I am somewhat disinclined to use an existing simulator, because its behavior would invariably be different from that of my physics engine, and ultimately it's my physics engine that I need it to work correctly in. Which isn't to say that my physics engine is physically inaccurate (although it may be), just that the specific of how my constraints behave, how the friction works, etc., would likely not be easily and accurately reproducible in another simulator.

RE: "if the input signal operates at a frequency greater than what it is sampled at": About a month ago I changed how constraint motors are controlled so that it runs a callback immediately before every physics tick... so it should have up-to-date info about the state of the physics world, and the values I set for the motor torques will potentially be changed again as soon as the next tick. And the ticks have a fixed timestep.



Anyway, will try with a tripod soon.
Title: Re: My Game Engine is too Lame
Post by: z64555 on January 22, 2013, 08:53:22 pm
...Which is why I suggested that you try simulating in a math program suite before trying as a discrete time system (DTS). A DTS can, and will, become very unstable if the input signal operates at a frequency greater than what it is sampled at. In realistic terms, this means you can't have the bug accelerating too fast between iterations.

RE: "simulating in a math program suite": You mean using an existing simulator? Or just for the analysis? I am somewhat disinclined to use an existing simulator, because its behavior would invariably be different from that of my physics engine, and ultimately it's my physics engine that I need it to work correctly in. Which isn't to say that my physics engine is physically inaccurate (although it may be), just that the specific of how my constraints behave, how the friction works, etc., would likely not be easily and accurately reproducible in another simulator.

Well, the other simulator would be a "guaranteed simulation of physical stuff," which means that if there's anything in your simulations that is just plain wrong, the game and the simulator will get 2 drastically different responses. The math program suite should allow you to simulate the physical model that you want and it'll plot you a nice curve of the response that you want out of your game. I'm going to try grabbing a copy of SciLab sometime this week to see if I can get some block diagram simulations going on it.

Quote
RE: "if the input signal operates at a frequency greater than what it is sampled at": About a month ago I changed how constraint motors are controlled so that it runs a callback immediately before every physics tick... so it should have up-to-date info about the state of the physics world, and the values I set for the motor torques will potentially be changed again as soon as the next tick. And the ticks have a fixed timestep.

In that case, the control system is operating at the same frequency as the system it is controlling. I think this should be ok, but I don't have enough experience with Z-domain modeling and simulation to give you a definitive thumbs up or down... I'll have to mess around with SciLab to see if I can get a better feeling of it.
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on January 23, 2013, 02:42:10 am
Made a tripod which uses the PID stuff. It's nowhere near as "rigid" as I want.



Also... physics trouble again :sigh:

I notice that when the legs of the tripod are touching the ground, the point of contact doesn't stay put... as if it's standing on a slippery surface. I'm not sure if that's because the forces are exceeding the force of friction, or if it's skipping out of contact with the ground every other frame, or what, but it's bad. And I think it's not entirely the PID system's fault, because there are similar problems with the player... e.g. when I try to stand still, my feet jitter and I very slowly inch forward or backward (depending on whether I'm looking up or down). And in the case of the player, it's definitely a case of not being in continuous contact with the ground.

Part of the problem is that when objects collide, they have a 'bounciness' which is a little more than enough to nullify their inward velocity. But gravity acts as a downward impulse applied every tick. Together this means that objects will never settle!

Maybe I need to make it so objects only bounce if the inward velocity is greater than the per-tick inward component of the delta-v from forces acting on the objects. I'll probably try that when I get up tomorrow.


Edit: Did that, but now it seems there's another issue... there's a system that undoes interpenetration between objects by directly modifying their positions, instead of changing their velocities... and if an object has two contact points with similar normal vectors, the displacement gets added and causes the object to move further than it really ought to. Shouldn't be too hard to fix though!
Title: Re: My Game Engine is too Slow
Post by: Tomo on January 26, 2013, 03:42:18 am
Both the issues raised generate energy from nowhere, which is obviously unrealistic.

You need damped collisions, that should solve both issues. Look up "inelastic collisions (http://en.wikipedia.org/wiki/Inelastic_collision)" on Wikipedia.

Perhaps treat interpenetration as the surface deforming under the "impact" and partially restore the surface elastically - like walking on a mattress.
- This will mean that all characters will always sink slightly below the surface, with the distance depending on their weight. The displayed models can take that into account.

Thinking about it, it also looks "right" if something with spiky legs jabs them slightly into the ground, rather than the ground being infinitely hard.
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on January 26, 2013, 03:10:21 pm
I already have inelastic and partially inelastic collisions, and have had them virtually from the beginning. That's what the "bounciness" variable is for. 0 = totally inelastic collisions. 1 = totally elastic collisions. There is no "energy from nowhere" involved in that aspect of the simulation.

I've removed the anti-penetration thing because it was indeed "energy from nowhere", and was causing problems.



Then I determined that my friction is borked: although I wanted it to only affect the tangential components of the relative local velocity between two objects at the contact point, it is affecting the normal component as well. Not quite sure how to fix.

But I realized something I hadn't realized before! I can represent a cross product as a multiplication by a 3x3 matrix! E.g. if I have a cross product a x b, I can represent that as multiplying vector a by [[0, b.z, -b.y], [-b.z, 0, b.x], [b.y, -b.x, 0]]. And so I determined that I can express the change in the relative local velocity at the contact point as a multiplication of the applied impulse by a 3x3 matrix :D

But when I tried to implement it it didn't work right :(
Title: Re: My Game Engine is too Slow
Post by: Tomo on January 27, 2013, 07:02:50 am
Ah, so so by "bounciness" you meant coefficient of restitution? That's correct then, sorry.

Not sure what you meant on the friction issue.
Perhaps knocking up something that draws the vectors (velocity, normal, and tangential) onscreen during sim would help you figure out where it's going weird?
Title: Re: My Game Engine is too Slow
Post by: z64555 on January 27, 2013, 12:55:21 pm
Ah, so so by "bounciness" you meant coefficient of restitution? That's correct then, sorry.

Spring coefficient, more likely. :)

I think that the vector indicators would be helpful, as well as maybe a control panel that will allow you to modify various coefficients in real-time (vs. going back, modifying a value, compiling, and simulating again).
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on January 28, 2013, 02:34:09 pm
Ah, so so by "bounciness" you meant coefficient of restitution? That's correct then, sorry.

Not sure what you meant on the friction issue.
Perhaps knocking up something that draws the vectors (velocity, normal, and tangential) onscreen during sim would help you figure out where it's going weird?

Ah yes! Coefficient of restitution (http://en.wikipedia.org/wiki/Coefficient_of_restitution)! I had heard the term before, but didn't realize it was the same as what I was doing.



RE: vectors:

One of the quantities I'm working with is the "relative local velocity" between two objects at the point of contact, i.e. the difference between the local velocities at that point... let's call this L for short. Computed as:

          L = v2 - v1 + r2 x ω2 - r1 x ω1

Where r is the vector from the respective object's CoM to the point of contact, and ω is the angular velocity of the object.



The way these quantities change when an impulse p is applied at the contact point are as follows:

          v1 += p / m1
          ω1 += I1-1 (p x r1)
          v2 -= p / m2
          ω2 -= I2-1 (p x r2)

Where I is the MoI of one of the objects.



Uh... where was I going with this?

Oh right! In theory, after I apply an impulse for "restitution", the component of L along the normal vector of the contact point should be non-negative, i.e. the objects should not still have a velocity that would cause them to go through each other. This much seems to be working.

The problem is that friction should only affect the components of L along the axes orthogonal to the normal vector (i.e. in the plane of the contact point)... but the way I've been computing the friction, I've just been using an impulse that's in the plane of the contact point, and that doesn't guarantee that the resulting ΔL will be in the plane as well.

I was thinking I could represent the conversion from p to the resulting ΔL as a 3x3 matrix multiplication, and then use the inverse matrix to compute an appropriate impulse... but as I said earlier, my implementation didn't work.



Edit:

I figured out why my implementation didn't work! It's because cross products lose information... i.e. if I have a function f(a) = a x b, it is not possible to reconstruct a given f(a). And so when I tried to invert a matrix which depended on the cross product matrices, it didn't turn out right.

So now I know why the thing I tried to do doesn't work, but I'm not really any closer to getting it working. :blah:



Edit II:

Turns out I just had the signs wrong in one of my equations (not one I posted though). I reversed the polarity and now it's working awesomely :D
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on February 05, 2013, 04:55:14 pm
There are still two "big" problems with my physics that I think I'm going to have to address before I can get back to working on physics-based movement...



1. Stuff going through other stuff, and contact between objects not being stable

I've tried turning the number of iterations the constraints solver does up from 15 to 200... that seems to fix the problem, but it also makes the game unacceptably slow. Somehow I need to achieve the effect of 200 iterations, while only using the processing time of 15 iterations :banghead:


The current setup is basically just a for loop iterating for MAX_CONSTRAINT_SOLVER_ITERATIONS around a for loop iterating through the list of constraints. It's "dumb" but has zero overhead.

In the past I tried a "smart" system where I broke the constraint graph into isolated subgraphs (caveat: constraint edges to immobile objects don't count for merging subgraphs), and then tracked which edges were "awake" due to an applied impulse at an adjacent edge during the previous iteration. That method had some initial setup overhead (I don't know how bad), and some overhead per constraint evaluated, but the benefit is that it let me skip evaluating some constraints which would end up doing nothing when I evaluated them. Also the results might be less consistent than the current setup, since constraints wouldn't always execute in the same order.

When I was trying to do stuff on the GPU I had another setup where I broke the constraint graph into batches with no adjacent edges. But that turned out slower than the pure-CPU implementation! I've tried a multi-threaded CPU implementation with this sort of batching as well, and it didn't seem to help much. This setup is also "dumb" in that it evaluates all the constraints, every iteration. I probably could've found edges which were completely isolated and made them only evaluate once, but beyond that I don't know if it would be possible to make this scheme do "smart" evaluation like what I mentioned in the isolated-subgraphs scheme.

What to do?



2. Contact regions that aren't just "points"

E.g. if I have a box resting on a slightly sloped surface, the entire bottom surface of the box will be in contact with the surface, and thus an "inward" velocity at any of the edges will be counteracted by the normal force / restitution / whatever we're calling it these days. A sphere, on the other hand, would only have a single point in contact with the surface, and thus would roll down the slope. But in my physics engine, if I only create a single contact point at the center of the box's bottom face, it will try to roll like a ball anyway... but unlike a ball, a box has a bigger radius at its corners than in the center of its faces, so it'll end up sinking into the slope as it tries to roll.

Currently I can have multiple contact points between a pair of objects, and it does what I want... but each one is an additional constraint for the constraint solver to process, and even with a lot of iterations of the constraint solver I need an "adhesion" threshold to keep the impulses at one corner from lifting another corner out of the ground. Also right now I don't have my collision detection set up to generate multiple contact points, except for collisions between multispheres and infinite planes, e.g. the ground plane I sometimes use to test physics with, which won't actually be used in the game anyway :blah:

I can probably modify my existing collision detection to produce multiple contact points for multisphere-multisphere and multisphere-triangle (of triangle mesh) collisions easily enough.

I'm thinking maybe I should change how ContactPoint works, so that instead of having a bunch of ContactPoint constraints between a pair of objects that has a non-pointlike region of contact, I would have a single constraint object that contains the shape data for the region (information which the current setup represents as a list of multiple ContactPoint constraints). What do you guys think?
Title: Re: My Game Engine is too Slow
Post by: Tomo on February 09, 2013, 04:48:29 am
I'm pretty sure you have to abandon the idea of any surface being perfectly hard, and deliberately allow an initial interpenetration based on the dynamic load, settling on a final interpenetration based on the static forces after collision energy is dissipated.

- Think "dropping a box on a mattress".

If you calculated the area of the interpenetration and use that as a scaling factor for the restitution force in the collision, would that work?
- The interpenetrating volumes might be more accurate, but harder to work out as you'll have to find the area first.
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on February 11, 2013, 10:50:26 pm
I'm pretty sure you have to abandon the idea of any surface being perfectly hard, and deliberately allow an initial interpenetration based on the dynamic load, settling on a final interpenetration based on the static forces after collision energy is dissipated.

- Think "dropping a box on a mattress".

I know there's going to be some initial interpenetration, just because I'm dealing with finite timesteps. But I'm pretty sure treating the objects as "springy" isn't the right way to go, if that's what you're suggesting.

Quote
If you calculated the area of the interpenetration and use that as a scaling factor for the restitution force in the collision, would that work?
- The interpenetrating volumes might be more accurate, but harder to work out as you'll have to find the area first.

The problem is not with the amount of restitution force, it's with the distribution of it. If I only measure relative local velocities at a single point, and apply impulses for restitution and friction at that same point, a box will behave identically to a sphere. To make a box behave like a box, it needs to have one such ContactPoint under each of its corners.




As far as the actual task of modifying my existing collision stuffs to create multiple contact points... I'm stuck. I started working on making the changes to multisphere-multisphere collisions... I made it find which of the spheres of each multisphere shape are past the "overlap distance" along the axis, and I made some switch statements to do different stuff according to how many such spheres there are from each object, but they don't do anything yet, and I don't know what to do as far as implementing them.




In other news, I've successfully re-implemented a "smart" constraint graph solver! But it broke my "adhesion threshold" fix for jittering :( Ah well, I'll probably come up with something.
Title: Re: My Game Engine is too Slow
Post by: z64555 on February 11, 2013, 11:20:21 pm
Perhaps the bouncing is due to usage of a > instead of a >= comparison?
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on February 12, 2013, 02:37:29 pm
Nope. The comparison is (normal dot relative local velocity) < 0, but I've tried doing <= 0, and < some positive threshold. Positive threshold (aka "adhesion threshold") was working... until I recently reimplemented the "smart" constraint graph solver, which broke it. I feel like I just said this. But looking at the most recent posts in this thread... maybe I only explained it in the WHIYL thread or something. :blah:

Maybe if I used a larger threshold I could make it work again... it feels kind of hackish though.

Edit: Confirmed, a larger threshold makes it work again. Still feels hackish though.




And I still need to figure out how to generate multiple contact points for my collisions (as appropriate).  :sigh:
Title: Re: My Game Engine is too Slow
Post by: Mika on February 14, 2013, 12:40:25 pm
I'm bit late in this thread, but there might be something I can help with.

First I would like to know what you are aiming at in the grand scheme of things? You have plenty of building blocks here, but to use some of them, I feel like it is going to contradict something else in your building blocks. I read that you'd like to have destructible terrain, but are you planning destructible units as well?

I think your engine would require finite element analysis sort of approach depending on how deep you want to go with something pushing something, or something hitting something. Though I'm not sure, but it seems to be heading that way.

My own background is in scientific computing, mainly in numerical methods and ray-object intersection tests.

Heh, never thought that traditional approach would be to have a box floating on the terrain, there's so much "cheaty" stuff in gaming that it's hard to believe it given its immersiveness.
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on February 14, 2013, 10:28:53 pm
O HAI!

As far as the destructible terrain system... I can already make holes in the terrain. I want to do island detection, but beyond that I don't have any plans.

Hm... destructible units... it would be cool to be able to blow a limb off a bug, but that would be yet another complication for physics-based movement. Idunno. I don't think I'm going to be doing anything like that scene in Starship Troopers where Rico carves a hole into the tanker bug's armor and tosses a grenade inside it :P



I don't see what I would need finite element method for? Except if I wanted realistic terrain deformation and fracturing... that's not going to happen any time soon, if ever.



Really I'm just stuck on getting the rigid body physics working cleanly  :blah:
Title: Re: My Game Engine is too Slow
Post by: Mongoose on February 14, 2013, 11:37:18 pm
I know this is probably a really stupid question, but are the methods you're implementing something that's fairly different than the standard approach, or are they something where there might be some resources out there to help set things up the way you want?  Trying to avoid reinventing the wheel seems like a good policy in general.
Title: Re: My Game Engine is too Slow
Post by: Mika on February 15, 2013, 02:20:42 pm
Quote
Really I'm just stuck on getting the rigid body physics working cleanly 

Right. So it's rigid body physics then.

Okay, what forces are you taking into account for the object? How do they progress through the body at the moment? Are you using a surface-surface contact model to model the leg friction, or is it just points?
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on February 15, 2013, 03:33:15 pm
@Mika, and others:

Context: rigid bodies in contact with one another:

If I only measure relative local velocities at a single point, and apply impulses for restitution and friction at that same point, a box will behave identically to a sphere.

That is my problem.

I can either solve this problem by creating multiple such "contact points" around the "corners" of the region of contact, or by modifying the ContactPoint struct to include the necessary extra data and modifying its DoConstraintAction method to use that extra data. Either way I need to modify the collision detection to compute that additional data.



@Mongoose: Well, I think in Bullet it only ever creates one "manifold point" between any pair of convex primitives... My ContactPoint struct is basically the same thing as one of Bullet's "manifold points". But I have no idea how Bullet deals with contact regions that aren't point-like.
Title: Re: My Game Engine is too Slow
Post by: Mika on February 15, 2013, 06:02:23 pm
Okay, I'm starting to get the hang of it. I even started to derive equations to see what is causing what! My differential calculus is a bit of rusty due to the severe neglect lasting for several years, but on the other hand, this stuff is interesting. Vector analysis on the other hand, is something I occasionally need to do at work.

I think using several points for analysis at the boundaries are a start, but as I started to think the formulation of the problem as a system of connected springs, there are several other factors popping up. Surface tension is one of them (otherwise ground conforms to the object shape, which doesn't happen in general case), then there is ground resistance towards pressure (must be an over dampened spring for typical landscapes). Additionally, the mass and the shape of the object on the surface become factors as well.

I think I need to check this out with pen and paper first, but heck, it's interesting!
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on February 19, 2013, 10:23:57 pm
@Mika: I don't mind that you're having fun exploring a new area, but that still sounds way more complicated than what I'm doing! The objects I am working with are rigid... they have a position, orientation, linear velocity, angular velocity, and mass, and defined in their local coordinate system they have a shape, center of mass, and a 3x3 moment of inertia matrix. No deformation, surface tension, or anything fancy like that :p

And what I'm doing is really more geometry that dynamics.



Givens:

What I'm trying to find:



To simplify things a bit, I decided to have a plane with that axis as its normal vector, and to put all of the contact points I produce on that plane and use the same normal vector for all of them. The plane is situated half-way between the farthest extent of the first object along the axis and the nearest extent of the second object along the axis.



I've got my code set up to collect two lists of spheres I consider "relevant" to the collision... one is the list of which spheres of the first object extend beyond the nearest extent of the second object, and the second is the list of which spheres of the second object extend nearer than the farthest extent of the first object. Then I have a pair of nested switch statements, executing different cases according to how many spheres were deemed relevant in each object: either 1, 2, or 3+ spheres. In other words, the relevant parts of each object can either be a sphere, a tube, or a plane. This part has been implemented for a week now.

I've implemented all the cases where either object only has one relevant sphere... these are the easy ones, because the contact point is just the position of that sphere flattened onto the plane (or the average position in the sphere-sphere case). For each of the remaining cases, I can describe the solution geometrically, but I'm stuck on how to actually implement them:

Title: Re: My Game Engine is too Slow
Post by: Mika on February 22, 2013, 03:03:35 pm
Sorry about the delay, last weekend was spent doing something completely different.

For tube-tube intersection, you need to store one point of the tube, preferably the center point of either end. Additionally, you need to keep track of the basis vectors of the tube, or on other words, the local coordinate system of the tube so that you know it's orientation all the time. Typically the unit basis vectors are denoted with i, j and k. So, whenever your tube is rotating, you need to rotate these basis vectors as well so that itrans = ai + bj + ck for general case. Note that in a case of cylinder, you may not need the basis vectors after all since you have the surface normal, but I mention this for more general surfaces.

I'm gonna use the following notation in the text: P1 is the position vector from the GLOBAL origin to the center of the circular end of the tube. The radius of this tube is then R1, and the tube length to the center of the other end is h1. The local coordinate vectors for this vector are it1, jt1 and kt1, each of which may contain components i, j and k of the GLOBAL coordinate system.

So, every point on tube 1 can be described in the global coordinate system with vector S1 = P1 + rit1 + sjt1 + nkt1, where r s and n are just coefficients in front of the LOCAL basis vectors. Similar vector definition applies for Tube 2. Note that this places additional conditions to solution, r2 + s2 < R12.  Additionally, n = [0 ... h1] and ditto for Tube 2. Now, that there can be a collision, intersection or union, S1 = S2 at that point. This can be written as P1 + rit1 + sjt1 + nkt1 = P2 + mit2 + ujt2 + qkt2.

You can split this to three equations, that each must fulfil the abovementioned conditions so that the intersection can happen. I may take a look at this a bit later, I think rotationally symmetry and normal vector can be utilized to ease this up, but I hope you get the general jist of the above.
Title: Re: My Game Engine is too Slow
Post by: Mika on February 22, 2013, 03:51:57 pm
Actually, don't start to code it yet, since the above would lead you to a triplet of equations that has three free parameters, which hints that the intersecting point may be anywhere in the combined volume of the two tubes. I have two additional approaches in mind for this set, I'll see where I get with them.
Title: Re: My Game Engine is too Slow
Post by: Mika on February 22, 2013, 05:24:45 pm
Okay, I think I got it. I'll spend the first hour after waking up on tomorrow to double check the logic - you never know if I missed something at this point of day!
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on February 22, 2013, 05:47:22 pm
What... is this the math for how to find where the surfaces of the tubes intersect?
Title: Re: My Game Engine is too Slow
Post by: Mika on February 22, 2013, 07:01:59 pm
The above was valid for the volume where the two tubes intersect. To get it to surface level, it is possible to get rid of two unknowns in the equation by requiring the relevant basis vector coefficients to fulfill the surface radius on both tubes. But the result is nevertheless very messy and still leaves one parameter free. But whatever, I think there is a more clever way of doing this algorithm wise, but you'll have to wait for that for tomorrow.

Yes, surface surface intersection tests are messy. Surface line intersection is much easier, but even there you don't want to get into higher order polynomials or B-Spline surfaces... Ray-trace software always uses simplest possible algebraic surfaces, such as spheres, rectangular volumes or just planes to enclose more complex geometries. Occasionally, the intersection point can be solved analytically for simple surfaces (like cylinders), but often it is the case that iteration is required, and this is one of the reasons why it is difficult to do a real-time ray-tracing engine.
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on February 22, 2013, 07:57:49 pm
But... I've already determined that they're colliding?
Title: Re: My Game Engine is too Slow
Post by: Mika on February 23, 2013, 08:12:08 am
Okay, the thing I thought about yesterday would have been okay for cylinders whose central axes intersect. However, this is not the case in general, and the larger the offset, the greater the error would have been.

Since I'm still not confident I understand your problem, could you draw me a formulation of the problem, tube-tube case first?

Meanwhile, for line-line intersection (I'm not sure whether you have already implemented this), the following should work:

P1 and P2 are points on the corresponding lines measured from GLOBAL origin, and thus vectors P1 and P2 are straightforward to define from the global origin. Additionally, you'll need the direction vectors for the both lines, be them n1 and n2 correspondingly. Normalize these vectors to unity.

First, compute n1 x n2. If the result is zero vector, the lines are parallel to each other and can only intersect if P1 = P2, otherwise no intersection is possible. If they do intersect, they'll intersect the whole distance they are defined at.

Second step, since we now know that n1 x n2  !=  0. We need to rule out the possibility that the three dimensional lines are skew, and thus could not possibly intersect. Compute (P1 - P2) * (n1 x n2). If the result is zero, intersection is possible. If the result non-zero, the lines are skew and cannot intersect.

Third step is the traditional solving free parameters r and s for P1 + n1r = P2 + n2s [1]
You could open up this to three equations for each coordinate axis, and solve for parameters s and r and substitute them to the last remaining equation to check whether it remains valid. The problem with this approach is that it gives rise for many possibilities of dividing by zero, or that some component of either normal vector is zero. Not good.

Instead, let's do the vector approach. Take a cross-product of [1] with n2. This eliminates one free parameter completely, one of the great things in vector algebra.
Result is n2 x (P1 + n1r) = n2 x (P2 + n2s), and because cross-product is distributive over addition, this can be written as
n2 x P1 - n2 x n1r = n2 x P2 + n2 x n2s, where n2 x n2 cancels. Re-arrange the remaining terms over right side, and leave r for the left, which leads to
n2 x n1 r = n2 x P2 - n2 x P1 = n2 x (P2 - P1). It sure would be nice to be able to leave r alone, but because this is a vector equation, we cannot divide the left side just with a vector. Instead, it pays off to multiply the equation with the dot-product of n2 x n1.

This results in (n2 x n1) * (n2 x n1) r = (n2 x n1) * [n2 x (P2 - P1)], and since the dot product of the vector itself is a scalar, it is now possible to divide the whole set with r's coefficient, leading to

r = [(n2 x n1) * [n2 x (P2 - P1)] /  | n2 x n1 |2

Substitute r to the P1 + n1r and you'll get the intersection coordinates. I'm not sure whether denominator normalizes to unity, so it is better to leave it that way.

Now, and this is a very big NOW, you cannot use these generally to determine the intersection points of the cylinders, especially if the cylinders have large base radii. Why? Because while skew lines do not intersect, skew cylinders can and will intersect when you least expect it, and this is the complicative issue.

The reason for the order of the three steps is the following. Since there is a multitude of pieces in the geometry and many of them needed to be tested, the intersection test should terminate as soon as possible if no intersection becomes apparent, and only go to heavy calculation as a last step - basically, we are sort of assuming that the intersection does not happen and this tends to be the case.
Title: Re: My Game Engine is too Slow
Post by: Mika on February 23, 2013, 11:46:40 am
And for line-tube intersection in general case, please refer to ye olde Graphical Gems (http://books.google.fi/books?id=CCqzMm_-WucC&pg=PA356&lpg=PA356&dq=line+cylinder+intersection&source=bl&ots=mslr35FJhk&sig=kXixeKo2sgQc17KDzu12pGyJ9XE&hl=fi&sa=X&ei=gPwoUYn5B8nRsga4vIGACQ&ved=0CGgQ6AEwCDgK#v=onepage&q=line%20cylinder%20intersection&f=false).

It also contains code to compute the points of intersection, along with the theory.

Now, since others have noted that a tube isn't that great of an enclosing surface (http://www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf), they recommend using capsules for faster intersection testing. Select something like 20 points on the underlying base circle with equal angle steps, and record these points on to a structure. Whenever the cylinder is rotated or translated, apply same to these points as well. Then do the intersection test between the lines defined by these points and the tube axial direction vector and the opposing tube as shown in the above code.

Now, what was the next intersection test? Line and a plane, or a tube and a plane? Or a line and a polygon?
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on February 25, 2013, 05:44:55 pm
Dude, stop :(

I'm not trying to do collision detection. I have already determined that the objects are colliding. I am trying to pick points within the region of contact to do my constraint stuff at.



Edit: and now it's done! Mostly. Might need to do some tweaks to get tube-tube and tube-plane working a little better, but it seems to be working.

Still gotta do all of multisphere-triangle (of triangle mesh) though.
Title: Re: My Game Engine is too Slow
Post by: Tomo on February 26, 2013, 10:51:26 am
My brain melted...

Great to hear you got it working! (Mostly)
Title: Re: My Game Engine is too Slow
Post by: Mika on February 26, 2013, 11:32:45 am
Congratulations on progress!

The above two methods I listed DO produce the exact point where something hits, i.e., they are actually not used for collision detection, but telling the exact point of the collision (the intersection). I thought that was what you asked.

Triangle-line intersection had a really snappy algorithm with some clever mapping in it, I wonder if that method could be generalized for spheres somehow...
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on February 26, 2013, 02:23:08 pm
Speaking of progress...  :sigh:

For some reason I am thinking about ditching multisphere shapes in favor of convex polygon meshes... despite the huge amount of time I've spent getting multisphere shapes working. Bleh.

Arguments pro switching:

Cons:
Title: Re: My Game Engine is too Slow
Post by: Mika on February 26, 2013, 03:33:40 pm
What I would think about polygon based collision testing and intersection finding is that you can then use the same algorithm for pretty much everything. Well, maybe little tweaks here and there. Since most of the surfaces (read:all) I have programmed have been continuous to second derivative, I don't know how to deal with the discontinuities in the polygon mesh so don't ask me about that.

There was a graphics engine that was completely sphere based a couple of years ago, which made real-time illumination with ray-tracing a breeze compared to anything else. What you are now doing is programming sort of geometric primitives (more analytic and scientific method of finding intersections), where each of them have to be handled in a different way. Polygons are bit more universal if I have understood them right. You'll still not get rid of bounding volumes completely, typically polygons have them too to speed up the collision/intersection testing.

If you go on with geometric primitives, I'd recommend using simple geometric enclosing volumes, tube probably isn't one of them, but a rectangular volume is. Typically what are used are spheres, rectangular bounding volumes and planes where applicable. The nasty thing is that the bounding volume must also rotate and move accordingly on each update.

So it all depends on what you want to do. You'll learn much either way, but doing something differently is usually a better way of learning.
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on March 05, 2013, 02:29:32 pm
Was trying to type reply but twice now have lost my whole message due to some combination of keypresses causing firefox to exit while I was battling with these stupid ****ing loose keys on my keyboard. Will maybe try again when I've calmed down.



Well, I decided to do the convex meshes thing.

I've gotten a fair amount done on my new ConvexMeshShape class. I've got an Init method which takes an array of points as input and from that figures out the vertices, edges, and faces of the minimum convex polyhedron necessary to enclose those points. I've tested it on my beveled cube "crate" model, and it seems to be working, including getting rid of unnecessary colinear verts.

I've also implemented some collision detection functions for it... CollideRay and CollidePlane are done (but untested), and CollideTriangle (of TriangleMeshShaped) and CollideConvexMesh are done as far as detecting the collision, at which point they call a GenerateContactPoints method, which is not done yet. Basically I'm where I was like a month ago; I've got collision detection, but I need to generate multiple contact points for the collisions I've already detected. But unlike a month ago, all the code is going to be in one function (instead of separate setups for -triangle and -multisphere), and everything is points instead of spheres. That should simplify things this time around.

As far as how GenerateContactPoints is going to work, I've already started the way I did previously by figuring out the min an max extents of the region of overlap, and then only concerning myself with the verts of either object which extend into that region. Anyway, I think I can implement this.



I'm a little worried about the performance of the actual collision detection (not the contact point generation) potentially being worse, though, because...

With the MultiSphereShape representation of these crates, I had 8 rounded spheres... so evaluating the min and max extents of each cube (in a collision between two such crates) was 16 dot products. The algorithm for deciding which directions to test was basically to test 8 points around the previous best result, zooming in 2x if they all score worse, and repeating this for 5 iterations. More for better quality... because it's a numerical thing, I can tune it by changing the number of iterations... although I've never thoroughly examined it to see how many false positives it produces with different numbers of iterations (by seeing how many false positives get removed with each additional iteration).

With the new ConvexMeshShape representation, there are 24 verts, 48 edges, and 26 faces... evaluating the min and max extents along an axis is therefore 48 dot products (1 for each vert, x 2 objects). And if I'm going to be doing it analytically instead of with a numerical-ish search like I did previously, I'm pretty sure I have to evaluate once for each of (2 * 26 + 2 * 24 * 24 + 2 * 24 * 48 + 2 * 48 * 48) directions in order to be guaranteed to find a separating axis if one exists.

Maybe I can intelligently limit which verts/edges/faces I need to test, and which verts I consider when evaluating the min and max extents? Or should I just continue doing this numerical-ish searching business I've been doing?
Title: Re: My Game Engine is too Slow
Post by: Mika on March 05, 2013, 07:08:59 pm
Okay, convex polygon meshes should have more defined methods in the literature and in the game design side. There's not much I can say about any sort of polygon intersections rather than subdividing them to triangle intersections. Since a single polygon can easily have over thousand triangles, going to intersection testing of all of them is something one does not want to do voluntarily. So bounding volumes still remain important. Additionally, I'd look for structs and flags containing information about for example, which parts of the player model are supposed to hit the ground in which stance, or if he is airborne at the moment or not - I don't whether they do it this way, but that's what I'd look for.

I'm a bit curious though, why are you trying to find a specific solution for the collision between two boxes? I thought CollideConvexMesh would do that as well - if it is performance you are looking at, then that's a different thing - I'd first recommend going further and not stopping to optimize this routine until it becomes a bottleneck. Remember that the premature speed optimization is the root of all evil. When it DOES become a bottle neck, first thing I'd do to improve the efficiency are bounding volumes of the polygons, these should speed up the collision search - and then you are sort of back to square one.

Good luck, I'll be looking for this thread occasionally

EDIT: Oh, and occasionally, it is so that the numerical method is more efficient than analytical method - or that the difference is so small that it doesn't matter, while numerical method is numerically more simple to program and possibly less ill-conditioned. All these sorts of things happen in the ray-tracing world as well!
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on March 05, 2013, 11:21:41 pm
@Mika: Yes, "the literature" was one of the pros for switching to convex meshes. Already been doing bounding volumes for a long time... at least for my broadphase collision detection anyway. What's this about boxes? I just searched for "box" and found nothing recent in this thread... Do you mean the crates? I'm just using those because it seems like a good example to test stuff with... and because you can't have an FPS without crates.



Anyway I finished implementing the methods I was working on, and got the things in-game... but there are a few problems...

First, it's unplayably slow! :ick: Significantly worse than multispheres. Maybe I can come up with something to get it working faster? Idunno. :sigh:

Second, there's some weirdness which seems to be arising from my "adhesion threshold" hack (threshold for local relative velocity, below which objects get pulled back together)... When I was doing multispheres I had it set at about 0.08 m/s to keep the crates (which had rounded corners) from jittering. But that's keeping these beveled-corner crates from rolling down hills when they ought to. But if I reduce the adhesion threshold, they jitter again!

Finally, there's an infinite loop that only seems to happen when I'm running a Release executable, and inconsistently then. Bleh.
Title: Re: My Game Engine is too Slow
Post by: Aardwolf on March 07, 2013, 03:04:45 pm
Bleh. I don't know what to do with my physics anymore.  :(

I've been struggling with the same problem in various forms for months now: how to achieve stable contact between rigid bodies. That is, with no jitter, no sinking into each other, and no aphysical adhesive properties. That last one is new, because I hadn't realized it was a problem until recently.

Also in case it wasn't obvious: it needs to run at a playable speed.



Things I've tried (but not necessarily in all combinations):

Things I haven't tried:

Australian doofus who dislikes FreeSpace suggests a combination of continuous collision detection and magic anti-penetration displacement... but implementing continuous collision detection would be a big undertaking.

 :sigh: :sigh: :sigh:
Title: Re: My Game Engine is too Slow
Post by: Mika on March 07, 2013, 04:24:45 pm
First thing I'd like to ask is, what do you think is causing the jitter? Are the crates moving or stationary? Is the ground they are placed at a plane or a polygon? If looking at the force gradients of the crates, do you see sudden spiky increases in them?

Could you describe what you are actually doing with the bodies in the code?
Title: Re: My Game Engine is too Jittery
Post by: Aardwolf on March 08, 2013, 02:31:57 pm
What's causing the jitter? I don't know / it depends. I've tried various things and depending which thing I'm trying it fails in various ways. Part of it is gravity adding extra energy to the system. When there are multiple contact points, (e.g. the corners of a box) the impulse applied at one corner will nullify any "inward" velocity at that corner, but may produce an upward velocity at one of the other corners.

Are the crates moving or stationary? Initially they fall from the sky onto either a level ground plane or a terrain mesh. The initial "bouncy" collisions are ok, but when the boxes should eventually be coming to rest (i.e. they should be stationary) they instead jitter. Note that "rolling contact" is something I need to get right as well, and it's kind of similar to static contact. I'm not sure under which conditions rolling contact jitters.

Is the ground they are placed at a plane or a polygon? Are you talking normal vectors or finite vs. infinite? I've done two different tests: one has a level ground plane which is effectively infinite; the other has a terrain mesh made of triangles.

Force gradients: wat :confused:





Could you describe what you are actually doing with the bodies in the code?


Ok well... here's pseudocode of what my "main loop" does every tick:
Code: [Select]
UpdateVel all the dynamic collision objects (effectively all rigid bodies); includes something like vel += gravity * timestep;
UpdateVel all the RayColliders

RayTestPrivate all the RayColliders

Do collision detection --> populate a list of ContactPoints

DoUpdateAction all the persistent PhysicsConstraints (e.g. JointConstraint) and collect them in a list of PhysicsConstraints
DoUpdateAction all the ContactPoints and add them to the list as well magic anti-penetration displacement directly modifies pos here

Solve the constraint graph (i.e. repeatedly DoConstraintAction all the PhysicsConstraints in the list we just built) modifies vel to keep objects from going through each other, etc.

UpdatePos all the dynamic collision objects includes something like pos += vel * timestep
UpdatePos all the RayColliders


And here's the basic idea of ContactPoint::DoConstraintAction:
Code: [Select]
Vec3 dv = GetRelativeLocalVelocity(); // i.e. the difference between the local velocities of each object at the point
float nvdot = Vec3::Dot(normal, dv);

if nvdot < adhesion_threshold:

Vec3 normal_nvdot = normal * nvdot;

// normal force aka restitution
float use_restitution_coeff = nvdot < bounce_threshold ? restitution_coeff : 1.0f;
Vec3 restitution_impulse = rlv_to_impulse * normal_nvdot * -use_restitution_coeff;

// friction
Vec3 full_friction_impulse = rlv_to_impulse * (normal_nvdot - dv);
float fric_fraction = min(1.0f, fric_coeff * restitution_impulse.ComputeMagnitude() / full_friction_impulse.ComputeMagnitude());

// apply computed impulses
Vec3 apply_impulse = restitution_impulse + full_friction_impulse * fric_fraction;
ApplyImpulse(apply_impulse);

if apply_impulse.ComputeMagnitude() > impulse_threshold:
wake up adjacent constraint edges in the constraint graph

rlv_to_impulse is an awesome 3x3 matrix which tells me what impulse I need to apply at the point in order to achieve a particular change in the relative local velocity.

GetRelativeLocalVelocity is effectively b.vel - a.vel + Vec3::Cross(pos - b.com, b.angular_vel) - Vec3::Cross(pos - a.com, a.angular_vel) (where pos is the "position" of the contact point, i.e. whatever value I gave it in the collision detection code when I created it.

ApplyImpulse is effectively
Code: [Select]
a.vel += impulse / a.mass;
b.vel -= impulse / b.mass;
a.angular_vel += Mat3::Inverse(a.moi) * Vec3::Cross(impulse, pos - a.com);
b.angular_vel -= Mat3::Inverse(b.moi) * Vec3::Cross(impulse, pos - b.com);




Could you describe what you are actually doing with the bodies in the code?

Well uh... pseudocode...  :nervous:
Title: Re: My Game Engine is too Jittery
Post by: Mika on March 08, 2013, 07:16:42 pm
Okay, I'll try to get through of that during this weekend since my own stuff struck a wall (Just why isn't there an easy way to create a scalable 2D graph for Windows from the get go?).

Meanwhile, think of gradient as a multidimensional derivative of a multivariate function :D I know that sounds awful (which is the reason why I said it that way), but don't get scared, it sounds more worse than it actually is. Take a look at here (http://en.wikipedia.org/wiki/Gradient). Basically, if you have a three dimensional vector function like velocity parameterized by a single parameter t as in v(t)=[x(t), y(t), z(t)], the gradient is then the partial derivative of each coordinate function like grad(v) = [x'(t), y'(t), z'(t)]. What's the relevance of this you are probably asking? Well, gradient of the velocity vector is the acceleration vector, and looking at the lengths of the gradients, you could see if there are sudden force spikes being applied to the crates when they are nearby. One of the reasons that could happen is numerical precision.

Suppose a crate is resting on a edge of two triangles of a single polygon. In general case, these triangles have slightly different normal vectors (unless the polygon is a plane). If it so happens that the box is starting to lean on either side due to gravity, you'll apply slight amount of rotational momentum on it, which will momentarily cause the edge of the crate to hit the other triangle. Since there is a bit of energy coming back from the ground (I understood your code that way) the crate now sees as a new force. If we happen to be doing updates on forces on certain time intervals, it may happen that the acceleration applied to the crate within this short time interval is much higher than expected, which would lead the edge of the crate bouncing off, leading to a rotational momentum that will then turn the crate to face the other triangle, rinse and repeat.

I don't know whether that is the actual cause, but I'd take a look on the acceleration (or force) vectors of the objects, as they might hold a clue why you see things happening in a way they do. Actually, instead of gradients, try drawing the combined force vector of a single object while you are running the game.
Title: Re: My Game Engine is too Jittery
Post by: Tomo on March 09, 2013, 02:12:33 am
no sinking into each other
Genuinely, I'm pretty certain this is where the jitter really comes from, as real objects are neither infinitely hard nor infinitely rigid.

When you get down to the molecules and atoms, every contact is actually a spring and an adhesion force, with the sizes of each depending on distances between the atoms.*

In any physical contact, there is always some interpenetration and deformation - usually small, but always non-zero.
So any scheme that tries to ensure this can't happen tick-to-tick can't work, and it seem is unlikely to work in the steady state either.

You're going to need to allow at least one of 'sinking into each other', or 'deformation' at some scale, and base the final the 'adhesion' and 'restitution' forces on the amount of interpenetration/deformation  - because that's how the real world works.

Also, in control theory - as in 'driving a real robot's joints' - there is always an error between the 'desired' final position and the actual final steady-state result. The constants are chosen to minimise it, but it's always there.

Perhaps one approach to finding a solution is to start from the steady-state:
What should the final resting place look like?
How can the algorithm know it's reached it?

* This is of course a lie, but it's reasonably close if you ignore chemistry.
Title: Re: My Game Engine is too Jittery
Post by: z64555 on March 09, 2013, 12:05:43 pm
The jitter could be just noise in the calculations, possibly from floating point errors?
Title: Re: My Game Engine is too Jittery
Post by: Aardwolf on March 09, 2013, 02:56:22 pm
@Mika: I am familiar with the concept of a gradient. I do not have any nonplanar polygons; in my TriangleMeshShape I have only triangles, and in my ConvexMeshShape I have only convex planar polygons. But yes, the jitter is probably something like that?



@Tomo: I am willing to permit a small amount of initial penetration between a pair of objects. I am not willing to permit those objects to continue moving further into each other over time. I chose the gerund form "sinking" because I am talking about an ongoing process, not a stable state.

RE: robots: I've put that on hold until I can get the physics working satisfactorily.

RE: steady-state: Ultimately the objects should be completely stationary. However, in the similar case of "rolling contact", the objects should have no relative local velocity at the point(s) of contact, and the objects should not penetrate into one another any further than they already are.

Edit: what I said earlier: no jitter, no sinking into each other, and no aphysical adhesive properties.



@z64555: Didn't you ask this before? I'm pretty sure I already said "no" to it being floating point imprecision.
Title: Re: My Game Engine is too Jittery
Post by: Mika on March 10, 2013, 03:51:35 pm
Okay, I went through a bit of your math

dv is the local relative velocity.
n is the local surface normal (normalized to unity, I suppose). Now, nvdot = n *dv is a scalar that can get pretty much all real values since there is no guarantee that the both vectors are positive, or that their dot-product would be positive.

The next row is:
Code: [Select]
if nvdot < adhesion_threshold
This comparison is dangerous, given the above. Hopefully, what actually reads in the code is
Code: [Select]
if fabs(nvdot) < adhesion_thresholdThis will make sure that the adhesion threshold comparison is always carried out in cases where it needs to be carried out.

The next line made me to check the ANSI C reference, since I haven't used ternary operators before (always done it with if constructs)
Code: [Select]
float use_restitution_coeff = nvdot < bounce_threshold ? restitution_coeff: 1.0f
I would write (nvdot < bounce_threshold) if the pre-processor just accepts it, these assignments can sometimes evaluate to something completely different without parentheses. I'm not sure how the expressions and operator precedence work in this construct, but from the charts, you should be safe. Basically what you are doing with this is just applying a modifier to the normal (force) in case of a partially inelastic collision where it is expected that there will be a shape change on either of the objects and there are losses of energy. If nvdot exceeds bounce_threshold, you apply the elastic collision model? Additionally, related to the earlier comment, think what happens if nvdot < 0 here...

The line
Code: [Select]
Vec3 restitution_impulse = rlv_to_impulse * normal_vector * (-1)*use_restitution_coeff)made me scratch my head for a while since impulse as I know it is force multiplied by time, thus it's unit is [kg m/s]. Okay, after a while I realized what it actually does, so no problem any more. Again, make sure the normal vector is pointing at the direction you want it to be pointing at, since there is no general guarantee that the surface normal is doing that. Ditto for the signs of the elements of the rlv_to_impulse. Additionally, there is a possibility for discontinuous derivatives at this point, since the restitution coefficient is basically calculated inside an if-loop. I have occasionally seen a local optimizer written by a certain person (cough cough) approach a local minimum, and assault a limiting condition that had a very heavy weight, which consequently threw the search out of the immediate area of the minimum since the derivative grew so large on the other side... Lesson learned, if the result doesn't improve, don't try to improve things by always going to max iterations. :D

For the fraction of friction
Code: [Select]
float fric_fraction = min(1.0f, fric_coeff*|restitution_impulse|/|full_friction_impulse|)at the current state, this should evaluate with positive numbers, so that's clear. How was the comparison actually implemented in the code?

That's for what I could see from the code itself. I'll try to think it from the physics perspective next.
Title: Re: My Game Engine is too Jittery
Post by: Aardwolf on March 10, 2013, 05:31:59 pm
Re: absolute value: nope; a negative nvdot indicates the objects are moving toward each other, and therefore I should do something to keep them from going through each other. The small positive "adhesion threshold" is just a hack I came up with to eliminate jitter. More on that at the end of this post.

Re: "impulse": I mean Δ(mv)

Re: fric_fraction: the actual line is
Code: [Select]
float fric_fraction = min(1.0f, fric_coeff * sqrtf(restitution_impulse.ComputeMagnitudeSquared() / full_friction_impulse.ComputeMagnitudeSquared()));
Which is mathematically equivalent, but only calls sqrtf once.



Really what I posted was almost an exact copy of my actual code (http://code.google.com/p/cibraryengine/source/browse/branches/nobullet/CibraryEngine/ContactPoint.cpp?spec=svn455&r=452#64).




I think I can solve the jitter issue with something like my adhesion threshold, but comparing to a constant isn't a solution that works in general. It kind of depends on the geometry of the contact region. Basically, shorter edges are stickier.
Title: Re: My Game Engine is too Jittery
Post by: Mika on March 10, 2013, 06:26:32 pm
Quote
Re: absolute value: nope; a negative nvdot indicates the objects are moving toward each other, and therefore I should do something to keep them from going through each other. The small positive "adhesion threshold" is just a hack I came up with to eliminate jitter. More on that at the end of this post.

Ah, so adhesion_threshold, tries to make things stick in that way. I'm trying to think what happens next if the velocity is small but negative, leading to a small, but negative nvdot value. Especially if it so happens that the crate is very near the intersection plane, and in the next step it would be very slightly inside the other object? What happens then? Does this attempt to push the crate back up?
Title: Re: My Game Engine is too Jittery
Post by: Aardwolf on March 12, 2013, 01:57:24 pm
A little explanation of how my SolveConstraintGraph thing works may be in order:

If a constraint applies a sufficiently large impulse it wakes up adjacent constraints, meaning it calls DoConstraintAction on them in the next iteration. This continues for up to 200 iterations. So by the time it finishes iterating, the objects should hypothetically never have an "inward" velocity at any of their contact points.



The jitter happens when one of the corners of the box ends up with an "outward" velocity, and thus in the next physics step it ends up not being in contact. But in another physics step or two, it will be in contact again (if it's the case of a box "resting" on the ground, anyway).

The "adhesion threshold" has the effect of preventing the corners from separating unless they really want to. It's a start, but as I said before, using a constant m/s value to determine that isn't good enough, because it effectively makes shorter edges more resistant to rolling. But unfortunately "edge length" isn't a real thing. What I have are ContactPoint objects each with a Vec3 pos. Maybe I could change it so all the contact points between two convex primitives are stored in a single place, and then actually make "edge length" be a thing? Idunno.



Edit: I am so smrt. :rolleyes:

I have a m/s quantity, and the values are too small for short edges. To compensate for this, I could divide by edge length, but then I get a s-1 quantity. Wtf is that? Hertz?

And then I realized: angular velocity!
Title: Re: My Game Engine is too Jittery
Post by: Mika on March 14, 2013, 03:07:22 pm
Would it make sense to allow the crate to sink a bit in the ground? That way, all corners should be touching the ground? I think this would reduce the jitter quite a bit.

Please tell how your modification to the adhesion threshold works out.
Title: Re: My Game Engine is too Jittery
Post by: Aardwolf on March 14, 2013, 04:01:34 pm
Yes, a stable state for these crates will typically involve all four corners of one face being in contact with the ground.

I decided to change stuff a bit... now I have a ContactRegion class which is derived from PhysicsConstraint, which wraps a collection of ContactPoint objects. This may make it easier to do stuff where one ContactPoint "knows about" the shape of the contact region. It also means less edges for my ConstraintGraphSolver to deal with, because they're all bundled together now.

I haven't actually done anything like what I was planning for the adhesion threshold yet, though :blah:
Title: Re: My Game Engine is too Jittery
Post by: Aardwolf on March 15, 2013, 03:34:06 pm
Double-post because update.

Poop. I should've expected this, actually. The adhesion threshold hack-fix for jitter is broken. That's because constraints in my ConstraintGraphSolver can only wake up adjacent constraints, and not themselves... but with the new ContactRegion changes, a lone box resting on the ground is just a single constraint, which evaluates for the first iteration and then stops. It takes multiple iterations for the adhesion threshold to do its thing.

It seems like I have three options here:

Option #1 would probably be the easiest, but it doesn't help me at all as far as eliminating jitter. Likewise for option #2, which I think would only be a little harder.

I already tried a little bit of option #3... my idea was to do make ContactRegion::DoConstraintAction do multiple iterations of ContactPoint::DoConstraintAction for all of the contained ContactPoint constraints, but it turns out I need a lot of iterations for it to be stable, and I can't afford to be doing ~16 iterations for every pair of convex primitives in contact with each other. Maybe if I only did it when it's an isolated ContactRegion constraint? I don't currently have any way to check for that, and it might still end up finishing iteration prematurely.



I don't know if the contact points really need to know about each other after all.

Maybe I need to actually have some sort of buffer zone that I allow the objects to sink into each other a little bit... but with a limit on how deep they can go. I remember when I was using Bullet it had something called margins which I think might have been similar?

I don't know how I would implement that, but it sounds like it might work.
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on May 12, 2013, 06:39:13 pm
Long time no update.

I decided to take a break from the physics, and to go back to trying to achieve Character Physics Happy Fun Time™ by other means.



I made a PlacedFootConstraint which constrains a point on a foot in place relative to another object, and optionally locks the orientation as well. The idea here is that it's much more reliable than the collision-detection + dynamics approach, which was always jittering, or allowing the foot to sink into the ground, or some other stupid thing like that. The exact setup for creating and breaking PlacedFootConstraint instances is still subject to change, but the basic idea is that when a Dood steps, a collision detection callback for the foot will execute, and if my code decides it likes it it will create a PlacedFootConstraint based on the ContactPoint data. Then when the Dood wants to lift that foot off the ground, it will destroy that constraint. Also in theory it will be possible for the constraint to "break" from the physics side, e.g. if the Dood gets hit really hard and goes flying.



I've made a few tweaks to my "cheaty character physics system" since the last time I mentioned it here. Previously, it conserved linear momentum but not angular. Now it conserves both. Here's the gist of the algorithm:

          Compute initial net linear and angular velocity of the Dood
          Dood::DoCheatyPose directly modifies the linear/angular velocity of each bone
          Compute change in net linear and angular velocity, aka "cheaty velocity"
          Dood::MaybeSinkCheatyVelocity has the option to modify the "cheaty velocity", e.g. in order to sink some of it into the ground via the PFCs
          Uniformly distribute the undoing of the remaining cheaty velocity

I believe this should be a good framework to build off of. I expect it will be easier to implement something that works in these terms than something that works in terms of per-joint torques, like I was trying to do before. I think the tiny amount of physical cheaty-ness is worth it.



My original approach (from earlier versions of the cheaty physics system) was to specify an orientation for each joint (and the root bone of the skeleton), and then set the linear and angular velocities of each bone to whatever they need to be to get them into position by the next tick. This technique produces the best out-of-the-box results: if I tell it to do the rest pose, and the PFCs are positioned properly for that, the Dood stands there very nicely... not quite rigid, but it gets the rigid bodies into a state that very nearly matches the pose I gave it.

But my goal is to make it stand and walk on varied terrain. It needs to be able to satisfy any configuration of the feet (within reason), not just the rest pose. And I don't know how to implement that.



One big problem with a per-joint orientation approach is that if there are multiple PFCs, not every configuration of joint orientations is going to be valid (let alone "good"). That is, if I start with one PFC's constrained pos/ori and move through the chain of joints to get to a second PFC, rotating and translating my pos/ori according to each joint, the pos/ori I end up with isn't necessarily going to match the constrained pos/ori of the second PFC.

About a year ago (well before I came up with the cheaty physics system) I experimented with a minimization-based approach to IK, where I told it the goal pos/ori of a foot relative to the pelvis, and it would figure out how to do it. But it was expensive and I had to spread the work over multiple simulation steps. That was good enough when I was telling a foot where to step, but I don't think it will work when there are multiple constraints on the skeleton: I don't think I can rely on this sort of "WIP over multiple simulation steps" solution to be a valid configuration.

Most recently I tried an approach where I just picked a pos/ori for the pelvis bone, and then the knee joint's position is constrained to a circle... and I would then select a point on that circle, and orientations for the two leg bones. But it hasn't been working, and I have no ****ing clue why. I've been reduced to shotgun-programming :( There are a few things I've figured while messing with this approach, though. One, I noticed that my Mat4::FromPositionAndOrientation method transposes the 3x3 rotation matrix portion of the Mat4, while Mat4::FromQuaternion does not. Sorting that one out is going to be a doozy, as Mat4::FromPositionAndOrientation is used all over the place, and I'm pretty sure Mat4::FromQuaternion is too. Second, I've noticed that if I try to tell the per-joint-orientation cheaty physics thing to do an orientation that exceeds a particular joint's rotation limits, bad stuff happens.



I also tried a more forward-dynamics-ish approach where I only modified the velocity data of select bones within the Dood. Specifically, I told the bones of the spinal column to orient to face the "yaw" direction, I told the pelvis to move up, and I told the feet to stay in their PFC-constrained pos/ori. At first this looked like it was going to turn out nicely... but it didn't. It only worked if I kept all the "cheaty velocity" (i.e. MaybeSinkCheatyVelocity changes the linear and angular "cheaty velocity" to zero, so nothing is undone). And anyway it looked much worse "out-of-the-box" than the per-joint orientation scheme.



So uh... I don't know what to do. I'm leaning toward something that uses the per-joint orientation scheme, though.
Title: Re: My Game Engine is too Lame
Post by: z64555 on June 26, 2013, 09:11:01 am
So, ah. Any news there, friend?
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on June 26, 2013, 08:47:22 pm
O HAI!

I wasn't able to make any definite progress with getting the Dood to stand/walk, so I decided I'd come up with a list of stuff I can work on that doesn't depend on the Dood being able to walk... I posted it on my Facebook, but didn't want to post it here because it was turning into a monologue. :blah:

Here's the list:


I've started on making the soldier hold the gun with both hands... I converted an updated version of the soldier model, as well as a newer gun model, and I've set up the relative transform between the gun and each hand. I'm seriously considering making the gun actually be a RigidBody. To that end, I created a new FixedJointConstraint class, and renamed JointConstraint to "SkeletalJointConstraint". And I briefly played around with a collision shape for the gun, but it wasn't very good... either I need to implement compound collision shapes sooner rather than later, or I'll just have to accept that the collision shape doesn't match the actual shape of the object very well.



I've also done a little thinking about my Destructible Terrain rendering, and I thought of something that could significantly improve the performance of it! Currently I have to draw a VBO for each material in each chunk, and they're drawn additively. This works mostly, but on rare occasions the depth test will say the depths for two fragments are "equal" when it shouldn't (because there isn't enough precision in the depth buffer). This results in two polygons' worth of materials being drawn on a single pixel, which means I've got a random double-bright pixel.

My new idea is to draw the whole thing to the depth buffer (technically this is already being done), and then do the per-material additive stuff in screen-space. My fragment shader would use the camera-space coords of the fragment and the depth value that was written there to reconstruct what the world-coords position of the point it's drawing must have been. I can then look up the amount of each material I need in a 3d texture. This will simultaneously improve performance and fix the double-bright pixels nonsense.

But there's a complication: up until now, I've been manually encoding and decoding depth info into an additional 3 color channels instead of using the built-in depth buffer. I know it's possible to get access to a depth buffer from a shader, but I don't know how to set it up. Just yesterday I did some fiddling trying to get it to work the "correct" way, but ultimately I got frustrated and reverted the changes. When I eventually get it working, I think it may also improve the performance of my deferred lighting and shadow-mapping stuff.
Title: Re: My Game Engine is too Lame
Post by: z64555 on July 02, 2013, 07:20:01 am
Sounds good, sounds good. How are your particles rendered? Simple face-to-camera planes, or something volumetric?
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on July 02, 2013, 01:34:51 pm
For the most part my particles are square billboards (so yeah, "face-to-camera planes"). I don't use OpenGL's point sprites because they clip based on the center of the sprite... I'm pretty sure I could control that using a custom vertex shader, but I can't be bothered. I also have "billboard trails" which are ribbony things used for bullet trails, impact spark effects, and blood spurts... those are done as quad strips with the 'wide' axis aligned orthogonal to the camera (by taking the cross product of the along-the-ribbon axis and the from-the-camera axis). The stitching between segments could use some improvement one of these days, but it generally looks decent.

I don't know squat about volumetrics. :ick:

I really don't know how I would go about making particles be affected by lighting. The big reason I want this is because when a particle is in an area that should be shadowed, it currently shows up with full brightness, and that's not very good. The thing is, I'm doing deferred lighting (or shading? not sure) and that means for opaque objects multi-source lighting is considerably simplified. I don't have to do any silly business like selecting the 8 most relevant light sources :) But if I'm going to change how I render translucent stuff so that it can be affected by lighting, I don't have the luxury of being able to do each light in sequence. I could do the select-the-8-lights business, but I'm not very eager too.

I had an idea for something interesting but possibly expensive... I could have something like a normal map on my particles, and do lighting sort of like normal... so the side of a dust particle closer to the light source is brighter, for example. Currently my dust particle texture just has the top lighter and the bottom darker, which looks pretty good from any angle except straight up or straight down... and when it's in shade.



I haven't really done anything this past week, except a tiny bit of "thinking" :( Maybe I'll make some progress on the two-handed-grip business this week. I need to spend less time on Youtube, Minecraft, Minesweeper, and Soldat, and more time working on the game engine.
Title: Re: My Game Engine is too Lame
Post by: z64555 on July 14, 2013, 12:52:11 am
Volumetric particles can have lighting and shading applied to them very easily, trouble is getting a good looking texture on them so that they look like a cloud or puff and not a pokey tetrahedron.

If you're doing raytracing, or shadow volumes, you can detect when a particle is within the shadow volume and tell the engine to turn down the lights.
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on September 25, 2013, 03:34:26 pm
:bump:



Progress!

Holding the gun with both hands

I got the soldier to hold the gun with both hands. The physics of it is working ok, but I haven't got the character pose/animation right yet. More on that in the last section of this post. Also the gun jitters a bit more visibly than I'd like, but I can fix that later.



Shadow maps the "correct" way

I got my shadow mapping to use the built-in depth buffer, instead of what I had been doing before (manually encoding the depth info as a color, then decoding it again). Surprisingly enough, it's actually slower :blah: According to Australian doofus who doesn't like FreeSpace, the ability to read depth values directly from a depth texture (presumably instead of using comparison operations) is a relatively new feature and some older graphics cards may not support it... so maybe it's also the case that the graphics cards that support it may not support it as well as they supported the shenanigans I was doing previously.

But it just makes more sense to use the depth buffer that's already being written to, rather than having a redundant color buffer to store the same data. So I'm going to keep it, even if it's somewhat slower than the color buffers thing. And anyway I was able to get it going faster again by simply decreasing the resolution of the shadow map from 40962 to 20482.

Maybe it would be better to use the depth comparison stuff for the shadow maps, where instead of reading floats from the depth texture, I can only compare the floats to other values. Idunno, I might go back and change it later. I think I will still need to get actual floats from the main depth buffer, even if the shadow map depth buffers can use depth comparison.



Cascaded shadow mapping

After I got shadows working the "correct" way, I made it so it renders 3 different shadow maps, all with the same resolution, but each one covering a larger area centered further from the camera. Then I procrastinated for a day. Then I made it so the deferred lighting (or is it shading?) fragment shader actually uses all 3 of the shadow maps I rendered.

I actually had to reduce the resolution again once I had 3 shadow maps going at once, so now it's down to 10242. It still looks decent, so I'm content to leave it as it is for now.



Enough of this graphics stuff, let's get back to C/PHFT

Character/Physics Happy Fun Time, that is.

Part of my problem, I think, is that I need more animations for my doods. As it is now, my soldier has animations for walking forward and backward, left and right, and turning left and right. But it doesn't account for the normal vectors of the terrain it's stepping on, and it doesn't account for differences in terrain elevation either. I might be able to resolve the normal vectors thing entirely with articulation of the ankle joint, I'm not sure. But to deal with walking up or along a slope I need animations for those things.

But my attempts to make poses or animations where more than one of the Dood's bones would be constrained (e.g. holding a gun with both hands, or standing with two feet on the ground) have all been failures. The way I have things set up, I tell each joint what orientation it should be in, and it will try to do that. But if there's two or more external constraints, I'm specifying more degrees of freedom than I have. Also I have to worry about whether the joint orientations I'm specifying are within the joints' rotation limits. Both of those issues can cause the Dood to tense up and contort himself in strange ways, making the actual bone orientations not match what the pose is telling it to do... which in turn makes editing the pose that much more difficult.

What I need is a tool to create and edit Dood poses and animations. So far I've made a program which displays a Dood, and that's about it. I spent a fair amount of time yesterday trying to plan in advance how the data would be stored for various purposes:


But ultimately it was too much and I didn't end up settling on anything. Maybe I will just make it possible to edit the pose of the Dood, and worry about I/O and formats and stuff once I get that working.



@z64555: Ehhh... dynamic lighting for particles is a low priority.
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on October 17, 2013, 12:53:44 am
It's not programming, per se, but it pertains to the development of this game, so I reckon I'll post it here anyway: progress shots of the soldier model! I redid the jetpack so it has downward-pointing nozzles instead of backward-pointing grills, and I've done some work trying to fill in a lot of the big holes in the model while at the same time trying to keep it looking reasonably flexible.

I'll be doing some more detail-work over time, and eventually I'll try to bake the high-poly mesh onto a normal map for a lower-poly mesh for actual in-game use... as it is now, the poly count is 11640 triangles just for the upper body.

(http://i93.photobucket.com/albums/l77/Aardwolf001/Misc%203D%20Models/nuarmor9tc11shoulder_zps27bbfe33.png)

(http://i93.photobucket.com/albums/l77/Aardwolf001/Misc%203D%20Models/nuarmor9tc11front_zps8aaf974a.png)

(http://i93.photobucket.com/albums/l77/Aardwolf001/Misc%203D%20Models/nuarmor9tc11rear_zpse9cc445d.png)

(http://i93.photobucket.com/albums/l77/Aardwolf001/Misc%203D%20Models/nuarmor9tc11side_zps3994297d.png) < it's a perspective shot, his hand isn't actually that big

(http://i93.photobucket.com/albums/l77/Aardwolf001/Misc%203D%20Models/nuarmor9tc11top_zps86bfb825.png)

(http://i93.photobucket.com/albums/l77/Aardwolf001/Misc%203D%20Models/nuarmor9tc11bottom_zps3e649bd9.png) < no, the in-game version won't be hollow on the inside


On the programming front, I've gotten a little done on the "DoodAnimTool" program, but there's a long way to go with that. It displays a Dood now, and I can select bones using the mouse. Earlier I had it so I could rotate individual joints, but that got broken when I implemented multi-bone selections recently. Next I'm planning to get rotation working again (but with multi-bone selections), and figure out how to impose external constraints (e.g. locking the xform between the two hands gripping a gun, or 2+ feet planted on the ground).
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on January 31, 2014, 02:12:21 pm
:bump:

Progress!

I've gotten the "DoodPoseyTool" aspect of "DoodAnimTool" effectively completed now! I can pose the soldier dood's bones, enable or disable external constraints (e.g. hands gripping the gun, feet locked to the ground, head forward vector matching gun forward vector), and load/save from/to a file of the user's choosing. :D

Also I've converted an updated version of the soldier mesh (skinning is shoddy and the hands are unposed, but whatever; I can improve that later).



Now what?

I still don't know quite how I'm going to proceed. I think it would make sense to split the soldier dood into two parts: upper and lower. The upper part would handle getting the head's and gun's forward vectors to point in the correct direction, while the lower part would handle connecting the chain of bones from one foot to the other. What I haven't worked out is how to split them ... or how to integrate them.



The derpy approach

Probably the simplest solution would be to just pick a pose for "torso 2" (the bone the shoulders and head attach to), the arms, and the head, and use that for everything, aiming by bending the joints between "pelvis", "torso 1", and "torso 2". I've attempted to do this in the FPS engine already, but it's pretty crummy. For some reason the gun forward vector doesn't match the head forward vector, even though in DoodAnimTool it said the total error squared for the whole dood was in the 10-11 range... meaning the angle difference between the directions could have at most been in the 10-6 radians range. So that will need investigating.

Even once the gun/head alignment issue is resolved, the above solution is pretty crummy. I've noticed from studying my own movements that when I "aim" left and right my entire body turns, not just my spine or arms.



The 3x3 grid idea

An idea I've been thinking about doing for a while is to have a 3x3 grid of poses for everything "pelvis" and up, and lerping between them to control the direction the head & gun aim. However, as I just mentioned, IRL your pelvis doesn't stay in one pos/ori when you sweep your aim left/right. Maybe I could do something where it comes up with the pelvis xform first (logic for this will be non-trivial), then transforms the "forward" vector (computed from pitch/yaw values) into the pelvis' local coords and looks up that value in the 3x3 grid? I don't know.
Title: Re: My Game Engine is too Lame
Post by: z64555 on February 01, 2014, 06:48:28 am
The 3x3 grid idea

An idea I've been thinking about doing for a while is to have a 3x3 grid of poses for everything "pelvis" and up, and lerping between them to control the direction the head & gun aim. However, as I just mentioned, IRL your pelvis doesn't stay in one pos/ori when you sweep your aim left/right. Maybe I could do something where it comes up with the pelvis xform first (logic for this will be non-trivial), then transforms the "forward" vector (computed from pitch/yaw values) into the pelvis' local coords and looks up that value in the 3x3 grid? I don't know.

This is where a control system comes in handy, You'd essentially feed the horizontal angles into the system, and it'll determine if it needs to reposition the legs to get a 'comfortable' delta between the pelvis and the shoulders. For a simple discrete system, you'd define a range of angles where the pelivs won't reorient towards the forward vector, and outside of this range it'll lerp towards the correct pose in the 3x3 grid. For left and right strafing, another range of angles can be set to keep the forward vector 90 degrees to the direction your strafing. In a situation like this, a dual-input, three-curve, single-output fuzzy logic type setup might be helpful.
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on February 01, 2014, 02:55:54 pm
Just to clarify, the idea of the 3x3 grid was that I specify the aim direction relative to the pelvis, and it uses that to look up what orientations to use for all the joints above the pelvis.



The algorithm would be something like this:
Code: [Select]
Upper body imposes limits on possible pelvis xform, based on aim direction
For each leg:
    Leg imposes limits on possible pelvis xform, based on PlacedFootConstraint/anticipated collision with ground
Select pelvis xform

Look up upper body joint orientations based on pelvis xform and aim direction
For each leg:
    Look up leg joint orientations based on pelvis xform and PlacedFootConstraint/anticipated collision with ground

Obviously I have very little idea how I would actually implement everything up to and including "Select pelvis xform" :blah:



From my IRL observations, at least when standing still, it seems that any change in the gun/head yaw will involve a change in the pelvis orientation. I think as far as the condition for "aim direction is too far to one side; pick up a foot and turn in place" goes, I might as well compare the aim direction to something like the average forward direction of the feet, rather than the pelvis. I'm not sure where in the above algorithm decisions of that nature would go; I'm thinking either before everything, after everything, or in the second "for each leg" block.



Edit for minor update: I've patched/fixed the issue where the head and gun forward vectors matched in DoodPoseyTool but not in the actual FPS. Turns out it's using the joint positions from the UberModel instead of the ModelPhysics. For now I've copied over the more up-to-date joint position data over from the ModelPhysics. In the long term, I will probably make it so that any joint which is in both uses the ModelPhysics's position.


Edit for slightly bigger update: I got that 3x3 grid thing working :D I ended up triangulating the grid quads because it's a heckuva lot easier that way. The range of motion is quite limited, so the pelvis is going to need to do a lot of the work of orienting to face different directions (especially up/down). Still, progress!
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on February 21, 2014, 03:48:36 pm
I'm completely stumped. Help me, Internet!
Title: Re: My Game Engine is too Lame
Post by: Cobra on February 25, 2014, 12:25:05 am
Smoke weed, get inspiration?
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on February 28, 2014, 11:50:51 pm
Haha... no.



Minor update, no real progress:

I'm considering ditching my custom PlacedFootConstraint foot/ground interactions and going back to plain old ContactPoint. The reason I originally decided to make a custom Constraint subclass was because I wanted stable contact between the feet and the ground, and none of the fiddling I was doing with the physics could get ContactPoint contact to actually be stable.

But PFCs have their own problems I've been unable to figure out how to resolve: they need conditions for when to break, both as demanded by the animation system, and in reaction to the physics (e.g. if something really big hits the player and they ought to go flying, the PFC can't stay active). And I haven't been able to come up with reasonable conditions for that. So I've got a Dood whose feet weld themselves to the ground every time he lands, and if he steps on something light-weight like the leg of a bug it's bad news.

Also occasionally I get crashes when disposing the PhysicsWorld, but that's probably because I've done something stupid, so I don't feel it's fair to hold it against PFCs in a PFC-vs-ContactPoint discussion.



Possible strategy

I've got a little bit of an idea for how I might implement the lower body stuff for the Soldier Dood. It occurred to me today that if the xform of the pelvis and the foot are both constrained and moving the pelvis makes it impossible to solve the pose, then it is time to separate the foot from the ground. So I put together a little bit of pseudocode based on this.

Code: [Select]
have a "desired velocity"
x,z components are based on forward and sidestep controls
y component is based on terrain slope? and jump control
constrain pelvis pos/ori:
pelvis moves by a velocity somewhere between the desired velocity and the current average velocity of the dood
pelvis yaws a little to help the aim yaw
pelvis moves forward/backward to balance the aim pitch (and maybe pitch the pelvis up/down a little as well?)
for both feet:
if the foot is grounded:
try to solve the knee IK to keep it grounded
if the foot is not grounded, or if the knee IK fails:
find a landing place for the foot
if landing place found:
move foot toward the landing place (but also up)
foot moves at about 2x the dood's average velocity
else if override (e.g. sprint or jump):
move foot forward anyway?

I reckon it has the best chance of working using the PlacedFootConstraint setup and with the cheaty no-angular-momentum stuff enabled. I'd like to disable that if possible, and I'd prefer a ContactPoint solution over the somewhat hackish PFC system, but I don't know if that will be possible.

Does this seem like a reasonable approach? Any oversights or complications I should worry about?
Title: Re: My Game Engine is too Lame
Post by: Cobra on March 01, 2014, 12:17:13 am
I still suggest weed.
Title: Re: My Game Engine is too Lame
Post by: Nuke on March 01, 2014, 01:46:21 am
I still suggest weed.

weed is good, but i cant say ive written many lines of code in a stoned state.

instead may i suggest crystal meth.
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on March 01, 2014, 04:40:08 pm
Quit it guys :mad2:
Title: Re: My Game Engine is too Lame
Post by: z64555 on March 02, 2014, 09:05:55 pm
So, you've got two analog control inputs for the feet control, the x and z desired velocity, and a couple of digital controls for the y - posture and jump.

Final velocity of the feet depend on the x and z slope of the terrain, and the y velocity is simply a product of the desired velocities and the terrain slope angles. If you set up your cheaty system to directly set the x and z final velocities to what is desired, then you'll get the hackish behavior of basically ignoring the terrain beneath it (worse-case: climbing a sheer wall with a y velocity of infinity).

Everything else seems like a good hypothesis for now.  :yes:
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on March 03, 2014, 05:14:32 pm
Not sure what you mean by analog and digital here. My control state has floats ranging [-1, 1] named "forward" and "sidestep", but for now these are always { -1, 0, 1 }. My Dood has floats "pitch" and "yaw". Pitch ranges from -π/2 to π/2. Yaw is periodic every 2π... although I'm not 100% sure it's properly symmetric for +/- 2π. Jumping is currently a boolean but I plan to change it to some sort of timer, so that if when you press it it starts crouching and then when you release it it starts moving upward... and have special behavior for long presses, or particularly short ones.

I'm not using a simple heightfield here, so determining "terrain slope" is nontrivial.



Beginning to plan additions to existing classes, etc. ...

Code: [Select]
per-foot/leg stuff:

end effector info?
position
required normal vector (or just "down"?) (optional)

out-of-contact timer

cached proposed footfall
bone position (and orientation?)
object to step on?
ETA?
required ground clearance?

virtual methods:
solve leg IK
find suitable footfall
pose ungrounded leg (with or without a planned footfall)

Code: [Select]
dood stuff:

virtual methods:
compute desired velocity
set root bone xform

new "jump timer" behavior
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on March 12, 2014, 07:49:32 pm
Bad Chemistry

Welp, progress has stalled due to bad brain chemistry.

Specifically, me being afraid to start yet another thing that won't pan out. Also, cycling between "This is too hard, maybe I should just do it the cheaty way", "I still don't know how to proceed", and "It would be so much cooler if I could do it without cheating".



Hmm

I did some experimentation with the posey tool to see what range of pelvis xforms I can have given a constrained xform between the feet. Unfortunately all I really learned is that the Soldier's rest pose is not the best point to start from. The rest pose has the knees almost straight, and the feet fairly close together. I think a pose with the knees slightly bent and the feet spaced and angled a little further apart would make for a better "default" pose. I say "default" rather than "rest" because at this point I really don't want to bother having to change the model, joints, and collision shapes. So the "rest" pose will continue to be the pose in which the mesh, joints, and collision shapes are defined, and the "default" pose (assuming I act on these observations) will be something other than "all joint orientations are the identity quaternion".

Maybe I will try the experiment again starting from a better pose.

I also noticed that I can actually get the gun's forward vector a lot closer to the upper torso's forward vector (instead of always having to aim left, like a right-handed archer); I just have to put the gun right at the hip, not half-way between hip and shoulder. The revised version of the gun model with the cut-off stock will also help with that, since there's less "the gun is intersecting the player mesh" to worry about.
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on April 24, 2014, 04:51:34 pm
Video bumpage! Because maybe generating more interest in the project will get someone to help me with ideas!

Title: Re: My Game Engine is too Lame
Post by: Flipside on April 28, 2014, 02:34:44 pm
That is simultaneously awesome and hilarious...

Makes me think of Space Harrier for some reason...
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on May 12, 2014, 06:27:47 pm
Joint-torque-based movement progress!

I made some very simple control logic to orient the head the way I want it. This was probably the simplest task of all the joint torque stuff I'm going to have to do, because there's only one joint that affects the head's orientation, and I can compute the solution analytically. This setup seems to work fine as long as the desired head orientation is actually reachable.



Arm control partially working!

Here's what I came up with:

Each bone has a desired orientation. I compare that with the current orientation to get the angular velocity necessary to get it to that orientation by the next tick, then compare that with the current angular velocity to get the angular acceleration necessary to get it to that velocity by the next tick, and then finally multiply by the moment of inertia to get the net torque I need. It's math I already know how to do, but it still took several tries to get the signs right, and the order of the quaternion ops.

So I know what net torque I want on each bone, but the thing I have control over is the torque applied at each joint. It's a 3-component vector which has to be within a certain OBB, the bounds of which I'm still tweaking. Each joint applies a positive torque to the "parent" bone and the opposite torque to the "child" bone, e.g.: the wrist applies the positive torque to the lower arm, and the opposite torque to the hand. By picking the right values for the joint torques, I can set the net applied torque on each bone, which determines the angular velocity of the bones prior to going through the constraint solver. But when the solver runs, it changes the linear and angular velocity of everything, and the thing I'm interested in controlling is the angular velocity after the solver runs.

There's no simple formula I can use to go from the actual net torque I want to the net applied torque necessary to produce it. Running the constraint solver to test a proposed solution is too expensive to be feasible. Also it may not even be 100% deterministic, because I'm using pointers as hash values. For now I've approximated and said "net applied torque = actual net torque", and it seems to work, sometimes.



So what's left?

I've got to make a few improvements to the posey system I'm using to come up with bone orientations—the 3x3 grid of poses I mentioned a while ago. For one thing, it can't aim straight up (or even reasonably close). I've also noticed some odd behavior as it switches between different triads of poses to interpolate between. That and the orientation it's suggesting for the gun is sometimes noticeably off from the direction it's supposed to be aiming. It needs some work.

I don't yet know what will make good values for the joint torque limits, but I'm fairly certain they won't be the same for all axes of all joints, so I'm going to want to make them configurable. Maybe I'll add that as an optional field for my ModelPhysics-builder utility function.
Title: Re: My Game Engine is too Lame
Post by: bobbtmann on May 15, 2014, 06:26:35 pm
I enjoy seeing the updates you post of your engine, though I'm not a very good programmer so I can't offer any advice. It's looking really good, though. Are you planning to build any games with it?
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on May 17, 2014, 05:53:31 pm
@bobbtmann: Maybe calling it an "engine" in the thread title was misleading. Although I am trying to develop things in a way that will let me reuse a lot of the code, there's only one active project using the engine, and that's the FPS where you fly around with a jetpack and shoot giant space bugs.



Minor Progress Update!

The Dood can now aim straight up and straight down! Also I've now got the spine joints' torques working properly, and the Dood is now anchored by its pelvis instead of the upper torso. It could probably use a few tweaks, but it's mostly working.

There's only one major task left before I can say C/PHFT is working (for the Soldier, at least). Unfortunately it's the hardest part: the legs, and the foot/ground interaction.
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on June 16, 2014, 07:42:13 pm
Bleh. I'm stumped again/still.

Somehow I've gotta make a function that takes the Dood's state and some parameters specifying some "goals" for it, and from that selects torques to exert for each lower-body joint to exert. The goals will probably be expressed as a desired linear and angular velocity for the pelvis and for each foot.

I could assign a score to a state, or to a transition between states, scoring based on factors like...

Problem. In some situations a series of "bad decisions"1 could cause the Dood to "back itself into a corner", where no possible output would let it satisfy the requests. Minimizing joint torque might help a little with this, since more torque applied amounts to more torque that might potentially need undoing later. Idunno.

Hypothetically for any input state I could do a lot of iterations to try to find the set of output torques with the best score2. So I could call that the "correct" solution, and feed that to something like a neural network as training data. I reckon that would take too long to train, might be too slow at runtime, and would probably need to be redone any time I change some tiny aspect of the problem (e.g. modifying the Soldier's collision shape).

Also neural nets hate me.




1Bad for the reason stated, but presumably good enough at the time, or good enough according to a poorly designed scoring function
2This is complicated somewhat by the fact that the constraint graph solver is not 100% deterministic, because I use objects' pointers as the hash function for those objects. The per-tick differences are tiny, but the cumulative effect can be significant. Understatement.
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on July 02, 2014, 09:51:18 am
Upper Body Stuff Working!
(i.e. what I had about a month ago)




Maybe another video featuring giant alien brambles soon. If it's before this gets any replies I might edit it into the post (I don't want to quadruple-post, even if it's because I have updates), so watch out.

Edit: remember to "like" the video (if you liked the video).

Brambles video probably not coming as soon as I hoped.



Edit II: Giant Alien Brambles!
Title: Re: My Game Engine is too Lame
Post by: Aardwolf on September 06, 2014, 02:14:19 pm
Not really an update, but I've started a topic on gamedev.net about this with the hope that maybe someone there will be able to save this project.

http://www.gamedev.net/topic/660671-motor-control-for-physics-based-character-movement/

 :sigh: