|
Post by captinjoehenry on Oct 12, 2016 1:07:37 GMT
How about a swarm approach? One - or a few - missiles use a somewhat more sophisticated intercept algorithm. Possibly, depending on salvo size, you seperate the salvo into subswarms, each guided by one missile, each swarm using a different - or differently parameterized - algorithm. All other missiles in the (sub-)swarm do only what is necessary to maintain station relative to their neighbors, possibly with the station distance as a function of target distance. Just aligning on two vectors should take very little computing power. Thus, you have your salvo-as-one-big-missile approach without significant loss in precision. Switchover should be implemented, of course, in case the swarm leader is incapacitated. I think that's a solid approach, and is one of the solutions I'd be leaning towards, personally. In particular, this paper -- which I've only skimmed so far -- explains a swarming algorithm approach that's near-linear, where the polynomial nature of the attractive/repulsive force calculations per-agent are mitigated by limiting each missile's search space through some implementation of nearest-neighbor search. The paper also has the benefit of showing that the clustering can be done in a massively parallel fashion with GPU acceleration, which means that, if necessary, very large numbers of swarming missiles' AI could be handled...at the cost of increased code complexity and impact to maintainability. I doubt the trade-off would be worth it, particularly given the latency of moving data between main memory and the GPU every physics tick, but it shows that it's possible. I'd have to do an actual computational analysis to determine the actual difference in computation time between per-missile optimal guidance and swarming, but with a low number of neighbors considered -- two is probably enough to avoid collisions -- combined with optimizations to avoid recalculating neighbors for every missile every tick...I think you could see a reduction in computational load of between 50% and 75% fairly easily. That's a SWAG, and I don't guarantee it, but at that point it's an N=3 potential fields problem, which is basically just "addition" with some control logic around it. Edit: I re-read this and realize I went a bit into left field. I'm happy to answer any questions folks may have! I have a bit of a passion for AI and I don't get to do it in my day job, so it'd seriously be my pleasure. Oh man that is so awesome and I wish I knew half of what you are talking about! I'm a video game programming student in college and everything you have been talking about is fascinating. Something you might really be interested in is the Modern Warfare mod for World In Conflict. It adds fully realistic missiles that can be fire or forget. Use lock on after launch. Real guidance systems and everything else! Here are some links to some of the articles for this glourious mod: www.moddb.com/mods/wicmw/features/flint-lead-pursuit-guidance-principleswww.moddb.com/mods/wicmw/news/progress-update-september-2011www.moddb.com/mods/wicmw/tutorials/wic-modding-tutorial-leading-a-moving-target-in-pythonwww.moddb.com/mods/wicmw/features/qa-session-regarding-aegis-like-air-defense-and-futurewww.moddb.com/mods/wicmw/articles
|
|
|
Post by nivik on Oct 12, 2016 4:31:28 GMT
I'd have to do an actual computational analysis to determine the actual difference in computation time between per-missile optimal guidance and swarming, but with a low number of neighbors considered -- two is probably enough to avoid collisions -- combined with optimizations to avoid recalculating neighbors for every missile every tick...I think you could see a reduction in computational load of between 50% and 75% fairly easily. That's a SWAG, and I don't guarantee it, but at that point it's an N=3 potential fields problem, which is basically just "addition" with some control logic around it. Edit: I re-read this and realize I went a bit into left field. I'm happy to answer any questions folks may have! I have a bit of a passion for AI and I don't get to do it in my day job, so it'd seriously be my pleasure. Collisions shouldn't be much of a problem in any case, as long as missiles don't trigger each other's warheads. Collisions would happen at very low relative velocities and - worst case - would throw the missiles off course. True, but -- in my opinion -- you'd want to maintain some level of dispersion. With area warheads like nuclear and fragmentation, it enhances coverage and likelihood of knocking out something important. With point effect weapons like KKVs and EFPs, it increases likelihood of an effective hit.
|
|
|
Post by nivik on Oct 12, 2016 4:39:35 GMT
I think that's a solid approach, and is one of the solutions I'd be leaning towards, personally. In particular, this paper -- which I've only skimmed so far -- explains a swarming algorithm approach that's near-linear, where the polynomial nature of the attractive/repulsive force calculations per-agent are mitigated by limiting each missile's search space through some implementation of nearest-neighbor search. The paper also has the benefit of showing that the clustering can be done in a massively parallel fashion with GPU acceleration, which means that, if necessary, very large numbers of swarming missiles' AI could be handled...at the cost of increased code complexity and impact to maintainability. I doubt the trade-off would be worth it, particularly given the latency of moving data between main memory and the GPU every physics tick, but it shows that it's possible. I'd have to do an actual computational analysis to determine the actual difference in computation time between per-missile optimal guidance and swarming, but with a low number of neighbors considered -- two is probably enough to avoid collisions -- combined with optimizations to avoid recalculating neighbors for every missile every tick...I think you could see a reduction in computational load of between 50% and 75% fairly easily. That's a SWAG, and I don't guarantee it, but at that point it's an N=3 potential fields problem, which is basically just "addition" with some control logic around it. Edit: I re-read this and realize I went a bit into left field. I'm happy to answer any questions folks may have! I have a bit of a passion for AI and I don't get to do it in my day job, so it'd seriously be my pleasure. Oh man that is so awesome and I wish I knew half of what you are talking about! I'm a video game programming student in college and everything you have been talking about is fascinating. Something you might really be interested in is the Modern Warfare mod for World In Conflict. It adds fully realistic missiles that can be fire or forget. Use lock on after launch. Real guidance systems and everything else! Here are some links to some of the articles for this glourious mod: www.moddb.com/mods/wicmw/features/flint-lead-pursuit-guidance-principleswww.moddb.com/mods/wicmw/news/progress-update-september-2011www.moddb.com/mods/wicmw/tutorials/wic-modding-tutorial-leading-a-moving-target-in-pythonwww.moddb.com/mods/wicmw/features/qa-session-regarding-aegis-like-air-defense-and-futurewww.moddb.com/mods/wicmw/articlesI need to check out that mod. I'm a big fan of that mod's youtube video which demonstrates the various guidance laws and how effective they are. :3 Yeah, my credentials are Master of Science in Computer Science (Artificial Intelligence Concentration). The main resource I recommend if you're interested in this sort of thing is The Algorithm Design Manual (Skiena). That will give you a fundamental understanding of a large number of well-known algorithms and their applications. It was recommended to me by a Google interviewer, and is written in a way that's pretty approachable. I also recommend checking out Google Scholar and just typing in stuff you're interested in. Also, never discount the value of the games you play: I got a grad assistantship with the skills I picked up creating player-hunting killbots in Garry's Mod.
|
|
|
Post by captinjoehenry on Oct 12, 2016 11:52:35 GMT
I need to check out that mod. I'm a big fan of that mod's youtube video which demonstrates the various guidance laws and how effective they are. :3 Yeah, my credentials are Master of Science in Computer Science (Artificial Intelligence Concentration). The main resource I recommend if you're interested in this sort of thing is The Algorithm Design Manual (Skiena). That will give you a fundamental understanding of a large number of well-known algorithms and their applications. It was recommended to me by a Google interviewer, and is written in a way that's pretty approachable. I also recommend checking out Google Scholar and just typing in stuff you're interested in. Also, never discount the value of the games you play: I got a grad assistantship with the skills I picked up creating player-hunting killbots in Garry's Mod. Well I am more than happy to hear you are interested in that mod! World in Conflict is a really great real time strategy game that while it's getting on in the years it still is the only RTS that I actually cared about the story of the campaign and the game mechanic for money is really neat along with the class system. So in the game everyone has the same amount of money that builds up to the max amount over time at the same rate no matter what. The more you have the slower it gets though. Then there are four classes in the game. Armor, Infantry, Support, and airpower. Each one has access to units unique to it and they need to work together in order to win as they all have their own weaknesses and strengths.
|
|
|
Post by nivik on Oct 12, 2016 15:22:02 GMT
I need to check out that mod. I'm a big fan of that mod's youtube video which demonstrates the various guidance laws and how effective they are. :3 Yeah, my credentials are Master of Science in Computer Science (Artificial Intelligence Concentration). The main resource I recommend if you're interested in this sort of thing is The Algorithm Design Manual (Skiena). That will give you a fundamental understanding of a large number of well-known algorithms and their applications. It was recommended to me by a Google interviewer, and is written in a way that's pretty approachable. I also recommend checking out Google Scholar and just typing in stuff you're interested in. Also, never discount the value of the games you play: I got a grad assistantship with the skills I picked up creating player-hunting killbots in Garry's Mod. Well I am more than happy to hear you are interested in that mod! World in Conflict is a really great real time strategy game that while it's getting on in the years it still is the only RTS that I actually cared about the story of the campaign and the game mechanic for money is really neat along with the class system. So in the game everyone has the same amount of money that builds up to the max amount over time at the same rate no matter what. The more you have the slower it gets though. Then there are four classes in the game. Armor, Infantry, Support, and airpower. Each one has access to units unique to it and they need to work together in order to win as they all have their own weaknesses and strengths. Yeah, I recall it being fun, but I think it's a game I actually originally bought on disk, which is almost certainly lost to the aether by now. :3 I might have to give it another look.
|
|
|
Post by captinjoehenry on Oct 12, 2016 15:27:09 GMT
|
|
|
Post by beatle on Oct 12, 2016 16:53:13 GMT
I had to make an account just to reply! GOG is more than trustworthy and I can't recommend them enough! I buy games from them instead Steam whenever they have it available. Their main distinguishing features are lack of DRM or always online abominations, supporting old titles and fair regional pricing.
|
|
|
Post by captinjoehenry on Oct 12, 2016 16:58:16 GMT
I had to make an account just to reply! GOG is more than trustworthy and I can't recommend them enough! I buy games from them instead Steam whenever they have it available. Their main distinguishing features are lack of DRM or always online abominations, supporting old titles and fair regional pricing. Ok cool! As I said it looks good and not having DRM is pretty great. I just haven't had any experence with them before so I gave a word of caution. Also welcome to the forum! And in that case definitely go and get it! It is a great game and the modern warfare mod for it is one of the best mods out there for any game and I simply adore it!
|
|
|
Post by beatle on Oct 13, 2016 15:12:39 GMT
Also welcome to the forum! Thank you very much! On the issue of missile guidance, this is something very interesting to me as I believe the addition of a feature allowing to write control scripts for missiles would be the single best way to improve the game even further. Possibly even to have a generic programmable control module that can be added to other systems as well, like turreted guns so that each could act as a independent CIWS turret. (I am not entirely sure as I haven't specifically tested for this yet, but it seams to me that now the whole ship will concentrate fire from all it's guns to a single target at a time, making it very inefficient against missile swarms.) A simple API exposing basic control inputs and list of target tracks and other service info coupled with, say, embedded LUA interpretator would do wonders. Imagine the flood of specialized attack and defense strategies, now impossible, that would create an arms race in this community! The hilarious unexpected side effects when one forgets to take into account the occlusion of target by friendly objects in a script controlling CIWS turret firing at missiles that zip by among one's own fleet! The possibilities are endless! Also, I believe that for many people the most engaging aspect of the game is creation of custom modules, ships and fleets and, in absence of a multiplayer option, exchanging these custom setups with other people is an important source of enjoyment. In this situation, the ability to implement one's vision of the synergies between created systems and strategies of their use in control scripts instead of manual control would help greatly with making sure that other players would receive interesting challenge from exchanged user designed ships that the generic AI would not know how to control well. Ability to have control over specific actions of enemy's ships of their modules in sandbox mode would also help greatly with testing out new designs in more controlled and repeatable way. The only downside I can think of is the very real possibility that I might loose my job because of absenteeism in the case that such feature would be implemented in the game. BTW, to the author, this game is simply amazing, I have dreamt of something like that for a long time. Thank you for bringing this to reality!
|
|
|
Post by captinjoehenry on Oct 13, 2016 15:20:02 GMT
Ah I definitely agree it would be amazing to be able to implement our own code and logic for the missiles but considering the fact that I routinely launch waves of a 100-200 missiles (I would launch more but it lags too much with just that many!) it is important to consider the performance of the missile guidance script as if you have one of them running for 100+ missiles it can very easily slow a game to an even slower crawl than just having that many missiles does already!
|
|
|
Post by beatle on Oct 13, 2016 16:21:43 GMT
Ah I definitely agree it would be amazing to be able to implement our own code and logic for the missiles but considering the fact that I routinely launch waves of a 100-200 missiles (I would launch more but it lags too much with just that many!) it is important to consider the performance of the missile guidance script as if you have one of them running for 100+ missiles it can very easily slow a game to an even slower crawl than just having that many missiles does already! For one if missiles behaved a little more intelligently maybe we would need less of them. I can't test it at this time, but if the game is single threaded now, maybe running custom user scripts on other cores would be a low hanging optimization target.
|
|
foof
New Member
Posts: 31
|
Post by foof on Oct 14, 2016 15:10:53 GMT
Ah I definitely agree it would be amazing to be able to implement our own code and logic for the missiles but considering the fact that I routinely launch waves of a 100-200 missiles (I would launch more but it lags too much with just that many!) it is important to consider the performance of the missile guidance script as if you have one of them running for 100+ missiles it can very easily slow a game to an even slower crawl than just having that many missiles does already! One way to reduce the needed computing power is to use your guidance algorithm only for a few missiles/drones and implement a flocking or shoaling/schooling algorithm for the rest. These algorithms are very simple and have the additonal bonus of build in collision avoidance and anti-predator(flak, laser, CIWS) behaviour.
That will work fine midcourse however I am not sure how the performance will be in the terminal flight phase.
Edit: I just read that normalitybytes recommended the same approach. Well if you get two independent opinions that come to the same conclusion...
|
|
|
Post by nivik on Oct 14, 2016 21:34:26 GMT
Ah I definitely agree it would be amazing to be able to implement our own code and logic for the missiles but considering the fact that I routinely launch waves of a 100-200 missiles (I would launch more but it lags too much with just that many!) it is important to consider the performance of the missile guidance script as if you have one of them running for 100+ missiles it can very easily slow a game to an even slower crawl than just having that many missiles does already! One way to reduce the needed computing power is to use your guidance algorithm only for a few missiles/drones and implement a flocking or shoaling/schooling algorithm for the rest. These algorithms are very simple and have the additonal bonus of build in collision avoidance and anti-predator(flak, laser, CIWS) behaviour.
That will work fine midcourse however I am not sure how the performance will be in the terminal flight phase.
Edit: I just read that normalitybytes recommended the same approach. Well if you get two independent opinions that come to the same conclusion...
I've also proposed this approach and then gone into some small detail on how it might work. My graduate thesis and work as a grad assistant also involved multiple robots/agents working together to most effectively apply an effect to an area while minimizing waste, overlap, and collisions. Multi-robot collaboration is sorta my thing. I haven't touched it in a few years, but that's my background. Not that I'm trying to beat anyone over the head with my credentials or anything. :3 I just want to stress that if done properly, this is probably one of the best balances between algorithmic performance, ease of implementation, and effectiveness of results. I'm considering working on an example implementation this weekend. Not sure if I want to do a pure demo with more realistic physics modeling in NetLogo or try to implement it in Lua so I can make use of it in From the Depths.
|
|
|
Post by captinjoehenry on Oct 14, 2016 21:45:14 GMT
One way to reduce the needed computing power is to use your guidance algorithm only for a few missiles/drones and implement a flocking or shoaling/schooling algorithm for the rest. These algorithms are very simple and have the additonal bonus of build in collision avoidance and anti-predator(flak, laser, CIWS) behaviour.
That will work fine midcourse however I am not sure how the performance will be in the terminal flight phase.
Edit: I just read that normalitybytes recommended the same approach. Well if you get two independent opinions that come to the same conclusion...
I've also proposed this approach and then gone into some small detail on how it might work. My graduate thesis and work as a grad assistant also involved multiple robots/agents working together to most effectively apply an effect to an area while minimizing waste, overlap, and collisions. Multi-robot collaboration is sorta my thing. I haven't touched it in a few years, but that's my background. Not that I'm trying to beat anyone over the head with my credentials or anything. :3 I just want to stress that if done properly, this is probably one of the best balances between algorithmic performance, ease of implementation, and effectiveness of results. I'm considering working on an example implementation this weekend. Not sure if I want to do a pure demo with more realistic physics modeling in NetLogo or try to implement it in Lua so I can make use of it in From the Depths. Well I would recommend you implement it in lua so you can have a real game example of 100+ missiles performing smartly. Another thing to go for is doing it in C++ as CoaDE is in C++ so if you can do most of the work on it the more likely we can all get smart missiles!
|
|
|
Post by RA2lover on Oct 14, 2016 22:08:22 GMT
...
|
|