SCI32 Source Code

[Kawa]

I'm okay with using A*, ScummVM uses it to great effect. My problem then is creating the graph for A* to use.

Allow me to steal an old picture from Phil's blog.


The yellow lines, as I understand it, are key to the A* phase.

Great. Now I have to merge polygons together for use and somehow build a web of edges for A* to use.

[Fox]

AAAA 00XA X000 XAAA 000X AX00 AAAA AAAX
XXAA  00XA AX00 0XAA 00XA AX00 AAXX AAX0
00XA  0XAA AAXX 00XA XXAA AAX0 AX00 AX00
000X  XAAA AAAA 00XA AAAA AAAX X000 AX00


A = walkable area
X = white border line

My suggestion:
1) detect 'blunt' edges in the walkable border lines (the white lines) using possible byte masks above
2) when a blunt edge is detected generate a node in the A* Graph
3) Try to connect all the found blunt edges via yellow edges with other blunt edges these form the transitions to other nodes in the A* Graph. A yellow line can not cross a white line. Note that the sharp edges don't have yellow lines.
4) Make a function to determine which graph points surround ego, make the node lying most in the direction of the mouse click the start node
5) Run the A* algorithm with heuristic that ego likes to walk straight in direction of the target
6) The A* algorithm finds the edge point lying most close to destination point.
7) A simple moveTo can be made from last edge point to destination point.

[Kawa]

I think you may have misunderstood the picture.

Though it looks like SCI0, which had no polygons, Cascadia Quest is not in fact SCI0 and does have polygons. Phil added SCI11-style polygon support himself. The white lines in the picture are not like the white lines on the SCI0 control screen. They are just a visualization of the SCI11-style polygons.

And SCI11-style polygons are what I'm after for my engine.

[troflip]

There are two tricky parts:
- coming up with the graph of edges
- dealing with all the floating point issues

On my blog, for the first one I talk about:

Another possibility is to use the concave vertices of a polygon. David Gouveia has a good article on this. Basically, by determining the interior line-of-sight connections between the concave vertices, you have all you need for pathfinding. Your start and end points (as long as they are within bounds) are guaranteed to connect to one of the concave vertices.

But it looks like that link is now broken lol...

[troflip]

Hmm, looks like it's here now:
https://www.david-gouveia.com/pathfinding-on-a-2d-polygonal-map

[Kawa]

I've gone over that page four times now. It still won't click for me how to actually do those things.

Edit: David Gouveia's page mentioned two parts of Game Programming Gems 1 and 2. I acquired copies and checked out the parts about pathfinding and... I'm still lost.

[EricOakford]

I've put together a barebones template in SCI32. It was built from the Torin's Passage demo. Download it here.

All system scripts are based on the 10/12/1995 source.

I was pleased to find that the interpreter for the Torin demo appears to have no version stamp check. So that's one obstacle cleared.

There's still one other issue: if the resource file is modified, SCICompanion mistakenly auto-detects the resource.map format as SCI1.0 and no LOFSA absolute. This results in errors relating to offsets if the resource file is altered any further!

[MusicallyInspired]

Does the Torin's Passage demo interpreter still support MIDI-based sound resources?

[EricOakford]

Yes, the interpreter still has MIDI support; I tested it myself. But since the music drivers weren't included, I grabbed the ones from the SQ6 demo.

[Collector]

Nice, but wouldn't Companion need to be updated to handle things like V56 and P56 resources? Would the compiler need to be updated? It would be nice to be able to build SCI32 games.

[Kawa]

Nice, but wouldn't Companion need to be updated to handle things like V56 and P56 resources? Would the compiler need to be updated? It would be nice to be able to build SCI32 games.

Both seem to work fine... except that you can't edit P56 resources. The compiler seems to work too... it's just that map format thing that's the worst issue here.

[EricOakford]

One thing I did notice in regards to the view editor - if you modify a view, there's a risk of it not displaying properly in the game. I discovered this when removing the embedded palette from the stock arrow cursor - the lower half of the cursor is gone in the game, but it is shown properly in the view editor.

On the plus side, SQ6 Roger looks simple enough (mostly solid colors instead of being really pixellated like GK1 Gabriel) to recolor into a generic ego. Sometimes the cartoony look pays off...