Déterminer si le point A doit couper un coin pour atteindre le point B

Je cherche un moyen efficace de vérifier si un objet va couper un coin pour aller du point A au point B ou empêcher l'objet de bouger du point A au point B s'il y a une position diagonale non échangeable entre les deux.Déterminer si le point A doit couper un coin pour atteindre le point B

ce qui est connu:

Chaque point est un carré de largeur et de hauteur 1
Chaque point a une liste de ses 8 points adjacents
Un point peut être soit praticable ou nonwalkable

Voici quelques exemples (a est la source, b est le desination et X est un point unwalkable):

aX 
b

Dans le cas ci-dessus, a ne peut pas marcher à être parce qu'il ya un point unwalkable adjacent à la fois le point et le point ab ... donc, pour cette affaire, b devient unwalkable de a (c.-à-a doit se déplacer vers le bas avant de procéder à b)

ce qui suit est un cas similaire, en ce sens que a ne peut pas marcher à b:

aX 
Xb

La façon dont je le fais au moment devient l'ensemble des points adjacents orthogonalement des deux points A et le point d'intersection B et ces deux ensembles. S'il n'y a pas d'éléments dans le résultat recoupé, le point A peut atteindre le point B.

... et cela fonctionne.

Mais est-il, peut-être ainsi, plus mathématique et efficace d'y parvenir?

Source

2010-08-09 Andreas Grech

Alors qu'est-ce que ça ressemble si elle est accessible à pied? Vous voudrez peut-être montrer comment aller de A -> B. –

Ce n'est pas pertinent. Je veux seulement savoir s'il est possible de passer de A à B. –

Je suppose que vous ne souhaitez dans le cas où b est l'un des un « un voisin, et seulement en diagonale adjacente. Ce serait

if ((abs(a.x - b.x) == 1) && (abs(a.y - b.y) == 1))

Maintenant, dans ce cas, nous avons juste besoin de vérifier les deux points adjacents aux deux.

if ((abs(a.x - b.x) == 1) && (abs(a.y - b.y) == 1)) { 
    if (blocked(a.x, b.y) || blocked(b.x, a.y)) { 
     // unwalkable 
    } else { 
     // walkable 
    } 
}

Vous pouvez bien sûr fusionner les instructions if.

Source

2010-08-09 12:30:12 deinst

small fix: ... || bloqué (b.x, a.y) –

Doh! Je suis un membre payant de l'ADN, l'association nationale des dyslexiques. Je le réparerai. – deinst

depuis la réponse ci-dessus suppose que les cellules à vérifier sont des voisins, vous pouvez simplement vérifier si elles sont en diagonale à l'autre au lieu de deux en diagonale et à côté de l'autre. De cette façon, vous pouvez raser une comparaison supplémentaire.

if (abs(a.x - b.x) == abs(a.y - b.y)) {

au lieu de

if ((abs(a.x - b.x) == 1) && (abs(a.y - b.y) == 1)) {

Source

2010-08-11 13:21:01

Déterminer si le point A doit couper un coin pour atteindre le point B

Répondre

Questions connexes