Evil Science A whole load of stuff

25Feb/140

C# Brute Force Sudoku Algorithm

I've created in C# an algorithm that solves sudoku using the brute force method. This algorithm is contained in the class csSudokuBruteForce.cs that can be found on GitHub here.

A little bit about it

The csSudokuBruteForce class contains a class called csCell which represents a cell within a sudoku grid with properties representing the row, column, box that cell belongs to, the cell's value and whether it is solved; 81 of these cells are stored within a generic list called grid which represent sudoku.

The public method BruteForce is called to begin the brute algorithm, which returns a integer array representing the solved sudoku. Testing on Quad core PC shows that solutions can be found in under a second for any tried.

This algorithm doesn't test the validity of the provided sudoku before it starts the brute force algorithm, and may therefore crash out if what is given to it is incomplete, malformed, containing incorrect characters. It just assumes it'll get a string 81 characters in length that consists of only the numbers 1 to 9 and 0.

Using the code

This class is easy to use, and requires only a string of 81 characters representing the sudoku to be solved.  Here's an example of it's use:


csSudokuBruteForce b = new csSudokuBruteForce();

<span style="line-height: 1.5em;">string puzzle = "003020600900305001001806400008102900700000008006708200002609500800203009005010300";</span>

//solve the sudoku and return the result as an integer array

int [] solution =  b.BruteForce(puzzle);

If you're using this code in a C# Console Application and want to output the array containing the solution, here's how to do it using Linq:


Console.WriteLine (
solution.Select((val, ind) => val.ToString() + ((ind+1) % 9 == 0 ? "\n" : ""))
.Aggregate((total, current) => total + current)
);

What about Project Euler 96?

No. I'm not going to tell you how to to solve it.

Go on!

No.

Please?

I'll give you a hand, but no more. Here's how to extract one puzzle at a time from Euler 96's text file of puzzles:


//load the entire sudoku.txt file
List<string> puzzles = new StreamReader("sudoku.txt").sr.ReadToEnd().Split('\n').ToList();

string puzzle;

for (int ctr = 0; ctr <= 49; ctr++)</span>
{

puzzle = puzzles.Where((val, ind) => ind >= (ctr * 10) +1 &amp;amp;amp; ind < (ctr * 10) +10)
.Aggregate((total, current) => total + current);

}

It uses loads the text file into a generic list, and then uses Linq to extract the required data from that file. Use your brain and work out how to use it yourself.

You're welcome.

Filed under: C# No Comments
24Feb/141

A C# algorithm to build interesting cave systems for your Roguelike !!!UPDATE!!!

Export map array as Bitmap

I have noticed that people have expressed an interest in getting an image of the generated map to pass into Unity3D. So I have updated the Github link to add a new function to the class csCaveGenerator.cs, that when called generates a bitmap of the map array, and I have pasted it below for your interest.

/// <summary>
/// Generate a bitmap from the contents of the map array
/// </summary>
/// <returns></returns>
public Bitmap GetMapImage()
{
//adjust to change the pixel size on the image
Size blocksize = new Size(5, 5);

Bitmap bmp = new Bitmap(MapSize.Width * blocksize.Width, MapSize.Height * blocksize.Height);
using (Graphics g = Graphics.FromImage(bmp))
{
using (SolidBrush sbBlack = new SolidBrush(Color.Black))
{
for (int x = 0; x < MapSize.Width; x++)
for (int y = 0; y < MapSize.Height; y++)
if (Map[x, y] == 1)
g.FillRectangle(sbBlack, new Rectangle(x * blocksize.Width, y * blocksize.Height, blocksize.Width, blocksize.Height));

}
}

Filed under: Main 1 Comment
23Feb/146

A C# algorithm to build interesting cave systems for your Roguelike part 1 UPDATED!!!!

I've been playing roguelikes for the last twenty years or so, and one thing that has consistently annoyed me is that dungeons, on the whole, tend to be rectangular rooms connected with long, straight corridors that turn at right angles. I've never came across a roguelike that has complex, chaotic looking cave systems with twisting corridors  and misshapen rooms, and that has annoyed me so much I decided to put together a simple algoritm in C# to generate such a system. Here's an example of a complex cave systems generated by my code, and below that I discuss the code used to generate it.

cavesystem3cavesystem2

!!!Update!!!

I have been blown away by the interest from the users of Reddit's Unity3D  and made an update to the code allowing users to generate a Bitmap of the generated map. See here for more details.

Overview

This algorithm works by using a modified form of Conway's Game of Life where:

  1. Each cell in the map is visited and a randomly probability is used to determine if that cell is closed,
  2. Cells are randomly visited and the number of neighbours that cell has is used to determine whether to close it or open it.

By repeating the second step thousands of times, "blobs" or "caves" start to form which. By adjusting various available properties the characteristics of the caves formed can change considerably, which can lead to some very interesting cave systems being formed.

After caves have been generated, a flood fill based algorithm locates each cave and the data for each cave into a generic list. With this list of caves they can be easily connected together with a dumb corridor building routine is used to try and connect the caves. This works by randomly selecting a cave and growing a corridor in a random direction and seeing if it hits another cave within a time period determined by a series of properties. If sucessful the two connected caves are placed in a list, and a further attempt is made to connect one of those caves to another, and so on.

The Application

You can find a simple C# application which demos the algorithm I've written here, and below is a screenshot of it.

app

The app consists of three areas:

  1. Property grid - the properties which govern the generation of the cave system.
  2. Picturebox - displays the generated cave system.
  3. Buttons:
    1. Build Caves - click to build a cave system.
    2. Connect Caves - click to connect the caves.
    3. Reset Properties - click the reset the property values to their default state.

Simply put, to build a cave system click the Build Caves button, and to change the appearance of a cave system fiddle with the properties.

Properties

This application has a number of properties which can be adjusted to determine the appearance of the generated generated cave system:

  1. Cave Cleaning
    1. Filling - Fills in holes within caves: an open cell with this number closed neighbours is closed.
    2. Lower Limit - the minimum size of caves allowed. If a cave is smaller than this number, it will be removed.
    3. Smoothing - Removes single cells from cave edges: a cell with this number of empty neighbours is removed
    4. Upper Limit - the maximum size of caves allowed. If a cave is larger than this number, it will be removed.
  2. Cave Generation
    1. Close Cell Prob - this value determines the chance of closing a visited cell.
    2. Cells to visit - the number of cells to visit during the generation process.
    3. Map Size - guess what this does.
    4. Neighbours - when this value is equalled or exceeded, change the cell state.
  3. Corridor 
    1. Breakout  - a counter value, that when exceeded stops attempting to generate corridors. Stops the corridor building process from getting stuck.
    2. Corridor Spacing - the number of empty cells the corridor has to have on either side of it for it to be built. This is dependant upon the direction it is travelling. If travelling north, it must have that number of empty cells to the east and west of it.
    3. Minimum Length - the minimum length of a corridor.
    4. Maximum Length - the maximum length of a corridor.
    5. Maximum Turns - the maximum number of direction changes a corridor can make whilst it is being built.
  4. Generated Map
    1. Caves - the number of caves in the generated system.

The Code

The code used to generate a caver system is contained within the class csCaveGenerator.cs, which sits in a standard C# form with a few controls on it which can manipulate that class.

For an overview of the class csCaveGenerator.cs, click here.

For a more detailed look at using the class csCaveGenerator.cs, click here.

To view the class csCaveGenerator.cs in GitHub click here.

Interesting Patterns

Playing around with the properties can produce cave systems with markedly different appearances, here are a few interesting systems that can be produced.

Several Large Caves

Setting the properties to:

  1. MaxSizeToRemove: 1500
  2. MinSizeToRemove: 450
  3. EmptyCells > EmptyCellNeighbours: 3

and clicking build a few times produced these three lovely caves.

cavesystem3

Many small chunky caves

Setting the properties to:

  1. Iterations: 10,000
  2. Smothing>EmptyNeighbours:3
  3. EmptyCells>EmptyNeighbours:4

And clicking build, produces lots of little chunky caves with straight edges, packed closer together.

cavsystem4

One Massive Cave

Setting the properties to:

  1. Caves > MaxSizeToRemove: 10000
  2. Cells > CloseCellProb: 55

And clicking Go a few times will produce a lovely, humongous cave, as shown below.

cavesystem5

 

Links

Github: To view the class csCaveGenerator.cs, which is used to generate the cave system, click here.

To download a C# app which demos the Cave Generator algorithm click  here.

Filed under: C#, Roguelike 6 Comments
23Feb/140

A C# algorithm to build interesting cave systems for your Roguelike – part 3

This post contains a more detailed look at the class csCaveGenerator.cs, whose layout is discussed here, and can be viewed on GitHub here

Within the class csCaveGenerator.cs, the source code is fully commented and easy to follow, and because I'm lazy I'm not going to copy those comments again :). However I will tell you how to use the class. Refer to the section below called Using the Class.

Using the class

This is simple enough:


csCaveGenerator cavgen = new csCaveGenerator();

To build a cave system:


cavgen.Build();

Connecting rooms is also simple:


cavgen.ConnectCaves();

The Generated Map

The publicly exposed property Map is a 2d array which contains the generated map - a value of 1 indicates a closed cell.

Filed under: C#, Roguelike No Comments
23Feb/140

A C# algorithm to build interesting cave systems for your Roguelike – part 2 class layout

This article describes the layout of the class csCaveGenerator.cs which is used to generate a cave system, and can be viewed on GitHub here. Within this class are several regions which are used to group together related methods, properties, data structures etc. These regions are:

  1. Properties
  2. Misc
  3. Map Structures
  4. Lookups
  5. Cave Related
  6. Corridor Related
  7. Direction Related
  8. Cell Related

Properties Region

Contains the properties used to control the appearance of the cave system being generated. Discussed in detail in part 1.

Misc

Contains the class constructor and the method Build() which generates the caves.

Map Structures Region

This contains the generic lists used to hold cave system data: Caves, Corridors and Map.

Lookups Region

Contains two lists of points which contain directions:

  1. Directions: four points which represent North, South, East and West.
  2. Directions1: 8 points which represent North, South, East, West, North East, North West, South East and South West.

These lists are used to examine the neighbours of a cell for the cave generation, smoothing and filling operations.

Cave Related Region

Contains the code used to generate caves, and subdivided into three regions:

  1. Make Caves
  2. Locate Caves
  3. Connect Caves

Make Caves

This contains the method BuildCaves() which generates the cave system

Locate Caves

This contains three methods used to locate discrete caves on the map and place them in the generic list Caves. The method GetCaves() is called to do this - which uses a recursive flood fill algorithm.

Connect Caves

Contains the method ConnectCaves(), a brute force method which randomly attempts to connect caves. Dependant upon methods in the Cave Related Region.

Corridor Related Region

Contains the methods:

  1. Corridor_GetEdge()
  2. Corridor_Attempt()
  3. Corridor_PointTest()

Which are all used by the method ConnectCaves().

Direction Related Region

This region contains a series of methods using in locating the neighbours of a cell, generating a randomly direction etc

Cell Related Region

A series of methods used for manipulating map cells.

Filed under: C#, Roguelike No Comments
11Feb/140

HTML 5: Canvas Element

ML 5 defines the <canvas> element as “a resolution-dependent bitmap canvas which can be used for rendering graphs, game graphics, or other visual images on the fly.” A canvas is a rectangle in your page where you can use JavaScript to draw anything you want.

