Path Finding

Ice_2k · 09-11-2003, 00:47

Stie careva ceva despre asta? Nu ma intereseaza algoritmul de cautare in sine, pt ca acela stiu cum sa-l fac... ceea ce ma intereseaza este modul in care o anumita harta se transforma in acea matrice de 0 si 1? (in special cum integrez in ea si alte nave & stuff...). 10x.

c0mas · 14-11-2003, 18:13

As cam stii ceva, dar depinde foarte mult de tipul jocului si mai ales de tipul hartii.
Daca ai fi mai explicit, poate as putea sa-ti dau cateva idei.

Ice_2k · 14-11-2003, 23:15

Jocul este un amestec de strategie si shooter... daca ai jucat battlezone, stii despre ce vorbesc...
Daca nu... imagineaza-ti un starcraft in care tu esti acolo, jos intre unitati... dupa ce faci o nava te poti sui in ea si pleci la lupta...

c0mas · 16-11-2003, 01:23

Da, in cazul asta ai nevoie de pathfinding.

Dupa cum vad eu problema ar fi cateva solutii, doua dintre ele le voi prezenta mai jos (oricum in ambele solutii harta de pathfinding ar trebui sa fie strans legata de neginele de teren):

- una ar ca pentru fiecare nod de teren sa stii daca se poate trece pe acolo (adica 0 sau 1)
- a doua solutie ar fi sa faci un graf de zone. Definesti o zona (chiar si dreptunghiulara) ca un dreptunghi in care nu exista obstacole (adica se poate merge in orice punct al zonei din orice punct al zonei). In felul asta cauti drumul intre zone si in interioruk zonei mergi liber.

Ice_2k · 16-11-2003, 09:17

Uite la asta nu ma gandisem, sa definesc zone... cred ca nu e o ideea tocma' rea, ar scade foarte mult numarul de noduri... dar tot nu mi-ai zis cum ocolesc celelalte nave...

Zergul · 16-11-2003, 13:45

Consideri un cerc de coliziune (boundary circle) in jurul fiecarei nave. Ploblema acum se reduce la a misca cercuri printre cercuri. Fie A cercul care se misca si B restul cercurilor. Scalezi cercurile B incat sa aiba raza rB + rA (rA e raza cercului A) iar cercul A se reduce la unpunct. Acum aproximezi cercurile B prin poligoane si problema se reduce la plimbatul unui punct printre poligoane ceea ce e deja mult mai simplu decat problema de la care ai plecat.

Il poti face cu un algoritm modificat de cost minim in graf (studiaza problema pentru optimizari).

Numai bine!
Cod.

Ice_2k · 16-11-2003, 15:56

Ok, totu clar pana aici, dar acum apare adevarata problema... acele nave se pot misca.. ce fac, calculez drumul de fiecare data cand se misca una din nave, sa vad daca ma incurca?

c0mas · 18-11-2003, 03:32

Hehehehehe, unitatile mobile sunt adevarata problema.
Eu am lucrat acum acateva luni la o strategie si am facut ceva de genul urmator:

- unitatile mobile oprite defineau anumite zone blocate de care tineam cont la cautare;
- unitatile in miscare verificau sa nu dea peste o alta unitate in miscare (cele statice erau eliminate la cautare)
- in caz ca era riscul sa treaca peste o alta unitate mobile, cea mai lenta (sau aici se poate face un set intreg de reguli) ii ceda prioritatea celeilalte dupa care isi continua drumul (adica cand se elibera trecerea).

Parea sa mearga destul de bine, dar era 2D s-ar putea ca la tine sa faci ceva 3D

Ice_2k · 18-11-2003, 13:24

hmm... de curiozitate... ce face motoru tau de cautare in urmatorul caz: doua unitati mobile se intalnesc intr-un pct... aia mai lenta se opreste, asteptand sa treaca cealalta, iar aia mai rapida se opreste exact in fata celeilalte? (aia lenta mai pleaca de pe loc sau ramane acolo?)

P.S. Cred ca motorul de cautare merge foarte bine pe 2D, kiar si pt un joc 3D (n-am de gand sa fac ceva de genu daca e o stramtoare blocata sa zboare peste, asa ca e OK)...

Thanks

Arise · 19-11-2003, 09:20

Poti sa implementezi si o tehnica mai isteatza... cand o nava vrea sa se deplaseze, celelalte ar trebui sa apeleze la o functie, sa ii zicem "bun_simt" si sa ii faca loc.

Zergul · 19-11-2003, 10:03

