¿Cómo encontrar todos los lugares posibles para ir en una cuadrícula?

Dada la cantidad de pasos que puede tomar en una grilla, ¿cómo podría implementar una forma de get todos los lugares posibles a los que puede llegar una unidad, en un juego como Advanced Wars?

Actualmente, tengo la búsqueda de ruta A * funcionando, pero sería bueno tener un indicador de los posibles lugares a los que ir. Me he vinculado a una image para aclarar las cosas.

Estaba pensando en calcular la ruta de cada una de las fichas de la cuadrícula al mosaico de la unidad, y luego lo estoy resolviendo a partir de ahí, pero me imagino que eso requerirá grandes cantidades de resources.

Observe cómo las otras unidades 'bloquean' la ruta de la unidad seleccionada. Por lo tanto, desafortunadamente no es un "dibujar un círculo con radio X" trivial

Observe cómo las otras unidades 'bloquean' la ruta de la unidad seleccionada. Por lo tanto, desafortunadamente no es un "dibujar un círculo con radio X" trivial

Breadth First Search puede calcular cada location accesible desde una position de inicio, y también puede contar cuántos pasos para esa location. (Si algunos pasos toman más "movimientos", entonces use el Algoritmo de Dijkstra en su lugar). Vea la cuarta demostración en esta página . Le diría al algorithm que pare después de un número de movimientos, para que no siga explorando el rest del map. En esta image lo detuve después de 5 pasos:

Primera búsqueda de amplitud limitada a la distancia 5

Solo tiene que modificar su implementación A * para salir cuando no queden baldosas aceptables y save todas las fichas que cumplan la condición.

Comience como de costumbre y establezca un valor de MaxCost (es decir, la distancia máxima que la unidad puede caminar). A continuación, itere los posibles mosaicos para ir y agregue los que son pasables y cuyo costo es menor o igual que MaxCost a una list. El algorithm finaliza cuando no quedan fichas vecinas con un coste de desplazamiento inferior o igual a MaxCost.