23 replies to this topic

[kryotech]

So I have some code here that is meant to find the ideal position and orientation relative to a target ship for attacking it. Here's the code:

var thisShip : GameObject;
static var hasPath : boolean=false;
var enemyTarget : GameObject;
var empty : GameObject;

function Update () {
	if (hasPath==false){
		var positions : Vector3[]=new Vector3[6*3*6*6*6*6*6];
		var orientation : Vector3[]=new Vector3[6*3*6*6*6*6*6];
		var enemyDamage : int[]=new int[3*6*6*6*6*6*6];
		var damageTaken : int[]=new int[3*6*6*6*6*6*6];
		var expectedGain : int[]=new int[3*6*6*6*6*6*6];
		var counter : int=0;
		for (var i : int=0; i<6; i++){
			for (var e : int=0; e<6; e++){
				for (var u : int=0; u<6; u++){
					for (var n : int=0; n<3; n++){
						for (var t : int=0; t<6; t++){
							for (var m : int=0; m<6; m++){
								for (var q : int=0; q<6; q++){
									positions[counter]=findPosition(i*60, e*60, u*60, n*100);
									orientation[counter]=Vector3(t*60, m*60, q*60);
									enemyDamage[counter]=findDamage(enemyTarget, thisShip, positions[counter], orientation[counter], "attacker");
									damageTaken[counter]=findDamage(thisShip, enemyTarget, positions[counter], orientation[counter], "defender");
									expectedGain[counter]=calcGains(enemyDamage[counter], damageTaken[counter]);
									counter++;
									an=i;
								}
							}
						}
					}
				}
			}
		}
		var dec : int=1;
		for (i=0; i<expectedGain.length; i++){
			if (expectedGain[i]>expectedGain[dec]){
				dec=i;
			}
		}
		hasPath=true;
	}

	if (hasPath==true){
		GetComponent("ship guidance").positioning=positions[dec];
	}
}

function findPosition(xangle : int, yangle : int, zangle : int, d : int){
	var anobject : GameObject=Instantiate(empty, enemyTarget.transform.position, Quaternion.identity);
	anobject.transform.rotation.eulerAngles.x=xangle;
	anobject.transform.rotation.eulerAngles.y=yangle;
	anobject.transform.rotation.eulerAngles.z=zangle;
	anobject.transform.Translate(anobject.transform.forward*d);
	var thepos : Vector3=anobject.transform.position;
	Destroy(anobject);
	return thepos;
}

// this code finds the damage that a ship will take from a resulting position
function findDamage(targetCraft : GameObject, attackingCraft : GameObject, positioning : Vector3, rotating : Vector3, dataType : String){
	var totalDamage : int=0;
	var initialObject : GameObject=Instantiate(empty, attackingCraft.transform.position, attackingCraft.transform.rotation);
	if (dataType=="attacker"){
		// there needs to be a way to move a 'ghosted' object around. How this will be done is a good question.
		//this method should get it to work
		initialObject.transform.position=positioning;
		var totalWeps : Vector3[]=new Vector3[attackingCraft.GetComponent("attributes").weapons.length];
		for (var i : int=0; i<attackingCraft.GetComponent("attributes").weapons.length; i++){
			var dist : int=Vector3.Distance(attackingCraft.transform.position, attackingCraft.GetComponent("attributes").weaponsPosition[i]);
			var dir : Vector3=attackingCraft.transform.position-attackingCraft.GetComponent("attributes").weaoponsPosition[i];
			dir=attackingCraft.transform.InverseTransformPoint(dir);
			var originalRot : Vector3=initialObject.transform.rotation.eulerAngles;
			initialObject.transform.rotation.eulerAngles=rotating;
			dir=attackingCraft.transform.TransformPoint(dir);
			var pos : Vector3=dist*dir;
			totalWeps[i]=pos;
		}
		for (i=0; i<attackingCraft.GetComponent("attributes").weapons.length; i++){
			for (var n : int=0; n<targetCraft.GetComponent("attributes").partsListPosition.length; n++){
				if (Physics.Linecast(totalWeps[i], targetCraft.GetComponent("attributes").partsListPosition[n])==false){
					if (attackingCraft.GetComponent("attributes").weaponsDamage[i]>=targetCraft.GetComponent("attributes").partsListHealth[n]+targetCraft.GetComponent("attributes").partsListArmor[n]){
						totalDamage+=targetCraft.GetComponent("attributes").partsListExplosive[n];
					}
					if (attackingCraft.GetComponent("attributes").weaponsDamage[i]<targetCraft.GetComponent("attributes").partsListHealth[n]+targetCraft.GetComponent("attributes").partsListArmor[n]){
						totalDamage-=targetCraft.GetComponent("attributes").partsListArmor[n];
						totalDamage+=attackingCraft.GetComponent("attributes").weaponsDamage[i];
					}
				}
			}	
		}
		Destroy(initialObject);
		return totalDamage;
	}
	if (dataType=="defender"){
		initialObject.transform.position=positioning;
		initialObject.transform.rotation.eulerAngles=rotating;
		for (i=0; i<targetCraft.GetComponent("attributes").weapons.length; i++){
			for (n=0; n<(attackingCraft.GetComponent("attributes").bow/2)/10; n++){
				if (Physics.Linecast(targetCraft.GetComponent("attributes").weaponsPosition[i], (initialObject.transform.position+(initialObject.transform.forward*n*10)))==false){
					totalDamage+=targetCraft.GetComponent("attributes").weaponsDamage[i];
				}
			}
		}
		Destroy(initialObject);
		return totalDamage;
	}
}

function calcGains(damageDealed : int, damageTaken : int){
	//let's toss in a calcRisk function some time from now
	var totalGain : int=damageDealed-damageTaken;
	return totalGain;
}

All those nested loops cycle through angles and distances for different positions and store data for each position/orientation set. The findPosition function simply finds the position from a distance from an orientation from the target ship. Then the calcDamage function finds how much damage is dealed to the enemy ship and how much damage is taken. The thing is that this function involves the use of instantiating objects. These objects should be deleted upon completion of the program, but instead, Unity keeps on drawing them, and the position data is not delivered to the ship guidance system. Anyone have any idea hat is causing this? I've even tried separating the loops into separate scripts, and even that yields the same result. Thanks for any assistance you can render (in advance)!

[Nanoha]

Is this an AI question or a Unity question? Does your solution work? I couldn't quite work out whats going on, some more info on your game would be helpful. Is it 2d/3d, what affects damage. Can the ideal position/orientation be anything or does it have a limit. Can you accept non-optimal solutions?

[kryotech]

I suppose this is an AI question (mainly a what am I doing wrong question, but not limited to that), and no, my solution simply makes a seemingly inifinte amount of empty game objects (as points I believe), so I just end the program after five minutes or so. It doesn't come up with a position/orientation while running. Damage is basically a function of the damage a weapon can deal (which is just a number arbitrarily assigned by me) minus the armor of the part (another arbitrary number). If this value exceeds the health value of the part, the part explodes, which has a seperate damage value (this explosive value becomes the damage). The game is also 3d, and the ideal position/orientation can be anything. However, the problem lies here that the code does not come up with an ideal position/orientation and simply continues to instantiate empty game objects. By non-optimal, I assume you mean below standards? There really is no standard, just whichever one has the best expected value (calculated via calcGains function).

Essentially, each loop is for a euler angle, with one loop for distance. There are two sets of euler angle loops, as the one is for positioning from the target ship (ie; think of it as casting a line from a ship in different directions to get a position at a certain distance) and the other set is orientations for this ship. Once it finds the best position/orientation from the list, it proceeds to update the ship's guidance component (which for some reason does not happen).

The game is essentially a space combat sim (the way I see it at least), and involves the player controling a ship (can be selected from various classes). It's got more to it, but essentially, I'm just trying to build a system that can pick a point/orientation that is best for attacking the player.

I hope this helps you to understand my code.

[i_luv_cplusplus]

var dist : int=Vector3.Distance(attackingCraft.transform.position, attackingCraft.GetComponent("attributes").weaponsPosition[i]);
var dir : Vector3=attackingCraft.transform.position-attackingCraft.GetComponent("attributes").weaoponsPosition[i];





possible typo here?

[kryotech]

Yes, that's definitely a typo, I'll give it another look, with the typo fixed....

[kryotech]

No change in the result with the typo fixed, it simply continues to instantiate many more empty gameObjects without any returns being given. Any other possibilities?

[kryotech]

I've isolated the problem to be within the calcDamage function. Looks like I need a new algorithm. If anyone wants to add their suggestions or something, feel free to do so.

[ApochPiQ]

How good is your calculus?

The typical approach to this is to formulate a multivariate function that accepts various angles as inputs and produces a scoring value, perhaps on the interval [0,1]. You then find the zeroes of the first-order derivative of the function to find local minima and maxima, which represent optimal solutions to the problem. There will be a number of constants and various coefficients which must be fed in beforehand; these you can leave abstract initially and just fill in the blanks in the differentiated version later once you work it out on paper.

Ideally, you could do this as a vector equation and eliminate Euler angles altogether, but that changes the nature of the mathematics somewhat. Depends on whether your trig or your linear algebra is stronger

The best approach though is probably to toss optimal solutions to the wind and just do some heuristics to guess at a good attack angle. Real pilots don't sit down with a calculator and sort out the perfect angle of attack and such before entering a dogfight; they rely on instinct and rapid reactions to dynamic situations. All the math in the world won't save your ass if you're busy computing while the other guy loops in behind your six and drops a missile into your tailpipe.

[kryotech]

I have managed to teach myself calculus actually (I can derive and integrate, I haven't really tried multi-variate functions, but hey, I'll give it a shot ). My trig and linear algebra are probably better though, so I might want to look into the vector equation.....although I'm not entirely sure I follow.

I see what you mean by the heuristics though, and that does seem like it would work. I'll give all of these a look I guess, and look at multi-variate derivation.....

[kryotech]

Quick questions: does raycasting a lot slow down/possibly freeze a game program?

[ApochPiQ]

Define "a lot."


(But yes, if you're casting, say, several million rays per frame, you're gonna get crap performance.)

[kryotech]

Well, it's about 279,936 rays per frame, if my calculations are correct, with other stuff goin' on as well.

Is there an alternative to raycasting? I simply need to see if a weapon has a line-of-sight on a target....

[ApochPiQ]

Line of sight meaning what, exactly? Nothing obstructs it?

If that's the case, then raycasting is indeed the correct solution, and from the sounds of it, you are indeed trying to do way too many raycasts per frame. Generally, there are better ways to approximate visibility of subcomponents of a large object for guessing if you can hit them with a weapon. There's also a lot of easy early-out checks you can do, e.g. test if you're on the same side of the object as the target, for instance, which will eliminate the need to cast a ray all the way through the object.

That said, it's also fairly standard to only cast rays from the current, actual position of a weapon versus enumerating every possible angle, as it seems like you might be trying to do.


Can you give us a more detailed idea of what you want your AI to do, exactly? I can probably suggest some heuristic approaches that'll get you a great result for several orders of magnitude less computation...

[kryotech]

