So right now my bullet emitter will shoot exactly at the player, but miss the player if the player is moving. I want to lead the target reliably. If you can't possibly hit the player then don't shoot, otherwise fire at where the player will be.
I said to myself "I'll use math, and I'll cheat." I constructed a scenario.
Bullet emitter at (ex,ey), target at (tx,ty). Not shown is the intercept point for the fired bullet, (ix,iy). Coordinate system uses screen coordinates, so the top left is 0,0 and positive Y goes down instead of up. For a given angle of movement theta, the X deflection is cosine(theta) and the Y deflection is sine(theta), with theta 0 pointing to the right.
So I tried to get Mathematica to do all the work.
LogicalExpand[
FullSimplify[
Reduce[
Eliminate[
{ix == ex + T * Cos[theta],
ix == tx + T * tv * Cos[ta],
iy == ey + T * Sin[theta],
iy == ty + T * tv * Sin[ta]},
{T}],
{theta, ix, iy},
GeneratedParameters -> (Subscript[k, #] &)]
]
]
I ended up with output in disjunctive normal form -- a bunch of either-or situations. Problem is, I got 28 different scenarios, many of them special cases where the target is not moving or is moving directly toward or away from the emitter. http://mspencer.net/PA_XNA/TargetLeading2.pdf
The plan is to interpret these as code for a branching tree of execution: some conditions will be tested to tell the difference between special cases, and some conditions will be go/no-go and will tell me if a firing solution even exists.
mspencer on
MEMBER OF THE PARANOIA GM GUILD
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
Can I reasonably expect that if I write a 2D platformer in this, it'll run on my antique low-end-for-2005 laptop? Or is that entirely dependent on how good I am at writing efficient code?
That seems excessively complicated. Given points T and E with object T moving at known velocity and bullets fired from E moving at a constant speed in a variable direction, you end up looking for theta such that the integrals meet.
However, it's a lot simpler than that, it forms a triangle TEI where the ratio of sides EI and TI are the ratio of the speeds of the bullet target respectively (since there is no acceleration) and angle ETI is known (as the direction of travel is known and fixed.
Now, to calculate the optimal intercept point, you require minimal deflection from a straight shot at your target so we will be calculating the minimum internal angle TEI which is given by the smallest possible length of side TI
Distance of any point k along line TI from E is given by the law of cosines: EI² = k² + ET² - 2k*ET*cos(ETI)
You are looking for the smallest k where: sqrt(k² + ET² - 2k*ET*cos(ETI)) == k * ratio
There are some restrictions on the result. k should be chosen as the smallest positive result. Only negative k indicates that there was a solution in the past but none in the future. Imaginary k indicates no solution.
The angle is trival to calculate given the intercept point.
Example
E is at 0,0
T is at 0,5
T is moving horizontally at 5 units/s therefore ETI = 90 degrees
We would expect the length of EI to be double that or 5.7735
Since it's a right triangle, 5² + 2.8867² = 5.7735²
edit: I suppose there's also the case where E, T and I are collinear and so don't actually form a triangle, however the in that case you always shoot directly at them if bullet speed + closing velocity is positive
Sir CarcassI have been shown the end of my worldRound Rock, TXRegistered Userregular
edited August 2010
Awesome OP. Almost makes me want to give XNA another try.
I messed with it a couple of years ago trying to make a single-player Wurm clone, but my head exploded when I started trying to learn about drawing a 3D landscape, specifically one that used square tiles and was deformable. Are there any good resources for doing that kind of stuff, preferably specifically for XNA? Or hell, some sort of library that does that stuff for me?
Sir Carcass on
0
Options
UnbrokenEvaHIGH ON THE WIREBUT I WON'T TRIP ITRegistered Userregular
edited August 2010
I could not have found this thread at a better time, having just deemed Unity3d unsuitable for my plans, and decided that the extra work involved in XNA is more than worthwhile considering the extra control/flexibility.
Starting tonight: a tile-based map editor! oooooooooooooooexciting.
Awesome OP. Almost makes me want to give XNA another try.
I messed with it a couple of years ago trying to make a single-player Wurm clone, but my head exploded when I started trying to learn about drawing a 3D landscape, specifically one that used square tiles and was deformable. Are there any good resources for doing that kind of stuff, preferably specifically for XNA? Or hell, some sort of library that does that stuff for me?
I have a book XNA 3.0 Game Programming Recipes: A Problem-Solution Approach by Riemer Grootjans with a chapter about something like that. This book assumes you already understand the basics and essentially discusses individual problems to solve and how you solve them. I don't think it covers deformation, but you could try modifying the terrain heightmap array dynamically and see if anything breaks. The author's web site is here: http://www.riemers.net/
Specifically two sections seem applicable to 3D terrain rendering:
2-10: Use a Quadtree to Hide Parts of a Grid That Are Not In Sight
2-11: Create a Real-Time Camera-Dependent Optimally Adapting Mesh (ROAM) Terrain
At the end of 2-10 the author talks about terrain being such a large subject he could fill an entire book with it.
mspencer on
MEMBER OF THE PARANOIA GM GUILD
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
0
Options
Sir CarcassI have been shown the end of my worldRound Rock, TXRegistered Userregular
That seems excessively complicated. Given points T and E with object T moving at known velocity and bullets fired from E moving at a constant speed in a variable direction, you end up looking for theta such that the integrals meet.
However, it's a lot simpler than that, it forms a triangle TEI where the ratio of sides EI and TI are the ratio of the speeds of the bullet target respectively (since there is no acceleration) and angle ETI is known (as the direction of travel is known and fixed.
Now, to calculate the optimal intercept point, you require minimal deflection from a straight shot at your target so we will be calculating the minimum internal angle TEI which is given by the smallest possible length of side TI
Distance of any point k along line TI from E is given by the law of cosines: EI² = k² + ET² - 2k*ET*cos(ETI)
You are looking for the smallest k where: sqrt(k² + ET² - 2k*ET*cos(ETI)) == k * ratio
There are some restrictions on the result. k should be chosen as the smallest positive result. Only negative k indicates that there was a solution in the past but none in the future. Imaginary k indicates no solution.
The angle is trival to calculate given the intercept point.
Example
E is at 0,0
T is at 0,5
T is moving horizontally at 5 units/s therefore ETI = 90 degrees
We would expect the length of EI to be double that or 5.7735
Since it's a right triangle, 5² + 2.8867² = 5.7735²
edit: I suppose there's also the case where E, T and I are collinear and so don't actually form a triangle, however the in that case you always shoot directly at them if bullet speed + closing velocity is positive
Law of cosines! I don't know if I ever learned that in school, but if I did I've since forgotten it.
I did initially try using geometry and trig, but all I could remember required use of right triangles. I had this construction where I took a tangent line to the target's movement vector and constructed a right triangle there. I used the ratio of the triangle's legs as the ratio of the speeds, but I couldn't figure out how to handle the case where the target is behind or in front of the 90-degree part of the right triangle. I ended up having to add or subtract the offset, and the offset didn't scale with the speeds.
It's so much easier when the triangle doesn't have to be a right triangle!
Thank you kindly. I'm still working through and absorbing what you wrote, charting it out with paper and pen.
mspencer on
MEMBER OF THE PARANOIA GM GUILD
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
I learned me some C# a while back and have always wanted to make a game. Now I just need to find some inspiration.
Also, I learned C# from the "Head First C#" book, which was really nice because the end project is to build a Space Invaders clone (they provide the sprites).
No problem. The law of cosines is the Pythagorean theorem generalized to all triangles, it's usually covered in school but most people forget it I find. That and the law of sines tend to be really useful for general geometry stuff (although I still had to look up the exact formula)
I could not have found this thread at a better time, having just deemed Unity3d unsuitable for my plans, and decided that the extra work involved in XNA is more than worthwhile considering the extra control/flexibility.
Starting tonight: a tile-based map editor! oooooooooooooooexciting.
Yeah I sat down with XNA last night and I was amazed at how simple it was to make a guy move around the screen.
Back in the day it took me a half a week to write something that good, but I did it in about 2 minutes.
bowen on
not a doctor, not a lawyer, examples I use may not be fully researched so don't take out of context plz, don't @ me
XNA is amazing. I have been playing around with it for awhile now, though I don't really have anything REAL to show. I'm still pretty much a novice to the whole thing, but I probably have some limited information for the real newbies if there are any questions. I intend to learn a lot from this topic as well.
I think I'm finally getting somewhere. Sorry Phyphor but I went back to trying to do it with straight trig and Mathematica. I feel like I'm closer. http://mspencer.net/PA_XNA/TargetLeading3.pdf
The second page of that document is in disjunctive normal form (like: A-and-B, or A-and-C-and-D, or A-and-C-and-E, or . . .) and it lists only nine scenarios. I've been studying them and so far they make sense.
The beginning of the expression (tx=0) is the first scenario, and then each time you see OR (huge letter V like symbol) c1 subset of Z (set of integers), that's a new scenario.
Scenario 1: if the target is on top of the cannon, fire in any direction except to the left. (Probably caused a divide by zero somewhere.)
Scenario 2: if the target is on the X axis (ty == 0) and is not moving, fire directly at it.
Scenario 3: if the target is on top of the cannon, fire to the left. (Weird duplicate of scenario 1.)
Scenarios 4 and 5: these cover most non-special-case scenarios and will be explained later. (once I figure out how they work and what each expression means.)
Scenario 6: if the target is headed toward the x-axis, timed just right so a bullet fired along the x-axis will reach the target, go ahead and fire directly along the x-axis. Must be a special case that avoids making another formula divide by zero.
Scenario 7: if the target is on the X axis and is not moving, fire directly at it. (Opposite of Scenario 2.)
Scenario 8: if the target is on the Y axis and is heading toward the X axis at just the right angle that the horizontal component of motion exactly matches a bullet's speed, fire directly along the X axis.
Scenario 9: if the target is on a collision course with the origin (flying directly at the emitter) then fire directly at the target. (Edit: on closer examination, I don't think this does what I think it does. theta is 2*arctan. Something is weird.)
I think I might be able to resume coding on that bullet hell game pretty soon!
mspencer on
MEMBER OF THE PARANOIA GM GUILD
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
I think so, but while reinventing the wheel is usually a bad thing, this time I'd like the experience of building code from Mathematica output. Thanks though -- I'll be sure and compare our code once I'm done.
mspencer on
MEMBER OF THE PARANOIA GM GUILD
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
So, I have the need to find if something is in line of sight in a 2D grid based system (the grid is basically passable terrain or unpassable). My initial thought for doing this was to find the equation of the line between the 2 points then checking it for every x and y value between the points, first checking x values, then y (but skipping any that have already been checked). Is this a silly way of doing things? Is there a better way?
So, I have the need to find if something is in line of sight in a 2D grid based system (the grid is basically passable terrain or unpassable). My initial thought for doing this was to find the equation of the line between the 2 points then checking it for every x and y value between the points, first checking x values, then y (but skipping any that have already been checked). Is this a silly way of doing things? Is there a better way?
That's probably how I'd do it. That's also how you'd probably do it in terms of 3d space too.
So, I have the need to find if something is in line of sight in a 2D grid based system (the grid is basically passable terrain or unpassable). My initial thought for doing this was to find the equation of the line between the 2 points then checking it for every x and y value between the points, first checking x values, then y (but skipping any that have already been checked). Is this a silly way of doing things? Is there a better way?
That's probably how I'd do it. That's also how you'd probably do it in terms of 3d space too.
There's a slightly better way to do that in XNA: Ray.Intersects()
mspencer on
MEMBER OF THE PARANOIA GM GUILD
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
Having been laoding information as both ContentPipeline serialised XML and my own free form effort parsed with LINQ I would say the LINQ method did not cause me to tweet offensive message at Shawn Hargreaves.
(Overall the ContentPipeline method is better but the fucking invisible hoops you have to jump through first!)
I think you have to go pretty far beyond "newbie XNA" before you run into Alistair Hutton's problems though. Please don't be discouraged from using XNA.
mspencer on
MEMBER OF THE PARANOIA GM GUILD
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
Posts
[ed] Oh, crap. It won't even install. Hmmmmm. That might be more of an issue.
This was the article I was thinking of. It's from a google cache, 'cause the guy's changed his site since he posted the article.
Robots Will Be Our Superiors (Blog)
http://michaelhermes.com
I said to myself "I'll use math, and I'll cheat." I constructed a scenario.
Bullet emitter at (ex,ey), target at (tx,ty). Not shown is the intercept point for the fired bullet, (ix,iy). Coordinate system uses screen coordinates, so the top left is 0,0 and positive Y goes down instead of up. For a given angle of movement theta, the X deflection is cosine(theta) and the Y deflection is sine(theta), with theta 0 pointing to the right.
So I tried to get Mathematica to do all the work.
LogicalExpand[ FullSimplify[ Reduce[ Eliminate[ {ix == ex + T * Cos[theta], ix == tx + T * tv * Cos[ta], iy == ey + T * Sin[theta], iy == ty + T * tv * Sin[ta]}, {T}], {theta, ix, iy}, GeneratedParameters -> (Subscript[k, #] &)] ] ]I ended up with output in disjunctive normal form -- a bunch of either-or situations. Problem is, I got 28 different scenarios, many of them special cases where the target is not moving or is moving directly toward or away from the emitter.
http://mspencer.net/PA_XNA/TargetLeading2.pdf
The plan is to interpret these as code for a branching tree of execution: some conditions will be tested to tell the difference between special cases, and some conditions will be go/no-go and will tell me if a firing solution even exists.
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK
QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
However, it's a lot simpler than that, it forms a triangle TEI where the ratio of sides EI and TI are the ratio of the speeds of the bullet target respectively (since there is no acceleration) and angle ETI is known (as the direction of travel is known and fixed.
Now, to calculate the optimal intercept point, you require minimal deflection from a straight shot at your target so we will be calculating the minimum internal angle TEI which is given by the smallest possible length of side TI
Distance of any point k along line TI from E is given by the law of cosines: EI² = k² + ET² - 2k*ET*cos(ETI)
You are looking for the smallest k where: sqrt(k² + ET² - 2k*ET*cos(ETI)) == k * ratio
Where ratio is speed of bullet / speed of ship
k² + ET² - 2k*ET*cos(ETI) == k² * ratio²
k²(1 - ratio²) -2k*ET*cos(ETI) + ET²
k = (2*ET*cos(ETI) +- sqrt(4*ET²*cos²(ETI) - 4ET² + 4ET²*ratio²)) / (2-2ratio²)
There are some restrictions on the result. k should be chosen as the smallest positive result. Only negative k indicates that there was a solution in the past but none in the future. Imaginary k indicates no solution.
The angle is trival to calculate given the intercept point.
Example
E is at 0,0
T is at 0,5
T is moving horizontally at 5 units/s therefore ETI = 90 degrees
Bullets move at 10 units/s
k²(1 - ratio²) -2k*ET*cos(ETI) + ET²
k²(1 - 4) -2k*5*0 + 25
-3k² + 25
Ratio is 2
k = 2.8867
We would expect the length of EI to be double that or 5.7735
Since it's a right triangle, 5² + 2.8867² = 5.7735²
edit: I suppose there's also the case where E, T and I are collinear and so don't actually form a triangle, however the in that case you always shoot directly at them if bullet speed + closing velocity is positive
I messed with it a couple of years ago trying to make a single-player Wurm clone, but my head exploded when I started trying to learn about drawing a 3D landscape, specifically one that used square tiles and was deformable. Are there any good resources for doing that kind of stuff, preferably specifically for XNA? Or hell, some sort of library that does that stuff for me?
Starting tonight: a tile-based map editor! oooooooooooooooexciting.
I have a book XNA 3.0 Game Programming Recipes: A Problem-Solution Approach by Riemer Grootjans with a chapter about something like that. This book assumes you already understand the basics and essentially discusses individual problems to solve and how you solve them. I don't think it covers deformation, but you could try modifying the terrain heightmap array dynamically and see if anything breaks. The author's web site is here: http://www.riemers.net/
Specifically two sections seem applicable to 3D terrain rendering:
2-10: Use a Quadtree to Hide Parts of a Grid That Are Not In Sight
2-11: Create a Real-Time Camera-Dependent Optimally Adapting Mesh (ROAM) Terrain
At the end of 2-10 the author talks about terrain being such a large subject he could fill an entire book with it.
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK
QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
Yeah, that's kinda the impression I got when I was doing my research. I'll look around some more.
Edit: Looking at his website, I actually remember following those tutorials. They were pretty awesome.
I did initially try using geometry and trig, but all I could remember required use of right triangles. I had this construction where I took a tangent line to the target's movement vector and constructed a right triangle there. I used the ratio of the triangle's legs as the ratio of the speeds, but I couldn't figure out how to handle the case where the target is behind or in front of the 90-degree part of the right triangle. I ended up having to add or subtract the offset, and the offset didn't scale with the speeds.
It's so much easier when the triangle doesn't have to be a right triangle!
Thank you kindly. I'm still working through and absorbing what you wrote, charting it out with paper and pen.
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK
QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
Also, I learned C# from the "Head First C#" book, which was really nice because the end project is to build a Space Invaders clone (they provide the sprites).
Yeah I sat down with XNA last night and I was amazed at how simple it was to make a guy move around the screen.
Back in the day it took me a half a week to write something that good, but I did it in about 2 minutes.
The second page of that document is in disjunctive normal form (like: A-and-B, or A-and-C-and-D, or A-and-C-and-E, or . . .) and it lists only nine scenarios. I've been studying them and so far they make sense.
The beginning of the expression (tx=0) is the first scenario, and then each time you see OR (huge letter V like symbol) c1 subset of Z (set of integers), that's a new scenario.
Scenario 2: if the target is on the X axis (ty == 0) and is not moving, fire directly at it.
Scenario 3: if the target is on top of the cannon, fire to the left. (Weird duplicate of scenario 1.)
Scenarios 4 and 5: these cover most non-special-case scenarios and will be explained later. (once I figure out how they work and what each expression means.)
Scenario 6: if the target is headed toward the x-axis, timed just right so a bullet fired along the x-axis will reach the target, go ahead and fire directly along the x-axis. Must be a special case that avoids making another formula divide by zero.
Scenario 7: if the target is on the X axis and is not moving, fire directly at it. (Opposite of Scenario 2.)
Scenario 8: if the target is on the Y axis and is heading toward the X axis at just the right angle that the horizontal component of motion exactly matches a bullet's speed, fire directly along the X axis.
Scenario 9: if the target is on a collision course with the origin (flying directly at the emitter) then fire directly at the target. (Edit: on closer examination, I don't think this does what I think it does. theta is 2*arctan. Something is weird.)
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK
QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK
QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
That's probably how I'd do it. That's also how you'd probably do it in terms of 3d space too.
http://cs.fit.edu/~wds/classes/cse5255/thesis/lineEqn/lineEqn.html
Use those.
Yeah, that's what I figured. I'm so glad my high school math is useful. Screw those other kids who said I'd never use it, now who's laughing!
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK
QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )
Don't worry, soon you will do something with the content pipeline that's not loading a texture and then the true horror will begin.
I made a game, it has penguins in it. It's pay what you like on Gumroad.
Currently Ebaying Nothing at all but I might do in the future.
Having been laoding information as both ContentPipeline serialised XML and my own free form effort parsed with LINQ I would say the LINQ method did not cause me to tweet offensive message at Shawn Hargreaves.
(Overall the ContentPipeline method is better but the fucking invisible hoops you have to jump through first!)
I made a game, it has penguins in it. It's pay what you like on Gumroad.
Currently Ebaying Nothing at all but I might do in the future.
XBL Michael Spencer || Wii 6007 6812 1605 7315 || PSN MichaelSpencerJr || Steam Michael_Spencer || Ham NOØK
QRZ || My last known GPS coordinates: FindU or APRS.fi (Car antenna feed line busted -- no ham radio for me X__X )