Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Pascal - Pseudo-IA
Forum - Pascal - Pseudo-IA

Avatar
()
Newbie


Messaggi:
Iscritto:

Segnala al moderatore
Postato alle 1:00
Giovedì, 01/01/1970
Ciao a tutti. Volevo realizzare una versione di pacman creata da me. Nel mentra della progettazione però mi è sorto un grande problema. In pacman i fantasmini inseguono pacman per mangiarlo/ucciderlo..beh, per inseguirlo devono "sapere" il percorso da fare per raggiungerlo..che algoritmo potrei studiare e poi cercare di implementare per poter calcolare tutto il percorso da compiere tra un punto A e un punto B?

ne ho implementato 1 nello snake che ho creato per far muovere da solo il serpentino però come pensavo funziona naturalmente solo se non ci sono barriere..appena se ne mette una naturalmente il serpente si va a schiantare..avrei bisogno di un modo per far aggirare l'ostacolo..e naturalmente potrei riutilizzare tale procedimento per crare pacman..

grazie a chi mi aiutera :D

Ultima modifica effettuata da il 27/03/2010 alle 17:13
PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1792
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 19:57
Sabato, 27/03/2010
un algoritmo largamente utilizzato nei giochi, per risolvere il cosiddetto problema del "path finding", è A* (si pronuncia A-star).

Si tratta di una variante dell'algoritmo Dijkstra per i grafi.
In questo caso i nodi del grafo sono rappresentati dalle caselle della mappa, e un arco congiunge due nodi se queste caselle sono adiacenti e sono comunicanti. Se due caselle sono separate da un muro, non esiste l'arco che le congiunge.

In letteratura troverai N-mila esempi ed implementazioni in tutti i linguaggi conosciuti, quindi adesso che conosci il nome dell'algoritmo, scatena il google che c'è in te! Don't be evil! ;)

PM Quote
Avatar
()
Newbie


Messaggi:
Iscritto:

Segnala al moderatore
Postato alle 0:31
Martedì, 11/05/2010
Posto un sorgente. Come al solito provo tutto su snake.

Codice sorgente - presumibilmente Delphi

  1. program snake_graphic;
  2.  
  3. uses wingraph,wincrt,sysutils;
  4.  
  5. type
  6. coordinate=record
  7. posizione:integer;
  8. distanza:integer;
  9. end;
  10.  
  11. var
  12.         m_old,n_old,n,m:integer;
  13.         v:longint;
  14.         o_x,o_y,velocita:integer;
  15.         x,y,punteggio:integer;
  16.         sg,mg:integer;  (*X inizalizzare la grafica*)
  17.         i,k,x_premio,y_premio,scelta_num:word;
  18.         exit,scelta,reticolo:boolean;
  19.         coda:array[0..100] of integer;
  20.         output,old_output:string[10];
  21.         scelta_due:string[2];
  22.         dimensione_campo:integer;
  23.         nome_giocatore:string;
  24.         angolo_secondi,angolo_minuti,angolo_ore:real;
  25.         h,minutes:integer;
  26.         s:real;
  27.         orario:string[8];
  28.         s_s,h_s,s_m:string[2];
  29.         secondi,minuti,ore,cento_secondi:word;
  30.         x_termine,y_termine:integer;
  31.         x_origine,y_origine:integer;
  32.         sconfitta:boolean;
  33.  
  34.  
  35. campo:array[1..50,1..50] of boolean;
  36. adiacenti_usabili:array[1..4] of coordinate;
  37. scelti:integer;
  38.  
  39.  
  40. {---------------------------------------------------CRONOMETRO---------------------------------------------------}
  41. procedure disegna_lancetta(angolo_in_gradi:real; colore:string);
  42. begin
  43. y_termine:=y_origine+trunc(sin(angolo_in_gradi*pi/180)*100);
  44. x_termine:=x_origine+trunc(cos(angolo_in_gradi*pi/180)*100);
  45. if colore='orange' then setcolor(orange)
  46. else if colore='red' then setcolor(red)
  47. else if colore='blue' then setcolor(blue)
  48.         else writeln('ERRORE COLORE!');
  49. line(x_origine,y_origine,x_termine,y_termine);
  50. end;
  51.  
  52. procedure cancella_lancetta(angolo_in_gradi:real);
  53. begin
  54. setcolor(black);
  55. y_termine:=y_origine+trunc(sin(angolo_in_gradi*pi/180)*100);
  56. x_termine:=x_origine+trunc(cos(angolo_in_gradi*pi/180)*100);
  57. line(x_origine,y_origine,x_termine,y_termine);
  58. end;
  59.  
  60. PROCEDURE CRONOMETRO(waiting:INTEGER);
  61. begin
  62. angolo_secondi:=angolo_secondi+6*waiting/1000;
  63. angolo_minuti:=angolo_minuti+0.1*waiting/1000;
  64. angolo_ore:=angolo_ore+0.008333333*waiting/1000;
  65. disegna_lancetta(angolo_secondi,'orange');
  66. disegna_lancetta(angolo_minuti,'blue');
  67. disegna_lancetta(angolo_ore,'red');
  68. s:=s+waiting/1000;
  69. delay(waiting);
  70. cancella_lancetta(angolo_secondi);
  71. cancella_lancetta(angolo_minuti);
  72. cancella_lancetta(angolo_ore);
  73. end;
  74. {-------------------------------------------CRONOMETRO-------------------------------------------}
  75.  
  76. {-------------------------------------------GESTIONE_CELLE-------------------------------------------}
  77. procedure accendi_cursore(ascissa,ordinata:integer; colore:string);
  78. begin
  79. if colore='red' then setcolor(red);
  80. if colore='yellow' then setcolor(yellow);
  81. rectangle(ascissa*8+1,ordinata*8+1,ascissa*8+7,ordinata*8+7);
  82. rectangle(ascissa*8+2,ordinata*8+2,ascissa*8+6,ordinata*8+6);
  83. rectangle(ascissa*8+3,ordinata*8+3,ascissa*8+5,ordinata*8+5);
  84. putpixel(ascissa*8+4,ordinata*8+4,red);
  85. setcolor(black);
  86. end;
  87.  
  88. procedure spegni_cursore(ascissa,ordinata:integer);
  89. begin
  90. setcolor(black);
  91. rectangle(ascissa*8+1,ordinata*8+1,ascissa*8+7,ordinata*8+7);
  92. rectangle(ascissa*8+2,ordinata*8+2,ascissa*8+6,ordinata*8+6);
  93. rectangle(ascissa*8+3,ordinata*8+3,ascissa*8+5,ordinata*8+5);
  94. putpixel(ascissa*8+4,ordinata*8+4,black);
  95. end;
  96. {-------------------------------------------GESTIONE_CELLE-------------------------------------------}
  97.  
  98. procedure riordina_vettore_coda;
  99. var w:integer;
  100. begin
  101. if punteggio>0 then for w:=0 to punteggio-1 do coda[w]:=coda[w+1];
  102. coda[punteggio]:=(x*100)+y;
  103. end;
  104.  
  105. procedure cogli_input;
  106. var
  107.     tasto:char;
  108. begin
  109. (*Se keypressed è vero allora raccoglie l'input modificando il vettore spostamento*)
  110. if keypressed then
  111. begin
  112. m_old:=m;
  113. n_old:=n;
  114. tasto:=readkey;
  115. if tasto=#72 then
  116.     begin
  117.     n:=-1;
  118.     m:=0;
  119.     end;
  120. if tasto=#80 then
  121.     begin
  122.     n:=1;
  123.     m:=0;
  124.     end;
  125. if tasto=#77 then
  126.     begin
  127.     m:=1;
  128.     n:=0;
  129.     end;
  130. if tasto=#75 then
  131.     begin
  132.     n:=0;
  133.     m:=-1;
  134.     end;
  135. if tasto=#27 then exit:=true;
  136. end;
  137.  
  138. if (m=m_old*(-1)) then m:=m_old;
  139. if (n=n_old*(-1)) then n:=n_old;
  140. n_old:=n;
  141. m_old:=m;
  142. end;
  143. (*################################################################################*)
  144. {procedure gioca_pc;
  145. begin
  146. m_old:=m;
  147. n_old:=n;
  148. if (x_premio=x) and (y_premio<>y) then
  149.         begin
  150.         n:=(y_premio-y) div (abs(y_premio-y));
  151.         m:=0;
  152.         end
  153. else if (y_premio=y) and (x_premio<>x) then
  154.         begin
  155.         m:=(x_premio-x) div (abs(x_premio-x));
  156.         n:=0;
  157.         end
  158. else if (x_premio<>x) and (y_premio<>y) then
  159.         begin
  160.         if abs(x_premio-x) > (y_premio-y) then
  161.                 begin
  162.                 m:=(x_premio-x) div (abs(x_premio-x));
  163.                 n:=0;
  164.                 end;
  165.         if abs(y_premio-y) > (y_premio-y) then
  166.                 begin
  167.                 n:=(y_premio-y) div (abs(y_premio-y));
  168.                 m:=0;
  169.                 end;
  170.  
  171.         end;
  172. if (m=m_old*(-1)) then m:=m_old;
  173. if (n=n_old*(-1)) then n:=n_old;
  174. end;}
  175.  
  176. PROCEDURE GIOCA_PC;
  177. var w:integer;
  178. iterazione:integer;
  179. fine:boolean;
  180. buffer:coordinate;
  181. nuova_ascissa,nuova_ordinata:integer;
  182. BEGIN
  183. iterazione:=0;
  184. w:=0;
  185. fine:=false;
  186.  
  187. if campo[x+1,y]=false then
  188.         begin
  189.         iterazione:=iterazione+1;
  190.         adiacenti_usabili[iterazione+1].posizione:=(x+1)*100+y;
  191.         adiacenti_usabili[iterazione+1].distanza:=abs(x-x_premio+1)+abs(y-y_premio);
  192.         end
  193. else if campo[x-1,y]=false then
  194.         begin
  195.         iterazione:=iterazione+1;
  196.         adiacenti_usabili[iterazione+1].posizione:=(x-1)*100+y;
  197.         adiacenti_usabili[iterazione+1].distanza:=abs(x-x_premio-1)+abs(y-y_premio);
  198.         end
  199. else if campo[x,y+1]=false then
  200.         begin
  201.         iterazione:=iterazione+1;
  202.         adiacenti_usabili[iterazione+1].posizione:=(x*100)+(y+1);
  203.         adiacenti_usabili[iterazione+1].distanza:=(x-x_premio)+(y+1-y_premio);
  204.         end
  205. else if campo[x,y-1]=false then
  206.         begin
  207.         iterazione:=iterazione+1;
  208.         adiacenti_usabili[iterazione+1].posizione:=(x*100)+(y-1);
  209.         adiacenti_usabili[iterazione+1].distanza:=(x-x_premio)+(y-1-y_premio);
  210.         end
  211. else sconfitta:=true;
  212.  
  213. if iterazione=1 then scelti:=adiacenti_usabili[1].posizione;
  214.  
  215. if iterazione>1 then repeat
  216.         begin
  217.         if w=3 then w:=0;
  218.         w:=w+1;
  219.         if adiacenti_usabili[w].distanza>adiacenti_usabili[w+1].distanza then
  220.                                                                                 begin
  221.                                                                                 buffer.distanza:=adiacenti_usabili[w+1].distanza;
  222.                                                                                 adiacenti_usabili[w+1].distanza:=adiacenti_usabili[w].distanza;
  223.                                                                                 adiacenti_usabili[w].distanza:=buffer.distanza;
  224.                                                                                 end;
  225.         fine:=true;
  226.  
  227. if iterazione=3 then if (adiacenti_usabili[1].distanza>adiacenti_usabili[2].distanza) or (adiacenti_usabili[1].distanza>adiacenti_usabili[3].distanza) then fine:=false;
  228.  
  229. if iterazione=4 then if (adiacenti_usabili[1].distanza>adiacenti_usabili[2].distanza) or (adiacenti_usabili[1].distanza>adiacenti_usabili[3].distanza) or (adiacenti_usabili[1].distanza>adiacenti_usabili[4].distanza) then fine:=false;
  230.        
  231.         if fine then scelti:=adiacenti_usabili[1].posizione;
  232.         end;
  233. until fine;
  234.  
  235. nuova_ordinata:=scelti mod 100;
  236. nuova_ascissa:=(scelti - nuova_ordinata) div 100;
  237.  
  238. if nuova_ordinata=y then
  239.                         begin
  240.                         m:=0;
  241.                         n:=nuova_ordinata-y
  242.  
  243.                         end;
  244.  
  245. if nuova_ascissa=x then
  246.                         begin
  247.                                 n:=0;
  248.                         m:=nuova_ascissa-x
  249.  
  250.  
  251.                         end;
  252.  
  253. writeln('N: ',n);
  254. writeln('M: ',m);
  255. END;
  256.  
  257. (*##############################################################################*)
  258. procedure genera_cibo;
  259. var found:boolean;
  260. begin
  261. if v<>0 then spegni_cursore(x_premio,y_premio);
  262. if (x=x_premio) and (y=y_premio) then accendi_cursore(x_premio,y_premio,'red');
  263. found:=false;
  264. repeat
  265. delay(5);
  266. randomize;
  267. x_premio:=trunc((random()*dimensione_campo)+1);
  268. delay(5);
  269. randomize;
  270. y_premio:=trunc((random()*dimensione_campo)+1);
  271. if (y<>y_premio) and (x<>x_premio) then found:=true;
  272. until found;
  273. accendi_cursore(x_premio,y_premio,'yellow');
  274. end;
  275.  
  276. procedure output_dati(ascissa,ordinata:integer);
  277. begin
  278.  
  279. SetTextStyle(TimesNewRomanFont,0,3);
  280. setcolor(black);
  281. outtextxy(ascissa,ordinata+60,orario);
  282. outtextxy(ascissa,ordinata,'Punti: '+(inttostr(punteggio-1)));
  283. setcolor(yellow);
  284. outtextxy(ascissa,ordinata+30,'Player: '+nome_giocatore);
  285. setcolor(white);
  286. outtextxy(ascissa,ordinata,'Punti: '+(inttostr(punteggio)));
  287.  
  288. setcolor(orange);
  289. if trunc(s)<10 then s_s:='0'+inttostr(trunc(s))
  290.         else s_s:=inttostr(trunc(s));
  291. if minutes<10 then s_m:='0'+inttostr(minutes)
  292.         else s_m:=inttostr(minutes);
  293. if h<10 then h_s:='0'+inttostr(h)
  294.         else h_s:=inttostr(h);
  295. orario:=h_s+':'+s_m+':'+s_s;
  296. outtextxy(ascissa,ordinata+60,orario);
  297. if trunc(s)=60 then
  298.         begin
  299.         s:=0;
  300.         minutes:=minutes+1;
  301.         end;
  302. if minutes=60 then
  303.         begin
  304.         minutes:=0;
  305.         h:=h+1;
  306.         end;
  307. if h=12 then h:=0;
  308. end;
  309.  
  310. begin
  311. i:=0;
  312. k:=0;
  313. (*Inizializzazione *)
  314. for i:=1 to 50 do for k:=1 to 50 do campo[i,k]:=false;
  315. i:=0;
  316. k:=0;
  317. y:=25;
  318. x:=25;
  319. m:=1;
  320. n:=0;
  321. v:=0;
  322. punteggio:=1;
  323. sconfitta:=false;
  324. coda[0]:=(x*100)+y;
  325. angolo_secondi:=270;
  326. angolo_minuti:=270;
  327. angolo_ore:=270;
  328. s:=0;
  329. minutes:=0;
  330. h:=0;
  331. x_origine:=650;
  332. y_origine:=350;
  333. orario:='00:00:01';
  334. dimensione_campo:=50;
  335.  
  336. repeat
  337.         writeln;
  338.         writeln('Chi vuoi che giochi? ');
  339.         writeln;
  340.         writeln('1- Io');
  341.         writeln('2- CPU');
  342.         WRITELN;
  343.         readln(scelta_num);
  344.         writeln;
  345.         if scelta_num=1 then scelta:=false else scelta:=true;
  346. until (scelta_num=1) or (scelta_num=2);
  347. v:=0;
  348.  
  349. if scelta_num=1 then
  350. begin
  351.         writeln;
  352.         write('Nome giocatore: '); readln(nome_giocatore);
  353.         writeln;
  354.         repeat
  355.         writeln;
  356.         write('Dimensione del campo: (tra 25 e 63) '); readln(dimensione_campo);
  357.         writeln;
  358. until (dimensione_campo<=63) and (dimensione_campo>=25);
  359.  
  360. end
  361.                 else nome_giocatore:='CPU';
  362.  
  363. {C:\FPC\2.4.0\bin\i386-win32\ppc386.exe snake_alfa.pas}
  364.  
  365. repeat
  366.         begin
  367.         writeln;
  368.         write('Velocita''? (consigliato tra 150 e 70) '); readln(velocita);
  369.         writeln
  370.         end;
  371. until (velocita>50) and (velocita<200);
  372.  
  373. repeat
  374.         writeln;
  375.         write('Vuoi che venga usato il reticolo? (s/n) '); readln(scelta_due);
  376.         if (scelta_due='si') or (scelta_due='s') then reticolo:=true else reticolo:=false;
  377.         writeln;
  378. until (scelta_due='si') or (scelta_due='s') or (scelta_due='no') or (scelta_due='n');
  379.  
  380.  
  381. (*Inizializzazione della modalità grafica*)
  382. sg:=detect;
  383. initgraph(sg,mg,'');
  384. genera_cibo;
  385. (*Fine dell'inizializzazione grafica*)
  386.  
  387. (*Fine inizializzazione*)
  388.  
  389.  
  390.  
  391. (*Disegno lo scheletro del campo e del cronometro*)
  392. rectangle(0,0,dimensione_campo*8+8,dimensione_campo*8+8);
  393.  
  394. if reticolo then while i<>dimensione_campo*8+8 do
  395.         begin
  396.         delay(250);
  397.         i:=i+8;
  398.         setcolor(white);
  399.         line(i,0,i,dimensione_campo*8+8);
  400.         line(0,i,dimensione_campo*8+8,i);
  401.         end;
  402.  
  403.  
  404. circle(x_origine,y_origine,102);
  405. (*Fine disegno dello scheletro e del cronometro*)
  406.  
  407.  
  408. repeat
  409.  
  410. {Contatore spostamento}
  411. v:=v+1;
  412. i:=0;   {reinizializzazione contatore sconfitta}
  413. {Contatore spostamento}
  414.  
  415. {Spegnimento ultima cella serpente}
  416. o_y:=coda[0] mod 100;
  417. o_x:=((coda[0] - coda[0] mod 100) div 100);
  418. spegni_cursore(o_x,o_y);
  419. {Spegnimento ultima cella serpente}
  420.  
  421. {Evita il movimento al contrario}
  422. if scelta=false then cogli_input else gioca_pc;
  423. {Evita il movimento al contrario}
  424.  
  425.  
  426. cronometro(velocita);
  427. x:=x+m;
  428. y:=y+n;
  429. (*Uscita dal quadrato*)
  430. if x=dimensione_campo+1 then x:=1;
  431. if x=0 then x:=dimensione_campo;
  432. if y=dimensione_campo+1 then y:=1;
  433. if y=0 then y:=dimensione_campo;
  434. (*Fine*)
  435. riordina_vettore_coda;
  436. accendi_cursore(x,y,'red');
  437.  
  438.  
  439. if (x=x_premio) and (y=y_premio) then
  440.         begin
  441.         punteggio:=punteggio+1;
  442.         genera_cibo;
  443.         end;
  444.  
  445. {if punteggio>4 then for i:=1 to punteggio-2 do if coda[punteggio]=x*100+y then sconfitta:=true;}
  446.  
  447. if v mod 50 = 0 then genera_cibo;
  448.  
  449.  
  450. if scelta=false then cogli_input;
  451.  
  452.  
  453. SetTextStyle(TimesNewRomanFont,0,5);
  454. output_dati(600,0);
  455.  
  456.  
  457. until exit or (punteggio=100) or (v=5000) or sconfitta;
  458.  
  459. cleardevice;
  460. setcolor(white);
  461. if sconfitta then outtextxy(280,150,'Alla prossima compare ;)');
  462. if exit then outtextxy(280,150,'Alla prossima compare ;)');
  463. if punteggio=100 then outtextxy(280,150,'Buona partita :D');
  464. if v=5000 then outtextxy(280,150,'La velocità non è il tuo forte xD');
  465. delay(3000);
  466. closegraph;     (*Chiusura della modalità grafica*)
  467.  
  468. end.



Non funziona...almeno non riesco a far giocare il pc con la procedura che dovrebbe evitare anche i muri.

Ho pensato di "immaginare" il campo da gioco come una matrice bidimensionale di booleans
in cui true vale casella chiusa e false casella aperta. Sono consentiti solo movimenti ortogonali ai due assi x e y. Il computer guarda le quattro caselle adiacenti all'attuale posizione della testa del serpente, vengono aggiunte a adiacenti_usabili le coordinate delle caselle libere e la stima euristica della loro distanza dal target. Viene ordinato l'array adiacenti_usabili in modo crescente per il parametro distanza viene scelto adiacenti_usabili[1] e adiacenti_usabili[1] infine per mantenere la compatibilità con il resto del gioco ho fatto in modo tale che alla fine mi venissero restituite le due componenti del vettore spostamento con m componente in x e n componente in y. non trovo dov'è il problema con questa procedura.

Ultima modifica effettuata da Phi il 11/05/2010 alle 18:15
PM Quote