Jump to content
  • Advertisement
Sign in to follow this  
MHOOO

Non-contiguous update routine

This topic is 4001 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm sorry if the title doesn't really fit my problem, but I just couldn't find a better way to describe it in a few words. So here's my actual problem: I have a Marketing Simulation where basically I have a few hundreds and thousands of what I like to call Entities, each defined through one or more Entity Types. If I say Entity I basically mean every thing which exists inside the simulation - be that a Location, an AI, a Market Commodity or whatever. Most of those Entities affect other Entities - this means that I need to call an update method for those Entities, however - with a few hundreds of thousand Entities, it is impossible to do that every simulation frame. Which is why I thought of implementing a non-contiguous update routine idiom (I came up with that term). Basically I want to only update an Entity whenever an update is actually necessary. As it is now however I struggle with a clean way to accomplish this - because it is very difficult to compute values for a time t2=500 when you don't really know which Entity could have changed your to-be-updated Entity between t1=200 and t2... Well, its all very confusing - and my brain is kinda starting to melt away by now, so I just figured I'd ask whether anyone knows of a programming pattern/idiom which describes all the problems I need to look out for when trying to implement something like this.

Share this post


Link to post
Share on other sites
Advertisement
I think maybe you are overcomplicating the situation.

Perhaps you could do a "continuous update" but just keep it cyclical.

T=100 Resources update
T=200 Suppliers update
T=300 Stores update
T=400 Consumers update
T=500 Repeat

Space your intervals out where processors keep up, then just set it up where your bottom rung on the overall ladder updates first, followed by the next etc. I know your spiderweb may be interconnected, but I do believe that you have an overall ladder in your marketing sim.

My 2cents.

Share this post


Link to post
Share on other sites
Sounds like you're over-engineering your program. I think you're splitting responsibilities up too much. For example, a location is a property of an entity, and I believe it's too low-level, too fundamental, to make it an actual entity of itself. Entity systems are usefull, but up to a certain point. You need to keep things practical. At some point, you need to stop forming abstractions and make something concrete - because that's what you're trying to accomplish in the end, something concrete. Abstraction is only a tool to reach that goal.


Anyway, it sounds like you'll want many of these entities to be event-driven. A particle emitter shouldn't do anything untill a trigger entity tells it to start spawning particles, for example. I've done something similar in the past by using a modified version of the observer design pattern for my entities, so entities could pass messages to other entities and I then only needed to update entities that required it. I haven't investigated the case much further though, but I'm sure there are others here who have more experience with this particular subject.

Share this post


Link to post
Share on other sites
Quote:
Original post by MHOOO
I have a Marketing Simulation where basically I have a few hundreds and thousands of what I like to call Entities, each defined through one or more Entity Types.
[...]
Basically I want to only update an Entity whenever an update is actually necessary. As it is now however I struggle with a clean way to accomplish this - because it is very difficult to compute values for a time t2=500 when you don't really know which Entity could have changed your to-be-updated Entity between t1=200 and t2...


At some point, your system must know. If you need to change an object, update it. If you don't change an object, don't update it. There are no invisible changes, after all.

Put objects into an update queue, ordered by next update time from soonest to latest. Each time, you start at the front of the queue and update any objects that are due for updates now. If they have knock-on effects on other objects, do them now as well. Once an object has been updated, remove it from the queue and add it back in with a new update time.

Beware - managing a dynamic list of hundreds of thousands of objects may actually be more resource intensive than just updating everything anyway, depending on how you do each of these things.

Share this post


Link to post
Share on other sites
Quote:
Original post by robert4818
[...]
Space your intervals out where processors keep up, then just set it up where your bottom rung on the overall ladder updates first, followed by the next etc. I know your spiderweb may be interconnected, but I do believe that you have an overall ladder in your marketing sim.
[...]

Yeah well, I thought about doing that as well, however this would restrict me to Updates based on the interval - and there are some Entities which are able to spawn other Entities at a given time t1. If that time t1 lies between two updates - and furthermore if the newly spawned Entity has its attributes changed just after spawning and still before the next update, I won't be able to figure out *when* exactly the attribute has changed.
This is actually one of the main problems I was facing.

