GTAOnline.net

San Andreas Multiplayer (sa:mp) => Scripting SA-MP [Pawn center] => Discussion démarrée par: chneubeul le 08 Janvier 2014, 07:45:16

Titre: [Demande Aide] Programmation IA
Posté par: chneubeul le 08 Janvier 2014, 07:45:16
Hello cheers : )

Donc voilà j'aimerais me lancer dans la programmation d'une IA pour m'amuser et j'ai réfléchis à tous les problèmes que je pourras rencontrer, et j'ai trouvés pas mal de solution mais j'aimerais parler optimisation.

J'aimerais développer l'IA sous forme de node qui seront enregistrés par mes soins, en parcourant la map évitant ainsi les bots qui passe à travers les objets, etc.. (ce qui permettrais bien entendu aussi de passer sous les ponts par un simple check de la distance entre les nodes.. et djisktra bien entendu :) )

Admettons que j'ai enregistrés toutes mes positions dans un fichier, pour plus de rapidité, je les charges dans un array, mais lorsque mes bots voudront se déplacer et calculer un itinéraire :

qu'elle serait la façon la plus rapide pour vérifier parmis TOUS les nodes le parcours ? puisqu'il faudrait parcourir un array très très lourd.


A+, Sam.
 :cheers:
Titre: Re : [Demande Aide] Programmation IA
Posté par: Xartrick le 08 Janvier 2014, 12:07:44
Pour moi, A* serait l'un des meilleurs choix: Algorithme A* - Wikipédia (http://fr.wikipedia.org/wiki/Algorithme_A*)
Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 08 Janvier 2014, 14:39:37
Merci de ta réponse :

Lien Wikipédia vers Algo A* (http://fr.wikipedia.org/wiki/Algorithme_A*)


Tu as oublié l'* dans ton lien :p

Je connais cet algo, mais apparemment il fonctionne sur 2D
Titre: Re : [Demande Aide] Programmation IA
Posté par: Ssk le 08 Janvier 2014, 17:47:42
Bien que le jeu soit en 3d tu peux considérer que les déplacement dans la map sont en 2d.

Car de toute façon, rare sont les cas où un nœud soit au dessus d'un autre.
Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 09 Janvier 2014, 12:05:33
Salut Ssk, justement j'aimerais éviter le soucis avec les ponts, c'est pour ça, mais admettons avec l'algorythme j'ai juste à classer les données dans n'importe qu'elle ordre et parcourir le tableau avec une boucle ou ya une méthode plus rapide en scindant le tableau en zone ou autres.. ?
Titre: Re : [Demande Aide] Programmation IA
Posté par: Ssk le 09 Janvier 2014, 12:39:53
Ça dépasse mes compétences je suis désolé, je n'ai jamais programmé d'IA je ne saurai te dire :/
Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 09 Janvier 2014, 23:54:25
Yop', j'ai tester un peu de travailler dans un gros tableau mais on est vite limité par la mémoire au niveau du tableau. Je vais approfondir mes idées et les exposés demain :)


_____________________________________________________________________________________________

Bonjour,

alors voilà j'ai pris les positions de la map, elle fait 5800x5500 environ, sachant que la map n'est pas que de la terre, qu'il y a les batiments, l'eau tout ça, si on considère en gros 60% de surface exploitable on obtiendrais environ 22.000.000 de positions à répertorier et à exploiter, donc,

j'ai eu l'idée de splité l'array de façon à répartir par zone etc.. mais le compilateur crash.. évidement ! 

donc ma première question :

Quel est la taille maximum d'un tableau ?

Lors de ma recherche sur le net, je ne pensais plus à l'emplois de vecteur :


que pensez de les utilisés surtout par rapport au temps d’exécution ?


Cordialement, Sam.
:cheers:
Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 13 Janvier 2014, 19:57:48
Après test, j'ai pu créer un tableau multi dimensionnelle [sector][node][float] de cet taille : [7][220000][3]

Le compilateur peine à compiler mais j'ai réussis à en créé 3 et compiler.

