Coder Corner

Played a bit more with Recast. It rocks so far.

I wonder if I could use the Recast nav-mesh with PathEngine?? Sounds like best of both worlds if Detour has some limitations. For example I don’t know yet if it handles dynamic obstacles very well.

The world is cut into several regions connected by portals. I think I will end up generating one nav-mesh per region. Then if a pathfinding query goes from point Pa in region Ra to point Pb in region Pb, I can always split the query into several sub-queries: first from Pa to the portal connecting Ra and Rb, then from the portal to Pb. Or maybe Recast’s “tiled” mode can do the trick directly.

Not sure how to handle moving platforms yet.

I tried Recast on ONI’s level 10. Seems to Just Work! This was all generated by clicking a button.

• Overview
• Closeup 1
• Closeup 2
• Closeup 3
• Closeup 4

I guess it’s time to try “Detour” to actually do some pathfinding queries on those meshes.

EDIT: first successful pathfinding queries done with “Detour”. Just Worked. Yay!

Some more Recast notes:

My characters use capsules with radius = 4.0 and total height = 15.0. After some tweakings I got the best results with those build parameters.

The cable holes on the ground are gone. But they did not disappear when changing the “walkable climb” value. They disappeared when changing the “cell height” from 0.2 to 0.7.

EDIT: the next paragraph is BS, see the comments.

On the other hand I still have troubles with cable holes in the small “command center”, somewhere else in that level. The nav mesh here would look very reasonable without that big hole in the middle. I didn’t manage to get rid of it. Admittedly the UI does not expose all parameters yet (like “max edge length”) and maybe playing with that one will do the trick.

I see troubles with the “walkable radius” otherwise. Even though I use the actual radius from my character’s capsule, the nav mesh misses some connections, areas that can definitely be crossed by the player. Reducing the “walkable radius” helps a bit but not much, since it’s quantized to an integer value internally. So I decrease the value a bit in the UI, nothing changes, repeat that a few times, until suddenly a big change happens because the internal code clamped the float to the next integer. Would be cool to be able to fine-tune this better.

Admittedly that mesh is not very friendly with all those narrow passages. But hey, real-world meshes tend to be painful to library developers - tell me about it!

To be continued, I will post more results after exposing the last build params to the UI.

EDIT: done! Tweaking the remaining params did not significantly change the results.

John Ratcliff told me about a new pathfinding library named “Recast“. It’s open source and it looks pretty good. I am currently using PathEngine in Konoko Payne. That’s a powerful library but it has one big problem for me: navigation meshes have to be created by artists. Since I am the only “artist” in this project, it has always been a huge pain in the butt to open MAX and manually, painfully, create the nav meshes. I more or less did it in KP’s prototype, but never even started for the “real” level (especially since the level is “under construction”. No way I’ll spend time creating a nav mesh for a level which might change the next day).

So the biggest appeal for “Recast”, to me, is that it automatically builds nav meshes. I have no idea about the runtime performance or memory requirements yet, but for me this single feature makes it worth checking.

So, I did.

Pretty simple API, seems to work as advertised. Didn’t test it much yet but seems to work, and it’s fast.

• This picture is what I get on KP’s “Depot” level. That’s what you get out of the box, without much parameter tweaking. Pretty good.
• Only problem I see is that some cables on the ground end up creating big holes in the nav mesh, for some reason. I don’t know why yet. I don’t know if it can be easily solved by tweaking the build parameters a bit more. In any case this is a non-issue, I can simply filter those triangles out of the building process.
• Here are the build parameters I used. You can open this from KP’s console and build everything while the game is running. So far, so good. This is one big step towards releasing KP’s source code. I couldn’t do it before since PathEngine’s license prevented it, but now everything’s possible! (I just have to replace the physics engine, duh!)

(to be continued)

Check your codebase if you don’t believe me. I posted this months ago on GDA but never found the time to make a proper note. And you know what? I still don’t have the time. Check the GDA archives for more information.

In short: the code solving the quadratic equation suffers from limited FPU accuracy and returns “no intersection” while there definitely is one. “Best” fix is to move the ray origin closer to the target sphere. See this small repro case for details.

It’s not a theoretical problem only, it happened in Konoko Payne when sniping a far away enemy with a Mercury Bow.

So, there. Off my TODO list, stupid item!

Oh you gotta love those absolutely non provocative titles.

I only use AZERTY keyboards. I’m useless with a QWERTY (or worse, the swiss QWERTZ). Each time people tried to use my PC in the office, they sat down, typed for 10 seconds, stopped, looked confused, looked down at the keyboard… and asked me why the hell I wasn’t using a “normal” keyboard.