Quote:
Original post by Captain P
[...]
Sounds like you're over-engineering your program. I think you're splitting responsibilities up too much. For example, a location is a property of an entity, and I believe it's too low-level, too fundamental, to make it an actual entity of itself. Entity systems are usefull, but up to a certain point. You need to keep things practical. At some point, you need to stop forming abstractions and make something concrete - because that's what you're trying to accomplish in the end, something concrete. Abstraction is only a tool to reach that goal.
[...]

Well, the Location was basically just an example.
The system in fact works somewhat different. Basically an Entity can have an arbitrary number of types - one of them a Location Type. It is somewhat like a parent class which defines the Entities properties and methods. This way I can easily reuse code for future Entities which are supposed to have the same behavior. Unless I actually assign values to, say, the x and y coordinates of the Location Type within an Entity, the default values of those properties from the Location Type are being used. So it's not like its a new Location Entity, but rather an Entity with the properties of a Location.
Puh... too much Entity...

Quote:
Original post by Captain P
[...]
Anyway, it sounds like you'll want many of these entities to be event-driven. A particle emitter shouldn't do anything untill a trigger entity tells it to start spawning particles, for example. I've done something similar in the past by using a modified version of the observer design pattern for my entities, so entities could pass messages to other entities and I then only needed to update entities that required it. I haven't investigated the case much further though, but I'm sure there are others here who have more experience with this particular subject.

Well, I thought about using an approach like this as well, however using this method, I still need to check when exactly an event happened - and in order to check for that, I'd need to implement a contiguous update routine :x
At least with the system as it is now, all possible events come from values which are changing *all the time*, so basically at any possible time t there *could* be a new value v(t).
But after thinking a lot while writing this here, I see there is really no other method of implementing this... I guess it all comes down to machine power in the end :/

Share this post


Link to post
Share on other sites
You need to think if you need to update all the entities every time. If you do, you are bound to some form of queue. If not mabe it's worth to use some kind of event system. Think of event brokers and event subscribers. That way you can update only those entities which are affected by certain entity, and after proper implementation it's easy to manage whole tree of events triggered by one change.
Some more informations here: http://en.wikipedia.org/wiki/Event_driven .

Share this post


Link to post
Share on other sites
Quote:

You need to think if you need to update all the entities every time. If you do, you are bound to some form of queue. If not mabe it's worth to use some kind of event system.


A queue IS an event system; the event system par excellence, one could say. As Kylotan said, the benefit of updating all entities according to a fixed time step lies in NOT having to maintain a queue.

Maintaining a priority queue for n events takes O(nlogn) operations, and it has to be processed serially. The benefit of an event queue is that you can use timesteps of arbitrarily small granularity.

Updating every entity once per timestep (or efficient variants thereof, like maintaining an unsorted list of 'dirty' entities per timestep and only updating those) takes O(n) time and can be distributed across several processors very simply. Disadvantage is you have to fix a timestep size that is not too small, because you have to actually traverse tsteps.

Quote:
Yeah well, I thought about doing that as well, however this would restrict me to Updates based on the interval - and there are some Entities which are able to spawn other Entities at a given time t1. If that time t1 lies between two updates - and furthermore if the newly spawned Entity has its attributes changed just after spawning and still before the next update, I won't be able to figure out *when* exactly the attribute has changed.
This is actually one of the main problems I was facing.



You need to stop thinking about 'entities', or rather 'Entities' and start thinking about events. The way you figure out when things happen is by keeping track of the pending events in an ordered fashion. So even if an event triggers others, you'll always be guaranteed to process the correct event next.

Of course, if two events occur at exactly the same time, you run into ambiguities...

The event model assumes you have things that can recieve an event and act upon it (by sending other events, for example).

So, each thing needs, apart from any logic specific to itself:

1) a list of things it knows about and can send messages to;

To synchronize events we need

2) a priority queue.

The time to process a message will be the time the receiver takes to process it + a time proportional to logn, where n is the number of messages currently in flight.

Voila. In fact, writing an event system is so simple I'll give you an example in python. Imagine we want to model a network of chatty people who all know each other. They react to being told gossip in two ways:

