I've been fighting with this for way too long today.

Basically, I'm working on getting the AI ships in my game be able to lead their targets. It's trickier than I thought it was, but after finding some good references and a nice Wikipedia article I'm now able to get my AI to properly lead their targets. Pretty cool stuff! I'm doing a fairly simple constant bearing interception formula using the Law of Sines, and it's working well.

However, now I'm having a hard time knowing which way to add the leading angle, so my bot leads properly when the target is circling clockwise, but not counter-clockwise, or vice-versa.

I know the angle from the source to the target, I know the angle of the target relative to the source as well as relative to the origin, I can find just about anything out, I'm just having a hard time finding a consistent way of knowing if an object is circling another one clockwise or counter-clockwise.

My brain is fried from thinking about this all day, can anyone give me a clue?

I'm happy to post my source code here if people want to take a look at it, but this is more of a theory question than anything else.

Thanks!

--clint

Or maybe have 4 quadrants with the bot at the origin, then check what quadrant the target is in as well as its direction, to figure out which way it is orbiting?

Edit, even pseudo-math can have mistakes.

[This message has been edited by CheeseStorm (edited November 19, 2006).]

Here's something that might be useful. you can define a circle as having an equal ratio of distance between to focal points. It's actually in that wikipedia article; the point is that if you find the distance between the the target and the origin and the target and another stationary point, like the far edge of the map, then if the ship is moving and two consecutive points have the same distance ratio then you will know that he is doing a circle and you should be able to define that circle to judge where you should aim. You might want to use an arc generating equation based on those two points rather than checking every possible position to see if those two distances are equal though

[This message has been edited by Cohort X (edited November 19, 2006).]

heres some C++ code (mix of directx and my basic 2d engine) which will target a moving enemy ahead and then when you press the space bar it'll shoot a line which will hit the enemy.

/// // Author: Jonathan Warner // Date: 19th November 2006 /// #include "main.h" DartEngine::CDartEngine g_engine; int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nShowCmd) { g_engine.Init(hInstance, WinProcMain, "TestApp"); D3DXVECTOR2 enemyPos, enemyDir; D3DXVECTOR2 playerPos, playerDir; D3DXVECTOR2 bulletPos, bulletDir; D3DXVECTOR2 trackPos; float playerSpeed = 10.0f, enemySpeed = 20.0f, bulletSpeed = 100.0f; float playerSize = 5.0f, enemySize = 5.0f, bulletSize = 2.0f; enemyPos = D3DXVECTOR2(-100.0f, 0.0f); enemyDir = D3DXVECTOR2(0.707f, 0.707f); playerPos = D3DXVECTOR2(100.0f, 0.0f); playerDir = D3DXVECTOR2(1.0f, 0.0f); bulletPos = D3DXVECTOR2(0.0f, 0.0f); bulletDir = D3DXVECTOR2(0.0f, 0.0f); while (g_engine.Run()) { float dt = g_engine.getDeltaTime(); dt *= 10.0f; g_engine.drawText("DartEngine v0.1a"); enemyPos += enemyDir * (enemySpeed * dt); playerPos += playerDir * (playerSpeed * dt); bulletPos += bulletDir * (bulletSpeed * dt); if (enemyPos.x > 400.0f) enemyPos.x -= 800.0f; if (enemyPos.x < -400.0f) enemyPos.x += 800.0f; if (enemyPos.y > 300.0f) enemyPos.y -= 600.0f; if (enemyPos.y < -300.0f) enemyPos.y += 600.0f; if (playerPos.x > 400.0f) playerPos.x -= 800.0f; if (playerPos.x < -400.0f) playerPos.x += 800.0f; if (playerPos.y > 300.0f) playerPos.y -= 600.0f; if (playerPos.y < -300.0f) playerPos.y += 600.0f; if (bulletPos.x > 400.0f) bulletPos.x -= 800.0f; if (bulletPos.x < -400.0f) bulletPos.x += 800.0f; if (bulletPos.y > 300.0f) bulletPos.y -= 600.0f; if (bulletPos.y < -300.0f) bulletPos.y += 600.0f; g_engine.GraphicsToolkit().drawCircle(enemyPos, enemySize); g_engine.GraphicsToolkit().drawVector(enemyPos, enemyDir * 50.0f, 0xffff0000); g_engine.GraphicsToolkit().drawVector(enemyPos, enemyDir * enemySpeed * 10.0f); g_engine.GraphicsToolkit().drawCircle(playerPos, playerSize); g_engine.GraphicsToolkit().drawVector(playerPos, playerDir * 500.0f, 0xffff0000); g_engine.GraphicsToolkit().drawVector(playerPos, playerDir * playerSpeed * 10.0f); D3DXVECTOR2 vec = (enemyPos - playerPos); float length = D3DXVec2Length(&vec); float timeToHit = (length / bulletSpeed); trackPos = enemyPos + ((enemyDir * enemySpeed) * timeToHit); g_engine.GraphicsToolkit().drawCircle(trackPos, 10.0f); vec = trackPos - playerPos; D3DXVec2Normalize(&vec, &vec); if (isKey(VK_SPACE)) { bulletPos = playerPos; bulletDir = vec; D3DXVec2Normalize(&bulletDir, &bulletDir); } vec = bulletPos - enemyPos; float dist = D3DXVec2LengthSq(&vec); if (dist <= ((enemySize * enemySize) + (bulletSize * bulletSize))) { bulletPos = D3DXVECTOR2(0.0f, 0.0f); bulletDir = D3DXVECTOR2(0.0f, 0.0f); } g_engine.GraphicsToolkit().drawVector(bulletPos, bulletDir * 10.0f, 0xff00ff00); } return 0; } LRESULT CALLBACK WinProcMain(HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam) { switch(msg) { case WM_KEYDOWN: { switch(wParam) { case VK_ESCAPE: PostQuitMessage(0); break; } } break; case WM_CLOSE: case WM_DESTROY: { PostQuitMessage(0); } break; default: { return DefWindowProc( hWnd, msg, wParam, lParam ); } break; } return 0; }

