Comment concevoir un algorithme pour générer un tracé de voie ferrée aléatoire mais valide ?
https://cs.stackexchange.com/questions/117972
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je me demande si j'ai la quantité C de pistes courbes et la quantité S de pistes droites, comment je pourrais concevoir un algorithme (assisté par ordinateur ou non), pour concevoir un tracé "aléatoire" utilisant toutes ces pistes, tel que les règles suivantes sont satisfait:
1) Les voies, lorsqu'elles sont toutes connectées, forment une boucle fermée (continue) que le train peut contourner.
2) Les rampes, les virages des voies, les bosses des voies, les croisements de voies ne sont pas autorisés.
3) C et S seront tous deux des nombres pairs.Un exemple serait C=20 et S=10.Notez qu'il faut 12 courbes dans la même orientation pour réaliser un cercle complet de 360 degrés, donc au moins 12 de ces courbes doivent être orientées de la même manière pour compléter les 360 degrés.Les autres peuvent « zigzaguer » tant que le résultat net est de 360 degrés pour que le train fasse une boucle complète.
Les pistes droites mesurent environ 10 pouces (25,4 cm) de long et les pistes courbes mesurent environ 12,4 pouces (31,6 cm) de long (au centre, en suivant la courbe) et s'incurvent à 30 degrés.Les « attaches » sur les rails ont une largeur maximale de 3 5/8 pouces (9,2 cm).J'ai placé un rail droit et un rail incurvé l'un sur l'autre et j'ai mesuré que la courbe de 12,4" (31,6 cm) avait 12" (30,5 cm) de longueur linéaire (dans la même direction que la ligne droite) et 3" (7,6 cm). de virage (dans le sens perpendiculaire de la droite).Un cercle 12C a un diamètre de 47,5" (120,6 cm) du centre au centre des pistes sur les côtés opposés.
Toutes les mesures sont approximatives.
MISE À JOUR
J'ai re-mesuré les pistes en utilisant beaucoup plus d'entre elles pour aider à éliminer les erreurs et, à ma grande surprise, la longueur des lignes droites n'est PAS de 10 pouces, elles semblent être d'environ 9,78 pouces.Cela a un impact significatif sur la correspondance des courbes en zigzag avec les lignes droites.Au départ je pensais que 4 courbes en zigzag = 5 lignes droites mais ce n'est pas tout à fait exact.4 courbes ont environ 47" de distance linéaire, donc 5 lignes droites à 9,78" chacune feraient 48,9", près de 2 pouces de plus.L’astuce consiste donc à trouver le LCM (Least Common Multiple) de 47 et 9,78.Il s'avère que c'est 235.235 = 47*5 et 235/9,78 = 24,028...(assez proche).Cela signifie que 20 courbes en zigzag équivalent pratiquement à 24 lignes droites en longueur linéaire.Heureusement, j'ai 26 suites donc j'ai à peine réussi.Les 2 restes peuvent facilement être positionnés ailleurs dans l’aménagement.
Une autre chose que j'ai découverte est que si je zigzague les courbes 2 avec la même orientation à la fois (OOCCCCOO), alors 8 d'entre elles ont une distance linéaire de seulement 83 pouces, et non de 94 pouces comme si j'alternais les courbes (OCCOOCCO).Le LCM de 83 et 9,78 est d'environ 166.Ainsi, 16 de ces courbes ont la même longueur linéaire que 17 droites.C'est utile à savoir car j'ai 44 courbes et seulement 26 lignes droites mais si je fais cette substitution, je peux aider à compenser cela.
Si je zigzague les courbes 3 à la fois (OOOCCCCCCOOO) et que je les plie légèrement, je peux obtenir la longueur linéaire exacte de 10 lignes droites (environ 97,8 pouces).
FIN DE MISE À JOUR
Le programme informatique devrait-il donc créer un modèle géométrique et mémoriser les positions exactes de chaque piste ou existe-t-il un moyen plus simple de coder cela ?Je veux pouvoir "appuyer sur un bouton" et l'ordinateur "crache" une "nouvelle" mise en page valide pour moi.
Je veux donner cet algorithme fonctionnel aux enfants qui utilisent les trains, afin qu'ils ne soient pas frustrés d'essayer un tracé qui ne fonctionne pas et qu'ils essaient ensuite de plier les voies pour que cela fonctionne ou de devoir laisser de côté quelques morceaux de voie. parce qu'ils ne correspondent pas.Un ordinateur peut créer un tracé valide en utilisant toutes les pistes et si l'algorithme est bon, peut-être en quelques secondes.Cela vise à éviter toute frustration pour eux.
J'ai quelques compétences en codage, mais je dois d'abord connaître un algorithme avant de pouvoir coder quelque chose de significatif (autre que simplement tester quelques parties d'un algorithme candidat)
Ce que je pense, c'est que je pourrais demander à l'ordinateur de modéliser les pistes en utilisant une représentation plus petite (à échelle réduite).Je pense qu'il pourrait alors simplement "placer" les pistes dans le tracé candidat et vérifier les collisions avec d'autres pistes déjà présentes.
Je pense qu'il existe probablement de meilleures façons de le faire, c'est pourquoi je demande ici de l'aide/des idées.Je veux vraiment que cela fonctionne et j'ai les pistes ici afin que je puisse les utiliser pour vérifier si l'algorithme fonctionne.
Nous pouvons utiliser C=20 et S=10 comme paramètres pour essayer de résoudre ce problème car il s'agit d'un nombre raisonnablement petit de pistes (30 au total).Je suppose que si l'algorithme est suffisamment robuste, les valeurs C et S peuvent être modifiées à volonté et cela fonctionnera toujours.Par exemple, je veux éventuellement essayer C=44 et S=26.
Dernier mot
Merci à tous pour vos commentaires et suggestions concernant cette question.J'ai aussi beaucoup appris.En tant qu'enfant, je n'ai jamais vraiment réfléchi aux voies ferrées et à la façon dont elles s'emboîtent, mais en tant qu'adulte, je peux voir que c'est un problème géométrique fascinant et un problème de comptage mathématique très difficile pour générer/déterminer combien de tracés de voies différents (uniques). il y a.J'espère que vous avez apprécié cet exercice autant que moi.Les enfants l'apprécient aussi.
Fin Dernier mot
La solution
Je pensais proposer la solution par force brute.
L’idée est d’essayer chaque tracé de piste tour à tour.Lors de la construction d’un réseau, seuls trois éléments doivent être pris en compte :une courbe à gauche, une courbe à droite et une ligne droite.
Vous pouvez encoder le tracé des pistes sous forme de nombre en base 3 avec une largeur correspondant au nombre de pièces dans le tracé.Pour énumérer toutes les dispositions de piste, comptez simplement en base 3, où l'encodage est 0=droit, 1=gauche et 2=droite.
L'étape suivante consiste à vérifier que le réseau se raccorde aux deux extrémités.La première vérification consiste à s’assurer qu’il y a suffisamment de courbes pour parcourir un circuit complet.Si nous choisissons un sens anti-horaire pour un circuit, alors 12 courbes à gauche sont nécessaires.Pour chaque courbe supplémentaire à droite, nous devons ajouter une courbe supplémentaire à gauche.Donc, pour vérifier qu'une disposition particulière peut fonctionner, ajoutez simplement le nombre de courbes à gauche et soustrayez le nombre de courbes à droite - cela doit être égal à 12.
Enfin, nous devons vérifier que les deux bouts sont effectivement joints.Nous traçons simplement la piste sur une grille cartésienne.Nous commençons l'origine à [0,0] et si elle se termine à [0,0], alors elle rejoint.
La manière la plus simple de tracer la piste est LOGO style.En d’autres termes, nous maintenons un vecteur directionnel qui pointe dans la direction du dernier morceau de piste posé.Si nous rencontrons une courbe à gauche, faites pivoter la direction de 30 degrés et pour une courbe à droite, faites une rotation de -30 degrés - une ligne droite n'affecte pas la direction.
Pour tracer réellement les courbes et les droites, nous agrandissons le vecteur direction en fonction de la taille de la pièce, c'est-à-dire10 unités pour une ligne droite et 12,4 x 12 / 2 x pi (rayon de la piste circulaire complète) pour une courbe.
AVERTISSEMENTS
En raison d'erreurs d'arrondi lors de l'addition des nombres à virgule flottante, le tracé n'est pas exact.Et dans la vraie vie, nous pouvons laisser une certaine marge de manœuvre pour joindre les deux bouts, il faut donc en tenir compte.
De nombreuses dispositions seront identiques, mais décalées d’une position.Je ne vois pas de moyen d'exclure les mises en page décalées en double autre que de conserver les précédentes et de les comparer.
L'algorithme n'exclut pas les dispositions où les pièces se croisent.Pour ce faire, vous devrez vérifier que chaque pièce d'une mise en page ne croise pas une autre pièce de la mise en page (c'est O(n^2)).Et il faudrait vérifier les croisements courbe-courbe, courbe-droite et droite-droite, et cela commence à devenir très complexe.
Le temps d'exécution de l'algorithme est évidemment O(3^N), ce qui est exponentiel - et probablement peu pratique pour les très grandes mises en page.
Vous trouverez ci-dessous du code VBA que vous pouvez coller dans Excel pour vous donner une preuve de concept.J'ai délibérément essayé de garder le code aussi simple que possible pour faciliter la conversion vers votre langue préférée.Si vous avez des questions, n'hésitez pas à les poser.
Option Explicit
Type Vector
X As Double
Y As Double
End Type
Sub GenerateTrackLayout()
Dim lCounts(40) As Long
Dim lColumn As Long
Dim lTrackLength As Long
Dim lCurveSum As Long
Dim lIndex As Long
Dim lIndex2 As Long
Dim vDirection As Vector
Dim vBase As Vector
Dim vTrackPosition As Vector
Dim fPI As Double
Dim fCurveRadius As Double
Dim fStraightLength As Double
Dim sPath As String
Dim lOutputRow As Long
Const TOLERANCE = 0.5 'inch
lOutputRow = 1
vBase.X = Sqr(3) / 2 ' 30 degrees
vBase.Y = 1 / 2 ' 30 degrees
fPI = 4 * Atn(1)
fCurveRadius = 12.4 * 12 / (2 * fPI)
fStraightLength = 10
lTrackLength = 12 ' initial track length
Application.ScreenUpdating = False
Do
' Check for closed track
lCurveSum = 0
For lIndex = 0 To lTrackLength - 1
If lCounts(lIndex) = 1 Then
lCurveSum = lCurveSum + 1
ElseIf lCounts(lIndex) = 2 Then
lCurveSum = lCurveSum - 1
End If
Next
If lCurveSum = 12 Then ' one 360 degree rotation anti-clockwise
vDirection.X = 0
vDirection.Y = 1
vTrackPosition.X = 0
vTrackPosition.Y = 0
' Plot the track and ensure that ends meet
For lIndex = 0 To lTrackLength - 1
Select Case lCounts(lIndex)
Case 0 ' straight
vTrackPosition = AddVectors(vTrackPosition, ScaleVector(vDirection, fStraightLength))
Case 1 ' left curve
vDirection = MultiplyVectors(vDirection, vBase, 1)
vTrackPosition = AddVectors(vTrackPosition, ScaleVector(vDirection, fCurveRadius))
Case 2 ' right curve
vDirection = MultiplyVectors(vDirection, vBase, -1)
vTrackPosition = AddVectors(vTrackPosition, ScaleVector(vDirection, fCurveRadius))
End Select
' If ends meet within tolerance then output the track
If Abs(vTrackPosition.X) < TOLERANCE Then
If Abs(vTrackPosition.Y) < TOLERANCE Then
If lIndex = (lTrackLength - 1) Then
sPath = ""
For lIndex2 = 0 To lIndex
Select Case lCounts(lIndex2)
Case 0 ' straight
sPath = sPath & "S"
Case 1 ' left
sPath = sPath & "L"
Case 2 ' right
sPath = sPath & "R"
End Select
Next
Application.ScreenUpdating = True
Cells(lOutputRow, 1).Value = sPath
Application.ScreenUpdating = False
lOutputRow = lOutputRow + 1
End If
End If
End If
Next
End If
' Count in base 3 where number width is Track Length
lColumn = 0
Do
lCounts(lColumn) = lCounts(lColumn) + 1
If lCounts(lColumn) = 3 Then
lCounts(lColumn) = 0
lColumn = lColumn + 1
Else
Exit Do
End If
Loop Until lColumn = lTrackLength
' We've tried all tracks of this length, next one up...
If lColumn = lTrackLength Then
Erase lCounts ' reset all columns to zero
lTrackLength = lTrackLength + 1
End If
DoEvents
Loop
End Sub
' Vector maths
Function MultiplyVectors(vVectorA As Vector, vVectorB As Vector, ByVal fConjugate As Double) As Vector
MultiplyVectors.X = vVectorA.X * vVectorB.X - fConjugate * vVectorA.Y * vVectorB.Y
MultiplyVectors.Y = vVectorA.Y * vVectorB.X + fConjugate * vVectorA.X * vVectorB.Y
End Function
Function AddVectors(vVectorA As Vector, vVectorB As Vector) As Vector
AddVectors.X = vVectorA.X + vVectorB.X
AddVectors.Y = vVectorA.Y + vVectorB.Y
End Function
Function ScaleVector(vVector As Vector, ByVal fScale As Double) As Vector
ScaleVector.X = vVector.X * fScale
ScaleVector.Y = vVector.Y * fScale
End Function
Autres conseils
Tout d'abord, un défi de cadre :
Un ordinateur peut créer un tracé valide en utilisant toutes les pistes et si l'algorithme est bon, peut-être en quelques secondes
Vous n'avez pas besoin que l'algorithme s'exécute en quelques secondes.Vous avez besoin d'une sortie dans quelques secondes.Je ne vois rien qui vous empêche de configurer un processeur de mise en page par force brute fonctionnant sur un ordinateur dans le coin et de stocker des solutions dans une base de données à partir de laquelle l'interface utilisateur peut ensuite sélectionner des mises en page aléatoires.
En termes de génération, il existe un certain nombre d'approches semi-standards.L’espace d’état est plutôt vaste, donc une recherche exhaustive peut ne pas être réalisable.Mais l’une des solutions suivantes pourrait valoir la peine d’être essayée :
- Mélange aléatoire pur d'une liste de lignes droites et d'un nombre égal de courbes gauche et droite, suivi d'un test de « bonté ».
- Escalade :commencez par une permutation aléatoire, puis testez des échanges simples pour voir s'ils améliorent la « bonté ».Si c’est le cas, effectuez l’échange et répétez.
- Recuit simulé :similaire, mais permet parfois des changements qui diminuent la « bonté » dans l'espoir d'arriver à une meilleure colline.
- Algorithme génétique:générer de nombreuses permutations aléatoires, les mélanger à plusieurs reprises et conserver les meilleurs résultats.Cependant, on ne sait pas vraiment comment les mélanger.
- Les trois derniers pourraient commencer par des courbes « connues » générées par des insertions dans un cercle.
- Explorez les options de rencontre au milieu.Par exemple.générez toutes les courbes avec un angle total de +90 degrés, indexez-les par vecteur 2D entre les extrémités, et s'il y a beaucoup moins de vecteurs qu'il n'y a de courbes, vous pourrez peut-être en considérer de manière exhaustive les quadruplés pour trouver ceux qui forment un quadrilatère fermé .
Pour les tests de « bonté », il doit évidemment y avoir une grosse pénalité si la courbe n'est pas fermée.Il faut également prévoir une pénalité importante en cas de chevauchement automatique.Je serais enclin à tester ceux qui utilisent un arbre quadruple pour trouver des segments qui ne sont pas consécutifs mais proches les uns des autres, puis à tester l'intersection arc-arc, arc-ligne et ligne-ligne pour voir si une arête délimitant un segment chevauche une arête en délimitant une autre.
Une autre stratégie qui pourrait permettre de forcer complètement le cas le plus petit mais pas le plus grand serait d'adopter une approche algébrique du vecteur total.Soit la longueur de la pièce droite $2\ell$ et le rayon de la pièce incurvée soit $2r$.Puisque les orientations sont toutes des multiples de 30 degrés, le vecteur entre les extrémités d’une pièce droite est en $$(0, \pm 2\ell), (\pm 2\ell, 0), (\pm \ell, \pm \sqrt3 \ell), (\pm \sqrt3 \ell, \pm \ell)$ $ et de même le vecteur entre les extrémités d'une pièce courbe est en $$(\pm r, \pm \sqrt3 r), (\pm \sqrt3 r, \pm r), (\pm (\sqrt3 - 1)r, \pm (\sqrt3 - 1)r))$$
À moins que l'un des $\frac \ell r$, $\frac {\sqrt 3 \ell} r$, ou $\frac \ell {\sqrt 3 r}$ est une fraction avec un petit numérateur et un petit dénominateur, les courbes et les droites sont indépendantes, vous pouvez donc trouver des ensembles de courbes de travail (la force brute est suffisante pour 20 courbes dont 16 dans un sens et 4 dans l'autre ;pour 44 courbes réparties entre 28 et 16, vous avez besoin d'une meilleure approche ;Je n'ai pas réfléchi aux implications d'exiger le $+\sqrt 3$s avoir un nombre correspondant de $-\sqrt 3$s, mais ils peuvent permettre un filtrage important), puis insérez des lignes droites par paires.L'appliquer par force brute à un petit nombre de courbes vous permettrait d'évaluer le nombre de mises en page que vous risquez de perdre avec l'approche symétrique.
Une solution possible rendre cela aussi simple que possible pour obtenir rapidement un algorithme fonctionnel serait le suivant.Le tracé le plus simple est bien sûr le 12C (12 pistes courbes ayant toutes la même orientation (les unes par rapport aux autres), et formant un simple cercle.Ce sera la base sur laquelle nous pourrons bâtir.
L'algorithme de base consistera donc à maintenir la disposition en boucle continue à 360 degrés à chaque étape lors de l'ajout de pistes.Nous pouvons le faire en examinant le nombre de pistes courbes qu'il nous reste et en les ajoutant à la disposition en groupes de manière à conserver la propriété à 360 degrés.Par exemple, commencez par notre disposition 12C (un simple cercle).Nous savons qu’il nous reste 20 °C au total, il nous reste donc 8 °C.L'ajout le plus simple de certains de ceux qui conserveraient la propriété de 360 degrés serait d'ajouter une courbe d'orientation inversée et une courbe de même orientation (identique au cercle principal avec lequel nous avons commencé).Nous ferions alors la même chose du côté opposé du tracé.Dans cet exemple simple, nous aurions ajouté 4 courbes supplémentaires à la disposition du cercle afin que 12C devienne 16C (avec 4C restants).Nous continuerions à placer les courbes jusqu'à ce que les 20 (dans cet exemple) soient correctement placées.Notez que cette disposition composée de toutes les courbes est une disposition en boucle fermée valide.Le train peut utiliser ce tracé, cependant, il se compose uniquement de voies courbes, nous n'avons donc pas encore terminé.
Les pistes droites seraient alors insérées de la même manière, sauf que celles-ci peuvent être ajoutées par paires (2 pistes) puisqu'elles ne modifient pas la propriété 360 degrés.Ils peuvent être insérés n'importe où donc je pense qu'il serait préférable de placer d'abord TOUTES les pistes courbes, puis de revenir en arrière et de faire un 2ème passage pour placer les lignes droites de manière aléatoire (mais symétriquement).
C'est l'algorithme le plus simple auquel je puisse penser pour l'instant.Il est garanti de produire une boucle fermée à 360 degrés, une piste symétrique, et en supposant que le nombre de courbes est un multiple de 4 et que le nombre de lignes droites est un multiple de 2, il utilisera chaque piste.
Une chose à considérer cependant (lorsque vous utilisez cet algorithme sur un ordinateur ou simplement dans votre esprit pendant que vous construisez la mise en page), c'est qu'il peut y avoir des restrictions d'espace plus dans un sens que dans l'autre.Par exemple, sur une terrasse longue mais pas si large.Lors de l’utilisation de l’algorithme, il doit être davantage orienté vers la dimension longue de l’endroit où le réseau sera assemblé.
Si quelqu'un pouvait trouver un algorithme pour former une disposition asymétrique utilisant toutes les pistes, ce serait encore plus impressionnant.
La différence de complexité entre la solution la plus simple et la plus compliquée est stupéfiante.Commencer par un cercle (12C) est à peu près aussi simple que possible pour ce problème et est raisonnable pour les enfants, mais il est très intéressant d'analyser une solution générique qui peut produire TOUTE disposition valide (y compris les asymétriques).
En réalité, un algorithme non informatique consisterait simplement à ajouter quelques formes "cool" à la mise en page et à la rapprocher de la connexion, puis à revenir en arrière et à l'affiner pour qu'elle se connecte effectivement (pour une boucle fermée).Avec 70 morceaux de rails au total (44C et 26S), un agencement immense est possible.J'ai calculé un total d'environ 67 pieds de voie, soit environ 20 mètres.Le train devrait prendre environ 1 minute pour parcourir l’intégralité du tracé une fois.
Une autre solution candidate serait de prendre les mesures réelles de chaque piste et de se souvenir du bord le plus à droite du tracé.Lors de la construction du tracé, vous pouvez commencer avec une piste droite ou avec une courbe à gauche (dans le sens inverse des aiguilles d'une montre), en accumulant la distance entre la dernière piste ajoutée et ce bord le plus à droite, puis lors de l'ajout d'autres pistes, en n'autorisant jamais une combinaison de pistes qui heurter ou traverser ce bord le plus à droite ou peut-être même ne pas s'en approcher.Ainsi, par exemple, commencez par une piste droite (pas de cercle initial 12C sur cette solution candidate), puis choisissez au hasard un autre morceau de piste.Notez dès le début que nous n'autoriserions PAS un virage à droite (dans le sens des aiguilles d'une montre), car cela enfreindrait la règle de « traverser » le bord le plus à droite.Après la première piste droite, nos seules options sont une autre ligne droite ou une courbe à gauche (dans le sens inverse des aiguilles d'une montre).Une autre règle à appliquer serait qu'après une ligne droite, nous ne sommes pas autorisés à ajouter plus de 9 courbes de même orientation à la suite, sinon cela risquerait de heurter/traverser d'autres pistes déjà en place.Cette limite pourrait même être réduite à 8 pour plus de dégagement, et si cela se produit, la prochaine piste DOIT être une courbe orientée inverse (puisqu'une ligne droite peut causer des problèmes).
Cet algorithme aurait besoin d'aide pour qu'il revienne et se connecte à l'autre côté de ce premier morceau de piste ajouté.Nous pouvons le faire en insistant sur le fait que les courbes dans le sens inverse des aiguilles d'une montre comptent pour +1 et que les courbes dans le sens des aiguilles d'une montre comptent pour -1, et que celles-ci doivent totaliser 12 sur la dernière courbe ajoutée.Nous pouvons y remédier en polarisant les courbes CC (dans le sens inverse des aiguilles d'une montre) selon un rapport de 4:1 avec des courbes dans le sens des aiguilles d'une montre, de sorte qu'il y a de fortes chances que nous obtenions 16 CC et 4 dans le sens des aiguilles d'une montre, ce qui permettra d'obtenir effectivement un cercle de 360 degrés.Si l'algorithme tente d'ajouter une courbe CC mais heurte les pistes existantes, nous avons 2 options à ce stade, essayer une courbe d'orientation opposée, ou abandonner le tracé et recommencer.Je pense que sur un ordinateur rapide, la mise en page finira par être bonne.
Je ne sais pas encore si cette méthode produirait les mêmes mises en page que celle commençant par 12C, mais elle pourrait peut-être être plus facile à mettre en œuvre sur un ordinateur car il n'y a que quelques règles à appliquer, et nous construisons la mise en page sur une seule piste. à la fois.
En fait, je viens de penser à un 3ème solution candidate possible cela devrait fonctionner et n’est pas trop difficile à mettre en œuvre.Cela se passe comme suit.
Utilisez la technique décrite ci-dessus, mais ne réalisez qu'un demi-tracé (en utilisant la moitié des pistes de chaque type, soit 10 courbes et 5 lignes droites).Nous demandons à l'ordinateur de choisir des pistes aléatoires, mais n'acceptons que les tracés qui aboutissent à un filet de 180 degrés de virage à gauche (car nous appliquons une bordure droite qu'aucune piste ne peut toucher ou traverser.D'accord, supposons que l'ordinateur trouve très rapidement une "demi-mise en page" valide.Ensuite, nous faisons simplement un inventaire du nombre de courbes dans le sens des aiguilles d'une montre et des courbes dans le sens inverse des aiguilles d'une montre, et dupliquons cela dans l'autre moitié de la piste (mais pas nécessairement symétriquement).Pour les lignes droites, il faut enregistrer sous quel angle elles ont été insérées puis les faire correspondre dans l'autre moitié de la piste, mais encore une fois, pas nécessairement symétriquement.
Essayons un exemple en utilisant S pour Straight, O pour la courbe dans le sens inverse des aiguilles d'une montre et C pour la courbe dans le sens des aiguilles d'une montre.Concentrez-vous d’abord sur la demi-mise en page.
La première piste droite s'éloignera de nous et cela définit notre bord le plus à droite que nous ne sommes pas autorisés à franchir.
SOOSOCSOOSSOOOC - Il s'agit d'un demi-tracé valide puisqu'il comporte 5 lignes droites et 10 courbes avec un filet de 6 courbes dans le sens inverse des aiguilles d'une montre (2 des 8 ont été "annulées par 2 courbes dans le sens des aiguilles d'une montre).
Nous devons maintenant "garder un œil" sur l'angle sous lequel les lignes droites ont été insérées et faire correspondre celles avec le même angle (mais dans la direction opposée) pour les "annuler".
1:Lignes droites à angle de 0 degré
0 :Lignes droites à un angle de 30 degrés
2 :Lignes droites à un angle de 60 degrés
0 :Lignes droites à 90 degrés
2 :Angle droit de 120 degrés
0 :Lignes droites à 150 degrés
0 :Lignes droites à 180 degrés
Donc, pour "faire correspondre" cela sur l'autre moitié du tracé et faire en sorte qu'il se connecte à la seule piste droite de départ, il nous suffit de faire correspondre le même nombre d'Os et de C, mais aussi de faire correspondre le même nombre de lignes droites au + Angle de « retour » de 180 degrés.Par exemple, il est préférable qu'une ligne droite de 60 degrés ait une ligne droite de 240 degrés de l'autre côté du tracé quelque part, pas nécessairement exactement à l'opposé.En effet, la ligne droite de 60 degrés ira principalement vers la gauche et un peu vers le haut (en utilisant ce schéma) et la ligne droite de 240 degrés la ramènera vers la droite et redescendrea du même montant pour "annuler" efficacement les contributions de ces 2 pistes à s'écartant de la position de départ de la piste.
Alors maintenant, tout ce que nous devons faire pour créer la « moitié manquante » du tracé est de prendre les pistes connues dont nous avons besoin (et de savoir à quels angles les lignes droites doivent être), et de simplement les « brouiller » dans n'importe quel ordre.
Il existe peut-être un moyen de NE PAS avoir à faire correspondre exactement la moitié du tracé avec des pistes "complémentaires" de l'autre côté, mais cela impliquerait des calculs plus complexes et il n'y aura probablement pas assez de temps pour résoudre ce problème dans le temps. la prime est active pour.Il est également possible que toutes les voies ne soient pas utilisées de cette façon et qu'une légère courbure de la voie soit nécessaire.Nous pouvons ignorer cette propriété spéciale pour cette question.
En fait, j'ai fait une piste asymétrique pour voir si cela fonctionnerait et il semble que ce soit le cas.En utilisant S pour ligne droite, O pour courbe dans le sens inverse des aiguilles d'une montre et C pour courbe dans le sens des aiguilles d'une montre, plus l'angle (en degrés) par rapport à la piste droite de départ, j'ai obtenu ce qui suit pour la moitié supérieure :
S0, O30, O60, S60, O90, C60, S60, O90, O120, S120, S120, O150, O180, O210, C180
Pour la moitié inférieure de la piste, j'ai obtenu :
O210, O240, S240, C210, O240, S240, O270, O300, S300, S300, O330, O360, O390, C360, S360
En fait, la photo a été prise du mauvais côté, donc le haut et le bas sont inversés.La première piste posée était la ligne droite près de la poubelle bleue et venant vers le spectateur de la photo et la 2ème piste est la courbe dans le sens inverse des aiguilles d'une montre.
Il semble que cette technique fonctionnerait pour un nombre pair de courbes et un nombre pair de lignes droites, y compris 44C et 26S, ce qui est mon objectif ultime.C'est vraiment encourageant puisqu'un ordinateur électronique n'est pas vraiment nécessaire pour résoudre ce problème, je peux simplement demander aux enfants de construire à peu près n'importe quelle forme de demi-cercle qu'ils veulent avec la moitié des pistes (22C et 13S), puis de "corriger" leur conception. qu'il fait 180 degrés, puis « faites correspondre » l'autre côté de la piste, pas nécessairement symétriquement.
Vous devrez être prudent si vous deviez créer une demi-disposition à 180 degrés où la piste de départ et la piste d'arrivée sont très proches l'une de l'autre.Par exemple, la forme de la partie supérieure d'un point d'interrogation "?" (sans le point) mais continuez cette courbe supérieure pour qu'il arrive plus et une descente directe de celle qui serait très proche de la droite qui est au-dessus du point où le point était.Ensuite, pour la moitié inférieure, vous ne seriez PAS en mesure de faire plus de courbes dans le sens inverse des aiguilles d'une montre tout de suite puisqu'il y a d'autres lignes droites à partir de la "moitié supérieure".L'image de ma mise en page en boucle fermée a fonctionné parce que je n'avais pas de "goulots d'étranglement" dans la moitié "supérieure", mais bien sûr, ceux-ci sont possibles comme je viens de le décrire.
La disposition « problématique » du train se produit lorsqu'une moitié de la voie forme en quelque sorte une forme de sablier avec un milieu étroit.Dans ce cas, il faut presque "miroriser" la partie supérieure car certaines courbes ne peuvent pas être réalisées tant les voies sont proches les unes des autres.Voici un exemple...
Une autre observation intéressante est que 4 pistes courbes en zigzag remplacent presque exactement (en termes de distance linéaire parcourue) 5 lignes droites.Cependant, un trop grand nombre de ces éléments créera une différence de longueur significative.Comme indiqué dans la section MISE À JOUR ci-dessus, 20 courbes en zigzag correspondent presque exactement (pour la distance linéaire) à 24 lignes droites.
Grâce à cette technique, un tracé géant peut être réalisé avec les 70 morceaux de piste.Il commencerait par un cercle de 12C, puis d'un côté, je pouvais insérer 24 droits (240 pouces de long).Sur le côté long opposé du tracé (pour correspondre presque à la longueur du côté droit), j'utiliserais 20 courbes en zigzag (également d'environ 240 pouces de long).Ceux-ci devraient presque s’aligner et une légère courbure devrait faire fonctionner.Les voies restantes (2 droites et 12 courbes) pourraient facilement être placées pour maintenir le tracé « équilibré » (et connecté).
Supposons que vous commenciez au point (0, 0) en allant tout droit vers la droite.Vous devez ajouter des pistes jusqu'à ce que vous atteigniez à nouveau le point (0, 0), cette fois directement depuis la gauche.Ici, nous avons deux problèmes:La première consiste à atteindre le point (0, 0) en venant de la gauche exactement.L'autre est de ne pas avoir de chevauchements.
Pour former un cercle dans le sens inverse des aiguilles d'une montre, vous aurez besoin de 12 pièces courbes tournant à gauche.Ceux-ci forment un cercle exact.Avec 0, 24 ou 36 pièces courbes, vous auriez un chiffre huit, deux ou trois cercles, dont aucun ne peut être réalisé sans croisement.
Et bien sûr, vous pouvez ajouter des pistes supplémentaires, et celles-ci doivent suivre certaines règles :Vous pouvez ajouter des pièces incurvées à gauche, droites et incurvées à droite par paires en commençant à des angles de x degrés et x+30 degrés, de sorte que vous reveniez à 0,0.Et le nombre de pièces incurvées à gauche au-delà des 12 premières doit correspondre au nombre de pièces incurvées à droite afin que les pièces correspondent à l'angle droit à 0,0.
Voilà donc les pièces que vous pouvez utiliser.Il faut évidemment vérifier qu'il n'y a pas de passage à niveau.
Si les longueurs sont exactement bonnes, il se peut que par exemple une combinaison gauche/droite/droite/gauche couvre exactement la même distance que quatre ou cinq lignes droites, donc d'autres combinaisons peuvent être autorisées.
Et bien sûr des pistes sont Bendy, ce qui peut produire beaucoup plus de possibilités.