1) If they didn't know the gossip already, they call two of their friends (it takes a random amount of time to complete a call) and tell them the gossip.

2) If they did know the gossip, they tell the person who told them that they're boring.

Next post brings the code.

Edit: Man, it's my day for stupid mistakes. Good night.

[Edited by - Anonymous P on October 31, 2007 10:54:09 AM]

Share this post


Link to post
Share on other sites
Here's a simple example; notice that most of the code (the people class) is incidental to the actual event queue mechanism, which is very straightforward if you have a heap algorithm. Both Python and C++'s STL have them, and writing your own is trivial.


from heapq import heappush, heappop
from random import sample, randint

event_q = []

# A message is a tuple of the form (time, sender, receiver, mtype, message)

def send(time, sender, receiver, mtype, message):
heappush(event_q, (time, sender, receiver, mtype, message))

def next_event():
m = heappop(event_q)
m[2].receive_message(m)

class Thing:
def __init__(self, name, known_things = []):
self.known_things = known_things
self.name = name

def receive_message(self, m):
time, sender, receiver, mtype, message = m
print self.name, ' received ', message.ljust(40), ' from ', sender.name, ' at ', time


class Person(Thing):
def __init__(self, name):
Thing.__init__(self, name)
self.known_gossip = set()

def set_known(self, known):
self.known_things = known

def receive_message(self, m):
Thing.receive_message(self, m)
time, sender, receiver, mtype, message = m
if mtype == 'gossip':
if message in self.known_gossip:
time += 0.1
send(time, self, sender, 'snarky', "I knew that %s" % message)
else:
self.known_gossip.add(message)
for friend in sample(filter(lambda x: self != x, self.known_things), 2):
time += randint(10, 15)
send(time, self, friend, 'gossip', message)
elif mtype == 'snarky':
time += 0.1
send(time, self, sender, 'abuse', "Yeah well I knew about yo mamma")

elif mtype == 'abuse':
pass #Gossipers get scared of strong language

# Create people
people = [Person(name) for name in ['Joe ', 'Jim ', 'Jane ', 'Sally', 'Larry', 'Sue ']]
for person in people:
person.set_known(people)

heappush(event_q, (0, people[0], people[1], 'gossip', 'Events are the new black'))
heappush(event_q, (0, people[0], people[1], 'gossip', 'Bears shit in the woods'))

while len(event_q) > 0:
next_event()


We see very edifying conversations emerging:


Jim received Bears shit in the woods from Joe at 0
Jim received Events are the new black from Joe at 0
Jane received Events are the new black from Jim at 14
Sally received Bears shit in the woods from Jim at 14
Joe received Events are the new black from Jim at 25
Jane received Bears shit in the woods from Sally at 27
Jane received Bears shit in the woods from Jim at 28
Sally received Events are the new black from Jane at 28
Jim received I knew that Bears shit in the woods from Jane at 28.1
Jane received Yeah well I knew about yo mamma from Jim at 28.2
Sally received Events are the new black from Joe at 37
Joe received I knew that Events are the new black from Sally at 37.1
Sally received Yeah well I knew about yo mamma from Joe at 37.2
Jim received Events are the new black from Sally at 39
Sally received I knew that Events are the new black from Jim at 39.1
Jim received Yeah well I knew about yo mamma from Sally at 39.2
Joe received Events are the new black from Jane at 40
Jane received I knew that Events are the new black from Joe at 40.1
Joe received Yeah well I knew about yo mamma from Jane at 40.2
Joe received Bears shit in the woods from Jane at 41
Larry received Bears shit in the woods from Sally at 41
Sue received Events are the new black from Joe at 48
Larry received Bears shit in the woods from Jane at 51
Jane received I knew that Bears shit in the woods from Larry at 51.1
Larry received Yeah well I knew about yo mamma from Jane at 51.2
Sally received Bears shit in the woods from Larry at 53
Larry received I knew that Bears shit in the woods from Sally at 53.1
Sally received Yeah well I knew about yo mamma from Larry at 53.2
Joe received Events are the new black from Sally at 54
Sally received I knew that Events are the new black from Joe at 54.1
Joe received Yeah well I knew about yo mamma from Sally at 54.2
Sally received Bears shit in the woods from Joe at 55
Joe received I knew that Bears shit in the woods from Sally at 55.1
Sally received Yeah well I knew about yo mamma from Joe at 55.2
Jim received Events are the new black from Sue at 62
Sue received I knew that Events are the new black from Jim at 62.1
Jim received Yeah well I knew about yo mamma from Sue at 62.2
Joe received Bears shit in the woods from Larry at 64
Larry received I knew that Bears shit in the woods from Joe at 64.1
Joe received Yeah well I knew about yo mamma from Larry at 64.2
Jim received Bears shit in the woods from Joe at 68
Joe received I knew that Bears shit in the woods from Jim at 68.1
Jim received Yeah well I knew about yo mamma from Joe at 68.2
Joe received Events are the new black from Sue at 72
Sue received I knew that Events are the new black from Joe at 72.1
Joe received Yeah well I knew about yo mamma from Sue at 72.2