Ca idee buna de design iti recomand sa ai clase de unitati cu aceeasi viteza (astfel anumite "flaws" din algoritm nu se vad in joc).

...sau se vad mai putin.

Notez unitatea mai rapida cu R si unitatea cu viteza mai mica cu r.

La pathfinding nu iei in considerare ca obstacole unitatile care se misca (dinamice).

Faci un update "virtual" (adica nu updatezi in mod real pozitiile) la pozitiile unitatilor pentru cadrul curent (ai putea sa updatezi si dupa viteza lor in mod ordonat iti recomand ca imbunatatire dupa ce merge varianta "basic") si vezi daca:

(a) R ciocneste r dar r nu ciocneste R atunci R asteapta un timp (cred ca o valoare buna e 0.3 - 0.4 sec) dupa care incearca sa isi continue drumul. Daca incercarea de update esueaza de 2-3 ori la rand faci pathfinding din nou.

(b) R ciocneste r si r ciocneste R atunci r intra idle ca mai sus. R face pathfinding iar cu r statica.

(c) R nu ciocneste r dar r ciocneste R - se poate intampla cazul asta? - r idle ca mai sus si apoi retry.

Zergul · 19-11-2003, 10:06

Cum spuneai tu se poate intampla ca intre timp o unitate sa fi ajuns la locul unde dorea sa ajunga si e "statica". Daca te ciocnesti cu ea faci pathfinding din nou.

Algoritmul are si neajunsuri dar incearca pana aici si vezi unde sunt cele mai mari probleme.

Keep up the good work!

Cod.

Ice_2k · 19-11-2003, 10:11

Poate-s io mai greu de cap, nu stiu... da' cum vine asta " R ciocneste r dar r nu ciocneste R" ca nu m-am prins...

Arise: ma indoiesc tare de tot ca ar merge kestia aia... gandeste ca "a-i face loc" inseamna ca aceasta nava insasi sa se mute... ea vrand sa se mute, alte nave ar trebui sa-i faca si ei loc si tot asa, nu? nu cred c-ar merge... intr-o ingramadeala de nave a-i putea ajunge in situatia in care fiecare nava incearca sa-i faca loc alteia.. sa vezi ce circ iese acolo...

Zergul · 19-11-2003, 10:23

R si r merg in aceeasi directie, R este in "urma" lui r. R o prinde din urma pe r.

Imi cer scuze ca nu am definit "ciocneste". Pentru ca R il intersecteaza pe r dar si r pe R (e normal). Insa pentru a stii daca se "ciocnesc" ia in considerare pozitiile curente si pozitiile update "virtual" plus vitezele unitatilor.

c0mas · 19-11-2003, 16:02

In algoritmul meu, cand unitatea mai lenta hotara sa astepte, seta un timp de asteptare. Cand timpul a trecut incerca sa continue drumul. Daca la sfarsitul timpului locul devenea blocat de o unitate statica (unitatea rapida care s-a oprit), recalcula drumul (cu algoritmul de cautare).

Arise · 20-11-2003, 09:54

Ce am zis eu se poate aplica cu succes in aplicatii in care numarul de entitati deplasabile este mai mic.
Oricum, ca fapt divers... nu prea are legatura cu intrebarea ta... poti incerca sa implementezi notiunea de turma

Ca in cazul particulelor. Exemplu: Pasarile merg in V, albinele stau roi, pestii sunt in bancuri etc... Asta inseamna ca in grupul de entitati fiecare individ sa aiba un spatiu personal, sa pastreze o anumita distanta intre el si vecini. Distanta trebuie sa fie intre anumite limite. Daca a scazut, trebuie initiate anumite proceduri de degajare, iar daca distanta s-a marit trebuie sa fie apelata procedura de apropiere.

Astfel, in clipa in care o unitate mai mare (A) vrea sa isi fac loc, trimite mesajul de eliberare a drumului, unitatea mica (b1) primeste mesajul si intra in spatiul personal al altei unitati mici (b2), avand ca restrictie revenirea in pozitia initiala pana cand unitatea mare(A) nu a trecut. Ca raspuns al incalcarii spatiului personal, unitatea mica (b2) se va deplasa usor in spatiul personal al altei nave mici...
In final va iesi o chestie de forma unui val care se retrage...

Exista si posibilitatea ca o nava sa o impinga pe cealalta... si isi face astfel loc.

Asta este interesant de implementat atunci cand ai nishte soldatei amarati si un tanc trebuie sa isi faca loc. Soldatei se imbulzesc pentru a face loc tancurilor.