Jag håller på att lära mig själv lite koncept inom linjär algebra som jag borde ha lärt mig för länge sedan. För tillfället så håller jag på att implementera en sensor som ska reagera när ett objekt rör sig inom dess synfält. Detta har jag lyckats med, men nu vill jag göra så att den inte kan se genom objekt; alltså någonting sånt här:
Min tanke är att jag för varje "sebart" objekt inom sensorns synfält ska kolla om vektorn mellan sensorn och objektet genomskär ett block. Det är detta som jag har problem med.
I slutändan så skulle jag vilja kunna hantera alla möjliga polygoner, men för stunden så kan jag nöja mig med rektanglar som är rakt horisontella och vertikala.
De resurser jag har hittat har antingen sugit, varit för komplexa för mitt stackars sinne, eller bara varit allmänt förvirrande. Så ha i åtanke att ni talar med någon som nyligen fattat vad en skalärprodukt är.
Kanske ska tillägga att jag är inte intresserad utav själva "sebarhetsvolymen" (d.v.s. det gula fältet i min bild), utan endast att få sensorn att inte kunna se igenom väggar.
Lägger till lite pseudokod för att visa vad det är jag gör just nu:
//Om objektet är tillräckligt nära sensorn för att ses
if distance(sensor.pos, object.pos) <= sensor.viewradius:
normalized_sensor_vector = normalize(sensor.facing)
sensor_to_object_vector = normalize(Vector( object.pos - sensor.pos ))
angle = acos( dot( normalized_sensor_vector, sensor_to_object_vector ) )
//sensor.viewfield är här den vinkeln sensorn kan se i radianer
if angle <= sensor.viewfield/2:
//objektet ses av sensorn
Jag och Anderslkpg diskuterade igår saken, och han kom då på en modell som bör fungera - men som är jag osäker på hur man bör implementera.
Den går ut på att man tänker sig världen som ytan på en klassisk radarbild där sensorn är i mitten och skannar av sin omgivning. Om ett block är ivägen så hamnar allt bakom i radioskugga. Denna radioskugga bör kunna uttryckas som området mellan bildas mellan vektorerna mellan sensorn och blockets yttersta hörn. Detta torde då fungera oavsett hur många hörn blocket har, och hur det är roterat.
Frågan är då hur man får fram vilka som är de yttersta hörnen, och hur man vet huruvida objektet ligger inom detta område.
Jag har dock en annan, kanske simplare tanke. Istället för att se blocket som... Ett block, så kan vi se den som ett gäng sammankopplade linjer. I sådant fall borde man kunna kolla huruvida linjen mellan sensorn och objektet korsar en utav blockets linjer. Det känns som att det vore enklare. I så fall så är problemet att hitta en linje-segment-genomskärningsalgoritm som inte får mitt huvud att explodera.
Du är smart![[rolleyes]](/img/smilies/rolleyes.gif)
Netherlick:
Du är smart
Tydligen inte tillräckligt. ![[sad]](/img/smilies/sad.gif)
Tack vare er uttömmande hjälp så har jag nu en fullt fungerande lösning som fungerar för allehanda polygoner - oavsett hur de är formade.
Jag körde på min idé med att behandla varje linje i polygonen istället för att koncentrera på polygonen självt.
Varje polygon består utav ett antal punkter. För varje par utav dessa punkter så kollar jag först huruvida båda punkter ligger längre bort från sensorn än vad objektet gör. Om de gör det så vet jag att de inte skymmer objektet. Om en eller båda punkter befinner sig närmre sensorn än vad objektet gör så använder jag denna magi för att kolla huruvida linjen mellan sensorn och objektet korsar linjen mellan polygonens två punkter:
function isOnSegment(xi, yi, xj, yj, xk, yk)
return (xi <= xk or xj <= xk) and (xk <= xi or xk <= xj) and (yi <= yk or yj <= yk) and (yk <= yi or xk <= yj)
end
function computeDirection(xi, yi, xj, yj, xk, yk)
local a = (xk - xi) * (yj - yi)
local b = (xj - xi) * (yk - yi)
if a < b then return -1 elseif a > b then return 1 else return 0 end
end
function doLineSegmentsIntersect(x1, y1, x2, y2, x3, y3, x4, y4)
local d1 = computeDirection(x3, y3, x4, y4, x1, y1)
local d2 = computeDirection(x3, y3, x4, y4, x2, y2)
local d3 = computeDirection(x1, y1, x2, y2, x3, y3)
local d4 = computeDirection(x1, y1, x2, y2, x4, y4)
return (((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and
((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0))) or
(d1 == 0 and isOnSegment(x3, y3, x4, y4, x1, y1)) or
(d2 == 0 and isOnSegment(x3, y3, x4, y4, x2, y2)) or
(d3 == 0 and isOnSegment(x1, y1, x2, y2, x3, y3)) or
(d4 == 0 and isOnSegment(x1, y1, x2, y2, x4, y4))
end
Allt som behövde göras efter det var att på ett någorlunda intelligent sätt testa varje linje som bildar polygonen. Det är säkert inte det snabbaste sättet, men jag tror att om man eliminerar så många fall som möjligt (d.v.s. punkter som ligger för långt bort) innan man börjar kolla vinklar så går det åtminstone tillräckligt fort för mina behov. Ska man kolla 10000 polygoner per sekund kanske man bör hitta på något snabbare.
För att snabba upp det hela kan du ju börja med att sortera bort alla linjer som inte har någon endpoint inom view distance; det borde vara en betydligt snabbare operation än att testa skärning för alla linjer direkt. Du kan ju även (om det handlar om ett spel där spelaren kan röra sig över spelplanen eller någon liknande simulering) hålla dig med flera olika listor av polygoner, så du bara behöver jämföra spelarens vy med de linjer som ligger i listorna omedelbart brevid spelaren.
Gentlernen:
För att snabba upp det hela kan du ju börja med att sortera bort alla linjer som inte har någon endpoint inom view distance
Heh. Hade givetvis tänkt göra så, men jag glömde helt enkelt bort att implementera det. Nu är det i alla fall gjort. Har inte gjort några mätningar för att se om det går fortare, men man borde kunna anta att de två extra mätningarna bör gå snabbare än ett onödigt skärningstest.
Gentlernen:
Du kan ju även (om det handlar om ett spel där spelaren kan röra sig över spelplanen eller någon liknande simulering) hålla dig med flera olika listor av polygoner, så du bara behöver jämföra spelarens vy med de linjer som ligger i listorna omedelbart brevid spelaren.
Nu förstår jag inte riktigt hur du menar. Vad jag gör är att kolla om spelaren är tillräcklig nära sensorn för att ses. I så fall kollar jag vilka polygoner som ligger tillräckligt nära för att kunna blockera sensorns synfält. Sedan kollar jag huruvida de polygoner som är tillräckligt nära faktiskt blockerar synfältet.
Insåg just att jag har ett fel i min algoritm. Jag kan inte sortera bort linjer vars ändpunkter är längre bort från sensorn än objektet. Då kan ibland sensorn "se igenom väggar". Låt mig illustrera med ett exempel:
Som ni kan se så är avståndet till spelaren mindre än avståndet till de båda punkterna, alltså skulle sensorn i det här exemplet "se igenom" väggen.
Åtta:
Nu förstår jag inte riktigt hur du menar.
Du har forfarande O(n) eftersom du måste jämföra spelarens position med samtliga objekt. Istället kan du göra som på den bifogade bilden. Den svarta rektangeln är spelplanen, och du har två listor; röd och grön. Den röda listan innehåller alla objekt som befinner sig på den högra halvan av spelplanen och den gröna alla objekt som befinner sig på den vänstra.
Om du ser till att de två listorna är minst dubbelt så breda som spelaren kan se, och att flytta objekt mellan dessa listor allteftersom de rör sig så behöver du bara jämföra spelarens position med den lista han just nu befinner sig i, och den omedelbart till vänster eller höger, eftersom alla andra objekt är för långt bort för att vara relevanta.
Helt meningslöst i exemplet med bara två listor, och kommer knappast att gå fortare på en enkärnig maskin pga. högre komplexitet och att du egentligen bara amorterar distanstestet, men det är betydligt enklare att parallellisera.
Gentlernen:
Om du ser till att de två listorna är minst dubbelt så breda som spelaren kan se, och att flytta objekt mellan dessa listor allteftersom de rör sig så behöver du bara jämföra spelarens position med den lista han just nu befinner sig i, och den omedelbart till vänster eller höger, eftersom alla andra objekt är för långt bort för att vara relevanta.
Ah! Då förstår jag hur du menar. Jag ska komma ihåg det när/om jag inkorporerar detta i ett spel någon gång. För tillfället är det bara ett fåtal polygoner och ett fåtal sensorer, så då har det ingen som helst betydelse.
spännande tråd. lär mig saker tror jag.