So, for the records: the AZERTY keyboard (or at least the AZERTY layout, I guess none of you still looks at the keyboard while typing, right?) is more efficient for coding, because it gives you the best of both worlds:

- if you want to type a number, you can use the numeric keypad on the right. Sorry guys, I know a lot of you hate it and just never use it, but hey, I grew up with this thing typing hexadecimal numbers from source code published in magazines. Trust me: for entering a lot of numbers at the same time, nothing beats the keypad.

- if you want to type a bunch of symbols widely used while programming, like:

& ” ‘ ( ) - _ = ! :

…well they are all available without pressing SHIFT. All of them. Compare this to the QWERTY layout which “wastes” keys by having “redundant” direct entries for all the numbers. Forcing you to press SHIFT much more often than AZERTY users.

So, AZERTY, less SHIFT pressing, better.

What do you mean you’re not convinced ?!

Here is a small “character slicing” demo that I was working on recently. It started as an innocent discussion at work. Somebody asked if it would be technically possible to cut a character at runtime with an arbitrary plane, and have the cut pieces continue using the character’s animation file for some frames, before going ragdoll. Some people said “forget it” because of the huge amount of work involved. I said “yes you can”, and then went ahead and proved it:

www.codercorner.com/Code/CharacterCutDemo.rar

The demo was made at home in the evenings, using an old Unreal character. Here is a video featuring a more modern character:

http://www.codercorner.com/Movies/CharacterCut.avi

There is a ridiculous amount of steps in this algorithm, although all of them are relatively simple. On top of my head:

• do software skinning for one frame, to get access to the character’s geometry
• cut the graphical mesh with a plane. This creates new vertices and triangles.
• compute new vertex data for the new vertices. You can lerp your way out of troubles for position / UVs / normal(s) / colors, but you can not interpolate the skinning data, so you need something else to figure out bone IDs and weights.
• triangulate the hole(s) you just created in the character’s surface. Replicate boundary vertices, compute new vertex data for those.
• optional: update vertex colors so that the vertices nearby the cut plane get a red tint.
• re-split the character for HW rendering (e.g. see “Skin Splitting for Optimal Rendering” in GPG6). When using HW skinning the character has already been cut to several batches, each batch using a limited number of bones depending on HW constraints. The nasty thing is that you can not cut each batch individually, as it creates troubles later on when triangulating the holes. So you need to put the skin back in a single batch, cut it, then re-split it according to HW limits.
• slice the bones’ bounding volumes. This may only work with boxes and convexes, as a sliced sphere or capsule gives you a non-trivial shape that your physics API might not support. Recreate physics shapes for cut volumes.
• duplicate physics bodies across the cut line. One issue here is that a vertex on one side of the cut plane might still reference bones located on the other side. So you need to choose between either fixing all the (now) invalid bone references in the vertex buffer, or let the bones exist as ghosts on the other side of the plane. Both approaches have pros and cons.
• disable joints across the cut line. Some subtleties here.
• create two new skins with the newly created graphics data, skinning data and physics data…
• optional: add extra effects like particles or blood spats, and sounds

I’m glossing over a fair amount of minor details and potential refinements, but that’s the rough road map.

Sometimes I forget why ICE is the coolest engine ever. I was working with another engine and this happened:

Object3D* some_object;

delete some_object;

and then of course it immediately crashes somewhere because of some stupid container still containing the pointer:

std::vector<Object3D*> mSomeContainer;

Fair enough, vanilla stuff. Still, it’s been years since I last saw such a primitive crash in ICE. Because my non-STL, non-standard-compliant, “ugly” containers are still smart enough to remove the dead pointers from themselves, automatically! Hell, I even forgot I had that feature. It’s been the backbone of the whole engine, for about 9 years now… I can savagely delete any “managed” object anywhere anytime, and the underlying kernel just fixes up whatever needs fixing.

STL, meh! The industry couldn’t even standardize matrix conventions between D3D and GL, everybody has to re-learn the company’s custom, in-house matrices / points / quaternions / whatever anyway. Maybe they should standardize this instead of somewhat trivial containers.

There was this line in some code:

#include <cruntime.h>

…and I was reading “include crunch time”. I must be tired

I’m so tired of those 2D height field fluids. Iguana did it in Heartquake 14 years ago, and people are still rediscovering them, reinventing the wheel, marketing them as new things, or proudly showing them off as the results of their “research”. Gimme a fucking break! It was cool the first time. And then everybody copied it from Iguana. In 1996 it was already dead boring, the horse had been beaten over and over again for 2 years. It’s almost 2009 now, can we move on? Please?

Soon they’ll give us shadebobs and keftales!