1

Alors pour situer le contexte, il s'agit d'un jeu sur TI. Juste pour qu'on ne me propose pas de solutions à base de fpu et autre je ne sais quoi. grin

Mes données :
- une table d'index, représentant la map sur laquelle évolue le perso. Les éléments seront représentés par un tile 16*16
- un personnage 8*13, pouvant se déplacer pixel par pixel sur cette map.
- les coordonnées représentant le top left corner du perso
- une vitesse horizontale et une vitesse verticale.

Mon problème
Mettons que :
- mon perso a une vitesse H de 8 pixels et une vitesse V de 5 pixels.
- un bloc infranchissable se trouve 1 pixel à droite et plus bas que lui

Si j'additionne la vitesse du perso à ses coordonnées, je vais obtenir une collision.

Donc, plusieurs possibilités :

1. idéalement, faire un calcul à base de vecteur pour trouver un angle et une norme. Je sais pas faire une racine en asm, c'est réglé.
Inconvénient : c'est la solution parfaite mais la plus couteuse.

2. additionner d'abord le déplacement horizontal. Vérifier une collision. Mon perso sera donc au-dessus du bloc, pas de problème.
Additionner ensuite le déplacement vertical. Je vais me rendre compte que je vais rentrer dans un bloc, donc je m'arrête à la limite.
Inconvénient : Si j'ai une grande vitesse verticale et une faible vitesse horizontale, en proportion, je vais me retrouver sur le tile, alors que j'aurais dû tomber sur le côté, de manière réaliste.

3. Je sais pas quoi trouver d'intermédiaire, ie pas trop couteux en terme de calcul, mais suffisamment bien pour ne pas provoquer d'énormité. Comment s'y prend-t-on, usuellement, dans ce genre de jeux ?

2

2 : et si au lieu de faire toujours d'abord l'horizontal, tu fais toujours d'abord celui qui a la vitesse la plus importante, ça ne pallie pas à l'inconvénient ?
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

3

Dans un tel cas, ça ne va pas marcher :
Qjjt

Si on part du point rouge pour arriver au vert, on doit arriver sur le tile. Hors si on commence par la viteses verticale (car > Vh), on va descendre sur le côté.

Ca reste une approximation relativement bonne cependant, car on a moins de chance de se planter en commençant par la plus grande vitesse en effet. smile

Mais y a-t-il mieux ?

4

