Sign in to follow this  
Alex1011

Organise Entities in a 2D Game

Recommended Posts

Hey guys,

 

I'm currently working on a 2D strategy game with a two dimensional grid but i wonder if my current approach of organising entities is suitable or could be improved. Im using C++(11) and SFML.

 

The map's size will be about 400*400 fields. I divided it into smaller chunks (~40*40) and will only render the corresponding ones.

 

These are the requirements of my container:

- insert / delete objects (seldom)

- change values of existing objects (often)

- access by coordinates

 

Therefore i chose a std::list to store unique_ptrs on the entitie's instance because inserting/deleting objects in a list is easier,

and another container with pointers on the unique_ptr pointers to access them without iterating through the whole list.

 

This is the second container:

std::vector<std::vector<std::vector<std::unique_ptr<mapObject>*>>> mMapObjectPointers;

-> mMapObject[X][Y][Multiple Objects on this field]

 

All Entities are derived from "mapObjects". I think there will be 400-2000 entities in total, that's why im trying to avoid using a search algorithm.

I'm pretty new to game programming and just want to improve my skills smile.png So please feel free to give a constructive criticism.

 

(I read two books, a basic one and the "SFML Game Development"-Book, and serveral tutorials on the internet, but couldn't find any solution to a smiliar problem. If you have good articles about this topic, feel free to post it.)

Share this post


Link to post
Share on other sites

Therefore i chose a std::list to store unique_ptrs on the entitie's instance because inserting/deleting objects in a list is easier,
and another container with pointers on the unique_ptr pointers to access them without iterating through the whole list.

 

std::list is a linked list implementation. It's optimized for frequent insertion/deletion (something you say is seldom). They are "relatively" slow for iteration due to cache misses - the nodes can be scattered around various places in memory. 400-2000 entities is few enough that it probably won't matter though (not to mention your map objects appear to be allocated from the heap too, so they'll be scattered about memory). By default I would have just used a vector based on your requirements, but list will probably be fine too.

 

 


This is the second container:

std::vector<std::vector<std::vector<std::unique_ptr<mapObject>*>>> mMapObjectPointers;
-> mMapObject[X][Y][Multiple Objects on this field]

 

 

Are these supposed to be the same objects than those in your std::list? If so, you can't use unique_ptr here, they should be raw pointers instead (and lifetime ownership is controlled by the unique_ptrs in your master std::list). unique_ptr implies (unique) ownership.

 

And assuming your map is not dynamically resizable during gameplay, you should just use a fixed array, not a vector of vectors.

 

In fact, if your gameboard is 400x400, that's 160000 squares, and you only have 400-2000 entities. So most of those squares are empty. At most, 1.25% are occupied. I would be tempted to use some sort of sparse storage instead, i.e. only store a vector of objects where there is a square with objects in it. You could use an associative container like std::unordered_map for this. They key would be the [x,y] coordinate (you'll need to provide a custom hash function for this, or merge the two coordinates into a single int or something), and the value would be a vector of raw mapObject pointers.

 

Alternatively, you could store the [x,y] coordinate on mapObject and implement some kind of spatial partitioning to allow finding an object quickly by [x,y].

Edited by phil_t

Share this post


Link to post
Share on other sites

Why only one?

 

Most games have multiple representations of the game objects with only one copy of the main object itself.  Pointers are great.

 

 

Typically this means large pools of assets -- your main collection of entities.  These don't move around, but the data in them changes.

 

Then you can build other tools and collections that work with pointers to these objects.

 

Then your spatial grid might be a loose quadtree that has pointers back to the primary objects. When an object moves the function that handles movement can update both the spatial tree information and the object's internal position details.  It also allows you to build objects that don't exist on the spatial tree. 

 

Games will often have several types of these trees.  A tree for physics, a similar but different tree for pathfinding and object footprints, a similar but different tree for rendering and occlusion culling, and so on.

Share this post


Link to post
Share on other sites

These are the requirements of my container:
- insert / delete objects (seldom)
- change values of existing objects (often)
- access by coordinates

 

Access by coordinates could easily be wrapped into a function. Since it's possible that there are multiple objects at a specific coordinate, you can write a function like:

 

std::vector<Object*> objectsAtLocation = GetObjectsAtLocation(mapData, location);
 

...looking up all the objects at a specific map cell in a single iteration of the array. 2000 is a small amount.

 

Therefore i chose a std::list to store unique_ptrs on the entitie's instance


Why unique pointers within a container? The container already manages the memory for you, using unique_ptrs is redundant - unless you are using polymorphism, in which case, pointers/unique_ptrs inside a container is necessary.
 

Therefore i chose a std::list to store unique_ptrs on the entitie's instance because inserting/deleting objects in a list is easier,

But you said you insert/delete objects seldomly, so use a vector, and write a couple of helper functions for insertion/deletion.

Does the order of the elements in the container matter? If not, swap-and-pop them - it's very efficient.
 

This is the second container:
std::vector<std::vector<std::vector<std::unique_ptr<mapObject>*>>> mMapObjectPointers;
-> mMapObject[X][Y][Multiple Objects on this field]


Ouch. How about this?

struct MapCell
{
    std::vector<std::weak_ptr<Object>> objects; //Non-owning pointers.
};

std::vector<MapCell> map;
map.resize(MapWidth * MapHeight);

Use a one-dimensional array, and treat it as two-dimensional when you need to.

Like this:

size_t index = (y * MapWidth) + x;
map[index] = ...;

All Entities are derived from "mapObjects". I think there will be 400-2000 entities in total

400-2000 entities per map, sharing two or three derived classes?
 

that's why im trying to avoid using a search algorithm.

When learning, just do the simplest thing that works until it no longer works fast enough. When I don't have experience, it's easier for me to get caught up in "Oh, I need some super uber clever way of doing things, because certainly doing it the brute force way would be too slow...", but computers nowadays are ridiculously powerful, and 2000 entities is still a tiny amount.

You can probably find your elements quick enough by iterating over each element in the array but, if not, you can easily look into alternative optimizations at that point in development, and at this point in development focus on making the game logic. Programmers are notoriously bad at predicting what parts of our code will be the bottlenecks - which is why we've invented tools (profilers) to tell us.

You don't need to do your logic every frame - you do rendering (drawing) every frame, but logic only X times a second, or logic only in response to certain actions.

Share this post


Link to post
Share on other sites
Are these supposed to be the same objects than those in your std::list? If so, you can't use unique_ptr here, they should be raw pointers instead (and lifetime ownership is controlled by the unique_ptrs in your master std::list). unique_ptr implies (unique) ownership.

 

No. My idea was to have unique_ptrs in the list to control theire lifetime, and the vector should contain raw pointers on the unique_ptrs.

 

 

Why unique pointers within a container? The container already manages the memory for you, using unique_ptrs is redundant - unless you are using polymorphism, in which case, pointers/unique_ptrs inside a container is necessary.

Yes. I'm using polymorphism.

 

400-2000 entities per map, sharing two or three derived classes?

I'm using the following structure:

mapObject

  -> structure

      -> town

      - >...

  -> movable

      -> army

      -> ...

 

 

Does the order of the elements in the container matter? If not, swap-and-pop them - it's very efficient.

No, it doesn't matter. But it could matter, when i would take another approach, f.ex. quicksort for coordinates.

 

 

And assuming your map is not dynamically resizable during gameplay, you should just use a fixed array, not a vector of vectors.

Yes it has a fixed size.

 

 

As a result of your answers, i will rethink my storage and will probably change it to an one-dimensional structure and use a suitable search-algorithm. I don't think that there will be much more than 2000 entities, maybe the map will be smaller. So this seems to be the better approach!

 

 

Quote

This is the second container:
std::vector<std::vector<std::vector<std::unique_ptr<mapObject>*>>> mMapObjectPointers;
-> mMapObject[X][Y][Multiple Objects on this field]


Ouch. How about this?

 

Could you explain, why a 3D/2D vector is an unfavourable?

 

 

Thank you for your informative answers!

 

Share this post


Link to post
Share on other sites

No. My idea was to have unique_ptrs in the list to control theire lifetime, and the vector should contain raw pointers on the unique_ptrs.


If all you need it a bag to hold onto references for lifetimes, a vector is almost the definition of what you need. A std::list is almost always the utterly wrong data structure to use; in the cases where a linked list is right, a std::list is still wrong. Just forget that it ever existed. While you're at it, forget std::map and std::set, too, and prefer unordered_map, unordered_set, or boost's flat_map and flat_set.

I'm using the following structure:
mapObject
  -> structure
      -> town
      - >...
  -> movable
      -> army
      -> ...


Why not have separate arrays/vectors for towns and armies? They have very little overlap in purpose or functionality in most games I'm familiar with compared to the amount of functionality that differs between them, so using a single class hierarchy for both is usually a bad use of OOP.

If there is a good chunk of code that's the same, consider a further split, e.g. a vector of town data, a vector of army data, and then a vector of drawable map object data (and more vectors for any other discrete chunks of common functionality/data). That then also lets you add all kinds of other things that can be drawn that are utterly unlike towns or armies, which may be useful. This approach is a form of component-based design.

Could you explain, why a 3D/2D vector is an unfavourable?


A vector-of-vectors is _not_ a 2D vector. A 2D structure would have a height and a width. A vector-of-vectors has a height and many (possibly all different) widths. These widths can get out of sync in cases where you really need them to be the same. The structure overall is not contiguous in memory. There's some mild overhead in tracking all the vector state for each row.

Share this post


Link to post
Share on other sites

What Sean said. happy.png 

Since I already typed it out before reading his response:

 

Could you explain, why a 3D/2D vector is an unfavourable?

 
Sure. First, let me clarify: I had two nested, abd you had three vectors nested, but speaking of the code logic, you had a "2D" vector of map cells (and each map cell had a vector), and I had a "1D" vector of map cells, and each map cell had a vector. I'm not arguing against each cell containing a vector.
 
Also, let me clarify that the "ouch" comment was the declaration:

std::vector<std::vector<std::vector<std::unique_ptr<mapObject>*>>> mMapObjectPointers;

I find that not very legible. Even if I was using the same thing, I'd rewrite it to show code intention more.

struct MapCell
{
    std::vector<std::unique_ptr<MapObject*>> objects;
};
 
typedef std::vector<std::vector<MapCell>> MapCells;
MapCells mapCells;

Virtually the same thing (only one minor usage difference), just easier for me personally to read, especially when passing into functions by reference.
 
Alrighty, onward! So, setting aside the map cells, what's the differences between using:

std::vector<int> blah(Width*Height);

And:

std::vector<std::vector<int>> blah;

 
First, an std::vector<std::vector<>> isn't a 2D array. It's an array-of-arrays. This means that each "row" can be a different length... it doesn't enforce squareness/rectangleness! This is especially significant if you resize the arrays (for example, different maps having difference sizes) - you have to make sure you resize all of them; you have to keep them in sync.
 
Second, remember that std::vector<> allocates and manages a chunk of memory for you. Doing std::vector<std::vector<>> means you are allocating many smaller chunks of memory scattered throughout the RAM, instead of one chunk of memory (adding up to the same amount, total) in one location in the RAM. This *might* be slower, in some circumstances. In this situation, I wouldn't worry about it at all, as it probably doesn't matter in your case, but it's important to know as a "difference" between them. 
 
Third, there are benefits to 1D vectors, and benefits to 2D vectors.
Now, let's suppose you had a class that actually was a 2D vector. We'll call it std::vector2D<> instead (no standard like that exists, but it'd be very easy to make).
 
The 1D benefits are, you can iterate from one end to the other really easily:

for(int i  = 0; i < vector.size(); ++i) //Alternatively: for(Type &type : vector)
{
     vector[i] = ...;
}

 
To do the same in 2D, you do:

for(int x = 0; x < width; ++x)
{
     for(int y = 0; y < width; ++y)
     {
          vector[x][y] = ...;
     }
}

 
More code for doing the same thing.
 
The benefit 2D arrays are indexing into them with 'x' and 'y', it more closely matches the mental model of your 2D board.

myMap[x][y] = ...;

 
But you can do the same thing with 1D arrays, by treating them as if they were 2D arrays:

myMap[(y * width) + x] = ....;

 
You get the best of both, with none of the other limitations.
 
The limitations (fragmentation of memory, manually keeping the row lengths in sync, extra code merely to iterate over every element) get worse and worse for each additional dimension you add. Three dimensions, four dimensions, whatever.
 
But you can treat a 1D array like an array of any number of dimensions you want, just by indexing into it how you like:

myMap[(z * width * height) + (y * width) + x] = ....; //Three dimensions

And you can wrap up the indexing into a helper function if you like.

 

Our memory (RAM) is one dimensional. Any 2D or 3D arrays are just mapping the indices to a 1D set of memory, the same way we are. Here, we're taking finer control over it so it maps the way we want, and so we can switch between 1D and 2D when we need (which we often do!).

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