Jump to content

  • Log In with Google      Sign In   
  • Create Account

Just a simple way to organize Entities in a 2D array.


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 WeNeedFocus   Members   -  Reputation: 154

Like
0Likes
Like

Posted 04 May 2013 - 12:20 PM

So I have two 2D array layers, one of the ground/terrain and another that contains entities/units.

One item can occupy a spot at a time, but since I want some entities to overlap, how can I efficiently do this?

I have already tried doing it with a list, but I don't prefer it since I have to run through the whole list each time I want a specific entity, when in a 2D array I can just do Entities[x,y] and I have the specific entity I want.

No code necessary, just an explanation. Thanks


Edited by WeNeedFocus, 04 May 2013 - 12:21 PM.


Sponsor:

#2 Squared'D   Members   -  Reputation: 2241

Like
0Likes
Like

Posted 05 May 2013 - 06:29 PM

So do you want multiple entities to be able to be in the same place in the entity array. You can do this by having not having an array of entities, but instead have it be an array of an entity container, maybe a list. Ie, when you do Entity[x,y], you'll get a list.

Here's another technique that you can use if you have a maximum number of entities that can use one spot. You can use a 3D array, where the third dimension is depth. You so if your map is 64 x 64 with 3 max entities at one location, you can use a 64 x 64 x 3 array.

I would probably just do an array of list. The list container would be able to check how many items are in it, and you could give it methods for quickly removing items since probably you entities will be moving around and will not stay in one place.

Hope that helps.

Learn all about my current projects and watch some of the game development videos that I've made.

Squared Programming Home

New Personal Journal

 


#3 WeNeedFocus   Members   -  Reputation: 154

Like
0Likes
Like

Posted 05 May 2013 - 07:14 PM

That works, out of curiosity, are there any other ways?

I'll most likely do the array of lists of entities, thanks.



#4 Khatharr   Crossbones+   -  Reputation: 3001

Like
0Likes
Like

Posted 05 May 2013 - 11:00 PM

Another way is: instead of storing entities by location have each entity store its own location and simply store them in an agnostic container. Pick a container that will allow you to quickly locate entities matching a position through iteration.

 

Which method is better depends on what you're doing. Having entities store their own location means that isolating all entities in a specific location takes longer. Having locations store more than one entity means iterating through all entities takes longer.

 

There's also the possibility of hybridization. That is, have a master list of entities which are aware of their own location and also retain a 2D array of containers that point to all entities that occupy each location. This is the most expensive in terms of storage and architecture but has the best access time for any method.


Edited by Khatharr, 05 May 2013 - 11:53 PM.

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

#5 Squared'D   Members   -  Reputation: 2241

Like
0Likes
Like

Posted 06 May 2013 - 12:22 AM

I do agree with Khatharr. You may find that you'll need a 2D array and also a separate list that contains all of your entities. A list of entities is useful when you need to iterate through all entities. Iterating through a 2D array with possible empty nodes each time you need to touch each entity may not be a good thing. Having each entity know it's location can also be a good thing. For example, if an entity dies, if each entity contains each location, it'll be easier to remove from the 2D array.

In my game, I use multiple forms of storage, each optimized for the task. I keep a list of entities for fast iteration, but I also use a Kd-tree(in your case, your 2D array) so I can quickly find things based on location. You don't need one master, one size fits all structure. You can use multiple ones. If you ever use a third-party physics library for example, it will store your entities in yet another way.

But anyway, for your original question, a 2D array of entity containers is probably what you are looking for.

Learn all about my current projects and watch some of the game development videos that I've made.

Squared Programming Home

New Personal Journal

 


#6 WeNeedFocus   Members   -  Reputation: 154

Like
0Likes
Like

Posted 06 May 2013 - 05:18 AM

Another way is: instead of storing entities by location have each entity store its own location and simply store them in an agnostic container. Pick a container that will allow you to quickly locate entities matching a position through iteration.

 

 

Having entities store their own location, was my very first choice, in a list. But it was inefficient since I had to run through the list each time I wanted an entity, so this seems logical.

Sorry, agnostic container? I searched some stuff on google, but there was nothing specific. Is this a some sort of a library, or just a spontaneous word you made?

 

 

There's also the possibility of hybridization. That is, have a master list of entities which are aware of their own location and also retain a 2D array of containers that point to all entities that occupy each location. This is the most expensive in terms of storage and architecture but has the best access time for any method.

 

This seems tough, but I'll consider it as my second option.

 

Thank you guys, if you can just help explain the concept of this agnostic container, I would be grateful.

Also, since almost anything with height will be an entity, and some entities won't update, should I keep them in a different layer?