Pourquoi créé ce tableau ? En faite chaque bots aura son secteur, et pourra se balader ainsi de secteurs en secteurs, et le temps d’exécution et de recherche de position sera ainsi réduits,  c'est à dire donc que les secteurs ne seront actifs que lorsqu'il y aura un joueur dedans pour profiter pleinement des bots, je vais devoir tester, et mettre en place un algorithme afin de diviser et de créé plusieurs tableau en réduisant ainsi les secteurs et la taille de ceci.

Libre à vous de me donner vos idées afin de faire profiter vos connaissances à la réalisation de ce projet.

:cheers:
Titre: Re : [Demande Aide] Programmation IA
Posté par: Ssk le 13 Janvier 2014, 20:13:34
Partager la map en plusieurs zone comme tu l'as dit et, sauver ces zones dans des fichiers.

Pour que ce soit compact et plus rapide, le faire en mode binaire.

Avec cette fonction pour lire le fichier, 

http://wiki.sa-mp.com/wiki/Fblockread (http://wiki.sa-mp.com/wiki/Fblockread)
Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 13 Janvier 2014, 21:39:21
J'aurais pensé à tous stockés dans un fichier oui, et à charger dans les tableaux comme j'ai expliqués, mais c'est quoi le principe de fblockread ?


edit : j'ai trouvé enfaite j'avais zappé la fin de la phrase dans ma lecture xD

Write data to a file in binary format, while ignoring line brakes and encoding.


c'est à dire que si j'enregistre tout ça, formater le fichier pour le rendre jolie à la lecture sera zappé ? xD
Titre: Re : [Demande Aide] Programmation IA
Posté par: Ssk le 13 Janvier 2014, 21:55:11
T'aura juste à écrire les données directement dans le fichier, par contre il faut que tu te crée une structure qui va te permettre de retrouver ton info rapidement dans le fichier sans avoir à tout charger dans des tableaux.


Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 13 Janvier 2014, 22:05:24
Je vais classer par secteur

par contre j'utilise des splits ou genre X=5154.55 etc.. ?
Titre: Re : [Demande Aide] Programmation IA
Posté par: Xartrick le 13 Janvier 2014, 22:26:55
La structure sert justement à éviter cela.

On sait exactement la taille des données en octets, donc on lit par groupe d'octets.
Par exemple, un
float correspond à 4 octets.
Les trois premiers groupes de 4 octets seront tes positions
X , Y et Z (par example).
Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 13 Janvier 2014, 23:04:45
daccord, donc je "split" juste par un espace et lit les groupe ? afin d'utiliser des fonctions à gogo ?
Titre: Re : [Demande Aide] Programmation IA
Posté par: Xartrick le 14 Janvier 2014, 21:48:39
Non, tu lis une taille fixe de données !
Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 15 Janvier 2014, 23:07:21
Salut,

désolé, j'ai pas eu trop le temps de tester et réfléchir à tout ça :p

je me suis informer un peu sur les fichiers tout ça, puis j'ai trouvé le moyen comme tu dis de lire donc avec fblockread, je rentre le nombre de cells là lire c'est à dire 8 ( 1 cells = 4 bits non ? ) puis je change l'index grâce à fseek

est-ce que tu pourrais me dire le format d'enregistrement enfin la forme du fichier stp ?


A+, Sam.
:cheers:
Titre: Re : [Demande Aide] Programmation IA
Posté par: Ssk le 15 Janvier 2014, 23:48:04
Salut, un cell correspond à 4 octets et non 4 bits ^^

Et pour la structure du fichier à toi de créer celle qui te convient le mieux.
Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 16 Janvier 2014, 08:13:54
Salut, ah merde, j'étais persuadé du contraire :p

D'accord, oui mais Xartrick a dit justement de pas utiliser de X= etc..

j'avais pensé à une structure genre :

<Sector 1>
          0.0 0.0 0.0
          0.0 0.0 0.0
</sector 1>

comme ça je lis ligne par ligne, et je sais quand est la fin, et le début, ainsi que le numéro du secteur
vous en pensez quoi ?
Titre: Re : [Demande Aide] Programmation IA
Posté par: Ssk le 16 Janvier 2014, 11:04:41
Tu peux utiliser une structure de ce genre dans ce cas.


