[java] kruispunt twee eenparig rechtlijnige obj.

[Verwijderd]

Ik zit leuk een robot voor robocode te maken, en nu heb ik het volgende probleem.

Ik wil een kogel afschieten die mijn vijand raakt, de snelheid en beginpositie zijn bekend, de hoek wil ik weten.

Van mijn vijand weet ik de positie, richting, en snelheid

dan kom ik op de volgende vergelijking uit voor de positie van mijn kogel:
Xk(t) = Xk(0) + sin(Ak) * Vk * T
Yk(t) = Yk(0) + cos(Ak) * Vk * T

en voor de vijandige bot
Xb(t) = Xb(0) + sin(Ab) * Vb * T
Yb(t) = Yb(0) + cos(Ab) * Vb * T

Xb(t) is de xpositie van de bot op tijdstip t, Ab is de hoek van de bot (en Ak van de kogel), Vb is de snelheid van de bot. Voor de beide hoeken geld dat 0° recht omhoog is, en verder met de klok mee (dus 90° is naar rechts)

De onbekenden zijn dus Ak (die wil ik weten) en T. Nu is het alleen maar een kwestie van de vergelijking naar ák oplossen, maar dat valt dus vies tegen... Mijn natuurkunde-studerende-vriendin kwam tot de conclusie dat ie misschien nummeriek op te lossen is. Maar het probleem lijkt zo eenvoudig...

Iemand een briljante ingeving?

edit:
spelling

[Janoz]

Ik zit ff te kijken... De robot en de kogel bewegen allebij in een rechte lijn en van allebij is de snelheid bekend toch?

Ik denk namelijk dat er mischien wel een iets makkelijker model op te stellen is als je van een andere basis uitgaat.

[leonardo1504]

Ik heb het vermoeden dat het je wel gaat lukken met een stilstaand doel. Een eenparig rechtlijnig bewegend doel is in essentie hetzelfde probleem. Nu moet je volgens mij de snelheid van de kogel (is vector dus rekening houden met de hoek) en die van je vijand bij elkaar optellen. Nu is het probleem gereduceerd tot hetzelfde probleem met een stilstaand doel.
Het slimme rekenwerk mag je zelf doen

[Soultaker]

Ah ja, dit probleem herken ik wel van 't coden van een Quake bot. Ik heb het toen opgelost met een benadering.

Eerst neem je de afstand van jou tot je doelwit en deelt die door de snelheid van je kogel. Je hebt nu de tijd tussen het afschieten van de kogel en het bereiken van het doel berekend. Op basis hiervan en de positie en snelheid van het doelwit, kun je inschatten waar je doelwit zich bevind als jou kogel 'm moet bereiken (redelijk simpel, zoals je zelf al aangaf).

Het probleem is natuurlijk, dat je eigenlijk uit moet gaan van de afstand van jou tot je doelwit op 't moment dat de kogel inslaat en niet op 't moment dat je de kogel afschiet. De positie van het doelwit bij inslag kun je pas berekenen, als je weet hoe lang je kogel er over doet en dat weet je pas, als de afstand tussen jou en je doelwit bij inslag bekend is. Kortom: cyclische afhankelijkheid en reden tot paniek.

De afstand is echter goed te benaderen door de bovenstaande procedure een aantal keer te herhalen, waarbij je de afstand die je aan 't eind van de procedure vind elke keer weer invult bij het begin van de procedure. De afstand tussen jou en je doelwit bij het lossen van het schot is dan een geschikte beginwaarde (hoewel je ook een willekeurige constante zou kunnen gebruiken).

Uiteraard moet je de procedure herhalen totdat het verschil met de vorige iteratie klein genoeg is om te verwaarlozen. (Ik weet trouwens niet zeker dat dit verschil strikt dalend is.)

Een redelijk klein aantal iteraties (10 ofzo) voldoet waarschijnlijk wel. Bedenk hierbij dat 't weinig zin heeft om dit probleem exact te berekenen, aangezien je er in je model vanuit gaat dat de snelheid van je doel constant is (wat, naar ik aanneem, niet zo is). Zelfs als je de vergelijking analytisch (en dus exact) oplost bestaat er dus een kans dat je je doel niet raakt. Je kunt dan versnelling meenemen in je model, maar uiteraard is dat slechts een verbetering van het model en garandeert het nog steeds geen 100% raakkans.

_{Wat een een goedkope rip-off van Crobots trouwens, dat Robocode.}

[MSalters]

4 vergelijkingen en 4 onbekenden, X(T) en Y(T) zijn ook nog onbekend..
Truc: sin(x) = sqrt( 1-cos(x)*cos(x) ) -> invullen en je hebt 4 lineaire vergelijkingen in x,y,t en cos(hoek). In elkaar substitueren (matrixje vegen), arccos van cos nemen en je hebt je hoek.

