Saturday, February 25, 2006

Grinding

I'm currently thinking about and poking a city placement algorithm. It's strongly based on games such as Master of Magic and Civilization.

I want "player" cities to be as far apart as possible. Neutral cities I care less about. For the common cases it's quite easy but let's say there's only one continent well then I want to place the cities with maximum space between them. I have an idea it's just getting myself to implement it. Today I don't think I'll be doing any work anyway. Schools busy at the moment as it's the end of the school year in Japan soon - so less programming time.

Anyway books:

The Pragmatic Programmer


By: Andrew Hunt, David Thomas

This is an excellent book on programming in general. There's a bit of an object / procedural bias which is perfectly understandable given that's what languages in general use today. The book addresses what exactly is meant by terms such "modular" and "flexible" and how such properties can be achieved. There are plain, well explained examples showing how to keep code clean and clear.

They also recommend the use of emacs or vi for all editing. The arguments seems pretty solid, only one set of commands to learn, language agnostic, works even without a graphical interface but I don't agree. I've used vi (though I admit not emacs) and I think the problem is they're text based and they're text editors. I want something that edits a programming language, currently the best editor has to be Visual Studio (or one of it's clones). I like C# so I'm quite bias. It's a graphical system, when coding you can see the tree of your project over on the side so you have an overall idea of the architecture.

Debugging



Debugging is built in. If the programs crashing, then with a click you can put in halt points marked in red. So when execution hits this point - it's paused and the code is displayed on your screen. By waving the mouse over the variables on the screen you are informed of their current values. If the variables are classes you can open them up and look at all the inner values without problem. And that's anywhere on the screen. As I said, I'm not familiar with emacs but vim doesn't have this type of debugging facility, infact I can't imagine that it could be achieved so intuitively in a text only program.

Not only that but you can change the code during execution. That's a benefit of the IDE being strongly coupled to the language.

If your code fails to compile, an error message appears, clicking on the error takes you to the exact place in the code where the problem is occuring.

Intellisense



This is avaliable in emacs and vim but not natively - you'd have to fiddle around with scripts or write one yourself (and it's never going to be as good if I> make it because I'll be tempted to leave out rarely used parts of the language). The VS IDE uses reflection to pick up the details of the classes you're using, then it creates a text box that guesses what you might be typing. If you press tab, it auto-completes the word (you can bring this up at any time with Control-Space). In a text-based system you cannot have that floating text box, you also cannot have pictures that represent what each option represents - a class, private or protected variable etc.

In-built Refactoring Tools



These two are great, I love the rename one alone. I know VI can be programmed to do such things but I don't want to spend time programming my programming tool - I just want to use it. Also such programming would be an extreme undertaking. Selecting areas of code and having them changed into a method automatically, by using Extract Method, is a godsend. Though the one I use most is probably rename - it's changes a ill-thought out name in a snap and it changes it throughout your program.

The future is a graphical IDE. (check out there flash movies)

Well, that turned into quite the rant, but other than that point - I agree and I think the book is excellent and important. (Though the actual book binding kind of sucks.)

Twisty Little Passages, An Approach To Interactive Fiction


By: Nick Montfort

A book about the history of text games. It's stressed that the term interactive fiction is more appropiate and should be used, but I think "text game" is more commonly understood and that's why I use it here. It covers the history of text games starting from riddles to Adventure, the first text game, then through the brief commercial period and finally to the current period of indie-ness. The history is interesting, though I feel a bit too much time is given to Zork and dicussion or analysis of Zork, like it was some long-thought-out master piece. There's too much overanalysis in general for my tastes - I'm not saying one shouldn't examine interactive fiction, like you might examine literature, rather that this isn't the place. It all seems to much of plea for "serious literate types" (whoever they may be) to appreciate this art-form. An issue I doubt many readers feel strongly about. But that is the focus of this book.

Apart from that it's an interesting read. There's a lot about the more obscure text games, that are trying something new. There's also a brief dicussion about puzzles and what makes a puzzle good. I would have liked more about this but once again maybe this isn't the book.

The really interesting text games are those that do some modelling of NPCs using chatterbots. But these are only mentioned in passing and it's hard to ascern how succesful the implementors have been. As the whole text games / art debate, I see no reason why a text game couldn't equal the importance of a linear book, though I think the parser improving by a factor of ten or so might help. (Try Rameses (bottom of the page) if you want to try a game that's a bit different.)

Given what I know now, I probably wouldn't buy this book. There's too much of "this is why text games are actually art" and not enough of "these games are extremely innotative and interesting" or "these puzzles are interesting for the following reasons". It's a well written and well researched book, those interested in text games would probably enjoy it a lot.

Wednesday, February 22, 2006

Generating Random Rivers

Rivers are now in my world generation.
At first I was trying to do all the fancy "rivers move around according to terrain" stuff - but my terrain height isn't generated in a standard "Earth" manner so it didn't work out well.

The current algorithm for generating a river is:

Get a continent for each river (if we want more rivers than there are continents then -> tough :D)
Get the highest point of each continent (randomly choose if there's more than one)
For each river assign a random high point as the source. (so yes there could be more than one river per continent.)
Choose a heading. (east, south, north, west - for example)
Advance towards that heading going forwards or up, or down, until the sea is reached.


Forwards

- -> --

Up
-
- -> -

Down

- -> -
-



It works quite well. Now I'm cleaning the generator class up, as it is this massive fat thing. I'm using the strategy pattern to cut the generator methods out. That way I can make a factory and load the planet up with various generators. The planet will then be made by running the generators it has. (A tiny bit more complicated than that - as some generators require other ones to have been run first and so on)

So the class still needs cleaning and then I have city placement to figure out. I'll try and give each warlord an equal a starting position. But I'm not sure how close I'll get. I have a rough city placing heurisitic worked out but only a few lines of code so far.

Also I need to update the reading list. I've polished off Code Complete and Twisty Little Passages. Next update I'll write a little about what I thought of them.

Saturday, February 18, 2006

Generating Worlds

Here's my world generation as it stands, very rough and ready.

 public void Start()

        {

            IntializeMap();

            Seed(25); // Should be a tile percentage

            int growthAmount = 11;

 

            for (int i = 0 ; i < growthAmount; i++)

            {

                Grow();

            }

 

            CalculateAverageHeight();

 

            regions.landmasses = detector.DetectRegions(map, TerrainType.Plains);

 

            StratifyLandmasses();

 

            detector.DefineCoast(map);

            regions.coasts = detector.DetectRegions(map, TerrainType.Coast);

 

            detector.DefineHills(map, averagePlainHeight);

            regions.hills = detector.DetectRegions(map, TerrainType.Hill);

 

            detector.DefineMountains(map, averagePlainHeight);

            regions.mountains = detector.DetectRegions(map, TerrainType.Mountain);

 

            SeedForests();

            GrowTerrain(TerrainType.Forest, forestSeedChance);

            GrowTerrain(TerrainType.Forest, forestSeedChance);

 

            regions.forests = detector.DetectRegions(map, TerrainType.Forest);

 

            SeedSwamps(); // just a few.

            regions.swamps = detector.DetectRegions(map, TerrainType.Swamp);

 

            //

            // The poles.

            //

            Point northPole = new Point(width / 2, (height / 4));

            Point southPole = new Point(width / 2, ((height / 4) * 3));

 

            map[northPole.X, northPole.Y].Type = TerrainType.Ice;

            map[southPole.X, southPole.Y].Type = TerrainType.Ice;

 

        }



I need to add rivers and then markers for cities. Also I really wanted to refactor a lot of this using the strategy pattern but I'm not really sure it fits so I'm leaving it.

Potentially my worlds may have lots of features but not all features are necessarily shared between all worlds or generated by each world in the same way. Lava and meadows may not occur on the same world for instance. Forests generation may require knowledge of where rivers are.

Washu post over here looks interesting, I'm looking forward to see the answer.

Thursday, February 16, 2006

The results of the unfocused developer

Well this was suppose to be a bit of eye candy that I'd implement at the end of the project if I had time.






Also I've started using subversion for source control, not for my project but for some other bits and pieces. It's the first time I've ever had it's setup, where it's usable for a windows users.

Oh and the globe it spins of course and each time the program is loaded a different world is generated. All I can say is watch out Ysanyea.

I recently found a cool resource called code4u.

Sunday, February 12, 2006

This weekends goals

Redo map generation so that continents are given region data.

Yesterday I did nothing, even though I've had the entire day free. Today I've been busy doing various social stuff but I don't want to let the weekend end without progressing. So I'm going to try and get one more step done. I have two little japanese plastic coffee drinks to help me.

EDIT1: Gauss Map Generation
Pros: A lot faster than seed or grow


40 30 37 28 35 27 21 16 20 37
29 41 27 23 21 33 21 23 23 21
31 25 38 36 32 35 36 32 32 20
31 22 35 45 46 28 41 27 37 37
26 32 36 47 35 45 29 24 36 42
42 41 27 45 52 33 43 24 35 47
33 29 40 46 58 58 33 25 21 42
46 27 24 45 37 39 53 28 18 38
32 43 38 43 31 27 30 46 37 38
43 28 25 42 41 38 32 32 36 41


Current heights randomly generated, a tiny bit too uniform I feel so I'll tweak.
One plastic cup of coffee down. If the results are good this is the generation method I may go with.

EDIT2:





Fast but the quality sucks (not continenty enough, no nice sized islands) so before hand I'm going to seed it and see if I get better map quality.

EDIT3:




Added random seeding to the start. Continents aren't clean enough. Even with a cleaning function they're all going to be joined together.

EDIT4:
Back to the seed method





Much better islandy type things now.

EDIT5:
Continent dectection is in. The ftp's being unfriendly so no picture.
Puts me back to where I was before but with slightly cleaner code.
Beforep pushing this into the main build I'll be updating it to add different land types. There's actually a height number that's incremented now so it might be nice to see where the mountains have landed.
For tonight though I've finished.

A few days later, ftp seems fine, don't want to make a brand new post. Here's the missing shot.






Related previous posts one and two.

Wednesday, February 08, 2006

Snail Prints

Progress had stalled a bit, it seems a bit I thought was pretty much done needs quite a few extra bits and pieces.

I've very nearly finished polishing off the second of three components in my "empire-builder-majig". It takes in a grammar then uses that grammar to replace certain parts of text.



Behold it's glory :D

My third and final component should be finished up by the weekend. Then I should finally be able to squeeze regions into my RPG map.

Cryptic as usual I guess.

Saturday, February 04, 2006

Adaptive Binary Tree

Here's the node nice and simple if we wanted to generalize it instead of a string we could have an array of T.

    public class Node

    {

        public char Letter;

        public int Count;

        public Node Yes = null;

        public Node No = null;

 

        public Node(char c)

        {

            Letter = c;

            Count = 1;

        }

    }



Here's the tree. Everything should work fine.


public class AdaptiveBinaryTree

    {

        protected Node root = null;

 

        public override string ToString()

        {

            return root.ToString();

        }

 

        /// <summary>

        /// Recursively build and sort tree.

        /// </summary>

        /// <param name="s"></param>

        /// <param name="i"></param>

        /// <param name="n"></param>

        /// <returns></returns>

        protected Node InsertData(string s, int i, Node n)

        {

            if (s.Length == i)

                return n;                   

 

            if (n == null)

            {

                n = new Node(s[i]);

                i++;

                n.Yes = InsertData(s, i, n.Yes);

            }

            else if (n.Letter == s[i])

            {

                n.Count++;

                i++;

                n.Yes = InsertData(s, i, n.Yes);

 

                n.Yes = SwitchNodes(n.Yes, n); //Yes should checks it's no child

                n.No =  SwitchNodes(n.No, n); // no should check it's no child

            }

            else

            {

                n.No = InsertData(s, i, n.No);

            }

 

            return n;

        }

 

        // Node count has just been increased do we need to switch?

        private Node SwitchNodes(Node n, Node nParent)

        {

            //

            //  Have a or b

            //

            //  a.)    p           b.)    p

            //           \                /

            //            n               n

            //           /               /

            //        n.No            n.No

 

            if (n == null) return n;

            if (n.No == null) return n;

            if (n.Count >= n.No.Count) return n;

 

            return SwapWithNoChild(n, nParent);

        }

 

        public void Add(string s)

        {

            root = InsertData(s, 0, root/*, null*/);  

        }

 

        protected Node SwapWithNoChild(Node n, Node nParent)

        {

            if (n.No == null) return n;

 

            Node child = n.No;

 

            n.No = child.No;

 

            child.No = n;

 

            if(nParent == null)

                return n;

 

            if (nParent.Yes == n)

            {

                nParent.Yes = child;

            }

            else

            {

                nParent.No = child;

            }

 

            return child;

        }

 

    }

Friday, February 03, 2006

www.godpatterns.com

I've registered a name. I've been thinking about making the move to a more freeing web prescence for a while. I love blogger but it would be nice to be able to have non-blog data, articles, source code and the like.

So that's cool. I'm actually hoping to pay nothing at all, not directly anyway. Adsense produces a very small trickle of money and with a generous $4 that I stumped up I registered the domain for a while. (It seems most com names are quite quite gone, I would have quite liked EIN, I'd thought of clockworkworlds for a while and until just recently it was free, but that's too long. CWW was also registered, as I assume nearly every three letter domain is. funkmanor is still free, as is megagermany and forthegloryofprussia, but I wanted something I could potential sell or distribute games from in the distant hazy future.)

But I've not just been frittering away advertisement dollars - oh no - I've been tackling thorny issue and rasing my code-foo.

Basically I wanted (among other things) to implement the old tab-complete thing. You press tab and it checks what possible words you could be writting and finishes it. Also control-space in VS.net - one of the bestest shortcuts ever. I didn't want to do it by going through a list of words and attempting to match them - that's like exponential complexity, no I wanted a tree!

So let's say we have the commands PRINT and PAUSE, the tree would look like:



P
/ x R
/ A I
/ \ x U N
\ S T
\ E x


Then if we typed PR and pressed TAB it would finish PRINT, well that's all very nic but I wanted more. The tree should be dynamic! I should be able to add words on the fly, ( at this point there's no way to remove them) and not only add them on the fly but the tree should auto-balance itself so that the most common words are the one's accessed first! For instance if we have PRINT, PAUSE, PARTY then it the tree would start P -YES-> A not P -YES-> R, because there's more chance of it being A, assuming the commands are used equally (not something I really desire to get into). So yes weighting goes in there as well, weighting and auto-sorting.

Anyhoo I'll probably post the code tomorrow. It's basically just a binary tree with weighted nodes, or something like an Adaptive Hoffman Tree. It only deals in strings but if I made it generic then it could predict likely orders of anything . . . though I can't really thing of what these other things might be at the moment.

Also I'm a year older and it's the traditional end of winter in Japan. For these reasons this weekend may result in a slump in productivity.