💾 Archived View for it.omarpolo.com › articoli › prim-e-labirinti captured on 2024-06-16 at 12:27:42. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

Prim e i labirinti

Qualche anno fa un me più giovane e ingenuo si apprestava allo studio di alcuni algoritmi in preparazione di un’esame. C’erano da ripassare diversi algoritmi sui grafi, e ricontrollando alla veloce su wikipedia rimase colpito da una GIF nella pagina dell’algoritmo di Prim: la generazione procedurale di un labirinto.

L’algoritmo di Prim viene usato per trovare il “minimum spanning tree” (wikipedia italia li chiama “alberi di supporto minimi”) di un grafo. Informalmente, un grafo è un insieme di punti, detti nodi, che possono essere collegati tra di loro con delle linee, detti archi. Questi archi possono essere “a senso unico” (e quindi si dicono orientati) oppure no, e opzionalmente possono anche avere un peso (o “costo”) associato. I grafi sono incredibilmente utili per modellare molte tipologie di problemi, e sono generalmente molto intuitivi come rappresentazione.

I grafi possono contenere dei “cicli”, ad esempio il seguente grafo contiene un ciclo su A-B-C

A-------B
 \     / \
  \   /   \
   \ /     D
    C

In molti ambiti la presenza di loop non è cosa gradita, e quindi sono stati sviluppati diversi algoritmi per “rimuovere” alcuni archi, in modo che tutti i nodi siano comunque raggiungibili, solo senza loop. Ad esempio, ecco una copia del grafo di prima senza cicli:

A-------B
 \       \
  \       \
   \       D
    C

Ma cosa ha a che fare tutto questo con i labirinti? L’idea di fondo è che una “griglia” come la seguente può essere vista come un grafo

┌─┬─┬─┬─┬─┐
├─┼─┼─┼─┼─┤
├─┼─┼─┼─┼─┤
├─┼─┼─┼─┼─┤
└─┴─┴─┴─┴─┘

dove gli “incroci” sono i nodi e le linee sono i gli archi. Quindi possiamo applicare l’algoritmo di Prim (uno di questi algoritmi per trovare il minimum spanning tree) per ottenere un labirinto. Ancora meglio: ci sono prove matematiche che il labirinto che otterremo avrà uno e un solo percorso due punti qualunque.

Ma ora saltiamo avanti di qualche anno e arriviamo a ieri, una domenica mattina. Avevo deciso di provare a scrivere qualcosa di piccolo, possibilmente semplice, e questo “generatore di labirinti” mi è tornato in mente. Ho quindi aperto il mio game engine preferito e poco tempo dopo, con del codice da paura — in senso negativo — il generatore era pronto.

L’algoritmo di Prim funziona in questo modo:

viene impostata la proprietà “chiave” a infinito per ogni nodo, e una proprietà π a ⊥
la “chiave” del nodo di partenza viene posta 0
si considerano i nodi uno alla volta, in ordine crescente in base alla “chiave”
per ognuno di essi, si considerano gli archi uscenti e si aggiornano i costi dei nodi (se inferiori), e impostando il parametro π in tal caso
alla fine si ha un minimum spanning tree

Alla fine è possibile ricostruire il minimum spanning tree consultando soltanto l’array π. Se π[v] = w significa che il nodo w è stato aggiunto dal nodo v, e che quindi il nostro albero risultante avrà l’arco v → w.

Nel mio caso, avendo a che fare con un grafo “a matrice” mi sono permesso (anche colpa la mia pigrizia) di deviare leggermente da quella che è la formulazione standard dell’algoritmo. Non ho ancora fatto nessuna analisi della complessità, nè tanto meno della correttezza, ma a occhio sembra funzionare, e logicamente sembra convincente.

Come dicevo, ho implementato il tutto con Godot, un motore di gioco libero.

Ah, e in pieno stile “game-developer” il codice è tutto confuso, scritto coi piedi, alla veloce e senza commenti. Siete stati avvisati.

In ‘Maze.gd‘, come variabili globali ho definito:

extends Node2D

# dimensioni della mappa
export (int) var height := 6
export (int) var width := 6

# metadati
var _maze := []
var _queue := []
var _edges := []            # ovvero π
var _edges_weight := []
var _cost := []             # ovvero C
var _found := []

Ho cercato di seguire al meglio della mia memoria la formulazione dell’algoritmo come presente nel libro di Cormen, quindi ogni nodo è identificato da un numero, e i vari “metadati” non sono altro che array. Quindi, per accedere al costo del nodo v basta accedere a ‘_cost[v]’. Sì, se dovessi riscrivere il tutto adesso avrei usato un unico array di dizionari probabilmente, ma anche così non è male alla fine.

