 |
dev.gamez.lv
Latvian Game Developers Community
|
| View previous topic :: View next topic |
| Author |
Message |
Kamazs
Guru
Joined: 17 Jan 2003
Posts: 829
Location: The glorious ancient city of Loja
|
 Posted: Fri Aug 24, 2007 11:55 am Post subject: Optimāla Random punkta izvēle spēles kartē |
|
Jautājums, iespējams, šķiet triviāls, bet tomēr ar šo problēmu esmu saskāries ne reizi vien, tāpēc labprāt dzirdētu citu spēļu veidotāju viedokļus par to, kā risināta šī problēma.
Problēmas izklāsts
Lieta ir gauži vienkārša (kā jau vienmēr) -- kaut kādā noteikti momentā es gribu, lai mans NPC ņem un dodas uz random punktu. Risinājums šķiet gandrīz elementārs, tjipa,
| Code: |
target_x = random_number( -map_hwidth, map_hwidth );
target_y = random_number( -map_hheight, map_hheight );
|
Bet tas neder, jo, iespējams, ka šajā vietā būs kāds objekts, varbūt karte tur nemaz nav pieejama (pathfindings netiek klāt). Kā rīkoties šādā situācijā?
Iespējamie risinājumi
Man ir vairāki varianti, kā risināt šo problēmu:
- paļauties, ka ja objektu maz, tad gan jau viss būs čiki vairumā gadījumu. Neder, jo reāli spēlēs "maza iespējamība" nozīmē to, ka viens no 100 NPC tomēr trāpīs tajā punktā. Un tā nav iespējamība, bet fakts.
- uztaisīt ciklu, kurā katrreiz izvēloties punktu, tiek pārbaudīts, vai tas der. Manuprāt, neder, jo tas imo ir slikts programmēšanas stils. Domāju, ka 90% gadījumu tas strādās labi un ātri, bet..ja nu nepieejama ir liela daļa kartes? Randoms šaus gandrīz pilnīgi nejauši pa visu lauku un mēs varam vienā brīdī iegrābties uz bezgalīgo ciklu, kas nokar visu pasākumu. No bezgalīgā cikla var izvairīties ar kaut kādu nosacījumu, bet tad mēs atgriežamies pie pirmā risinājumu un, kopumā ņemot, problēma reāli nav atrisināta.
- ar specifisku soli sistemātiski izstaigāt karti un atmiņā saglabāt visus punktus, kuri der. Pēc tam vienkārši uz labu laimi izvēlēties jebkuru no šiem punktiem. Izvēloties soļa lielumu un aplūkojamo zonu, var piedzīt perfomanci. Es neesmu drošs vai šis neder, bet kaut kā baigā sajūsmā par šādu risinājumu neesmu, lai gan tas principā ir diezgan drošs un neko daudz perfo. neapēdīs (ja rīkosies prātīgi). Nepatīk, jo smagnējs.
- varbūt risinājums ir šo metožu kombinācija? piemēram, uztaisīt īsu ciklu (~5 iterācijas), kuru laikā mēģina uz labu laimi trāpīt kādā punktā un, ja tad nesanāk, tad ar soļu metodi atrod drošu punktu. Risinājums nav tik smagnējs, nav arī perfo-hita diža. Šim mīnusus neatrodu.
- vēl viens risinājums ir randomā paņemt jebkuru punktu un pēc tam, ja tas neder, interpolēt kādu citu punktu, kas der. Piemēram, izvēlamies punktu A, tas neder, bet, novelkot līniju no mūsu varoņa līdz A un pasperot soli varoņa virzienā gan pa x, gan y koordinātām uz šīs līnijas izvēlamies citu punktu A1, kas, iespējams der. Vēl labāk, ja zinām objekta izmērus, kas "sēž" virsū nelaimīgajam punktam, tad mēs varam pakāpties atpakaļ pa šo līniju tieši par šī objekta izmēru. Šis arī šķiet tīri pieklājīgs risinājums un es pat to izmantoju vietām. Nav tā ka neder, bet mani kaut kā uztrauc doma par to -- a ja nu A1 arī neder? Reāli dzīvē (spēlē) gandrīz 100% gadījumu tas derēs, bet -- tas ir tā pat, kā ar to pirmo variantu. Ja ir kaut 1% iespējamība, tad tas noteikti notiks. Vai manas bažas ir veltas? Katrā ziņā "tīra" un "droša" šī metode nav. Vismaz bez papildinājumiem.
- ir arī mazliet jancīgs variants -- ja mums nav obligāti noteikts, ka jāatrod punkts tieši visā kartes laukumā, bet jebkur, tad var atrast attālumu līdz tuvākajam objektam un random punktu izvēlēties šī attāluma robežās, zinot, ka neviena cita objekta te nebūs. Šitas ir tāds ātrs un viegls risinājums, bet iespējams radīs gļuku ja varonis būs ļoti tuvu kādam objektam.
Tātad it kā risinājums man ir, bet es tomēr labprāt dzirdētu arī citu viedokļus, domas. Iespējams, ka es par jaunu gudroju velosipēdu, "normāli cilvēki jau sen dara savādāk". Laipni lūdzu visus uz diskusiju!
_________________
...un es uzskatu, ka Fallout ir etalons |
|
| Back to top |
|
 |
