 |
dev.gamez.lv
Latvian Game Developers Community
|
| View previous topic :: View next topic |
| Author |
Message |
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
 Posted: Sun Nov 25, 2007 8:21 pm Post subject: |
|
| Storm wrote: | | Edit : tas ir lietojot manhatanu un 4 virzienus, tiesi kaa tev xD |
Man vairs nav 4-virzieni. Tur augstāk pamainīju, lai būtu ar 8 - kā tev :)
Paskaties uzmanīgāk uz manu karti - cik smieklīgi šis staigā pa taisnu koridoru:
| Code: | x x x
xxxxoxoxxxxx
oooo o o ooo
xxxxxxxxoxxx
x x |
x - siena, o - ceļš.
Neiet pa taisno, bet zigzagā! Biju uzlicis, lai vispirms aplūko rūtiņas pa diagonāli, un tikai pēc tam taisnās, lai var uz pagriezieniem ap stūriem ietaupīt.
Iedomājies, kā 3d spēlē tas izskatīsies - AI skraidīs kā apdzēries :)
Vajadzētu laist uz atrasto ceļu - postprocessingu, lai iztaisno zigzag ceļus. Vai arī otrādi - meklēt normāli vispirms horizontāli un vertikāli, un pēc tam pa diagonālēm, un eigās postprocessingā pagriezienus ap stūriem aizstāt ar vienu soli, nevis diviem.
Vai arī normālāk būtu nestaigāt pa diagonālēm un lietot tikai 4-way connectivity.
Un varēji jau arī nemainīt uz tādu pašu funkciju kā man - ar to jau arī A* atšķirās, cik atbilsošu un optimāla heiristikas funkciju tiks izvēlēta.
Cik tev sanāk liekas rūtiņas apmeklēt? Tas jau laikam ir otrs interesantākais rādītājs (aiz darbības laika), kas pie tam raksturo implementētā A* algoritma kvalitāti. |
|
| Back to top |
|
 |
Storm
Joined: 11 Apr 2006
Posts: 742
|
| Posted: Sun Nov 25, 2007 8:43 pm Post subject: |
|
Part to apdzeerusos staigaasanu... jaalieto mazaaks H
Man ir uztaisiits arii taa, lai vins stuurus appiet neizmantojot diognaales, bet kur ir iespeejams taisnaaks celjs pa diognaali - izmantojot diognaali.
Gaidu nai rezultaatus un exe, ja nav zeel xD |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Mon Nov 26, 2007 12:46 am Post subject: |
|
Ok, noskatījos filmu, un tad uz stundiņu pieķēros optimizēšana. Progress sanāca labs :)
Vispirms uzliktu tikai 4-way staigāšanu, nu i nafig ar tām diagonālēm. Uzliku visur arī, lai H=32.
larger labirints (bilde samazināta ~10x):
Labs progress! Iepriekš praktiski viss (99%) bija sarkans. Izskatās arī, ka tā šaubīšanās iepriekš par 5 sekundēm ir lieka. Domāju, ka mierīgi var to laiku dabūt pat zem kādas pusotras sekundes.
| Code: | Time = 1884.28 msec // wow, gandrīz 40x ātrāks! :)
Path length = 235947
Total free cells = 16634913
Total visited cells = 8148346 (48.9834%)
Used memory = 260024 KiB |
Storm mazais labirints:
Jokaini šķiet, ka noņemot staigāšanu pa diagonāli tik ļoti izmainījās tā apakšējā daļa.. Jāpaskatās sīkāk kāpēc.
| Code: | Time = 4.27708 msec
Path length = 1557
Total free cells = 79999
Total visited cells = 17978 (22.4728%)
Used memory = 1245 KiB |
Cita izeja:
Palika drusku labāk!
| Code: | Time = 4.97326 msec
Path length = 2123
Total free cells = 79999
Total visited cells = 21537 (26.9216%)
Used memory = 1245 KiB |
No pēdējiem diviem secināju, ka algoritma izmantotais laiks visvairāk ietekmējas no tiem "total visited cells", tb jo vairāk lieku rūtiņu apstaigās, jo sliktāk. Tagad visas operācijas ir O(1) izņemot pielikšanu un izņemšanu Open listā - tās ir O(log N). Vēl ir padomā lieta kas arī izņemšanu no Open lista padarīs par O(1), bet to ne tagad. Kā par brīnumu optimizētais kods sanāca vienkāršāks un ir pat vieglāk lasāms. Arī garumā tas sarāvās - iepriekšējo ~600 rindiņu vietā tagad ir ~400. Šovakaram ar to arī pietiks. |
|
| Back to top |
|
|
Storm
Joined: 11 Apr 2006
Posts: 742
|
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Thu Jan 03, 2008 1:56 am Post subject: |
|
Hm.. interesanti. Tad, kad tu konstatē, ka jaunā node jau atrodas Open nožu sarakstā un ir lētāka nekā tur esošā node, tad tu vienalga to iebāz tajā Open sarakstā ar lētāko cenu. Iznāk, ka tā node tiks apskatīta divas, vai pat vairāk reizes, ja tā atrodas karsta krustojuma centrā. Taču tas ietaupīs mešanu ārā no open saraksta, bet arī drusku vairāk atmiņas patērēs - it īpaši, ja daudz krustojumi kartē. Tās izmešanas ietaupīšana var izrādīties diezgan izdevīga lieta.. it īpaši šādām vienkāršām grid kartēm, kad nav sarežģītā un ilgā veidā nožu kaimiņu jāmeklē.
Rīt būs jāpakesperimentē ar manējo A*, vai un kādu ieguvumu šitais dod. |
|
| Back to top |
|
|
Storm
Joined: 11 Apr 2006
Posts: 742
|
| Posted: Thu Jan 03, 2008 2:25 am Post subject: |
|
Es jau patiesiibaa ne tik daudz uz to pathfindingu neemos kaa uz to movementu pa vinju... man ir 90% (varbuut arii mazaak ko var zinaat  ) pabeigta taata lieta kaa path smoothings, kas tiek pielietots kaa posteffekts, lai ieguutu dabiskaaku kustiibu (kas nu notiks nevis pa visiem atrastajiem celja punktiem, bet tikai tiem, kas nav savienojami "pa taisno", bet rodas probleemas ar to pasu paarveidosanu ka curve, jo iznemot aaraa paaraak daudz vins liikumos vnk taa nogludina, ka iebrauc sienaa... Vareetu taisiit kkadu koliiziju detekciju vai kko tamliidziigu vai arii domaat kaa un kur ideaalaa gadiijumaa ievietot papildus punktus.
Btw viss grafikas kods ir sacepts pa kaadu stundu XD |
|
| Back to top |
|
|
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Thu Jan 03, 2008 10:53 pm Post subject: |
|
Izmēģināju to fīču - nemest no open saraksta atkārtojošos elementus.
Ātrdarbības ieguvums labirinta veida mapēs (tādās kādās mēs te iepriekš mērījāmies) ir pilnīgi nekāds, izņemot vienkāršāku kodu ;) Taču mapēs, kurās ir daudz tukšuma t.i. rūtiņā var nonākt no vairākiem ceļiem, ieguvums ir iespaidīgāks: no 1.5 reizēm mazākām kartēm līdz pat 4 reizēm lielākām kartēm. Patērētais atmiņas daudzums (vismaz manā implementācijā) pieauga nenozīmīgi - ap 1%. Viduvējai kartei, kura patērē ap 65 KiB, atmiņas patēriņs pieauga par 1 KiB.
Laba optimizācija :) Vienkāršāks kods un pie reizes ātrdarbības pieaugums. |
|
| Back to top |
|
|
Storm
Joined: 11 Apr 2006
Posts: 742
|
|
| Back to top |
|
|
snake5
Indago dalībnieks
Joined: 27 Jun 2007
Posts: 2590
|
| Posted: Sun Jan 06, 2008 5:18 pm Post subject: |
|
kaa tur jaabalso?
_________________
"There are two choices here: "looks good" and "realism"." -- Paul Nettle |
|
| Back to top |
|
|
Storm
Joined: 11 Apr 2006
Posts: 742
|
|
| Back to top |
|
|
snake5
Indago dalībnieks
Joined: 27 Jun 2007
Posts: 2590
|
| Posted: Sun Jan 06, 2008 7:21 pm Post subject: |
|
ok, ir!
tev 1. vietu iedevu 
_________________
"There are two choices here: "looks good" and "realism"." -- Paul Nettle |
|
| 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
