Jump to content

  • Log In with Google      Sign In   
  • Create Account

How do I insert a multimap into another multimap?


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
16 replies to this topic

#1 bedtime   Members   -  Reputation: 159

Like
0Likes
Like

Posted 26 November 2012 - 03:32 PM

I've looked around and can't seem to find the answer.

Here is my multimap and an attempt at my idea of what I want to do:

[source lang="cpp"] // declared multimap of x/y/object std::multimap<int, std::multimap<int, GameObject*>*> gameObj; // pseodo code of what I want to do: GameObject* tempObj = new GameObject; gameObj.insert({ 1, { 1, tempObj });[/source]


Any ideas?

Sponsor:

#2 SiCrane   Moderators   -  Reputation: 9594

Like
2Likes
Like

Posted 26 November 2012 - 03:47 PM

Your multimap has a pointer to a multimap as the value, so you need to pass a pointer when you insert into it. Probably by using new to allocate a multimap. So something like:
gameObj.insert(std::make_pair(1, new std::multimap<int, GameObject *>()));


#3 bedtime   Members   -  Reputation: 159

Like
0Likes
Like

Posted 26 November 2012 - 04:17 PM

Your multimap has a pointer to a multimap as the value, so you need to pass a pointer when you insert into it. Probably by using new to allocate a multimap. So something like:

gameObj.insert(std::make_pair(1, new std::multimap<int, GameObject *>()));


Thank you. Worked perfectly!

Here's what I did:

[source lang="cpp"] std::multimap<int, std::multimap<int, GameObject*>*> go2; std::multimap<int, std::multimap<int, GameObject*>*>::iterator it1, itlow1, ithigh1; std::multimap<int, GameObject*>::iterator it2; // just return first result (better used with map than multimap) it1 = go2.find(x); it1->second->find(y);//->second; // inserting a new object go2.insert(std::make_pair( 1, new std::multimap<int, GameObject *>() )); // make object to insert std::multimap<int, GameObject*> gameObj; GameObject* insertedGameObject = new GameObject; // inserting object gameObj.insert({ 1, insertedGameObject }); go2.insert(std::make_pair( 1, &gameObj )); itlow1 = go2.lower_bound(x); ithigh1 = go2.upper_bound(x); // interate through all uppper/lower x/y values for (it1 = itlow1 ; it1 != ithigh1; ++it1) { for (it2 = it1->second->lower_bound(y); it2 != it1->second->upper_bound(y); ++it2) { // do something } }[/source]

#4 Servant of the Lord   Crossbones+   -  Reputation: 19508

Like
3Likes
Like

Posted 26 November 2012 - 04:19 PM

When doing containers within containers, it helps to typedef them (if it makes sense in whatever context your code is in).
typedef std::multimap<int, GameObject*> GameObjectMap;
std::multimap<int, GameObjectMap*> gameObj;

Second, you 'new' a GameObject, but call it 'tempObj'. A new'd variable is definitely not temporary. Anything you new must be deleted. Your map will not delete it for you.
Likewise, following SiCrane's suggestion, you need to remember to delete any std::multimap<int, GameObject*> you new.

If you use smart pointers, the smart pointers will delete the memory for you - but as it stands, you'll have multiple massive memory leaks (depending on the number of GameObjects and how hefty they are).

I like to typedef my smart pointers within GameObject class itself, so I can use GameObject::Ptr instead of std::shared_ptr<GameObject>.

This will result in code that looks like this:
typedef std::multimap<int, GameObject*> GameObjectMap;
std::multimap<int, GameObjectMap> gameObjects;

gameObject.insert({1, {1, std::make_shared<GameObject>(...arguments for GameObject constructor...)}});

It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#5 Zipster   Crossbones+   -  Reputation: 674

Like
2Likes
Like

Posted 27 November 2012 - 02:19 AM

A multimap inside a multimap sounds like quite the hairy data structure, not to mention the extra memory management you incur by having the outer multimap store pointers to the inner multimaps! You could accomplish the same thing with a single multimap to your objects and a composite key :)

#6 bedtime   Members   -  Reputation: 159

Like
0Likes
Like

Posted 27 November 2012 - 08:43 AM

When doing containers within containers, it helps to typedef them (if it makes sense in whatever context your code is in).

typedef std::multimap<int, GameObject*> GameObjectMap;
std::multimap<int, GameObjectMap*> gameObj;

