Discussion :

[Greg L.]

Bonjour à tous,

A titre personnel, je travaille actuellement sur un projet de jeu par navigateur web et je ne sais pas s'il existe un algorithme générique permettant la détection d'obstacle sur une grille donnée.

Concrètement, j'ai une unité qui attaque et qui a une certaine portée, ainsi qu'une unité cible. Le tout étant que l'unité attaquante ne puisse lancer son attaque que s'il n'y a pas d'obstacle entre elle et sa cible.

Existe-t-il un algorithme simple pour résoudre ce problème ?

Pour information, le plateau de jeu est de dimension réduite (grand maximum 20x20 et les portées à l'avenant, disons 5 cases maximum)

Merci beaucoup !

[nouknouk]

salut,

je pense que la façon la plus simple de faire serait que ton code trace une 'ligne virtuelle' entre le tireur et la cible afin de connaître l'ensemble des cases que le projectile traversera. Ensuite, pour chacune des cases, tu peux vérifier si c'est un obstacle ou pas.

Pour un algo en particulier pour le 'traçage de ligne virtuel', tu peux par exemple te baser sur l'algo de Bresenham.

[Greg L.]

Merci pour le tuyau. C'est ce que j'avais déjà trouvé sur la question, mais je vais essayer d'optimiser ça, si c'est possible, pour des zones restreintes.

[icer]

Pour l'optimisation de ce genre de tache, les algorithmes de partitionnement de l'espace sont trés efficaces. Mais peut-être que ton plateau de jeux est trés petit et qu'un algorithme bourrin suffit.