Astar sur une map de 600x600 ?

[php_addict]

bonjour

toujours en galère sur l'algo Astar...


type de jeu

MOORPG php/sql/ajax

dimension de la map:

600x600 (360.000 cases....)

cases interdites:

- les bords de la map (soit 2400 cases)
- environ 10% de la map (comme des murs par exemples...) (soit 36.000 cases)

cases ayant un cout supplémentaire en raison du terrain:

- environ 44% (soit 159999 cases)

IMPERATIF

ne pas interroger trop souvent la base de donée étant donnée le nombre de cases...


Voici ce que j'ai fais jusqu'à présent:

- mise en variable (tableau) des cases interdites (38400 cases)
- mise en variable (tableau) des cases ayant un poids en fonction du terrain (159999 cases)
- l'alog astar est lancé avec toutes ces données...

Le problème

vous l'aurez compris, c'est la taille de la map...

je pense que pour un MOORPG en php, se servir de variable (tableau) contenant les infos pour 38.400 cases n'est pas raisonable...enfin je pense, non?


je ne vois pas comment faire simple, peu gourmand en ressource (variables), en interrogeant la base de donnée un minimum de fois, rapide, etc...

avez vous une idéee de comment faire?
est ce raisonable?
dois je abandonner quelques parametres (genre le cout pour le type de terrain) ?


merci de m'avoir lu ;-)

bonne soirée

[Sephi-Chan]

Pourquoi ne pas stocker les chemins trouvés ? Ainsi, tu ne les calcule jamais plus d'une fois.

Si un joueur souhaite aller du point A au point B, tu cherche s'il existe un chemin précalculé pour cette paire {source, destination}. Si ça n'existe pas, tu calcules puis tu stockes (sous forme d'une liste de cases).

C'est juste une idée, jetée comme ça. On doit pouvoir améliorer ce concept.

Après, en solution purement technique, tu peux stocker ta carte en RAM (grâce à un serveur Memcached) pour rendre les temps d'accès très courts. Mais ça implique d'être sur un serveur dédié.


Sephi-Chan

[Sloop]

Et peut-être de vérifier si un chemin n'a pas été calculé en plusieurs fois ? Bien que mathématiquement, il n'y ait pas de relations de linéarité de minimum de coût.

La question que tu peux te poser : Combien de temps un joueur va-t-il mettre pour faire 100, 200, 300 ou 1000 cases entre un point et un autre ? Est-ce que c'est quelque chose de vraiment sensé comme temps de trajet (en ne faisant que voyager ?) ?
Est-ce que ta carte a une taille censée par rapport à ton jeu ? Un jeu assez connu n'avait qu'une carte de 200 cases (ou 250) de côté et c'était déjà suffisamment grand.

Ce que je veux dire par là, c'est que la solution n'est pas forcément là où tu veux qu'elle soit. Elle peut être trouvé ailleurs mais c'est à toi d'y réfléchir. Sinon la solution de Sephi est une solution à creuser. Mais je n'ai jamais testé et je ne connais pas les enjeux.

[wild-D]

là je rejoint les autre, je vois pas pourquoi tu t'obstine à vouloir gérer ton A* sur la map globale.

ma première question (mais me semble déjà abordée sur un autre topic) pourquoi lancer l'algo sur la totalité de la map: normalement le champs de vision du joueur porte pas sur la totalité de la map non ? D'un point de vue simplement ergonomique tu as prévu qu'il fasse comment pour indiquer sa case cible quand elle est à 600 cases de sa position actuelle ?

enfin moi je ferais encore un peu plus simple que sephi (le principe est le même). Inspire toi de la réalité .
quand tu voyages toi, tu t'amuse pas à calculer le A* de ton chemin. Tu suis les routes et les panneaux de direction. Tu n'as qu'à faire pareil pour ton jeu. Tu précalcules les chemins entre "lieux connus" (genre village, ville, auberge pour voyageur, autre point de repère particulier de la carte). Quand un perso veut se déplacer hors de son champ de vision, tu décompose le voyage: il rejoint le "lieu connu" le plus proche suit les route de "voyage" balisée et rejoint son point d'arrivée. Ce n'est pas le chemin le plus court, mais "le plus réaliste" .

[NicoMSEvent]

+1 wild-D
Si je vois un chemin, je ne vais m'amuser a essayer de calculer un raccourci pour voir si c'est plus rapide de traverser le buisson touffu, ou bien le contourner via le chemin (même si ça prend 5 minutes de plus :p )

Les routes et les chemins sont des éléments assez important dans mon jeu (carte de 1000/1000 -> 1.000.000 de cases), et je ne permets pas le calcul genre A*. Soit tu suis le chemin, soit tu essayes (a tes risques et périls) de trouver un raccourci

[php_addict]

Bonjour et merci à tous

D'un point de vue simplement ergonomique tu as prévu qu'il fasse comment pour indiquer sa case cible quand elle est à 600 cases de sa position actuelle ?

un peu comme travian...

l'autre probleme sur ma map c'est que je n'ai pas de terrain du type chemin, donc pré-calculer des parcours sur une map de 360.000 cases me parait assez enorme...

je peut diviser ma map 600x600 en mini-map de 100x100 mais le jour ou un petit malin essai de parcourir la map en traversant 20 mini-map, cela fait tout de meme 200.000 cases pour l'algo astar...ca reste assez enorme, non?

en imaginant que je mette des points de repere pour precalculer des parcours, avec 36 minimap de 100x100 cela fait 1296 à précalculer mais ce n'est pas le plus réaliste en ce qui concerne le chemin le plus court...

je suis completement paumé...

merci de votre aide.

[Ramat]

je crois que je "voie" ton probléme - me manquait juste la référence à travian, jeu que je ne connais pas , pour comprendre - et le pourquoi d'une carte de 600*600.

En gros ce sont donc les déplacements "long courrier" des troupes/marchands qui posent un soucie, car tu t'imposes des cases inaccessibles (eau, montagne, je suppose), ce que ne font jamais ce genre de jeu (j'évolue sur guerre tribale depuis qq mois donc j'ai eu le temps de le décortiquer )

Ce que tu cherches apporterait certes plus de tactiques à ton jeu, mais c'est, à mon avis, trop lourd à gérer en tant que tel.

à la limite, pour simplifier le probléme, il te faudrait à la place des cases inaccessibles, des cases coutant plus de temps de parcours. Par contre, cela induit aussi que le joueur doit pouvoir, avant/aprés avoir fait une recherche de "route" pouvoir modifier lui même cette route s'il veut essayer de contourner les éléments couteux en temps de déplacement - si on part du principe que ton algorytme de calcul ne cherche que le plus court chemin en terme de distance et non de temps - et là tu gagnes effectivement un petit plus "tactique" (entre celui qui prendrait le temps de cherchait à optimiser la route et ceux qui s'en remettront au moteur du jeu), en immergeant un peu plus tes joueurs par la même occasion, car ils devront se creuse la cervelle aussi

j'espére avoir bien compris ce que tu cherchais ... et avoir été assez clair surtout ^^

Ramat

[php_addict]

bonjour Ramat

merci pour ta reponse

en effet ce serait une map de 600x600 avec rivieres et terrain avec un cout pour le temps de deplacement

donc Le Astar en terme de ressource serveur (apache et php) c'est inconcevable? beaucoup trop gourmand? (je parle pour un dédié forcément...) ???

[wild-D]

clair qu'avec travian comme référence ça change quelque peu la perspective du problème. (moi j'imaginais le perso isolé joué par le jouer qui se balade et vit ses aventures).

ce genre de jeu généralement n'utilise pas de A*, ils se contentent souvent de calculer la distance à vol d'oiseau entre la position de départ et d'arrivée pour évaluer le temps. Les plus "complexe" rajoute des évents ou d'autre forme de raffinement impactant le temps de trajet (perte de troupe/temps dans un accrochage avec un ennemi,ou un accrochage; et je suis pas sûr que ce soit forcément en fonction du nombre de zone traversée et de leur facteur de "dangerosité").


