Sign in to follow this  
ravinDavin

Complexity of Dictionary - C#

Recommended Posts

Hey, I am creating a game using XNA 4.0 and C#.

I am currently trying to create a HUD. I ended up going with 2 classes to create the HUD. It will be easier to show you than explain:

[code]
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using CGPLibrary.Sprites;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework;

namespace CGPLibrary
{
public class HUDElement
{
protected Sprite element;
protected Texture2D texture;
protected int width, height;
protected Vector2 m_position;
protected int offsetX, offsetY;
protected GameWindow Window;
protected Color color;


public enum Position
{
TOP_LEFT, TOP_RIGHT, TOP_MIDDLE, MIDDLE_LEFT, MIDDLE_RIGHT, MIDDLE, BOTTOM_LEFT, BOTTOM_RIGHT, BOTTOM_MIDDLE

}

public enum ELEM_TYPE { Health, Armour, H_ABackground, Life }ELEM_TYPE elementType;

public HUDElement(Sprite sprite, GameWindow window)
{
color = sprite.sprColor;
Window = window;
offsetX = 0;
offsetY = 0;
element = sprite;
texture = sprite.spTexture;
width = sprite.Width;
height = sprite.Height;
}

public Sprite spr { get { return element; } }
public int Width { get { return width; } }
public int Height { get { return height; } }
public Color elemColor { get { return color; } set { color = value; } }
public Texture2D elemText { get { return texture; } }
public ELEM_TYPE type { get { return elementType; } set { elementType = value; } }
public Vector2 position { get { return m_position; } }
public int xOffset { get { return offsetX; } set { offsetX = value; } }
public int yOffset { get { return offsetY; } set { offsetY = value; } }

public void setPosition(Position pos)
{
switch (pos)
{
case Position.TOP_LEFT:
m_position = new Vector2(offsetX, offsetY);
break;
case Position.TOP_MIDDLE:
m_position = new Vector2((Window.ClientBounds.Width / 2 - texture.Width / 2) + offsetX, offsetY);
break;
case Position.TOP_RIGHT:
m_position = new Vector2((Window.ClientBounds.Width - texture.Width) + offsetX, offsetY);
break;

case Position.MIDDLE_LEFT:
m_position = new Vector2(offsetX, (Window.ClientBounds.Height / 2 - texture.Height / 2) + offsetY);
break;
case Position.MIDDLE:
m_position = new Vector2((Window.ClientBounds.Width / 2 - texture.Width / 2) + offsetX, (Window.ClientBounds.Height / 2 - texture.Height / 2) + offsetY);
break;
case Position.MIDDLE_RIGHT:
m_position = new Vector2((Window.ClientBounds.Width - texture.Width) + offsetX, (Window.ClientBounds.Height / 2 - texture.Height / 2) + offsetY);
break;

case Position.BOTTOM_LEFT:
m_position = new Vector2(offsetX, (Window.ClientBounds.Height - texture.Height) + offsetY);
break;
case Position.BOTTOM_MIDDLE:
m_position = new Vector2((Window.ClientBounds.Width / 2 - texture.Width / 2) + offsetX, (Window.ClientBounds.Height - texture.Height) + offsetY);
break;
case Position.BOTTOM_RIGHT:
m_position = new Vector2((Window.ClientBounds.Width - texture.Width) + offsetX, (Window.ClientBounds.Height - texture.Height) + offsetY);
break;

}

}
}
}

[/code]
[code]
using Microsoft.Xna.Framework;
using System.Collections.Generic;
using HeadStacker;
using CGPLibrary.Sprites;
using Microsoft.Xna.Framework.Graphics;
using CGPLibrary.Entities;


namespace CGPLibrary
{
/// <summary>
/// This is a game component that implements IUpdateable.
/// </summary>
public class HUD : DrawableGameComponent
{
protected Dictionary<HUDElement.ELEM_TYPE, HUDElement> hudElements;
HumanPlayer player;
protected SpriteBatch batch;
public Main game;

public HUD(Main game)
: base(game)
{
hudElements = new Dictionary<HUDElement.ELEM_TYPE, HUDElement>();
this.game = game;
player =game.human;
this.batch = game.spriteBatch;

}


public void addHudElement(HUDElement elem)
{
hudElements.Add(elem.type, elem);


}
public override void Draw(GameTime gameTime)
{
batch.Begin();
batch.Draw(hudElements[HUDElement.ELEM_TYPE.Life].elemText, hudElements[HUDElement.ELEM_TYPE.Life].position, hudElements[HUDElement.ELEM_TYPE.Life].spr.sourceRect,
hudElements[HUDElement.ELEM_TYPE.Life].elemColor, 0f, Vector2.Zero, hudElements[HUDElement.ELEM_TYPE.Life].spr.Scale,SpriteEffects.None,0f);


batch.Draw(hudElements[HUDElement.ELEM_TYPE.H_ABackground].elemText, hudElements[HUDElement.ELEM_TYPE.H_ABackground].position,null,
hudElements[HUDElement.ELEM_TYPE.H_ABackground].elemColor,0f,Vector2.Zero,hudElements[HUDElement.ELEM_TYPE.H_ABackground].spr.Scale,SpriteEffects.None,0f);



batch.Draw(hudElements[HUDElement.ELEM_TYPE.Health].elemText, hudElements[HUDElement.ELEM_TYPE.Health].position,
new Rectangle(0,0,(int)(hudElements[HUDElement.ELEM_TYPE.Health].Width * ((double)player.health/100)),hudElements[HUDElement.ELEM_TYPE.Health].Height)
,hudElements[HUDElement.ELEM_TYPE.Health].elemColor,0f,Vector2.Zero,hudElements[HUDElement.ELEM_TYPE.Health].spr.Scale,SpriteEffects.None,0f);



batch.Draw(hudElements[HUDElement.ELEM_TYPE.Armour].elemText, hudElements[HUDElement.ELEM_TYPE.Armour].position,
new Rectangle(0, 0, (int)(hudElements[HUDElement.ELEM_TYPE.Armour].Width * ((double)player.armour / 100)), hudElements[HUDElement.ELEM_TYPE.Armour].Height)
, hudElements[HUDElement.ELEM_TYPE.Armour].elemColor,0f, Vector2.Zero, hudElements[HUDElement.ELEM_TYPE.Armour].spr.Scale, SpriteEffects.None, 0f);
batch.End();

base.Draw(gameTime);
}
public override void Update(GameTime gameTime)
{
float elapsed = (float)gameTime.ElapsedGameTime.TotalSeconds;
hudElements[HUDElement.ELEM_TYPE.Life].spr.animate(elapsed);
// hudElements[HUDElement.ELEM_TYPE.Health].elemText = player.currentWeapon.texture;

base.Update(gameTime);
}
}
}


[/code]

You can see in the draw method, I find each element inside the Dictionary and draw it. My question is, will this cause any kind of overhead? I think I read that the Dictionary is normally O( c )but that was using the .containsKey() method. Will using the [] notation cause any slowdowns(or increased performance)?

Share this post


Link to post
Share on other sites
I can't speak to the efficiency of your system, but your code makes my eyes bleed. Why don't you try something like this?

[code]

HudElement element = hudElements[HUDElement.ELEM_TYPE.Life];
batch.Draw(element.elemText, element.position, element.spr.sourceRect, element.elemColor, 0f, Vector2.Zero, element.spr.Scale,SpriteEffects.None,0f);

[/code]

Share this post


Link to post
Share on other sites
[quote name='Suspense' timestamp='1318699438' post='4872905']
I can't speak to the efficiency of your system, but your code makes my eyes bleed. Why don't you try something like this?

[code]

HudElement element = hudElements[HUDElement.ELEM_TYPE.Life];
batch.Draw(element.elemText, element.position, element.spr.sourceRect, element.elemColor, 0f, Vector2.Zero, element.spr.Scale,SpriteEffects.None,0f);

[/code]
[/quote]

Haha, It makes mine bleed , also, I have no idea why I didn't do that in the first place. Thanks for that

Share this post


Link to post
Share on other sites
[code]
HudElement life = hudElements[HUDElement.ELEM_TYPE.Life];
batch.Draw(life.elemText, life.position, life.spr.sourceRect, life.elemColor, 0f, Vector2.Zero, life.spr.Scale,SpriteEffects.None,0f);
//or
HudElement HUDLife = hudElements[HUDElement.ELEM_TYPE.Life];
batch.Draw(HUDLife.elemText, HUDLife.position, HUDLife.spr.sourceRect, HUDLife.elemColor, 0f, Vector2.Zero, HUDLife.spr.Scale,SpriteEffects.None,0f);
[/code]

I don't know. Suspense's code definitely does the job. But I guess, if it were me, I'd like a little more description.

Share this post


Link to post
Share on other sites
All of the above would work better if it were turned the other way round:[code]
class HudElement {
...
public void RenderToSpriteBatch(SpriteBatch s) {
s.draw(elemText, position, spr.sourceRect, elemColor, 0f, Vector2.Zero, spr.Scale,SpriteEffects.None, 0f);
}
...
};[/code]

