[Scummvm-devel] Kyrandia pathfinding issues

Neil Millstone neil at millstone.demon.co.uk
Fri Apr 17 12:06:59 CEST 2009

Johannes wrote:
> 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.
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.

Also, this code ran fine in previous versions, so I'm not sure why it would be so much slower now.

> 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.
I agree, a change like that at this point would be too risky.
>> > 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
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'm going to try adjusting compiler optimisation options to help it, as I've switched instruction sets since the last build (in order to get around the growth of the binary) so it's possible this would have made the performance worse. I can optimise just the one file concerned.

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

Failing that, my only other option would be to release without Kyrandia support since it's not playable at the moment.

Thanks for your help,

- Neil

More information about the Scummvm-devel mailing list