Tous droits réservés

Tester si deux tranches horaire se croisent

Marche aussi pour tester la collisions dans les jeux vidéos en 2D

Bonjour à tous ! :)

Nous allons voir dans le très court billet comment savoir si deux tranches horaires se superposent.

Imaginons donc deux tranches horaires :

  • La première qui va de A1 (heure de début) à A2 (heure de fin)
  • Le seconde, qui va de B1 (heure de début) a B2 (heure de fin)

Comment feriez-vous ?

Titre

C’est facile ! Si B1 est entre A1 et A2, ou que B2 est entre A1 et A2, alors il y à supperposition !

C’est bien essayé, mais ce n’est pas tout à fait exact.

Si on fait un petit schéma, cette solution fonctionne dans les cas suivants :

Schéma où cela fonctionne
Schéma où cela fonctionne

Mais cela ne fonctionne pas pour ce cas-ci, où les tranches horaires entrent pourtant en collision :

Cas où cela ne fonctionne pas alors que ça devrait
Cas où cela ne fonctionne pas alors que ça devrait

Afin de trouver la meilleure solution, faisons un schéma de tous les cas possibles.

Tous les cas possibles
Tous les cas possibles

Si on regarde ce schéma, on peut voir que dans les deux premiers cas, il n’y a pas de collision, alors qu’il y en a dans tous les autres cas.

Je vous propose donc de prendre le problème à l’envers : Faisons une conditions pour savour où il n’y à PAS de collision.

Il n’y a pas collision si la deuxième tranche horaire est trop à gauche de la première, ou trop à droite de la première.

Le pseudo-code associé serait donc :

SI B2 INFERIEUR A A1 OU QUE B1 SUPPERIEUR A A2 ALORS
    PAS DE COLLISION
SINON
    COLLISION
FIN
Titre

C’est bien joli tout ça, mais moi je voulais savoir quand il y avait collision !

Et bien nous avons juste à inverser la condition !

SI PAS (B2 INFERIEUR A A1 OU QUE B1 SUPPERIEUR A A2) ALORS
    COLLISION
SINON
    PAS DE COLLISION
FIN

Et voilà ! :magicien:



J’espère que cette petite astuce vous aura été utile !

Sachez également que cela fonctionne pour tester les collisions entre deux rectangles dans un jeu en 2D. Il suffit d’ajouter l’axe vertical dans la condition, et le tour est joué !

16 commentaires

Quelques remarques cependant :

  1. Ça ne fonctionne que si des paires (A1, A2) et (B1, B2) sont ordonnées.
  2. Dans le cas de données temporelles, il faut s’assurer que les données utilisées sont réellement comparables entre elles.
  3. L’écriture donnée contient une double négation (SI PASSINON) et la condition négative du test donne un résultat positif, ce qui est assez pénible à comprendre. On devrait pouvoir simplifier la condition et écrire quelque chose du genre – sauf erreur de ma part :
collision = (A1 < B2) et (A2 > B1)

Ce qui est plus lisible et au moins aussi efficace (sauf cas pathologique).

collision = (A1 < B2) et (A2 > B1)

Ce qui est plus lisible et au moins aussi efficace (sauf cas pathologique).

SpaceFox

J’ai pas regardé si c’est juste, je te fait confiance. :p Mais dans ce cas, ne pas oublier la condition "égale". Sinon, 13H-14H ne sera pas en collision avec 14H-15H (sauf si c’est ce que l’on veux).

Sinon, oui, j’ai considéré que les dates sont valides. Mais disons que ce billet était là pour donner une "théorie". Après, c’est à appliquer selon les langages et outils de dates utilisés.

+0 -0

Ce qui est bien c’est que le schéma montre les tests unitaires à faire pour assurer le fonctionnement de la méthode :)

artragis

Et pour bien faire les choses, il faudrait deux versions des tests : une première avec des valeurs d’exemples et une approche en property based testing (puisque les règles s’appliquent quelque soit les valeurs des plages).

La première permet d’avoir des jeux de données d’exemples. La seconde de valider les propriétés de l’algorithme.

Et ça révèlerait des cas limites mettant à mal l’algorithme. Comme le cas d’une plage couvrant minuit (i.e. 22h-4h par exemple)

Et ça révèlerait des cas limites mettant à mal l’algorithme. Comme le cas d’une plage couvrant minuit (i.e. 22h-4h par exemple)

Mzungu

Ça typiquement, c’est pas un problème d’algorithme mais le problème de type de données temporelles dont je parlais ci-dessus.

On parle de tester si deux plages horaires se chevauchent ou se recouvrent.

Et pour pouvoir simplifier des expressions comme PAS (B2 INFERIEUR A A1 OU QUE B1 SUPPERIEUR A A2) ce qu’on utilise ce sont les lois de De Morgan.

Ici @SpaceFox n’a pas strictement appliqué les règles puisqu’il a considérer que la négation de B2 < A1 est A1 < B2 ce qui est vrai seulement si on ne regarde pas le cas où A1 == B2.

Je tique aussi sur le sous-titre:

Marche aussi pour tester la collisions dans les jeux vidéos en 2D

Ce n’est pas vrai. Ça ne marche que pour des rectangles en 2D.

+3 -0

Et pour pouvoir simplifier des expressions comme PAS (B2 INFERIEUR A A1 OU QUE B1 SUPPERIEUR A A2) ce qu’on utilise ce sont les lois de De Morgan.

Je ne connaissais pas, merci pour l’info ! :)

Je tique aussi sur le sous-titre:

Marche aussi pour tester la collisions dans les jeux vidéos en 2D

Ce n’est pas vrai. Ça ne marche que pour des rectangles en 2D.

C’était pour avoir un sous-titre plus court, mais je précise bien dans la conclusion que cela fonctionne que pour les rectangles.

Sachez également que cela fonctionne pour tester les collisions entre deux rectangles dans un jeu en 2D. Il suffit d’ajouter l’axe vertical dans la condition, et le tour est joué !

(et puis ça fait des click ! :D )

+2 -0

🤣 🤣 🤣

On dirait un contrat d’assurance.
Ça promet des gros truc dans le titre et en tout petit en bas, dans un coin ça se défile.

+2 -0

En soit ça marche aussi dans les jeux 3D avec des cubes : faut juste check l’intervalle de profondeur en plus.

artragis

En soit ça marche aussi dans les jeux à n-dimensions avec des hypercubes de dimensions n : faut juste check pour chaque dimensions en plus.

+3 -0

C’est hors sujet mais voici un jeu en 4 dimensions (j’ai réussi à le manipuler) et son petit frère en 5 dimensions (qui lui dépasse les capacités de mon cerveau).


PS : si dans le cas du Rubik’s Cube (les jeux ci-dessus) ajouter des dimensions complexifie le jeu, ça n’est pas toujours le cas. Par exemple la version 3D du 2048 est beaucoup plus simple que la version standard en 2D, parce que la dimension supplémentaire fait qu’on est beaucoup moins bloqués.

Avec une procédure de tri, on peut éviter des cascades de 'IF’, machine à bug… Par exemple :

def croise(a0,b0,a1,b1)
  l=[[a0,1],[b0,1],[a1,2],[b1,2]].sort 
  return !( l[0].last == l[1].last && l[1].first<l[2].first )
end


p true==croise(5,10,5,10) 
p false==croise(5,10,1,4)
p false==croise(5,10,20,30) 
p true==croise(5,10,10,30) 
p true==croise(10,20,0,10) 
p false==croise(20,10,9,0) 
p true==croise(5,10,6,7) 

Autre fantaisie :

def borne(min,max,value) 
  return [min,value,max].sort()[1] 
end

p borne(0,100,50)
p borne(0,100,200)
p borne(0,100,-1)
p borne(100,0,50)

+1 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte