Scumm findPathTowrads algorithm

Ask for help with ScummVM problems

Moderator: ScummVM Team

Post Reply
limulo
Posts: 1
Joined: Wed Jul 05, 2017 12:49 pm
Contact:

Scumm findPathTowrads algorithm

Post by limulo » Wed Jul 05, 2017 3:45 pm

Hi everyone,

in the last couple of days I've been examining the source code of the scumm engine implementation and I'd like to ask a question about a specific algorithm. The code I'm stucked on is the function `findPathTowards` at line 800 of `boxes.cpp` file.

This function seems to examine the 4 coordinates of 2 adjacent boxes. It then compares the coordinates each time a new clockwise rotation of their names happens.

In order to go deeper into the subject, I'm actually curious to know if this algorithm has a name or where it comes from.
Thank you for your support

bye
limulo

digitall
ScummVM Developer
Posts: 964
Joined: Thu Aug 02, 2012 1:40 pm

Post by digitall » Thu Jul 06, 2017 12:26 am

I am no expert on SCUMM engine internals, but see this:
https://gamedev.stackexchange.com/quest ... l-relevant

I think this is much simpler and less resource hungry compared to the more general algorithms for 2D pathfinding such as A*, but required manual / precomputed walkbox to work... but consider that these were intended for 286 PC era machines and the constraints of RAM and CPU time required this:
https://en.wikipedia.org/wiki/Pathfinding

Post Reply