La tua griglia 2D ha ovviamente N ^ 2 punti.
Il caso peggiore in assoluto è che l'euristica indirizza sempre erroneamente l'algoritmo, quindi l'algoritmo evita il punto di destinazione. Con A *, ciò può accadere con una serie estremamente complessa di ostacoli, in modo che il tentativo di spostarsi verso l'obiettivo sia generalmente una strategia di ricerca non valida.
È possibile costruire una mappa in cui l'unica via verso il target visita ogni singola cellula non bersaglio prima del raggiungimento della destinazione. Avendo costruito quella mappa, puoi rimuovere le barriere che non influenzano in realtà il modo in cui l'algoritmo cerca (l'algoritmo fa ancora la stessa ricerca anche con quelle barriere rimosse) per consentire superficialmente più libertà, tuttavia quella libertà non è mai sfruttata.
Fondamentalmente, ciò significa che il caso peggiore è quadratico - l'algoritmo può cercare ognuna di quelle cellule N ^ 2 prima di trovare il bersaglio.
Un modo per migliorare l'algoritmo è usare una misura della distanza che è sensibile alle barriere - non solo come le mosche-corvo. Ovviamente se l'unica rotta verso il target richiede la visita di ogni cellula che non fa differenza, ma l'euristica è molto meno probabile che indirizzi male la ricerca se c'è una certa libertà di scelta.
Il problema è che ottenere una misura perfetta della distanza è tanto complesso quanto trovare comunque il percorso perfetto verso l'obiettivo. Tuttavia, puoi precomportare una distanza minima possibile per ogni cella se il bersaglio si trova sempre nello stesso punto e utilizzarlo come tabella di ricerca più tardi.