roddy: (Default)
When I get depressed, I program. I recently found myself in a severe funk, so I started looking around for some interesting programming projects to do.

Enter Project Euler. (For the uninitiated or uninformed, that's pronounced "Oiler", not "Yew-ler.") Project Euler contains a series of over 300 mathematical and logical problems of various difficulties. The idea is, with all these programming languages available, a solution should be possible.

I decided, for the sake of being different, that I'd do my Project Euler problems in PLT Scheme.

  1. Add all the natural numbers below one thousand that are multiples of 3 or 5. (19 November 2010)

roddy: (Default)
This is the first in a series of posts about attempting Project Euler in PLT Scheme. The posting schedule is, for the most part, every Friday. For more information, see the introductory post.

The first problem on Project Euler is relatively simple:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.
Project Euler

See solution. )
roddy: (Default)
In previous articles, we developed a rudimentary dungeon generating program that would build a simple dungeon of rectangular rooms and straight hallways. Through the use of a random number generator, we were able to build rooms at randomly (or pseudo-randomly) chosen locations throughout the map. This random room placement ensured that no two dungeons would be alike, but it also ensured that we would, at times, generate dungeons where not all rooms and corridors were connected or accessible.

In practical terms, this is not necessarily a bad thing. Some games have traps that include trap doors that drop you into a pit of monsters (and treasure). Alternatively, a dungeon level might have multiple sets of stairs, each leading to a different part of the next level, or perhaps skipping the next level entirely. Throne rooms, prisons, panic rooms, treasure troves – there are numerous possibilities for an unconnected dungeon.

But what if we want a plain old fully-connected dungeon, where we can start at any point A and travel to any other point B?

This article discusses the concept of a connected dungeon, where every part of the dungeon is accessible from every other part. We will discuss the concepts behind connectivity, and develop an algorithm for connecting an unconnected dungeon. We will be extending the original dungeon generating class developed in previous articles.

Connected Dungeons )
roddy: (Default)
I received an email from a friend several days ago mentioning that he had seen my Dungeon generating code and wanted to extend the Dungeon class and add additional features. This had me looking back at my original code and realizing that, as it stands, Dungeon is not very extendible.

In this article, I will be modifying the class so as to allow for better extendability, and explaining the design decisions that I make in regards to why certain aspects of the Dungeon are private rather than protected.

I would expect that people reading this article will have at least a basic understanding of inheritance in Java, and would understand what I meant about the effect of certain variables being private or protected.
Extending the Dungeon )
roddy: (Default)
One of the most interesting aspects of the old "Roguelike" games are their dungeon building algorithms. Every time you descend into the depths of the dark cave or the gloomy catacombs, you're faced with a new, automatically generated setting. There are rooms of treasure, long corridors filled with traps, hidden rooms, and so forth.

Dungeon generation, I would hazard to say, is one of the most fascinating problems in computer science, not only because of how common it is in game development, but because of the sheer scope of the problem. It is, at its heart, a purely decision-based situation. Should this tile be a wall or a floor? Are all the rooms connected? No? How do I connect them? Where should I put the door? Where do I put the traps?

There are many different algorithms out there that focus on this problem. Some are rooted in cellular biology and artificial life that create some very cool looking cave-like structures with irregularly shaped rooms. Others produce honest-to-god mazes and labyrinths of winding corridors and few open spaces.

Today we are going to focus on a very simple dungeon generation program that will build the dungeon itself, but not place anything in it. Doors, traps, stairs, monsters, and treasures will not fall within the scope of this program. Even the dungeon itself will be rather simplistic: it will consist of square or rectangular rooms, and corridors.
Dungeon generation )


roddy: (Default)
Roddy of the Frozen Peas


RSS Atom

Expand Cut Tags

No cut tags

November 2010


Style Credit