[Scummvm-devel] Kyrandia pathfinding issues

Johannes Schickel lordhoto at gmail.com
Fri Apr 17 14:17:52 CEST 2009

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.

> 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.

// Johannes

More information about the Scummvm-devel mailing list