This excellent article examines the canvas element in detail, clearly and concisely.

Filed under: HTML5 No Comments
20Jan/140

7 tricks to simplify your programs with LINQ

Does what it says above. Very handy.

http://igoro.com/archive/7-tricks-to-simplify-your-programs-with-linq/

Filed under: C# No Comments
8Jan/142

Creating a RogueLike Game View with C#

In a RogueLike the game view (GV) is a rectangular area of the map occupied by the player that is displayed on screen, an example of which is shown below. A gameview consists of two parts: a size and an origin (the x and y coordinates which define the top left corner). The origin is calculated from the player's current coordinates by subtracting half the GV width from player X and half the GV height from player Y, and making adjustments to them under certain conditions described below.

gameview1

This article describes how to calculate the coordinates required for a game view.

Terminology

The following terms are required in order to calculate the GV origin coordinates GVOriginX and GVOriginY:

  1. PlayerX, PlayerY - The coordinates of the player's current location
  2. GVWidth, GVHeight  - The size of the game view
  3. MapWidth, MapHeight - The size of the map the player is exploring.

It is assumed that MapWidth > GVWidth and MapHeight > GVHeight.

For the player to be displayed dead centre in the GV GVWidth and GVHeight must be odd numbers.

Calculations

This origin of the GV is defined as:

  • GVOriginX = playerX - GVWidth / 2
  • GVOriginY = playerY - GVHeight / 2

Therefore, the bottom right corners coordinates of the GV are GVOriginX + GVWidth and GVOriginY + GVHeight.

However, there are obvious conditions where GVOriginX and / or GVOriginY are less than 0, or the bottom right coordinates exceed the MapHeight and / or MapWidth, so we need to make the followings checks and correct as appropriate after calculating generating GVOriginX and GVOriginY:

Check Correction if true
GVOriginX < 0 GVOriginX = 0
GVOriginY < 0 GVOriginY = 0
GVOriginX + GVWidth > MapWidth GVOriginX -= (GVOriginX + iViewWidth - MapWidth)
GVOriginY + GWHeigtht > MapHeight GVOriginY -= (GVOriginY + iViewHeight - MapHeight)

The effect of making these changes will cause the player to be displayed off centre and closer to the edge being moved towards, as shown below. If none of the above corrections are required, the player will be shown in centre of GV as shown in the picture at the start of this article.

gameview2

Code

A Visual Studio demonstrating the above method in a simple demo which allows a player to explore a map using the keys Q,W,E,A,S,D,Z,X and C can be found here.

Github: here.

Have I seen this before?

The observant amongst you will notice that this code comes from my Evil Science article Field of Vision using recursive shadow casting: C# .Net 3.5 implementation, but I thought I'd use the code again with emphasis on how to draw the Game View.

Filed under: C#, Roguelike 2 Comments
6Jan/146

Simple Roguelike Dungeon Generator Using C#

Building a dungeon for your character to explore, along with being able to see that dungeon,  is one of the most important parts of a Roguelike, and unlike sight algorithms there is a near infinite number of ways that a dungeon can be generated. This article describes a simple map building algorithm using rooms and corridors, which is written in C# 3.5 - links to the code are the bottom of this article.

Building a Map

Using the app is pretty simple: select one of the two options in the combobox in the top left corner and click the button Build and a map will be generated. The property grid on the left hand side can be used to adjust various map building properties, which are discussed in more detail below.

MapBuilder

Two options are offered for building a map:

  1. Build_OneStartRoom - a start room is placed in the centre of a map as starting point, and rooms and corridors are built of it.
  2. Build_ConnectedStartRooms - two rooms are placed on opposite sides of the room and joined with a corridor as starting point, and rooms and corridors are built of it.

The difference between the two methods is that Build_OneStartRoom() produces a map with rooms and corridors clustered together, whilst Build_ConnectedStartRooms produces a more distributed map that fills more of the map area.

Map Properties

Adjusting the properties, which are discussed in more detail below, can produce maps with different appearances. Here are a few examples:

Example1
Build Probability: 100 - this will cause corridors to only be built of existing corridors.
Example2
Build Probability: 0 - this will cause corridors to only be built of existing existing rooms.
Example3
Rooms to Build: 5 and Maximum Corridor Turns: 25. Nice twisty corridors!
Example4
Corridor Spacing: 10, Break Out: 1000. Corridors must be a distance of 10 units away from other corridors. Break Out counter is increased to allow successful map generation.

 

Map Building Logic

Both of the map building options use the following logic to build a map:

  1. Place start room or rooms.
  2. Required number of rooms built? No, go to step 2, else quit.
  3. Get a random point on the edge of a room, or a corridor,
  4. Test if the only point is valid. Yes, go to step 3, else step 1.
  5. Attempt to build a corridor and examine the outcome of that method:
    1. The corridor has hit an existing room: build corridor
    2. The corridor has hit an existing corridor: build corridor.
    3. The corridor operation has completed: attempt to build a room on the end point of the corridor, and if successful build the corridor.
  6. If break out property exceeded exit the loop. Prevents the loop from getting stuck.
  7. Go to step 1.

Properties

Mapbuilder has a number of properties which can be adjusted to determine the appearance of the generated map:

  1. Corridor Related
    1. Corridor Spacing - the number of empty cells the corridor has to have on either side of it for it to be built. This is dependant upon the direction it is travelling. If travelling north, it must have that number of empty cells to the east and west of it.
    2. Minimum Length - the minimum length of a corridor.
    3. Maximum Length - the maximum length of a corridor.
    4. Maximum Turns - the maximum number of direction changes a corridor can make whilst it is being built.
  2. Map
    1. Map Size - the size of the rectangle containing the dungeon.
    2. Break Out - When this value is exceeded, exit the dungeon generating While loop.
  3. Probability
    1. Select room - the value between 1 and 100, that when exceeded will cause a room to be selected as the starting point for a corridor build operation.
  4. Room
    1. Corridor Distance - the minimum distance a room can be placed from existing corridors.
    2. Distance from other rooms - the minimum distance a room can be from other rooms before it can be built.
    3. Maximum Size - the maximum size of a room.
    4. Minimum Size - the minimum size of a room.
    5. Rooms to build - the total number of rooms to build.

Corridor Building

The process for finding a start point for a corridor is:

  1. To randomly choose a start point on a corridor or room and a direction the corridor will "grow" in using the method Corridor_GetStart. The property Select Room is used to determine the probability of choosing a corridor or room, by default it is set to 50%.
  2. If step 1 successful pass the start point and direction the method CorridorMake_Straight and examine the return value to determine what to build, some of the return values are:
    1. Completed: corridor has been completed without running into anything.
    2. Hit existing corridor: corridor has hit an existing corridor.
    3. Hit existing room
    4. Hit self

(All return types are described in the enum CorridorItemHit).

In the example method Build_ConnectedStartRooms() and Build_OneStartRoom(), if the corridor is completed, an attempt to build a room of it is made and if that is successful both the room and corridor are built. If the corridor hits an existing room, an existing corridor or itself the corridor is built.

Corridors are added to the map array, and also stored in the generic list lBuilltCorridors to enable additional tests when attempting to build other rooms or corridors. When a corridor is being built it is stored in the generic list lPotentialCorridor.

Room Building

A room is a rectangle which is built of a corridor end point in the direction the corridor was moving. After a rectangle has been created using the properties Minimum Size and Maximum Size, it is tested in the method Room_Verify()  for the following:

  1. Check it occupies legal, empty coordinates in the map 2d array.
  2. It is expanded by the property RoomDistance and tested to see if it makes contact with any current rooms stored in the generic list rctBuiltRooms.
  3. It is expanded by the property CorrdiorDistance and tested to see if it makes contact with any current rooms stored in the generic list lBuilltCorridors .

If the above criteria are met, the room is built - it is added to the 2d array map, and the rectangle which defines it is added to the generic list rctBuiltRooms.

Directions

When a corridor is being built a direction is chosen using one of the two methods:

  1. Direction_Get(Point dir) - get a random direction, as long as that direction is not the opposite of the one provided to the method. This prevents back tracking.
  2. Direction_Get(Point pDir, Point pDirExclude) -  get a random direction, as long as that direction is not the opposite of the one provided to the method AND the direction specified in pDirExclude. The later direction is the first direction chosen when a corridor is built - this will stop a generating corridor from going in the opposite direction to the one  it started with. Makes longer, less twisty corridors.

The corridor building method CorridorMake_Straight () offers a parameter called PreventBackTracking, that when set to to true will select the later option and when false the former. In all build_ examples, a value is selected randomly.

Break out, or getting stuck

Adjusting the properties will produce mazes with different characteristics, but may cause prevent the map from being built, for example if one specifies 100 rooms in a relatively small map the loop contained within the build method will never exit as 100 rooms won't fit, so a counter is placed within the loop that will cause the loop to exit when the property Break Out is exceeded and the method will return false and in the provided application a messagebox will alert the user to this.

The Map Builder Code

The class csMapbuilder.cs contains the code used to build a map.

The public methods Build_ConnectedStartRooms() and Build_OneStartRoom() are called to build a map, and the boolean value returned indicates if building a map was successful; success occurs when the required number of rooms are built before the property Break Out is exceeded.

The public property Map, a two dimensional integer array contains the built map. A value of 1 indicates a solid cell and value of 0 is an empty space your adventurer can explore.

Here's a bit of pseudo code demonstrating the above:


csMapbuilder mpbuild = new csMapbuilder(150, 150); //the numbers are the starting map size

if (mpbuild.Build_ConnectedStartRooms() == true)
{

//map drawing code to go here
}

Get the code

To download the C# source code click here.

Github: click here.

Filed under: Main 6 Comments
6Jan/140

Island and labyrinth generating algorithm using C#

This is a simple generating routine I developed in C# whilst experimenting whilst playing around with the algorithms for Conway's Game of Life.By adjusting the properties it can produce "island" or "labyrinth " type maps. I "discovered" this algorithm

Here's a few examples of maps it can generate, with the property values used to create them.  Explanations of the properties are given later in the article.

default.png
x=100,y=100,p=45, h=true, n=4, i = 50000 produce an "island" map.
variant1.png
 x=100,y=100,p=45, h=false, n=4, i = 50000 produce a "labyrinth" map.
variant2.PNG
 x=100,y=100,p=55, h=true, n=4, i = 50000.
variant3.PNG
 x=100,y=100,p=45, h=true, n=4, i = 85000.
variant5.PNG
x=100,y=100,p=45, h=false, n=2, i = 50000.
variant6.PNG
 x=100,y=100,p=75, h=true, n=5, i = 80000.

Using the App

Load up the app, fiddle with the properties and click the Go button.

How it Works

Map generation is controlled by the following variables:

  1. p (int) - close cell probability. Between 0 and 100.
  2. h (bool) - cell operation specifier.
  3. i (int) - counter.
  4. n (int) - number of cell's neighbours.
  5. c (int) - examined cell's closed neighbours. Between 0 and 8.

Calling the method go() in the class csIslandMaze will generate a map using the following logic:

  1. Randomly choose a cell from map
  2. If the cell is open use a p to determine whether we close it.
  3. Get c
    1. h = true: If c > n close the cell, else open it.
    2. h = false: If c > n open the cell, else close it.
  4. Repeat steps1 - 3 i number of times.

Varying the above mentioned variables will produce maps of surprisingly different appearances.

Source Code

You can download the C# source code here.

Github: here.

Filed under: C#, Roguelike No Comments