Code: (pawn) [Sélectionner]
enum e_Sector
{
i_SectorId,
Float:f_X,
Float:f_Y,
Float:f_Z
};

new Sector[e_Sector];

Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 16 Janvier 2014, 15:11:38
Je parlais dans le fichier même :p
Titre: Re : [Demande Aide] Programmation IA
Posté par: Ssk le 16 Janvier 2014, 17:30:56
Oui, la structure sera la même dans le fichier ^^
Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 16 Janvier 2014, 17:59:55
C'est à dire :

Sector 1

     0.0
     0.0
     0.0

     0.0
     0.0
     0.0


etc..

Sector 2

(...)


c'est ça ? xD
Titre: Re : [Demande Aide] Programmation IA
Posté par: Ssk le 16 Janvier 2014, 19:10:54
Tu galère un peu :P, je t'ai fait ça pour que tu puisse comprendre :

[spoiler]
Code: (pawn) [Sélectionner]
#include <a_samp>



enum e_Sector
{
        i_SectorId,
        Float:f_X,
        Float:f_Y,
        Float:f_Z
};
 


GetSectorCount(a_File[])
{
new File:l_file;
new Sector[e_Sector];
new l_count;

l_file = fopen(a_File, io_read);
l_count = 0;

if(l_file != File:0)
{
l_count = flength(l_file) / (sizeof(Sector) * 4/*sizeof(cell)*/);
fclose(l_file);
}
return l_count;
}

CreateSector(a_File[], a_SectorId, Float:a_X, Float:a_Y, Float:a_Z)
{
new File:l_file;
new Sector[e_Sector];

l_file = fopen(a_File, io_append);

if(l_file != File:0)
{
Sector[i_SectorId] = a_SectorId;
Sector[f_X] = a_X;
Sector[f_Y] = a_Y;
Sector[f_Z] = a_Z;

fblockwrite(l_file, Sector, sizeof(Sector));
fclose(l_file);
}
}

GetSector(a_File[], a_SectorId, &Float:a_X, &Float:a_Y, &Float:a_Z)
{
new File:l_file;
new Sector[e_Sector];
new i;

l_file = fopen(a_File, io_read);

if(l_file != File:0)
{
i = GetSectorCount(a_File);

while(i > 0)
{
fblockread(l_file, Sector, sizeof(Sector));

if(Sector[i_SectorId] == a_SectorId)
{
a_X = Sector[f_X];
a_Y = Sector[f_Y];
a_Z = Sector[f_Z];
i = 0;
}
i --;
}

fblockwrite(l_file, Sector, sizeof(Sector));
fclose(l_file);
}
}



public OnFilterScriptInit()
{
new Float:l_X, Float:l_Y, Float:l_Z;
new l_count;

CreateSector("s_001.sec", 0, 10.0, 0.0, 0.0);
CreateSector("s_001.sec", 1, 10.0, 10.0, 0.0);
CreateSector("s_001.sec", 2, 10.0, 10.0, 10.0);
CreateSector("s_001.sec", 3, 10.0, 10.0, 15.0);
l_count = GetSectorCount("s_001.sec");
printf("Sector count %d", l_count);

l_count --;

while(l_count >= 0)
{
GetSector("s_001.sec", l_count, l_X, l_Y, l_Z);
printf("ID %d X : %f Y : %f Z : %f", l_count, l_X, l_Y, l_Z);
l_count--;
}

}
[/spoiler]

Alors par contre tu as du le comprendre, il n'y a pas de formatage donc si on l'ouvre avec un éditeur hexadécimal ça donne ça.

