[Demande Aide] Programmation IA

[chneubeul]

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.
 

[Xartrick]

Pour moi, A* serait l'un des meilleurs choix: Algorithme A* - Wikipédia

[chneubeul]

Merci de ta réponse :

Lien Wikipédia vers Algo A*


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

Je connais cet algo, mais apparemment il fonctionne sur 2D

[Ssk]

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.

[chneubeul]

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.. ?

[Ssk]

Ça dépasse mes compétences je suis désolé, je n'ai jamais programmé d'IA je ne saurai te dire :/

[chneubeul]

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.

[chneubeul]

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.

[Ssk]

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

[chneubeul]

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

[Ssk]

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.

[chneubeul]

Je vais classer par secteur

par contre j'utilise des splits ou genre X=5154.55 etc.. ?

[Xartrick]

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).

[chneubeul]

daccord, donc je "split" juste par un espace et lit les groupe ? afin d'utiliser des fonctions à gogo ?

[Xartrick]

Non, tu lis une taille fixe de données !