- Home /
The question is answered, right answer was accepted
Most efficient way to remove a null object from a dictionary
Each Enemy has a dictionary of buildings and their distances from the enemy. However, once a building gets destroyed it stays in the dictionary as 'null'. Given that the dictionary is not ordered, what is the most efficient way to remove this object? At the moment I just iterate through with this code:
void Remove()
{
//TODO Less resource-hungry
for(int i = 0; i < distances.Count; i++)
{
var key = distances.ElementAt(i).Key;
if (key == null)
{
distances.Remove(key);
}
}
}
Note that buildings could get destroyed by other enemies too, so 'removing on destruction' would be a problem - of course, if anyone can give me a good way to do this it would be awesome. Additionally, you cannot remove 'null' keys from a dictionary and the class responsible for destroying the building is not the enemy class, which is only responsible for damaging it, so removing on destruction could be problematic.
Thanks!
Edit: After a lengthy conversation in the comments, I have opted for an event-based system because it also helps with other factors. Thanks everyone for all your help!
Why not just remove it ins$$anonymous$$d of setting it to null and then removing it?
Why would removing it on destruction be a problem?
Are you sure you want to even remove it? Surely reuse would be more efficient because it would stop introduction of GC issues trough deallocation?
Why does it matter if it's null?
There are a bunch of ways to solve this problem but I would suggest there is some inherent issues in your architecture so maybe fixing the problem at that level is more sensible.
Fair enough, I'm not gonna pretend I'm experienced in this :). At the moment, I have an 'EntityController' in the scene that collects all the entities for me. Enemies have access to it at the beginning to create a dictionary of distances. 1. Removing it occurs in the Enemy class whereas destruction occurs in the Building class. I suppose I could create a coroutine to wait 5 secs before destroying so it is not null, but then it would have to have another boolean 'destroyed' for the enemy to tell if it should include it or not and it all becomes a mess. If you think this is more efficient I believe you, but please tell me. 2. to remove it on destruction, each individual Building class would have to notify each individual enemy. I am not experienced in this field, but I do not know a way to do this. If you do, please tell me :) 3. Reusing it would be more efficient, but I have no way to reuse it because once the first enemy is placed no more buildings are 4. I can't (or at least Unity says I can't) remove a 'null' object from a dictionary
If you see any way around any of these, please do tell me! This is basically my first solo project, so any help would be greatly appreciated!
Oh there are a million and one ways to do this but I could mock a couple out for you after lunch. If you cant wait:
One way to do it is to use events
Another is to use callbacks.
Another still is to use a singleton for your caching mechanism and then just either delegate responsibility for clean up or just update it when your characters are "destroyed".
There are all sorts of spawning pool examples online and I suggest thinking about the problem and attempting your own until you get one that doesnt feel clunky.
This in my opinion sounds a little clunky.
I'll be back after lunch with some examples.
If you are still about can you articulate the exact requirements. Because reading back its a little hard from your original post.
So you have buildings. They get destroyed by enemies and on the event that they get destroyed you want what to happen? To know which enemy destroyed them?
Why is their distance relevant?
Why do you need to store the enemies in a dictionary at all?
Still around :). Thanks for sticking around yourself. Essentially, it's like Clash Of Clans - each enemy goes to the closest building to destroy it, and when it's destroyed it has to no longer be in the 'distances' dictionary of any enemies so they attack only existing buildings. This logic occurs in the 'Enemy.cs' class, but the building has no way to access what destroyed it as of now as it itself checks it's own health and destroys itself. I could actually pass through which enemy damaged it, but as I said it needs to be removed from all enemies. The only thing I want to occur is for these destroyed buildings to be removed from the distances dictionary of all enemies. Hope this helps, looking back I realise I didn't quite explain it very well. Thanks for all the help so far.
Ok so I see what you are building now. Can I suggest a different architecture ins$$anonymous$$d?
I think You are overcomplicating this.
So You shouldn't need to keep track of the items within the radius of the buildings you can just use an OverlapSphere
https://docs.unity3d.com/ScriptReference/Physics.OverlapSphere.html
That will do it all for you and you can just instantiate one when you need to evaluate whos in range.
Now with regards to your damage question. You can do it either way
Either put a method on your building type called Damage. That method takes in a sender object of type player.
So void Damage(player Player) which you call from the player like this Building.Damage(self)
Or you can add an attack method to the Player which takes a parameter of the Building its attacking i.e.
void Attack(building: Building) which you call on the Player like this:
Player.Attack(myBuilding)
Can you rephrase your question to be more about solving that problem and I can answer it with a code example.
Answer by sacredgeometry · Aug 09, 2019 at 09:57 PM
So you could rewrite it to be something like this.
Watch Video DEMO
Building
public enum BuildingState {
Alive,
Destroyed
}
public class Building : MonoBehaviour
{
public List<Enemy> Attackers = new List<Enemy>();
private float _health = 1000;
public float Health
{
get
{
return _health;
}
set
{
_health = value;
State = _health > 0 ? BuildingState.Alive : BuildingState.Destroyed;
}
}
public BuildingState State = BuildingState.Alive;
public void Attack(Enemy sender, float damage)
{
if(!Attackers.Contains(sender))
{
Attackers.Add(sender);
}
Health -= damage;
if(State == BuildingState.Destroyed)
{
gameObject.SetActive(false);
Disengage(sender);
}
Debug.Log($"{gameObject.name}: {Health}");
}
public void Disengage(Enemy sender)
{
Attackers.Remove(sender);
}
}
Enemy
public class Enemy : MonoBehaviour
{
public float Radius = 15;
public Building Target;
void Update()
{
if(Input.GetKeyDown(KeyCode.Space))
{
Attack(100);
}
}
public void Attack(float damage)
{
if(Target != null)
{
if(Target.State != BuildingState.Destroyed)
{
Target.Attack(this, damage);
}
else
{
Target.Disengage(this);
Target = GetClosestBuilding();
}
}
else
{
Target = GetClosestBuilding();
if(Target != null) Attack(damage);
}
}
public Building GetClosestBuilding()
{
return GetBuildingsInRange().FirstOrDefault();
}
public IEnumerable<Building> GetBuildingsInRange()
{
var buildings = new List<Building>();
var hitColliders = Physics.OverlapSphere(transform.position, Radius);
return hitColliders
.Where(x => x.tag == "Building")
.Select(collider => collider.gameObject.GetComponent<Building>())
.OrderBy(o => Vector3.Distance(o.transform.position, transform.position));
}
}
Edit: There we go. Have a read, let me know if you have any questions. Honestly using the observer pattern would be neater but I have already been told it was far too complicated once today so let's stick to basic language features.
This would be so much cleaner using Observers or Rx.
Thanks for all the time you put into this! When you say observers, however, do you mean as in delegates? I'm pretty happy to do that. However, this is a big refactor and this project is never going to be released so it's more of a learning curve. I feel like I've learned a lot and I'll definitely put it into effect on my next project - thanks for that - but for now I think I'm gonna plough on ahead. As it's never going to be released, I don't need to optimise everything. Thanks a bunch for all your time though, I'll make sure to plan out everything better on my next project :)
Just a word of warning. Introduction of technical debt because you chose to not refactor early in light of a potentially problematic design choices is more painful than rewriting a bunch of code up front. In fact, by orders of magnitude.
It goes something like this:
You make a bad design choice, then you start implementing on top of that. Soon you start to hit walls and bugs, you start adding workarounds because now the codebase is bigger than it was when you decided to ignore the problem, and so it goes on until the problem basically touches all of your codebase which is now, much larger. This goes on until it becomes literally painful to work on, either because performance issues are killing it or because the code is a soup of spaghetti of work arounds or because the codebase is unnecessarily large for the problems it's trying to solve.
And then you are forced with a pressing question. You have to rewrite anyway but now ins$$anonymous$$d of a few files its hundreds.
Just understand that refactoring early is better than late and accruing tech debt should be understood as what it is. Just pushing work further down the line, not making it disappear. That work may come with some serious interest (i.e. debt accumulation) depending on the particular problem.
Just a friendly warning from a professional software engineer of 12+ years.
Answer by Bunny83 · Aug 10, 2019 at 11:34 AM
Of course using a direct event to remove an element from the dictionary is the most efficient solution as long as you have a back-reference. However if those changes are difficult to implement in your current code, your current solution does work as well but they way you do it is horrible inefficient. The major issue is the usage of the Linq function "ElementAt" inside a loop. Each time you call it you will actually create a new IEnumerable object which will iterate through all elements until index "i" is reached. That means you create "i"-times such an IEnumerable and IEnumerator and they are successive iterated more and more. The complexity is O(n²/2) or just O(n²) since only the highest power is relevant. The biggest issue is the creation of the IEnumerable / IEnumerator instances which need to be garbage collected afterwards.
It's much more effective to do
List<YourKeyType> toBeRemoved = new List<YourKeyType>();
void Remove()
{
toBeRemoved.Clear();
foreach(var kv in distances)
{
if (kv.Key == null)
{
toBeRemoved.Add(kv.Key);
}
}
for(int i = 0; i < toBeRemoved.Count; i++)
{
distances.Remove(toBeRemoved[i]);
}
toBeRemoved.Clear();
}
Depending on how you actually use the dictionary you may call this clean up method only every now and then. Since the Dictionary for each enumerator is a struct enumerator, no garbage should be allocated. Since we reuse the toBeRemoved list no additional garbage should be allocated once the list has grown to the required size.
Note that the enumerable of the dictionary iterates over KeyValuePair<TKey, TValue>
structs.
We just don't know enough about your requirements, how and when you use the dictionary for what exact purpose. Since you call is "distances" I would assume it's something like Dictionary<GameObject, float>
? Why exactuy do you use a dictionary here? Is it possible that you try to add the same object multiple times? If you just need the data to find the closest object a simple List with KeyValuePairs would be enough. When you actually looking for the closest object, just iterate the list backwards with a normal for loop and check for a null value. If it's null you can safely remove it on the fly
Thanks for the reply! There is a lot of conversation in the comments where I explain everything but did not remember to update the question - sorry about that! In the end I opted for an event-based system. Thanks for taking the time to reply though!
Answer by ShadyProductions · Aug 09, 2019 at 05:36 PM
You remove the building from the dictionary the moment the building is destroyed.
I thought about that, but how exactly would it work? The troop damaging the building does not have a way to be notified of its destruction, nor can it remove it after destroyed as you cannot remove something with a value of 'null' from a dictionary. Additionally, the way I see it is once another troop destroys another building how will this troop get access to that information? I've updated the original post to explain this.
The building knows when its being destroyed though doesn't it?
Yes, but how could it communicate to the enemies? Like ShadyProductions said with each building having a list of enemies - would that really be more efficient?
I suppose your dictionary is something like enemy as key and List as value? Then the moment you call Destroy() on the building, you need to get the list dic[enemy].Remove(building); or something similar. It can't be that hard.
The dictionary is in the enemy class with the building as key and distance as value. Are you suggesting that all buildings should also have a list of all enemies? Now that I think about it actually, all the defenses will have to, so should I extend that to all buildings? $$anonymous$$ost importantly, would that be more efficient?
Follow this Question
Related Questions
Multiple Cars not working 1 Answer
Distribute terrain in zones 3 Answers
Why this c# program can not to auto die player 1 Answer
Unity5 filled my SSD? 0 Answers
Generate floor mesh according to walls 0 Answers