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




hoorray

19 09 2006

YESSSS!! I have got it working. The engine is written in Nemerle. I recompiled the appropriate F# module had to apply the appropriate arguments by hand at a console eww. A special CLI independent version of the compiler was given, my version of F# was written when mono did not support generics. btw the people who wrote F# invented generics for .net…F# is like the C of .net – the next level after assembly in terms of performance. More on everything later.

Screenshot:Linux:

screenshot.png

Windows:

screen2.JPG

Mac OSX:

I dont have it but that is supported too


wooh 0 fps! Psych im running Ubuntu through VMPlayer with lots of background tasks both on Ubuntu and windows not to mention a few firefox crashes and leakages. Im quite certain if it can run at ~2 – 5fps here then i have little to worry about in terms of speed.

The windows one is running at 85fps on top of vmplayer.. There is a lot more going on than the simple screen would suggest. Graphics library allowing system independent code is Irrlicht.net CP.

Python script.

tex1 = graphics.scene_author.texture_pool.Load_Texture("Stone_Sample_002.JPG")

graphics.scene_author.Add_Sky_Box("sk5n.bmp", "sk5n.bmp",
                   "sk4n.bmp", "sk2n.bmp",
                   "sk1n.bmp", f = "sk3n.bmp")

plane = graphics.terrain.Create_Terrain_with_plane(width = 3000, height = 3000)
graphics.scene_author.Add_Terrain_to_scene_Plane(plane, tex1)

the bmps were originally in a textures subdirectory but i had to change the script and copy bmps to same dir as app. THe solution to this is quite easy thanks to .NET! More and how I was able to change my graphics layer in a way that didnt break scripting to later.. Ramble ramble

A more cohesive post tomorrow / later





Portability

19 09 2006

WARNING **: The class Microsoft.FSharp.Unit could not be lo aded, used in fslib, Version=1.1.10.4, Culture=neutral, PublicKeyToken=a19089b1c74d0809

=================================================================
Got a SIGSEGV while executing native code. This usually indicates
a fatal error in the mono runtime or one of the native libraries
used by your application.
=================================================================

Stacktrace:

in transcendent.GraphicObject:Load_Texture (string) <0xffffffff>
in transcendent.GraphicObject:Load_Texture (string) <0x43>
in (wrapper dynamic-method) System.Object:Load_Texture##1 (object,object) <0x9f2>
in (wrapper delegate-invoke) System.MulticastDelegate:invoke_object_object_object (object,object ) <0xffffff85>
in IronPython.Runtime.OptimizedFunction2:Call (object) <0x3d>
in IronPython.Runtime.BuiltinFunction:Call (object[]) <0x4c>
in IronPython.Runtime.ReflectedMethodBase:TryOptimizedCall (object[],object&) <0x5e>
in IronPython.Runtime.ReflectedMethodBase:TryCallWorker (object[],object&) <0x51>
in IronPython.Runtime.ReflectedMethodBase:Call (object[]) <0x1f>
in IronPython.Runtime.ReflectedMethodBase:Call (IronPython.Runtime.ICallerContext,object[]) <0xa 0>
in IronPython.Runtime.ReflectedMethodBase:Call (IronPython.Runtime.ICallerContext,object) <0x47>
in IronPython.Runtime.Ops:CallWithContext (IronPython.Runtime.ICallerContext,object,object) <0x5 1>
in (wrapper dynamic-method) System.Object:input##0 (IronPython.Runtime.Frame) <0x561>
in (wrapper delegate-invoke) System.MulticastDelegate:invoke_object_Frame (IronPython.Runtime.Fr ame) <0xffffffd3>
in IronPython.Runtime.FrameCode:Run (IronPython.Runtime.Frame) <0x43>
in IronPython.Hosting.PythonEngine:ExecuteFile (string) <0x84>

All that is in my way from porting my game to mono and acheiving crossplatform freedom is that F# dont play nice with mono and ECMA standards by default. argh.