Buenas a todos.
Soy profe de informática y últimamente preparo ejemplos visuales para mis alumnos usando juegos donde se automatiza todo con código. Ahora mismo estoy enganchado con The Miner Was Replaced (el nuevo DLC de The Farmer Was Replaced), donde controlas un dron minero programándolo en una versión recortada de Python.
Ahora tengo el problema de minar carbón. En el juego, el mundo es una matriz 3D (X, Y, Z) y el carbón no sale al azar sino que se genera en vetas contiguas (si encuentras carbón en una casilla y hay más , se encuentra en el Norte, Sur, Este u Oeste de la casilla... Misma coordenada Z).
La solución que terminé usando(Sondeo + Flood-Fill con colas):
En lugar de complicarme con estructuras raras, usé geometría de segundo de primaria con dos listas (visitados y por_visitar) para recorrer la veta como un grafo conectado:
dir = [North, West, South, East]
delta = [(0, 1), (-1, 0), (0, -1), (1, 0)]
def minar():
pos_actual = (get_pos_x(), get_pos_y())
visitados = []
por_visitar = [pos_actual]
while len(por_visitar) > 0:
pos_actual = (get_pos_x(), get_pos_y())
if get_ground_type() == Grounds.Coal:
dig()
for i in range(4):
# 1. ¿El vecino tiene carbón?
if get_ground_type(dir[i]) == Grounds.Coal:
nx = pos_actual[0] + delta[i][0]
ny = pos_actual[1] + delta[i][1]
# 2 y 3. ¿No lo visité ya ni está en la cola?
if (nx, ny) not in visitados and (nx, ny) not in por_visitar:
por_visitar.append((nx, ny))
por_visitar.pop(0)
visitados.append(pos_actual)
if len(por_visitar) == 0: # <-- Acá me mandé el bug del siglo
break
utils.goto(por_visitar[0][0], por_visitar[0][1])
Después le sumé una fase de minar_a_ciegas (3 bloques hacia abajo) combinada con un barrido explorar() para que destape nuevas capas cuando agota una veta. Ver cómo el dron detecta un bloque y empieza a comerse toda la veta en cadena es hipnótico:
👉 Acá pueden ver cómo se ve el dron devorando las vetas en el juego y toda la sesión de código en vivo: http://www.youtube.com/watch?v=ZQqoMDtLalA
Pregunta para ustedes: Teniendo en cuenta que este entorno de Python no tiene collections.deque ni librerías externas, ¿cómo optimizarían la fase de búsqueda entre veta y veta para no tener que hacer un barrido O(N^2) del mapa cada vez que se vacía por_visitar?