Recorrer una matriz en espiral

[Windgate]

Espiral no es el nombre exactamente: El caso es que en mi juego de droides quiero que sean capaces de detectar objetivos en el tablero de juego según su proximidad. Para ello necesito recorrer la matriz "en espiral" desde su posición localizando así el objetivo más cercano.

Necesito un algoritmo que pueda recorrer la matriz en un orden similar a este:

Por ahora tengo el algoritmo que la recorre por cuadrados, pero para grandes distancias los objetivos en las diagonales pierden mucha preferencia.

Ahí queda el peludo problema xD

EDIT: Cualquier recorrido distinto pero que se haga "en círculos" me servirá aunque no sea exactamente igual a lo de la foto :P

[laghengar]

podrías chequear todos los que están dentro de la distancia acordada, y luego ver cuál de ellos es el que está más cerca.

[Windgate]

Podría valer, pero me interesa mucho la eficiencia.

Tras hacer unas pruebas dibujando circunferencias sin suavizado con el Paint.NET de radio 3, 5, 7, 9, etc. Observé que el problema es el mismo, es un problema trigonométrico y creo que lo mejor es ir trazando radios alrededor de los 360 grados y chequeando la celda a la que se llega en cada momento.

El problema de lo anterior es que dependiendo de la longitud del radio hay que chequear bien sea avanzando de 30 en 30 grados (Circunferencia pequeña) o bien grado a grado, incluso menos de un grado cada vez para circunferencias grandes.

En cualquier caso, la eficiencia se resiente mucho así que por el momento lo tengo solucionado recorriendo cuadrados en lugar de círculos, no es "perfecto" pero me por ahora me sirve.

No obstante, si alguien tiene algún algoritmo mejor se agradecerá.

[SplinterGU]

yo te suguiero que uses mapas de bits, o sea, 8 celdas por byte... o 32 celdas por int... de esta forma llenas tu tablero... si tu rango es radio 16 celdas, solo chequeas 32 (o 64 bytes en el caso donde estes cerca de los limites) y verificas que si alguno de esos bytes es diferente de 0, entonces significa que hay algun robot en las proximidades, con lo que ahi si haces un analisis mas profundo del tablero...

se optimiza mucho... es chequear 64 contra 169 chequeos y seguramente hay mas variables en juego en el metodo de 169.

[Windgate]

Oh, entiendo lo que dices, es como dicotomizar... Como tener un clon "mini" del tablero donde realizar chequeos sencillos antes de acceder finalmente al tablero.

A ver si saco un rato y lo pongo en práctica, karma++

[laghengar]

Eso lo usé y ayuda, pero bueno, luego pensé en poner en la casilla un color que corresponda con la id del proceso, así leyendo el color, vas directamente al proceso.

No se si se podría hacer hasta ahí no llegué. Ya que en ese momento me comí mucho la cabeza para conseguir que los personajes no se solaparan y hiciesen una búsqueda de camino teniendo en cuenta a los personajes ya colocados en el mapa, y bueno cuando logré que sortearan los obstáculos me di por satisfecho :P

[Windgate]

Todavía no me he puesto con la búsqueda de caminos, no me gusta nada la eficiencia que tiene y el límite de tablero. Ahora mismo mi tablero tiene 400x400 celdas y path_find resuelve 100x100, más creo que no...

Lo de dibujar colores con las ids de proceso me parece buena idea para poder dejar en el disco el resultado del "encuentro"... Lo pensaré.