[Scummvm-devel] Kyrandia pathfinding issues

Neil Millstone neil at millstone.demon.co.uk
Sat Apr 18 00:19:41 CEST 2009

Matt wrote:
> 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.
> Thoughts?

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.

- Neil

More information about the Scummvm-devel mailing list