bubu
Indago Uzvarētājs
Joined: 23 Mar 2004
Posts: 3223
Location: Riga
|
| Posted: Fri Aug 24, 2007 12:13 pm Post subject: |
|
Es ļoti iespējams, ka ņemtu for cikla variantu.
Vai arī iespējams ka to stara metodi. tb izvēlētos punktu (x,y), vilktu staru no tava NPC uz šo punktu un, ja tas atdurtos kādā citā objektā, tad ietu uz šo punktu. Ja nevar nekur paiet (tipa stāvi pie sienas, un stars izvēlēts tieši virzienā uz sienu), tad nekur neietu - stāvētu. Tas jau arī savā ziņā ir normāli.
Cik saprotu, tad spēle tev ir 2d pasaulē, tāpēc meklēt sadursmi staram ar citiem objektiem var ļoti ātri. Tur var izmantot Wolfenstein 3D spēlē izmantoto raycasting metodi - pasaule sadalīta rūtiņās, un velkot staru tiek iets tikai pa rūtiņu malām/krustpunktiem. Tavā gadījumā atliks tikai pārbaudīt katrai rūtiņai iekšpusi, vai tur nekolidē stars ar objektu. Katrā ziņā tas būs daudz ātrāk par O(n), kuru prasītu salīdzināt stara sadursme ar visiem pasaules objektiem. |
|
| Back to top |
|
|
elvman
Indago Uzvarētājs
Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga
|
| Posted: Fri Aug 24, 2007 12:58 pm Post subject: |
|
Kā būtu ar variantu: ej kur deguns rāda? Nevis nostādīt destination punktu, bet pēc kaut kādiem nosacījumiem (šaut starus un pārbaud'ti vai sāni/priekša ir brīva utt.) rotēt un kustēties deguna virzienā. Šis variants neprasīs nekādus algoritmus path'a meklēšanai un izskatīsies diezgan reāli.
_________________
long time; /* know C */ |
|
| Back to top |
|
|
EDDY
Joined: 07 Oct 2005
Posts: 1610
Location: Dzimtā zeme, Latvija
|
| Posted: Fri Aug 24, 2007 1:04 pm Post subject: |
|
Es izvēlētos sarakstu ar jau esošo (aizņemto ) objektu koordinātēm katrai mapei atšķirīgu. Sarakstā man būtu arī informācija par objekta aizņemto laukumu. Visu beidzot, viss ir atkarīgs no funkcijas un tās iespējām.
Manuprāt daudzi programmētaji atsauks atmiņā "Šautriņu mešanas algoritmu", kur tiek dota punkta koordinātes un speciāla funkcija pārbauda, vai objekts tur iekļūst.
Nav problēmas izveidot aizņemtos laukumus ap katru objektu no listes.
Plus vēl piekombinēt vēlamos laukumus no "otras listes".
Un anyway tavs npc tik bieži nemostas kādā vietā, lai uztrauktos par ātrdarbību.
_________________
Monday|Tuesday|Wednesday|Thursday|Friday|Saturday|Sunday |
|
| Back to top |
|
|
Kamazs
Guru
Joined: 17 Jan 2003
Posts: 829
Location: The glorious ancient city of Loja
|
| Posted: Fri Aug 24, 2007 2:02 pm Post subject: |
|
| Quote: |
Un anyway tavs npc tik bieži nemostas kādā vietā, lai uztrauktos par ātrdarbību.
|
Nuuu..vispār tas notiek ļoti bieži. Kā jau nojaušams, runa ir par Wellguardu -- top-down 2D, kur ir daudz žurku, kas pseido-haotiski pārvietojas. Līdz ar to, tur ir ļoti daudz NPC (šobrīd ~220), kas katrs grib kaut kur doties ik pēc brīža -- kur brīdis var būt diezgan īss. Sekas -- parādās bottlenecka simptomi un prasās pietiekami optimālu algoritmu, lai neatnjirgtos. Tā jau pathfindings rij nost resursus pietiekami.
Katrā ziņā, paldies par idejām, tas man tiešām palīdzēja!
_________________
...un es uzskatu, ka Fallout ir etalons |
|
| Back to top |
|
|
EDDY
Joined: 07 Oct 2005
Posts: 1610
Location: Dzimtā zeme, Latvija
|
| Posted: Fri Aug 24, 2007 2:47 pm Post subject: |
|
Varbūt zini (pilnīgi noteikti), ka iekš Microsoft SDK ir piemērs, kur rodas jauni Tiny modeļi, turklāt vēl animētie. Tas piemērs jau parāda to, ka var variēt ar 1000 un vairāk objektiem bez ievērojamas bremzes.
Kaut kas saistīts ar partīkļu loģiku. Īsti neesmu pētījis, bet tā vienkārši to piemēru jau neliktu iekšā.
_________________
Monday|Tuesday|Wednesday|Thursday|Friday|Saturday|Sunday |
|
| Back to top |
|
|
snake5
Indago dalībnieks
Joined: 27 Jun 2007
Posts: 2590
|
| Posted: Fri Aug 24, 2007 2:50 pm Post subject: |
|
nu, var darīt tā:
randomā izvēlas punktu, un pa spirāli pārbauda sadursmes...
vai uztaisa gridu, sanumurē visus brīvos punktus jau iepriekš UN dabū randomā numuru starp 0 un brīvo punktu skaitu, un attiecīgi paņem tā punkta koordinātes..
_________________
"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: Fri Aug 24, 2007 3:19 pm Post subject: |
|
| EDDY wrote: | | Manuprāt daudzi programmētaji atsauks atmiņā "Šautriņu mešanas algoritmu", kur ... |
Vai šis algoritms ir saistīts ar bēdīgi slaveno "Spider-algoritmu"? |
|
| Back to top |
|
|
EDDY
Joined: 07 Oct 2005
Posts: 1610
Location: Dzimtā zeme, Latvija
|
| Posted: Fri Aug 24, 2007 3:32 pm Post subject: |
|
Galvenais jau pati ideja, uz ko attiecināms šis nosaukums.
Varbūt tavā augstskolā to sauca savādāk, varbūt tam pat ir cits nosaukums (kas ir ļoti ticams), bet ideju, ka punkts (šautriņa) tiek mesta laukumā, kuru veido funkcija, es paņēmu no grāmatas.
_________________
Monday|Tuesday|Wednesday|Thursday|Friday|Saturday|Sunday |
|
| Back to top |
|
|
snake5
Indago dalībnieks
Joined: 27 Jun 2007
Posts: 2590
|
| Posted: Fri Aug 24, 2007 3:37 pm Post subject: |
|
kas ir spider-algoritms? googlē neatradu..
_________________
"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: Fri Aug 24, 2007 4:25 pm Post subject: |
|
| EDDY wrote: | | Varbūt tavā augstskolā to sauca savādāk... |
Nezinu gan, manā augstskolā neko tādu neesmu dzirdējis.
| snake5 wrote: | | kas ir spider-algoritms? googlē neatradu.. |
Palasi šeit: http://dev.gamez.lv/viewtopic.php?t=1113 |
|
| Back to top |
|
|
snake5
Indago dalībnieks
Joined: 27 Jun 2007
Posts: 2590
|
| Posted: Fri Aug 24, 2007 5:14 pm Post subject: |
|
ahaa  the "spider" algorithm  nuu labais... ir taads teiciens: ko cilvēks ir uzcēlis, to cilvēks var arī nojaukt.. tas par aizsardzībām, progām, un ASM...
_________________
"There are two choices here: "looks good" and "realism"." -- Paul Nettle |
|
| Back to top |
|
|
Storm
Joined: 11 Apr 2006
Posts: 742
|
| Posted: Sat Aug 25, 2007 1:41 am Post subject: |
|
| Profesionaalaas speelees taa lieta tiktu risinaata vienaakrsi un geniaali - katram NPC developeris ir pielicis listinju ar jaukaam vietaam, kur shas vareetu izmest kaadu liikumu - rezultaataa visas lokaacijas buus logiskas un skaistas - piem vins apstaajaas lai paostiitu pukiites un pie reizes izdvess kaadu fraazi vai arii vnk paklejo xD |
|
| Back to top |
|
|
elvman
Indago Uzvarētājs
Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga
|
| Posted: Sat Aug 25, 2007 8:50 am Post subject: |
|
Laikam neizlasiji visu topiku Storm. Algoritms ir vajadzīgs žurciņām, kuru skaits var būt neierobežots. Tur katram salikt triggerus nebūs iespējams.
_________________
long time; /* know C */ |
|
| Back to top |
|
|
Storm
Joined: 11 Apr 2006
Posts: 742
|
| Posted: Sat Aug 25, 2007 2:25 pm Post subject: |
|
Ar pathfindinga paliidziibu atrodi speeles saakumaa katrai zurkai random punktu listinju , un speeles laikaa lai shaas skraida pa tiem random puntiem.
Veel vareetu vnk visaam zurkaam vienu lielu listu - buutu variaacijas vairaak, bet tad var gadiities ka taas zurkas visas ir vienaa kartes galaa saskreejusas Bet ja katrai zurkai savs listsins tad var kontroleet cik taalu tie random punti var atrasties no saakuma lokaacijas un buus katrai zurkai sava teritorija  tas gan nenoziimee ka zurkaam nevar taas teritorijas paarklaaties 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
