PureBasic

Bah on va aussi dire qu'un bêta-testeur on se doute bien que c'est pas un alpha-gamer héhé, de tout façon je suis pas un grand gamer, mais ton jeu à l'air vraiment sympa

Contrairement à ce que l'on pourrait penser, je ne suis pas non plus un grand amateur de jeux vidéos classiques. Par contre les RPG offrent quelque chose de différent des jeux habituels : la possibilité de raconter une véritable épopée, de la développer pendant des heures en donnant au joueur le premier rôle.
Pour moi, peu importe les graphismes, aucun film ou livre n'arrive à la cheville d'un bon RPG ;p

Les RPG sont malheureusement souvent trop enfantins, alors qu'ils gagnent tellement meilleurs lorsqu'ils s'adressent à un public plus mature où lorsque leur univers est très développé.
Je pense à des jeux Fallout (I et II), Secret Of Mana ou encore FF7 (tout jolis qu'ils soient, les autres FF ne tiennent pas la comparaison), trois RPG totalent différents qui resteront gravé dans ma mémoire à tout jamais.

Nostalgie...

Pareil, Falout I et II, Secret Of Mana, et FFVI parcontre, pas le VII, sont restés et resteront gravés dans ma mémoire

Juste une petite question technique de débutant. Vous savez combien de temps prend un processeur moyen pour faire le tour d'une boucle vide, pour tester un if et pour effectuer un calcule simple dans un tableau ?

J'ai mis au point un algorithme de pathfinder qui me semble assez efficace pour l'IA des coéquipiers et des ennemis mais je ne veux éviter les mauvaises surprises à la programmation tant qu'il en est encore temps.

Code : Tout sélectionner

T1 = ElapsedMilliseconds()

For n = 1 To 1000000000
  
Next

T2 = ElapsedMilliseconds()

MessageRequester("Temps", Str(T2 - T1) + " ms")

6.6 s pour 1 milliard de tour de la boucle For sur mon 900mhz et avec du bazar qui tourne en arrière plan

donc 1 million de tour de boucle For, ça fait 6 ms

C'est vrai que l'on n'est jamais mieux servit que par sois-même ;p
Merci Soldat Inconnu pour m'avoir donné les vitesses sur un 900Mhz.

Apparament si on ajoute un if vide dans la boucle, elle est 2.5 fois plus lente.

Si on ajoute un if vide qui test un tableau de structure, elle est alors 40 fois plus lente !

Structure bla
test.s
blabla.l
test2.l
coucou.l
EndStructure

Dim tab.bla(200,200)

T1 = ElapsedMilliseconds()

For n = 1 To 1000000000
If tab(10,15)\test2 = 897376
EndIf
Next

T2 = ElapsedMilliseconds()

MessageRequester("Temps", Str(T2 - T1) + " ms")

Pour ce genre de test, pensez a décocher le Debugger

Tu as raison, c'est deux fois plus rapide sans le débuggeur, mais bon ça permet aussi d'avoir une bonne marge de sécurité ;p

J'ai mis au point l'algorithme du pathfinder, j'avais déjà fait des tentatives par le passé mais avec de trop grandes contraintes liées à la lenteur des langages. Après 8 heures de réflexion je pense avoir un bon compromis boustant les performances sans tâtonnement et dans le cas d'un décors dense les personnages vont parfois devoir longer un mur trop grand.

Pour résumé j'utilise la cartographie créée par l'éditeur de map, je lui donne a manger les coordonnées du point de départ et du point à atteindre et il génère un waypoint. Une fois arrivé au waypoint ou si la cible bouge tout en étant à faible distance, il relance son script de pathfinder et se génère un nouveau waypoint.

Je ne vais pas entrer dans les détails, mais je vais essayer de modifier ce vieux code de Comptois (si il m’y autorise bien sur) pour tester ma méthode totalement différente, ça devrait être bien plus rapide et le chemin devrait répondre aux spécificités de LDE et donc plus correspondre au comportement d’un humain en terrain inconnu (on verra bien ;p).

; ***********************************************************
; ** Comtois le 15/08/03 - Pathfinding pour Purebasic V0.2 **
; ***********************************************************
;Rapidement retouché le 24/01/05

; **********************************************************************
; ************************** Mode d'emploi *****************************
; **********************************************************************
; ** Touche [F1] pour Afficher les cases Closed / Open **
; ** Touche [F2] pour Afficher le chemin **
; ** Bouton Gauche de la souris ajoute un mur **
; ** Bouton Droit de la souris efface un mur **
; ** Bouton Gauche de la souris + la Touche [Shift] Déplace la cible **
; ** Bouton Droit de la souris + la touche [Shift] Déplace le départ **
; **********************************************************************

; --- Initialisation ---
If InitSprite() = 0 Or InitKeyboard() = 0 Or InitMouse() = 0
MessageRequester("Erreur", "Impossible d'initialiser DirectX 7 Ou plus", 0)
End
EndIf

; --- Plein écran ---
#ScreenWidth = 800
#ScreenHeight = 600
#ScreenDepth = 16
If OpenScreen(#ScreenWidth,#ScreenHeight,#ScreenDepth,"Essai Pathfinding") = 0
MessageRequester("Erreur", "Impossible d'ouvrir l'écran ", 0)
End
EndIf
; --- Variables globales ---
Global ciblex,cibley,departx,departy, AffOpenClosed,affPath
affPath=1

; --- dimension du tableau et taille d'une case ---
#max_x=48
#max_y=48
#taille=12
; --- positionne la cible sur la grille ---
ciblex=1+Random(#max_x-2)
cibley=1+Random(#max_y-2)

; --- positionne le départ sur la grille ---
departx=1+Random(#max_x-2)
departy=1+Random(#max_y-2)

; --- pour la recherche du chemin ---
Dim map(#max_x,#max_y)
Dim open(#max_x+1,#max_y+1)
Dim parent(#max_x,#max_y,1)
Dim F(#max_x,#max_y)
Dim G(#max_x,#max_y)
Dim H(#max_x,#max_y)
Dim closed(#max_x+1,#max_y+1)
Dim path(#max_x*#max_y,1)

; ************************************************************************************
; *** LES SPRITES ***
; ************************************************************************************
Enumeration
#depart
#cible
#Souris
EndEnumeration

;/Départ
CreateSprite(#depart, #taille, #taille)
StartDrawing(SpriteOutput(#depart))
Circle(#taille/2,#taille/2,(#taille/2),RGB(255,255,255))
StopDrawing()
;/Cible
CreateSprite(#cible, #taille, #taille)
StartDrawing(SpriteOutput(#cible))
Circle(#taille/2,#taille/2,(#taille/2),RGB(255,55,18))
StopDrawing()
;/ Souris
CreateSprite(#Souris, #taille, #taille)
StartDrawing(SpriteOutput(#Souris))
DrawingMode(4)
Box(1,1,#taille-1,#taille-1,RGB(100,200,255))
StopDrawing()

; ************************************************************************************
; *** LES PROCEDURES ***
; ************************************************************************************
Procedure mur()
Couleur=RGB(100,100,255)
StartDrawing(ScreenOutput())
For y=0 To #max_y
For x=0 To #max_x
If map(x,y)
xa=x*#taille
ya=y*#taille
Box(xa + 1,ya + 1,#taille - 1,#taille - 1,Couleur)
EndIf
Next x
Next y
StopDrawing()
EndProcedure
Procedure init()
path(0,0) = 0
;faire le point sur ce qui est vraiment utile d'initialiser
For a = 0 To #max_x
For b = 0 To #max_y
open(a,b) = 0
parent(a,b,0) = 0
F(a,b) = 0
G(a,b) = 0
H(a,b) = 0
closed(a,b) = 0
Next b
Next a
EndProcedure

Procedure.w ChercheChemin()
; C'est mon interprétation du fameux A*
init()
If departx=ciblex And departy=cibley
fin=2
EndIf
; --- on met le point de départ dans la liste open ---
open(departx,departy)=1
; --- calcul F = G + H pour la Case de départ ---
F(departx,departy)=-1
; --- tant que la liste open n'est pas vide et tant qu'on a pas trouvé la cible
While fin = 0
; --- on cherche la Case la plus avantageuse ( avec F le plus bas) ===
meilleurF = 0
For a = 0 To #max_x
For b = 0 To #max_y
; --- si la Case est open ---
If open(a,b) = 1 And closed(a,b) = 0 And (F(a,b) < meilleurF Or meilleurF = 0)
meilleurF = F(a,b)
x = a
y = b
EndIf
Next b
Next a
; --- il n'y a pas de chemin ---
If meilleurF = 0
fin = 2
EndIf
; --- on met la Case trouvée dans la liste closed
closed(x,y) = 1
; --- on teste les cases autour si fin = 0 ===
; dans cette version le déplacement se fait dans les huits directions
; il est possible d'ajouter un paramètre pour limiter les déplacements à 4 directions
If fin = 0
For a = x - 1 To x + 1
For b = y - 1 To y + 1
; ---- si la Case est libre et n'a pas encore été traitée
If a >= 0 And a <= #max_x And b >= 0 And b <= #max_y
If map(a,b) = 0 And closed(a,b) = 0
interdit = 0
If a=x-1 And b=y-1 And map(x,y-1)=1 And map(x-1,y)=1 : interdit=1 : EndIf
If a=x-1 And b=y+1 And map(x,y+1)=1 And map(x-1,y)=1 : interdit=1 : EndIf
If a=x+1 And b=y-1 And map(x,y-1)=1 And map(x+1,y)=1 : interdit=1 : EndIf
If a=x+1 And b=y+1 And map(x,y+1)=1 And map(x+1,y)=1 : interdit=1 : EndIf
If interdit = 0
; calcule G pour la Case en cours de test ( à adapter selon le jeu)
; si la distance n'a pas d'importance , on peut se contenter de calculer
; le nombre de cases , donc de faire G = G(x,y) + 1
If Abs(a - x) > 0 And Abs(b - y) > 0
G = 14 + G(x,y)
Else
G = 10 + G(x,y)
EndIf
; si la Case n'est pas dans la liste open
If open(a,b) = 0 Or G < G(a,b)
open(a,b) = 1
parent(a,b,0) = x
parent(a,b,1) = y
; --- calcule F = G + H
G(a,b) = G
distance = (Abs(ciblex-a) + Abs(cibley-b))*10
H(a,b) = distance
F(a,b) = G(a,b) + H(a,b)
; --- la cible est trouvée ---
If a = ciblex And b = cibley
fin = 1
Break 2
EndIf
EndIf
EndIf
EndIf
EndIf
Next b
Next a
EndIf
Wend
ProcedureReturn fin
EndProcedure
Procedure souris(ToucheShift)
If ExamineMouse()
SX = MouseX() / #taille
SY = MouseY() / #taille
If SX >= 0 And SX <= #max_x And SY >= 0 And SY <= #max_y
If ToucheShift = 0
If MouseButton(1)
map(SX,SY)=1 ;place un mur
ElseIf MouseButton(2)
map(SX,SY)=0 ; supprime un Mur
EndIf
Else
If MouseButton(1)
ciblex = SX : cibley = SY ; place la cible
ElseIf MouseButton(2)
departx = SX : departy = SY ; place le départ
EndIf
EndIf
EndIf
EndIf
EndProcedure
Procedure AffOpenClosed()
CoulOpen=RGB(200,255,200)
CoulClosed=RGB(255,200,200)
StartDrawing(ScreenOutput())
For y=0 To #max_y
For x=0 To #max_x
xa=x*#taille
ya=y*#taille
If closed(x,y)
Box(xa + 1,ya + 1,#taille - 1,#taille - 1,CoulClosed)
ElseIf open(x,y)
Box(xa + 1,ya + 1,#taille - 1,#taille - 1,CoulOpen)
EndIf
Next x
Next y
StopDrawing()
EndProcedure
Procedure affPath()
If ChercheChemin()=1
a=-1
b=-1
cx=ciblex
cy=cibley
Couleur=RGB(255,255,100)
StartDrawing(ScreenOutput())
While a <> departx Or b <> departy
a = parent(cx,cy,0)
b = parent(cx,cy,1)
xa=(cx*#taille)+#taille/2
ya=(cy*#taille)+#taille/2
xb=(a*#taille)+#taille/2
yb=(b*#taille)+#taille/2
LineXY(xa,ya,xb,yb,Couleur)
cx = a
cy = b
Wend
StopDrawing()
EndIf
EndProcedure
Procedure AffCadre()
Couleur=RGB(255,255,255)
StartDrawing(ScreenOutput())
DrawingMode(4)
Box(0,0,#taille*(#max_x+1),#taille*(#max_y+1),Couleur)
StopDrawing()
EndProcedure
; ************************************************************************************
; *** BOUCLE PRINCIPALE ***
; ************************************************************************************
Repeat
ClearScreen(0,0,0)
;/ état du clavier
If ExamineKeyboard()
If KeyboardReleased(#PB_Key_F1)
AffOpenClosed=1-AffOpenClosed
EndIf
If KeyboardReleased(#PB_Key_F2)
affPath=1-affPath
EndIf
ToucheShift = KeyboardPushed(#PB_Key_LeftShift) Or KeyboardPushed(#PB_Key_RightShift)
EndIf
;/ Gestion de la souris
souris(ToucheShift)
;/affiche le fond
mur()
AffCadre()
If AffOpenClosed
AffOpenClosed()
EndIf
;/Lance la recherche
If affPath
affPath()
EndIf
;/Affiche les sprites
DisplayTransparentSprite(#Souris,MouseX() - #taille / 2,MouseY() - #taille / 2)
DisplayTransparentSprite(#cible,ciblex * #taille,cibley * #taille)
DisplayTransparentSprite(#depart,departx * #taille,departy * #taille)
FlipBuffers()
Until KeyboardPushed(#PB_Key_Escape)
End

(Très pratique ton script pour un test préalable).

bien sur que tu peux le modifier ,et n'hésite pas à nous montrer le résultat.

c'est toujours intéressant de voir d'autres méthodes ou des améliorations , et il y en a à faire , mais bon, je remets toujours à plus tard

Merci beaucoup Comtois, je vais utiliser le système d'affichage, il est vraiment impeccable pour bloquer/débloquer les cases, placer les positions de départ et d'arrivé facilement et simuler plein de situations (et la il y en a bien besoin ;p).

Sinon je ne sais pas si quelqu'un s'y est déjà essayé, mais créer une procédure LongerLeMur la plus brève possible n'est pas si évident ^^.

Edit : Je le fais avec une variable "direction" (qui me donne le sens de déplacemnt actuel) et une variable "accorché" (qui me dit quel coté de la case on longe). A partir de ca je distingue 24 cas différents (2 directions possibles pour un "accorché" et 3 cas par "direction").

C'est extrèmement rapide à exécuter, mais si à une meilleure méthode (en utilisant la trigonométrie pour tourner autour des caases peut-être) je suis preuneur.

dans une autre version , j'avais ajouté
une touche pour sauvegarder la map
une touche pour charger la map
une touche pour tout effacer

j'avais aussi ajouté un chrono pour vérifier si les modifs amélioraient ou dégradaient les performances ,et ceci pour différentes maps de référence.

à l'époque je testais une dll écrite en C , je dois encore l'avoir , faudrait que je fouille . J'avais aussi une fonction qui précalculait les maps , ça réduisait la recherche en délimitant les zones accessibles. l'algo est basé sur le remplissage d'une surface, si je ne pouvais pas détecter la cible en remplissant la surface de la map en partant du point de départ, c'est qu'il n'y avait pas de chemin possible , par contre , je pouvais relever la position la plus proche de la cible , et du coup le pathfinding ne perdait pas son temps à chercher des chemins impossibles , il cherchait le chemin pour aller au point le plus proche de la cible .

si c'est pas clair , tu peux toujours poser des questions

Si j'ai bien compris tu précalculais des points passables importants en untilisant un remplissage de la surface de la carte, puis tu allait directement vers le plus proche de la cible ? ( Dans ce cas tu devais passer par des points intermédiaires non ?)
Le problème avec les jeux c'est qu'il faut éviter de relancer le pathfinding trop souvent (une fois par pas c'est déja beaucoup lorsqu'il y a 100 unités à afficher et plein d'autres petites choses à tourner derrière).

Pour le moment je test une méthode consistant à partir dans 2 directions et à longer les murs jusqu'a ce que la cible puisse être rejointe par deux vecteurs. Je garde le premier parcours arrivé le premier et je place un waypoint que mon personnage peut rejoindre (en diagonale ou direction si la diagonale est impossible). Arrivé au waypoint ou si la cible à changé de place je relance un coup de pathfinder.
Je n'arrive pas a calculer la vitesse du script car il place le waypoint en moins d'une ms pour le moment, mais il reste quelques correctifs à ajouter car certains cas ne fonctionnent pas correctement (ça doit pouvoir se résoudre en créant des points de passage (en compilant la carte) si on est dans une certaine zone et que l'on veut en sortir).

Je ne suis pas très doué pour expliqué, je mettrai le code une fois terminé (ce qui risque d'être relativement plus long que prévus ;p).

Le pathfinder est un sujet très intéressant, si tu retrouve d'anciennes tentatives à toi je suis preneur ^^.

j'ai déjà donné cette adresse plusieurs fois , mais il est toujours bon de la rappeler

http://www.vieartificielle.com/article/ ... cle&id=178

Tu pourras peut-être y puiser quelques idées.

A ce sujet, tu as essayer le Quick Sort de ton Comtois?
J'ai pas encor trouver le temps de le faire moi... Et j'ai toujours quelques soucis avec la version "Threadée"... (Un bug en cache toujours un autre

)

J'ai déja lu cet article par le passé, mais une petite relecture ne me fera pas de mal, merci ;p

PureBasic

La Dernière Etreinte & Editeur de cartes - développement