Come gestire oggetti di dimensioni diverse in una situazione di ricerca percorso (A *, A-star)

Question

Sto lavorando a un gioco che utilizza A-star (A *) per trovare percorsi ma sono arrivato a un punto in cui da Ho alcuni oggetti che sono più grandi di un singolo quadrato della griglia.

Sono in esecuzione su una griglia di 16 * 16 px. i segmenti di muro sono 16 * 16 e quindi rendono invalicabile un singolo quadrato. Alcuni dei miei nemici sono 32 * 32 e quindi hanno bisogno di verificare che un gap sia largo almeno 2 quadrati per essere in grado di superarlo.

Non riesco a creare la griglia 32 * 32 perché il progetto richiede pareti sottili (a 16px) e ci sono un paio di cattivi più piccoli che occupano solo un singolo 16 * 16 quadrati.

Come implementare questo ambiente a risoluzione multipla? La stella A è ancora lo strumento corretto da utilizzare?

Answer 1

http://aigamedev.com/open/article/clearance-based-pathfinding/

Answer 2

Per una soluzione relativamente semplice, Vorrei aderire alla stessa A * algoritmo da per 16x16 oggetti di dimensioni ma con un modo leggermente diverso per valutare se un quadrato è percorribile o no.

• Un oggetto di dimensioni 16x16 può camminare su un quadrato se quel quadrato è calpestabile.
• Un oggetto di dimensioni 32x32 può camminare su un quadrato se quel quadrato ei suoi vicini sono tutti percorribili.