Algorithme pour trouver les meilleurs itinéraires pour la distribution de nourriture dans le jeu

Question

Je suis la conception d'un jeu de construction de ville et a obtenu un problème.

Imagine Sierra Caesar III Les mécanismes de jeu: vous avez de nombreux quartiers de la ville avec un marché chacun. Il y a plusieurs greniers sur la distance liée à un graphique pondéré réalisé. La différence: les gens (ici les voitures) sont des unités qui forment les embouteillages (va ici les poids graphique)

.

Note: en série de jeux Ceasar, les gens ont récolté des aliments et empilée dans plusieurs grands greniers, alors que de nombreux marchés (petits commerces) ont pris la nourriture des greniers et a livré aux citoyens

.

La tâche :. Dire chaque district où ils devraient obtenir leur nourriture tout en prenant moins de temps et de minimiser les congestions sur les routes de la ville

Exemple de carte

Supposons que les districts jaunes ont besoin 7, 7 et 4 pommes en conséquence. 7 ont bleuâtres greniers et 11 pommes en conséquence.

poids bords supposés être proportionnels à leur longueur. Ensuite, la solution doit être quelque chose comme les chiffres indiqués gris sur les bords. Par exemple, le premier arrondissement obtient 4 pommes du 1er et 3 pommes du 2ème grenier à blé, tandis que le dernier district reçoit 4 pommes seulement le 2e grenier à blé.

Ici, les routes verticales sont d'abord occupés au maximum, puis le reste des travailleurs sont envoyés aux chemins en diagonale.

Question

Quel algorithme pratique et très rapide dois-je utiliser? Je regardais des papiers ( Jeux de Congestion: Optimisation en compétition , etc.). Décrivant les jeux de congestion, mais n'a pas pu obtenir la grande image

Answer 1

Vous voulez regarder dans le Max flux problème. On dirait que dans ce cas, il est un graphe biparti, ce qui devrait rendre les choses plus faciles à visualiser.

Answer 2

Ceci est un multi-sources multi-puits Débit maximum Problème qui peut facilement être transformé en simple problème de débit maximum en créant une super source et un puits super comme décrit dans le lien. Il y a beaucoup de href="http://en.wikipedia.org/wiki/Maximum_flow_problem#Solutions" efficaces aux problèmes de débit maximum.

Answer 3

Une chose que vous pourriez faire, qui traiterait le problème de la mise à jour incrémentale discuté dans une autre réponse et qui pourrait être aussi moins cher à l'ordinateur, est oublier une solution globalement optimale. Que chaque villageois de participer à quelque chose comme ant d'optimisation des colonies.

Pensez à empêcher le peuple sur le nœud jaune à la main en bas à droite dans votre exemple de évinçant ceux sur le nœud jaune main extrême droite en permettant aux personnes au nœud jaune main extrême droite de soumissionner le " prix » d'acheter des ressources à partir du nœud bleu à droite, ce qui encouragerait une partie de ceux du nœud jaune à la main en bas à droite pour prendre la marche un peu plus au nœud bleu à la main gauche.

Answer 4

Je suis d'accord avec Larry et mathmike, il semble bien que ce problème est une spécialisation de flux réseau.

Sur une autre note, le problème peut être plus facile si votre algorithme final trouve un arbre couvrant pour chaque marché à ses ressources (greniers), consomme ces ressources goulûment sur la base premier chemin le plus court, puis se déplace sur la prochaine pile de ressources.

Il peut aider à penser en termes d'utilisation d'une route à la capacité maximum d'abord (en maximisant l'efficacité de la route), plutôt que d'essayer de minimiser la congestion.

Cela va à la racine du problème - en général, il est plus facile de trouver à proximité des solutions optimales dans les problèmes de graphes et en termes de jeu dev, proche de l'optimum est probablement assez bon

.

Edit: Je voulais aussi souligner que le lien de mathmike Wikipédia parle aussi Problème débit maximal vertex capacités où chacun de vos greniers peuvent être considérés comme des sommets avec une capacité finie.

Answer 5

Quelque chose que vous devez noter, est que votre jeu est continue. Si vous avez une solution X à l'instant t, et un petit changement se produit (par exemple: le joueur construit une autre route, ou l'une des villes gagner plus la population), la solution que les algorithmes Max flux vous donnent peut changer radicalement , mais vous voudrez probablement la solution à t + 1 pour être similaire à X. Une solution totalement différente à chaque pas de temps est irréaliste (1 nouvelle route est construite à l'extrémité sud de la carte, et tous les itinéraires sont re-calculé automatiquement).

J'utiliser un algorithme pour calculer la solution initiale (ou lorsqu'un changement important se produit, comme un tremblement de terre détruit 25% des routes), mais la plupart du temps Mise à jour seulement de façon incrémentale : sens, définir une certaine forme de transformation valide sur une solution (par exemple, 1 ville tente d'obtenir 1 unité de nourriture d'un grenier à blé différent que maintenant) - vous essayez de la mise à jour (simulent la congestion attendue), et maintenir la solution mise à jour si son mieux que la solution existante. Exécutez cette étape N fois après chaque tour de jeu ou d'une unité de temps.

ses deux informatiquement efficace (ne pas besoin d'exécuter chaque seconde complète Max Flow) et vous obtiendrez des changements plus réalistes, lisses dans le comportement.

Answer 6

Il est peut-être plus amusant d'avoir une dynamique qui modélise un comportement donnant lieu à une bonne solution raisonnable, plutôt que de trouver une solution idéale pour conduire le comportement. Supposons que vous planifiez chaque voyage individuellement. Si vous êtes un pilote et vous avez besoin d'aller du point A au point B, comment voulez-vous y arriver? Vous pourriez envisager un certain nombre de choses:

1. Je sais que sur les conditions de circulation typiques à cette heure et je vais essayer de trouver des façons de contourner les routes qui sont généralement occupés. Vous pouvez modéliser cela comme une valeur moyenne de la circulation à des moments différents, que les automobilistes ne sont pas nécessairement une information parfaite sur le trafic actuel, mais peut apprendre et identifier les tendances au fil du temps.

2. Je n'aime pas longtemps, confondant les routes avec beaucoup de virages. Lors de la planification d'un voyage, vous pourriez pénaliser ceux avec beaucoup d'arêtes.

3. Si les limites de vitesse et les feux de circulation sont inclus dans votre modèle, je veux éviter de longues périodes avec des limitations de vitesse et / ou beaucoup de feux de circulation. Je préfère les autoroutes ou les routes pour les longs trajets, même si elles ont plus de trafic.

Il peut y avoir d'autres dynamiques intéressantes qui évoluent de considérer le problème behaviorally plutôt que comme une simple optimisation. Dans la vraie vie, le trafic converge rarement sur des solutions optimales, donc une grande partie du défi dans l'ingénierie des transports est à venir avec des incitations, des sanctions et des conceptions qui encouragent une meilleure solution de la dynamique naturelle jouant dans les décisions des pilotes.