The problem

I'm working on a text adventure game as a hobby project to teach myself some new Haskell concepts.

I've now run into the challenge of representing the levels (or 'scenes') in the game and the various ways in which they're connected. To keep things simple for myself, I've visualised the 'map' of the game as a simple 2d space, in which scenes are connected via cardinal directions (NESW):

        Lake
        ⇳
        Forest
        ⇳
Home  ⬄ Field*

*: Starting location

Here, going south from the lake would lead you to the forest, and vice versa; going west from the field would lead you to the home. The challenge here is that I need some way to encode not only which scenes are connected, but how they are connected, where 'how' refers to a cardinal direction.

Two options I've considered so far are representing levels as a graph or using lists of tuples, but I'm not entirely happy with either approach.

Representing scenes as a Graph

My basic approach in representing scenes and their connections as a graph was as follows:

data Scene = InitialField | Forest | House | Lake

-- |`gameScenes` maps scenes to their integer representation, as used in `sceneGraph`.
gameScenes :: Map Int Scene
gameScenes =
    let scenes =
            [ (0, InitialField)
            , (1, Forest)
            , (2, House)
            , (3, Lake)
            ]
    in
        fromList scenes

-- |the `sceneGraph` describes the way different scenes of the game connect to each other.
sceneGraph :: Graph
sceneGraph =
    let
        bounds = (0, 3)
        edges =
            [ (0, 1) -- link initial field to forest
            , (0, 2) -- link initial field to house
            , (1, 3) -- link forest to lake
            ]
    in
        buildG bounds edges

Downside: The main limitation here is that this graph does not encode any information with regards to cardinal directions. This is unfortunate, because aside from that limitation, a graph seems like a perfect data structure to represent scenes (vertices) and their linkages (edges). Is there any way to encode 'metadata' (in this case, cardinal directions) of edges in a graph?

Representing scenes using list of tuples

When I came upon the above limitation, I decided to try a different approach and represent the links between scenes as a list of tuples:

data Scene = InitialField | Forest | House | Lake
data CardinalDirection = North | East | South | West
type LinkedScene = (CardinalDirection, Scene)

-- |`linkedScenes`, applied to a `Scene`, returns a list of the connected scenes and their cardinal directions.
linkedScenes :: Scene -> [LinkedScene]
linkedScenes InitialField = [(North, Forest)]
linkedScenes Forest = [(South, InitialField), (West, Lake)]
-- The other links are left as an exercise for the reader ;)
linkedScenes _ = []

Downside: This approach does allow us to encode the linkages between different scenes simply by applying sceneLinks to the Scene the player is currently in, but it has a big, ugly downside: it requires us to double-endedly encode the spatial linkages between scenes. In other words, if we know that the forest is north of the field, we need to write two functions: one that takes Forest and yields [(South, InitialField)], and an inverse one that takes InitialField and yields [(North, Forest)]. This seems like it's begging for bugs: if I ever want to add a scene, or change the layout of the game world, I need to remember to double-check every single linkage from both ends.

Summing up: requirements

Ideally, I am looking for an approach that:

• Allows me to encode a bidirectional relationship between scenes using a single data point (no 'double-ended' encoding as in the second approach, since that is asking for bugs);
• Allows me to easily change the layout of the game/map at a later stage, without a giant headache;
• Is guaranteed to be spatially consistent at compile time, meaning that it does not allow for invalid spatial configurations, such as a state in which the player starts at the field, goes north to the forest, goes back south and suddenly finds themselves in the lake. I am not certain that this is possible without dependent types, however.

If anyone could think of such an approach, it would surely be someone in the Haskell community :)

Thanks!

CodePudding user response：

I see two options:

1. Go with the simple graph, but additionally embed the scenes in a two-dimensional space. Then from any given point, the graph tells you which other scenes are neighbours, and by taking the difference in the vector space you can obtain the direction.

   This is simple to visualize and implement. Disadvantage is that it brings in an absolute frame of reference, meaning you can just link two locally designed groups of scenes together but first need to translate them to avoid overlaps. Also, it's kind of boring and precludes emergent non-Euclidean geometry... if you're into that kind of thing.

   (Note that you could still have non-Euclidean geometry by embedding into a non-flat manifold. In this case you could use the PseudoAffine class for the distances.)

2. Go with the list of tuples, but wrap it all in your own graph-like abstraction. QuickCheck that abstraction to death, and only export an interface that automatically keeps track of synchronising the changes between neighbouring nodes. Then in the actual game, only manipulate the scenes-world through the abstract interface.

CodePudding user response：

Start with triples describing some of the connections:

data Scene = Field | Forest | House | Lake
data Dir = N | E | S | W
type Edge = (Scene, Dir, Scene)

uniEdges :: [Edge]
uniEdges = [(Field, N, Forest), (Forest, W, Lake)]

Expand to the full map by reversing all the tuples:

class Dual a where dual :: a -> a
instance Dual Dir where
    dual N = S
    dual E = W
    dual S = N
    dual W = E
instance Dual Edge where dual (s, d, s') = (s', dual d, s)
instance Dual a => Dual [a] where dual = map dual

allEdges :: [Edge]
allEdges = uniEdges    dual uniEdges

Then insert these into whatever data structure you like; a Map Scene (Dir, Scene) or a Gr or whatever.

One nice feature of this approach: it leaves you with the ability to decide later that not all edges should turn back on themselves without changing all the users of the scene graph, as in this map with a curved path:

House
  |
   \
    `--Lake