## Tower Defense Question

• 288 Views
• 5 Replies
raidthewood
raidthewood
• Member since: Apr. 7, 2010
• Offline.
Forum Stats
Member
Level 04
Blank Slate
Tower Defense Question Aug. 1st, 2012 @ 09:41 PM

Hey guys, Im working on a tower defense type game. Instead of using the classic waypoint system where the creeps follow a predetermined path they pathfinding their way to a random target [random turret or building].

Anyway, needless to say, I need to save as much memory as possible. I've run into my first efficiency problem with my turrets.

In the turret class I loop through a Vector holding each and every enemy and use Manhattan distance to see if it is within range, then-- because I dont want a square range I use ecludian distance [I do 2 distance detections because I dont want to use ecludian distance for EVERY enemy, manhattan distance is much faster]

Even with my ecludian distance I dont use Math.sqrt. I simply square the range and compare the 2.

Here is my code:

[sorry its pretty sloppy]

``````package
{
import ShotTypes.Shot;
/**
* ...
* @author Rick Horwath
*/
public class Turret
{

public var x:int = 0;
public var y:int = 0;
public var rot:Number = 0;

public var tier:int = 0;
public var color:int = 0;

public var target:Creep;
public var accuracy:Number = 0;
public var firing:Boolean = false;
public var range:int = 0;

public var spray:Boolean = true;

private var inRange:Vector.<Creep> = new Vector.<Creep>();

public function Turret(Color:int, Tier:int, Range:int)
{

tier = Tier;
color = Color;
range = Range;

}

var timer = 0;

public function Update():void {

for (var i:int = 0; i < Global.creepLength; i++) {

var t:Creep = Global.creepList[i];

var dX:Number = t.x - x;
var dY:Number = t.y - y;
dX = (dX < 0 ? -dX : dX);
dY = (dY < 0 ? -dY : dY);

if(dX < range && dY < range){
if (inRange.indexOf(t) == -1) {

if ((dX * dX) + (dY * dY) < range*range) {

inRange.push(t);

}

}
}
}

if (inRange.length > 0) {

firing = true;

}

if (firing) {

target = inRange[0];

var difX:Number = x-target.x;
var difY:Number = y-target.y;
var dist:Number = (difX * difX) + (difY * difY);
rot = Math.atan2(difY, difX);

timer++;
if(timer >= 5){
fire();
timer = 0;
}

if (dist > range*range) {

inRange.splice(0, 1);
firing = false;

}

if (Global.creepList.indexOf(target) == -1) {

inRange.splice(0, 1);
firing = false;

}

}

}

private function fire():void {

Global.shots.push(new Shot(rot, this));

}

}

}``````
raidthewood
raidthewood
• Member since: Apr. 7, 2010
• Offline.
Forum Stats
Member
Level 04
Blank Slate
Response to Tower Defense Question Aug. 1st, 2012 @ 09:43 PM

Sorry for double post but I forgot the actual question! Does anyone know of any way to optimize my search? I'm looking for a way to not even loop through enemies that are too far to even consider.

MSGhero
MSGhero
• Member since: Dec. 15, 2010
• Online!
Forum Stats
Supporter
Level 16
Game Developer
Response to Tower Defense Question Aug. 1st, 2012 @ 10:21 PM

At 8/1/12 09:43 PM, raidthewood wrote: Sorry for double post but I forgot the actual question! Does anyone know of any way to optimize my search? I'm looking for a way to not even loop through enemies that are too far to even consider.

No, or at least not reasonably. If you're only doing basic math calculations, there's no reason to optimize unless you have millions of enemies or something. Loop through all enemies, if it's too far from the tower, continue. One optimization is to get rid of the manhattan distance calculation, as the splice method in arrays and vectors probably takes more time to run than the rest of your code.

Also don't use global variables (global constants are ok). Keep the list of enemies as a private var inside the main class and pass it in as a parameter to your update function:

``````// enterframe
for each turret
turret.update(creepList);
// update method
for each creep in creepList
check distance``````

Don't code with optimization in mind. Worry about that later once everything works.

egg82
egg82
• Member since: Jun. 24, 2006
• Offline.
Forum Stats
Member
Level 05
Game Developer
Response to Tower Defense Question Aug. 1st, 2012 @ 10:45 PM

this link should be of help.

uints are fastest on player 10 and above

``private var inRange:Vector.<Creep> = new Vector.<Creep>();``
``private var inRange:Vector.<uint> = new Vector.<uint>``

also: "new" is the slowest keyword in flash. Avoid using if at all possible.

local variables are fastest when getting information.

``for (var i:int = 0; i < Global.creepLength; i++) {``
``````var len:uint = Global.creepLength;
for (var i:int = 0; i < len; i++) {``````

if statements are slower than math

``````dX = (dX < 0 ? -dX : dX);
dY = (dY < 0 ? -dY : dY);``````

use direct references when going through arrays and inserting into arrays.

``inRange.push(t);``
``inRange[i] = t;``

some variables can just be left out.

``````if (inRange.length > 0) {

firing = true;

}

if (firing) {
...
}``````
``````if (inRange.length > 0) {
...
}``````

as for a basic "too far to consider"

``````package  {
import flash.display.MovieClip;
/**
* ...
* @author Alexander
*/
public class Radcheck {

public function Radcheck() {
//constructor
}

public function near(target:MovieClip, vector:Vector.<MovieClip>, rad:uint = 10):Vector.<uint> {
var near:Vector.<uint> = new Vector.<uint>;
var len:uint = vector.length;
var tx:Number = target.x;
var ty:Number = target.y;
var twid:Number = target.width*0.5;
var thei:Number = target.height*0.5;
var next:uint = 0;
var mc:MovieClip;

for (var i:uint = 0; i < len; i++) {
mc = vector[i];
if ((mc.x-mc.width*0.5 >= tx-twid-rad || mc.x+mc.width*0.5 < tx+twid+rad) || (mc.y-mc.height*0.5 >= ty-thei-rad || mc.y+mc.height*0.5 < ty+thei+rad)) {
near[next] = i;
next++;
}
}

return near;
}

}

}``````

it's very basic and very general. Mold it to your purposes, don't just copy and paste; it'll be extremely slow otherwise.
However, that should reduce your enemy array to a more manageable size, so you can use your more CPU-intensive functions after that.

One last thing: division is MUCH slower than multiplication.

Programming stuffs (tutorials and extras)
PM me (instead of MintPaw) if you're confuzzled.
thank Skaren for the sig :P

egg82
egg82
• Member since: Jun. 24, 2006
• Offline.
Forum Stats
Member
Level 05
Game Developer
Response to Tower Defense Question Aug. 1st, 2012 @ 11:39 PM

At 8/1/12 10:45 PM, egg82 wrote: use direct references when going through arrays and inserting into arrays.

inRange.push(t);

inRange[i] = t;

in that situation, push may be faster (considering the fact that you'd have to count the whole array beforehand)

though I suppose you could use i = inRange.length, i++, and then inRange[i] - but that would be just as slow.

Programming stuffs (tutorials and extras)
PM me (instead of MintPaw) if you're confuzzled.
thank Skaren for the sig :P

egg82
egg82
• Member since: Jun. 24, 2006
• Offline.
Forum Stats
Member
Level 05
Game Developer
Response to Tower Defense Question Aug. 2nd, 2012 @ 12:01 AM

triple-post, sorry.

i'm trying not to sound like an idiot, but MintPaw keeps proving me wrong

I haven't run the test myself, but it seems a bit odd that the two benchmarks i've seen so far have the same code with opposite results.

Programming stuffs (tutorials and extras)
PM me (instead of MintPaw) if you're confuzzled.
thank Skaren for the sig :P