What's wrong with my tree traversal code?
I have a simple tree, defined thusly:
type BspTree =
| Node of Rect * BspTree * BspTree
| Null
I can get a collection of leaf nodes (rooms in my tree "dungeon") like this, and it seems to work:
let isRoom = function
| Node(_, Null, Null) -> true
| _ -> false
let rec getRooms dungeon =
if isRoom dungeon then
seq { yield dungeon }
else
match dungeon with
| Node(_, left, right) ->
seq { for r in getRooms left -> r
for r in getRooms right -> r }
| Null -> Seq.empty
But now I'm trying to get sister leaf node rooms so I can connect them with corridors, and I'm failing miserably (as I often do). Here's my attempt:
let rec getCorridors dungeon =
match dungeon with
| Null -> failwith "Unexpected null room"
| Node(_, left, right) ->
match left, right with
| Null, Null -> Seq.empty
| Node(leftRect, _, _), Node(rightRect, _, _) ->
if isRoom left && isRoom right
then seq { yield makeCorridor leftRect rightRect }
else seq { for l in getCorridors left -> l
开发者_开发百科 for r in getCorridors right -> r }
| _ -> failwith "Unexpected!"
I just end up with an empty seq. Anyway, this all hurts my brain, and I know it's unlikely anyone will slog through it, but I figured it wouldn't hurt to ask.
As Robert commented, maybe your makeCorridor function needs some attention. I've adapted your code, making my own makeCorridor function and replacing Rect by int.
I've used an active pattern to determine when a BspTree is a room. I've also used yield! sequence
instead of for x in sequence -> x
. These modifications result in the same behavior. I just wanted to show what an active pattern can do:
type BspTree =
| Node of int * BspTree * BspTree
| Null
let (|IsRoom|_|) dungeon =
match dungeon with
| Node(_,Null,Null) -> Some dungeon
| _ -> None
let rec getRooms = function
| IsRoom dungeon -> Seq.singleton dungeon
| Null -> Seq.empty
| Node (_, left, right) -> seq { yield! getRooms left
yield! getRooms right }
let makeCorridor leftNode rightNode =
match leftNode, rightNode with
| Node(left,Null,Null), Node(right,Null,Null) ->
sprintf "(%d) -> (%d)" left right
| _ -> failwith "Illegal corridor!"
let rec getCorridors = function
| Null -> failwith "Unexpected null room"
| Node(_, Null, Null) -> Seq.empty
| Node(_, IsRoom left, IsRoom right) -> seq { yield makeCorridor left right }
| Node(_, left, right) -> seq { yield! getCorridors left
yield! getCorridors right }
Example:
let dungeon =
Node(1, Node(2, Node(4,Null,Null),
Node(5,Node(8,Null,Null),
Node(9,Null,Null))),
Node(3, Node(6,Null,Null),
Node(7,Null,Null)))
Result in FSI:
> getCorridors dungeon;;
val it : seq<string> = seq ["(8) -> (9)"; "(6) -> (7)"]
精彩评论