1

Petite question qui me trotte dans la tête au sujet d'Ingress.

Les points sont raccordés entre eux par des liens et 3 liens peuvent former un field.

La règle est assez simple : on ne peut pas croiser deux liens et on ne peut pas tirer un lien depuis l'intérieur d'un champ.

Si j'ai un triangle ABC avec un point D au milieu, pour optimiser, je peux faire AB, AD, DB, BC, CA, CD (et DC n'est pas possible vu que le champ existe déjà) et je me retrouve avec 4 champs (donc autant de points).

Sachant que depuis un point donné on ne peut tirer que 8 liens maxi, je me demandais s'il était possible de faire un petit programme qui à partir d'une liste de points (X, Y) soit capable de sortir le meilleur plan de fields et l'ordre des opérations pour le tisser.
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

2

je ne sais pas tsss

Il faut des vrais matheux calés en théorie des graphes.

Et le problème est peut être indécidable... sorry

3

Pareil, je suis pas assez matheux. Mais effectivement, ça ressemble fortement aux problèmes de théorie des graphes.
Par exemple : http://en.wikipedia.org/wiki/Delaunay_triangulation (mais je sais pas si ça respecte tes critères)

Y'a bien quelqu'un qui pourrait probablement t'aider, mais il aime pas les jeux propriétaires tongue

Au passage, tu as combien de points ? C'est pour savoir si on peut utiliser de la force brute ou pas.
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

4

C'est pas que les points, c'est aussi pour la défense, y'a une mitigation en cas d'attaque entre les portails liés, et un bon maillage rend la structure plus solide.
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

5

Ouais, mais ça dépend : c'est quelques dizaines, quelques centaines, quelques milliers, plus ?

Et c'est quoi un "bon" maillage ? J'ai compris qu'il y avait un nombre maximum de segments qui partent d'un point, mais il y a quoi d'autre ? Faut maximiser la surface des triangles ?
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

6

un maximum de triangles, dont le maximum se recouvrent, parce que des règles précises qui permettent de les recouvrir si on crée les arêtes dans le bon ordre.

Voir une ébauche ici
http://ingress.wikia.com/wiki/Control_Field

7

Pour l'ordre de grandeur, Paris, c'est 10'000 portails, mais si je parvenais à le faire sur une centaine à la fois ça pourrait être largement suffisant
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

8

Y'a un truc qui m'échappe, je ne vois pas comment on peut concilier ça :
vince (./1) :
La règle est assez simple : on ne peut pas croiser deux liens et on ne peut pas tirer un lien depuis l'intérieur d'un champ.
et ça :
squalyl (./6) :
un maximum de triangles, dont le maximum se recouvrent,
Pour moi, avec les règles de Vince, on obtient que des triangles qui ne se recouvrent pas.
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

9

tu peux tirer un lien depuis un portail sur le bord d'un field existant, ils sont considérés comme a l'extérieur.

triangle ABC avec D au centre, tu linkes

A->B
A->C
B->C
A->D
B->D
C->D
(par ex et si j'ai bien compris, je ne suis qu'un padawan embarrassed)

10

Oui c'est bien ça

11

On peut peut être tenter une triangulation de delaunay, ca donnerait un maillage triangulaire le plus "régulier"possible, mais sans superposition, puis détecter les situations où on peut faire des fields superposés.
Ou choisir manuellement les points "internes"qui servent a faire des fields superposés.

12

Je veux bien essayer de résoudre le problème mathématique, mais ne connaissant pas le jeu, je n'ai rien compris à vos descriptions (pas très mathématiques) du problème. sad
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

13

(Rien compris à la description du problème aussi)

14

lisez la page wikia. l'objectif est de faire un max de triangles sur un ensemble de points, avec des conditions qui autorisent a les superposer.

15

URL?
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

16

17

Le probleme est NP complet et pas simple a resoudre meme en brute force
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

18

19

Mes propre recherches la dessus
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

20

Bon, prenons un exemple avec 5 portails (points) A B C D E.
fsMD

Premier cas (en haut à gauche), pas très rentable (le premier point ne peut être à l'intérieur d'un field) :
AB
AE
AD
DE(on a créé le field AED)
DC
EB(on a créé le field ABE)
EC(on a créé le field CED)
CB(on a créé le filed BCE)

=> 4 fields