./1 > Un premier truc à voir: Est-ce que tu as des objets solides pour lesquels ton perso pourrait en 1 frame passer d'un côté à l'autre, sans qu'une détection de collision grossière ne s'en aperçoive ? (genre des ennemis ou je ne sais quoi)
Sinon la solution à tout est de discrétiser... Je veux dire... discrétise ta discrétisation (Mathématiquement: en considérant la fonction sur intervalle continu obtenue par interpolation de ta fonction discrétisée tongue)
Pour le reste c'est à peu de choses près le même principe que l'algo de bresenham. Disons que tu dois mentalement (enfin plutôt virtuellement, en l'occurence) tracer une droite de ton point d'origine à ton point de destination idéal. A chaque pixel mental tu testes les collisions de manière précise.
Ça c'est la manière 100% générique la plus basique et la plus fiable, mais selon les contraintes exactes du problème tu peux pas mal simplifier la discrétisation et/ou l'algorithme du problème.
Déjà, si tu peux appliquer l'algorithme de collision grossier (i.e. faire avancer entièrement; tester collision) et que tous tes blocs sont complètement carrés tu peux t'en tirer relativement simplement. En gros déterminer quelle direction x ou y a touché l'élément en premier, l'ajuster, et calculer l'autre (ça bouffera quelques cycles cela dit) pour que les deux d'accordent.
Tu dois également pouvoir faire un truc assez bourrin avec des tables pré-calculées si tu connais de manière assez précise l'encadrement des différents mouvement possibles.

(Oui et cross pendant que j'écrivais j'ai pas encore lu les posts tongue)
avatar
Le scénario de notre univers a été rédigée par un bataillon de singes savants. Tout s'explique enfin.
T'as un problème ? Tu veux un bonbon ?
[CrystalMPQ] C# MPQ Library/Tools - [CrystalBoy] C# GB Emulator - [Monoxide] C# OSX library - M68k Opcodes

5

pencil
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

GoldenCrystal (./4) :
Un premier truc à voir: Est-ce que tu as des objets solides pour lesquels ton perso pourrait en 1 frame passer d'un côté à l'autre, sans qu'une détection de collision grossière ne s'en aperçoive ? (genre des ennemis ou je ne sais quoi)

Je sais pas encore s'il y a des ennemis grin Pour le moment, je m'en fous on va dire, je fais un moteur.
GoldenCrystal (./4) :
Sinon la solution à tout est de discrétiser... Je veux dire... discrétise ta discrétisation (Mathématiquement: en considérant la fonction sur intervalle continu obtenue par interpolation de ta fonction discrétisée tongue.gif )

Oublie tout de suite, les maths ça fait 10 ans et c'était pas pas la gloriole. grin
GoldenCrystal (./4) :
Pour le reste c'est à peu de choses près le même principe que l'algo de bresenham. Disons que tu dois mentalement (enfin plutôt virtuellement, en l'occurence) tracer une droite de ton point d'origine à ton point de destination idéal. A chaque pixel mental tu testes les collisions de manière précise.

On va zyeuter Bresenham. Tu proposes en fait ma solution .1, la meilleurs, mais certainement la plus couteuse aussi. J'aurais voulu éviter.

PpHd, t'as fait comment pour SMA ? (et me renvoie pas aux sources, si l'algo est compliqué, je suis plus là grin)

7

Et techniquement, si tu dois privilégier une coordonnée pour avancer, privilégie la coordonnée minimum, et pas la plus grande.
Tu sais que la minimum va avancer de 0 ou 1 pixel. Si il y a collision par là c'est réglé (dans le cas 0 y'en à jamais donc simplification énorme ^^), sinon tu testes la collision dans l'autre sens (là ça requiert de connaitre le numérateur/décominateur a priori... mais tu n'as à le calculer qu'une fois par vecteur, donc même en utilisant un DIVS sur 68k c pas la mort), et si il y a tu n'as aucun problème à ajuster la coordonnée par la suite...
avatar
Le scénario de notre univers a été rédigée par un bataillon de singes savants. Tout s'explique enfin.
T'as un problème ? Tu veux un bonbon ?
[CrystalMPQ] C# MPQ Library/Tools - [CrystalBoy] C# GB Emulator - [Monoxide] C# OSX library - M68k Opcodes

8

Zerosquare m'a fait préciser pas mal d'infos manquantes sur irc :
Mes sprites sont assimilables à des rectangles, donc techniquement, on est pas dans le cas de recherche de collision au pixel près.

J'ai eu une idée :
- je fais le rapport X == Vitesse_la_plus_grande / Vitesse_la_plus_petite
- je déplace mon sprite de X pixels dans la direction la plus grande, puis de 1 dans la direction la plus petite.

Ca devrait réduire l'erreur qui consiste à se déplacer à fond dans une direction puis à fond dans l'autre. Ca revient à faire l'algo de monsieur mDebenmachin, mais sans tenir compte de l'erreur.

C'est honnête à votre avis, étant donné que je ne cherche pas la précision ultime, mais à garder une bonne vitesse ?

9

Je propose de tester d'abord l'horizontal, puis le vertical si on descend, et d'abord le vertical, puis l'horizontal si on monte, ça va faire que le personnage se retrouve sur le tile en cas de doute, donc c'est le moins frustrant pour le joueur.
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é

10

Folco (./6) :
PpHd, t'as fait comment pour SMA ? (et me renvoie pas aux sources, si l'algo est compliqué, je suis plus là biggrin.gif )

==>
Kevin Kofler (./9) :
Je propose de tester d'abord l'horizontal, puis le vertical si on descend, et d'abord le vertical, puis l'horizontal si on monte, ça va faire que le personnage se retrouve sur le tile en cas de doute, donc c'est le moins frustrant pour le joueur.


11

Folco > tu n'as pas forcément besoin de calculer angle, norme et tout, mais effectivement il faut sans doute suivre l'idée de GoldenCrystal et tester étape par étape.
Mais tu peux peut-être te contenter de ceci : au total ton perso va se déplacer de 5+8 = 13 pixels. La seule chose à déterminer est l'ordre des déplacements (horizontal/vertical) pour que ce soit réparti équitablement : en gros il s'agit d'intercaler les déplacements d'un pixel vers la droite et d'un pixel vers le bas. Déjà tu peux considérer que comme H est plus grand que V il y aura toujours un déplacement (d'un ou plusieurs pixels) vers la droite entre deux déplacements vers le bas, et tu peux aussi commencer et finir par la droite. Donc le déplacement vers la droite va être réparti en 5+1 = 6 étapes, et ce déplacement doit être de 8, ce qui fait un pixel par étape plus deux pixels à répartir. Comment les répartir, ben 6/3 = 2 donc par exemple en troisième et sixième position (si tu t'en fous que ce soit symétrique).

Ainsi donc tu obtiens la séquence : DBDBDDBDBDBDD, et tu testes les collisions à chaque fois.

(edit : cross, je répondais à ./6)
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

12

Folco (./8) :
Zerosquare m'a fait préciser pas mal d'infos manquantes sur irc :
Mes sprites sont assimilables à des rectangles, donc techniquement, on est pas dans le cas de recherche de collision au pixel près.

J'ai eu une idée :
- je fais le rapport X == Vitesse_la_plus_grande / Vitesse_la_plus_petite
- je déplace mon sprite de X pixels dans la direction la plus grande, puis de 1 dans la direction la plus petite.

Ca devrait réduire l'erreur qui consiste à se déplacer à fond dans une direction puis à fond dans l'autre. Ca revient à faire l'algo de monsieur mDebenmachin, mais sans tenir compte de l'erreur.

C'est honnête à votre avis, étant donné que je ne cherche pas la précision ultime, mais à garder une bonne vitesse ?

C'est ce que j'ai écrit dans le post au dessus (enfin non faut inverser grand/petit ! embarrassed)
Mais oui ça marche. Par contre ce que j'ai pas précisé c'est que tu peux également déterminer quel axe à généré la collision dans le cas où tu as double collision x/y. (Faut comparer par rapport à la moitité de max(|vx|, |vy|))
Et en fait il se trouve que tu peux pré-calculer les divisions assez facilement donc réduire énormément le temps de calcul... Enfin si tu peux suffisamment borner tes vitesses tongue
avatar
Le scénario de notre univers a été rédigée par un bataillon de singes savants. Tout s'explique enfin.
T'as un problème ? Tu veux un bonbon ?
[CrystalMPQ] C# MPQ Library/Tools - [CrystalBoy] C# GB Emulator - [Monoxide] C# OSX library - M68k Opcodes

13

En fait j'avais pas vu le post ./8, mais je trouve ça bizarre de ne pas tenir compte du reste de la division (ce que tu as l'air de faire), ça veut dire que si tu te déplaces de 10 pixels vers la droite et de 19 pixels vers le bas tu vas faire BDBDBDBDBDBDBDBDBDBDBBBBBBBBB ? c'est certes mieux que de faire d'abord toute une direction puis toute l'autre, mais est-ce acceptable dans ton contexte ?
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

14

Ah oué j'avais pas vu ce détail dans son post cheeky
Non c'est clairement pas acceptable, surtout que garder compte du reste coute pas vraiment cher en calculs, et c'est déjà fourni par le calcul de la division si tu utilises l'instruction du 68k. (pour les tables c'est toi qui choisit donc la question se pose pas)
avatar
Le scénario de notre univers a été rédigée par un bataillon de singes savants. Tout s'explique enfin.
T'as un problème ? Tu veux un bonbon ?
[CrystalMPQ] C# MPQ Library/Tools - [CrystalBoy] C# GB Emulator - [Monoxide] C# OSX library - M68k Opcodes

15

Bon, ben merci à tous \o/ smile

Je vais prendre la solution de KkHd :
- c'est la plus simple et la plus rapide
- ça a fait ses preuves parce que SMA c'est le pied grin

Merci pour tout. happy

16

PpHd (./10) :
Folco (./6) :
PpHd, t'as fait comment pour SMA ? (et me renvoie pas aux sources, si l'algo est compliqué, je suis plus là biggrin.gif )

==>
Kevin Kofler (./9) :
Je propose de tester d'abord l'horizontal, puis le vertical si on descend, et d'abord le vertical, puis l'horizontal si on monte, ça va faire que le personnage se retrouve sur le tile en cas de doute, donc c'est le moins frustrant pour le joueur.

Great minds think alike. smile
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é

17

Bon, ce problème est donc résoudru.

Passons à un autre : celui de la décélération de mon perso, une fois qu'il monte :
Si on saute ou qu'on passe sur un bumper, il prend une vitesse verticale de 15pixels par frame. Ok. Si je réduis d'un pixel par frame sa vitesse ascentionnelle, il va avoir une décélération complètement linéaire, ce qui n'est pas le cas en vrai, si je me rappelle bien de mes cours de physique.

