A* Pathfinding (he oui, encore :) - Page 1

Ceux qui ont déjà fait un pathfinding verront tout de suite quel est le problème, je pense. Les autres, lisez bien, le probleme n'est pas directement lié au pathfinding lui même.

Pour "trouver son chemin", il faut utiliser une matrice dont toutes les cases valent initialement 0 (case valide), puis les mettre à 1 au fur et à mesure qu'on trouve des cases à éliminer.
Normalement, il faut donc faire un gros "memset 0" sur sa matrice, pour la fixer à 0 et commencer un pathfinding, mais je vais avoir besoin d'en effectuer un grand nombre assez rapidement, donc j'aimerais éviter ce memset.

J'ai envisagé la solution de considérer la valeur "1" comme "case occupée". La matrice se remplit donc un peu partout de 1. Au pathfinding suivant, on code "case occupée" par 2, ce qui fait que les anciennes cases (qui valaient 0 ou 1) sont de toute façon considérées comme "libres", et on évite ainsi le memset.
Le problème est que quand on arrive à 255, 65535, etc..., il faut repartir de 0, et alors là il y a le risque de retomber sur d'anciennes cases considérées comme "occupées" par un pathfinding anterieur. Par exemple quand la valeur "occupée" est 2, et que l'on tombe sur une case qui vaut 2, il n'y a pas de moyen de savoir si cette case a été déclarée comme occupée à ce pathfinding, ou bien à un autre qui a eu lieu bien avant, à un moment ou la valeur "occupée" était également 2.

En me relisant je n'ai pas l'impression d'avoir été très clair... Enfin si qqun a une solution qui permet d'éviter le memset, et qui n'ait pas cet inconvegnant, je suis preneur

Tu n'a qu'à faire un memset au bout de 255 pathfinding. (et tu codes tes trucs sur des bytes, ça sera moins long à effacer).

Vertyos a écrit :
...Enfin si qqun a une solution qui permet d'éviter le memset, et qui n'ait pas cet inconvegnant, je suis preneur

"éviter le memset"
J'ai pensé aussi à cette solution qui est un mélange des deux que j'explique dans mon post, mais je cherche une méthode qui permette de ne faire aucun memset

Enfin, un memset tous les 255 times, ça me paraît tout à fait raisonnable...

Oui et non... Si je ne trouve pas d'autre solution c'est ce que je ferais, mais le but de ce topic était de m'assurer qu'il n'y a pas mieux avant

Pkoi tu utilise pas la mm 'matrice' pour tout; en utilisant un pointeur et des acces différent, exemple:

unsigned char *pPrincpal = NULL;
unsigned char *pP1,*pP2,*pP3, ..., *pPn;

pPrincipal = malloc(TAILLE_TOTALE_PAR_TABLEAU*n);
pP1 = (pPrincipal + TAILLE_TOTALE_PAR_TABLEAU*n-1);
[i]...[/i]
pPn = (pPrincipal);

[i]// Affectation des Matrices[/i]
*(pP1 + larg*j+i) = nombre ;
[i]...[/i]
*(pPn + larg*j+i) = nombre ;

Bref, un memeset sur pPrincipal permet de tout effacer ...

Pyroangel powaaaaaaaaaaa
Djikstra for evaaaaaaaaaaa

nEUrOne > Oulà c'est très couteux en memoire ça...

Moumou >

Et pourquoi tu veux pas utiliser memset? Parce que c'est trop lent?

