# Non-contiguous update routine

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

## 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 on other sites
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 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 on other sites
Quote:
 Original post by MHOOOI 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 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 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.

##### 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 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, heappopfrom random import sample, randintevent_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 ', timeclass 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 peoplepeople = [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  0Jim    received  Events are the new black                  from  Joe    at  0Jane   received  Events are the new black                  from  Jim    at  14Sally  received  Bears shit in the woods                   from  Jim    at  14Joe    received  Events are the new black                  from  Jim    at  25Jane   received  Bears shit in the woods                   from  Sally  at  27Jane   received  Bears shit in the woods                   from  Jim    at  28Sally  received  Events are the new black                  from  Jane   at  28Jim    received  I knew that Bears shit in the woods       from  Jane   at  28.1Jane   received  Yeah well I knew about yo mamma           from  Jim    at  28.2Sally  received  Events are the new black                  from  Joe    at  37Joe    received  I knew that Events are the new black      from  Sally  at  37.1Sally  received  Yeah well I knew about yo mamma           from  Joe    at  37.2Jim    received  Events are the new black                  from  Sally  at  39Sally  received  I knew that Events are the new black      from  Jim    at  39.1Jim    received  Yeah well I knew about yo mamma           from  Sally  at  39.2Joe    received  Events are the new black                  from  Jane   at  40Jane   received  I knew that Events are the new black      from  Joe    at  40.1Joe    received  Yeah well I knew about yo mamma           from  Jane   at  40.2Joe    received  Bears shit in the woods                   from  Jane   at  41Larry  received  Bears shit in the woods                   from  Sally  at  41Sue    received  Events are the new black                  from  Joe    at  48Larry  received  Bears shit in the woods                   from  Jane   at  51Jane   received  I knew that Bears shit in the woods       from  Larry  at  51.1Larry  received  Yeah well I knew about yo mamma           from  Jane   at  51.2Sally  received  Bears shit in the woods                   from  Larry  at  53Larry  received  I knew that Bears shit in the woods       from  Sally  at  53.1Sally  received  Yeah well I knew about yo mamma           from  Larry  at  53.2Joe    received  Events are the new black                  from  Sally  at  54Sally  received  I knew that Events are the new black      from  Joe    at  54.1Joe    received  Yeah well I knew about yo mamma           from  Sally  at  54.2Sally  received  Bears shit in the woods                   from  Joe    at  55Joe    received  I knew that Bears shit in the woods       from  Sally  at  55.1Sally  received  Yeah well I knew about yo mamma           from  Joe    at  55.2Jim    received  Events are the new black                  from  Sue    at  62Sue    received  I knew that Events are the new black      from  Jim    at  62.1Jim    received  Yeah well I knew about yo mamma           from  Sue    at  62.2Joe    received  Bears shit in the woods                   from  Larry  at  64Larry  received  I knew that Bears shit in the woods       from  Joe    at  64.1Joe    received  Yeah well I knew about yo mamma           from  Larry  at  64.2Jim    received  Bears shit in the woods                   from  Joe    at  68Joe    received  I knew that Bears shit in the woods       from  Jim    at  68.1Jim    received  Yeah well I knew about yo mamma           from  Joe    at  68.2Joe    received  Events are the new black                  from  Sue    at  72Sue    received  I knew that Events are the new black      from  Joe    at  72.1Joe    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 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 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.

1. 1
Rutin
24
2. 2
3. 3
JoeJ
20
4. 4
5. 5

• 9
• 46
• 41
• 23
• 13
• ### Forum Statistics

• Total Topics
631749
• Total Posts
3002033
×