Saturday, April 30, 2005

Recommended Game Programming Books (updated)

Game Programming Books






Software Engineering and Computer Games: Learn Software Engineering by Computer Game Design with Windows MFC and OpenGL [UK] [US]

This is an excellent book, infact probably one of the best computer programming books.

The title sounds hideous who ever did the marketing for this one should be fired. It's not really anything to do with MFC or OpenGL for that matter. It is about how to organise you code, how you object orientated design, what programming patterns should be used for computer games. It's gold.







Managed DirectX 9 (Kick Start S.) [UK] [US]

Excellent introduction, no-nonsense covering DirectX using C# in straightforward easy to understand language. I use this as a reference all the time.

The author is the development lead for managed directX so he's knows what he's talking about. He also has a blog.


So not that many game programming books this is because there aren't all that many goods ones. I've read quite a few as well and will continue to do so!


Other Books





Read this! Then read everything else he has written. It's excellent and will give you lots to think about. In a round about way it's about programming "thinking". But it's much more than that. I don't agree with everything he says (i think he overestimates the amount of information in music) but it's all interesting and should be read.



A book bursting with ideas that will help you think in different ways. An inspirational book I think, very good. Great to just open up anywhere.




This is the graphics theory text. Anyone who programs advanced computer graphics will have this book as a reference. Needless to say it's quite high level :o

The Official Book Of Ultima

I want this book so much but it's very hard to find. It goes through the methodology of Ultima and how the games where crafted.

Friday, April 29, 2005

The Dragon that follows you!

final fantasy style rpg graphics showing anchor game programming technique

I want to write some code, anchor code. Very simple code, but I'm going to talk about it anyway. What I'm after is having something follow the character. Not in a complicated way, rather at a fixed distance and always behind the character. One might remember early games where you might have flying dragon behind you or an egg that grew up as you fought monsters. It could also be used for a light spell, 10 game units behind the player there could be an orb of glowing light as I've attempted to show in the picture (the sprite is from Final Fantasy, the grass tile I took from Tsugumo's Pixel Art Tutorial). That kind of thing.

Currently I've lost touch with my code. I'm attempting to rectify this but instead of blundering in, I'm going to prototype my function in a C# windows program. I like to do this as it keeps my windows knowledge fresh and always reminds how DirectX is setup and what's useful bits and pieces DirectX has. I find on a big program I totally forget a lot of the basic stuff.

So for the program I want a DirectX enabled area, when I click on it with the mouse then a small dot will appear. Then I click again and another small dot appears. But also a third dot appears - the anchor dot on the same line as the first two dots and behind the current position of the player.

I had no problem getting my small windows program running but I had problems with the maths - hate it so it so much! So I asked on GameDev and got a very quick very correct answer.

I'll give a brief overview of the code in case anyones interested, I was always interesting in how to get DirectX and windows to play nicely together. First let's look at the globals, I'm only going to have three points so I should make an array for them.


private const int maxVerts = 3;
Device device = null;
VertexBuffer vB = null;

CustomVertex.TransformedColored[] verts =
new CustomVertex.TransformedColored[maxVerts];
int numIndex = 0;


So a device, vertex buffer and vert array. These will allow me points to be stored and then rendered. I'm only going to have three points, the first two human entered the third computer generated. The cryptically entitled variable "numIndex" is the vertex index number, the current vertex we want to write. So once we click one we written the first - therefore increase numIndex by one, another click increment it again, then the computer does it's stuff and increments it. One last click and it reverts as does everything else.

Let's look at some of the code. I created a panel and hooked directX up to it. Easy enough. Then in the form designer I double clicked on the panel. This generated a click on panel event and VS.net wrote all the hook up code and deposited me in the OnClickPanel function, ready to write. This is what I wrote:


private void panel1_MouseDown(object sender,
System.Windows.Forms.MouseEventArgs e)
{
if(numIndex == maxVerts)
{
verts = new CustomVertex.TransformedColored[maxVerts];
numIndex = 0;
return;
}


verts[numIndex].Position = new Vector4(e.X,e.Y, 0,1);
numIndex++;

if(numIndex == maxVerts-1)
{
verts[numIndex].Position =
CalculateTail2(verts[1].Position, verts[0].Position, 10f);

verts[numIndex].Color = Color.White.ToArgb();
numIndex++;
}


OnVertexBufferCreate(vB, null);
}


System.Windows.Forms.MouseEventArgs e this things pretty cool it will tell you all about the mouse which buttons are down the position (which is what I used here) and mouse wheel stuff.

So for the first and second vertices we add a white vertex at the position of the mouse. Then if it's the second click (numIndex == maxVerts-1) the computer calls CalculateTail2 and puts a vertex down at it's return position. The third argument is the distance behind the point that it will place the third point. If it's the third click (numIndex == maxVerts) then the vertex buffer is reset as is the click count, click count now that would have been a good varaible name, oh well too late now.

Let's look at the magic function the computer uses to work out where to place the third. I'm awful at maths, this game from the gamedev message boards some one answered my plea for help.

It find the vector running between those two points and extends it by D to get the third point . . . well I guess this is what it does anyway :D


private Vector4 CalculateTail2(Vector4 currentPos, Vector4 lastPos, float distance)
{
//If they're the same do nothing
if(currentPos.X == lastPos.X
&& currentPos.Y == lastPos.Y)
return currentPos;

Vector4 p3 = lastPos - currentPos;
p3.Normalize();
p3 = currentPos + p3 * distance;
return p3;
}


Finally I'll render the points. Here's the process function that's called every frame.


private void Process()
{
device.Clear(ClearFlags.Target, System.Drawing.Color.Brown,
1.0f, 0);
device.BeginScene();
device.SetStreamSource(0, vB, 0);
device.VertexFormat = CustomVertex.TransformedColored.Format;

device.DrawPrimitives(PrimitiveType.PointList, 0, numIndex);
device.EndScene();
device.Present();
}


To prevent us having problems rendering we only render what we've assigned in the buffer.

final product isn't it pretty


And there we go a little mini-program demonstrating the technique, of course the main thing is the function, which I didn't write :D But oh well. The white dot is the computer one, the black dot nearest the white dot is the second click dot.

Other News

I'm ripping out my camera class and fiddling with it so it will be more useful and less clumsy. That's todays job. Also in the latest DirectX under DXUT there's suppose to be lots of GUI helper files - to help programmers make a quick GUI but I have no idea, at the moment, how to access these, or even if their avaliable through C#. I hope they are I much prefer having some one do all the hard work for me.

I decided I need to go through my code piece by piece and reconstruct it into a new project. When I tried to sub-divide it into namespace before - it's painfully obvious I failed. The current architecture I'm now implementing seems to go against the suggested grain, a big fat singleton that everything's connected to. There are some words on the different types of singleton here in C#.

But everything needs time! Eveything need texture management! Maybe everything needs to know the GameState! Player Account kinda needs to be known by everything!

That's what's happening anyway I think it should be okay. There's nothing more that needs to be in the singleton everything else is handled at a lower level. It will take some time to pull everything across but at least it will reaquaint me with my code. Also as I do this I convert it all to the latest SDK and improve any oversights so it's not a bad thing.

Maybe some day soon I'll even have some kind of game - that would be novel!

Thursday, April 28, 2005

Latest SDK means more updates gah!

So I've installed the latest SDK now and it's kind of fixed my problem. I still believe that C++ has a better interface to the CALCRECT stuff.

API Rant That Probably Won't Mean Much If You Haven't Been Playing With The Same Areas Of The API Recently. Yes Lots Of Captial Letters!

With C++ you pass in a reference to a rectangle. According to the docs on my system the API call will take into account the width of this rectangle (or height) and then tell you what sort of shape your big lump of text will be. Where as in C# you give it the text and it tells you the dimensions of the text as it's formatted. So if you've written a really long sentence - it gives you the width of that really long sentence you cannot (as far as I can tell) tell it measure the text dimensions if the width is constrained :(

Also the syntax has changed in places - so I need to go through the first few tutorials again and update the source code :D I think this teaches me an important lesson about downloading the latest SDKs before updating tutorials!

Some very nice code

Don't you hate it when you have an awful feeling. The feeling you are coding something that has probably been done already by the API but you just can't find it! Especially when you write code that's as inefficent as mine. Still I'm rather proud of it as I programming defensively from the start and once it compiled it worked! First time yay!

  /// <summary>
/// Removes a substring measured in pixels from
/// a string that will that will be rendered in a
/// given font.
/// </summary>
/// <param name="s">The string that will be reduced.
/// It's width in pixels in font f must be greater than
/// the Width parameter!</param>
/// <param name="f">The Font that the text will be rendered in</param>
/// <param name="Width">The width's-worth to be removed</param>
/// <param name="splitWords">Should the program splits lines in the middles of words?</param>
/// <returns>A string reprenting a widths worths removal</returns>
private string CutWidthFromString(ref string s, dxFont f,
float Width, bool splitWords)
{
#region Pre Conditions
#if DEBUG
Debug.Assert(Width > 0f,
"The Width to subtrack must be greater than 0!");
Debug.Assert(f != null, "The font object must not be null!");
Debug.Assert(s.Length > 0,
"The length of the string s must be greater than 0!");
Debug.Assert(Width <
f.MeasureString(null, s,
DrawTextFormat.WordBreak,
0).Width,
"The pixel-width to subtract must be less than the pixel-width of the string");
int DEBUG_startLength = s.Length;
#endif
#endregion

//Take off a widths worth of substring
//!Super inefficent way!
string substring = "";
float substringWidth = 0f;
int stringIndex = 1;

while(Width > substringWidth)
{
substring = s.Substring(0,stringIndex);

//I'm guessing this call is expensive.
substringWidth =
f.MeasureString(null, substring,
DrawTextFormat.WordBreak,
0).Width;
stringIndex++;

#region Debug
#if DEBUG
Debug.Assert(stringIndex <= DEBUG_startLength,
"Substring is attempting to read from outside the parent string");
#endif
#endregion
}

//Substring is actually bigger now so knock one character off
substring = substring.Remove(substring.Length-1, 1);


if(!splitWords)
{
int splitPoint = substring.LastIndexOfAny(
new char[3] {' ', '\n', '\t'});

if(!(splitPoint== -1))
substring = substring.Substring(0,splitPoint);
}

s = s.Remove(0, substring.Length);

#region Post Conditions
#if DEBUG
Debug.Assert(s.Length < DEBUG_startLength,
"Parent String was not reduced in size!");
Debug.Assert(f.MeasureString(null, substring,
DrawTextFormat.WordBreak, 0).Width
< Width);
#endif
#endregion

return substring;
}

A word or two about the above function

So for super-fast-release mode we take out the asserts (which shouldn't be a problem as they don't actually do anything but halt the program). Very handy for writing correct code. Also VS.net has those cool #region region ... #endregion blocks that can hide away all the debug code.

Also I was looking through some directX code and I saw that param code stuff. (Which, of course, has all been eaten by html argghhh!). Fix soon!


Well it's not just eyecandy VS.net will pick if up and when you make a call to that function, as you write it, you'll be prompted with the argument descriptions that you've written! I'm sure this is old hat to a lot of people but I only just found out, it's quite spiffy.

So I continue work on Game GUI and Grammar stuff.

Tuesday, April 26, 2005

Source Control with VS.net and CalculateRect Problems

I really need source control. I want to be able to start some new and crazy feature in my code with out any risk of breaking it. Source control allows me to do this. I don't have source safe and from what I hear it's not really worth learning too much about. It's not suppose to be very good. (Though I hear this is possibly set to change with a new edition but who knows!)

So my requirements are free and very easy to use.

This article on Source Control using CVS with VS.net seems to be the perfect answer.

A word of warning when you go to download igloo and you want the installer it's here. The link on the actual igloo page is incorrect.

That actually wasn't my only problem installing this. Before I could get it to work properly I had to take the contents of the beta zip and stick them inside my install directory for igloo.

Anyway it all works now - apart from I've no idea how to use it! I don't know how to revert or branch or anything. I'll have to hunt down some docs.

In other more hair pulling and gnashing of teeth news. There appear to be no way to make use the to the DrawTextFormat.CalculateRect. I'm downloading the latest SDK now in the hope that this is fixed. (I hope its a peaceful install). Other wise I'll have to try and work it out manually (T_T). Or I'll have to go into unmanaged mode and see if I can do this in C++ - it's only a guess that I might be able to do that, not a fact.

Oh well.

On the upside I did write a bit of code that retrieves the LUA error number from the error message. So instead of crashing the Grammatron it now just reports the line number. Still highlighting, line numbering and auto-complete seem very far away. I've been looking for opensource projects to fill the gap but they've tended to be sprawling octopi of programs rather than a nice encapsulated text box. I'll continue looking.

Sunday, April 24, 2005

The Wonderful World Of Grammars Part II: A Lua Grammar Parser

This article follows on from my previous introduction into the wonderful world of grammars. In this section we'll be mainly writing in Lua code, only using C# to polish our Lua / Grammar editor. By the end we'll have muddled through and have something that parses a very basic grammar. This can then be extended upon allowing us to investigate a range of different grammars.

Let us begin

Now we wish to write some LUA code to parse our grammar and then later do a run through it and present the output (this will be covered in part 3). We'll start with small steps and work our way up. It's also handy at this point to have some idea of what our grammar will look like and how it will be formatted. I imagine rules will basically fall like this:

[non-terminal] -> [mix] of [non-terminals] [and] terminals

There's a problem with this formatting though - how do we recognise where one rule ends and another rule begins? We could have each rule on a new line. This is pretty elegant but what if your rule is quite complicated and you'd like to space it out? Then the one line rule might get in the users way.

The best way would be to have the computer handle it. As you write - it labels the rules. A small sidebar marks the start of every rule with a number 1..n. This still leaves the problem of how to seperate the rules by computer though.

A simple way, the way I'm going to use is to have all rules of the format:

([non-terminal]) -> ([mix] of [non-terminals] [and] terminals)

That way it's easier to know when a rule ends. As I said we're starting simple, we can refine later. The first thing we're going to do is have the entire Grammar read into a lua variable. Then lua will read out the rules in a numbered manner. If you know nothing about LUA programming, this is a really good time to learn. Though, it's quite possible that you can pick it up on the way. Okay - let's do our simple task.

Detecting A Rule

Usually we'd have Grammar to define our Grammar and the work off this. This grammar would say things like "non-terminals are enclosed in [,]'s, terminals aren't" but I'd rather wing it as I'm lazy and it shouldn't be that complicated. Let's have a look at some pseudo code for reading a rule.

ReadARule

First non-space character should be '('
If it's not report Then an error and a line number

Eat(
ReadANonTerminal
Eat)

ReadAnArrow

Eat(
ReadASetofNonTerminalsAndTerminals
Eat)


So yes this might be familiar because yes we're kinda writing a parser for a language. But our language is very simple and specialized so not to worry. They key is to be very strict and be quite willing to throw out error messages left, right and center. Of course this makes it very easy to be the programmer perhaps slightly harder to be the user. We could have the computer intercept these errors and then show the user exactly where his error seems to be on the form. Maybe some time in the distant future.

Enough babling though let's see if we can't turn the above into Lua code. We don't have to exactly follow the suggested functions in the pseudo but it does seem to provide some clarity. Here's some code to start us on our path:

--CFG Version 0.01

--Globals
noOfRules = 0; --the number of the rule we're currently parsing


--Functions
function ReadARule(rules)

Output(noOfRules .. ": " .. rules);
noOfRules = noOfRules + 1;
end

--Main Code


ReadARule(GRAMMAR);

From this you can probably pick up on a few things. "--" indicate comments much like "//" in C#, C and various other languages. The function doesn't use braces, instead it has the keyword end. And Lua is dynamically typed so we don't have to explicitly say what our variables are actually going to be.

What does the code do? Well it reads the entire grammar and then put's the number 0 in front of it and outputs it. So we've solved the problem for the one-rule grammar - yay us! ".." is string concatination. We'll read through the grammar and extra rules. Each time we extract a rule we'll number it. Then we'll output all this information. Eventually we're going to be filling in a data structure with these rules so we have to seperate them into their constiuent parts. With the above code we're well on our way.

Polishing Small Flaws

Writing this though has brought one or two potential problems to light. One, which I know about, is that writing in Lua, if you make a mistake then the entire program will crash. We'll deal with this but not now. Another problem is that Ouput erases the entire contents of the output box - I think this is more of a feature and while it can be changed doesn't need to be. Especially now we know how to use the "..". The last one is when we press the GO button - it doesn't save the LUA content to disk. So if it crashes we lose our changes. This is a bit unforgivable so we'll rectify it now.

It's simple enough - so to the GO button function and before anything is done call the Save Lua File button pressing handler. The code goes like so:

private void buttonGo_Click(object sender, System.EventArgs e)
{
//Save Lua file
menuItem3_Click(sender, e);
lua["GRAMMAR"] = textBoxGrammar.Text;
lua.DoString(this.textBoxLua.Text);
}
An improvement on this would be to disable the GO button until there is both some LUA code and some Grammar stuff too. Let's do that then. First we'll add some code to the editing the Lua box. Like so:


private void textBoxLua_TextChanged(object sender, System.EventArgs e)
{
if(textBoxLua.Text != "")
buttonGo.Enabled = true;
else
buttonGo.Enabled = false;



Then to make everything work well we should also add some enable / disable code when loading a LUA file.

public void ReadLuaFile(string fileName)
{
if(fileName.EndsWith(".gin"))
{
try
{
textBoxLua.Clear();
IFormatter formatter = new BinaryFormatter();
Stream stream = new FileStream(fileName, FileMode.Open, FileAccess.Read, FileShare.Read);
textBoxLua.Text = (string) formatter.Deserialize(stream);
stream.Close();

}
catch (Exception e)
{
// Let the user know what went wrong.
MessageBox.Show(this, "The file could not be read.",e.Message);
}
}
else // save as plain text
{
//the user might want to call it .txt or .lua or whatever
//no restrictions will be placed on the extension but only plain
//text will be written.

using (StreamReader sr = new StreamReader(fileName))
{
textBoxLua.Text = sr.ReadToEnd();
}
}

if(textBoxLua.Text != "")
buttonGo.Enabled = true;
else
buttonGo.Enabled = false;

}


Select buttonGo in the form designer, go to properties and set enabled to false. That should cover all our bases. There's one last thing that's worth polishing - stay in the form designer and select the Grammar textBox. Set AcceptsTabs to true. Go the luaTextBox and do the same. This means when we press tab we'll move along a tab in the text box. Instead of moving to another control on the form. This will help when we're formating our code.

Back To Writing Our Parser

To break up our rules we need to do some pretty intensive string processing. Therefore we'll want to use LUAs string library. This is something we have to say we're going to use in our C# code. So here we go:

public Form1()
{

InitializeComponent();

//Do Lua stuff
lua.OpenStringLib();
lua.RegisterFunction("Output" , this, this.GetType().GetMethod("luaWriteToOutput" ));


That was easy wasn't it? :D

Writing A Parser

Isn't really a beginner topic but whatcha gonna do? Ours is pretty simple and we have lua's groovy string functions to help us. In fact if I was feeling really clever, which I'm not, I'm a sure a program could be written that would strip out our rules - really simply. The only thing that worries me is the error states. What if it's given a malformed grammar can it report where it had the problem? I can't think of an easy way to do this so I'm going to handle it the old fashioned way (kind of, I'm new to lua and don't know much about it's gubbins)

First thing we want to do is check that's there a leading bracket. This is the only possible thing we can have because we can't actually make a run on an empty grammar! So if it's not there then we'll report an error. If it is there then we'll remove it, thus preventing us from detecting it again. Our first program then should be able to perform the following:

Image Hosted by ImageShack.us

It kills off that first bracket. So we need a function that will do this and handle any possible error.

Read A Bracket Function

We're going to add three globals. Two are for error reporting. The third is the current state of the grammar we reading. As we read the grammar we're going to remove the bits we've read. For now we're storing this in a seperate global. Let's have a look at these globals then:

--Globals
noOfRules = 0;

readingGrammar = GRAMMAR;

error = false;
errorString = "no error";


That's not too bad. We're going to have code, that if an error is detected, then the error message is displayed to the Output window. You'll see how this works shortly. Let's look at the function that will eat a '('. It demands that the next non-space character is a '('. If this is not the case it returns an error. If it is the case then it updates the readingGrammar so that the paranthesis has been eaten. Here it is in code form:

function EatOBracket(s)
_, bracketstart = string.find(s, "%(");

--Error Checking
if(bracketstart == nil) then
error = true;
errorString = "Expected to find an opening (";
return "Error"
end

--Check all characters before this are empty
--If not then error

prefix = string.sub(s,1,bracketstart-1);
if(string.find(prefix,"%S+")) then
error = true;
errorString = "Expected ( got: " .. prefix;
return;
end

--Remove all read characters
readingGrammar = string.sub(s, bracketstart+1);

end
If you're as new to Lua programming as I am, this may take some explaining. I've called it EatOBracket for eating an opening bracket. Let's take this apart piece by piece.

_, bracketstart = string.find(s, "%(");

On the assigment side are two variables "_" and "bracketstart". "_" is a throw away variable I don't care what goes in there. This is a standard lua naming convention. string.find looks through the string and returns the first instance of (. It then returns the start position and the end position. As it's only one character long we only need to record one of these values. I chose to record the end position in a a variable I confusingly called bracketstart. That's all straight forward the thing that may seem a little out of place is the "%" mark. This is because ( is a special character and to say we don't want to make use of it's special use, rather we just want to search for it, then we must prefix it with an escape character - namely %. Mystery solved.


--Error Checking
if(bracketstart == nil) then
error = true;
errorString = "Expected to find an opening (";
return "Error"
end


If ( can't be found then it returns nil (think null) for both the start and end value. We check if nil has been returned and if it has then we have an error to deal with. So we set up our Global error variables and return the string; "Error". If nil hasn't been returned then we know where the first '(' is, so let's assume that's the case and get on with the code.

prefix = string.sub(s,1,bracketstart-1);
if(string.find(prefix,"%S+")) then
error = true;
errorString = "Expected ( got: " .. prefix;
return;
end
This code says "Does the next ( appear cleanly in the code or is there something before it?". For instance the following would be an error.

([Dog]) -> ("Frodo") "Spot"
([Cat]) -> ("Cuddles")

But unless we added the above code we wouldn't have been able to pick up on it. So lets check out that last piece of error checking code.

We assign prefix to be the sub string of all characters preceeding the (. The next line says if there are any non-space characters present then .... "%S+" means non-space characters.


%s means space characers
%S means the complement of s. (that is all non-space characters)
+ means one or more repetitions.

So we're asking can we find any non-space characters, if the answer is "No, we can't" then we can proceed. If we can find other characters then we inform the user of the error. Provided we get past both these error tests then we can remove the '('.


--Remove all read characters
readingGrammar = string.sub(s, bracketstart+1);

This says that everything starting after the ( character we to the end we cut out and assign to reading grammar. If you don't put a third argument here it defaults to -1 which is the last character of a string. (All this useful information is avaliable in Chapter 20 of Programming in Lua.)

Now we're ready to test this out. Though to do this we need a little bit more framework. Last time we had an early ReadARule function so let's modify that a bit.

function ReadARule(rules)

--Eat The First Bracket
if(EatOBracket(rules) == "Error") then return end;

Output(noOfRules .. ": " .. readingGrammar);
noOfRules = noOfRules + 1;
end

Notice the rather crude error testing we've added in :D This will serve. Next we have our "main" function.


--Main Code


ReadARule(GRAMMAR);

if(error == true) then
Output(errorString)
end


We attempt to read one rule. If during the course of our reading an error flag is raised then we output that error (output clears the text box before writing so we'll only ever see the error). Now you can play about with different grammar inputs and make sure only the correct code is accepted. The output window will display an error message or it will display the string you entered with the first ( removed.

Reading a non terminal

We expect a non-terminal to be enclosed in square braces. Within the square braches can be anything apart from a closing square brace. You'd actually think we'd be able to share code with previous bracket detection thing - I'd tried this and struggled to get it to work. Passing in %[ just didn't seem to want to go, maybe I'm missing something obvious. I didn't bother for too long before I soldiered on!

We want the meaty goodness of the non-terminal. But where do we store this meaty goodness? Well with LUA this isn't a very hard choice it having the only one major data structure. A TABLE! (notice how this all links back to the first tutorial - it's not planning, it's magic). Our table isn't too hard to set up. Another global and away we go.

--Globals
ruleTable = {};

At this point you might be thinking, Dan, this seems to be sloppy coding whats with all the globals. Luas a prototypingy, scriptingy language and I'm experimenting not laying this code down forever. That's why! It can be done of course in lua, it's tables are really objects! :o Suprise! But this isn't something I'm going to get into here as I wouldn't know what I'm talking about (even moreso than usual).

Anyway CODE!

function ReadNonTerminal(s)
--must begin and end with [,]'s

_, bracketstart = string.find(s, "%[");

--Error Checking
if(bracketstart == nil) then
error = true;
errorString = "Expected to find an opening [";
return "Error"
end

_, bracketend = string.find(s, "%]");

--Error Checking
if(bracketend == nil) then
error = true;
errorString = "Expected to find an closing ]";
return "Error"
end

--more error checking nothing occurs before the non-terminal

prefix = string.sub(s,1,bracketstart-1);
if(string.find(prefix,"%S+")) then
error = true;
errorString = "Expected [ got: " .. prefix;
return "Error";
end

--remove this section from the global grammar, yet add to the
--current rule.
ruleTable[1] = string.sub(s, bracketstart, bracketend);
readingGrammar = string.sub(s, bracketend+1);


end

So we find a starting [ and check that one exists, then we find the ending ] and check that exists too. Once we're satisfied of their existance we check nothing comes before the non-terminal that shouldn't, errant characters or numbers, that kind of thing. If we're still okay then we add the non-terminal as the start of the rule. We're merely storing the rules as strings for now. Then we cut off what we've read. Wonderbar.

Let's see the modifications to the main code that will give us some feedback on what we've done.

function ReadARule(rules)

--Eat The First Bracket
if(EatOBracket(rules) == "Error") then return end;

if(ReadNonTerminal(readingGrammar) == "Error") then return end;

Output(noOfRules .. ": " .. ruleTable[1] ..
"\n| What's left: ".. readingGrammar);
noOfRules = noOfRules + 1;
end

It reads out what we've currently got of the rule and what's left of the grammar. For some reason the newline does not register with the text box. I'm willing to leave this as an enduring mystery for now. Everything is looking pretty spiffy I'm quite happy. Once again feel free to experiment.

Polishing

Once again a few annoyances have crept in, oh for some kind of line-number tool. I've tried to make one but I failed. I feel the sneaking supiscion that a RichText box would solve all my woes. But not yet! Lua crashing the window is still a pain but I need to read some documentation to solve that! So psstf save that for later. The main ease of use improvement I can think of right now is making sure the code is saved if we shut down. So let's do that!

Image Hosted by ImageShack.us

Hook up a nice closing event. We want to do things before the form closes - and this is were we'll do them!


private void Form1_Closing(object sender, System.ComponentModel.CancelEventArgs e)
{
if(textBoxGrammar.Text.Length != 0)
buttonSaveGrammar_Click(this, null);

if(textBoxLua.Text.Length != 0)
menuItem3_Click(this,null);
}


If we close with out saving we prompt for save or autosave. Because I'm messing about with the grammar so much at the moment I'm going to comment the first one out. It makes editing that much easier.

Read The Closing Brace

Now we wish to read the closing brace. Maybe here we can do some code sharing.

Let's generalize the bracket reading function:

function EatBracket(s, bType)
_, bracketstart = string.find(s, bType);

--Error Checking
if(bracketstart == nil) then
error = true;
errorString = "Expected to find: "
.. string.sub(bType, 2); --remove the %
return "Error";
end

--Check all characters before this are empty
--If not then error

prefix = string.sub(s,1,bracketstart-1);
if(string.find(prefix,"%S+")) then
error = true;
errorString = "Expected " .. string.sub(bType, 2)
.. " got: " .. prefix;
return "Error";
end

--Remove all read characters
readingGrammar = string.sub(s, bracketstart+1);

end

First let's get the above working for the opening bracket again - shouldn't be too hard. All we have to do is pass in the extra argument of %(

if(EatBracket(readingGrammar, "%(") == "Error") then return end;

No problems. Now let's add a closing brace. Should be easy as pie.

if(EatBracket(readingGrammar, "%(") == "Error") then return end;

if(ReadNonTerminal(readingGrammar) == "Error") then
return
end;

if(EatBracket(readingGrammar, "%)") == "Error") then return end;

That works very nicely. Feel free to experiment. Next we have to eat the arrow this should also be pretty easy to code.

Reading An Arrow

This should be relatively simple. All we do is match "->". A lot of the code is also similar to before so we're going to add it all in one big chunk.

function EatArrow(s)
--eat the arrow -> and remove it from the code

arrowtail, arrowhead = string.find(readingGrammar, "->");

--Check we can find it
if(arrowhead == nil) then
error = true;
errorString = "Expecting to find arrow ->." ..
"Instead have the following " ..readingGrammar;
return "Error";
end

--Check there are no errant characters behind it
prefix = string.sub(s,1,arrowtail-1);
if(string.find(prefix,"%S+")) then
error = true;
errorString = "Expected -> got: " .. prefix;
return "Error";
end

--Add Arrow to rule string
ruleTable[1] =
ruleTable[1] .. string.sub(s, arrowtail, arrowhead);
readingGrammar = string.sub(s, arrowhead+1);

end --END OF ARROW EATER

So we search for the "->" arrow and we record it's start and it's end. If it's not there then we return an error. If there's any non-space characters before the arrow we also return an error. If everything is fine then we add arrow to the rule string and remove the arrow from the grammar we're reading. Easy!

Let's add it to the ReadARuleFunction

function ReadARule(rules)

--Eat The First Bracket
if(EatBracket(readingGrammar, "%(") == "Error") then return end;

if(ReadNonTerminal(readingGrammar) == "Error") then
return
end;

if(EatBracket(readingGrammar, "%)") == "Error") then return end;


if(EatArrow(readingGrammar) == "Error") then
return
end;


Simple!

After this an opening bracket

Now another opening bracket, it is the easiest thing in the world. We just add another line to our ReadARule function.

if(EatBracket(readingGrammar, "%(") == "Error") then return end;

if(ReadNonTerminal(readingGrammar) == "Error") then
return
end;

if(EatBracket(readingGrammar, "%)") == "Error") then return end;


if(EatArrow(readingGrammar) == "Error") then
return
end;

if(EatBracket(readingGrammar, "%(") == "Error") then return end;

Reading a terminal or a non-terminal

Now this is a bit tricky. we have to look adhead and check what we'll be reading - a terminal or a non-terminal or a end bracket and then deal with it.

Let's think this through with some psuedo code. Of course the C way would be reading character by character but I don't know how to do that easily in Lua this is the first thing I've ever programmed in it! And if I may reiterate once again - it's not speed we're after.

can we detect an [ if
YES: IS THE PREFIX CLEAR
YES: READ A NON-TERMINAL
NO: can we detect a "
YES: IS THE PREFIX CLEAR
NO: can we detect a (
...

Messy. I can think of maybe a better way.


While (detect) is false and error is false)
{
if( detect[ is false
and detect" is false)
error = true;
errorString = "Expected ')' got " .. readingGrammar;
end;
}


If detect is a success it auto reads and eats the terminal or non-terminal. We'll create a main function called EatRuleBody. This needs three detect functions. We also need to write a eat function for a non-terminal, by the by, I decided a non-terminal would be put in quotes "".

First let's read an empty rule.

([nothing]) -> ()

This shouldn't be too hard. But until we finish the code we run the problem of a possible infinite loop. We'd rather avoid this if at all possible.

function EatRuleBody(s)

result = DetectCloseBrace(s);
while(result == "False" and not error) do
result = DetectCloseBrace(readingGrammar);
end

if(result == error) then return "Error" end

end --END OF EAT RULE BODY

With the above code if we have

([nothing]) -> ("nothing")


We'll enter an infinite loop and the program will crash - so don't do that! We can however report a correct error from:
([nothing]) -> (

Here we expect the closing brace but can't find it. With the EatRuleBody code our error messages may not be in the same order as the errors present in the code. Not to worry though. Let's write our detect function which might be more aptly named -"detect and if possible eat".

function DetectCloseBrace(s)

_, bracketstart = string.find(s, "%)");

--Error Checking
if(bracketstart == nil) then
error = true;
errorString = "Expected to find ) instead got: "
.. s;
return "Error";
end

--Check all characters before this are empty
--If then return false

prefix = string.sub(s,1,bracketstart-1);
if(string.find(prefix,"%S+")) then
return "False";
end

--if it's the last character then eat the brace
if(EatBracket(readingGrammar, "%)") == "Error") then return "False" end;

return "True"; --success don't really have to return this

end

It's very similar to the eat code. But finding characters in the prefix doesn't mean an error this time, instead it means that there's earlier stuff to read.

Detecting Non-Terminals

This is also pretty easy but we want to add the non-terminal to the rule in our ruleTable. The current non-terminal function replaces the entire rule with the non-terminal - as before we had just assumed this was alpha bit of the production rule. Therefore let's make a little edit to the non-terminal code. Before we begin a rule we initiate the rule string to the empty string. This is am important thing to do in a dynamically typed language.

function ReadARule(rules)

ruleTable[1] = "";

Then instead of replacing the entire rule with the discovered non-terminal we instead concatinate the non-terminal to the current rule we already have.

function ReadNonTerminal(s)
--must begin and end with [,]'s

_, bracketstart = string.find(s, "%[");

--Error Checking
if(bracketstart == nil) then
error = true;
errorString = "Expected to find an opening [";
return "Error"
end

_, bracketend = string.find(s, "%]");

--Error Checking
if(bracketend == nil) then
error = true;
errorString = "Expected to find an closing ]";
return "Error"
end

--more error checking nothing occurs before the non-terminal

prefix = string.sub(s,1,bracketstart-1);
if(string.find(prefix,"%S+")) then
error = true;
errorString = "Expected [ got: " .. prefix;
return "Error";
end


--remove this section from the global grammar, yet add to --the current rule.
ruleTable[1] =
ruleTable[1] .. string.sub(s, bracketstart, bracketend);

readingGrammar = string.sub(s, bracketend+1);

end --END OF NT EATER
After adding this we remove our infinite loop problem. Let's flesh out the EatRuleBody function.

function EatRuleBody(s)

result = DetectCloseBrace(s);
while(result == "False" and not error) do

if(DetectNonTerminal(readingGrammar) == "False") then
error = true;
errorString = "Expected end brace ) got "
.. readingGrammar;
return;
end;


result = DetectCloseBrace(readingGrammar);
end

if(result == error) then return "Error" end

end --END OF EAT RULE BODY

If we can't detect an end-brace and we can't detect a non-terminal then there's an error - we should at the least expect an end-brace so that's what we tell the user. If a non-terminal is detected it's eaten.

The following errors are detected and a suitable error message is generated.

([d]) -> ([g]
([d]) -> ((
([d]) -> (error)
([d]) -> ([tt)

It works pretty well now. Once we add support for non-terminals then we've pretty much got a fully functional parser. (If you ever want to write a programming language - winging it, like this, probably isn't the way to do it. Look into Backus Naur Form, Bison, Yacc and Lex).

Terminal Detector and Eater

Well this is going to be pretty much exactly the same as the non-terminal stuff but using "'s. Easy! Just copy paste with some minor modification. Actually there's a few hiccups with using the same symobol '"' for start and end. We must cut off the first one before searching for the second. Also we must use the correct character codes.

function DetectTerminal(s)
_, bracketstart = string.find(s, "\"");

--We don't have to have a terminal
if(bracketstart == nil) then
return "False";
else
prefix = string.sub(s,1,bracketstart-1);
if(string.find(prefix,"%S+")) then
return "False";
end

if(ReadTerminal(readingGrammar) == "Error") then
return "False";
end;

return "True";
end

end --END DECTECT TERMINAL


It's pretty much the same as earlier. If we detect a ' " ' and there's nothing before it - well then read in a terminal. Otherwise return False. Now let's look at the ReadTerminal statement.


function ReadTerminal(s)
--must begin and end with "'s

_, bracketstart = string.find(s, "\"");

--Error Checking
if(bracketstart == nil) then
error = true;
errorString = "Expected to find an opening \"";
return "Error"
end


--more error checking nothing occurs before the terminal

prefix = string.sub(s,1,bracketstart-1);
if(string.find(prefix,"%S+")) then
error = true;
errorString = "Expected \" got: " .. prefix;
return;
end

s2 = string.sub(s, bracketstart+1);

_, bracketend = string.find(s2, "\"");

--Error Checking
if(bracketend == nil) then
error = true;
errorString = "Expected to find an closing \"";
return "Error"
end

--remove this section from the global grammar, yet add to --the current rule. plus one cos we cut off the start
ruleTable[1] =
ruleTable[1] .. string.sub(s, bracketstart, bracketend+1);
readingGrammar = string.sub(s2, bracketend+1);

end --END OF TERMINAL EATER
We have to find two "'s then we have to make sure there's nothing before the first ". Then we need to cut out what's between the "'s including the "'s. It's that easy ... kinda. I think the code is reasonably followable. Once this has been written then we can update EatRuleBody. It's a simple add on that will allow our code to accept pretty much any rule body - even the empty one.

function EatRuleBody(s)

result = DetectCloseBrace(s);
while(result == "False" and not error) do

if(DetectNonTerminal(readingGrammar) == "False"
and DetectTerminal(readingGrammar) == "False") then
error = true;
errorString = "Expected end brace ) got "
.. readingGrammar;
return "Error";
end;


result = DetectCloseBrace(readingGrammar);
end

if(result == error) then return "Error" end

end --END OF EAT RULE BODY

Once we make some simple changes to ReadARule we're practically done. So let's make those changes now.

function ReadARule(rules)

ruleTable[1] = "";

--Eat The First Bracket
if(EatBracket(readingGrammar, "%(") == "Error") then return end;

if(ReadNonTerminal(readingGrammar) == "Error") then
return
end;

if(EatBracket(readingGrammar, "%)") == "Error") then return end;


if(EatArrow(readingGrammar) == "Error") then
return
end;

if(EatBracket(readingGrammar, "%(") == "Error") then return end;

if(EatRuleBody(readingGrammar) == "Error") then return end;

ruleTable[noOfRules] = noOfRules .. ": " .. ruleTable[noOfRules] ..
"\n| What's left: ".. readingGrammar;
noOfRules = noOfRules + 1;
end --END EAT A RULE
So that's a simple addition. More of a problem is that at various places in the code we've used the magic number 1, as in the first rule. What should have been there is the noOfRules variable. This means all the functions are working with the current rule, rather than just rule number 1. If you look at the start of ReadARule there's an example of this.

function ReadARule(rules)

ruleTable[1] = "";

Must be changed to read:

function ReadARule(rules)

ruleTable[noOfRules] = "";

Talking of which we should change the global too so it's starts from 1, which is standard in Lua. So let's do that now:

noOfRules = 1; --index in Lua tends to be from 1

Now checking through the code for more '1' offenders. There's one at the end of the non-terminal rule eater:

--remove this section from the global grammar, yet add to   --the current rule.
ruleTable[noOfRules] =
ruleTable[noOfRules] .. string.sub(s, bracketstart, bracketend);
readingGrammar = string.sub(s, bracketend+1);

end --END OF NT EATER

And at the end of the terminal eater! An epidemic.

--remove this section from the global grammar, yet add to --the current rule. plus one cos we cut off the start
ruleTable[noOfRules] =
ruleTable[noOfRules] .. string.sub(s, bracketstart, bracketend+1);
readingGrammar = string.sub(s2, bracketend+1);

end --END OF TERMINAL EATER

And at the end of the arrow eater - I'm not showing the code, as I'm positive you have the idea :D. You should confirm everything works by running the parser on a test grammar.

There are other problems with arrow eater too. It doesn't have proper error checking - oh no! Before that though we need to setup our read a rule so it returns errors correctly. I know Lua does exceptions but I haven't read about them yet, so this is the way I'm doing it. I might go to exceptions in a future revision.


function ReadARule(rules)

ruleTable[noOfRules] = "";

--Eat The First Bracket
if(EatBracket(readingGrammar, "%(") == "Error") then
return "Error";
end;

if(ReadNonTerminal(readingGrammar) == "Error") then
return "Error";
end;

if(EatBracket(readingGrammar, "%)") == "Error") then
return "Error";
end;

if(EatArrow(readingGrammar) == "Error") then
return "Error";
end;

if(EatBracket(readingGrammar, "%(") == "Error") then
return "Error";
end;

if(EatRuleBody(readingGrammar) == "Error") then
return "Error";
end;

ruleTable[noOfRules] = noOfRules .. ": " ..
ruleTable[noOfRules] ..
"\n| What's left: "..
readingGrammar;
noOfRules = noOfRules + 1;
end --END EAT A RULE

This should help things go a little smoother when we're attempting to detect errors over the entire grammar. Well I've messed about with the code now and I've got the read out working. The formatting is unpleasent but nothing something i'm going to worry over.
function ReadAllRules(s)

while( string.find(readingGrammar,"%S+") ) do

if(ReadARule(readingGrammar) == "Error") then
error = true;
return "Error";
end;

end

This reads all the rules. It says "keeping reading rules until there's only empty space stuff left". It also handles any errors perfectly (though error messages supplied at this point may be a little off!). So this records all the rules in our table. Subarashi!

Next up is to write out the contents of our table. For some reason this took me a while though it's very straight forward.

function OutputResults()

all = "";
stop = noOfRules-1;

for i = 1, stop do
all = all .. ruleTable[i];
end

return all;

end

It's noOfRules minus one because we always increment the value everytime a rule is parsed. So when parsing rule ten we up the amount to 11 because that's the next rule we'll be looking at. So that's the minus one, everything else is pretty normal. Let's look at the main code.

ReadAllRules(GRAMMAR);


if(error == true) then
Output(errorString)
else
Output(OutputResults());
end


And that seems to work pretty well. Of course, as I said, the formatting is quite nasty but at least it's doing what we want :D.

That'll do it. For the parser that's pretty much all there is to it! Yes some of the error reporting is wonky and so is the output but hey it's definitely working! It's something that can be refined and used.

Download icon.[Grammar Parser in GIN format]
Download icon.[Grammaratron Program with slight polishing]

Freshening Up The Tutorials Again

I've just been through the second tutorial that deals with creating a tile based game, getting tiles to the screen, making grass and stone tiles from textures and that sort of thing. Once again a few mistakes have been fixed and complicated sentences have been broken down into simpler ones. I also have added source code. It should be much better to follow now. (I've also removing comments dealing with the older version so they wouldn't be confusing! They're only hidden not deleted :D All the issues they addressed have hopefully been resolved.)

I also spent a little time with the first tutorial again improving the formatting and add two more source code snippets. I will undoubtly in the fullness of time work my way through the rest of them.

Cleaning The Blog's Appearance

Obviously the template for this blog has been horribly broken hopefully that's now somewhat resolved. I would happily write my own, but I like to use lots of tools and I could imagine it would be a chore on my portable. So I've grabbed another pre-made template and attempted to maximize the screen real-estate of my main posts. (as my big images tend to kill frames, or divisions.

The basic grammar parser is pretty much finished. I've been having some thoughts about terminals and non-terminals. Terminals could be functions so I could have something like:


[wall] -> "StartDrawingWall()" [walltiles] "FinishDrawingWall()"
[walltiles] -> "DrawATile" "MoveToNewSelectedTile" [walltiles]
[walltiles] -> "DrawATile"


The only worry with this, is that I'm overcomplicating things. But this way I could have the computer know which tiles make up a wall and therefore base other decisions off it. The real thing I want to do is have a grammar that given some area of tiled space - will create a building in it. I'm pretty sure it's not hard just to make a box building but I'd like the buildings each to have idiosyncrasies (acloves, ruins rooms, enterance ways, patios etc (this wouldn't be hard to put into the grammar)). Saying that I don't want the grammar reliant on too much of my C# code.

The one possible avenue of attack for this is to have the alpha part (first part of the rule) of the production describe areas larger than one tile.

[grasstile] [grasstile] [grasstile] [grasstile] [wall_tile] [grasstile]
[grasstile] [grasstile] [grasstile] -> [grasstile] [wall_tile] [grasstile]
[grasstile] [grasstile] [grasstile] [grasstile] [wall_tile] [grasstile]


This would really benefit from a more graphical interface. It's also even now for me hard to predict what would happen. I think an endless loop? Of course you'd have a cut off point. The other thing that is important though is when building a room or a house - the computer must know it's a room or a house. That way the grammar can add chairs and people and everything necessary.

Maybe I should just start simple for now it's not an easy problem. The wonderful thing about grammars is that it's very easy to add diversity by only adding a few more rules.

Wednesday, April 20, 2005

Minor News

Today I did a quite a bit of work on a small Lua parser for a context free grammar. It's looking pretty good. I also updated the previous article on grammars with a few more step by step pictures.

I want to get some time to begin correcting and make the tutorials easier too. Tommorrow though I have a meeting I have to go to :( so I probably won't be able to do too much. Still I'm quite happy with how everything is progressing. I have few ideas for small seperate application programs that I will then patch into my game.

Sunday, April 17, 2005

The Wonderful World of Grammars: Randomly Generated Content for Roleplaying Games using Grammars

Image Hosted by ImageShack.us

Do you know what I think are really cool? Grammars.

I like the idea of randomly generated content. I like it a lot. I also like Grammars because they're pretty simple. Your programming language of choice was defined using a grammar. There are many different types of Grammars and many have scary looking definitions with lots of nasty set theory stuff. Let's not get bogged down in that, rather let's look how a Grammar might be useful for a computer game, especially a role playing game.

To sum up: Grammars are cool.

They've been used to model the growth of molds and cities, even music and cool stuff like that. You could use them to write nonsense books, make up words, zen koans etc.

Issues

The problem is grammars are to some extent limited. You CANNOT translate one (human) language into another using a grammar. CANNOT. Language is too fluid grammars are far too stiff. Also the very nature of language means there may be extra detail contained in a sentence that cannot be filled in by a language that does not record that detail. But I'm getting off track. The important question is - are grammars too limited to do really groovy stuff with games?

With that question in mind let's set out to discover the wonderful world of grammars. Now, I wanted to be able to try out a few different grammar definitions, to see what was what in the world of grammars. This isn't the kind of thing I can program in the middle of my already cluttered computer game! Instead it's the perfect thing for a small seperate application. It will be cool and shiny and allow us to experiment with any kind of grammar we wish. Does it sound groovy? It is!

Formal Grammar Definitions

Did the word formal make you cringe. I'll look through the most basic grammar definition explainng what it's actually saying in plain English. Hopefully this will fire you're imagination a bit.

Let's look at a Context Free Grammar. Context-free means it the context of something doesn't matter for the rules to go ahead. That's sounds a little confusing so let's clear things up with an example.

Imagine infront of you is a white table.

Image Hosted by ImageShack.us

Now on this table are some smarties.

Image Hosted by ImageShack.us

The smarties are arranged in two rows. The first row of smarties, about five smarties long, are all blue.

Image Hosted by ImageShack.us

The second row of smarties also about five smarties long are all red - apart from the third smarty he's blue - and looks very out of place, maybe he feels a bit initimated too.

Image Hosted by ImageShack.us

Now imagine a non-context free grammar. That means context could come into play! So let's suppose we have a non-context free grammar rule - if could say if there's a blue smarty surrounded by two reds then change it to a green smarty.

Image Hosted by ImageShack.us
That's what context is. In a context-free grammar it would be hard to put this type of rule in. But to define context free grammars are simpler. What we'll do next is look at the formal definition of context free grammar.

Formal Definition Of A Context Free Grammar

A context free grammar is a four tuple (a pair can be thought to be a two-tuple) defined:

(V, E, S, P)

V is a finite alphabet of non-terminal symbols.
E is a finite alphabet of terminal symbols.
V intersect E = the empty set
S is an element of V
P is a set of ordered pairs {alpha, beta} called production rules
That's the main part of the definition. Writing the mathmatical notation is a little tricky. I'm might try and find something a little more elegant. Let's look at the formal definition for a production rule and then we'll go through and explain it in English.

alpha and beta are elements of (V union E)* and alpha contains at least one symbol from V
You would be surprised how straight forward this all is if you know the lingo. We don't really need to know if for the game though, maybe you'll be able to pick some of it up from the following explanation.

Let's explain this line by line.

1. V is a finite alphabet of non-terminal symbols.

V is a set. Set are like boxes that are INSIDE your head - obviously not physically. They can be infinite (the set of all numbers 1,2,3, ... there's no end that's means it's infinite - yeah?) or finite the set of fingers of my left hand (five - isn't strange that we always include the thumb in the set of fingers but would never other wise call it a finger). So we had a finite set this means we can count the elements. It can still be very very very large but not infinite.

It's an alphabet of symbols. I guess alphabet means the symbols are all different and have some meaning. Let's say our V is the following.

V = {[a man's name], [the number of people in a city], [a series of arm movements], [the position of a space station]}


Looking at that you might notice something ... they're all descriptions rather than actual data. Interesting no? Well this is to do with non-terminal. For instance a finished sentence might.

Roger Redhat likes Jenifer Yellowhat.

This is a fine sentence each word here can be thought to be terminal. The grammar can be thought to have finished. Non-terminals are what the grammar uses as it approaches being finished for instance the above sentence may have gone through the following stages. (I'm using [,]'s to mark non-terminals).

[sentence]
[personage] likes [thing]
[young boy] likes [personage]
Roger Redhat likes [young girl]
Roger Redhat likes Jenifer Yellowhat
I hope you can see how that might have worked. Non-terminals means the grammar shouldn't terminate yet.

2. E is a finite alphabet of terminal symbols.

The actual symbol here isn't a E it should be an epsilon (I think that's the right word). Looks awfully similar to the previous rule and it is - exception being that this is the set of terminals - that means rules that declare an end. They cannot be modified anymore.

E = {Peter, 7 million, ((0,0,0),(17.4,12,8.8),(45.2,6,8.9)), (X:2.111, Y:45.7A Z:99.3)}

And that kind of thing. Generally you don't fill these sets with random crap like I have instead you craft them lovingly so they'll be able to create cool things. You want cool things don't you?

3. V intersect E = the empty set

This means anything that's a non-terminal can't also be a terminal because it just wouldn't work. And anything that's a terminal can't also be a non-terminal. Pretty common sensical :)

4. S is an element of V

S here stands for the start symbol. It has to be a member of V - the non-terminals or there's no point have a grammar as it would already be finished. Examples of start symbols might be:

[A made up book]
[A interesting world]
[A dungeon]
[A galaxy]
[A space ship weapon]
[An arch-nemisis]

Then from this we keep going applying rules until we have a big group of non-terminals and whatever we wanted to make has been made.

P is a set of ordered pairs {alpha,beta} called production rules. Alpha and beta are elements of (V union E)* and alpha contains at least one symbol from V

The first thing the gets my attention is that (V union E)*. It's a bit odd. What it means is any possible combination of terminals and non-terminals. These are the rules basically saying "If you see this stuff" then "make it look like this stuff". It's basically the production rules. Applying a production rules is often called a derivation. Let's have a look at an example of some rules.

[CATS] -> [CAT] [CATS]
[CATS] -> [CAT]
[CAT] -> "Pete the Cat"
[CAT] -> "Jim the Cat"
[CAT] -> "Growly the Cat"
[CAT] -> "Ginger the Cat"
[CAT] -> "Tooth the Cat"
[CAT] -> "Furball the Cat"

Well these rules could produce many derivations if we assume S, the start symbol, is [CATS]. The final result could be "Jim the Cat", "Jim the Cat Jim the Cat" or "Furbal l the Cat, Growly the Cat, Pete the Cat" any possible combination of cats.

Looking closely at that last rule it seems a bit off. It seems we could get round the non-context rule. So we'll just self impose that :D On to the code now.

The Program: Grammatatron.

That's not actually my projects name but you may wish to consider it. It does sound pretty cool. Let's give the basic run down of what I want in this project.

A window displaying the output.

For now this is text only output (we're not going to have graphical interactive worlds). The non-terminals will be strings of text. This is just for ease of use and simplicity at the moment. They could also be instructions, functions, rules, images anything you could imagine sticking at the end of your grammar.

Example output might be:

"You are on the contient of Zaabaa. It's famous exports are bannanas, mangoes, and wool. Currently you're in a cave."


And hopefully we'll be able to do things a little more fancy that that. A lot of it is up to how you write your grammar rules. The whole point of this is allow us to experiment in this fashion and see how much rich, luscious detail we can create.

A Text Box to Write The Grammar In

Here we'll have all our grammar rules. We'll also want easy saving and loading functions. Possibly we could add some highlighting. Maybe even auto-complete of known non-terminals. Pretty fancy pretty swish. Of course that means we'd have to have set definitions of what a non-terminal looked like. A restriction that's probably worth imposing.

A big red GO! Button

Note, finally button may not be big, or red. This button would say "given these grammar rules" go generate us a gramar or tell us where the grammar has gone wrong.

A LUA Grammar Interpreter

Yeah, this ones a bit of a surprise huh? We're going to have another text box. This one is going to take LUA code. When run LUA is going to read our grammar the follow our grammar. We can edit the way it does this on the go - impressive heh? This would also benefit from highlighting and a nice debugger to. The intructions are going to pretty simple so we could potentially write the code in a more fully fledged GUI.

The best thing about this is we could have a number of LuA files each representing a slightly different grammar. This allows us to experiment.

Creating the Program

Boot up Visual Studio. We're programming in C# as it's the best programming language in the world :D Then start a new project and select a windows form project.

Image Hosted by ImageShack.us

Now we have a nice new empty project. Well apart from the form crap that's in there but not to worry about that for now.

In the toolbox grab the tabControl. Drag this over into your form. Now in the tabControl go to properties. Go to Dock and choose fill. In my version of the IDE when I click on Dock it brings up a small gui with five buttons, click the central most one, that's fill. The tab control should not have expanded to fill the entire form.

Image Hosted by ImageShack.us

Grabbing a Tab Control.

Image Hosted by ImageShack.us


Go back to properties and this time choose TabPages. There will be a button with three dots when you click on it. Press the button with three dots. Add two tab pages, this can be done by clicking the Add button twice. Now go the tab pages properties and give both tabs a name. I named the first Grammar Editor and the second LUA Interpreter. After doing this, close that window.

Image Hosted by ImageShack.us

Press that blue add tab hotlink twice.

Image Hosted by ImageShack.us

Change the tab names!

In the form designer you'll now see two tabs! And you can click on them both. Each gives a different tab page which you can fill with handy controls. Let's start with the second tabPage the one I named "LUA Interpreter".

LUA Interpreter

We're going to keep this pretty simple. Add a TextBox from the control panel. Go to Dock choose fill again. Then set MultiLine to true, now it will fill the entire window. This is where our LUA code is going to go. We may want to change the font later too, as the current one sucks.

Image Hosted by ImageShack.us

Grammar Editor

This tab will be slightly more complicated. I threw on two text boxes each taking up roughly half the form. The one of top we're going to use a output. Therefore we don't want our user typing in it. (Even if the user is only ourselves it looks prettier this way). So we set ReadOnly to true. I also renamed it so it was called textBoxOutput. I don't usually rename stuff when I'm using the form wizard but then I usually create very small programs.

The other box I called textBoxGrammar and I set it's multiline to true too. We don't set the readonly flag because this is where we'll be typing in our grammar. Over each box, I added a nice little label too so they're easily identifiable.


The next thing to work on is loading and saving for the Grammar. We want to save our grammars, the ones that are particularly nice we can cherish and leave as a legacy in our wills and so forth. Therefore I added two buttons and dropped them quite near the grammar window.

Image Hosted by ImageShack.us

One button would be used to save, called buttonSaveGrammar the other used to load called buttonLoadGrammar. Then to make load and saving more user friendly I went back to the tool box and drop a loadFileDialog and a saveFileDialog onto my form. These appear at the bottom of the designer and we don't really have to touch them for now. Though I renamed them so "loadGrammarDialog" and "saveGrammarDialog".

We've done enough as we can in pleasent form designer now we actually have to write some code!

Load and Saving Grammars

We want stress free loading and saving of these grammars. I also wanted to make it fairly idiot proof as I often save over stuff.

Let's do saving first. We're going to save in our propiertary format :D Only because this is even simplier than saving it as a text file. First we need to add some using statements at the top of the code file.


using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;

I love serialization it's great. If you ever can use, use it. With a computer game though you should be careful with it, make sure you're not saving lots of redundant stuff. Here we're using it very simply. In the form designer double click on the save button. This will hook up and event and take you it.

private void buttonSaveGrammar_Click(object sender, System.EventArgs e)
{
}

Save in the most general case is going to save to the last saved position. If there is no last save postion then we give the user a save dialog and ask her where he'd like to save. We check the last save position by looking at where the openGrammar dialog last opened a file from.

If it hasn't opened a file yet, then we can assume this is a new grammar being written and we prompt the user to save it where she or he would like. We're going to have a look at the code now so get ready!

if(openGrammarDialog.FileName == "")
{
//Didn't load a file, instead wrote
//from scratch
if(saveGrammarDialog.ShowDialog() == DialogResult.OK)
{
WriteGrammar(saveGrammarDialog.FileName);
}

Saved = true;
GrammarEdited = false;
}
else
{
WriteGrammar(openGrammarDialog.FileName);
}


Seem's pretty straight forward. The first line that may cause worries is:

if(saveGrammarDialog.ShowDialog() == DialogResult.OK


This is saying, load the SaveGrammarDialog - so the user is presented with a window where they can choose to save their file. If they have second thoughts and cancel then the if-statement fails and the function is returns. If on the other hand the user says "ok save here" then the saveGrammarDialog records the filename to save to. We then pass the filename along to our SaveGrammar function, that we haven't written yet.

Dialog Results is an enumeration of all the common dialog buttons, so Yes, No, OK, CANCEL etc. When the dialog closes it returns the button it was closed with. Was it closed by the user pressing OK or was it closed by the user pressing cancel?

The next bit that might be confusing is


grammarSaved = true;
grammarEdited = false;

Don't worry about them for now. Just define some globals and carry on.


bool grammarEdited = false;
bool grammarSaved = false;

That's pretty much the pressing the save button function. The actually writing is squirrelled away and now is the time to unsquirrel it. This function is so simple and groovy we're going to look at it all in one go:


private void WriteGrammar(string fileName)
{
IFormatter formatter = new BinaryFormatter();
Stream stream = new FileStream(fileName, FileMode.OpenOrCreate, FileAccess.Write, FileShare.None);
formatter.Serialize(stream, textBoxGrammar.Text);
stream.Close();

textBoxOutput.Text += "\nFile Saved " + fileName;
}

First line says we're going to be writing out binary (rather than say XML which we could do if we took a fancy to it). Next we create the file stream using the file name. If it's present on the hard drive we'll open it and write to it, if it's not there then we'll create it. We're only going to be writing. FileShare doesn't concern us. Then we use the formatter to seralize our text. It handles all the writing to a file for us. After this close the stream and report a succesful save. Couldn't be simpler!

Now to loading!

We can set up a "pressed-the-load-button-event" by going to the form designer and double clicking on the load button.

private void buttonLoadGrammar_Click(object sender, System.EventArgs e)
{
}


We'll get something like the above.

Now in here we're going to add a bit of code. The first code we're adding is going to be checking for possible mistakes by the user. If we're potentially overwriting something the user might wish to keep we're going to warn him.

How do we know what the user might want to keep?

*Has she saved it?
*Has he edited it since it was loaded?
*Is there anything to save?

So if what's-currently-in-the-grammar-window is not nothing and has been edited and hasn't been saved then we should prompt the user. So how do we do this? We'll be making use of the two bools we introduced in the Saving a file section.

bool grammarEdited = false;
bool grammarSaved = false;

GrammarEdited means "Have we just edited what's in the window?". And saved means "Have we just saved what's in the window?". Pretty straight forward, no? Checking if the Grammar Text Box is empty is a simple comparison of the text. Here's the conditional:


if(!(textBoxGrammar.Text.Length == 0) &&amp;amp;amp;
grammarEdited &&
!grammarSaved)
{

If we pass that if-statement then we warn the user. Now if it's the case that we're potentially losing important data, we're going to ask if the user's sure. There's lots of built in stuff that makes this really easy. We're going to build a YesNo box, and ask "Are you sure you want to save?", if the user says yes we save. If he says no we cancel. Here's the code:


if(!(textBoxGrammar.Text.Length == 0) &&amp;amp;amp;
grammarEdited &&
!grammarSaved)
{
//Should have a message box asking
//if want to overwrite stuff in box
//if it's not saved
if(MessageBox.Show ("Load without saving?", "Really?",
MessageBoxButtons.YesNo, MessageBoxIcon.Asterisk)
==
DialogResult.No)
return;
}


If the user say's "No, don't load without saving my data first" then we drop him back to the window to save (just do a void return from this statement). If he says "Yes" load without saving then we carry on.

So let's assume he carries on. We do a piece of code very similar to the save dialog but this time we're using load:


if(openGrammarDialog.ShowDialog() == DialogResult.OK)
{
ReadGrammar(openGrammarDialog.FileName);
}

grammarEdited = false; //we couldn't haven't edited the data
}

Once again though we have a function that requires unsquirreling. It too is beautifully simple.

private void ReadGrammar(string fileName)
{
try
{
textBoxGrammar.Clear();
IFormatter formatter = new BinaryFormatter();
Stream stream = new FileStream(fileName, FileMode.Open, FileAccess.Read, FileShare.Read);
textBoxGrammar.Text = (string) formatter.Deserialize(stream);
stream.Close();

}
catch (Exception e)
{
// Let the user know what went wrong.
MessageBox.Show(this, "The file could not be read.",e.Message);
}

}

I put try and catch statements here too! So we can now load and save but there's still a little thing missing. How do we know when the textBoxGrammar has been edited? Well there's a nice delegate for this that we can hook an event up to.

The easiest way to do this is to go to the form designer. Select textBoxGrammar. Then go over to the properties and select the lightening bolt icon. Scroll down to TextChanged then double click in the blank box next to it and this will hook and event up there for us.

private void textBoxGrammar_TextChanged(object sender, System.EventArgs e)
{
}


You should get some thing like the above. In here we're going to play with our bools. (HAHAHA! I'm a comedy genious)


//If we edit the text then we changed the grammar
//we record this in a bool so we can do a save prompt in necessary
private void textBoxGrammar_TextChanged(object sender, System.EventArgs e)
{
grammarEdited = true;
grammarSaved = false; //We've no longer have saved
//what's in the box
}


This is getting pretty fancy now so let's put a last shine of polish on it. Go back to the form designer and select the "openGrammarDialog" go to it properties (we're back to properties now, not events). I've decided Grammar files will be called .grm's.

So we'll set DefaultExt to "grm". Then we scroll down to Filter here we input "Grammar Files | *.grm". This means when opening files tell the user we're opening grammars files and look only for files with the extension .grm. Now goto the saveGrammarDialog and chose it's properties and make the same changes to the same fields.

That's pretty fool proof loading and saving. Feel free to load and save some files and marvel at how it doesn't break (hopefully) :D.

The GO! Button

Everybody needs a big red go button. Though as I said it's not going to be big or red rather it will be small and gray. Simply grab a button from the tool box and drop it on to your form.

Upon pressing the GO! button we're going to have LUA run grammar and then execute a run on it. Every time we press the go button LUA will reread the grammar and do a new run upon it. Not terribly efficent but it's not like this program is mission critical. Before going any farther I think you should read the LUA tutorial.

Okay now set up LUA so it's referenced and the .dlls are all in the right places. If you can't remember how check out the LUA tutorial.


First let's add the using statement.

using LuaInterface;

Right now let's add a nice LUA global.

Lua lua = new Lua();

Everything else takes place within the GO! buttons OnPressedEvent. So go back to the form designer and double click on the button to automatically hook up this event for you. Here it is all with some code added.

private void buttonGo_Click(object sender, System.EventArgs e)
{
lua["GRAMMAR"] = textBoxGrammar.Text;
lua.DoString(this.textBoxLua.Text);
}

We're saying make the GRAMMAR variable in lua store all our grammar text. Then run our grammar processing code. Pretty sweet. We're almost ready to go! All that's left to do is have LUA output something to our program. To do this we'll need to write an output function. I'm going to preface the functions I'm sending to lua with the string "lua". Currently I'm undecided how much preprocessing the Grammar Text will go through before we pass it on to Lua to deal with - for now it's going to be none. Let's look at the output function we intend to hook up to Lua.

public void luaWriteToOutput(string output)
{
textBoxOutput.Text = output;
}


Simple. Now we just want to have Lua be able to use it. This is no big problem and we'll take care of it in the forms constructor.


public Form1()
{
InitializeComponent();

//Do Lua stuff
lua.RegisterFunction("Output" , this, this.GetType().GetMethod("luaWriteToOutput"));
}

Before we test this. Let's make coding a little easier on the eyes and change the default font in the code windows - both the grammar one and the lua one. Select the text box go to font and choose a nice font. I chose Lucida Sans Console. Wild speculation here but I believe the word console means it was specially designed for the computer screen and columns will line up much better. So that's the one I chose and set for both text boxes (the grammar one and the lua one) - now on to the test.

Boot up your trusty GRAMMARATRON program. Select the second tab and type:


Output("Crazy Horses! Waaaaaaaaaaaaaaaaah");

Sit back and admire the font for a bit. Now go back to the first tab and press "THE BIG RED GO BUTTON THAT IS NEITHER BIG NOR RED". And you should see some text go to the output window. Isn't that great!

I think this is going to be a two parter. So to close this part we're going to add a main-menu for loading and saving of our LUA files. Then in the next part we'll build our first fully functional LUa grammar parser / generator - won't that be fun! Then we'll all be free to experiment with grammars and hopefully our games will grow more diverse because of it!

For instance imagine book that generates each page as you read it, the generation function based off the page numbers as well as other facts about the book - no of pages, colour, binding etc all of which were also randomly generated. Everything becomes generated from everything else. This is how, in part, games like elite worked.


Adding a menu and loading saving for our lua files

So on the first tab we've gone with buttons, which while possibly a bit non-standard at least they're in esay reach. The second tab though we'll be doing programming I don't really want to take up anymore space. Therefore we'll add a menu bar with a file menu and to options "load lua file, save lua file" we can also add more stuff a we go.

This is all pretty easy and can be done in the form designer. We take the mouse on over to the tool box and choose MainMenu. Then we draw the main menu so it's at the top of our form.


Image Hosted by ImageShack.us


This produces a little white box with the caption "type here". This is where we can add our information. It's quite common to have the first menu item be File then Edit then ... and finally Help. It's very good to stick to standards like these it makes that program instantly useable by anyone who comes along. But I'm going to break with tradition - I'm going to have my first menu as Lua. For now the only menu item but it's easy to imagine adding one that would say grammar.

Clicking on the "type here" text allows you to type out your menu. I typed in "Lua" then under that menu I added Save Lua File and Load Lua File. I want to put in the same idiot proofing as before that will stop me saving over work or losing things that could be avoided!


Image Hosted by ImageShack.us


As we're loading and saving let's add two more dialogs. An openFileDialog and a saveFileDialog. Let's call them openLuaDialog and closeLuaDialog instead. Now we can use these for easy loading and saving of Lua files. Great! Let's get to the code. Like before we want to program an event handler that will handle the event of "Load Lua File" being selected from the menu for instance. The easiest way to get to this is to double click the relevant menu choice.


//Load A Lua File
private void menuItem2_Click(object sender, System.EventArgs e)
{

}
Of course you can (and probably should) rename this in the properties window of the form designer. That way you won't be dealing with the rather ambigous "menuItem2_Click".

We don't want to jump straight into loading a file though. First we want two global variables that will help us idiot proof our editing. So let's add those.

private bool luaSaved = false; //has the Lua code just been saved?
private bool luaEdited = false; //has the Lua code just been edited?

Now we're a little bit more prepared. Let's write our load function. We can pretty much copy the start from the buttonLoadGrammar_Click function. All we need do is change some of the variable names.

I've given my text box on the second tab the name "textBoxLua". So the condition for warning the user that he might be losing data goes as follows:


if(!(textBoxLua.Text.Length == 0) &&amp;amp;amp;
luaEdited &&
!luaSaved)


and underneath this we can have the exact same code as in the Grammar loading function.


{
//Should have a message box asking
//if want to overwrite stuff in box
//if it's not saved
if(MessageBox.Show ("Load without saving?", "Really?",
MessageBoxButtons.YesNo, MessageBoxIcon.Asterisk)
==
DialogResult.No)
return;
}


the end of the function is also very similar.


if(openLuaDialog.ShowDialog() == DialogResult.OK)
{
ReadLuaFile(openLuaDialog.FileName);
}

luaEdited = false;
}

We need to create a temporary loading class to allow the code to compile.

public void ReadLuaFile(string fileName)
{
}


Before going any further let's fix up the luaEdited varaible so it's actually useful. In the form designer go to the second tab select the lua text box and go to the event properties. Should be symbolized by a lightening bolt and be above the properties window. Then double click the white box next the Text Changed event. That should produce the following:


private void textBoxLua_TextChanged(object sender, System.EventArgs e)
{

}


And inside we put the file


luaEdited = true;

Reading Serialized Lua Files

Plain text reading can come later for now we'll just do the serialized versions so we have something working. This code is very simple and based off the Grammar saving code.

I'll think we'll use the extension .gin for grammar interpreter files. We can use the extension to determine how we will go about storing the file - serialization or plain text.


public void ReadLuaFile(string fileName)
{
if(fileName.EndsWith(".gin"))
{
try
{
textBoxLua.Clear();
IFormatter formatter = new BinaryFormatter();
Stream stream = new FileStream(fileName, FileMode.Open,
FileAccess.Read, FileShare.Read);
textBoxLua.Text = (string) formatter.Deserialize(stream);
stream.Close();

}
catch (Exception e)
{
// Let the user know what went wrong.
MessageBox.Show(this, "The file could not be read.",e.Message);
}
}
else // save as plain text
{
//the user might want to call it .txt or .lua or whatever
//no restrictions will be placed on the extension but only plain
//text will be written.

/** We'll write this later **/
}
}


That's all pretty straight forward, we can finish up by fiddling with the properties of the openLuaDialog. We'll set the default extension to "gin". And in filters add the following string "Grammar Interpreters | *.gin|Text File|*.txt|Any File|*.*". This leaves it quite open for the user. Of course at the moment the only format supported is .gin, because it's the easiest to program. That's loading done - now to saving.

Saving Lua Grammar Interpreters

We can hook up a Save Lua event much in the same way we hooked up a Load Lua event. Just double click on the menu item and allow visual studio to do all the hard work for you! Which should get you to the following:


private void menuItem3_Click(object sender, System.EventArgs e)
{

}



Once again it maybe advisable to edit menuItems3 name so it's a little more clear "LoadLuaFile" for instance. The code is going to be very similar to the SaveGrammar function so we can copy, paste and edit. Quickly we'll produce the following function:


private void menuItem3_Click(object sender, System.EventArgs e)
{
if(openLuaDialog.FileName == "")
{
//Didn't load a file, instead wrote
//from scratch
if(saveLuaDialog.ShowDialog() == DialogResult.OK)
{
WriteLua(saveLuaDialog.FileName);
}

luaSaved = true;
luaEdited = false;
}
else
{
WriteLua(openLuaDialog.FileName);
}
}


Pretty simple of course we need a skeleton function to allow this to compile - easily done


private void WriteLua(string fileName)
{
}


We can fill the above in pretty easily as it's like a minorly extended version of the saveGrammar function.


private void WriteLua(string fileName)
{
if(fileName.EndsWith(".gin"))
{
IFormatter formatter = new BinaryFormatter();
Stream stream = new FileStream(fileName, FileMode.OpenOrCreate, FileAccess.Write, FileShare.None);
formatter.Serialize(stream, textBoxLua.Text);
stream.Close();
}
else //Save as plain text
{
/** Code needs to be written **/
}

textBoxOutput.Text += "\nFile Saved " + fileName;
}


Finally a bit of polishing. We go back to the form editor and goto the properties of saveLuaDialog. Here we make the same changes as we did to openLuaDialog, namely we change the default extension to ".gin" and add the following line to filers: "Grammar Interpreters | *.gin|Text File|*.txt|Any File|*.*".

To test this write a simple text program. Such as "output("hello world");" then save this lua file, close the program, run the program, open the saved file and run it. In the output box it should say "Hello World".

Plain text loading and saving is left as an excerise for the reader, as is the command Lua>Save As ... which might be useful. You may also wish to add "New Lua file" and maybe a Grammar section and File section to the the Menu Bar. (I've added a file option to mine, it has a "File> Save All". To add keyboard-shortcuts you add the character '&' before one of the letters in your Menu Item's Name, this will then be the shortcut-key for it. For instance I use 'Alt-F then S' all the time for saving. I've mimicked that here with "&Save All" under the file menu. So I press Alt-F this gets me into the file menu, pressing S runs the Save All event handler.

In the next part we'll be interpreting the Grammar. To get you started you may wish to try something like this in lua interpreter:


Output(GRAMMAR);

Now everything you type into the Grammar box will be faithfully reproduced in the output window - mess around with this and have fun.

Download icon.[Grammatron Code Version 1]