ah ok, c'est du 2d... ben je sais pas, par exemple si ta distance est |x-x'|+|y-y'| et que tu essayes de chercher des grands rectangles vides, tu peux simplifier le graphe

x-x-x-x-x-x-
| | | | | | 
x-x-x-x-x-x-
| | | | | | 
x-x-x-x-x-x-
| | | | | | 

qui a n*p sommets et 2 n*p arêtes en le graphe

x-x-x-x-x-x-
| | | | | | 
x- - - - - -
| | | | | | 
x- - - - - -
| | | | | | 

qui a n+p sommets et 2(n+p) arêtes

mais je ne sais pas du tout à quoi ressemblent tes niveaux, combien d'objets sont mobiles, etc... donc je ne sais pas si ça s'applique vraiment ^^