(http://i.imgur.com/Nuc4BfF.jpg) (http://i.imgur.com/Nuc4BfF.jpg)
Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 16 Janvier 2014, 19:37:46
Ouais je galere, parce que vous dites rien d'explicite xD


Enfaite, j'ai regarder ton code, ça n'a rien a voir par rapport à ceux que je pensais Oo xD

Chez moi ton code ne fonctionne pas, tu n'a pas du le faire sur pwn si ? Puisque rien qu'à ta manière de définir : new Sector[e_Sector]; sachant que ça me met un warning comme quoi il n'est pas utilisés, donc je l'ai mis en dessous de l'enum, ça compile et là bad entry point dans ma console : "invalid index parameters", donc ça vient de ton array,

new Sector[e_Sector]; il faudrait genre new Sector[10][e_Sector];

tu vois ce que je veux dire ? C'est pour ça aussi, que je partais dans un autre raisonnement, j'me suis battu a essayer plein de façon avec les arrays mais on est vite limité, puisqu'ils sont pas dynamique ( la raison pour laquelle je parlais de vecteur.)

:cheers:
Titre: Re : [Demande Aide] Programmation IA
Posté par: Ssk le 16 Janvier 2014, 23:27:06
Le code comme je l'ai donné fonctionne parfaitement, je l'ai testé ^^

Par contre je n'ai pas compris ce que tu voulais.

PS : Mon code n'est qu'un exemple de structure, tu peux en faire une meilleure.
Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 17 Janvier 2014, 10:35:17
(124) : warning 204: symbol is assigned a value that is never used: "Sector"

    GetSectorCount(a_File[])
    {
            new File:l_file;
            new Sector[e_Sector];  <-- ligne 124




Tu as des warnings toi ? et même avec le warning ça marche pas non plus.. :p
Titre: Re : [Demande Aide] Programmation IA
Posté par: Ssk le 17 Janvier 2014, 11:37:30
Pour eleminer le warning, mets cette fonction à la place.


Code: (pawn) [Sélectionner]
GetSectorCount(a_File[])
{
new File:l_file;
new Sector[e_Sector];
new l_count;

l_file = fopen(a_File, io_read);
l_count = 0;

Sector[i_SectorId] = 0;

if(l_file != File:0)
{
l_count = flength(l_file) / (sizeof(Sector) * 4/*sizeof(cell)*/);
fclose(l_file);
}
return l_count;
}


Et oui, ça marche très bien chez moi :

Sector count 4
ID 3 X : 10.000000 Y : 10.000000 Z : 15.000000
ID 2 X : 10.000000 Y : 10.000000 Z : 10.000000
ID 1 X : 10.000000 Y : 10.000000 Z : 0.000000
ID 0 X : 10.000000 Y : 0.000000 Z : 0.000000
  Filterscript 'sector.amx' loaded.

Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 17 Janvier 2014, 13:28:40
Voilà, là ca marche on est d'accord :D
Titre: Re : [Demande Aide] Programmation IA
Posté par: Ssk le 17 Janvier 2014, 13:38:32
Ça a toujours marché :P

Le warning était juste la pour dire que la variable sector n'était pas utilisée.
Titre: Re : [Demande Aide] Programmation IA
Posté par: chneubeul le 17 Janvier 2014, 18:14:45
Ouais, mais juste que là tu le met à 0 avant, alors que c'étais quand même utiliser parce que quand tu l'enlever pawno péter un plomb parce que c'étais pas définis xD
Bref, j'ai rien compris sur cet histoire là, j'vais voir la semaine prochaine pour faire quelque chose qui tient debout grâce à ton code, j'vais m'en inspirer.. j'commence à comprendre ton raisonnement, parce que je pensais pas du tout du tout ça, je comptais travailler sur un array, pour dijkstra après ça serait plus simple :p


Edit :  J'ai trouvé un peu de temps pour t'annoncer mon idée, enfaite, tu m'a donné une idée et les moyens de le faire, grâce à ton système et à ce que vous m'avez appris et ceux sur quoi je me suis renseigner (système de fichier etc.. :p ).

Enfaite je vais enregistrer toutes les données des positions où le npc pourra allez, puis lorsqu'il spawn, je vais chercher toutes les positions autour de lui, afin de les mettre dans un array, pour que ce soit plus pratique et plus rapide à travailler, parce que dijkstra sur un fichier, j'crois pas c'est une très bonne idée par rapport à l'optimisation du système :D

Voili Voilou, bref, au faite je n'ai pas dit, mais si vous connaissez des apprentis développeur qui souhaite apprendre, des petites astuces ou développer avec moi, je peux donner un coup, j'ai des tas d'idées et système à faire, afin de réaliser un petit projet pour s'amuser et apprendre :)