Hope that helps, I have seen some slight misses, but I take that as floating point error, or possibly that it's like midnight and I've goto get up at 6am.. lol. Don't worry about what the graphics toolkit does or the init, just engine stuff. If you PM me with your MSN account I can email you the demo if you want.

------------------
www.auran.com

[This message has been edited by dartsman (edited November 19, 2006).]

Dartsman, that demo code is fantastic. I was busy doing everything in polar space (forces and angles), but I like the simplicity of your approach, and I think I should probably just do things that way. I'll have to add some checks in there for when there is no solution to the problem (the target is moving faster than the bullet can ever catch it), but by and large your way looks simpler, more understandable, and more maintainable. Thanks!

--clint

------------------
My projects page:
http://calinnegru.googlepages.com/projects

[This message has been edited by fearless (edited November 20, 2006).]

quote:

---

Originally posted by fearless:
If the ship movement has pathfinding you can use path nodes that the targeted ship hasn't yet reached as destination for targeting ship.

---

Good idea, but no -- it's targeting the player's ship, which is directed with keystrokes rather than AI path nodes.

Sorry, I gave short answers to Cheese and Cohort before -- I'll touch on them a little more.

Cheese -- I was thinking more about yours, and that's the direction that I was pursuing for most of the day on Saturday. The main trouble I ran into is when it crosses the origin, (...358, 359, 0, 1, 2...) things start to get weird. I think you're right-on with your ideas, the trouble is just figuring out all of the intricacies when converting between perspectives like that also (when the firing ship has a heading of 37 degrees, what defines "left", what defines "right", and how do you deal with the origin crossover issue that pops up in several places). It wound up being a lot of special cases and I just got in over my head.

Cohort: Using a delta-theta like that isn't a bad idea. If Dartsman's code doesn't work out, that will be a very good thing for me to try.

Thanks again for the help, all!

--clint

[This message has been edited by HanClinto (edited November 20, 2006).]

------------------
www.auran.com

Dartsman, your code is very nice for approximations, but as I was implementing it, I realized the error. The reason why the occasional shot is missing is not due to floating point error, but rather because your formula is only a rough approximation because it take into account that TimeToHit might not be the same for the extrapolated position. I drew a quick picture to illustrate:

It was working decently well, but messing with your math gave me some new insights into doing it the old way (using the Law of Sines to get the true extrapolated position rather than an estimate), and while I still notice it glitching from time to time, I was able to get it working well enough to make two teams of AI and watch them pummel each other to death. The game is getting to a fun and playable state now -- I should probably post an update in the Weekly Updates thread.

Anyways, here's your algorithm implemented in Torque Script:

function shipClass::getTargetInterceptHeadingDartsman( %this ) { %target = %this.target; if (!isObject(%target)) return ( %this.heading ); %dist = t2dVectorDistance( %this.getPosition(), %target.getPosition() ); %timeToHit = %dist / 120; // TODO: Get a non-magic-number bullet speed here %targetHeading = %target.getLinearVelocity(); %trackPos = t2dVectorAdd( %target.getPosition(), t2dVectorScale( %targetHeading, %timeToHit ) ); %interceptHeading = t2dAngleBetween( t2dVectorSub( %this.getPosition(), %trackPos ), "0 1" ); %interceptHeading = (%interceptHeading + 360) % 360; if ( %this.getPositionX() > %target.getPositionX() ) { return (360 - %interceptHeading); } else { return (%interceptHeading); } }

function shipClass::getTargetInterceptHeading( %this ) { %directHeading = %this.getTargetHeading(); %targetHeading = getWord( %this.target.getLinearVelocityPolar(), 0 ); %a = %this.getTargetHeadingShort(); %b = 180 - %a; %c = %targetHeading; if (%c > 180) %c = 360 - %c; %bowAngle = mDegToRad( %b - %c ); // Get the speed of the two ships %vTarget = getWord( %this.target.getLinearVelocityPolar(), 1 ); %vBullet = 120 + getWord ( %this.getLinearVelocityPolar(), 1 ); // TODO: Fix muzzel velocity to not be a hard-coded magic number. // Plug'n'chug if ((%vTarget <= 0.01) || (%vBullet == 0)) { return( %directHeading ); } else { %tmp = ( %vTarget / %vBullet ) * mSin( %bowAngle ); if (%tmp > 1) { // If %tmp is greater than one, then we're too slow, and no solution exists return ( %directHeading ); } %leadAngle = mRadToDeg(mAsin( %tmp ) ); if (%directHeading < 180) return (%directHeading - %leadAngle); else return (%directHeading + %leadAngle); } }

Just thought you might be curious to see how it all played out.

Thanks again for the help, all!

In Christ,
clint