Currently there are two anti-missile weapons in Gratuitous Space Battles. Point Defence Lasers and ECM beams. The point defence laser basically tracks incoming missiles and just zap them. They always hit (at the moment) and take one out. Of course, they can be overloaded,e specially by multiple-warhead missiles, but they are pretty cool. The other one (ECM beam) does exactly the same, but rather than destroy the missile it scrambles its guidance system and there is a cool wibbly wobbly effect as it veers everywhere. In the final game, the choice between them will probably be some sort of crew/power/cost/weight trade-off.

The thing they share though, is that they can ONLY target missiles that are aimed at their ship. You can’t have an ECM frigate at the spearhead of your fleet zapping all the incoming missiles to screen your capital ships from attack.

Clearly this sucks.

The solution isn’t trivial though. There are a LOT of ships in GSB and a LOT going on. if I’m to enable anti-missile weaponry to select from any missile on the map, that will involve a lot of processing. My mind is agog with quadtrees and other methods of limiting the amount of times each weapon has to do this:

for(each missile)
{
are_you_the_closest_one?
}

etc. It would normally be a trivial thing, but it’s something that isn’t in the game yet because it hasn’t really been necessary. The question is, do I write some big generic system that every piece of taregt selection will reference to find the nearest object? if so, that involves a fair bit of re-work, and it’s likely to be a several-cups-of-tea and a free morning sort of problem.

14 Responses to “Anti-Missile weapons”

  1. Folo4 says:

    can’t you make a simple missile alignment check or something?

    I mean, there’s only 2 sides.

  2. Keith LaMothe says:

    That is a tricky problem because logically you do have to check every potential target. I guess one way is to make a sort of binary tree of lists, where each list stores a pointer to all the objects in 1 1/64th of the map (or 1/128, etc, just 2 ^ max_depth) so for a given ship you could drastically pare down the number of objects you need to check for eligible targets. I threw together some example code here, using a list of subdivisions rather than a tree:

    http://pastebin.com/f164225f4

    Not my best coding, but hopefully gets the idea across.

    As for making a generic system for targetting, well, typically if you have two different pieces of code that do the same thing they will inevitably develop different behaviors. I can already see the future of bug lists where anti-missile weaponry isn’t targetting quite right ;)

  3. Karl Katzke says:

    Could you change the anti-missile laser to a ballistic weapon that shoots a fan of projectiles in front of the ship (think flak/shrapnel … burning magnesium mebbe?) and takes out a percentage of the smaller craft (fighters/missiles) in that area?

    Have missiles assigned to a ‘flight’ (or Salvo, or whatever you want to call it) that are grouped together by when they fire and from what ship. That reduces the number of objects you have to handle. When the ‘flight’, which is in a certain nebulous area defined by a bounding box (since I assume you’re already animating them individually), gets hit by a shrapnel weapon of X strength, it gets recorded in a message queue. Every time the missile flight gets processed as part of The Loop, it checks to see if it needs to reduce it’s strength. If it does, it destroys random missiles in the flight. The ballistic weapon also has a ‘spread’ on it like a shotgun that means it’s effectiveness drops to zero after X range from the origin point because the density of the projectiles is too low to effect enough hits on a missile.

    Switching to a ballistic anti-missile weapon decoupes the ‘hit’ and the missile-destroy functionality… which drastically reduces the amount of logic you have to do behind the animation work. The percentage basis is how a number of space-oriented paper RPGs run missile defense.

    The graphics could look REALLY cool too … imagine a ship emitting a fire-hose of sparkly particles in the direction of an incoming flight of missiles.

    Another ‘difference’ could be PenAids – aka Penetration Aids. Choosing the right option (anti-flak armor / boosted targeting head) will reduce the effect of the weapons but reduces the yield and/or flight time of the missile over a plain one.

  4. Karl Katzke says:

    Oh, and if missiles have enough time on their maneuvering jets left, they could do ‘evasive maneuvers’ — which would reduce their chance of dying. With lasers, additional animation work would be required on both ends. With flak, animation work only needs to happen on the missile end.

  5. Zeus says:

    Can there just be an option where the user can click a button, click on a nearby friendly ship and then just shoot down any missiles that attack it? Or maybe have it automatically shoot down all missiles attacking nearby friendlies with a starting priority on capital ships and moving down the line.

    In other words, instead of focusing on the missiles, focus on their targets.

    Is friendly nearby?
    Is friendly being attacked by missile?
    If yes, shoot missile.

  6. cliffski says:

    Those kind of behaviours are already in there in per-ship terms, although not per-weapon, which is another kettle of fish which I’m not sure I want opened (that would be worms I suppose).

    You can tell a ship to prefer to engage targets which are attacking a designated friendly craft, for example.

    Some sort of ECM-chaff style system is definitely an attractive idea. In terms of the coding of all this, it turns out that I’ve actually already got a method of making it pretty lightning fast as it is. I keep chopping an changing between different areas of the game so much that it’s hard to keep on top of it all :D

  7. MrNice says:

    This problem is as old as computer games… It’s been solved a million time. This is the same problem when you have 1000s objects in your world. Witch one do you draw?

    You need a quick way to find all the objects localize into a specific area.

    You should use a uniform solution that will solve your problems for drawing and for IA. So, you don’t have to write a specifi code for every little different problems.

  8. baz says:

    > other methods of limiting the amount of times each weapon has to do this:

    Just dont check every missle every cycle :-) its almost a feature, they have to search for targets.
    yeah, ok, thats a bit lame. I guess it would need a quad tree, or something…

  9. Keith LaMothe says:

    Ah, when people who actually know what they’re talking about chime in, I learn things ;)

    So is the “quad tree” idea somewhat similar to the binary tree thing I was talking about, except with each node having 4 children representing the upper-left, upper-right, lower-left, and lower-right quadrants of their area? And the leaf nodes would have a list of map objects within their area?

    The point is to be able to say “ok, this is a weapon with 400 range, so no point in considering stuff in quadrants where the closest point is 600+ away”, right?

    Thanks,
    Keith

  10. Nick says:

    I’m with MrNice. This is a long-solved problem in games programming. The problem domain is spatial partitioning – http://en.wikipedia.org/wiki/Spatial_partitioning . In game-specific terms it’s the same as broad-phase collision detection of any stripe.

    Quadtree or even just a plain grid will do as a spatial partitioning system, quadtrees have additional overhead but you’ll gain if your game can result in uneven distribution of entities around the game world (because the most densely populated regions will subdivide to suit). Grid works almost as well in many situations. Sweep and prune is another, even simpler, possibility for broad phase detection.

  11. Steven Barker says:

    My first though was like Zeus’s, that you could consider the target of the missiles to make it easier to pick out the ones that are good targets. For a while I couldn’t actually take the next logical step to see how it could work in code though, but I think I’ve finally arrived at an algorithm that would not require much work for picking targets.

    The core idea is that you can assume that each missile will move in an approximately straight line from it’s current position to it’s target’s location, so the path it will follow can be predicted in advance. Each missile can generate an estimated trajectory when it is launched and update it occasionally (not every game step, possibly just once ever few seconds) to address the fact that it’s target is moving too.

    Each point-defense turret would occasionally (again, only once every few seconds) examine the full list of enemy missiles (or some a fairly large subset from a quad tree or whatever) and find the ones who’s trajectories will take them within interception range using a simple point-to-line distance check. This does not need to be done very often, because the trajectories of the missiles don’t change much. With some clever code, you might only need to test newly fired missiles and ones that were barely out of range when checked before. There are other neat things you could do here too like calculate the times the missile will be in range so the turret can ignore the missile the rest of the time.

    When the turret is ready to shoot, it can quickly look at its list of missile trajectories and pick out the best target (the one closest to it, or closest to reaching its own target, or the one that will go out of range soonest, or whatever).

  12. What about just shooting a missile – potentially any missile – within range? It doesn’t discriminate; it just blasts. That way, an ECM screen ship at the head of your fleet could be a liability as well – it could potentially get your missiles as well. If you wanted to limit it to only attacking enemy missiles, it still wouldn’t be an overwhelming advantage – besides, even a missile that isn’t guided towards one of your ships could still be a threat.

  13. cliffski says:

    That’s what I ended up doing, and I’ve done some tests of sticking counter-missile frigates ahead of the fleet and it both works, and looks pretty neat :D

  14. […] Despite a fairly extensive pre-release marketing campaign which included gameplay videos and blog posts discussing the development¬†which had me excited to play the game, and despite having purchased 3 […]