 |
dev.gamez.lv
Latvian Game Developers Community
|
| View previous topic :: View next topic |
| Author |
Message |
nai
Joined: 20 Dec 2006
Posts: 48
|
 Posted: Sun Nov 25, 2007 12:24 am Post subject: |
|
Hehe. Es gan vairāk tēmēju uz "normālām" kartēm.
| Quote: | | Skreenu? Pastaastiisi kaads tev Open/Closed lista implementaacijas? Maybe vari piedaavaat standalone, gribu paskatiities cik aatri buus un mana, vaargaa xD procesora (P4 640 3.2Ghz) |
Ir binary heaps, kura elementi satur openlista elementa indeksu un F vērtību. Un tad ir pats open lists ar pārējo infu.
Tav itkā vajadzētu pat izpildīties ātrāk, jo PF man laižas uz vienas kores(2.13ghz).
Pielaboju atmiņas reservēšanu std::vectoram un no 500ms nokritās līdz 200ms(10,000reizēm).
Nav simpātisks test environments. |
|
| Back to top |
|
 |
Storm
Joined: 11 Apr 2006
Posts: 742
|
| Posted: Sun Nov 25, 2007 12:28 am Post subject: |
|
Kapeec 10k visu laiku xD Postee vnk kur ir 1 reizei :P Ar exe padaliisies?
Edit : Kas vains karteem :D es vinjas tuuliit centiisos dabuut cilveeku formaataa (visticamaak ka baitinju listaa xD) Un ieposteesu uz testu, ceru ka padaliisies ar excutabli pasreizeejo lai varu paskatiities kaa atskiraas performance uz mana datora :)
P.S Subarea count? Vai tu sadali veel seachu subareaaas un izmanto to konektivitaaes informaaciju?
Fails (lielaa karte - nav gan 512x512 bet 399x399 :P)
No saakuma, piemeeram no [0,0] uz [398,298] (masiivaa)
399*399 baiti 0 - siena 1 - briivs :
http://yy.lv/download.php?f=82669 |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Sun Nov 25, 2007 3:20 am Post subject: |
|
Bah nesaprotu tavu domu... vai nu arī es nesaprotu A*. Manā skatījumā A* nav paredzēts šāda veida labirintiem. Šādām "kartēm" vislabāk derēs vienkārša apstaigāšana dziļumā. Reku palaidu uz to larger.gif labirintu savu kādu laiku atpakaļ rakstīto dziļumā apstaigātāju:
Atrastais ceļš - http://maiss.02.lv/faili/bubu/larger_out.png
Apstaigātās rūtiņas - http://maiss.02.lv/faili/bubu/larger_out_full.png
| Code: | Time = 912.375 msec
Path length = 235956
Total visited cells = 8573546
Dead-ends = 428463 |
Nepilna sekunde!! Tas uz Core duo (bez 2) 1.8 Ghz (lai tu nepadomā, ka man te klāsteris ar meinfreimiem :)
Un pasaki tagad, vai tavs A* spēs kaut vai veselās 5-ās sekundēs atrast kaut vienu ceļu šajā labirintā? Īstenībā tur tikai precīzi viens arī ir - speciāli palaidu apstaigātāju plašumā (nevis dziļummā) un dabūju visu iekrāsotu sarkanu tajā full bildē. |
|
| Back to top |
|
|
Storm
Joined: 11 Apr 2006
Posts: 742
|
| Posted: Sun Nov 25, 2007 3:28 am Post subject: |
|
Tas nav lai paarbaudiitu cik aatri izstaigaa labririnu  taa ir vienkaarsa Open/Closed lista performance un visa A* performance pa absurdi sarezgiitu situaaciju. Un parada to loti labi  |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Sun Nov 25, 2007 3:49 am Post subject: |
|
Hm.. ok, ja tā uz to skatās, tad cita runa! Jāpadomā, diezgan interesanti palikās ;) Moš arī sanāks A* uztaisīt. Ļaunais Storm iebaroja tik interesantu tēmu ar visu lielo labirintu... :)
Btw, ja kādam vajag, tad rekur tas larger labirints vieglāk nolasāmā veidā nekā gif fails: http://maiss.02.lv/faili/bubu/larger.zip
Pirmie divi baiti failā - platums.
Nākamie divi baiti - augstums.
Abi divi ir 5769.
Pēc tam viss pārējais failā ir pats labirints. Platums skaitā rindas no augšas uz leju, no kreisās malas uz labo. Katrs baits = viena rūtiņu tādā pat formātā kā sākumā Storm deva. |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Sun Nov 25, 2007 4:51 pm Post subject: |
|
Tāks. Pirmajā piegājienā bez nekādas vēl optimizēšanas implementēju A*, kas uz to mazo, Storm sākumā doto labirintu, izmanto aptuveni tikpat daudz laika - 0.5msec, taču atrod īsāko ceļu - to pašu, ko nai.
Taču tas larger ir riktīgi ļauns, jo tajā ir tikai viens vienīgs ceļš uz izeju, tāpēc sanāk apstaigāt diezgan daudz. Pašlaik ir aptuveni 75 sekundes. Apstaigāts tiek 99% visu brīvo rūtiņu (16480736 no 16634913). Staigāju tikai pa 4-way-connected rūtiņām. Reku bilde: http://maiss.02.lv/faili/bubu/larger_out_a_star.png
Patlaban izmantoju Manhetenas distanci heiristikas funkcijai. Visāda veida konteineriem lietoju tikai STL - closed lists ir std::map ar nodēm. Open lists ir std::map ar nodēm un std::multimap sakārtotām nodēm pēc svara, kas glabā iteratorus uz pirmo std::map. Tātad visas darbības ar šiem listiem ir O(log N). Tagad laiks būtu ķerties klāt pie optimizēšanas :) |
|
| Back to top |
|
|
Storm
Joined: 11 Apr 2006
Posts: 742
|
| Posted: Sun Nov 25, 2007 7:02 pm Post subject: |
|
| bubu wrote: | Storm sākumā doto labirintu, izmanto aptuveni tikpat daudz laika - 0.5msec, taču atrod īsāko ceļu - to pašu, ko nai.
|
Man arii atrod iisaako celju, bet ne jau pie H=32, un relase buildaa(pirmais skriins ir debug + studija fonaa) + H prieks iisaakaa celja laiks ir 0.2msec :P
Lielo trako gabalu man atrod ~24 sekundees, bet tas ir neobjektiivs rezultaats, since man vinjam jaarokaas pa disku, jo nav rama XD, maybee panemam mazliet reaalaako, 399x399 variantu? :lol:
| Quote: |
Tav itkā vajadzētu pat izpildīties ātrāk, jo PF man laižas uz vienas kores(2.13ghz).
|
Hehe, mulkiibas, tavs procis ir apmeeram 2x aatraaks  http://www.tomshardware.com/us/ |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Sun Nov 25, 2007 7:16 pm Post subject: |
|
Vai tad jēga Debug konfigurācijā kautko mērīt? Es mērīju release konf, bet fonā webu browsēju, kad šis meklēja to ceļu.
Kas ir tas H=32 tev?
Un par to atmiņu - tev tas algoritms tik daudz izmanto, vai arī fiziski datorā maz atmiņas?
Paskatījos, cik man sanāca izmantot... ap 800MiB. heh, tas ar būs jāoptimizē. |
|
| Back to top |
|
|
Storm
Joined: 11 Apr 2006
Posts: 742
|
| Posted: Sun Nov 25, 2007 7:23 pm Post subject: |
|
yup, paslaik kompii tikai 512  Disks gan man aatrais bet nesaliidzinaami leenaaks par ramu shaa vai taa... Pirmdien aiziesu nopirksu ramu 2Gb (nemot veeraa kaadas cenas tagad :lol) un tad skatiisiemies to lielo  H ir heruistiks.
Kaada jeega optimizeet gandriiz 6k reiz 6k gridu atminjas laucinjaa? Tu tak nedomaa sho izmantot? XD Anyway, daudz ko tur saspiest nav
Last edited by Storm on Sun Nov 25, 2007 7:25 pm; edited 1 time in total |
|
| Back to top |
|
|
snake5
Indago dalībnieks
Joined: 27 Jun 2007
Posts: 2590
|
| Posted: Sun Nov 25, 2007 7:24 pm Post subject: |
|
doh..
jūs abi ar kompjiem sacenšaties vai ar astariem?
_________________
"There are two choices here: "looks good" and "realism"." -- Paul Nettle |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Sun Nov 25, 2007 7:44 pm Post subject: |
|
Reku uz to 399x399 sanāk šis te:
| Code: | Time = 61.4905 msec
Path length = 1111
Total free cells = 79999
Total visited cells = 23377 (29.2216%) |
Uzliku, lai staigā pa 8-way-connectivity. Lai būtu tāpat kā tev.
Tas pat ir arī īsākais ceļš! Papildus uzlaidu Dijkstru virsū - tas izdeva šo pašu ceļu 1111 garumā (ja vien neesmu kļūdījies tās implementācijā).
Kautkā nepatīk tas plašums sākumā... Jāskatās. Vēlāk būs noteikti vēl ātrāk :) Šis ir tikai, kā jau teicu, galīgi neoptimizēts variants - vienas stundas laikā uzrakstīju. Atmiņas patēriņu nespēju pagaidām nomērīt - programma nostrādā acumirklīgi, taskmangerī nepaspēju ieraudzīt izmantoto skailit ;) Vēlāk uzlikšu, lai programma skaita pati.
| Quote: | | Anyway, daudz ko tur saspiest nav |
Ir ir! Pašlaika atmiņu riju kā traks. Viens items Closed listā man aizņem vismaz 32 baitus, bet Open listā vismaz 68 baitus. Vismaz - jo īsti tagad no galvas nezinu STL papildus pielikto atmiņu katrai mapa/multimapa nodei (pieņēmu 3 pointerus, slinkums sizeof'us salikt :). Un to visu var vismaz uz pusi nomest nost, jo tur glabājas diezgan lieka informācija (tā bij vienkāršāk kodu uzrakstīt).
Es jau prasu - kas tas ir? Konstante vai?
Man heiristikas funkcija ir šāda (iepriekš teicu - Manhetenas attālums):
| Code: | class Heuristic
{
public:
Heuristic(const Position& goal) : _goal(goal)
{
}
uint operator () (const Position& node) const
{
return std::abs(_goal.x - node.x) + std::abs(_goal.y - node.y);
}
private:
Position _goal;
}; |
Last edited by bubu on Sun Nov 25, 2007 7:53 pm; edited 2 times in total |
|
| Back to top |
|
|
Storm
Joined: 11 Apr 2006
Posts: 742
|
| Posted: Sun Nov 25, 2007 7:46 pm Post subject: |
|
Cake.raw (399x399), Taadaa pasaa formaataa kaa bubu (width, height, data)
http://yy.lv/download.php?f=82884
H tiek piereiznaats pie heuristic f-jas iznaakuma, es paarmekleeju 8 virzienus un lietoju Euclidean variantu...
P.S lieto unsigned short nevis int ;)
Bubu - tev ir smuka paarmekleeto apgabalu apskatiisana, kaa izskatiisies no 0,0 liidz 0,398 ? |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Sun Nov 25, 2007 7:59 pm Post subject: |
|
| Quote: | | H tiek piereiznaats pie heuristic f-jas iznaakuma |
Hm. Sāk palikt ļoti interesanti. Rīktīgi labs performances ieguvums sanāca!
Paņēmu H=3, ieguvu daudz labāku rezultātu (uz citiem skaitļiem sanāk drusku sliktāk, bet arī H=2..5 dod aptuveni šo pašu variantu):
| Code: | Time = 29.6879 msec
Path length = 1111
Total free cells = 79999
Total visited cells = 11822 (14.7777%) |
Acīmredzami, ka mazāk jāstaigā.
| Quote: | | P.S lieto unsigned short nevis int ;) |
Nu jā, tagad to varu. Iepriekš nevarēju. Tai lielai kartei ceļa garums bija stipri virs 65535. |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Sun Nov 25, 2007 8:08 pm Post subject: |
|
| Storm wrote: | | Bubu - tev ir smuka paarmekleeto apgabalu apskatiisana, kaa izskatiisies no 0,0 liidz 0,398 ? |
Šoreiz sanāk labāk ar lielākiem H (>10).
H=20.
Ar atrada īsāko ceļu.
| Code: | Time = 56.4315 msec
Path length = 1525
Total free cells = 79999
Total visited cells = 22391 (27.9891%) |
Nezinu gan tikai, ko mans algoritms meklē tajā labajā apakšējā stūrī ejot uz augšu :)
Parādi tagad savus skaitļus, lai zinu uz ko man jātiecas ;) |
|
| Back to top |
|
|
Storm
Joined: 11 Apr 2006
Posts: 742
|
| Posted: Sun Nov 25, 2007 8:13 pm Post subject: |
|
Man shameejam variantam sanaak 11.0msec ar H = 40
Ja no 0,0 liidz 398,398 tad ar H = 4 sanaak 4.2msec :P
Edit : tas ir lietojot manhatanu un 4 virzienus, tiesi kaa tev xD |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