mais tu devrait penser à "simplifier" ton problème. Est-ce que tu as besoin d'un calcul d'A* pour avoir un "rendu" qui apporte l'élément de gameplay/réalisme ou autre que tu recherche ?
Parce que là tu reste focalisé sur ton idée de "chemin le plus court"... une armée en campagne à souvent bien d'autre contrainte avant cela (les armes de siège c'est pas du "tout terrain", il faut éviter de passer par des défilés ou des zones trop exposée ou l'armée risquerait de se faire tailler en pièce trop facilement, il peut aussi y avoir le problème du ravitaillement-> nécessité de passer par des points d'eau, etc...). La discrétion, la sécurité, etc... y a bien des facteur qui rentre en compte.

une manière barbare de proposer des alternative et des choix au joueur, plutot que du chemin "réel" ()
idée bête:
- proposer à ton armée différent type de déplacement:
a) normal => temps de base
b) à marche forcée => gain de temps, mais l'armée et "fatiguée" quand elle arrive à destination (donc perte d'efficacité pour l'établissement du siège/combat ?)
c)etc...
- proposer à l'armée une fois sur place de:
a) prendre le chateau d'assaut
b) faire le siège du chateau
c)etc...
- plus d'autres propositions de choix stratégique....

et au rendu, tu peux bien sûr faire simplement un questionnaire avec des cases à cocher. Ou alors tu lui présente une carte avec plusieurs chemins (pas besoin que les chemin soient fait avec de vrai A*, du moment que le joueur voit plusieurs chemin avec une variante plus rapide, une plus sûres, etc... ), des plan de bataille -rangs sérré, ou lâche, si tout le monde attaque en même temps ou par vague,...-, etc.. de quoi donner au joueur une bonne impression qu'il maitrise les choix stratégique de son armée.

pas besoin de te lancer automatiquement dans un algo A* qui peut être couteux en calcul serveur pour améliorer le réalisme et le gameplay du jeu.

le plaisir de jeu n'est pas proportionnel au coût de calcul coté serveur; à toi d'optimiser ce ratio; plutot que chercher à utiliser des "algo qui en jettent".

[Ramat]

en effet ce serait une map de 600x600 avec rivieres et terrain avec un cout pour le temps de deplacement

j'en reviens à ce que j'avancais donc avant, à savoir que ce doit être tes cases inacessibles (en théorie j'entend) qui doivent faire bugger le programme de calcul.

donc Le Astar en terme de ressource serveur (apache et php) c'est inconcevable? beaucoup trop gourmand? (je parle pour un dédié forcément...) ???

Ne connaissant par le A* (enfin pas plus ce que j'ai pu en lire à droite à gauche sur la toile pour le moment), je ne pourrais pas répondre à cette question.

Par contre, ce que tu peux tenter - aprés avoir attribué des valeurs de temps à tes cases eau/montagne - c'est de faire en sorte que ces cases, dites "inaccessibles" ne soient pas écartés par l' Alogorytme au moment du calcul, mais qu'ils y passent.

Cela simplement à fin de voir si c'est le fait, ou non, d'interdire à ton algo le passage par ces cases qui le fait bugger. Et si c'est bien le fait d'interdire le passage par ces cases qui fait planter, dans ce cas, il faudrat juste leur donner une valeur suffisement forte pour décourager les joueurs d'emprunter cette route par exemple ou simplement rendre le temps de parcours plus réaliste (dans le sens ou s'ils devaient contourner l'obstacle, combien de temps mettraient ils ?)

l'autre solution, "simple" car connu, serait de faire en sorte que le joueur soit obligé de poser des jalons (comme tu peux le faire sous Googlemap par exemple, quand tu veux passer par certain point non conseillé par le logiciel au premier coup).