Per pragmaticità ed efficenza il grafo viene rappresentato con una lista di adiacenza (l’array ‘_maze’ contiene le liste degli archi uscenti per ogni nodo.)

Dato che la mappa è organizzata su una griglia ma i nodi hanno identificativi numerici ho definito una funzione per ottenere l’id date le coordinate:

func _xy_to_idx(x: int, y: int) -> int:
	return y * width + x

Il contrario è possibile, e molto semplice anche:

var x := int(floor(idx % width))
var y := int(floor(idx / width))

Il generatore viene inizializzato in questo modo:

func _maze_initialize() -> void:
	var size := width * height

	_edges.resize(size)
	_edges_weight.resize(size)
	_maze.resize(size)
	_cost.resize(size)
	_found.resize(size)

	for i in size:
		# inizializza le liste di adiacenza
		_maze[i] = []
		_edges_weight[i] = []

		var x := int(floor(i % width))
		var y := int(floor(i / width))

		# computa gli archi uscenti
		if x > 0:
			_maze[i].append(_xy_to_idx(x - 1, y))
		if x < width - 1:
			_maze[i].append(_xy_to_idx(x + 1, y))
		if y > 0:
			_maze[i].append(_xy_to_idx(x, y - 1))
		if y < height - 1:
			_maze[i].append(_xy_to_idx(x, y + 1))

		# da un peso casuale ad ogni arco in uscita
		for t in _maze[i].size():
			_edges_weight[i].append(randf())

	for i in size:
		_cost[i] = 999

	for i in size:
		_found[i] = false

All’algoritmo serve poter estrarre da un insieme di nodi uno con il costo minore. Ci sono diverse strutture che si potrebbero usare, ma per semplicità ho scelto di usare un classico e inefficiente scan seriale su tutta la lista:

func _queue_min() -> int:
	var m = null
	var idx := 0
	for i in _queue.size():
		var e = _queue[i]

		# alla prima iterazione m è null!
		if m == null or _cost[e] < _cost[m]:
			m = e
			idx = i

	# rimuovi l’elemento dalla lista
	# prima di ritornarlo
	var t = _queue[idx]
	_queue.remove(idx)
	return t

Ora manca soltanto il cuore dell’algoritmo. La definizione data nel Cormen e anche su Wikipedia richiede — forse per una buona ragione — che la lista dei nodi inizialmente li contenga tutti. Mi sono permesso di attuare una piccola modifica: i nodi vengono aggiunti alla lista man mano che vengono “scoperti”. Nella mia versione, l’algoritmo assomiglia di più a un BFS. La motivazione è stata cercare di compensare l’O(n) di ‘_queue_min’ in qualche modo: estrarre di volta in volta l’elemento col costo minore da una lista non ordinata facendo uno scan seriale “puzza” da soluzione quadratica; se invece la lista è popolata man mano che viene scoperta nel caso peggiore rimarrà comunque quadratico, ma ho delle chance che il caso medio sia meno mediocre.

func _maze_create() -> void:
	# forza il primo nodo in alto a sinistra ad essere
	# quello di partenza
	_cost[0] = 0
	_found[0] = true
	_queue.append(0)

	while _queue.size() != 0:
		var v := _queue_min()
		_found[v] = true

		for i in _maze[v].size():
			var w: int = _maze[v][i]
			var c: float = _edges_weight[v][i]
			if not _found[w] and c < _cost[w]:
				_cost[w] = c
				_edges[w] = v

				# XXX: personalizzazione!  Aggiungi w alla lista
				# sol quando viene “scoperto”
				_queue.append(w)

E questo è tutto l’algoritmo. Prim è infatti relativamente semplice da realizzare, efficiente nel computare — almeno nella versione da libro di testo, con le mie modifiche non ho ancora pensato ma probabilmente è peggio. A questo ci ho aggiunto una TileMap per disegnare i muri, un paio di sprite libere scaricate da kenney’s e il risultato è qualcosa del genere:

Anteprima del labirinto [PNG, 68K]

Si ringrazia poi Riccardo, aka MarriX, per aver sistemato il progetto. Appena gliel’ho mostrato si è subito messo a ri-organizzare il codice, riscrivere un menu iniziale, aggiustare le luci e via dicendo. È diventato proprio un game-developer coi fiocchi, poverino.

Abbiamo anche avuto qualche idea su come poter “completare” il tutto in qualcosa di giocabile; magari ci sarà un futuro update!

$BlogIt: index.gmi,v 1.1 2021/10/20 07:43:19 op Exp $