Hi, do you have any recommendation for Distance Transforms (for Distance Fields computation of volume)? I'm looking into implementing Distance Transforms but I'm very noob at this. I will get it sorted out eventually. Just thinking maybe you have some advice. Perhaps in the form of some library?

A little bit on what my plan is: I have already a set of OpenCL functions which implements pathfinding that is based on Potential Fields (computed from gradients of distance fields of "obstacles" and summed with other contributing fields). This part I had done before getting into PolyVox. Now I'm trying to get PolyVox to work with that. My plan is to extract some sort of information from the Volume, similar to the SurfaceExtractors. I'm sorry I can't say exactly what I'm going to extract because like I said, I don't even know how to generate distance transforms. Well, that's the plan, extract the information from the Volume, then compute the distance transform from that using what I'm going to implement with OpenCL. After that, I can pass this data to my A.I functions.

I would like to add maybe computing distance transforms in order to do path-finding may not even work. I'm not sure what I want yet. I'm also thinking of using NavMesh and run the mesh that is generated from PolyVox through that. I'm not sure whether that will work.

Hi,

If you want to compute a distance transform then you should look into 'distance propagation' methods. These are fast but maybe not that accurate. You can improve on this with the slower 'vector propagation' techniques. I don't think I have an actual library for you though and I haven't implemented it into PolyVox.

How3ever, the problem with distance fields is that the whole thing can become invalid if one voxel changes in the volume. And I think a 256^3 one takes a couple of seconds to compute. You can probably improve on this if you only want it to be locally accurate - I'm not sure though.

As for other ideas, I think Recast Navigation uses some voxel based internal format. Maybe you can hook into that but again I doubt if it's real time.

Otherwise maybe subsample the volume to a lower resolution and just use something conventional like A*?

Sorry I can't be more helpful, I don't have much experience with AI...

Maybe I will do that, downsample and use A*.

Today I thought maybe I could compute the distance function from the noise function. I simply say that above certain value returned from my noise function implies that it is impassable (due to larger value of gradient on the Y), and the distance value would be threshhold - current_value. Wait, the problem is with dynamic content... Hmm. Maybe I'm going scale down my vision and just limit the type of AI that I have in mind to certain precomputed areas. Then for everywhere else I can think those places as wilderness and have random dumb mob AIs. Doing everything I wanted is going to be hard.

Thanks.

Yeah, this is basically the biggest problem. You need to rely on as few data stuctures as you can, and those that you do rely on need to be updated in realtime (or spread out over a few frames).

Maybe you could instead attach 'feelers' to each character in the form of raycasts in several directions? Raycasts at least are fast through volume data. This can stop AI walking into walls but doesn't give them much sense of direction.

Yep, tricky problem

Well I'm going to try A* for global pathfinding and RVO2 for local avoidance. The reason I looked into distance map in the first place is because I wanted to try something new, I wanted to try Potential Field based methods. I don't actually need it. A* should work.