Greetings gang,
I thought some of the programming Wizards who put together ScummVM could answer a question for me.
What kind of pathfinding do the old Scumm game use? It works quite well for what it is...yet I'm thinking perhaps it's not A*? All the articles on the topic nowadays talk about A* or something that's more processor intensive than that, but I'm hoping/guessing that Scumm used some cleverer, cheaper trick to get it working.
Any general explanation of the method would be great.
Thanks!!
How does pathfinding work in Scumm?
Moderator: ScummVM Team
The only thng I know is that the resource files store all paths. For example, when a character is on Box 1 and he wants to go on Box2, SCUMM will automatically find in which box to go next by looking into an already computed matrix in the resource files (BOXM block). I don't know how this matrices were computed, but most likely with A*. Once the next box in the path is found, I have no idea what happens, I guess the path has to be filtered some way so that the characters don't always go in the center of the boxes or something... ScummVM guys might be able to ask this question though.
-
spacetroll
- Posts: 53
- Joined: Tue Jul 10, 2007 6:15 pm
You might find this article interesting:
http://graphics.cs.ucdavis.edu/~okreylo ... nding.html
I'm not that familiar with SCUMM's internals but I guess conceptually this is a similar approach, except here they use polygons while in SCUMM the polygons are restricted to be rectangles.
http://graphics.cs.ucdavis.edu/~okreylo ... nding.html
I'm not that familiar with SCUMM's internals but I guess conceptually this is a similar approach, except here they use polygons while in SCUMM the polygons are restricted to be rectangles.
ScummVM doesn't using anything complicated like A* at all!
Rather, the game screen is divided into so-called "boxes" (which in the later SCUMM versions could essentially be almost arbitrary non-overlapping quadrangles).
Normally, an "actor" (like e.g. Guybrush in Monkey Island) is confined to movement within those boxes. So at any time, an actor has a "current box" attribute assigned to it. Let's assume the actor is in box 1.
When the user clicks somewhere, the engine first determines which box the click was in. If it's the same as the actor to be moved is in anyway, it can just be walked there. That's easy. Now assume the click was in a different box, e.g. box 5. THen the engine first determines how to get to that box. For this, it looks in the "box matrix", which is essentially a precomputed n*n matrix, where n is the total number of boxes in the room. For each pair (i,j) of boxes, it contains a value k which says: "If you are in box i and want to get to get to box j, first go to box k". Note that "k" could equal j if box i and j are adjacent.
Now, equipped with this value, the engine will first compute a path for the actor to walk from its current position to the new box k. This depends on how the boxes i and k "touch".
Anyway, so the actor walks a bit and reaches box k. If this was the same as the box of our final destination, then we just walk to the final destination, and are done. If not, we rince and repeat: Look up the entry (k,j) in the box matrix to find the next box; walk to that; etc.
This probably sounds more complicated than it is, really
.
There is also code in ScummVM to compute the box matrix (not all game versions carried the box matrix in the resources, for some it had to be computed on the fly). This, too, is a very simple task, (see createBoxMatrix() in boxes.cpp), and we implement it using Kleene's algorithm (start with an incidence matrix, and iteratively compute the box matrix from that; the source code is documented, take a look there, and/or look it up on Wikipedia).
Rather, the game screen is divided into so-called "boxes" (which in the later SCUMM versions could essentially be almost arbitrary non-overlapping quadrangles).
Normally, an "actor" (like e.g. Guybrush in Monkey Island) is confined to movement within those boxes. So at any time, an actor has a "current box" attribute assigned to it. Let's assume the actor is in box 1.
When the user clicks somewhere, the engine first determines which box the click was in. If it's the same as the actor to be moved is in anyway, it can just be walked there. That's easy. Now assume the click was in a different box, e.g. box 5. THen the engine first determines how to get to that box. For this, it looks in the "box matrix", which is essentially a precomputed n*n matrix, where n is the total number of boxes in the room. For each pair (i,j) of boxes, it contains a value k which says: "If you are in box i and want to get to get to box j, first go to box k". Note that "k" could equal j if box i and j are adjacent.
Now, equipped with this value, the engine will first compute a path for the actor to walk from its current position to the new box k. This depends on how the boxes i and k "touch".
Anyway, so the actor walks a bit and reaches box k. If this was the same as the box of our final destination, then we just walk to the final destination, and are done. If not, we rince and repeat: Look up the entry (k,j) in the box matrix to find the next box; walk to that; etc.
This probably sounds more complicated than it is, really
.There is also code in ScummVM to compute the box matrix (not all game versions carried the box matrix in the resources, for some it had to be computed on the fly). This, too, is a very simple task, (see createBoxMatrix() in boxes.cpp), and we implement it using Kleene's algorithm (start with an incidence matrix, and iteratively compute the box matrix from that; the source code is documented, take a look there, and/or look it up on Wikipedia).