Thread: Unit Actions

  1. #1
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743

    Unit Actions

    Well, I am working on having units act upon given commands right now in my RTS game, and I have some questions on how would be the best way to go about some things.

    For my game:

    Left Mouse-Click == Select Unit
    Right Mouse-Click == Have selected unit perform primary action at position of right mouse-click.

    Take Age of Empires for example. The left and right mouse clicks in my game perform the same operations. Left selects units, right attacks/moves/gathers.

    Also, at the current moment I keep all of my entities in the game stored in a std::vector. This way I can simply iterate through every entity each frame and do the proper updating to each entity. In my Entity::Update() function, the first thing I do is check for left clicks on the mouse. If a left click has occurred, I check to see if it has occurred in the area of that entity. If so, I select that unit. If not, I deselect the unit.

    Then, if the unit is selected, I check for right clicks, which imply that the user wants the selected unit to act in some sort of way. Up to now the only action has been to move (as was seen in my recent Alpha demo on my other thread about 1 week ago). That is all well and good, but now I need to add additional actions such as attack and gather (mainly working on attack right now).

    Therefore, this is what I have implemented:

    Psuedo Code:
    Code:
    if ( Entity is Selected )
    {
    	if ( Right Click has occurred )
    	{
    		Get Position on screen in which click occurred;
    		Set destination of entity to that position;
    		Check to see if enemy unit is at that position;
    		if ( enemy exist at position )
    			Set Target to that enemy entity;
    	}
    }
    Now, that seems pretty sensible to me. What I am wondering about is how I am implementing my checking to see if an enemy exists at the target location.

    At the current moment, I call a function which iterates through the entire entity list and checks the position of each entity. If a certain entity is located at the right-clicked position, and that entity is an enemy of the selected enemy, then I set it as the target entity of the selected entity, and break out of the loop. In essence, it is an O(n) algorithm. This O(n) algorithm is run for every selected unit on the map. Therefore, if every single entity on the map is selected, it is order O(n^2). However, it is highly unplausable that every entity on the map will be selected. At most their might be 25 units selected at a time.

    Do you think this is a good way to go about doing things? One obvious optimization is to split the entity list and have a seperate entity list for each player. That will happen later in development, but the project is not yet ready for that.

    However, another thought has popped into my mind. I am not sure how efficient it would be, however, and so I thought I would throw it out in front of all of you guys and see what you think. What if, when I update each entity each frame, I look at its world position, and then I go to the physical map and make that specific position on the map point to that entity, basically tying that position on the map and that entity together. Then, when I right click, I simply take the map position, see if it is pointing to any entity, see if that entity is an enemy, and then set it as a target.

    It seems efficient, but yet it also seems like it might be complicated at the same time. So what do you think about it?

    Also, if you know of any other good methods, what are they?
    My Website

    "Circular logic is good because it is."

  2. #2
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    On a side note:
    Since objects proably get destroyed and created often, why don't you use an std::list instead of an std::vector?
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  3. #3
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Well I've got a solution for you...but you might not like it.

    Try using a quadtree.

    First store a bounding box for each unit...you probably already have this. Divide your map into a set amount of quads using recursion.

    If the unit is not in the quad you are searching...move to its neighbor. You should be able to find the unit in under 5 recursions depending on how deep your tree goes. This will also work for multiple selections -> ie: the bounding box becomes the box that the player draws around the units.

    I think this has O(log n) but I could be wrong.

    Attached is a DOS quadtree example:

    Usage: quadtree <depth>

    If depth is too large then a stack fault or out of memory error can occur.
    This does not construct a quadtree...it just illustrates what it is doing. To see it go slower simply up the depth to about 10 and you will see what is taking place.

    If you want to you can put a getch() in the CreateQuadTree function() to further slow it down. Simply press a key to move to the next recursion.
    Last edited by VirtualAce; 05-25-2004 at 09:41 AM.

  4. #4
    Banned
    Join Date
    May 2004
    Posts
    129
    I read your post twice and I am not sure about the recursive O(n) algorithm. However, you seem to know what youa re talking about so I cannot really comment (I do not personally know what it is).

    For a generalized way of implementing very believable entity movement is to simulate a processor for each entity. Each entity has its own instruction pointer, and with the instruction pointer comes an 'operation code'. Then, you get to invent your own instruction set! The operation code typically holds:

    A floating point scalar
    An opcode identifier
    An entity pointer
    An integer
    A vector

    so you have:
    struct OPCODE
    {
    int OPCode;
    Vector OPVector;
    float OPFloat;
    int OPInt;
    Entity *OPEntPptr;
    }

    This seems like a total hack at first, but this is mroe or less how it is done professionally. Think about it, whenever you want to do *anything* with any unit in the world, it must involve one of those datatypes. If not, then you simply dont' use it! For example, you may want to attack an enemy, that requires various things
    a) knowing what the entity is (entity pointer)
    b) knowing WHERE the entity is (vector)
    c) how fast to move towards target persecond (float)

    you would then need to enumerate the types of operations:
    Code:
    enum 
    {
    Attack=0,
    Move,
    Idle,
    Patrol,
    NumOfInstructions
    }
    Each physical entity will own these things to make this work:

    Code:
    class ENTITY
    {
    public:
    void Update();
    static OPCODE instructions[NumOfInstructions]; //all that is needed is to set the OPCode identifier 
    //with these, which are typically held in either your enum or in #defines of a file
    int instructionpointer(0);
    int fetch(1); //true / false, tells the simulated process whether or not to fetch a new instruction
    OPCODE instruction; //the actual instruction owned by each entity
    }
    then in your handy dandy update function, you do something like this:

    Code:
    if(fetch) //do we need a new instruction yet? 
    //i.e have we accomplished what we previously wanted to do, 
    //or, have we quit trying to do what we previously wanted to do?
    {
    this->instruction = ENTITY::instructions[instructionpointer];
    //init values specific to scenario, i.e player position, or new target
    fetch = 0;
    }
    
    switch(instruction.OPCode)
    {
    case Attack:
    {
    //run your program attack code until you kill target or give up
    break;
    }
    
    case Move:
    {
    //do stuff
    break;
    }
    
    case Idle:
    {
    //DONT do stuff :)
    break;
    }
    
    }
    etc etc. I've made several syntax mistakes but its hard to show how this works. When you get it right, it works perfectly. You are starting to go down a road where you manually must check EVERY SPECIFIC condition in the world ALL of the time and things wont happen automatically. Obviously the next instruction pointer you want the program to do is decided upon algorithmically in each of those switch statements. You can have 10,000 possible actions, and depending on the outcome of each action you can branch off to potentially any other action, which is also a basis in neural nets and simulated human response.

    and just an example
    Code:
    	case	Attack:
    		{
    			if(EntityIsDead(instruction.OPEntity))
    			{
    				instructionpointer = Patrol; //or you can decide to idle, depending on random numbers
    				fetch	=	1; //tell engine to update my instruction set
    			}
    			else
    			{
    				//Calculate attack angles to player, you could even add MORE opcodes such that there is a specific
    				//'calculate pitch and yaw' instruction added to your instruction set, otherwise, you are in attack mode
    				//so continue attacking
    			}
    			break;
    		}
    The very nice thing about this type of implementation is that your recursive 0(n) algorithm can be encapsulated, but more effectively utilized, using this setup. Now if only I could get the whole grammar thing right
    Last edited by vNvNation; 05-26-2004 at 12:37 AM.

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    He was discussing how to effectively 'find' the unit in the list that has been selected...not how to move them convincingly.

    My algo will work super fast. With 10000 units the time it would take is: 4 recursions.

  6. #6
    Banned
    Join Date
    May 2004
    Posts
    129
    yeah i realized that, but there still needs to be conditions for breaking off the search and coordinating what new actions to take, etc, which is why i thought i could post that junk above

    doesn't really matter though i guess

  7. #7
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    I'm kind of interested in this topic, but I don't quite understand your idea, Bubba. So you divide a large quad into smaller ones...Then...um you keep dividing it a certain number of times (based on depth) and search through much smaller quads? I'm having trouble seeing how this could be very efficient.

    And what you said makes it sound like he's searching for a specific unit, when it sounded like he was just checking to see if any units were at a specific position.

    Maybe I'm just stupid
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  8. #8
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Quote Originally Posted by JaWiB
    I'm kind of interested in this topic, but I don't quite understand your idea, Bubba. So you divide a large quad into smaller ones...Then...um you keep dividing it a certain number of times (based on depth) and search through much smaller quads? I'm having trouble seeing how this could be very efficient.

    And what you said makes it sound like he's searching for a specific unit, when it sounded like he was just checking to see if any units were at a specific position.

    Maybe I'm just stupid

    There's a great visual representation at gametutorials.com (though its an oct-tree demo, not quad. same idea though)

    check it out Fifth one down

  9. #9
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    OK I actually checked out http://www.gamedev.net/reference/pro...res/quadtrees/

    And I think I understand the basics of it...But I still fail to see how it relates to his problem...
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  10. #10
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    Thanks for the replies guys.

    vNvNation, even though your response was not exactly what I was looking for, I do love your idea. Of course I do already have an enum of actions such as ATTACK, WALK, GATHER, etc., but I never thought of implementing them like opcodes. That is definitely an idea I will consider. Thanks for that idea. I like it a lot.

    Bubba, thanks for your idea about speeding up my search method. Like JaWib, I don't know much about quadtrees, as I have never used them before. But I think it's time I use them since I have been programming for 6 years now!!! So I will definitely search the quadtree/octtree tutorials that have been posted on my thread and consider using them.

    Recently I just purchased Tricks of the Windows Game Programming Gurus from Half Price Books for $12 (I love Half Price books...such great prices!!). I am not sure if it discusses quadtrees in it, but I will check.

    Anyways, thanks all for the ideas and help.
    My Website

    "Circular logic is good because it is."

  11. #11
    Banned
    Join Date
    May 2004
    Posts
    129
    I'm glad that you like the idea david. Another thing I wanted to point out for that whole opcode paradigm is that you can break sequences down to cut down on the amount of processing that needs to be done. For example, instead of running the entire algorithm you have for path finding, you might be able to run one or two steps per frame, or base the number of steps you run based on the frame time itself. In this case the OPCode data would hold the results of the last search step you ran. Otherwise, running a complete recursive search of the map to find other entities might take up too much process time, and not leave enough time for rendering (which in a 2D game isn't as much of an issue, but it will be once you start throwing a good amount of entities in there). Obviously, a potential problem can occur because the other entities are always moving, but, it is just an idea.

  12. #12
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Quadtrees relate to this because:

    1. We know where the user clicked.
    2. We have all the coordinates of our units.
    3. We know the bounding boxes of those units.

    Therefore if the bounding box of the unit clicked is not within a certain quad...we discard that quad. Then we divide the quad that we have determined the unit is in..into smaller quads and do the same check. So on the first recursion you eliminate 3 very large areas that might contain any number of units. You will see why this algo is so fast very quickly.

    To visually illustrate. Take a piece of paper. Draw an X anywhere on the paper. Draw a bunch of O's all over the rest of the page. The paper is our map and the X is our unit and the O's are other units. Now divide the paper into 4 equal sections -> tear it in the middle on the horizontal and tear it down the middle on the vertical. If the X is not in the new sections...we discard those sections. Now look at the piece that the X is in. Tear it in half vertically and horizontally. If the X is not in a new piece...discard it. Now take the piece that the X is in...tear it in half vertically and horizontally. Now we should be able to determine where exactly our X is. If not tear it again and do the same check until you get 'close enough' to the X. Our 'close enough' is the bounding box of the unit.

    Now take the pieces of paper that have the O's on them. You should have 3 large pieces of paper, followed by 3 smaller pieces, etc., etc. This is because our X is guaranteed to be in at least one of them or one of the quads.

    First count the number of O's on the biggest 3 pieces. Now you see how many units we discarded in 1....count it...1 recursion. Very powerful.

    Now you see what I'm getting at??


    Compile this code and run it. Heck, if you have a version of BASIC you could get this up and running quickly and simply use LINE(x,y)-(x2,y2),color,BF for the boxes or quads.

    Code:
    #define DESIRED_WIDTH 4
     
    //This will only work correctly if x and y begin at 0
    void CreateQuads(int x,int y,int x2,int y2)
    {
      if ((x2-x)<=DESIRED_WIDTH) return;
     
      int midx=(x2+x)>>1;
      int midy=(y2+y)>>1;
      int red=rand()%255;
      int grn=rand()%255;
      int blu=rand()%255;
     
      DrawBox(x,y,x2,y2,red,grn,blu);
     
      //Top left
      CreateQuads(x,y,midx,midy);
     
      //Top right
      CreateQuads(midx,y,x2,midy);
     
      //Bottom left
      CreateQuads(x,midy,midx,y2);
     
      //Bottom right
      CreateQuads(midx,midy,x2,y2);
    }
    Last edited by VirtualAce; 05-27-2004 at 03:52 PM.

  13. #13
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    I'm still having trouble seeing your point. Wouldn't you still have to search through the entire list of units? I mean, unless you have an array of 10,000 elements (or however many tiles you have) you couldn't just discard the first n elements, because any one of them could be at any position on the map...So like you have a vector to store the units (maybe allocating space for 100 units), even if you put them in order from 0,0 to 100,100 (or whatever) you still can't tell how many of the units are in a specific region without searching the whole thing...

    I'm just having trouble seeing how you could design this to work the way you say it would...
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  14. #14
    Banned
    Join Date
    May 2004
    Posts
    129
    typically a section of the world would contain a list of pointers to the entities that are within that particular section. Whenever an object is moved, it undergoes a process called "relinking", where you calculate what parts of the world each object's bounding box lies in, and removing itself from the previous parts of the world it no longer resides in. You do not have to recurse the entire world when you do this. Then, when a mouse click occurs, you only need to
    a) recursively calculate where the mouse click occured (this will typically lie in only one part of the world, but could overlap onto several different parts depending on the size of the mouse click bounding box

    b) search each part that the moues click resides in and check each of its entities if the mouse click overlaps the entity bounding box

  15. #15
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    ...or you only have to search the first time through. The second search would only search units that passed the first test.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Creating C/C++ Unit Test Cases
    By chiefmonkey in forum C++ Programming
    Replies: 1
    Last Post: 04-28-2009, 08:29 PM
  2. structural fault any ideas
    By kaijuu in forum C Programming
    Replies: 17
    Last Post: 04-17-2007, 02:43 PM
  3. newbie here.. pls help me in this program!
    By rothj0hn in forum C Programming
    Replies: 2
    Last Post: 02-01-2006, 10:40 PM
  4. 2-d object avoidance. Help please! (basic stuff, I think)
    By charbach007 in forum Game Programming
    Replies: 4
    Last Post: 06-15-2004, 03:49 PM
  5. Unit Theory - input requested
    By Jeremy G in forum Game Programming
    Replies: 9
    Last Post: 11-18-2003, 10:54 AM