redzamības noteikšana
- kristapuciitis
- Posts: 163
- Joined: 03 Jun 2011, 14:22
redzamības noteikšana
Sveiki!
Vajag palīdzību! Es nezinu, kā noteikt, vai kāds noteikts objekts ir redzams, ja ir dotas tavas atrašanās vietas koordinātas (punkts) (x, y), šķēršļu stūru koordinātas (x, y), caur kuriem nevar redzēt, un objekta stūru koordinātes (x, y). Vai kāds var palīdzēt?
Vajag palīdzību! Es nezinu, kā noteikt, vai kāds noteikts objekts ir redzams, ja ir dotas tavas atrašanās vietas koordinātas (punkts) (x, y), šķēršļu stūru koordinātas (x, y), caur kuriem nevar redzēt, un objekta stūru koordinātes (x, y). Vai kāds var palīdzēt?
Gooby pls
Re: redzamības noteikšana
Tur ir visvisādi varianti.
Vienkāršotā gadījumā, ja tev karte ir kā rūtiņas, tad var vilkt staru no savas pozīcijas uz mērķi, un skatīties, vai stars krusto sienu, vai nē. Ja nekrusto, un staru var aizvilkt līdz tavam objektam, tad tas nozīmē, ka objekts ir redzams.
Efektīvi to var darīt ar raycasting'u kā darīja Wolfenstein 3D:
http://www.permadi.com/tutorial/raycast/
Nevajag sabīties no 3D. Pats algoritms darbojas divās dimensijās. Wolfenstein 3D iegūto rezultātu izmantoja, lai renderētu 3D telpu.
Visa sāls ir Figure 14 bildē. Raycastings pēc būtības ir Bresanhēma līnijas zīmēšanas algoritms (rūtiņu apstaigšana, velkot līniju aiz sevis - tb tavā gadījumā stars no acs līdz objektam): http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
Šeit kautkāds piemērs, kas sadursmes ar šķēršļiem meklē pikseļu līmenī (būs ļoti neefektīvi un dārgi, ja liela karte): http://www.codeproject.com/KB/GDI-plus/ ... ing2D.aspx Šo vispārinot - pārtaisot pikseļus par lielākām rūtiņām - dabūsi augstāk minēto Wolfenstein 3d stila raycasting'u. W3D katra rūtiņa, caurstaigājama vai necaurstaigājama, bija viens bloks - sienas klucītis, durvis, galds, utml.
Ja karte nav pa rūtiņām, un šķēršļi var būt patvaļīgi, tad ir sarežģītāk. Vienkāršākais variants būtu izmantot kādu 2d fizikas bibliotēku, kas tev kolīzijas pati sameklēs. Domāju, ka Box2D vai Chipmunk to vajadzētu mācēt.
Ja gribi pats rakstīt, tad vajadzēs ņemt palīgā ģeometriju un mācēt atrast taisnes/nogriežņa krustpuntu ar tavu šķēršļu objekta formām (kvadrāti/sfēras/nogriežņi/utt). Un lai to visu darītu efektīvāk nāksies izmantot kādu telpas dalīšanas algoritmu pa daļām. Tur visādi BSP, QuadTree, utml.
Vienkāršotā gadījumā, ja tev karte ir kā rūtiņas, tad var vilkt staru no savas pozīcijas uz mērķi, un skatīties, vai stars krusto sienu, vai nē. Ja nekrusto, un staru var aizvilkt līdz tavam objektam, tad tas nozīmē, ka objekts ir redzams.
Efektīvi to var darīt ar raycasting'u kā darīja Wolfenstein 3D:
http://www.permadi.com/tutorial/raycast/
Nevajag sabīties no 3D. Pats algoritms darbojas divās dimensijās. Wolfenstein 3D iegūto rezultātu izmantoja, lai renderētu 3D telpu.
Visa sāls ir Figure 14 bildē. Raycastings pēc būtības ir Bresanhēma līnijas zīmēšanas algoritms (rūtiņu apstaigšana, velkot līniju aiz sevis - tb tavā gadījumā stars no acs līdz objektam): http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
Šeit kautkāds piemērs, kas sadursmes ar šķēršļiem meklē pikseļu līmenī (būs ļoti neefektīvi un dārgi, ja liela karte): http://www.codeproject.com/KB/GDI-plus/ ... ing2D.aspx Šo vispārinot - pārtaisot pikseļus par lielākām rūtiņām - dabūsi augstāk minēto Wolfenstein 3d stila raycasting'u. W3D katra rūtiņa, caurstaigājama vai necaurstaigājama, bija viens bloks - sienas klucītis, durvis, galds, utml.
Ja karte nav pa rūtiņām, un šķēršļi var būt patvaļīgi, tad ir sarežģītāk. Vienkāršākais variants būtu izmantot kādu 2d fizikas bibliotēku, kas tev kolīzijas pati sameklēs. Domāju, ka Box2D vai Chipmunk to vajadzētu mācēt.
Ja gribi pats rakstīt, tad vajadzēs ņemt palīgā ģeometriju un mācēt atrast taisnes/nogriežņa krustpuntu ar tavu šķēršļu objekta formām (kvadrāti/sfēras/nogriežņi/utt). Un lai to visu darītu efektīvāk nāksies izmantot kādu telpas dalīšanas algoritmu pa daļām. Tur visādi BSP, QuadTree, utml.
Re: redzamības noteikšana
Vienkāršākais variants ir salasīties stara-objektu sadursmes kodus un ciklā testēt visus. Sarežģītākais būtu pateikt, ar kādiem tieši objektiem ir darīšana. Tile-based līmeņiem jāmeklē vokseļu apstaigāšanas algoritms. Tas līniju zīmēšanas algoritms šādam uzdevumam (tile-based līmeņiem) galīgi neder, jo tiek palaisti garām stūri. Ar pikseļiem gan būs OK.
Re: redzamības noteikšana
Labrīt. Kā nu neder, ka der. Robežgadījumu gadījumā < pamaini uz <= (vai > uz >=) un būs tev tie stūri. Un brezahēma algoritmu vienmēr var uzrakstīt 8-way-adjacency pikseļiem, ne tikai 4-way ja tu to domāji ar "stūrus palaidīs garām": http://lifc.univ-fcomte.fr/~dedu/projec ... index.htmlsnake5 wrote:Tas līniju zīmēšanas algoritms šādam uzdevumam (tile-based līmeņiem) galīgi neder, jo tiek palaisti garām stūri.
Un vokseļi vispār jau ir 3d objekti. 2d gadījumā tavu "vokseļu" apstaigāšanu sauc par raycasting'u.
Re: redzamības noteikšana
Ir jēga spiest kaut ko ārā no viena algoritma, ja ir cits, kurš visu perfekti izdara?
Raycasting tas ir neatkarīgi no dimensiju skaita. Un voxel/grid traversal algoritmi atšķiras tikai ar vienu asi (dažas koda līnijas), darbības principi ir tieši tie paši.2d gadījumā tavu "vokseļu" apstaigāšanu sauc par raycasting'u.
Re: redzamības noteikšana
Tieši tā - brezanhēma algoritums visu perfekti izdara :)snake5 wrote:Ir jēga spiest kaut ko ārā no viena algoritma, ja ir cits, kurš visu perfekti izdara?
Re: redzamības noteikšana
Neizdara perfekti: http://imageshack.us/photo/my-images/19 ... rvrsl.png/ (bilde no wikipēdijas SVG, nedaudz uzlabota). Wikipēdijai gan pārāk ideāls tas attēls (kad es testēju, gļukoja daudz biežāk), bet problēmas var atrast anyway.
Sarkanie laukumi tiek palaisti garām. Un tajā modifikācijā pārāk daudz laukumus sīkāk testētu.
Sarkanie laukumi tiek palaisti garām. Un tajā modifikācijā pārāk daudz laukumus sīkāk testētu.
Re: redzamības noteikšana
Tu linkus, kurus es dodu neskaties? http://lifc.univ-fcomte.fr/~dedu/projec ... index.html
Re: redzamības noteikšana
Es apskatījos. Atbilde uz to:
Es arī nedaudz apšaubu iespēju noteikt secību/sadursmes punktu/normālvektoru tādā veidā.Un tajā modifikācijā pārāk daudz laukumus sīkāk testētu.