Als het vegen niet lukt, dan is je doel niet te raken (rent harder weg dan je kogels gaan)

[Verwijderd]

Is toch in het 2D vlak? Dus heb je toch te maken met y = ax+b vergelijkingen?

het ontgaat me waar die sin en cos voor zijn.

[Verwijderd]

Op woensdag 12 juni 2002 14:57 schreef Soultaker het volgende:
Ah ja, dit probleem herken ik wel van 't coden van een Quake bot. Ik heb het toen opgelost met een benadering.

Ja, ik krijg langzamerhand ook de indruk dat een benadering toch het makkelijkste is, zeker omdat ander bots waar ik de source van het doorgespit ook zoiets doen...

Op woensdag 12 juni 2002 18:15 schreef MSalters het volgende:
4 vergelijkingen en 4 onbekenden, X(T) en Y(T) zijn ook nog onbekend..
Truc: sin(x) = sqrt( 1-cos(x)*cos(x) ) -> invullen en je hebt 4 lineaire vergelijkingen in x,y,t en cos(hoek). In elkaar substitueren (matrixje vegen), arccos van cos nemen en je hebt je hoek.

een wortel is altijd positief, dus hoe kan sin(x) gelijk zijn aan sqrt(iets)?

[Verwijderd]

Op woensdag 12 juni 2002 18:20 schreef Otis het volgende:
Is toch in het 2D vlak? Dus heb je toch te maken met y = ax+b vergelijkingen?

het ontgaat me waar die sin en cos voor zijn.

Ja, maar die a (de helling) is niet direct bekend. Je hebt de hoek, de richting van de snelheid, en met de sinus neem de de x-component van de snelheid.

[Verwijderd]

De oplossing van soultaker is de enigste mogelijkheid omdat de loop van het kanon ook nog tijd nodig heeft om bij te draaien en die weer afhankelijk is van de hoek. Tip als er nog meerdere robots zijn schiet het eerst op robots die ten opzichte van de kijkrichting van jouw robot het minste zijwaarst bewegen. En nu je toch iteratief de schietrichting moet bepalen kun je beter blijven rijden terwijl je richt/schiet.

[Verwijderd]

Hmmm. Ik ben er al een tijdje uit, maar het riekt naar 2D vectormath: dus je hebt 2 vectoren en wanneer raken ze elkaar? Volgens mij kun je dit absoluut uitrekenen ipv door iteratie. Het is volgens mij niet eenvoudig (en dan is door proberen het een stuk eenvoudiger) omdat je op een gegeven moment uitkomt op het berekenen van lengtes van zijden van driehoeken die geen rechte hoek hebben, maar met een plaatje tekenen kom je er imho wel uit. Misschien dat een wiskundige vectorgeek hier meer mee kan

[MSalters]

Op woensdag 12 juni 2002 19:31 schreef Zentair het volgende:

[..]

een wortel is altijd positief, dus hoe kan sin(x) gelijk zijn aan sqrt(iets)?

Hoek tussen de 0 en pi, natuurlijk. Sowieso heb je een oneindig aantal oplossingen omdat sin(x)==sin(x+2pi) = -sin(x+pi), dus je moet je beperken.

Maar bij nader inzien is de vergelijking niet meer lineair maar kwadratisch; dat maakt direct vegen onmogelijk. Evengoed is het daarmee nog niet onmogelijk; je kunt sin(x)*sin(x)+cos(x)*cos(x) als vijfde vergelijking toevoegen, de eerste 4 vegen met sin(x) en cos(x) als separate variabelen en de resulterende uitdrukkingen voor sin(x) en cos(x) in X,Y en T invullen in de laatste vergelijking, waarmee je sin(x) en cos(x) hebt geelimineerd. En vanaf daar is het netjed schrijven.

[Verwijderd]

code:

Xk(t) = Xk(0) + sin(Ak) * Vk * T
Yk(t) = Yk(0) + cos(Ak) * Vk * T

Xb(t) = Xb(0) + sin(Ab) * Vb * T
Yb(t) = Yb(0) + cos(Ab) * Vb * T

Oplossen van raakpunt:
Xk(t) = Xb(t)
Yk(t) = Yb(t)

sin(Ak) = (Xb(0) - Xk(0) + sin(Ab) * Vb) / Vk
cos(Ak) = (Yb(0) - Yk(0) + cos(Ab) * Vb) / Vk

Vervolgens kun je die sin of cos in een van de bovenstaande vergelijkingen invullen en oplossen (indien mogelijk) naar T. Of zit ik er nu helemaal naast?