[Scummvm-devel] Kyrandia pathfinding issues

Neil Millstone neil at millstone.demon.co.uk
Fri Apr 17 16:28:51 CEST 2009

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.
>> I'm not sure what you mean. I can't run Dosbox on the DS, there's not 
>> enough RAM or CPU on the DS to run Dosbox.
> As stated by Pierre-Yves I was takling about DOSBox on a PC.
Ah.  Ok.
>> I don't think you'd notice the slowdown if you're playing on a fast 
>> machine like a modern PC.  The DS is only a 67Mhz ARM9, so is 
>> incredibly slow compared to anything recent ;-)
>> I can see some modifications to the pathfinder since the last major 
>> release but can't try reverting these because of other changes to the 
>> codebase making the old code incompatible with the current engine.
> I can't see any changes since 0.11.0, except one comments style 
> change. There was some code restructuring after 0.10.0, which 
> introduced some more virtual function calls in the pathfinder code, 
> but those are currently needed, because of code differences between 
> different Kyra game versions.
>> f this doesn't work, is it possible to make the pathfinding less 
>> accurate on a #define without breaking the game?  It's also possible 
>> that the slowness is down to virtual method calls, or something, 
>> where just inlining those would fix it without making any changes to 
>> the actual algorithm.  It all depends on how much time I get to look 
>> at it before Saturday.
> I don't think a define would be possible for the current code.
Well, I'll just see what I can hack tonight then, if compiler options 
don't do the trick.  I'd rather not release a build without games that 
were present in the last build, but I know the attitude to releasing 
builds after the release date isn't very forgiving.

So, given the choice of releasing without Kyra, and not releasing at 
all, leaving the current ancient version of ScummVM DS on the downloads 
page for another 6 months, I'll choose dropping Kyra.

- Neil

More information about the Scummvm-devel mailing list