• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
WeNeedFocus

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

10 posts in this topic

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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites

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

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

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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
2

Share this post


Link to post
Share on other sites

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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites
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.
0

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  
Followers 0