Lode Runner - Page 2

Oui ça arrive ^^

c'est meme partit ^^

Mauvaise nouvelle
J'ai fini pas mal de choses, une bonne partie du code a changé depuis mes derniers tests sur real calc, et aujourd'hui je me suis dit que le jeu était suffisamment mûr pour une beta, je l'ai envoyé sur ma TI pour tester et c'est trop lent En fait, à chaque fois que le personnage principal se déplace d'une case, le pathfinding est recalculé pour les ennemis et ça fait un gros lag (sinon, tant que le joueur reste dans le même tile c'est très fluide...).
Donc il faut absolument que j'optimise énormément mon algo de pathfinding. En fait, je pensais que le nouveau que j'ai implémenté récemment serait plus puissant, puisqu'il permet d'ajouter autant d'ennemis qu'on veut sans que ça ne ralentisse les calculs, mais je n'avais toujours pas testé sur real calc...
Franchement, je crois qu'il faut que je multiplie par 5 ou 10 sa vitesse d'exécution. Donc soit je passe tout en ASM avec des structures de données très bas niveau (parce qu'actuellement, la version C est écrite de façon assez haut niveau, pas hyper optimisée), soit je repense complètement l'algo pour diminuer sa complexité.

Franchement, je pense q'il fait pas que tu cherche a faire un path finding trop complexe, les méchants dans le jeu original on tendance a avoir n comportement tres bizzare, donc te gene aps, pas besoin de les faire tres inteligents

les méchants dans l'original que j'avais sur un macintosh noir et blanc avec un écran de 15cm^2 (lol un truc très très vieux), ben ils cherchaient justent (et il cherchent tjrs car le pc marche toujours) à aller au même niveau de hauteur que celui du joueur. Puis une fois au même niveua vertical, il essaient de rejoindre l ejoueur par l'horizontal.

Loderunner existe dans une autre version ici :
http://tezxas.ticalc.org/platform.htm

./33

Moi il me semblait qu'ils avaient un minimum de "réflexion" (dans le sens où ils avaient un certain recul sur l'architecture du niveau, leur permettant de choisir un chemin pas trop con pour atteindre le héros).
Enfin, si je n'arrive pas à améliorer suffisamment mon algo, je ferai comme vous dites. J'espère que la jouabilité ne sera pas trop affectée.

Actuellement, à chaque fois que le personnage principal change de tile, les plus courts chemins pour arriver jusqu'à lui sont calculés sur toute la map, en utilisant l'algo de Dijkstra (il me semble). Ça ne me semble pas énorme en calculs, j'ai du faire une implémentation merdique tout simplement.

je sais pas comment tu fais, mais j'ai une idée de comment faire pour calculer tous les chemins pour aller vers le joueur (indépendamment du nombre d'ennemis):
Tu explores toutes les cases en partant du joueur une fois par frame: Dans chaque case tu enregistres la distance jusqu'au joueur. Pour savoir dans quelle direction l'ennemi doit aller, il regarde le nombre de la case où il est, par exemple N, et il va à la case N-1.


(le 0 représente la position du joueur)

Sasume :
Actuellement, à chaque fois que le personnage principal change de tile, les plus courts chemins pour arriver jusqu'à lui sont calculés sur toute la map, en utilisant l'algo de Dijkstra (il me semble). Ça ne me semble pas énorme en calculs, j'ai du faire une implémentation merdique tout simplement.

La composante connexe fait combien de cases ?

Dijkstra ça me semble un peu bourrin.
L'algorithme A* serait pas mieux adapté sur TI?

si les ennemis sont trop intelligents, les niveaux ne risquent pas de devenir impossibles ?

geogeo :
Dijkstra ça me semble un peu bourrin.
L'algorithme A* serait pas mieux adapté sur TI?

A* c'est juste un type de Dijkstra, donc selon la façon dont Sasume a implémenté son Dijkstra ça peut être plus ou moins efficace que A* ^^

./38> C'est exactement ce que je fais.

./39> Ça dépend des niveaux, mais globalement, comme leur taille est de 16x28 tiles, ça ne peut pas dépasser 448. Je pense qu'elle doit être de l'ordre 300-350...

ah ok, c'est du 2d... ben je sais pas, par exemple si ta distance est |x-x'|+|y-y'| et que tu essayes de chercher des grands rectangles vides, tu peux simplifier le graphe

x-x-x-x-x-x-
| | | | | | 
x-x-x-x-x-x-
| | | | | | 
x-x-x-x-x-x-
| | | | | | 

qui a n*p sommets et 2 n*p arêtes en le graphe

x-x-x-x-x-x-
| | | | | | 
x- - - - - -
| | | | | | 
x- - - - - -
| | | | | | 

qui a n+p sommets et 2(n+p) arêtes

mais je ne sais pas du tout à quoi ressemblent tes niveaux, combien d'objets sont mobiles, etc... donc je ne sais pas si ça s'applique vraiment ^^

Il y a un screenshot du premier niveau dans le premier post, si ça peut t'aider
Merci en tout cas.

ah, donc c'est plus du 1d que du 2d

mais du coup je comprends pas bien, tu n'as aucun objet mobile à prendre en compte dans ton graphe en fait ? (i.e. c'est pas parce qu'il y a un autre monstre entre ton monstre et le joueur que tu vas devoir éviter de prendre ce chemin-là)

du coup tu peux subdiviser ton niveau en lignes droites, calculer la matrice des distances minimales entre toutes les extrêmités de lignes droites et hop, non ?

Oui, c'est une bonne idée. Sinon, je pourrais faire ce que tu décris en ./44.
Je vais y réfléchir...

La méthode de ./44 telle quelle ne t'apportera pas gd-chose, c'est efficace uniquement si tu as de grands espaces 2d dans lesquels tu peux te déplacer librement... (ce qui n'est pas le cas ici, tu ne peux pas voler dans les espaces vides)

Là puisque tu n'as pas d'objets mobiles tu devrais plutôt calculer explicitement le graphe du niveau, avec un sommet à chaque case... Ensuite tu peux appliquer des transformations, alors je sais pas mais moralement je me dis qu'il faudrait essayer de trouver des "blocs" avec un faible nombre de sommets d'entrée et de sortie ; par exemple si tu as une échelle :

<- A -> X
   ^    |
   |    v
   X -> X
   ^    |
   |    v
   X -> X
   ^    |
   |    v
-> B -> C ->

tu peux considérer que les sommets A, B et C sont les seuls sommets d'entrée-sortie accessibles de l'extérieur de l'échelle, donc tu peux réduire le bloc au graphe suivant, en cachant les sommets X :

<- A
   ^ \
   |  x
-> B -> C ->

L'idée étant que si tu cherches un chemin entre le point U et le point V, soit l'une des extrêmités est cachée dans le bloc, et alors on utilise le graphe non simplifié, soit aucune des extrêmités n'est cachée, et alors tu peux utiliser le graphe simplifié. Tu peux généraliser à un nombre arbitraire de blocs, et même une hiérarchie de blocs (par exemple, si ton échelle est trèèès longue, un bloc pour le bas de l'échelle, un bloc pour le haut de l'échelle, et un super-bloc pour l'union des deux).

Il ne reste plus qu'à trouver comment construire la hiérarchie des blocs, par exemple, si ton graphe satisfait la condition "pour tout sous-ensemble de points du graphe il y a une partition de ce sous-ensemble en deux blocs de taille à peu près égale et dont le nombre de points d'entrée-sorties est inférieur à M fixé", alors on peut facilement trouver une solution au problème du pathfinding entre U et V quelconques en O(M^2 log N) où N est le nb de sommets du graphe de départ ^^

Sasume: tu as reussi a exploiter le fichier que je t'ai envoyé ?

J'ai regardé vite fait, ça a l'air utilisable
Mais là je suis en vacances, je n'ai plus le temps !

Bah en fait les vacances sont finies.
Et je n'ai plus vraiment envie de me consacrer à la prog sur TI. Ça ne m'amuse plus tellement.
Alors tant pis...

Hihi, je m'y suis remis
J'ai eu besoin de ma TI en cours dernièrement. Comme le cours était super chiant, je me suis amusé avec les jeux qui étaient restés dessus depuis. J'ai retrouvé Lode Runner et je me suis dit que c'était con d'avoir presque fini le projet et de l'avoir laissé en plan.
Du coup, pour l'IA (qui me posait problème, cf plus haut), je me suis dit que le mieux serait de copier au plus près le comportement des versions "authentiques" de Lode Runner, donc j'ai repompé le code de KGoldRunner et ça marche nickel

J'essaierai de proposer une release pendant les vacances de février

C'est bien que vous vous y remettiez

Sasume (./52) :
Hihi, je m'y suis remis
J'ai eu besoin de ma TI en cours dernièrement. Comme le cours était super chiant, je me suis amusé avec les jeux qui étaient restés dessus depuis. J'ai retrouvé Lode Runner et je me suis dit que c'était con d'avoir presque fini le projet et de l'avoir laissé en plan.
Du coup, pour l'IA (qui me posait problème, cf plus haut), je me suis dit que le mieux serait de copier au plus près le comportement des versions "authentiques" de Lode Runner, donc j'ai repompé le code de KGoldRunner et ça marche nickel

J'essaierai de proposer une release pendant les vacances de février

J'espère que les niveaux que je t'avais filé te serviront ^^

Ben là je ne retrouve plus le zip. Mais pour l'instant je n'en ai pas encore besoin. Je vais bien finir le moteur de jeu, puis je m'occuperai d'importer tes niveaux. Si à ce moment je ne retrouve toujours pas le zip, tu pourrais éventuellement m'en refaire un ?

No soucis ^^