Sunday, August 27, 2017

Fast Marching Method pursuit

I've been experimenting to learn more about the fast marching method, which is a really nice way of generating distance fields that take into account cost fields.

First, FMM is used to compute a signed distance field to the obstacles (the dark gray boxes). This distance field is the basis for a cost field, which is then used by FMM for computing distance from the mouse cursor. The cost field smooths the paths around corners, which makes it easier for groups to avoid getting snagged.

The red shading represents the cost function, while the contour plot represents the cost-influenced distance field to the mouse cursor. The orange dots move downhill on this field to approach it.

I think this is roughly similar to the "FM2" method outlined by Alberto Valero-Gomez et al. My cost-from-obstacle-distance function is totally ad hoc though. I still need to dig up the real math for that.