Author Topic: SCI32 Source Code  (Read 5153 times)

0 Members and 1 Guest are viewing this topic.

Offline Kawa

Re: SCI32 Source Code
« Reply #30 on: April 22, 2020, 07:08:14 AM »
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.

Offline Fox

Re: SCI32 Source Code
« Reply #31 on: April 23, 2020, 12:28:14 PM »

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.


Offline Kawa

Re: SCI32 Source Code
« Reply #32 on: April 23, 2020, 03:47:28 PM »
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.

Offline troflip

Re: SCI32 Source Code
« Reply #33 on: April 23, 2020, 05:00:32 PM »
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:

Quote
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...
Check out my website: http://icefallgames.com
Groundhog Day Competition

Offline troflip

Re: SCI32 Source Code
« Reply #34 on: April 23, 2020, 05:01:08 PM »
Check out my website: http://icefallgames.com
Groundhog Day Competition

Offline Kawa

Re: SCI32 Source Code
« Reply #35 on: April 23, 2020, 07:53:50 PM »
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.
« Last Edit: April 23, 2020, 09:50:13 PM by Kawa »


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

Page created in 0.08 seconds with 25 queries.