Help: Quick way to test if value lies within a list of lists ofranges?

[Ben O'Steen]

Scenario:
=========

Using PyGame in particular, I am trying to write an application that will
run a scripted timeline of events, eg at 5.5 seconds, play xxx.mp3 and put
the image of a ball on screen, at 7.8 seconds move the ball up and down.
At this point, I hear you say 'Oh, like Flash'.

Yes, well... Like Flash, but I don't want to take this app in the same
direction as Macromedia took Flash, nor do I (ever) want the two to be
compatible.

One particular need is for the timeline to be quickly traversable. If I
want to go to time=239.4 seconds, I'd like it to go there pretty much
painlessly and hopefully with one call. (Same with play, reverse and pause
really) I also want it to play for a long duration, with lots of different
items (images, audio, etc.)

Let me be a little more specific:

sprite(a) -> (onscreen during) 2 - 10 secs, 20 - 50 secs
sprite(b) -> (onscreen during) 15 - 30 secs
sprite(c) -> (onscreen during) 42 - 50 secs
.....

I need a quick way to rattle off a list of sprites that should be on
screen at a given time. Needless to say the number of sprites will be
variable, and might even change unpredictably in game.

E.G.

onscreen(time = 8.8 secs): return [sprite(a)]

onscreen(time = 44.134 secs): return [sprite(a), sprite(c)]

onscreen(time = 28 secs): return [sprite(a), sprite(b)]

(NB Anything from 10 -> 200 sprites would be normal intended usage, each
set -up with a list of start,stop times.)

Any suggestions on a clever way to do this? I don't like the idea of
looping through 100+ sprites and test them each an arbitary number of
times every update. Is this just something unavoidable which should be
written in C for speed and included with SWIG or something similar?

Ben

(Anti-Zealotry ward)
:0:
* ^Subject:.*Re: Microsoft Hatred FAQ
| gzip >> junk-archive.gz
IMO, We all have our personal experience or beliefs as to how MS operates..
Petitioning MEP's/Senators will accomplish more than arguing on a Python
mailing list.

 

[Paddy]

Would this help?


'''{'a': [[5, 12], [27, 89], [120, 137]],
'b': [[6, 23], [26, 84], [200, 222]],
'c': [[2, 22], [47, 60], [67, 122]]}

names4val(28) ['a', 'b']
names4val(11) ['a', 'c', 'b']
names4val(145) []

'''
from pprint import pprint as pp

name2ranges = {
'a': [[48,60], [27,89], [5,12], [120,137]],
'b': [[78,84], [26,79], [200,222], [6,23], [72,74]],
'c': [[67,122],[2,22], [47,60]]
}

for name, ranges in name2ranges.iteritems():
# sort ranges
name2ranges[name].sort()
# Coalesce overlapping ranges.
# If the max of one range is >= the min of the next range then
# the adjacent ranges are combined
ln = len(ranges)
newranges = []
i = 0
while i< ln:
mn,mx = ranges
j = i+1
while j< ln and ranges[j][0] <=mx:
mx = max(mx, ranges[j][1])
j += 1
newranges.append([mn,mx])
i = j
name2ranges[name] = newranges

def names4val(val):
" find the names whose ranges intersect the value"
from bisect import bisect_left
names = []
for name,ranges in name2ranges.iteritems():
bs = bisect_left(ranges, [val,val])
if (bs and ranges[bs-1][0] <= val <= ranges[bs-1][1] ) or (
bs <len(ranges) and ranges[bs][0] <= val <= ranges[bs][1] ):
names.append(name)
names.sort()
return names

####

Cheers, Pad.

 

[Paul McGuire]

Scenario:
=========

Using PyGame in particular, I am trying to write an application that will
run a scripted timeline of events, eg at 5.5 seconds, play xxx.mp3 and put
the image of a ball on screen, at 7.8 seconds move the ball up and down.
At this point, I hear you say 'Oh, like Flash'.

Yes, well... Like Flash, but I don't want to take this app in the same
direction as Macromedia took Flash, nor do I (ever) want the two to be
compatible.

One particular need is for the timeline to be quickly traversable. If I
want to go to time=239.4 seconds, I'd like it to go there pretty much
painlessly and hopefully with one call. (Same with play, reverse and pause
really) I also want it to play for a long duration, with lots of different
items (images, audio, etc.)

<snip>

Ben -

This sounds very similar to a discrete event simulator, which uses a
timeline to track when the "next" event is supposed to occur, and advances
by events, rather than by straight elapsing of time (so that a 3 week
simulation doesn't take 3 weeks to run!). SimPy does this very thing, and
it also has a "real-time" mode so that simulations can be watched as they
would really transpire.

The one difference is that with SimPy, you don't really script the timeline
ahead of time, but instead you script the individual events, and the
resources that the various processes have to compete/contend for, thereby
causing the events to get spread out over time.

But you might get some clues from SimPy's traversal of the event queue, and
the alternative model of building the queue dynamically while "executing" it
might give you some other ideas about your game design. (I do recall that
SimPy's event queue can eventually grow to hold thousands of events, and a
huge speedup was accomplished a ver versions ago by using the bisect module
to insert new events at the proper location in the queue. But this is only
relevant if you build the queue dynamically.)

-- Paul