Graphs

20 09 2006

I originally began my project in C# but quickly hit its abstraction ceiling. Well, I did not actually hit it but thinking forward to what I wanted to do, I realized that I need the best abstractions that the CLI could provide. Good as C# is, it is still too similar to C++ and Java.Whenever someone says .NET, people instantly think C#, which for people who enjoy exploring the outer edges of .NET (or more appropriately, the CLI) can be quite feather ruffling. With respect to programming, my project was began for three reasons: to rekindle my interest in programming, learn about .NET and the language independence it claims and to test its CLI claims. It has lived up to and beyond claims made in this area. Indeed Rebooted was suprised that I was able to get all the languages working cross platform – it was due to no special skill of mine but the incredible ease that which the CLI allows all those who obey its rules to interoperate. The languages need not know about each other so long as they speak the common tongue. Now, it is not completely trivial – there is still a need to design what classes you plan to expose outwards carefully, especially with respect to types (or enter typing hell – super nested generic classes), so they can be consumed without being choked on. Nonetheless the process is smooth and I have yet to feel the need to beat my computer with a bat while working on this project.

As stated in an earlier post and will be gone over in further detail in a future post, I have switched to Nemerle as the main vehicle for my engine for reasons due to its incredible macro system (lisp level, quotations, exposed compiler api), OOP and ease of code organization, rich type system (perhaps overly so…despite .net) and is functional (despite .net). The last part is what I want to focus on in this post.

People wonder if you can write a game in a functional language. I say yes but not in the strict sense. I take the same stance of functional programming as the makers of OCaml where (loosely quoting) they state that functional programming is not so much about immutability and lack of state but rather a program that is more or less a composition of black box like functions that though they may contain some mutability internally, on the whole, the behaviour of the program is essentially functional.

Nonetheless it does not do to obsess over a paradigm at the expense of sensibility. Some problems are more tractible taken from an imperative stance while others are from a functional. That is why functional languages that mix this well allow for ease of concept -> code as smoothly as possible. What Nemerle does is mix the concepts OOP quite seamlessly with functional programming. This has the added advantage of not only allowing the abstractions of the functional paradigm but also the organizational benefits of OOP. However this post will not show much Nemerle syntax (due to its rich type code of Nemerle the stuff I will show required alot of upcasts and type constraints and other stuff with the IL code not as good as F# version and so it made alot more sense to keep it in F#).

By abstracting away, you reduce the number of steps that take you from concept idea to concrete code, allowing less mistakes and efficient implentation. It makes alot of sense to write an RPG in a functional language.

In fact it does not make sense to write an RPG in a language like C++. RPGs contain alot of concepts (quests, game-player interactions, conversations, magic, skills, vocations/jobs/class, pathfinding, …) that are best represented with recursion, recursive data types and deconstructed with pattern matching.

I recently faced this when I decided to approach conversation in the game. Even C# did not have the appropriate constructs to do this most succintly. At first I thought to represent the conversations as trees but felt that they were not the most appropriate data structure. Thinking further, I realized that conversations are nothing more than directed graphs such that each node or vertex is either of type R (responses) or S (statements). Where for each R there is only one edge and each S has an edge to unique Rs (since if it does not then the S was not well formed). Each S has an edge to atleast one R node even if R is the empty node. By directed graph I mean a set (V,E) of vertices and edges with directed meaning that the edges are arrows:

conv_graph.jpg

I can think of no uses of the tools of graph theory with NPC conversing but if the need ever arises I will be sure to post on it. Nonetheless I set out to represent this concept in code. I realized that a graph could be treated as a list of vertices where each vertex is paired with a list of edges it points to. Hacking concepts out on the interactive top level of Ocaml i was able to come up with the following code:

let ins v g = (v , []) :: g

let edges_to a b g =
  let rec edg a b g g2 =
     match g with
        l :: g -> if fst l = a then ((a, b :: snd l) :: g2) @ g
                  else edg a b g (l::g2)
        | _ -> g
   in edg a b g []

let g1 = ins "Hello" []
let g2 = ins "bye" g1
edges_to "Hello" "bye" g2
;; 

The code is far shorter than the equivalent C# or C++ version would be. As well, by using the top level of OCaml I was able to accelerate my brainstorming and be assured that not only will I not have syntax errors when rewriting for the game, that it would work with no logical errors. As I stated earlier this did not translate well to Nemerle so I decide to do it in F#. However, to get it to communicate with other languages I had to rebrand it with .NET compliant classes.

The relevant F# code:

type 'a graph = ('a * 'a list) list 

let ins v g = (v , []) :: g

let rec edg a b g g2 =
     match g with
        l :: g -> if fst l = a then ((a, b :: snd l) :: g2) @ g
                  else edg a b g (l::g2)
        | _ -> g 

type 'a Graph = class
	new (a) = {graph_object = ins a [] }
	val mutable graph_object: 'a graph

member this.Insert_Edge (vertex_a, vertex_b) = 
		this.graph_object <- edg vertex_a vertex_b this.graph_object []
	member this.Insert (v)  = 
		this.graph_object <- (v , []) :: this.graph_object
	member this.List_Edges_To (v) = 
		List.to_array (List.assoc v this.graph_object)
end

Examples of usage:

dbg.PNG
The next post will not just be a test but will build converation around this and making accessing and listing much easier to the end user/me.

Advertisements

Actions

Information

One response

7 12 2006
Don Syme

Interesting stuff! I’m looking forward to subscribing to your blog.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: