[Scummvm-devel] Kyrandia pathfinding issues

[Johannes Schickel]

Neil Millstone wrote:
> I've been testing ahead of the release later this month, and have found 
> issues with Kyrandia 1's pathfinding.  It seems that it can take more 
> than 10 seconds to find a path from one side of the screen to the other 
> on the DS.  This makes the game almost unplayable.
>   

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.

Of course one might think of just implementing a new pathfinder for 
KYRA. I myself don't have the time for that before 0.13.1 and I would 
say it would be too risky to adopt a new one for a minor-release anyway. 
I might look into a new pathfinder after release though.

> One particular bad case is found on the screen 'Below Brandon's Home' 
> right near the game's starting point. 
>
> To reproduce this issue:
> 1) Start a new game.
> 2) Exit the room
> 3) Skip the cutscene
> 4) Click the bottom of the screen to travel down on the root
> 5) You should be in 'Below Brandon's Home'.  On the left side of the 
> screen there is a root that's slightly lighter than the rest.  
> Underneath this is a dark patch of grass.  Click this patch of grass and 
> the DS takes 10 seconds to calculate a route.
>
> I've tried this on the PC, and there's not even a hitch - but this is 
> probably to be expected since my PC is many times more powerful than a DS.
>   

I can't reproduce that other here either, but I'm not sure which place 
you are talking about exactly. It would be nice if you could supply a 
screenshot with the spot marked. There's some debugging code in the KYRA 
pathfinder which could be enabled to check which positions it searches 
when trying to calculate that path.

// Johannes