Second, you 'new' a GameObject, but call it 'tempObj'. A new'd variable is definitely not temporary. Anything you new must be deleted. Your map will not delete it for you.
Likewise, following SiCrane's suggestion, you need to remember to delete any std::multimap<int, GameObject*> you new.

If you use smart pointers, the smart pointers will delete the memory for you - but as it stands, you'll have multiple massive memory leaks (depending on the number of GameObjects and how hefty they are).

I like to typedef my smart pointers within GameObject class itself, so I can use GameObject::Ptr instead of std::shared_ptr<GameObject>.

This will result in code that looks like this:
typedef std::multimap<int, GameObject*> GameObjectMap;
std::multimap<int, GameObjectMap> gameObjects;

gameObject.insert({1, {1, std::make_shared<GameObject>(...arguments for GameObject constructor...)}});

Thank you for this info. It's embarrassing how neglectful I've been with deleting my 'new' objects. I also for some reason thought that when the object went out of scope it was delete automatically but after hearing you and reading a little it isn't. A good find here. As far as smart pointers I, they seem like a lazy way to do things but perhaps that's perfect for me for now. :)

A multimap inside a multimap sounds like quite the hairy data structure, not to mention the extra memory management you incur by having the outer multimap store pointers to the inner multimaps! You could accomplish the same thing with a single multimap to your objects and a composite key

A composite key? I don't think I've heard of this before. I've just dabbled into this on google and it looks like I have a little reading to do, thanks.

#7 SiCrane   Moderators   -  Reputation: 9594

Like
1Likes
Like

Posted 27 November 2012 - 08:49 AM

A composite key would be instead of using a multimap with an int key containing multimaps with int keys, instead use a single multimap with a key that contains two ints like a std::pair<int, int> such as std::multimap<std::pair<int, int>, GameObject *>.

#8 bedtime   Members   -  Reputation: 159

Like
0Likes
Like

Posted 27 November 2012 - 10:20 AM

A composite key would be instead of using a multimap with an int key containing multimaps with int keys, instead use a single multimap with a key that contains two ints like a std::pair<int, int> such as std::multimap<std::pair<int, int>, GameObject *>.


This sounds like a great idea and I don't want to keep bugging you for examples. Is there perhaps a good tutorial on this? I have several C++ books but they don't seem to go this in depth. If you can recommend a book that will help me with this I'll read it.

There seems to be a another way. That is to use a Key class to store the keys. How does that compare to using a 'pair' of keys?

Here's what I have played with so far ('val' is encapsulated code that allows me to store to that object and test it):

[source lang="cpp"]class Keys { public: Keys(int k1, int k2) : key1(k1), key2(k2) { } bool operator<(const Keys &right) const { return (key1 < right.key1 && key2 < right.key2); } const int getKey1() const { return key1; } const int getKey2() const { return key2; } int key1; int key2;}[/source]

[source lang="cpp"] std::multimap<Keys, GameObject> go2; GameObject* gameObj1 = new GameObject; gameObj1->val()->newNum("test", 10); go2.insert(std::pair<Keys, GameObject>( Keys(1, 2), *gameObj1) ); GameObject* gameObj2 = new GameObject; gameObj2->val()->newNum("test", 20); go2.insert(std::pair<Keys, GameObject>( Keys(3, 4), *gameObj2) ); GameObject* gameObj3 = new GameObject; gameObj3->val()->newNum("test", 30); go2.insert(std::pair<Keys, GameObject>( Keys(1, 2), *gameObj3) ); for(auto& i : go2) { std::cout << "x: " << i.first.getKey1() << " y: " << i.first.getKey2() << " test: " << i.second.val()->getNum("test") << std::endl; }[/source]

The above code seems to print out the results just fine, but I question how easy it'll be to get this to iterate in ranges. I do think it might be nice as it would allow multiple ways to sort but I'm new to all this.

Edited by bedtime, 27 November 2012 - 10:22 AM.


#9 SiCrane   Moderators   -  Reputation: 9594

Like
1Likes
Like

Posted 27 November 2012 - 11:06 AM

There seems to be a another way. That is to use a Key class to store the keys. How does that compare to using a 'pair' of keys?

Congratulations, you've re-implemented std::pair<int, int> ... incorrectly. For an operator < overload to be valid for use in a std::map or std::multimap it needs to be a strict weak ordering. Some of the qualities of a strict weak ordering are irreflexivity (x < x is false), antisymmetry (if x < y then y < x must be false) and transitivity (if x < y and y < z then x < z). You've got these three. However, the last quality of a strict weak ordering is transitivity of equivalence (also called transitivity of incomparability). Under a strict weak ordering, two objects x and y are equivalent if x < y and y < x are both false. With transitivity of equivalence if x and y are equivalent and y and z are equivalent then x and z must be equivalent. Here your operator < fails. With your function (1, 2) and (3, 2) are equivalent and (3, 2) and (3, 4) are also equivalent. However (1, 2) is less than (3, 4).