Que faire ? Une table précalculée ferait l'affaire (mettons que pour toute vitesse de 1 à 15, j'accorde tanr de pixels de décélération, en suivant une courbe non linéaire). Ca irait ?

18

Euh, si, une réduction constante de la vitesse à chaque frame est bien correcte. L'accélération g est constante, donc la vitesse est linéaire en fonction du temps et donc le déplacement de l'objet suit une équation quadratique.
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é

19

Ouais comme dit Kevin.
Le seul truc vraiment important à prendre en compte au delà de ça ce seraient les frottements de l'air (dans ton cas, tu met un max sur la valeur absolue de ta vitesse ça suffira amplement)
avatar
Le scénario de notre univers a été rédigée par un bataillon de singes savants. Tout s'explique enfin.
T'as un problème ? Tu veux un bonbon ?
[CrystalMPQ] C# MPQ Library/Tools - [CrystalBoy] C# GB Emulator - [Monoxide] C# OSX library - M68k Opcodes

20

Pas besoin de tables. Tu peux faire un moteur physique élémentaire mais correct avec quelques calculs simples :

- tu définis 3 variables pour chaque axe (X et Y) : position, vitesse et accélération
- à chaque frame, tu fais vitesse = vitesse + accélération + gravité, et position = position + vitesse.

Après il faut définir quelques conditions :

- gravité c'est nul en X ; en Y, une constante positive (c'est l'attraction terrestre), ou zéro si tu touche le sol (équilibre des forces).
- si la vitesse en X ou en Y est supérieure à un seuil, tu la rends égale à ce seuil (c'est la résistance de l'air ; en vrai c'est plus complexe, mais c'est suffisant comme approximation pour un jeu).
- sauter correspond à ajouter (une seule fois) une vitesse initiale dans le sens où se fait le saut

Voilà, grâce à ça tu obtiens naturellement des courbes de saut semblables aux vraies. Après tu peux t'amuser à plein de trucs rigolos (modifier la gravité selon les niveaux, créer des chocs mous/élastiques en changeant le signe de la vitesse et en multipliant par une constante quand tu touches un obstacle, etc...)

EDIT : cross

EDIT2 : tous ces calculs doivent être effectués en virgule fixe (ou flottante, mais faut pas rêver tongue), sinon l'algorithme sera plombé par les problèmes d'arrondi.
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

21

EDIT2 : tous ces calculs doivent être effectués en virgule fixe (ou flottante, mais faut pas rêver tongue )

Motorola a fait en 1978 des routines floating-point rapides (floats binaires sur 32 bits) pour 68000, mais:
* la version originale de ces routines a une convention d'appel nettement différente de toutes les conventions classiquement utilisées par les softs pour TI-68k (tous OS et environnements confondus);
* ici, l'arithmétique fixed-point est plus rapide tout en donnant des résultats tout à fait honnêtes.
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

22

Je confirme que la virgule fixe est sans doute la meilleure solution.
Pour exemple dans grav, j'ai tenté une version avec des float et ca ne fonctionne pas, c'est trop lent eek

Sinon je pense que les ti68k sont largement assez puissantes pour faire tourner ce genre de moteur, pourquoi ne pas vouloir utiliser la version précise ?
Visitez mon site : http://www.bobti89.fr.st
Testez mon forum ici

23

Parce que c'est une histoire de compromis. Il y a trop peu à gagner par rapport à la perte, à mon sens.

24

