Algorithm for targetting enemies

[EccentricDuck]

Hey, I have a major dilemma that I have been struggling with. I'm making a tower defense game in XNA, and I need a way to get the tower to target an enemy within it's range (created a circle class with a contains method that does this just fine) and target the enemy that is closest to the base/endpoint (to prioritize enemies that are farthest along the path). I have a method for measuring the distance to the endpoint, and the enemies are contained within a list.

My thought was that I would set the target enemy's position to a pointer/reference of some sort so that it could update dynamically. A previous attempt of mine used a queue with the first enemy to enter the tower's radius at the beginning of the queue, but I didn't realize that it would just store the static positions at the time the enemies entered the queue (and I figured that adding to and clearing the queue with every update call was a very inefficient way of implementing this). One thought I had was that I would sort the list of enemies by distance to endpoint (shouldn't really change too much) and then run through the contains method foreach enemy in the list, and then the first enemy that satisfied the conditional statement (contained within the radius of the circle) would be added to the pointer/reference used for targetting and I'd break out of the method (minimal calculations since it breaks as soon as it reaches a valid target).

Now in practice I've been running into all kinds of problems in trying to implement this. I can't seem to get the List.OrderByDescending() method to work properly (this is necessary since it allows the next method with the Contains conditional statement to grab the first available enemy that is closest to the endpoint). Additionally, I'm not sure exactly what a pointer/reference like that would look like. An example of how that would look would be very helpful. Also, an alternate way of accomplishing what I'm trying to do would be just as helpful.

Thank you.

[Live-Dimension]

I didn't realize that it would just store the static positions at the time the enemies entered the queue.

Most likely by accident your making a copy of the enemy and that's the "thing" going in the que. C# does "support" pointers to some degree, but it's unsafe code. C# programming shouldn't need to use pointers at all.

Some code could be useful.

[EccentricDuck]

I have a list of enemies created in a class I call WaveGenerator (generates the waves of enemies):

Code: Select all

public List<GameObject> enemies1;
.
.
.
// logic for the adding enemies on a timer goes in here

                        // Parameters are string name, Vector2 position, float velocity, float turnSpeed, 
                        // int health, int defense, int attack, string level (used in a case-switch statement for level specific features)
                        enemies1.Add(new GameObject("Enemy", new Vector2(0, 590), 1.0f, 0.025f, 
                            120, 5, 0, "Fiji"));

I no longer have the exact code for the queue, but essentially it went along the line of using a foreach loop that added enemy.position (their Vector2 position) to the queue. It was not specific to the enemy's distance from the end of the path, instead relying on the fact that it would iterate through them in the order of when they were created. The queue's type was Vector2. Here's more or less how it went:

Code: Select all

foreach (GameObject enemy in enemies1)
{
    // logic for seeing if they're within the turret's radius
    {
        target.Enqueue(enemy.position);
    }
}

[Live-Dimension]

Now I know exactly what is going on!

First - your saying a queue when in fact your using a list. These two are completely different things. I think I may be misunderstanding what your trying to say however.

Second - I'm going to assume that each loop you go through that enemies list and update each enemies X/Y in some way?

How about a look at the GameObject class?

[EccentricDuck]

Sorry, I probably should have explained that code a little better. I was indeed using a queue for targetting, though I first showed the list I used for creating the enemies to give a better idea of how the code for the enemies works. The queue is simply intended for targeting purposes - adding enemies to the queue that meet the requirement (though I realize now that I'm only adding their position to the queue). "target" is a queue with type Vector2 (though I wonder if I should use GameObject and then just reference the position on each GameObject).

I actually use the same GameObject class for both towers and enemies - they just have different constructors and update methods. My thinking at the time was that it would simplify things since there's a lot of commonalities, but now I'm not sure if I should break them into two distinct classes or not (though I'm going off a bit on a tangent). Additionally, I've since revamped my code and created a ClosestEnemy class that should work. I couldn't test it properly last night though because I screwed something else up (as I'm just realizing now). I wanted to test it on 1 enemy, so in my perfect logic I decided to tell the loop that creates enemies not to reset the timer I created (because that'll make it only create 1 enemy right). I was too tired to clue into why there was a solid block streaming along the path the enemies walk.

Anyway, here's the full code for the GameObject class if you're interested:

Code: Select all

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;
using Microsoft.Xna.Framework.Net;
using Microsoft.Xna.Framework.Storage;

namespace Waypoints
{
    public class GameObject
    {
        public string           name;
        public Vector2          direction;
        public float            rotation;
        public float            targetRotation;
        public float            turnSpeed;
        public float            difference;
        public Vector2          center;
        public float            velocity;
        public int              health;
        public int              defense;
        public int              attack;
        public bool             alive;
        public Vector2          position;
        public ClosestEnemy     targetEnemy;
        public Queue<Vector2>   waypoints;
        public float            timer;
        public float            interval;
        public Circle           circle;

        #region Constructors

        // Paramaterless constructor (for inheritance)
        public GameObject()
        {

        }

        // Basic test constructor
        public GameObject(string name, Vector2 position)
        {
            this.name       =   name;
            this.position   =   position;
            rotation        =   0.0f;
            velocity        =   0.0f;
            alive           =   true;
            timer           =   0.0f;
            interval        =   50f;
        }

        // Fully paramaterized constructor for turrets
        public GameObject(string name, Vector2 position, float turnSpeed,
            int attack)
        {
            this.name       =   name;
            this.position   =   position;
            this.rotation   =   0.0f;
            this.turnSpeed  =   turnSpeed;
            this.attack     =   attack;
            alive           =   true;
            timer           =   0.0f;
            interval        =   100f;
            circle          =   new Circle(position, 600);      // needs a customizable circle for different units
            targetEnemy     =   new ClosestEnemy();

        }

        // Fully paramaterized constructor for enemies
        public GameObject(string name, Vector2 position, float velocity, float turnSpeed,
            int health, int defense, int attack, string level)
        {
            this.name       =   name;
            this.position   =   position;
            this.rotation   =   0.0f;
            this.turnSpeed  =   turnSpeed;
            this.velocity   =   velocity;
            this.health     =   health;         // if necessary, maxHealth (for hitpoints measurement) can be made equal to this and then left unchanged
            this.defense    =   defense;
            this.attack     =   attack;
            alive           =   true;
            timer           =   0.0f;
            interval        =   100f;
            waypoints       =   new Queue<Vector2>();

            #region Waypoints
            // The enemy units have pre-defined paths set out in a queue
            switch (level)
            {
                case "Fiji":
                    waypoints.Enqueue(new Vector2(250, 590));
                    waypoints.Enqueue(new Vector2(320, 490));
                    waypoints.Enqueue(new Vector2(345, 230));
                    waypoints.Enqueue(new Vector2(420, 135));
                    waypoints.Enqueue(new Vector2(790, 135));
                    waypoints.Enqueue(new Vector2(870, 240));
                    waypoints.Enqueue(new Vector2(880, 330));
                    waypoints.Enqueue(new Vector2(980, 430));
                    waypoints.Enqueue(new Vector2(1400, 430));
                    break;

                case "Matterhorn":
                    // Enter waypoints once this level is implemented
                    break;
            }

            #endregion
        }
        #endregion

        #region Methods

        public float DistanceToEnd()            // should be integrated with UpdateEnemy if it is used
        {
            return Vector2.Distance(position, waypoints.Last<Vector2>());
        }

        public void UpdateTurret(GameTime gameTime)
        {
            // Updates which enemy is the target
            targetEnemy.Target(this);

            // Updates the direction to face the target enemy
            direction       =   -(position - targetEnemy.closestEnemy.position);
            direction.Normalize();                          // normalizes the vector to 1 unit in length so that our velocity variable can act as a scalar value

            // Updates the rotation based upon the target rotation and the allowed turning speed
            targetRotation  =   (float)Math.Atan2(direction.Y, direction.X) + (float)Math.PI / 2;

            difference      =   targetRotation - rotation;
            difference      =   MathHelper.Clamp(difference, -turnSpeed, turnSpeed);

            rotation       +=   difference;

        }

        public void UpdateEnemy(GameTime gameTime)
        {
            // Updates the direction to face the next waypoint
            direction       =   -(position - waypoints.Peek());
            direction.Normalize();                          // normalizes the vector to 1 unit in length so that our velocity variable can act as a scalar value

            // Updates the rotation based upon the target rotation and the allowed turning speed
            targetRotation  =   (float)Math.Atan2(direction.Y, direction.X) + (float)Math.PI / 2;

            difference      =   targetRotation - rotation;
            difference      =   MathHelper.Clamp(difference, -turnSpeed, turnSpeed);

            rotation       +=  difference;

            // Move in the current direction towards the waypoint
            position        =   position + (direction * velocity);

            if (Vector2.Distance(position, waypoints.Peek()) < 1.0f)
            {
                waypoints.Dequeue();

                if (waypoints.Count == 0)
                {
                    alive = false;
                }
            }
        }
        #endregion
    }
}

And here's the ClosestEnemy class (minus using statements - it currently targets the enemy closest to the turret since that related to an example I saw and I just wanted to try something that would work and go from there):

Code: Select all

namespace Waypoints
{
    public class ClosestEnemy : WaveGenerator
    {
        private float distance;
        private float closestEnemyDistance;
        public GameObject closestEnemy = new GameObject();

        public void Target(GameObject turret)
        {
            foreach (GameObject enemy in base.enemies1)
            {
                distance = Vector2.Distance(enemy.position, turret.position);
                if (distance < turret.circle.radius && distance < closestEnemyDistance)
                {
                    closestEnemyDistance = distance;
                    closestEnemy = enemy;
                }
            }
        }
    }
}

Now to fix the problem I just recognized (with the timer) and test it again.

[EccentricDuck]

Augh, I can't seem to get it to work. After debugging my code (revealing yet more problems) I've realized that my ClosestEnemy class references won't work since I haven't instantiated my FijiScreen class (the gamestate for the level I'm running it on) nor would that make sense since this should be usable by different gamestates. Same goes if I drop that method down into the GameObject class (the only place where it's instantiated and called from anyway).

Well, this needs to be reworked but I need to sleep for now. This is so exhilaratingly frustrating... Must keep going but must stop for sleep...

[Live-Dimension]

I'm seeing more problems.

Code: Select all

// Basic test constructor
        public GameObject(string name, Vector2 position)
        {
            this.name = name;
            this.position = position;
            rotation = 0.0f;
            velocity = 0.0f;
            alive = true;
            timer = 0.0f;
            interval = 50f;
        }

this.name = name;
this.position = position;

compare it with this

rotation = 0.0f;

As you can tell, any varible inside a classes function automatically has "this" added to it unless it was from another class. In effect, your probably doing this....

this.name = this.name;
this.position = this.position;

You do this over and over again in the code sample you provided - and it's completely legal code. Obviously it's not what you want though. I'm somewhat surprised Visual Studio doesn't provide a warning for it, it's a top-notch IDE.

I actually use the same GameObject class for both towers and enemies - they just have different constructors and update methods. My thinking at the time was that it would simplify things since there's a lot of commonalities, but now I'm not sure if I should break them into two distinct classes or not (though I'm going off a bit on a tangent).

I seen what you've done in the source code. That is BAD. I cannot emphasise just how bad it is. First of all you completely and utterly obliderate all kinds of type safety. turrent != enemy. laserTurrent != missileTurrent. etc etc. But with your logic it will go turrent == enemy, laserTurrent == missileTurrent, etc. Sometimes it's tempting to break type-safety, but all your doing is shooting your foot.

I've also noticed that you've even put the levels into each game object (Waypoints). That should be as part of the level objects.

If that's not bad enough, what happens when you have 20 different enemies and say 15 different turrents. How on earth will you compare them? program that? With 35 constructors, update functions, etc? What your looking for is inheritance, and is one of the biggest helps and ideals with OOP. Here's a good start. I've only skimmed the page, but feel free to ask anything you don't understand. There is PLENTY of examples and lessons on inheritance all over the net.
http://www.codeproject.com/KB/cs/csharpintro01.aspx

Once you've got your classes sorted out and your code fixed up feel free to ask if your still having troubles.

[ismetteren]

I'm seeing more problems.

Code: Select all

// Basic test constructor
        public GameObject(string name, Vector2 position)
        {
            this.name = name;
            this.position = position;
            rotation = 0.0f;
            velocity = 0.0f;
            alive = true;
            timer = 0.0f;
            interval = 50f;
        }

this.name = name;
this.position = position;

compare it with this

rotation = 0.0f;

As you can tell, any varible inside a classes function automatically has "this" added to it unless it was from another class. In effect, your probably doing this....

this.name = this.name;
this.position = this.position;

You do this over and over again in the code sample you provided - and it's completely legal code. Obviously it's not what you want though. I'm somewhat surprised Visual Studio doesn't provide a warning for it, it's a top-notch IDE.

As you can tell, any varible inside a classes function automatically has "this" added to it unless it was from another class
Im more of a Java programmer than a C# programmer, but im pretty sure that not is right. AFAIK scope works like this:

Code: Select all

{
    String varA = "one";
    {
        String varA = "two";
        //here im accesing varA from the innermost scope, whic means this will print "two"
        print(varA);
    }
    //same thing here, so this prints "one"
    print(varA);
}

i havent tested it though, but im VERY sure this is right.

I have not read the whole thread from end to end so im sorry if im way of.

[Live-Dimension]

As you can tell, any varible inside a classes function automatically has "this" added to it unless it was from another class
Im more of a Java programmer than a C# programmer, but im pretty sure that not is right. AFAIK scope works like this:

Code: Select all

{
    String varA = "one";
    {
        String varA = "two";
        //here im accesing varA from the innermost scope, whic means this will print "two"
        print(varA);
    }
    //same thing here, so this prints "one"
    print(varA);
}

i havent tested it though, but im VERY sure this is right.

I have not read the whole thread from end to end so im sorry if im way of.

Now that you mention it yes I'm pretty sure your right. I think it's a terrible idea that it's legal, and you should never try to do it. It's just so confusing >_<. As you can tell, I never use it.

[EccentricDuck]

It seemed to make a lot of sense to me to name the parameters the same as the variables/objects that I was assigning them to. When you get a whole bunch of parameters it's a pain to have to "translate" one thing into another thing when they are indeed the same thing. Why, for example, would you create a velocity object, then put a parameter for movementRate in the constructor and assign the value of that to velocity when you could just use velocity consistently? Maybe that's just me, but I find that in such a case it makes it simpler and cleaner to use velocity as a parameter (so in the scope of the constructor method) and assign it to this.velocity (the velocity for the class). When I go through it later I look at the parameters and I instantly know what they are relative to the fields, whereas if I give them different names then they are harder to keep track of and I have to cross reference what's what.

I'm seen several code examples in C# using properties that do this too, giving a different property name to the same variable and it becomes so hard to keep track of. It seems to make my time spent reading and coding that much less efficient, as if hearing a conversation about Bob and Jack - where Bob was continually referred to as Jim, Bill, Joe, Jake, Ted, and Rob and Jack was referred to as Roy, Henry, Steve, George, and Harry. It makes me pause to figure out who is actually being referred to in the conversation.

Regarding the issue with having enemies and towers in the same class I will change that and I definitely need to read up more on inheritance. I understand the concept well enough, though I think I need some solid practice in implementing it in order to make it seem more natural and train myself to use it when applicable.

Thanks for the help!

[Live-Dimension]

It seemed to make a lot of sense to me to name the parameters the same as the variables/objects that I was assigning them to. When you get a whole bunch of parameters it's a pain to have to "translate" one thing into another thing when they are indeed the same thing. Why, for example, would you create a velocity object, then put a parameter for movementRate in the constructor and assign the value of that to velocity when you could just use velocity consistently? Maybe that's just me, but I find that in such a case it makes it simpler and cleaner to use velocity as a parameter (so in the scope of the constructor method) and assign it to this.velocity (the velocity for the class). When I go through it later I look at the parameters and I instantly know what they are relative to the fields, whereas if I give them different names then they are harder to keep track of and I have to cross reference what's what.

I'm seen several code examples in C# using properties that do this too, giving a different property name to the same variable and it becomes so hard to keep track of. It seems to make my time spent reading and coding that much less efficient, as if hearing a conversation about Bob and Jack - where Bob was continually referred to as Jim, Bill, Joe, Jake, Ted, and Rob and Jack was referred to as Roy, Henry, Steve, George, and Harry. It makes me pause to figure out who is actually being referred to in the conversation.

Regarding the issue with having enemies and towers in the same class I will change that and I definitely need to read up more on inheritance. I understand the concept well enough, though I think I need some solid practice in implementing it in order to make it seem more natural and train myself to use it when applicable.

Thanks for the help!

Ah. Well I use lower-case for all class variables. On a function argument I make it an upper-case. IE

void Move(int X, int Y) {
x = X;
y = Y;
}