#### ChessMasterRiley

##### Member

Hello all!

I am trying to build a distance map for a 2D grid using the Fast Marching Method and I'm hoping to get feedback/suggestions for my algorithm in case I'm missing something to speed it up (whether the calculation itself or the way I am storing/referencing the data). I do understand this isn't a "cheap" process, but I am trying to make it as efficient as possible. I know Djikstra's is a bit faster, but I need the Eikonal solutions because I am building a vector field from this and Djikstra's only creates 8 discrete directions when creating the vector field (really only 4 except for the Cartesian directions around the goal cell).

Here is my process (with timer benchmarks for building the cell grid and for calculating the distance map):

Here is my code to visualize the results:

And finally, here is the resulting representation of the distance grid:

It appears to be working just fine, but I would be incredibly grateful for any suggested performance boost suggestions. This is a 100x100 grid and it is taking roughly 50-60ms to build the grid of cells and populate neighbors and then 700-750ms to perform the distance calculations. In practice, I'll be chunking these calculations so I only have to calculate on a few chunks when the map changes, but I'm trying to weed out any stupid mistakes in my method up front.

YYC only provides negligible improvements.

Implemented from: http://www.numerical-tours.com/matlab/fastmarching_0_implementing/

and: https://canal.uned.es/uploads/material/Video/49784/Presentaci__n_Luis_Moreno.pdf

and: https://jvgomez.github.io/files/pubs/fm2star.pdf (source paper)

If anyone smarter than me can understand this "heat method," this may be a better choice...http://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/index.html

Thank you for your time!

I am trying to build a distance map for a 2D grid using the Fast Marching Method and I'm hoping to get feedback/suggestions for my algorithm in case I'm missing something to speed it up (whether the calculation itself or the way I am storing/referencing the data). I do understand this isn't a "cheap" process, but I am trying to make it as efficient as possible. I know Djikstra's is a bit faster, but I need the Eikonal solutions because I am building a vector field from this and Djikstra's only creates 8 discrete directions when creating the vector field (really only 4 except for the Cartesian directions around the goal cell).

Here is my process (with timer benchmarks for building the cell grid and for calculating the distance map):

GML:

```
//timer/benchmarking variables
var _t,_start,_stop;
_start = get_timer()
//initialize grid variables
width = 100
height = 100
cell_size = 8 //just for drawing purposes
cell_grid = ds_grid_create(width,height) //contains cell data
distance_grid = ds_grid_create(width,height) //grid to hold distance values
start_x = 0 //starting point for wave propagation
start_y = 0
//establish enum for cell arrays
enum cell
{
x = 0,
y = 1,
cost = 2,
neighbors = 3
}
//create cells and fill cell_grid with data
var i,j;
for (i=0;i<width;i++)
{
for (j=0;j<height;j++)
{
var c = array_create(4)
c[cell.x] = i
c[cell.y] = j
c[cell.cost] = 1
c[cell.neighbors] = ds_list_create()
ds_grid_set(cell_grid,i,j,c)
}
}
//add neighbors to cells
for (i=0;i<width;i++)
{
for (j=0;j<height;j++)
{
c = cell_grid[# i,j]
if i > 0 ds_list_add(c[cell.neighbors],cell_grid[# i-1,j])
if j > 0 ds_list_add(c[cell.neighbors],cell_grid[# i,j-1])
if i < width-1 ds_list_add(c[cell.neighbors],cell_grid[# i+1,j])
if j < height-1 ds_list_add(c[cell.neighbors],cell_grid[# i,j+1])
}
}
//timer/benchmarking
_stop = get_timer()
_t = (_stop - _start) / 1000
show_debug_message(string(_t)+"ms to fill grid and assign neighbors to cells")
_start = get_timer()
//create a priority queue for frontier and a list for already calculated cells
var frontier = ds_priority_create()
var closed = ds_list_create()
ds_grid_clear(distance_grid,infinity) //clear distance grid
distance_grid[# start_x,start_y] = 0 //set start location distance to 0
//add starting location to closed list
var start = cell_grid[# start_x,start_y]
ds_list_add(closed,start)
//add neighbors of start location to frontier queue
var neighbor;
for (i=0;i<ds_list_size(start[cell.neighbors]);i++)
{
neighbor = ds_list_find_value(start[cell.neighbors],i)
ds_priority_add(frontier,neighbor,neighbor[cell.cost])
}
var i,current,distance,dx,dy,delta;
var left,right,top,bot;
while !ds_priority_empty(frontier) //loop through all cells in frontier until empty
{
current = ds_priority_delete_min(frontier) //get lowest cost cell in frontier queue
//get distances of neighboring cells
left = distance_grid[# max(0,current[cell.x]-1),current[cell.y]]
right = distance_grid[# min(width-1,current[cell.x]+1),current[cell.y]]
top = distance_grid[# current[cell.x],max(0,current[cell.y]-1)]
bot = distance_grid[# current[cell.x],min(height-1,current[cell.y]+1)]
//calculate Eikonal distance
dx = min(left,right)
dy = min(top,bot)
delta = 2*current[cell.cost] - sqr(dx-dy)
if delta >= 1
{
distance = (dx+dy+sqrt(delta))/2
}
else
{
distance = min(dx+current[cell.cost],dy+current[cell.cost])
}
//update distance grid
distance_grid[# current[cell.x],current[cell.y]] = distance
//add neighbors to frontier queue if they are not already calculated (part of closed list)
for (i=0;i<ds_list_size(current[cell.neighbors]);i++)
{
neighbor = ds_list_find_value(current[cell.neighbors],i)
if ds_list_find_index(closed,neighbor) = -1
{
ds_priority_add(frontier,neighbor,distance+neighbor[cell.cost])
//add neighbor cell to closed list so we don't add to frontier again
ds_list_add(closed,neighbor)
}
}
}
//destroy frontier and closed to avoid memory leak
ds_priority_destroy(frontier)
ds_list_destroy(closed)
//timer/benchmarking
_stop = get_timer()
_t = (_stop - _start) / 1000
show_debug_message(string(_t)+"ms calculate fast marching distance")
```

GML:

```
var i,j,value,color,size,half_grid;
size = cell_size
draw_set_font(fnt_main)
for (i=0;i<width;i++)
{
for (j=0;j<height;j++)
{
value = ds_grid_get(distance_grid,i,j)
color = merge_color(c_black,c_red,abs(sin(value/2)))
draw_set_color(color)
draw_rectangle(i*size,j*size,i*size+size,j*size+size,0)
}
}
```

It appears to be working just fine, but I would be incredibly grateful for any suggested performance boost suggestions. This is a 100x100 grid and it is taking roughly 50-60ms to build the grid of cells and populate neighbors and then 700-750ms to perform the distance calculations. In practice, I'll be chunking these calculations so I only have to calculate on a few chunks when the map changes, but I'm trying to weed out any stupid mistakes in my method up front.

YYC only provides negligible improvements.

Implemented from: http://www.numerical-tours.com/matlab/fastmarching_0_implementing/

and: https://canal.uned.es/uploads/material/Video/49784/Presentaci__n_Luis_Moreno.pdf

and: https://jvgomez.github.io/files/pubs/fm2star.pdf (source paper)

If anyone smarter than me can understand this "heat method," this may be a better choice...http://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/index.html

Thank you for your time!

Last edited: