1. Hey! Guest! The 36th GMC Jam will take place between February 27th, 12:00 UTC - March 2nd, 12:00 UTC. Why not join in! Click here to find out more!
    Dismiss Notice
  2. NOTICE: We will be applying a Xenforo update on Tuesday 25th of February. This means that from approximately 10:00 to 14:00 BST the forums will be offline (or possibly longer). Sorry for the inconvenience! Official Announcement here.

Best Data Structure For This?

Discussion in 'Programming' started by robproctor83, Jan 10, 2020.

  1. robproctor83

    robproctor83 Member

    Joined:
    Sep 30, 2019
    Posts:
    296
    Hello,

    I need a data structure that can hold multiple timers (just an int) and an ID (object id). I need to be able to search by the id at periodic times and each step I am going to loop through each entry in the structure and count down until reaching 0 where it will be removed from the structure. The number of entries will be random, but usually no more than 5 at a time. Are DS Maps the best way to handle this? I was thinking maybe Grids, but the values will be : id - 985497983 and timer: 0.48 so I don't know that grids would work well...
     
  2. Alice

    Alice Toolmaker of Bucuresti Forum Staff Moderator

    Joined:
    Jun 20, 2016
    Posts:
    835
    I'm not sure what do you mean by ID exactly - whether it's an GameMaker instance ID, or some kind of custom virtual object ID (not handled by standard GM mechanics). If it's a GameMaker instance, you might want to considering storing the timers as variables of instances, and when the "tick" comes, decrease the timers for each instance which still has it (e.g. it's not set to undefined or something like that).

    If it's not a GameMaker object or you cannot use instance variables for some other reason, I'd suggest a ds_list of lightweight structures instead.

    Right now, a lightweight structure can be emulated by a ds_list (kind of like array) or a ds_map (e.g. {"id": 1265463, "time": 0.48}). Then, the code becomes something like this:
    Code:
    for (var i = ds_list_size(timers) - 1; i >= 0; i--) {  // counting down for easier deletion
      var timer = timers[| i];
      timer[? "time"] -= 1;  // or timer[| 1] -= 1 for ds_list; you know the gist
      if (timer[? "time"] < 0) {
        // do something with object ID
        ds_map_destroy(timer);
        ds_list_delete(timers, i);  // we can delete from list without disrupting the for loop, because we count down
      }
    }
    You might want to wait for new GML features (the open beta is supposed to be Soon™), so that you can define an actual lightweight object for timer instead of emulating it.
     
  3. robproctor83

    robproctor83 Member

    Joined:
    Sep 30, 2019
    Posts:
    296
    Thanks for the detailed response

    Im storing enemy collisions with ammo. When an enemy touches an ammo obj it stores which ammo object it hit with a timer and then counts down how long until that particular ammo object can hit the enemy again, otherwise the ammo collides every step. One ammo can hit multiple enemies and multiple times. The time between hits is also unique based on which ammo. Maybe it's a long lasting spell that only hits once or maybe it's a slow moving spell that can hit multiple times quicky. So whenever a collision happens I search that data structure and see if it already exists, if so ignore the hit and if not proceed. I ended up using a map because it can have random keys (object IDs) that I can search for to get a value.
     
  4. Alice

    Alice Toolmaker of Bucuresti Forum Staff Moderator

    Joined:
    Jun 20, 2016
    Posts:
    835
    Ah, yes, I misread your initial post and thought you meant to decrease the timers periodically, while it was randomly accessing specific timers. For accessing specific timers, ds_map is indeed much better.

    I just got another idea for your specific scenario, which is a little bit craftier and maybe not as easy to grasp as countdown timers, but I think it ultimately results in cleaner code.
    What if you didn't keep countdown timers in the map, but the next damage time instead?

    Let's say each weapon (the thing that damages enemies) keeps a lifetime variable, increasing by 1 every step and cooldown, defined for specific weapon type.
    When it damages the enemy, it stores the enemy id in a nextDamageTime map, with the value of lifetime+cooldown.
    When it collides with the enemy, it compares its current lifetime with the enemy's entry in nextDamageTime (if any) - if lifetime is lower, don't do anything, if it's same or higher, damage again.

    So e.g. when a bullet with lifetime 3 and cooldown 5 hits an enemy, it stores nextDamageTime for enemy id with value of 8. For steps 4, 5, 6, 7 it collides with the enemy but does nothing, but on step 8 it crosses the enemy's nextDamageTime threshold and damages again, this time setting the enemy's nextDamageTime to 13.

    What do you think? It should remove the need for iterating through timers completely, just basic map management, single variable incrementation and simple comparisons.
     
  5. GMWolf

    GMWolf aka fel666

    Joined:
    Jun 21, 2016
    Posts:
    3,523
    There are a number of ways to handle this:
    A) For each enemy, a list of IDs and timers.

    C) for each bullet, a list of IDs and timers.

    B) a map of collision pairs to timers


    The map of collision pairs to timers is not great because it's hard to achieve in GM (collision pair) and it's hard to do memory management. So let of ignore it.

    The map for each enemy could grow to be very large if you keep shooting at an enemy without killing it.

    Assuming the bullets/spells/whatever is short lived, then it may make more sense to store the list there.


    So, have each damager object store a list of timers, and a map of IDs to timer index. Each I'd and timer pair are matched by their index in the list.
    Every frame loop through the list and decrease the timer.
    Optionally remove any timer that is 0, as well as the corresponding entry in the ID map (that's trickier)

    When colliding with an instance, just find it's position in the timer list. If it's not in the list, or the timer at that position is 0, then reset the timer and deal damage.


    Notes on efficiency:
    The reason for the map/list combo is to iterate the list carefree (map iteration can be slow and painful). The map allows you to easily lookup the timer.
    You may like to replace the map with a list, and lookup items by their position in the list to reduce memory usage.
    Creating and deleting lists and maps all the time may be slow. Consider using a pool if it becomes an issue.
    Nevermind all that, read if you are interested but the solution offered by @Alice makes a lot of sense and I recommend you use that instead.
    It's cleaner, simpler and higher performance.


    I still don't like the idea of maps though, I wonder if the same thing could be achieved without such an expensive data structure (memory wise). Perhaps some sort of sorted list? Idk
     
    Last edited: Jan 10, 2020
  6. robproctor83

    robproctor83 Member

    Joined:
    Sep 30, 2019
    Posts:
    296
    Alice, thanks again for the response, I hadn't noticed any alerts for this thread and so somehow I missed your response entirely, very sorry about that. Your solution makes sense, I hadn't thought about it that way, to compare lifetimes and what not. I ended up just using maps and iterating through each item every step to increment the timer, but your suggestion is tempting. I may go back and give that a shot as it's not too late. If that works, I may implement that idea into my status effect timers too.

    Tanks!
     

Share This Page