Sign in to follow this  
lride

how to keep track of game entities

Recommended Posts

Let's say I'm making a rpg.
In a rpg game, there are many monsters randomly spawning.
How am I supposed to keep track of these monsters?
Should I store these in an array and iterate through the entire array to update each monster and render them?-This way seems very inefficient.

Share this post


Link to post
Share on other sites
[quote name='lride' timestamp='1349057087' post='4985612']
This way seems very inefficient
[/quote]
Yes it is for larger amounts of mobs. A very good and [i]easy [/i]data structure for holding [i]moving [/i]entities is [url="http://en.wikipedia.org/wiki/Sweep_and_prune"]sweep'n'prune[/url].

Share this post


Link to post
Share on other sites
[quote name='lride' timestamp='1349057087' post='4985612']
Should I store these in an array and iterate through the entire array to update each monster and render them?-This way seems very inefficient.
[/quote]

Do you want to update and render every monster, every frame? If so, an array sounds like a pretty efficient way to be able to iterate over them all. If your 'this seems inefficient' comment isn't based on actually measuring performance, you're just guessing, and that's not science.

A better, more efficient way of transforming a large amount of heterogeneous data is to group the data into homogeneous chunks and update those chunks together.

But I would really hope a discussion about performance contains real data that can be analyzed and commented on precisely.

Share this post


Link to post
Share on other sites
[quote name='lride' timestamp='1349057087' post='4985612']
Should I store these in an array and iterate through the entire array to update each monster and render them?-This way seems very inefficient.[/quote][b]For what purpose?[/b]
If your goal is to run physics on them, you have no choice but delegating a physics API (albeit those objects are likely [i]kinematic[/i]).
If all the monsters are to be updated each tick, it's possible an array will actually be the faster option. [b]You need to elaborate on your needs.[/b]

To give you an answer: I don't keep track of my "monsters". I actually don't keep track of anything in my game(s). I only keep track of a [font=courier new,courier,monospace]WorldLogic[/font] object. This object has responsibility to propagate ticks to all the entities it wants. On top of that, certain entities are [i]live[/i], for example rigid bodies will evolve by themselves and receive asynchronous events every once in a while. Those objects effectively have two ways of ticking.
I have certain entities called [font=courier new,courier,monospace]ValueGenerator[/font]s. They are non-positioned entities. I store them in an [font=courier new,courier,monospace]std::vector[/font], and I'm fine with it, I stop looking at profiler results after hitting 1% of CPU time, they're likely down there.

Share this post


Link to post
Share on other sites
Which of these functions do you need:
- random access monster
- inserting and deleting monsters a lot
- searching monster in the "list" a lot

As you see, depending on what you will do many different types of containers could help:
- vectors/array (good for random access, bad for inserting deleting
- lists (bad for random access, good for inserting, deleting)
- maps (good for searchin)
- ... Edited by AticAtac

Share this post


Link to post
Share on other sites
Problaby yes. You might also be interested in data oriented design.

Sometimes it's faster to store your entities in a simple table or array and updating them all. Instead of traversing a scene graph or sorting them and only updating specific items.

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