L'opération "correcte" est de faire plusieurs couches (en bas)
AE
AD
ED(on a créé le field AED)
AC
DC(on a créé le field ACD)
CE(on a créé les fields DEC et CAE) (je ne peux pas faire EC parce que E est à l'intérieur de ACD)
CB
AB(on a créé le field ABC)

Le bon schéma mais pas dans l'ordre peut tout gacher (en haut à droite) :
AE
AD
ED(on a créé le field AED)
AC
EC(on a créé le field AEC)
DC(on a créé le field DEC)
CB
AB(on a créé le field ABC)
=> 4 fields seulement alors que le schéma est le bon


Le problème consiste donc à trouver le bon maillage et en plus à indiquer quel ordre pour la création des liens.
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

21

Ah, j'oubliais, il y a une autre limite : depuis un portail on ne peut tirer que 8 liens alors que N portails peuvent tirer un lien vers le même.

(pour tirer un lien, il faut une "clé" du portail d'en face, on peut en droper jusqu'à 4 par portails en 4 heure de base, des mods sur le portail permettent d'augmenter le nombre maximal si y'a besoin)
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

22

Sans fixer une definition exacte, il est difficile de prouver qu'il est polynomial ou NP-difficile.

Comme le dit Kevin, il faudrait une description un peu plus formelle pour commencer a réfléchir sur la complexité du problème : utiliser un vocabulaire plus standard, définir l'objectif d'optimisation en ces termes, et lister les contraintes (règles) précises.

Je crois comprendre sur la page indiquée que l'adversaire peut annuler un triangle en retirant un seul sommet. Dans ce cas, un objectif n'est-il pas de minimiser le nombre d’arêtes par sommet ? nombre moyen ou nombre maximal ?
Si oui, le problème est multi-objectif : on a deux objectifs contradictoires (maximiser le nombre de triangles mais minimiser le nombre d'arêtes). C'est un champ de recherche encore jeune en optimisation combinatoire, et tous les problèmes pratiques de ce type sont NP-difficiles. Un algorithme optimal pour des graphes de taille 100 (taille évoquée par vince) prendrait des heures ou des jours, sinon des mois. Cependant, il peut y avoir des heuristiques qui donneraient des solutions très satisfaisantes.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

23

La règle la plus simple quand tu prévois c'est de commencer par faire les triangles les plus grands possibles. C'est pas toujours le plus rentable, surtout en clefs, mais ça passe. Je sais qu'il y a un quartier en ville où je peux tirer une trentaine de fields simplement avec une base à 4 portails, mais il me faut une bonne quantité de clefs...

Après, personellement, j'utilise ingraph: http://atistar.net/~stepp/ingraph/

(Et balance ton pseudonyme en jeu tongue)

Hors Sujet: ça fout quoi dans le sous forum TI ?x)

Un résumé des règles pour les matheux:

* Deux liens ne peuvent pas se croiser.
* Les liens ont une direction et un sens (en somme, ce sont des vecteurs, appelons les donc vecteurs)
* Un point ne peut pas être l'origine d'un vecteur si ledit point est dans un field.
* Le nombre de vecteurs maximum originant d'un point est de 8.
* On peut faire entrer un nombre infini de vecteurs sur un point.
* Trois points reliés entre eux en triangle forment un "field".

Je crois que je n'ai rien oublié.

On peut ignorer l'aspect farming de clef @vince, suffit de hacker le matin sur le chemin tous les jours :P Ou de taxer des clefs aux autres joueurs.

24

Warpten (./23) :
Hors Sujet: ça fout quoi dans le sous forum TI ?x)

C'est historique, la section Algo était dans le sous forum TI à la base, et la multi parentalité n'étant pas encore supportée...


Je ne connaissais pas ingraph, ça a l'air sympa smile
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

25

Omagad y'en a qui se sont vraiment posé la question grin

Tu nous diras si ca aide vince?

26

La source est en haskell ... x.x

27

squalyl (./25) :
Omagad y'en a qui se sont vraiment posé la question grin

Tu nous diras si ca aide vince?

Je regarderai ouais smile
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

28

Warpten : La variété des fonctions objectif proposées semble confirmer que le problème n'a pas de description définitive qui satisferait tout le monde.
Est-ce que, au moins pour certains objectifs, tu as une idée de la performance de cette heuristique (écart entre les solutions qu'elle donne et l'optimum) ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

29

Warpten (./26) :
La source est en haskell ... x.x

Et c'est probablement très adapté à la résolution de ce genre de problèmes.
avatar
<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !

30

./29 Mais je suis incapable de la lire grin

./28 Il y a différentes approches pour différentes situations, mais en général l'heuristique du "Save Flynn Event" est (curieusement, étant donné que la solution qui maximise le gain en AP est la plus recherchée) la plus proche du résultat réel.

En revanche sur un grand nombre de noeuds le programme crash simplement (typiquement, sur une 50 aine, j'ai eu un joli message d'erreur windows ^^)

à noter qu'il y a de toute façon plus d'une solution optimum pour ce type de problèmes.

C'est un problème intéressant mais je n'ai (malheureusement, étant joueur tongue) pas le bagage mathématique pour m'y attaquer moi-même.