Oui, quand la map est trop grande, si il faut faire 1 pathfinding toutes les 1/2 secondes ça va serieusement se ressentir (bon j'exagere là mais il faudra quand même en faire beaucoup).

faqhard ?

à qd Vertel version pathfinding?

J'ai pas comprit la blague là

Vertyos: nan, ce n'est pas tres conteux en mémoire ... y'a pire

Vertyos> Si le memset est trop lent, fais ce qu'il fait toi-même... C'est-à-dire remets toutes les valeurs à zéro en C ou en assembleur pour faire plus rapide! (En utilisant tous les registres ou presque et movem)
C'est quand même vrai que si tu peux trouver une autre méthode pour ne pas l'utiliser aussi souvent, ou même éviter de l'utiliser, c'est mieux.

Attendez, memset est assez rapide pour ce qu'il est prévu pour faire ... seulement, c'est vrai que pour effacer un bon nombre de tableaux, ben il est largué et c'est normal ...
Vertyos: essaie avec la méthode que je te suggère histoire quand même de voir la "place" que ca prend. Si c'st insuportable, utilises en effet un memset perso tirée un ClrScr en asm bien déroulé

Mieux : les movems

je v surement dire une conneris, mais en effacant les anciennes traces au fur et à mesur que tu en créer des nouvelles ??

Ce qui implique que je dois sauver au fur et à mesure les traces pour les effacer après . Un memset à chaque cycle serait mieux

Vertyos> ben on pourrait faire un jeu de stratégie temps réel en Basic ce serait bien

Faut-il que je réponde ?

C'était ta réponse

Djikstra for evaaaaaaaaaaa

tout dépend des cas.
pour les chemins longs, et surtout, complexes, DIjkstra est plus adapté que A*
mais pour des chemins courts, et surtout, simples, A* est plus adapté, de par sa méthode heuristique

Vertyos a écrit :
Ceux qui ont déjà fait un pathfinding verront tout de suite quel est le problème, je pense. Les autres, lisez bien, le probleme n'est pas directement lié au pathfinding lui même.

Pour "trouver son chemin", il faut utiliser une matrice dont toutes les cases valent initialement 0 (case valide), puis les mettre à 1 au fur et à mesure qu'on trouve des cases à éliminer.
Normalement, il faut donc faire un gros "memset 0" sur sa matrice, pour la fixer à 0 et commencer un pathfinding, mais je vais avoir besoin d'en effectuer un grand nombre assez rapidement, donc j'aimerais éviter ce memset.

J'ai envisagé la solution de considérer la valeur "1" comme "case occupée". La matrice se remplit donc un peu partout de 1. Au pathfinding suivant, on code "case occupée" par 2, ce qui fait que les anciennes cases (qui valaient 0 ou 1) sont de toute façon considérées comme "libres", et on évite ainsi le memset.
Le problème est que quand on arrive à 255, 65535, etc..., il faut repartir de 0, et alors là il y a le risque de retomber sur d'anciennes cases considérées comme "occupées" par un pathfinding anterieur. Par exemple quand la valeur "occupée" est 2, et que l'on tombe sur une case qui vaut 2, il n'y a pas de moyen de savoir si cette case a été déclarée comme occupée à ce pathfinding, ou bien à un autre qui a eu lieu bien avant, à un moment ou la valeur "occupée" était également 2.

En me relisant je n'ai pas l'impression d'avoir été très clair... Enfin si qqun a une solution qui permet d'éviter le memset, et qui n'ait pas cet inconvegnant, je suis preneur

J'ai un embryon de solution mais d'une part je crains que ce ne soit trop difficile à mettre en oeuvre et d'autre part j'ai pas eu le temps de creuser. Enfin bref voilà l'idée

au lieu de mettre des indices croissants dans tes cases, l'utilisation de l'algèbre de gray pourrait éviter ce type de problème (c'est utilisé sur certains compteurs rapides)

Rappel en algèbre de Boole on compte : 000 001 010 011 100 101 110 111

Le principe de l'algèbre de Gray c'est qu'un seul bit ne change à chaque fois : 000 001 011 010 110 100 101 111

Ainsi en comptant le nombre de bit qui ont changé tu peux savoir si une valeur est du tableau précédent ou d'un tableau plus ancien...

squale92: je te rejoins assez dans tes propos, mais il faut rappeler que A* n'est vraiment utile que dans peu de problemes, quand il s'agit s'un simple probleme de chemin le plus court sur une map simple (on pourrait l'appeler d'une dimension, par exemple, pas de différentes surfaces qui ralentissent les vitesses...) il est inutile par rapport à Dij****a

vince a écrit :
J'ai un embryon de solution mais d'une part je crains que ce ne soit trop difficile à mettre en oeuvre et d'autre part j'ai pas eu le temps de creuser. Enfin bref voilà l'idée

au lieu de mettre des indices croissants dans tes cases, l'utilisation de l'algèbre de gray pourrait éviter ce type de problème (c'est utilisé sur certains compteurs rapides)

Rappel en algèbre de Boole on compte : 000 001 010 011 100 101 110 111

Le principe de l'algèbre de Gray c'est qu'un seul bit ne change à chaque fois : 000 001 011 010 110 100 101 111
Ainsi en comptant le nombre de bit qui ont changé tu peux savoir si une valeur est du tableau précédent ou d'un tableau plus ancien...

C'est pas bête du tout ça faudra que j'essaye

Je ne suis pas sûr que ça marche vraiment :
quand on repasse à 0, on retombe dans le même problème...

nEUrOne> certes
qd tu as un véritable labirynthe, DIkstra est plus performant (puisqu'il prend toujours le même temps pr une map, quelque soit le chemin recherché)
mais pr des chemin simples sur une carte pas trop complexe, c A* powa

(je parle d'expérience, sur ce coup)

Dites... Ici c'est A*, alors vous êtes sympa mais Dijkstra => dehors