The function is essentially trying to compute the damage a ship can deal on an enemy ship (now streamlined much more to be simply a position). In order to do so, it goes through every weapon on board the attacking ship, and sees if it has a clear line-of-sight on the position. If it does, it adds it's damage count to the total damage. If not, it continues on to the next weapon. This is done for every loop you see in the beginning of the program to see what position (at a certain distance) and orientation (of the attacking ship, and for the direction from the target ship). <BR><BR>My only issue so far is the line-of-sight issue, as you can see. I'm very close to cracking this program if only I could find a better line-of-sight function. I tried getting the gun turret to look at the relative target position (I found a way to get the target ship's position relative to the attacking ship when the angle/position of attack is being calculated. This works for sure), and see if it's angles are greater than a particular number, but that doesn't really work either. <BR><BR>The same side tests seem to have promise, but any suggestions you can give would be helpful.

[IADaveMark]

279,936 rays per frame

You're doing it wrong.

[ApochPiQ]

OK, crash course in AI for 3D space combat games

(If you're interested in my credentials for this, I did a lot of AI work for the X series of games by Egosoft, including the foundational AI for the upcoming X: Rebirth. I have plenty of experience here and I can definitely assure you that I'm speaking from harsh experience in many of these areas. Now, that said, let's get to it!)

Important Principles
There are a few key things to keep in mind when designing any AI, but especially a 6-degree-of-freedom system like you get in space combat:

• Brute force is always the wrong answer. Always.
• The faster your heuristics for planning attacks and evasions, the better.
• It's not about being smart, it's about being reactive. Iterate or die.
• Proactive is (usually) easy if you get reactive right the first time.
• If in doubt, offline computation is your friend. But you don't need it, because brute force is always the wrong answer. Always.

You never want to be in a situation where you have to compute a huge amount of stuff just to make a decision. In the worst case, you should at least precompute this sort of thing outside the game, and cache the results; instead of looping through thousands of orientations and distances every frame, for instance, compute optimal angles of attack for different combinations of ships, and store those. Then just have your AI try to steer into the known optimal positions instead of recalculating them unnecessarily.

However, I want to re-emphasize point one from above: if you're resorting to brute force, offline or otherwise, your AI is probably Doing It Wrong™ as Dave noted above. More on Doing It Right™ later.

The goal here is to build heuristics - guesses, in a word - which give you near-optimal results at much higher speed. Speed is not just important for framerate; it's important for the overall intelligence of your AI. The faster you can react to the player (or another AI) doing something, the better. Fighter pilots have a system called OODA - Observe, Orient, Decide, Act. The goal isn't to be perfectly smart at each step - in fact, the whole system is designed to help absorb inevitable mistakes and deal with the unexpected, which is going to happen in a dogfight. OODA is all about doing it fast - iterating through your situation, observing your surroundings, framing them in a way that you can deal with efficiently, deciding what to do, and then carrying out the decision.

The best fighter pilots can score consistent kills in shockingly little time by simply running through the OODA process as fast as possible. This applies equally to your AI.

Now, there's something to be said for initiative of course: doing something proactive to get the upper hand. You'll find (and we'll see later in this writeup) that proactive behaviour is easy to do once you get reaction right, at least for dogfight AI (this may not always be the case for other types of intelligence, especially at the strategic level).

So, armed with these principles, let's take a look at how a typical professional AI would handle a dogfight.



The OODA Loop In AI
Observation is the first step, and it's fairly easy. Just look for your target's position. Done! This might get tricky if you start adding features like cloaking devices, radar jammers, etc., but for the most part, observation is pretty trivial, and just consists of simple checks or lookups.

Orientation comes next. This is where things get interesting. In AI terms, what you want to do is score the various options you have available. Is the enemy in a position to fire on you? Evade! Is the enemy in a position to get shot down? Fire! Except you don't want to decide yet - you want to look at all of your options, and rank them.

Once you have a ranking of options, you can decide which one(s) to carry out. This is usually just a matter of picking the highest-scoring option, but that leads to bland AI that is easily predictable, and often very frustrating to play against. Sometimes, your AI should randomly make a mistake or do something sub-optimal, because that adds character.

Finally, you can act. This is usually a matter of changing your steering parameters to try and reach a new position, be it evasive or offensive, or just wandering around looking bored because there's nobody to fight nearby.


But what about optimal attack angles?
For the initial thrust, don't worry about this; concentrate on getting the fundamentals working well, and you'll more than likely discover that it just doesn't matter as much as you might think. For two small, fighter-style ships competing for a scrap of space, orientation means very little; if I can hit you, I want to hit you, and who cares if I blow up your shield generator or your engines first. Tight, twisting, "furball" style combat is what you want here, and in a furball, you take every shot you think you might be able to land, period.

Now, the case where things get interesting is in attacking a large capital warship with a fighter group. This is where angles and such become relevant. However, it's a lot easier to accomplish than you might think. Divide up the space around your target into zones; quadrants (Cartesian volumes) work well, where you look at the relative coordinate space of the target and divide it into eight regions based on the axes of the coordinate system. In an offline step, note where the elements of interest are located on the target. Engines might be in quadrant III, shield generator in VI, and so on. This can be cached for later use in the realtime AI.

Once you know, in some relative sense, where the Good Stuff To Shoot is located on your target (be it a warship or space station or whatever else), all you have to do is (A) get your fighters into that quadrant, and (B) point them directly at the object of interest and go guns blazing.

Of course, if you have really complex geometry, i.e. highly concave areas, you might need more than just Cartesian quadrant volumes; this is up to you. The idea, though, remains the same: divide the region around the target into areas where certain sub-targets are visible, and just fly into those regions and start blasting.


Proactive vs. Reactive
Remember I said the proactive stuff would be fairly easy? Well, here's the magic sauce: once you know where a capital ship's weak points are, or once you know that an enemy fighter is about to blast your cockpit into smithereens, you can start transitioning from reaction to proaction.

Suppose you're in a situation where two fighters are trying desperately to get a shot on each other. Fighter A has to decide what to do; he can break left, or he can break right. If he goes left, he exposes his damaged flank to the enemy, and risks a kill shot; but if he goes right, he shows his more strongly shielded/armored side, and might live longer. Poof: go right!

Or, what if you have a capital ship that sees a swarm of little interceptors coming at it, aimed right for the engine reactor? Just rotate a bit so that the main guns can aim at the little buggers, and swing the engines away to safety.

This sort of trick can be done all over the place in space combat, because once you can see a situation to react to it, you can predict that situation as well - and prediction is the entire difference between being reactive and being proactive.


The Bottom Line
Reaction is always going to look better than exhaustive planning, because the best laid plans are easy to tear to shreds if you know what they are. If your AI always tries to shoot my shield generator before taking shots of opportunity on my missile batteries, I'm going to fly in a way that always shows him my missiles and never my generator. Suddenly, your AI is easy to beat and boring.

On the flip side, if the AI reacts to your moves and takes the best option it can at every available tick, you get a much smarter looking enemy, a much more dynamic experience, and a much cooler feel overall.

Now, combine this with a little bit of prediction, and you can have your AI doing all kinds of cool stuff with very little computational power.


Some Final Spices for the Recipe
There's a few little tricks that don't merit much writeup but can still be useful when building a space combat game:

• You don't need to tick the AI every frame. Every 3-4 seconds is plenty. If you need a smarter-feeling enemy, up his individual tick rate to once every 1-2 seconds. More than that and you run the risk of your foes being frustratingly hard to kill.
• Utility-based systems for scoring various maneuvers and such are really handy.
• Build a library of cool-looking moves for ships to do, and perform them occasionally (but not too often, or they get cheesy). You can just randomly snag one, they don't have to be particularly intelligent.
• Emphasize interesting visuals and experience over optimality. You're making a game, not a stock market divination device.
• Don't fall victim to the temptation to write really complicated behaviours for your AI. Players probably won't notice.
• Steering systems and basic flocking can take you a very, very long way.
• Have your AI yell stuff over the comms every now and then based on its predictions and/or reactions. Nothing is as fun as hearing your enemy cuss you out when he realizes you've outsmarted him. By the same token, watching your wingmen appear to coordinate complex attacks is damned cool.
• Don't forget to add a layer of AI that can communicate between ships; something as simple as "hey let's all focus fire on that weakened destroyer over there" goes a long way.

Conclusion
So there you have it; a bit involved perhaps, but should be plenty of advice to get you going, and hopefully it'll lead you down the right roads towards making a really kick-ass game.

Best of luck! And of course feel free to drop me a line here in the thread or via PM if you have any specific questions.

[kryotech]

Thanks! This is really helpful, and I think I have a good idea of how to work this system now.....

[Kian]

Really cool post, ApochPiQ.

[Mithon]

The advice about heuristics and not doing things the brute force way sounds very appealing to me, but I've nothing to contribute on that, so instead I'll note that in code that's iterating a lot a few optimizations will probably make a huge difference. In essence you're checking which orientation is the best for each possible position. Even so you're recalculating the position for every orientation. Furthermore you're storing all these values in memory, and I can't figure out why. It seems to be because of checking them against eachother later on. Why not do this checking within the calculation-loop?

function Update () {
	if (hasPath==false){
		var position : Vector3;
		var orientation : Vector3;
		var bestPos : Vector3;
		var bestGain : int=0;

		var enemyDamage : int=0;
		var damageTaken : int=0;
		var expectedGain : int=0;

		for (var i : int=0; i<6; i++){
			for (var e : int=0; e<6; e++){
				for (var u : int=0; u<6; u++){
					for (var n : int=0; n<3; n++){
						position=findPosition(i*60, e*60, u*60, n*100);
						for (var t : int=0; t<6; t++){
							for (var m : int=0; m<6; m++){
								for (var q : int=0; q<6; q++){
									orientation=Vector3(t*60, m*60, q*60);
									enemyDamage=findDamage(enemyTarget, thisShip, position, orientation, "attacker");
									damageTaken=findDamage(thisShip, enemyTarget, position, orientation, "defender");
									expectedGain=calcGains(enemyDamage, damageTaken);
									if (expectedGain > bestGain){
										bestGain=expectedGain;
										bestPos=position;
									}
								}
							}
						}
					}
				}
			}
		}
		hasPath=true;
	}

	if (hasPath==true){
		GetComponent("ship guidance").positioning=bestPos;
	}
}

bestGain should either be initialized to something smaller than all possible gains, or a check on hasPath==false could be added to ensure the first position is set as bestPos at its iteration. hasPath could also be set up there. By setting hasPath in there, you could even add a sort of "I panick" when there's no good positions to move to, ie. the hasPath will remain false, meaning the ship guidance won't be updated in this situation. I'm assuming some other part of your system is resetting hasPath to false at some point? Otherwise the ship guidance will at most be updated once.

[SWQUEENIFY]

The advice about heuristics and not doing things the brute force way sounds very appealing to me, but I've nothing to contribute on that, so instead I'll note that in code that's iterating a lot a few optimizations will probably make a huge difference. In essence you're checking which orientation is the best for each possible position. Even so you're recalculating the position for every orientation. Furthermore you're storing all these values in memory, and I can't figure out why. It seems to be because of checking them against eachother later on. Why not do this checking within the calculation-loop?

function Update () {
	if (hasPath==false){
		var position : Vector3;
		var orientation : Vector3;
		var bestPos : Vector3;
		var bestGain : int=0;

		var enemyDamage : int=0;
		var damageTaken : int=0;
		var expectedGain : int=0;

		for (var i : int=0; i<6; i++){
			for (var e : int=0; e<6; e++){
				for (var u : int=0; u<6; u++){
					for (var n : int=0; n<3; n++){
						position=findPosition(i*60, e*60, u*60, n*100);
						for (var t : int=0; t<6; t++){
							for (var m : int=0; m<6; m++){
								for (var q : int=0; q<6; q++){
									orientation=Vector3(t*60, m*60, q*60);
									enemyDamage=findDamage(enemyTarget, thisShip, position, orientation, "attacker");
									damageTaken=findDamage(thisShip, enemyTarget, position, orientation, "defender");
									expectedGain=calcGains(enemyDamage, damageTaken);
									if (expectedGain > bestGain){
										bestGain=expectedGain;
										bestPos=position;
									}
								}
							}
						}
					}
				}
			}
		}
		hasPath=true;
	}

	if (hasPath==true){
		GetComponent("ship guidance").positioning=bestPos;
	}
}

bestGain should either be initialized to something smaller than all possible gains, or a check on hasPath==false could be added to ensure the first position is set as bestPos at its iteration. hasPath could also be set up there. By setting hasPath in there, you could even add a sort of "I panick" when there's no good positions to move to, ie. the hasPath will remain false, meaning the ship guidance won't be updated in this situation. I'm assuming some other part of your system is resetting hasPath to false at some point? Otherwise the ship guidance will at most be updated once.

what language is that?