So there are two types of entities, the ones that stay still (trees), and the ones that move (animals). There is no point to do Entity.Update() if it's a still entity, so it's logical to keep them in two different layers, right? But the problem is, since they're both entities, it's like separating skin from bone, I don't like the idea of two layers for entities.

Is there another method for this as well (or should I make a new thread)?


Edited by WeNeedFocus, 06 May 2013 - 05:21 AM.


#7 Juliean   GDNet+   -  Reputation: 2607

Like
2Likes
Like

Posted 06 May 2013 - 06:15 AM

This seems tough, but I'll consider it as my second option.

 

Thats not really that tough, and it also is something that applies to "everyday" game programming in general, so you better get used to that.The concept of having a plain list of objects, but still organizing those objects in some other datastruct for different uses should appeal naturally. Just imagine a scene graph, or space partitioning data structure like an octree or quadtree. One would never store objects directly and only in such a structure - unless you feel cool with traversing the whole tree for simple tasks as Update()-ing those objects.

 

Just think about it as one place where the objects are stored and truley belong. Then there are theoretically unlimited other containers that might store those objects, specially laid out for a certain processing task - be it frustum culling, collision, ... . Just as you need it.


Edited by Juliean, 06 May 2013 - 06:15 AM.


#8 Khatharr   Crossbones+   -  Reputation: 3001

Like
0Likes
Like

Posted 06 May 2013 - 02:46 PM

Sorry, agnostic container? I searched some stuff on google, but there was nothing specific. Is this a some sort of a library, or just a spontaneous word you made?

From the Greek:

a - negating prefix
gnosis - 'knowledge'

Agnostic essentially means 'without knowledge'.

When something in programming terms is described as agnostic it usually means that it doesn't care about something relevant to the subject. In this case it would be a container that doesn't care about the position of the objects it stores. If something is described as type agnostic that means it doesn't care about type, etc. I think the most common use I've heard of it in programming is 'platform agnostic', which describes something that is compatible with any platform because it doesn't need any information about the platform in order to run. For instance, the TCP/IP suite is platform agnostic. It runs the same on a mac, a PC or a playstation.
void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

#9 Squared'D   Members   -  Reputation: 2241

Like
0Likes
Like

Posted 06 May 2013 - 06:37 PM

If you have two types of entities, one that requires updates and one that doesn't, you can put all of your entities in the 2D array, that way you have everything sorted by location. Then you can also have a separate list that contains only the updatable entities. When you do an update, just look at the updatable list. That way you won't have to check everything. Storing things in multiple places where they can be most effeciently used is a good idea. Calling an empty virtual Update() method is just a waste so your two layer approach is very logical.

Learn all about my current projects and watch some of the game development videos that I've made.

Squared Programming Home

New Personal Journal

 


#10 WeNeedFocus   Members   -  Reputation: 154

Like
0Likes
Like

Posted 12 May 2013 - 08:11 AM

Thanks guys, but, I'm facing another problem.

What if the entity is meant to occupy more than one space? If for example a bonfire is 2x2 tiles wide, how do i fit that into the 2 dimentional entities array?

Should I just make it into a list instead of a 2d array, and put Point Location; so the entity will contain it's own location? But when I want to retrieve a certain entity, I have to go loop through the whole list... Is there a better way to do this?

 

I thought of separating entities into different parts: TopLeftOfBonFire, TopRightOfBonFire, BottomLeftOfBonFire, BottomRightOfBonFire, so each one can occupy one tile. But then I faced the problem with Units. Units are updated, so separating them into parts like this is not efficient.

Please help, Davud



#11 Squared'D   Members   -  Reputation: 2241

Like
0Likes
Like

Posted 15 May 2013 - 10:48 PM

Well let's think this out. First, what are your use cases and why do you need the array? Is it for collision detection, quick selection with a mouse, displaying the entities, or all of the above? Some entities can take up more than once space. Is this the same for units or just buildings? If a building is at a location, can a unit be there? Can more than one building be at the same location? These are questions that you need to ask yourself. If only buildings will take more than one location and are static, should they be treated the same as moving units?

For big objects, you can store them indirectly in the map. Like you stated, you can have topright, bottomleft, etc objects that just serve as placeholders. They're not real entities, and they point back to their parent which is the real entity. You'll still only need to update an entity only once since the place holders aren't real entities and don't need to go in the main entity list. When something moves, just move the real entity, and you can have it move it's place holders. That's just one option.

Learn all about my current projects and watch some of the game development videos that I've made.

Squared Programming Home

New Personal Journal

 





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS