CODEWITHSUNDEEP
haskelldata-structures
epsilonhalbe
epsilonhalbe

Reputation: 15959

What datatype to choose for a dungeon map

As part of a coding challenge I have to implement a dungeon map.

I have already designed it using Data.Map as a design choice because printing the map was not required and sometimes I had to update an map tile, e.g. when an obstacle was destroyed.

type Dungeon = Map Pos Tile

type Pos = (Int,Int) -- cartesian coordinates
data Tile = Wall | Destroyable | ...

But what if I had to print it too - then I would have to use something like elaboratePrint . sort $ fromList dungeon where elaboratePrint takes care of the linebreaks and makes nice unicode symbols from the tileset.

Another choice I considered would be a nested list 

type Dungeon = [[Tile]]

This would have the disadvantage, that it is hard to update a single element in such a data structure. But printing then would be a simple one liner unlines . map show.

Another structure I considered was Array, but as I am not used to arrays a short glance at the hackage docs - i only found a map function that operated on indexes and one that worked on elements, unless one is willing to work with mutable arrays updating one element is not easy at first glance. And printing an array is also not clear how to do that fast and easily.

So now my question - is there a better data structure for representing a dungeon map that has the property of easy printing and easy updating single elements.

Upvotes: 2

Views: 254

Answers (2)

daniel gratzer
daniel gratzer

Reputation: 53901

How about an Array? Haskell has real, 2-d arrays.

import Data.Array.IArray -- Immutable Arrays

Now an Array is indexed by any Ix a => a. And luckily, there is an instance (Ix a, Ix b) => Ix (a, b). So we can have

 type Dungeon = Array (Integer, Integer) Tile

Now you construct one of these with any of several functions, the simplest to use being

array :: Ix i => (i, i) -> [(i, a)] -> Array i a

So for you,

startDungeon = array ( (0, 0), (100, 100) )
              [ ( (x, y), Empty ) | x <- [0..100], y <- [0..100]]

And just substitute 100 and Empty for the appropriate values.

If speed becomes a concern, then it's a simple fix to use MArray and ST. I'd suggest not switching unless speed is actually a real concern here.

To address the pretty printing

import Data.List
import Data.Function

pretty :: Array (Integer, Integer) Tile -> String
pretty = unlines . map show . groupBy ((==) `on` snd.fst) . assoc

And map show can be turned in to however you want to format [Tile] into a row. If you decide that you really want these to be printed in an awesome and efficient manner (Console game maybe) you should look at a proper pretty printing library, like this one.

Upvotes: 4

leftaroundabout
leftaroundabout

Reputation: 120731

First — tree-likes such as Data.Map and lists remain the natural data structures for functional languages. Map is a bit of an overkill structure-wise if you only need rectangular maps, but [[Tile]] may actually be pretty fine. It has O(√n) for both random-access and updates, that's not too bad.

In particular, it's better than pure-functional updates of a 2D array (O(n))! So if you need really good performance, there's no way around using mutable arrays. Which isn't necessarily bad though, after all a game is intrinsically concerned with IO and state. What is good about Data.Array, as noted by jozefg, is the ability to use tuples as Ix indexes, so I would go with MArray.

Printing is easy with arrays. You probably only need rectangular parts of the whole map, so I'd just extract such slices with a simple list comprehension

[ [ arrayMap ! (x,y) | x<-[21..38] ] | y<-[37..47] ]

You already know how to print lists.

Upvotes: 3

Related Questions