Then:
[code]...
public override void Draw(GameTime gameTime)
{
batch.Begin();
foreach(KeyValuePair<HUDElement.ELEM_TYPE, HUDElement> e in hudElements) {
e.Value.RenderToSpriteBatch(batch);
}
batch.End();
...[/code]

Share this post


Link to post
Share on other sites
[quote name='Alpha_ProgDes' timestamp='1318700190' post='4872909']
[code]
HudElement life = hudElements[HUDElement.ELEM_TYPE.Life];
batch.Draw(life.elemText, life.position, life.spr.sourceRect, life.elemColor, 0f, Vector2.Zero, life.spr.Scale,SpriteEffects.None,0f);
//or
HudElement HUDLife = hudElements[HUDElement.ELEM_TYPE.Life];
batch.Draw(HUDLife.elemText, HUDLife.position, HUDLife.spr.sourceRect, HUDLife.elemColor, 0f, Vector2.Zero, HUDLife.spr.Scale,SpriteEffects.None,0f);
[/code]

I don't know. Suspense's code definitely does the job. But I guess, if it were me, I'd like a little more description.
[/quote]

Ye thanks, I did it the way you did aswell after I read Suspense's reply. I also like some description :D.. He was probably just generalising anyway.

Share this post


Link to post
Share on other sites
Speaking to your question, I'd be surprised --extremely surprised-- if: aDictionary.containsKey("blah") was faster or improved in any way than aDictionary["blah"]. If anything, aDictionary.containsKey("blah") would have to do a scan of all keys until it reached the key it was looking for. aDictionary["blah"], IIRC, is the better choice of the two. And definitely should be still O(c).

Share this post


Link to post
Share on other sites
[quote name='Antheus' timestamp='1318700675' post='4872912']
All of the above would work better if it were turned the other way round:[code]
class HudElement {
...
public void RenderToSpriteBatch(SpriteBatch s) {
s.draw(elemText, position, spr.sourceRect, elemColor, 0f, Vector2.Zero, spr.Scale,SpriteEffects.None, 0f);
}
...
};[/code]

Then:
[code]...
public override void Draw(GameTime gameTime)
{
batch.Begin();
foreach(KeyValuePair<HUDElement.ELEM_TYPE, HUDElement> e in hudElements) {
e.Value.RenderToSpriteBatch(batch);
}
batch.End();
...[/code]
[/quote]


Ahhh cool, I was looking for a way to do it all at once after I got it working. Thanks!

Share this post


Link to post
Share on other sites
[quote name='Antheus' timestamp='1318700675' post='4872912']
All of the above would work better if it were turned the other way round:[code]
class HudElement {
...
public void RenderToSpriteBatch(SpriteBatch s) {
s.draw(elemText, position, spr.sourceRect, elemColor, 0f, Vector2.Zero, spr.Scale,SpriteEffects.None, 0f);
}
...
};[/code]

Then:
[code]...
public override void Draw(GameTime gameTime)
{
batch.Begin();
foreach(KeyValuePair<HUDElement.ELEM_TYPE, HUDElement> e in hudElements) {
e.Value.RenderToSpriteBatch(batch);
}
batch.End();
...[/code]
[/quote]
Out of curiosity, is the way you structured your code because of how XNA is structured? Or would you take that approach regardless of the game-dev library you used?

Share this post


Link to post
Share on other sites
[quote name='Alpha_ProgDes' timestamp='1318700912' post='4872917']
Out of curiosity, is the way you structured your code because of how XNA is structured? Or would you take that approach regardless of the game-dev library you used?[/quote]

It balances the encapsulation and coupling.

- HudElement doesn't need to expose its internals. It could, for other reasons, but in this case it isn't needed. So HudElement knows how to render itself.
- The container that holds these isn't all that relevant either. If one were to choose array, ArrayList, ..., anything iterable, code remains same (almost).
- Elements to be rendered don't need to be explicitly named. Just render entire container.

Later, one could get fancy. If Hud had to be rendered to something else, one could use delegates or somesuch. If there were multiple containers one could pass the iterator, perhaps custom one.

But code above groups orthogonal concepts.

Advanced topics:
- It's aligned with Inversion of Control, which tends to minimize coupling.
- HudElement is now isolated. Aside from being directly reusable on any SpriteBatch, it can be also tested in isolation.
- foreach contains more contextual information and hints that container is not "clever". If we need something more (specific ordering, subset of elements, ...), it needs to be stated specifically.

Share this post


Link to post
Share on other sites
[quote name='Antheus' timestamp='1318701539' post='4872922']
[quote name='Alpha_ProgDes' timestamp='1318700912' post='4872917']
Out of curiosity, is the way you structured your code because of how XNA is structured? Or would you take that approach regardless of the game-dev library you used?[/quote]

It balances the encapsulation and coupling.

- HudElement doesn't need to expose its internals. It could, for other reasons, but in this case it isn't needed. So HudElement knows how to render itself.
- The container that holds these isn't all that relevant either. If one were to choose array, ArrayList, ..., anything iterable, code remains same (almost).
- Elements to be rendered don't need to be explicitly named. Just render entire container.

Later, one could get fancy. If Hud had to be rendered to something else, one could use delegates or somesuch. If there were multiple containers one could pass the iterator, perhaps custom one.

But code above groups orthogonal concepts.

Advanced topics:
- It's aligned with Inversion of Control, which tends to minimize coupling.
- HudElement is now isolated. Aside from being directly reusable on any SpriteBatch, it can be also tested in isolation.
- foreach contains more contextual information and hints that container is not "clever". If we need something more (specific ordering, subset of elements, ...), it needs to be stated specifically.
[/quote]

Ah, I can't really use your way, I need to be able to have a separate draw method for the different elements so I can calculate the sourcewidth of the Healthbar/Armour etc. Now I think of it, that was the reason for the HUDElements not drawing themselve in the first place, they all need to be drawn differently

Share this post


Link to post
Share on other sites
[quote name='Alpha_ProgDes' timestamp='1318700753' post='4872914']
Speaking to your question, I'd be surprised --extremely surprised-- if: aDictionary.containsKey("blah") was faster or improved in any way than aDictionary["blah"]. If anything, aDictionary.containsKey("blah") would have to do a scan of all keys until it reached the key it was looking for. aDictionary["blah"], IIRC, is the better choice of the two. And definitely should be still O©.
[/quote]
The issue with accessing the Dictionary with the key directly as in: Dictionary[key] is that if the key is not found, it will throw a KeyNotFoundException. The safest method is to actually use a TryGetValue(), which internally does a ContainsKey() lookup and then indexes the dictionary to return the item. It's faster than doing ContainsKey/lookup yourself since you only need a single key lookup call, not two.

In summary,
[list][*]Dictionary[key] : fastest, key not found throws exception[*]Dictionary.TryGetValue() : slightly slower. key not found returns null[*]Dictionary.ContainsKey/Dictionary[key] : equivalent to Dictionary.TryGetValue(), but slower.[/list]

Share this post


Link to post
Share on other sites
[code]
public enum Position
{
TOP_LEFT, TOP_RIGHT, TOP_MIDDLE, MIDDLE_LEFT, MIDDLE_RIGHT, MIDDLE, BOTTOM_LEFT, BOTTOM_RIGHT, BOTTOM_MIDDLE
}

public void setPosition(Position pos)
{
switch (pos)
{
case Position.TOP_LEFT:
m_position = new Vector2(offsetX, offsetY);
break;
case Position.TOP_MIDDLE:
m_position = new Vector2((Window.ClientBounds.Width / 2 - texture.Width / 2) + offsetX, offsetY);
break;
case Position.TOP_RIGHT:
m_position = new Vector2((Window.ClientBounds.Width - texture.Width) + offsetX, offsetY);
break;

case Position.MIDDLE_LEFT:
m_position = new Vector2(offsetX, (Window.ClientBounds.Height / 2 - texture.Height / 2) + offsetY);
break;
case Position.MIDDLE:
m_position = new Vector2((Window.ClientBounds.Width / 2 - texture.Width / 2) + offsetX, (Window.ClientBounds.Height / 2 - texture.Height / 2) + offsetY);
break;
case Position.MIDDLE_RIGHT:
m_position = new Vector2((Window.ClientBounds.Width - texture.Width) + offsetX, (Window.ClientBounds.Height / 2 - texture.Height / 2) + offsetY);
break;

case Position.BOTTOM_LEFT:
m_position = new Vector2(offsetX, (Window.ClientBounds.Height - texture.Height) + offsetY);
break;
case Position.BOTTOM_MIDDLE:
m_position = new Vector2((Window.ClientBounds.Width / 2 - texture.Width / 2) + offsetX, (Window.ClientBounds.Height - texture.Height) + offsetY);
break;
case Position.BOTTOM_RIGHT:
m_position = new Vector2((Window.ClientBounds.Width - texture.Width) + offsetX, (Window.ClientBounds.Height - texture.Height) + offsetY);
break;
}
}
[/code]

Ew. Why not something like:

[code]
private static int pixels<TEnum>(this TEnum alignment, int size) {
return ((int)alignment * size) / 2;
}

public enum VerticalAlignment { TOP = 0, MIDDLE, BOTTOM };
public enum HorizontalAlignment { LEFT = 0, MIDDLE, RIGHT };
public void setPosition(VerticalAlignment v, HorizontalAlignment h) {
m_position = new Vector2(
offsetX + h.pixels(Window.ClientBounds.Width - texture.Width),
offsetY + v.pixels(Window.ClientBounds.Height - texture.Height)
);
}
[/code]

(Or you could make actual classes with some pre-defined instances instead of banging enums into submission)

Share this post


Link to post
Share on other sites
[quote name='Zahlman' timestamp='1318840210' post='4873376']
[code]
public enum Position
{
TOP_LEFT, TOP_RIGHT, TOP_MIDDLE, MIDDLE_LEFT, MIDDLE_RIGHT, MIDDLE, BOTTOM_LEFT, BOTTOM_RIGHT, BOTTOM_MIDDLE
}

public void setPosition(Position pos)
{
switch (pos)
{
case Position.TOP_LEFT:
m_position = new Vector2(offsetX, offsetY);
break;
case Position.TOP_MIDDLE:
m_position = new Vector2((Window.ClientBounds.Width / 2 - texture.Width / 2) + offsetX, offsetY);
break;
case Position.TOP_RIGHT:
m_position = new Vector2((Window.ClientBounds.Width - texture.Width) + offsetX, offsetY);
break;

case Position.MIDDLE_LEFT:
m_position = new Vector2(offsetX, (Window.ClientBounds.Height / 2 - texture.Height / 2) + offsetY);
break;
case Position.MIDDLE:
m_position = new Vector2((Window.ClientBounds.Width / 2 - texture.Width / 2) + offsetX, (Window.ClientBounds.Height / 2 - texture.Height / 2) + offsetY);
break;
case Position.MIDDLE_RIGHT:
m_position = new Vector2((Window.ClientBounds.Width - texture.Width) + offsetX, (Window.ClientBounds.Height / 2 - texture.Height / 2) + offsetY);
break;

case Position.BOTTOM_LEFT:
m_position = new Vector2(offsetX, (Window.ClientBounds.Height - texture.Height) + offsetY);
break;
case Position.BOTTOM_MIDDLE:
m_position = new Vector2((Window.ClientBounds.Width / 2 - texture.Width / 2) + offsetX, (Window.ClientBounds.Height - texture.Height) + offsetY);
break;
case Position.BOTTOM_RIGHT:
m_position = new Vector2((Window.ClientBounds.Width - texture.Width) + offsetX, (Window.ClientBounds.Height - texture.Height) + offsetY);
break;
}
}
[/code]

Ew. Why not something like:

[code]
private static int pixels<TEnum>(this TEnum alignment, int size) {
return ((int)alignment * size) / 2;
}

public enum VerticalAlignment { TOP = 0, MIDDLE, BOTTOM };
public enum HorizontalAlignment { LEFT = 0, MIDDLE, RIGHT };
public void setPosition(VerticalAlignment v, HorizontalAlignment h) {
m_position = new Vector2(
offsetX + h.pixels(Window.ClientBounds.Width - texture.Width),
offsetY + v.pixels(Window.ClientBounds.Height - texture.Height)
);
}
[/code]

(Or you could make actual classes with some pre-defined instances instead of banging enums into submission)
[/quote]

Hi, sorry for the late reply, but I have never seen this before, do you have any links to explanations to what this is/how it works?

Share this post


Link to post
Share on other sites
[quote name='Zahlman' timestamp='1318840210' post='4873376']
Ew. Why not something like:

[code]
private static int pixels<TEnum>(this TEnum alignment, int size) {
return ((int)alignment * size) / 2;
}

public enum VerticalAlignment { TOP = 0, MIDDLE, BOTTOM };
public enum HorizontalAlignment { LEFT = 0, MIDDLE, RIGHT };
public void setPosition(VerticalAlignment v, HorizontalAlignment h) {
m_position = new Vector2(
offsetX + h.pixels(Window.ClientBounds.Width - texture.Width),
offsetY + v.pixels(Window.ClientBounds.Height - texture.Height)
);
}
[/code]

[/quote]
I didn't know you can generify extension methods...

That is quite clever. He treates enums as a int. He then declared a extension method on a generic, and uses it on a int in this case. Awesome!

This is some mind bending language hackery.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this