Minor bugfix edit.

[Edited by - Anonymous P on October 31, 2007 10:00:58 AM]

Share this post


Link to post
Share on other sites
So, after thinking a lot and reading your post over and over again, and trying to make it fit with what I had in mind, I kinda get this one huge problem pop up in my head.
Lets make this into an example.

"We have one power plant which produces 20 energy units per hour. Furthermore we have one car factory which manufactures cars. Needless to say, the latter requires Energy, say 15 energy units per hour. All is fine and well, the power plant produces more than the car factory can use up. But what if we now, add a new car factory which is connected to the same power plant?
We'd have energy consumption of 30 units per hour and energy production of 20 units per hour. So lets say the energy storage was at 30 units the moment the second factory has been connected to the power plant. Basically every hour, we'd lose 10 units of energy - after 3 hours chaos breaks loose as there is not enough energy. Needless to say, the car factories are going to work less efficient, as there is simply not enough energy. If we split it evenly, both get 10 energy units per hour - instead of 15, so they work with an efficiency of ~66.66%."

I kinda struggle with an implementation of this. But then again, this is really an implementation specific detail which I am only going to solve if I adapt it to the code I already have o.O

I'll have to try and think some more if I want to implement this.

So errm,
thanks all :)

Share this post


Link to post
Share on other sites
Quote:
So, after thinking a lot and reading your post over and over again, and trying to make it fit with what I had in mind, I kinda get this one huge problem pop up in my head. (example snipped)
Yes; it's the problem of managing dependencies in a concurrent system. You don't seem to realize that this is basically what 'simulation' boils down to. :)

Because electricity is limited, we can't just let an arbitrary amount of factories request (and get) 15 watts at the same time; they would be using electricity that doesn't exist, and thus leave our system in an inconsistent state (more electricity is being used than is being produced).

Basically, if a factory consumes electricy, that electricity will be unavailable to other factories. That's fine, we might say: every time a factory uses electricity, just decrement the amount of electricity available. If a factory requests electricity, check that there is enough before satisfying the request.

But multiple factories may request electricity at the same time, and all the individual checks will succeed, and all factories will be given electricity!

One way to solve this issue is to introduce explicit locks around operations which have to know about each other (as in typical multithreaded programming). We know that the 'request electricity and decrement the amount available for others' operation needs to be atomic. If requests are serviced one after another instead of in parallel, we will never give out electricity we don't have. So we say, 'perform the check and give out electricity to one user at a time'.

The problem with this approach is that we must explicitly keep track of the interactions that may conflict, and lock them. That can quickly become unmanageable if we have lots of interactions with different requirements (as in modeling).

ANOTHER way (the event-actor way I described above) says: 'the only atomic operations are those performed by an object internally. Messages are asynchronous.' This means that an object can't assume anything about the state of another at any point in time; it can only react to messages from it. This makes simulations easier; it just requires you to think carefully about what states objects can have, because local change of state is the only guaranteed atomic operation.

Still another way is to permit events that are not local to an object; this looks like mutiple dispatch (eg Lisp provides it) and solves the problem elegantly.

So, how would we write the factories-powerplant model in the Thing formalism? We would bear in mind the atomicity of local ops.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!