[Scummvm-devel] Kyrandia pathfinding issues
neil at millstone.demon.co.uk
Sat Apr 18 00:19:41 CEST 2009
> On Fri, 17 Apr 2009, Neil Millstone wrote:
>> Johannes Schickel wrote:
>>> Neil Millstone wrote:
>>>>> KYRA's pathfinder is rather simple & stupid. I remember it might
>>>>> search through the whole scene borders when calculating a patch. It
>>>>> does so in both directions (counter clock wise and clock wise) and
>>>>> if no possibility is found it tries to find the nearest accessible
>>>>> point. All in all that's *some* positions processed, but 10 seconds
>>>>> sound too much. Just for your information, a scene can contain
>>>>> something like 80*60 positions at maximum, but it shouldn't really
>>>>> try all of them. Did you try how fast it is in DOSBox? Since our
>>>>> implementation should be identical to the original such a delay
>>>>> should be noticeable in the original DOS version too.
> Just out of curiosity, can the pathfinder that Walter developed for
> FreeSCI be used here? Eliminating this duplication wouldn't be
> appropriate for a point release, but would potentially be useful for
> the next major release.
> This would also be a good component for me to add unit tests for,
> assuming its feasible to make the code generic enough to be shared in
> the first place.
Well, I'm not sure, to be honest. I would imagine the games store their
walk box data in quite different ways, and so a different piece of code
would be needed to evaluate them. Maybe also some engines are not
looking for the best path, but one that the original engine would have
chosen. I would guess that a generic pathfinder wouldn't be possible
although I'll wait for one of the engine devs to answer it properly.
After 100s of printfs, I finally found the problem with Kyra, and it's
nothing to do with the pathfinder as I initially thought.
In KyraEngine_v1::updateInput(), the engine polls the event manager for
input. This event manager appears to collect events while the engine is
busy playing an animation. This means that by the time the animation
has finished, there are hundreds of mouse move events in the event
buffer. When the game eventually calls updateInput(), it calls the
backend's updateScreen() for every one of these events. This causes the
long pause I was seeing.
I've implemented a hack in the DS backend which throttles the maximum
rate that mouse move events can be generated. This seems to help/fix
it. I haven't tested too much to find out, and theoretically it could
still cause problems on long cutscenes, but this should be hugely better
than it was.
This could be a problem on other ports, where updateScreen() is
expensive, depending on how mouse move events are generated by the backend.
More information about the Scummvm-devel