Bon permettez-moi de faire un petit répiculatacutif de tout ce moteur. smile (J'étais pas une flèche en méca grin)

J'ai donc 3 éléments pour chaque axe :
- position, vitesse, accélération.

Donc, les éléments qui influent sur mon bonhomme, c'est ça :
- les touches directionnelles mettent une constante dans l'accélération tant que la vitesse n'a pas atteint un certain plafond
- la gravité augmente la vitesse verticale de manière linéaire
- un obstacle annule la vitesse dans l'axe concerné
- un sol diminue la vitesse horizontale de manière constante (Vhz = Vhz * c, avec c<=1)

Devrais-je simuler une bonne approximation de la physique avec ça ?
Je suis conscient du fait que les frottements sont très imparfaits, car ce sont eux qui devraient limiter la vitesse horizontale, qu'il est plus facile de plafonner à la main.
Ca vous semble honnête comme modélisation ?

25

physique exacte dépend de ton personnage précis, mais en gros pour un personnage standard (avec des pieds), l'accélération horizontale est quasi toujours nulle. En fait ça fait un truc un peu comme ça: /\ / \ ---- ---------------- - \ / \/ 0 1 2 3 4 5 6 7Bah, techniquement pour un personnage de jeu vidéo normal, l'accélération est toujours quasi nulle (mais la vitesse non), et non, le sol ne doit pas modifier la vitesse. La modélisation 0. le personnage est à l'arrêt
1. le personnage commence à marcher/courrir
2-5. le personnage est à sa vitesse de croisière
6. le personnage commence à freiner
7. le personnage est à l'arrêt

La courbe d'accélération exacte dépend entièrement de ton personnage mais elle doit à priori toujours avoir une forme semblable.
Ça prend en gros en compte le temps d'accélération physique pour le début et les frottements avec le sol à la fin. (Je rapelle, le perso a des pieds ici ^^)
Pour le reste le seul vrai frottement que tu aurais à prendre en compte c'est avec l'air, et ça c'est négligeable.
En revanche tu pourrais avoir du vent, qui entrainerait éventuellement lui de devoir gérer des frottements avec le sol, mais ça dépend du cas précis là encore.
avatar
Le scénario de notre univers a été rédigée par un bataillon de singes savants. Tout s'explique enfin.
T'as un problème ? Tu veux un bonbon ?
[CrystalMPQ] C# MPQ Library/Tools - [CrystalBoy] C# GB Emulator - [Monoxide] C# OSX library - M68k Opcodes

26

Ben si un sol ne diminue pas la vitesse horizontale ça signifie que si tu commences à courir et que tu lâches le bouton le personnage continue à courir indéfiniment jusqu'à ce que tu freines confus
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

27

Ok merci. Bonne idée, uen petite brise, une simple constante. cheeky

Par contre, comme Sally, si je compte sur les frottements de l'air pour arrêter le perso, c'est la patinoire. grin

28

(aka super mario bros)
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

29

Sally (./26) :
Ben si un sol ne diminue pas la vitesse horizontale ça signifie que si tu commences à courir et que tu lâches le bouton le personnage continue à courir indéfiniment jusqu'à ce que tu freines confus

Non le truc c'est pas ça, c'est que tes pieds (oui j'ai précisé un personnage avec des pieds) s'appuient sur la friction avec le sol pour te permettre d'avancer. Mais en aucun cas c'est la friction qui limite ta vitesse. En fait pour nous c'est justement l'inverse. Plus la friction, ou ce qui peut s'assimiler à la friction est faible (cf sol gelé ou feuilles mortes dans la fôret...), plus on patine. En gros moins y'a de friction moins on contrôle notre vitesse, car tout comme on s'appuie sur la friction pour freiner, on le fait également pour accélérer tongue
Mais avec une friction normale, et dans une certaine mesure qui ici parait raisonnable (un humain ou un animal quoi), la limite de vitesse atteignable est purement physique.

En gros tu vas chercher à simuler réellement les frottements avec le sol *surtout* quand tu voudras simuler l'absence de frottements :]
(typiquement la patinoire)
avatar
Le scénario de notre univers a été rédigée par un bataillon de singes savants. Tout s'explique enfin.
T'as un problème ? Tu veux un bonbon ?
[CrystalMPQ] C# MPQ Library/Tools - [CrystalBoy] C# GB Emulator - [Monoxide] C# OSX library - M68k Opcodes

30

Oui ok, mais alors ici ce n'est pas une question de simulation physique mais de contrôle. En quelque sorte l'idée est que quand tu appuies sur droite tu dépenses une certaine énergie à avancer (cette énergie utilise en effet les frottements du sol pour te propulser si tu es par terre, et utilise de la magie propre aux jeux de plate-forme si tu es en l'air, mais peu importe). Quand tu lâches droite, tu cesses de dépenser cette énergie et, *si tu es par terre* et que ça ne glisse pas, tu vas spontanément ralentir (en raison des frottements du sol). C'est différent de freiner où tu vas activement utiliser de l'énergie (et toujours les frottements) pour diminuer ta vitesse plus rapidement. Il faut qu'il y ait les deux formes de ralentissement, décélération spontanée et freinage actif, a priori.

Le fait que tout ça vienne en réalité d'utilisations différentes de la friction du sol n'est pas très important, il s'agit juste de simuler l'effet des contrôles de façon simplifiée.
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#