1

I am making a game in Unity with c# code and I want a character to have something like aggro table.

It will be something like (float, int) table where int is other character id and float is actual aggro value.

Basically, I have few things in mind:

  • The table should be sorted by float keys so I can quickly get top entries
  • I need to be able to frequently lookup entries by its int value because of (3)
  • I want to change float key frequently and have the table sorted up all the time
  • I dont care about memory usage as there wont be that many entries
  • I do care about performance of operations like inserting/removing/changing entries and re-sorting the list

I am not very experienced in C# saw few things like sortedlist/dictionary, but it doesnt seem to be optimalized for all the things I want.

Do you have any advice?

EDIT: Not sure if I did a good job at explaining what I want to achieve. It might be very similar to a table of football player names and number of goals they scored during the season. I will frequently ask for "most productive players" and also I will frequently update their scores by looking up their names and changing their stats, needing the table to be sorted all the time.

Improve this question
6
  • Side note : Never use floats as keys, they are not meant to be exact, which means retrieving your key-value pair will be a nightmare, using an int as a key you could use dotnetperls.com/sorteddictionary or dotnetperls.com/sortedlist Commented Sep 25, 2016 at 9:40
  • Made an edit to further clarify. Commented Sep 25, 2016 at 10:11
  • How's the aggro value being used? Is it based on player range from creature or damage dealt to creature? Commented Sep 25, 2016 at 11:15
  • Damage dealt. No need to deal with range. Commented Sep 25, 2016 at 11:20
  • It is used just for sorting targets once the monster enters combat. Commented Sep 25, 2016 at 11:21

2 Answers 2

Reset to default
2

You could use a List<Character>, or an array excluding the player's character. You keep the List<Character> sorted with the highest aggro value at the front. To keep everything sorted every frame you run quicksort first. Once a Character has a lower aggro value than the player's aggro threshhold you escape out of the method.

If aggro is above the threshold just run the aggro check.

You could extend this to work for multiplayer by having a List<Player>. Something like:

void quicksort(List<Enemy> enemies, int first, int last)
{
   int left = first;
   int right = last;
   int pivot = first;
   first++;

   while (last >= first)
   {
       if(enemies[first].Aggro >= enemies[pivot].Aggro &&
           enemies[last].Aggro < enemies[pivot].Aggro)
           swapp(enemies, first, last)
       else if(enemies[first].Aggro >= enemies[pivot].Aggro)
         last--;
       else if(enemies[last].Aggro < colliders[pivot].Aggro)
         first++;
       else
       {
            last--;
            first++;
       }
   }

   swap(enemies, pivot, last);
   pivot = last;
   if(pivot > left)
      quicksort(enemies, left, pivot);
   if(right > pivot + 1)
     quicksort(enemies, pivot + 1, right);
}

void swap(List<Enemy> enemies, int left, right)
{
   var temp = enemies[right];
   enemies[right] = enemies[left];
   enemies[left] = temp;
}

void CheckAggro()
{
   quicksort(enemies, 0, enemies.Count - 1);
   for(int = 0; i < players.Count; i++)
   {
       for(int j = 0 < enemies.Count; j++)
       {
           if(players[i].AggroThreshhold < enemies[j].Aggro)
           {
                break;
           }
           // Perform what happens when enemy is high on aggro threshold.
       }
   }
}

If players have different aggro thresholds you could save all of the enemies who have aggro above the minimum to a separate List, and then do a check against that from the player with the lowest to highest threshold. Just keep the list of players sorted with the lowest aggro threshold first.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Well I will have to use quicksort each frame for each aggro list which doesnt seem very efficient, but since there is no better answer, I will probably have to it this way.
Quicksort will have O(n * log n), and will run extremely fast if the data is mostly sorted. You could use Radix sort, but that would only be faster if you have a very large data set. Mostly, likely way more enemies than what you would have on the screen.
Ok, thanks for info on quicksort performance with near sorted data, will do it this way. Even if I would have problem with performance, I can always limit the quicksort call to every nth frame I guess.
Yeah, it really depends on how you're updating your aggro values.
0

I think the best solution here in the SortedList. From What i could gather: SortedList <TKey, TValue> has faster insertion and removal operations when it comes to sorted date.

There is a question that i think will help: When to use a SortedList<TKey, TValue> over a SortedDictionary<TKey, TValue>?

hope I helped.

Improve this answer

1 Comment

But given that those components are sorted by key, that would mean I would have to iterate through the entire list to change the key (or remove and insert it again with different value). That seems inefficient.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.