Author Topic: How did AGI and SCI do path finding  (Read 4434 times)

0 Members and 1 Guest are viewing this topic.

Offline Uhfgood

How did AGI and SCI do path finding
« on: March 22, 2017, 11:59:50 PM »
Kind of curious how they did pathfinding back in the day.  My search led me to believe that SCI 1.1 has real pathfinding, but how does it work, and what did the earlier versions do? (AGI and SCI 1.0)



Offline troflip

Re: How did AGI and SCI do path finding
« Reply #1 on: March 23, 2017, 12:08:35 AM »
Funny, I was just delving into this.

AGI and SCI0 had no pathfinding (SCI0 had an "Avoider", which is a clumsy half-baked attempt at pathfinding).

SCI1 and up had real pathfinding (the AvoidPath kernel), based on polygons. You can use a points-of-visibility graph (a graph that defines the line-of-sight connections between the concave points of a polygon), and run an A* algorithm over that. I don't think that's exactly how SCI did it, but it would produce a similar result. ScummVM implements the SCI pathfinding, so you can look at that source code to see how they reverse engineered it.
« Last Edit: March 23, 2017, 12:10:09 AM by troflip »
Check out my website: http://icefallgames.com
Groundhog Day Competition

Offline Kawa

Re: How did AGI and SCI do path finding
« Reply #2 on: March 23, 2017, 07:06:29 AM »
This certainly makes the maze in Mixed-Up Fairy Tales somewhat ridiculous.

Offline OmerMor

Re: How did AGI and SCI do path finding
« Reply #3 on: March 24, 2017, 02:27:35 PM »
Here's a report by Walter van Niftrik (waltervn) from 2006 on the subject:
FreeSCI pathfinding extension (from archive.org)

If you prefer a wiki format, it's also available on ScummVM's wiki:
http://wiki.scummvm.org/index.php/SCI/FreeSCI/Pathfinding


Offline troflip

Re: How did AGI and SCI do path finding
« Reply #4 on: March 24, 2017, 08:00:03 PM »
Ah, I remembered there was some paper on it.

Some of their specifications on this page seem wrong though. The edges of a polygon are always valid for the ego to walk on (I just verified this with Sierra SCI this morning), but that paper claims the edges are "barred". Anyway, we know whatever implementation ScummVM has works :-).

Check out my website: http://icefallgames.com
Groundhog Day Competition

Offline Kawa

Re: How did AGI and SCI do path finding
« Reply #5 on: March 24, 2017, 08:26:33 PM »
Wasn't there also something about the winding order?

Offline lskovlun

Re: How did AGI and SCI do path finding
« Reply #6 on: March 24, 2017, 09:10:05 PM »
Here's a report by Walter van Niftrik (waltervn) from 2006 on the subject:
And here I was thinking that you would point to the source  ;D
https://github.com/OmerMor/SCI16/blob/master/INTERP/GETPATH.C

or to the patent, which was a large part of the reason we had to do it differently...
https://patents.google.com/patent/US5287446A/en

Offline troflip

Re: How did AGI and SCI do path finding
« Reply #7 on: March 24, 2017, 11:24:14 PM »
Wasn't there also something about the winding order?

It did mention that the patent implied winding order had to be a specific way, but that games supplied polygons with either winding order, and so Sierra's engine handled it anyway (it's trivial to automatically change the winding order if it's the wrong way - SCI Companion does this when it saves the polygons, although I guess it doesn't need to).

The restriction that polygons couldn't intersect is interesting. "SCI Quest" uses some overlapping polygons in spots, I wonder if that's why the pathfinding seemed a little wonky (if I recall correctly).

For Cascade Quest's engine, in which I just implemented pathfinding, I use the clipper library to subtract barred polygons from contained access. That gives me a set of non-intersecting polygons indicating where the ego can go. Then it's just A* over the concave points in those polygons. It mostly works, but I still have some problems with rounding errors, which that paper talks about too.

The restriction on overlapping polygons probably explains why Sierra didn't auto-create barred polygons for props that block Actors from passing through them. The Door class (in some games) has code for creating polygons from its bounding rect, but Views/Props don't. Then places where they need to block the ego, it looks like they "manually" assign them polygons, which probably means they could craft them carefully so that they don't intersect.
Check out my website: http://icefallgames.com
Groundhog Day Competition

Offline OmerMor

Re: How did AGI and SCI do path finding
« Reply #8 on: March 25, 2017, 07:09:09 AM »
And here I was thinking that you would point to the source  ;D
https://github.com/OmerMor/SCI16/blob/master/INTERP/GETPATH.C

First time I'm looking at that piece. It has some cool ASCII art!  ;D

Offline lskovlun

Re: How did AGI and SCI do path finding
« Reply #9 on: March 25, 2017, 04:32:59 PM »
I've seen mention of a test suite for polygons... that one would be quite revealing, I guess.


SMF 2.0.14 | SMF © 2017, Simple Machines
Simple Audio Video Embedder

Page created in 0.112 seconds with 23 queries.