One way to fix it is to change your operator < implementation:
        bool operator<(const Keys &right) const
        {
            if (key1 < right.key1) return true;
            if (key1 > right.key1) return false;
            return key2 < right.key2;
        }
Or you could just use std::pair<int, int>.

Also, it's kind of pointless to create getters for public member variables.

The above code seems to print out the results just fine, but I question how easy it'll be to get this to iterate in ranges. I do think it might be nice as it would allow multiple ways to sort but I'm new to all this.

What do you mean by "iterate in ranges"?

#10 Servant of the Lord   Crossbones+   -  Reputation: 19508

Like
1Likes
Like

Posted 27 November 2012 - 11:30 AM

Thank you for this info. It's embarrassing how neglectful I've been with deleting my 'new' objects. I also for some reason thought that when the object went out of scope it was delete automatically but after hearing you and reading a little it isn't.

Variables on the stack are deleted automatically when they go out of scope (if they have a destructor, it is also called).
Variables on the heap (dynamic allocation) are only deleted manually.

Stack = Automatic allocation, automatic deallocation.
Heap = Manual allocation, manual deallocation (so you can control the lifetime so the memory can exist beyond the scope).

Smart pointers themselves are on the stack, but they point to data on the heap. So when the smart pointer goes out of scope, its destructor is called (being on the stack), which then manually deletes the memory pointed to for you (but only if no other smart pointer is pointing to the same memory).

Prefer everything on the stack whenever possible, but when needed otherwise, use smart pointers to handle the allocation and deallocation for you, except in the 1% of times when you really truly do need to manage it yourself.

A good find here. As far as smart pointers I, they seem like a lazy way to do things but perhaps that's perfect for me for now. Posted Image

They are the safe way of doing things, and safe is good. The laziest AND safest method is putting memory on the stack instead; but in this situation, your GameObjects probably want to be smart pointers (std::shared_ptr is the smart pointer you'll most likely want). Your keys should be on the stack though.
It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#11 bedtime   Members   -  Reputation: 159

Like
0Likes
Like

Posted 27 November 2012 - 11:36 AM

Congratulations, you've re-implemented std::pair<int, int> ... incorrectly. For an operator < overload to be valid for use in a std::map or std::multimap it needs to be a strict weak ordering. Some of the qualities of a strict weak ordering are irreflexivity (x < x is false), antisymmetry (if x < y then y < x must be false) and transitivity (if x < y and y < z then x < z). You've got these three. However, the last quality of a strict weak ordering is transitivity of equivalence (also called transitivity of incomparability). Under a strict weak ordering, two objects x and y are equivalent if x < y and y < x are both false. With transitivity of equivalence if x and y are equivalent and y and z are equivalent then x and z must be equivalent. Here your operator < fails. With your function (1, 2) and (3, 2) are equivalent and (3, 2) and (3, 4) are also equivalent. However (1, 2) is less than (3, 4).

One way to fix it is to change your operator < implementation:

		bool operator<(const Keys &right) const
		{
			if (key1 < right.key1) return true;
			if (key1 > right.key1) return false;
			return key2 < right.key2;
		}
Or you could just use std::pair<int, int>.

Thank you so much for that explanation. Now I know.

Also, it's kind of pointless to create getters for public member variables.

Lol, yeah. I noticed that too. I'm so used to declaring class variables private and making a get function for it... Why stop now?? Posted Image

What do you mean by "iterate in ranges"?


I want to be able to do something like this:

[source lang="cpp"]void getXY(const int& x, const int& y, const int& xRange, const int& yRange){ // pseodo code: for(it = xlow; it != xhigh; ++it) for(it2 = ylow; it != yhigh; ++it2) // do something}[/source]

This way I can print out only certain x/y chunks whilst in my game. If std::pair<int, int> works thats great but I don't know where to find a good tutorial or an example.

#12 Servant of the Lord   Crossbones+   -  Reputation: 19508

Like
1Likes
Like

Posted 27 November 2012 - 12:44 PM

Let's step back a second. What are you actually trying to do? Not, "how are you trying to implement it", but what is your overall design problem you are solving?

Do you have a grid of spaces, and a game object might be on that grid?
It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#13 bedtime   Members   -  Reputation: 159

Like
0Likes
Like

Posted 27 November 2012 - 01:06 PM

Let's step back a second. What are you actually trying to do? Not, "how are you trying to implement it", but what is your overall design problem you are solving?

Do you have a grid of spaces, and a game object might be on that grid?



I'm making a mario-style side-scroller. My map is made up of x and y chunks, but it is not a grid. They are more like a list of chunks. This way I can skip chunks (or sections, whatever you want to call it) for areas that don't have any objects. So this is not tile-based. I would like to make a board map that is speed and memory efficient that can do positive and negative chunks. This is important because I want the map to be realtime expandable during runtime. There will be a lot of objects in the game so I want to be able to focus on only displaying the very minimum. There may be more then one object on the same chunk as well, hence the multimap. Levels might just go up 0 degrees. They might go backwards (270 deg). They might 'squiggle' or go in a circle.

I've done this all before but only with an X chunk and not with a Y chunk as well. So the map was only cut into X sections which led to inefficiencies if the level went straight upward. Since then I've since learned some new concepts such as component/entity programming so I'm changing things up and starting over.

#14 SiCrane   Moderators   -  Reputation: 9594

Like
1Likes
Like

Posted 27 November 2012 - 01:23 PM

If what you want to do is to do some operation on every element with x_begin <= x < x_end and y_begin <= y < y_end, one way to do that would be like:
typedef std::pair<int, int> Key;
typedef std::multimap<Key, GameObject *> Map;

template <typename Operation>
void loop(const Map & map, int x_begin, int x_end, int y_begin, int y_end, Operation operation) {
  if (x_end <= x_begin) return;
  if (y_end <= y_begin) return;

  Key lower(x_begin, y_begin);
  Key upper(x_end - 1, y_end);
  auto first = map.lower_bound(lower);
  auto last = map.lower_bound(upper);  

  for (auto itr = first; itr != last;) {
    int x = itr->first.first;
    int y = itr->first.second;

    if (y < y_begin) {
      itr = map.lower_bound(Key(x, y_begin));
    } else if (y >= y_end) {
      itr = map.lower_bound(Key(x + 1, y_begin));
    } else {
      //do whatever
      operation(*itr);

      ++itr;
    }
  }
}


#15 Servant of the Lord   Crossbones+   -  Reputation: 19508

Like
1Likes
Like

Posted 27 November 2012 - 02:07 PM

Excellent description of your intents. If you can't describe it, you have a problem - but you described it very succinctly. Posted Image

Are chunks are composed of tiles? Or objects?

Programming rule #3421: Premature optimization is the root of many evils.
Programming rule #745: KiSS: Keep it Stupidly Simple (alternatively, Keep it Simple, Stupid)

Have you actually tried just making a grid of uniform chunks, and actually seeing if it's too slow for your program?

But that aside, let's see what we can do. It helps simplify things if you put stuff into their own classes or structs.

Your game world is composed of Objects (enemies, walls, the player, moving platforms, spikes, etc...).

Each object has a location in the world, probably in a pixel-like measurement unit.
So: World has 100,000+ objects. Obviously we can't load and process all those at the same time. (Actually with modern computers, we probably could - but we'll pretend we can't).

So you break your world into 'chunks'. World has a grid of smart pointers to Chunks (yes, a grid). Each location on the grid can either be a null smart pointer (thus saving you your precious memory Posted Image), or can have a smart pointer to a valid Chunk.

A World:
  • Has a grid of chunks.
  • Streams chunks in and out around the player.
  • Tells chunks to draw, update, etc...
A chunk is just a "bucket" of entities. Any solid who's center is over the chunk's boundaries, belongs to that chunk.
A Chunk:
  • Manages it's own loading and saving from file.
  • Tells the Objects within it to draw, think, etc...
  • If an Object Entity walks off of one chunk, that chunk passes ownership of that object to the next chunk.
When 'unloaded', the Chunk still exists, the Objects are destroyed (until the next reload), unless that particular Object is persistent and needs to think even when distant from the player, in which case they aren't drawn and only need to be updated at a much slower update rate.
Almost all walls are persistent, but don't need to think when the player isn't near. Almost all enemies need to think, but don't need to be persistent. Some enemies need to think and be persistent (a special enemy hunting the player from a million miles away, for example).

Maybe you want to specify to only keep an object in memory if it's within a certain range.

Let's convert this directly to pseudo-code:
Object
{
	 Position
	 IsPersistent
	 RangeToKeepInMemory //The distance away the player needs to be before it is destroyed.
	
	 bool SaveStateWhenDestroyed() -> (IsPersistant && hasChanged)
	 bool KeepInMemory(playerDistance) -> (playerDistance > RangeToKeepInMemory)

	 Save()
	 Load()

	 Draw()
	 Update(deltaTime) //Think, animate, etc...
}

Chunk
{
	 Vector<Object::Ptr> Objects

	 StreamOut() //Unloads all objects except those it needs to keep in memory.
	 StreamIn() //Loads all persistent objects, like walls and enemies that don't spawn but have preset locations like bosses.

	 Draw() -> Draw every object
	 Update(deltaTime) -> Update every object
}

World
{
	 Grid<Chunk::Ptr> Chunks;

	 LoadNewWorld();
	 StreamChunksAround(location);

	 Draw() -> Draws all chunks nearby.
	 Update(deltaTime) -> Updates chunks (which in turn updates objects)
}

This can be improved upon, but it's a good start and really straightforward and simple. It also does not waste much memory or speed.

You can steal my C++ Grid class here - re-sizable and permits negative indices. If you know the size of your World ahead of time, and it doesn't change during the course of that play, you could use a std::vector of size (width*height) instead.

The whole map<map<Object>> thing just doesn't seem like good design.

Edited by Servant of the Lord, 27 November 2012 - 02:10 PM.

It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#16 bedtime   Members   -  Reputation: 159

Like
0Likes
Like

Posted 27 November 2012 - 04:37 PM

If what you want to do is to do some operation on every element with x_begin <= x < x_end and y_begin <= y < y_end, one way to do that would be like:

typedef std::pair<int, int> Key;
typedef std::multimap<Key, GameObject *> Map;

template <typename Operation>
void loop(const Map & map, int x_begin, int x_end, int y_begin, int y_end, Operation operation) {
  if (x_end <= x_begin) return;
  if (y_end <= y_begin) return;

  Key lower(x_begin, y_begin);
  Key upper(x_end - 1, y_end);
  auto first = map.lower_bound(lower);
  auto last = map.lower_bound(upper);  

  for (auto itr = first; itr != last;) {
	int x = itr->first.first;
	int y = itr->first.second;

	if (y < y_begin) {
	  itr = map.lower_bound(Key(x, y_begin));
	} else if (y >= y_end) {
	  itr = map.lower_bound(Key(x + 1, y_begin));
	} else {
	  //do whatever
	  operation(*itr);

	  ++itr;
	}
  }
}


Thank you so much for taking the time to type that up. This was exactly what I was looking for; iterating within a range of x/y chunks. Took me a few times reading it over to understand most of what's going on. One thing that puzzles me is the operator input within the parameters. I'm not entirely sure how to supply that parameter input or what it does. If I had to guess its something to do with iterating... I noticed you left out the 3rd parameter in the for loop and incremented it within the loop below the 'operator'. Looks intriguing. Could you explain this?

Also, I see you made map a const in the parameters. Was there a reason for that? I'm likely going to be changing some object within the loop if that's advisable to do.

Once again, I really appreciate you taking the time write all that out for me.


Are chunks are composed of tiles? Or objects?

Objects. Each x/y map cooridinate is loaded with a GameObject which stores the 'components' such as rendering values and instructions for that specific character, the character itself, and sound components...


Have you actually tried just making a grid of uniform chunks, and actually seeing if it's too slow for your program?

Yes, I had started out with a vector tile-based situation. I profiled it (bare text run, no graphics), testing it with various chunk sizes and getting best performance at around 250 - 500 fps. This was with little characters on the screen and no AI, graphics, at all yet. More characters slowed it right down, 25 - 100 fps. Just not cutting it. I then profiled a system based on a 'list' of airborne x/y chunks, which only had chunks that held objects, and fps went to 4000 -10000 fps. When I first jumped I thought it was broken because I couldn't see the character jump! Posted Image When I loaded the board and level with characters, massively, it still did 150 - 500 fps, which was good enough.


So you break your world into 'chunks'. World has a grid of smart pointers to Chunks (yes, a grid). Each location on the grid can either be a null smart pointer (thus saving you your precious memory Posted Image), or can have a smart pointer to a valid Chunk.

I like the smart pointer idea and I like the idea of maybe using something to say if a character is enabled or not. Objects not enabled could be used as pooled objects, which is fine. By 'chunks' I see you mean a 'grid' but I do not want a tile-based grid. I'd rather a list (map, vector....whatever container) 'within' a chunk. So anything on that list that is processed if that chunk is on the screen.

A chunk is just a "bucket" of entities. Any solid who's center is over the chunk's boundaries, belongs to that chunk.
A Chunk:

  • Manages it's own loading and saving from file.
  • Tells the Objects within it to draw, think, etc...
  • If an Object Entity walks off of one chunk, that chunk passes ownership of that object to the next chunk.[/qoute]
I'll take a look at your code. I'm thinking of maybe having an outside entity control the chunks. As for objects changing chunks, you've described it exactly how I had it before; objects swapping memory positions to different containers. As well, leaving a pooled disabled object in its tracks to be used later.


Maybe you want to specify to only keep an object in memory if it's within a certain range.

That's a good idea. Perhaps a small loop that runs a list of these characters and runs an update() with full or high range chunks. But that's a while away.

Let's convert this directly to pseudo-code:

Object
{
	 Position
	 IsPersistent
	 RangeToKeepInMemory //The distance away the player needs to be before it is destroyed.
	
	 bool SaveStateWhenDestroyed() -> (IsPersistant && hasChanged)
	 bool KeepInMemory(playerDistance) -> (playerDistance > RangeToKeepInMemory)

	 Save()
	 Load()

	 Draw()
	 Update(deltaTime) //Think, animate, etc...
}

Chunk
{
	 Vector<Object::Ptr> Objects

	 StreamOut() //Unloads all objects except those it needs to keep in memory.
	 StreamIn() //Loads all persistent objects, like walls and enemies that don't spawn but have preset locations like bosses.

	 Draw() -> Draw every object
	 Update(deltaTime) -> Update every object
}

World
{
	 Grid<Chunk::Ptr> Chunks;

	 LoadNewWorld();
	 StreamChunksAround(location);

	 Draw() -> Draws all chunks nearby.
	 Update(deltaTime) -> Updates chunks (which in turn updates objects)
}

This can be improved upon, but it's a good start and really straightforward and simple. It also does not waste much memory or speed.

You can steal my C++ Grid class here - re-sizable and permits negative indices. If you know the size of your World ahead of time, and it doesn't change during the course of that play, you could use a std::vector of size (width*height) instead.

The whole map<map<Object>> thing just doesn't seem like good design.

Thank you for all that info! I'll take a look at your Grid class tomorrow when my mind is more agile and has had some rest. Been at this all day. Negative indices and resizable definately sounds good. It's just what I need.

#17 SiCrane   Moderators   -  Reputation: 9594

Like
1Likes
Like

Posted 27 November 2012 - 05:12 PM

One thing that puzzles me is the operator input within the parameters. I'm not entirely sure how to supply that parameter input or what it does. If I had to guess its something to do with iterating...

As written you can supply anything function like that would take a reference to a const value_type including function pointers, function objects, lambdas, etc. If you don't understand it, you can just replace the call with the actual functionality you want to do on each element.

I noticed you left out the 3rd parameter in the for loop and incremented it within the loop below the 'operator'. Looks intriguing. Could you explain this?

There's not much to explain. All three parts that go inside the parenthesis for a for loop are optional. for (A; B; C) is just syntactic sugar for
{ A;
  while (B) {
    // body of for loop
    C;
  }
}
With the exception that if you leave out the second part the while loop looks like while (true). If you leave off the first part, nothing is done before the going through the loop for the first time. If you leave out third part, nothing extra happens after the body of the for loop. So for (;;) {} would be the same as while (true) {}. Since in this loop what happens to itr is different depending on what itr refers to, trying to stick it in the third part of the for loop, while possible, would be horribly unreadable.

Also, I see you made map a const in the parameters. Was there a reason for that? I'm likely going to be changing some object within the loop if that's advisable to do.

This code doesn't handle the situation of adding or removing nodes from the map while it's looping. Ex: if for some reason you remove the element pointed to by last, it'll keep looping until it crashes. However, one of the interesting things about std::map is that if you have a map with pointers as the values, you can call non-const functions on the pointed to objects from a const_iterator. That is to say, this is legal:
  std::map<int, Foo *> foo_map;
  // fill the map
  std::map<int, Foo *>::const_iterator itr = foo_map.begin();
  itr->second->non_const_function();

Edited by SiCrane, 27 November 2012 - 05:13 PM.
formatting





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