Kollisions tjek

Det er en hel videnskab i sig selv. Jeg ville nok anbefale dig at søge på google efter svaret for at finde præcis det der passer til dig... Jeg har selv lavet noget lignende, men det er mere indviklet end blot to firkanter. Det tager højde for en masse geometriske figuerer og det tager højde for at der sikkert er en del af dem. Så hvis du skal bruge noget simpelt, vil jeg anbefale dig at finde noget simpelt - så kan du også selv kode videre på det, hvis du vil.

Jeg kom lige i tanke om et andet trick, hvis blot at du givet et punkt skal vide om det ligger inden for et polygon.

forudsætningerne her er at kanterne i polygonet betragtes som linjesegmenter.

Hvis du gerne vil vide om punktet p ligger inden for polygonet omkrandset linjesegmenter, så laver du et linjesegment der går fra (-uendeligt, p.y) til (p.x, p.y), med uendeligt menes blot noget stort nok.
Nu skal du blot vide hvor mange af linjesegmenterne i polygonet der skærer dit konstruerede linjesegment. hvis det er et lige antal ( modulus = 0) så ligger punktet uden for polygonet, hvis det er et ulige antal så ligger punktet inden for polygonet.

kørselstiden for denne metode er O(N) hvor N er antallet linjesegmenter som polygonet er lavet af. med mere inviklede algoritmer kan denne tid reduceres til O(logN) men på bekostning af hukommelsen som bliver O(NlogN), Med decideret nærmest umulige algoritmer kan dette dog (i teorien) reduceres til O(N) igen.

Men sålænge at dine polygoner ikke er større end 5-6 (og sikkert også større) linjesegmenter, så er det ligemeget.

Metoden virker på både konvekse og konkave polygoner.

http://www.gamedev.net/community/forums/topic.asp?topic_id=340219

GameDev er en glimrende side når det gælder spiludvikling. De har en hel række af artikler der fortæller om hvordan man kan udregne psyhics og mere.

Desuden prøv at kigge her: http://www.pfirth.co.uk/

http://www.gamedev.net/community/forums/topic.asp?topic_id=340219

GameDev er en glimrende side når det gælder spiludvikling. De har en hel række af artikler der fortæller om hvordan man kan udregne psyhics og mere.

Desuden prøv at kigge her: http://www.pfirth.co.uk/

Jeg har tidligere kigget på GameDev, jeg syntes dog ikke at jeg kan finde noget brugbart. Det andet link ser til gengæld ret interessant ud. Tjekker det ud senere!

Lige et link mere: http://www.gamedev.net/reference/articles/article735.asp

http://en.wikipedia.org/wiki/Separating_axis_theorem

virker med alt, mellem alt, sålænge det bare er konvekst

edit: virker i øvrigt også i 3d!

http://en.wikipedia.org/wiki/Separating_axis_theorem

virker med alt, mellem alt, sålænge det bare er konvekst

edit: virker i øvrigt også i 3d!

Forstår ikke helt hvad det går ud på. Hvordan bruger man det i praksis?

Det eneste jeg skal bruge er en algoritme af en art som beskrevet i min første post.

Det her tager godt nok udgangspunkt i OpenGL, men du kan måske omsætte det til noget brugbart.

http://www.3dcodingtutorial.com/Collision-Detection/Collision-Boxes.html

Det her tager godt nok udgangspunkt i OpenGL, men du kan måske omsætte det til noget brugbart.

http://www.3dcodingtutorial.com/Collision-Detection/Collision-Boxes.html

Så vidt jeg kan se giver den ikke rigtig svar på mit spørgsmål..

Jeg kom lige i tanke om et andet trick, hvis blot at du givet et punkt skal vide om det ligger inden for et polygon.

forudsætningerne her er at kanterne i polygonet betragtes som linjesegmenter.

Hvis du gerne vil vide om punktet p ligger inden for polygonet omkrandset linjesegmenter, så laver du et linjesegment der går fra (-uendeligt, p.y) til (p.x, p.y), med uendeligt menes blot noget stort nok.
Nu skal du blot vide hvor mange af linjesegmenterne i polygonet der skærer dit konstruerede linjesegment. hvis det er et lige antal ( modulus = 0) så ligger punktet uden for polygonet, hvis det er et ulige antal så ligger punktet inden for polygonet.

kørselstiden for denne metode er O(N) hvor N er antallet linjesegmenter som polygonet er lavet af. med mere inviklede algoritmer kan denne tid reduceres til O(logN) men på bekostning af hukommelsen som bliver O(NlogN), Med decideret nærmest umulige algoritmer kan dette dog (i teorien) reduceres til O(N) igen.

Men sålænge at dine polygoner ikke er større end 5-6 (og sikkert også større) linjesegmenter, så er det ligemeget.

Metoden virker på både konvekse og konkave polygoner.

Okay, det forstår jeg godt. Det endeste problem er: Hvordan finder man ud af hvor mange linjer i polygonet der skærer den fiktive linje?