Archives

Archives / 2005 / February
  • Blogging

    Blogs are a new communication medium, mainly used as a single-direction information channel. On a blog, the owner publishes new posts, which can be read and commented on by readers.

    This model looks a lot like a forum where treads are started and replies are given, expect on a blog, only the blog owner creates new posts. Some compare this model to an online diary or the private newspaper of an amateur journalist.

    The greatest strength of blogs is the fact that they are very personal and contain a lot of valuable information. They also show the human side of companies when employees are blogging.

    Another great advantage of a blog is syndication. This is the use of a particular XML file, using a described schema, called an RSS-feed or an ATOM-feed, to display all the information on a particular blog. By using so called feed-readers, it is possible to read several blogs from one application.

    As a part of my internship, I had to post articles about what I did on my blog. Most of these articles correspond with the content of this report.



    Read more...

  • Virtual PC

    Another tool I had at my disposal was Microsoft Virtual PC. This is a product that enables you to run several operating systems inside your existing one, each one of them acting as a real PC.



    This was very useful when I needed to test some of the things I created on a different server, a Windows 2003 server running Windows SharePoint Services for example.

    After I had created my Windows 2003 image, I could use it on any PC I wanted to work on, on my laptop and on my desktop as well. This proved very useful when having to test against a specific machine.

    A virtual PC can share its network with the host operating system, making it possible to run several virtual machines at one, simulating a complete network, acting as if it were unique servers on the network. This was a very nice feature before deploying something to the real production servers.



    Read more...

  • SharePoint

    For the Microsoft Student Council, I decided to write a small database application that would keep track of the users their points. The council has access to a SharePoint site, so I decided to create a WebPart that would use existing user data and integrate nicely into the existing infrastructure.



    The first thing I did, was install the Web Part Templates for Visual Studio .NET on my machine. To do this, it required the Microsoft.SharePoint.dll during installation. So I decided to install Windows SharePoint Services first, which was freely available on the Microsoft Download website.

    After I installed SharePoint, I discovered the SmartPart. This is a special WebPart, created by Jan Tielens and Fons Sonnemans, which allows you to encapsulate a regular ASP.NET User Control in a WebPart. This is a great solution because it gives you the productivity of using the designer and the power of accessing the SharePoint Object Model at the same time.

    As this WebPart would be storing data, I had to start looking where to store it. My first idea was to store it right in the SharePoint database, but there was almost no information on it and I got advised it wasn’t a good thing to put third party data in the database. In the end I created two Custom Lists in SharePoint, who would act as database tables to store the data.



    The next step was the creation of the User Control. To do this, references to Microsoft.SharePoint.dll and SmartPart.dll had to be added, the SmartPart, Microsoft.SharePoint and Microsoft.SharePoint.WebControls namespaces had to be imported and the IUserControl interface had to be implemented. This interface takes care of the link between your User Control and the SharePoint Web.

    After this, it was possible to access everything of the SharePoint Object Model. For example, to fill a dropdown list with the available users, I used the following code:

     

    private void FillUserList() {

      this.viewUserList.Items.Clear();

                     

      SPUserCollection webUsers = this.SPWeb.Users;

      this.viewUserList.Items.Add(new ListItem("All", "-1"));

      foreach (SPUser webUser in webUsers) {

        this.viewUserList.Items.Add(new ListItem(

          Microsoft.SharePoint.Utilities.SPEncode.HtmlEncode(webUser.Name),

          webUser.LoginName));

      }

    } /* FillUserList */


    This dropdown was later used as a filter in the administrative part of the WebPart.

    To retrieve the available types from the Custom List, I used the following piece:

     

    private void FillTypeList() {

      this.typeList.Items.Clear();

      SPListItemCollection puntenTypes = this.SPWeb.Lists["PuntenList"].Items;

      foreach (SPListItem puntenType in puntenTypes) {

        if (!Convert.ToBoolean(puntenType["Obsolete"].ToString())) {

          this.typeList.Items.Add(new ListItem(

                                          puntenType["Punten Type"].ToString(),

                                          puntenType["Punten Type"].ToString()));

        }

      }

    } /* FillTypeList */


    With code like these small pieces, demonstrating the SharePoint Object Model, I created a small User Control, containing a DataGrid to display the items, some input fields to add new items and a dropdown list with users, to filter on when being logged on as an Administrator.

    Read more...

  • NSurvey - Pie Charts

    NSurvey already provides general charts displaying the results, but it uses a bar chart and I had to output pie charts as well. So, I implemented them as well.

    First, I created a new page, called PieChartReport.aspx, which was empty. After this I used the same code as the BarChartReport and filled up a ChartPointCollection, which I then used to create a new PieChart, render it and send it back to the client

     

    ChartEngine engine = new ChartEngine();

    ChartCollection charts = new ChartCollection(engine);     

               

    engine.Size = new Size(350, 400);

    engine.Charts = charts;

    engine.Title = new ChartText();

               

    if (questions.Questions[0].IsParentQuestionIdNull()) {

      engine.Title.Text = Server.HtmlDecode(

              Regex.Replace(questions.Questions[0].QuestionText, "<[^>]*>", " "));

    } else {

      String questionText = String.Format("{0} - {1}",

                          questions.Questions[0]["ParentQuestionText"].ToString(),

                          questions.Questions[0].QuestionText);

      questionText = questionText.Replace(Environment.NewLine, "");

      questionText = questionText.Replace("\t", "");

      questionText = questionText.Replace("<p>", "");

      questionText = questionText.Replace("</p>", "");

      engine.Title.Text = Server.HtmlDecode(

                                     Regex.Replace(questionText, "<[^>]*>", " "));

    }

     

    PieChart pie = new PieChart(data);

    engine.Charts.Add(pie);

    ChartLegend legend = new ChartLegend();

    legend.Position = LegendPosition.Bottom;

    engine.HasChartLegend = true;

    engine.Legend = legend;

    engine.GridLines = GridLines.None;

     

     

    Update: I used the following control by the way (which was already in NSurvey): http://www.carlosag.net/Tools/WebChart/Default.aspx

    Read more...

  • NSurvey - MapPoint Integration

    NSurvey provides charting reporting by default, but this could be enhanced by using the Country List control together with the added Belgian Regions. With this question in a survey, as a required question, every entry would have location information. Together with MapPoint a graphical overview could be made, showing additional information per country and region.

    To accomplish this, I created a new administration page and edited the UINavigator and HeaderControl classes to add the new page to the menu. On this page were two dropdown lists which included the column names of a survey’s text entries. These lists were used to indicate where NSurvey stored the Country and Region questions. Together with a button that would generate the chart.



    To generate the chart, all possible regions were first collected by grouping the entries and storing the unique country and regions. After this, the MapPoint FindService was instantiated and the Find method was called for each address.

     

    FindServiceSoap findService = new FindServiceSoap();

    if (ConfigurationSettings.AppSettings["MapPointProxy"] != String.Empty) {

      findService.Proxy = this.proxyObject;

    }

    findService.Credentials = this.ourCredentials;

    findService.PreAuthenticate = true;

                     

    FindSpecification findSpec  = new FindSpecification();

    findSpec.DataSourceName = "MapPoint.EU";

                     

    foreach (DictionaryEntry locationEntry in locationData) {

      // key example: "West-Vlaanderen, BE"

      findSpec.InputPlace = locationEntry.Key.ToString();

      FindResults foundResults = findService.Find(findSpec);

      if (foundResults.NumberFound > 0) {

        ((CustomLocation)locationEntry.Value).LatLong =

                                   foundResults.Results[0].FoundLocation.LatLong;

      }

    }


    This gave me the LatLong of every location MapPoint had found, which I used to create an array of Location objects to be passed to the GetBestMapView method. This method returned a MapViewRepresentations object which described to view to use when calling the GetMap method. This view assured every location was on it.

     

    MapViewRepresentations mapRepresentations =   

                         renderService.GetBestMapView(myLocations, "MapPoint.EU");

    ViewByHeightWidth[] myViews = new ViewByHeightWidth[1];

    myViews[0] = mapRepresentations.ByHeightWidth;

     

    At this point all required location information was known, the only thing left was to define pushpins that would show up on the generated map and would be clickable.

     

    Pushpin[] myPushpins = new Pushpin[foundRegions.Count];

    Int32 pinCounter = 0;

    foreach (DictionaryEntry foundRegion in foundRegions) {

      myPushpins[pinCounter] = new Pushpin();

      myPushpins[pinCounter].IconDataSource = "MapPoint.Icons";

      myPushpins[pinCounter].IconName = "1"; // Red pin

      Int32 nrResults = ((CustomLocation)foundRegion.Value).ResultCount;

      myPushpins[pinCounter].Label = String.Format("{0} {1}",

                                         nrResults,

                                         (nrResults == 1) ? "result" : "results");

      myPushpins[pinCounter].LatLong = (LatLong)foundRegion.Key;

      myPushpins[pinCounter].ReturnsHotArea = true;

      myPushpins[pinCounter].PinID =

                                    (CustomLocation)foundRegion.Value).Location();

      pinCounter++;

    }


    To get the map, I had to call the GetMap method and supply a MapSpecification. This specification describes the size of the map, the quality, the pushpins and what MapPoint should return. Here, it will return a URL, pointing to the generated map.

     

    MapSpecification mapSpec  = new MapSpecification();

    mapSpec.DataSourceName = "MapPoint.EU";

    mapSpec.Views = myViews;

    mapSpec.Options = new MapOptions();

    mapSpec.Options.ReturnType = MapReturnType.ReturnUrl;

    mapSpec.Options.Format = new ImageFormat();

    mapSpec.Options.Format.Height = 500;

    mapSpec.Options.Format.Width = 500;

    mapSpec.Options.Style = MapStyle.Locator;

    mapSpec.Pushpins = myPushpins;

    MapImage[] mapImages = renderService.GetMap(mapSpec);


    After the call, MapPoint returned a MapImage object, containg the url to the map, together with information about the special areas on the map, called HotAreas. To make these areas clickable on the map, an HTML imagemap had to be generated.

     

    StringBuilder imageMapName = new StringBuilder();

    imageMapName.Append("<map name=\"").Append(mapObject.ID);

    imageMapName.Append("_Map\">");

    for (Int32 i = 0; i < hotAreas.Length; i++) {

      String pinId = hotAreas[i].PinID;

      imageMapName.Append("\n<area shape=rect coords=\"");

      imageMapName.Append(hotAreas[i].IconRectangle.Left).Append(",");

      imageMapName.Append(hotAreas[i].IconRectangle.Top).Append(",");

      imageMapName.Append(hotAreas[i].IconRectangle.Right).Append(",");

      imageMapName.Append(hotAreas[i].IconRectangle.Bottom);

      imageMapName.Append("\" title=\"").Append(pinId).Append("\">");

    }

    imageMapName.Append("</map>");

    this.imageMapHotAreas.Text = imageMapName.ToString();

    mapObject.Attributes["USEMAP"] = "#" + mapObject.ID + "_Map";

     

    The result was a map, scaled to the best size to include all locations, with pushpins on it, which are clickable and point to the same page with an additional querystring.



    This made it possible to visualize the results per region, and when you select a certain region, provide filtered results of that region.

    Read more...

  • NSurvey - Belgian Regions

    One of the standard controls of NSurvey is the Country List, which provides a dropdown list of countries. Belgium is one of these countries, but when you select Belgium, it doesn’t display the possible regions for Belgium.

    This is because the region information is also implemented with the subscriber model. When the country selection changes, it publishes the selected country to the Region List which then looks up the xml file of the selected country, containing the region information. The problem was that there wasn’t a region file for Belgium. So, I looked up the Belgian regions from Microsoft Passport and created the be.xml file:

     

    <?xml version="1.0" standalone="yes"?>

    <NSurveyDataSource xmlns="http://www.nsurvey.org/NSurveyDataSource.xsd">

      <XmlDataSource>

        <RunTimeAnswerLabel>Region :</RunTimeAnswerLabel>

        <XmlAnswers>

          <XmlAnswer>

            <AnswerValue></AnswerValue>

            <AnswerDescription>[Select Region]</AnswerDescription>

          </XmlAnswer>     

          <XmlAnswer>

            <AnswerValue>Antwerpen</AnswerValue>

            <AnswerDescription>Antwerpen</AnswerDescription>

          </XmlAnswer>

          <XmlAnswer>

            <AnswerValue>Vlaams-Brabant</AnswerValue>

            <AnswerDescription>Vlaams-Brabant</AnswerDescription>

          </XmlAnswer>

          <XmlAnswer>

            <AnswerValue>Hainaut</AnswerValue>

            <AnswerDescription>Hainaut</AnswerDescription>

          </XmlAnswer>

          <XmlAnswer>

            <AnswerValue>Liege</AnswerValue>

            <AnswerDescription>Liege</AnswerDescription>

          </XmlAnswer>

          <XmlAnswer>

            <AnswerValue>Limburg</AnswerValue>

            <AnswerDescription>Limburg</AnswerDescription>

          </XmlAnswer>

          <XmlAnswer>

            <AnswerValue>Luxembourg</AnswerValue>

            <AnswerDescription>Luxembourg</AnswerDescription>

          </XmlAnswer>

          <XmlAnswer>

            <AnswerValue>Namur</AnswerValue>

            <AnswerDescription>Namur</AnswerDescription>

          </XmlAnswer>

          <XmlAnswer>

            <AnswerValue>Oost-Vlaanderen</AnswerValue>

            <AnswerDescription>Oost-Vlaanderen</AnswerDescription>

          </XmlAnswer>

          <XmlAnswer>

            <AnswerValue>Waals-Brabant</AnswerValue>

            <AnswerDescription>Waals-Brabant</AnswerDescription>

          </XmlAnswer>

          <XmlAnswer>

            <AnswerValue>West-Vlaanderen</AnswerValue>

            <AnswerDescription>West-Vlaanderen</AnswerDescription>

          </XmlAnswer>

        </XmlAnswers>

      </XmlDataSource>

    </NSurveyDataSource>

    Read more...

  • NSurvey - Microsoft Layout

    As this application was going to collect feedback from Microsoft events, it had to look like it belonged to Microsoft, and it had to be designed professionally. To do this, I visited the Microsoft site, and saved the page to my dev pc. There I stripped all the content and created a template with two user controls, SiteHeader and SiteFooter.

    The next step was to include the previously created SurveyListControlOverview on the Default.aspx page to provide a starting point for the user.



    When they user selected a survey and clicked the button, the OverviewSurveyId property was retrieved and forwarded to the Survey.aspx page, which displayed the survey in the same layout, together with the survey title.



    If an error occurs, the user gets redirected to a generic error page and an email gets dispatched to the site administrators.



    A contact page was also added to provide a contact person for users having problems or questions.



    The last step in creating the layout was testing if it worked the same in Internet Explorer and Mozilla Firefox. Luckily it worked the same from the first time and the layout was finished.

    Read more...

  • NSurvey - Answer Types

    By default NSurvey provides different kinds of answer types. These are for example Basic Field, Rich Field, Calendar Field, Email Field, Hidden Field, Password Field, Large Field and dropdown lists which use XML files as data source. NSurvey, however, also allows you to extend on these types to create new answer types, with specific functionality.

    One of the requirements of the survey was that it had to be possible for students to select their school from a list, but also have the possibility to enter it manually if it wasn’t listed. To do this, I created a School answer type.

    This type was inherited from a regular Basic Field type, but was invisible by default. The special feature of this field was that it subscribed to a dropdown list which listed all available schools and an Other possibility. This meant that when the selection of the dropdown list changed, it would publish the new selection to all subscribed answers. Because of this, when the Other possibility was chosen, the field was made visible and it was possible to manually enter the school.

    To do this, I had to implement the IAnswerSubscriber interface and use the following code for the ProcessPublishedAnswers method:

     

    public void PublisherCreation(Object sender, AnswerItemEventArgs e) { }

     

    public void ProcessPublishedAnswers(Object sender, AnswerItemEventArgs e) {

      if (e != null && e.PostedAnswers != null && e.PostedAnswers.Count > 0) {

        String selectedSchool = ((PostedAnswerData)e.PostedAnswers[0]).FieldText;

        this.ShowField = selectedSchool.ToLower().Equals("other");

        this.CreateChildControls();

      }

    } /* ProcessPublishedAnswers */


    I also provided a modified CreateChildControls method:

     

    protected override void CreateChildControls() {                        

      if (this.ShowField) {

        if (this.ShowAnswerText) {

        // This prevents the Answer title being displayed twice

          if (Controls.Count > 2) {

            Controls.RemoveAt(1);

            Controls.RemoveAt(0);

          }

          if (this.ImageUrl != null && this.ImageUrl.Length != 0) {

            Image selectionImage = new Image();

            selectionImage.ImageUrl = this.ImageUrl;

            selectionImage.ImageAlign = ImageAlign.Middle;

            selectionImage.ToolTip = Text;

            Controls.AddAt(0, selectionImage);

          } else {

            Literal literalText = new Literal();

            literalText.Text = this.Text;

            Controls.AddAt(0, literalText);

          }

          Controls.AddAt(1, new LiteralControl("<br>"));

        }

     

        if (this.FieldHeight > 1) {

          // Creates a multi line field

          _fieldTextBox.TextMode = TextBoxMode.MultiLine;

          _fieldTextBox.Wrap = true;

          _fieldTextBox.Columns = this.FieldWidth;

          _fieldTextBox.Rows = this.FieldHeight;

        } else {

          _fieldTextBox.MaxLength = this.FieldLength;

          _fieldTextBox.Columns = this.FieldWidth;

        }

     

        Controls.Add(_fieldTextBox);

        OnAnswerPublisherCreated(new AnswerItemEventArgs(GetUserAnswers()));

      } else {

        Controls.Clear();

      }

    } /* CreateChildControls */

    This way, the field only got shown when the published answer equaled other, otherwise it was hidden. Another version of this was the CheckBoxField answer type. This type provided a default invisible field, which became visible after a certain checkbox was checked.



    Read more...

  • NSurvey - Matrix Questions

    NSurvey supports matrix questions in its surveys. The only problem with this type of question was that in the reporting section of NSurvey, it listed each row of a matrix question as a possible selection, but it didn’t include which matrix it belonged to. This leaded to a very confusing list, when you have several identical matrix questions which only differentiated in the main question asked.

    The solution I had in mind was to change the output from “row question” to “matrix question – row question”. To do this, I first had to modify some stored procedures to include the ParentQuestionText field. After this I traced down the places where the possible questions were added to the dropdown list and added some logic to check if it was a matrix question and concatenated the matrix question with the row question.

    One of the places where I had to do this was in the BarChartReport class, which was responsible for generating charts of the rated matrix questions. In the SetQuestionData method the following piece of code could be found

     

    engine.Title.Text = Server.HtmlDecode(

           Regex.Replace(_dataSource.Questions[0].QuestionText, "<[^>]*>", " "));


    Which I changed to the following:

     

    if (_dataSource.Questions[0].IsParentQuestionIdNull()) {

      engine.Title.Text = Server.HtmlDecode(

    Regex.Replace(_dataSource.Questions[0].QuestionText, "<[^>]*>", " "));

    } else {

      String questionText = String.Format("{0} - {1}",

     _dataSource.Questions[0]["ParentQuestionText"].ToString(),

     _dataSource.Questions[0].QuestionText);

      questionText = questionText.Replace(Environment.NewLine, "");

      questionText = questionText.Replace("\t", "");

      questionText = questionText.Replace("<p>", "");

      questionText = questionText.Replace("</p>", "");

      engine.Title.Text = Server.HtmlDecode(

                        Regex.Replace(questionText, "<[^>]*>", " "));

    }


    This change, together with the changed procedure because the ParentQuestionText had to be used, resulted in charts with the correct title.



    The only thing left was to make sure this change also occurred in the HTML report and the questions dropdown list.

    To do this I had to add the following piece of code to the GetQuestionListWithSelectableAnswers method in the DataAccess part:

     

    foreach (QuestionData.QuestionsRow row in questions.Questions) {

      if (!row.IsParentQuestionIdNull()) {

        row.QuestionText = String.Format("{0} - {1}",

                                        row["ParentQuestionText"].ToString(),

                                        row.QuestionText);

      }

    }


    These changes made the matrix questions display correctly, as you can see in this picture, which represents a five-question matrix.

    Read more...

  • NSurvey - Survey Overview

    The first thing I noticed is the small dropdown in the admin section listing all available surveys. This would become my starting point for users, a perfect place to choose the survey they want to take.

    I tracked this down to the SurveyListControl user control which I inherited to create SurveyListControlOverview. This user control removes to automatic postback when it’s in overview mode and also provides an OverviewSurveyId property to indicate the selected survey. It also displays all surveys, because it had to run in anonymous mode, without users having to log on before being able to answer. A shared password would be provided on the event, giving access to the survey.

    After this, the user could select a survey from the dropdown list. The only problem was that the choices were ordered by creation date, which would become a problem in the long run when a lot of surveys would be available. To change this I added a simple ORDER BY Title in the vts_spSurveyGetList stored procedure.

    At this point, I had a dropdown list with all surveys listed alphabetically to add to any aspx page I wanted.

    Read more...

  • NSurvey

    For one of the projects I had to do, I had to create an online survey application, which would be used to gather feedback from Microsoft events. Up until then, feedback was collected by handing out a form and entering the data manually.

    As I was given free choice on how to solve this problem I suggested using an existing open-source framework and extending it to meet the requirements. This suggestion was quickly approved because on one side it meant commitment from Microsoft towards open-source and on the other hand it prevented re-inventing the wheel. The project used for this solution is called NSurvey. This provides a survey framework, making it very easy to setup surveys, add questions, add users, do mailings, implement security on a survey-based level, perform statistical operations on the answers and add new functionality by extending on existing classes.



    NSurvey is an ASP.NET application, written in C#, which uses a SQL Server back-end, using stored procedures, and various other layers. The installation of NSurvey went very smoothly because of an msi file, placing all files in their correct location.

    I started by testing the application and learning the big structure of how it worked. During this small test round, I began thinking on how the final solution would look.

    Read more...

  • Reflector

    One of the tools I had in my toolbox was Reflector. This tool is written by Lutz Roeder and allows you to examine a .NET assembly. Through the use of reflection it can display all namespaces, classes, methods, properties, events and fields in the dll.

    It is possible to view the code in IL, C#, VB.NET and Delphi. Some of the useful features are the Call and Callee Graph.

    The Call Graph shows you which items are used by a given method, while the Callee Graph displays all the methods that call a given method.







    Forgot something for blog readers, the url where to get it: http://www.aisto.com/roeder/dotnet/

    Read more...

  • Imagine Cup

    Important note (to not get confused):
    The text below (and the future ones) is written in the past tense, because they are text that have to go into a book for school, which you have to write after your internship, giving info about what you did. But I'm writing it piece by piece, because otherwise it will be too much to remember, and a lot less detailed :)



    For the second year in row, Microsoft organized the Imagine Cup. This is an international contest with various categories. As a part of my internship, I had to compete in the Visual Gaming and the Information Technology category.


    The IT category was about diving into solving real life IT problems. With questions about networks, databases and various servers the content was really diversified.

    You get 30 minutes to solve 30 questions, scoring 3 for each correct answer, 0 for a blank answer and -1 for a wrong answer. The first 5 people of a country advanced to the next category, which was the first goal of my internship.

    After having spent half an hour taking the quiz, I had to wait a day to get the results, to prevent abuse. My score ended up being a 66/90, placing me at a shared first place in the Belgian competition. My first goal was reached.



    The Visual Gaming competition was a coding challenge. In this competition you were given an SDK, which included a 2D-viewer, 3D-viewer, documentation and the required assemblies.

    In the VG competition you had to write code for robots in a small game, their brains, or also called, AI. The main things I learned thanks to this competition were algorithm-knowledge, performance issues and logic thinking.

    Algorithm knowledge was useful to find optimal actions for the robots, for example, the A* algorithm explained above, helped to find the shortest path. Other algorithms such as Traveling Salesman Problem also had to be solved and implemented to gain a strategic advantage in this game.

    Performance was a very important aspect in the VG competition. Because your code had a limited time-window it could run in, it had to be very fast, making sure it stayed inside that window. This was the reason why I implemented a binary heap in the pathfinder, and why I made a lot of performance optimizations, such as preventing boxing and unboxing, storing certain 2-dimensional arrays in a 1-dimensional and cutting back on object initializations.

    But knowing how the algorithms work and how to tweak for performance alone didn’t do the trick. The difficulty lies in making it all work together and operating as a big unit, working its way to a victory. That’s where logic thinking came in, to determine what tactics to use, and which algorithms to use.

    After having played with this an afternoon I managed to get 1325 points, which was enough to get to Round 2, and to achieve another internship goal. My personal next goal was to try to score as good as possible in the second round.

    (Which I will talk about when the second rounds is on its way :p)

    Read more...

  • Binary Heaps

    A pathfinder has to be very fast, but when we take a look at the performance we notice that working with the open-list is the bottleneck.

    There are several possible data structures to store the open-list. We could use an ArrayList to store the values and keep it sorted using an IComparable interface. With this solution we end up with too much overhead keeping the entire list sorted. After all, the only thing our pathfinder is interested in, is the node with the lowest F-score, it doesn’t care about the other nodes.

    A better solution is using a binary heap. In a binary heap, each item has two children with a value higher or equal to itself. Which means in the end the lowest item is at the top of the heap, easily accessible.



    One of the nice things of a binary heap is the fact that it can be stored in a 1-dimensional array, making sorting of the heap a very quick operation.

    The top of the heap is always stored at index 1. We don’t use the 0-index when working with zero-based arrays.



    The children of any given item are always stored at the item’s location * 2 and the item’s location * 2 + 1. For example, in the image given above, the item with value 20 is stored at index 3 and its two children can be found at index 6 (3 * 2) and index 7 (3 * 2 + 1).

    Adding an item to a binary heap can be achieved by adding the new item at the end of the array and then letting the new item bubble its way up.

    This is achieved by comparing the item with its parent, swapping them when the item is smaller then its parent and repeating this until the parent is smaller.

     

    public void Add(Int32 fCost) {

      this.binaryHeap[this.numberOfItems] = fCost;

      

      Int32 bubbleIndex = this.numberOfItems;

      while (bubbleIndex != 1) {

        Int32 parentIndex = bubbleIndex / 2;

        if (this.binaryHeap[bubbleIndex] <= this.binaryHeap[parentIndex]) {

          Int32 tmpValue = this.binaryHeap[parentIndex];

          this.binaryHeap[parentIndex] = this.binaryHeap[bubbleIndex];

          this.binaryHeap[bubbleIndex] = tmpValue;

          bubbleIndex = parentIndex;

        } else {

          break;

        }

      }             

      this.numberOfItems++;

    } /* Add */


    To remove an item from a binary heap, we simply take the item at index 1. But now we have to repair our heap, because there is a gap at the top. To fix this we take the last item and place it at the top, after which we let it sink downwards. This is done by comparing the value with its two children, replacing it with the smallest child and repeating this until the parent is smaller than both children.

     

    public BinaryHeapItem Remove() {

      this.numberOfItems--;

      Int32 returnItem = this.binaryHeap[1];

     

      this.binaryHeap[1] = this.binaryHeap[this.numberOfItems];

     

      Int32 swapItem = 1, parent = 1;

      do {

        parent = swapItem;

        if ((2 * parent + 1) <= this.numberOfItems) {

          // Both children exist

          if (this.binaryHeap[parent] >= this.binaryHeap[2 * parent]) {

            swapItem = 2 * parent;

          }

          if (this.binaryHeap[swapItem] >= this.binaryHeap[2 * parent + 1]) {

            swapItem = 2 * parent + 1;

          }

        } else if ((2 * parent) <= this.numberOfItems) {

          // Only one child exists

          if (this.binaryHeap[parent] >= this.binaryHeap[2 * parent]) {

            swapItem = 2 * parent;

          }

        }

        // One if the parent's children are smaller or equal, swap them

        if (parent != swapItem) {

          Int32 tmpIndex = this.binaryHeap[parent];

          this.binaryHeap[parent] = this.binaryHeap[swapItem];

          this.binaryHeap[swapItem] = tmpIndex;

        }

      } while (parent != swapItem);

      return returnItem;

    } /* Remove */


    A small comparison between an ArrayList and this binary heap implementation gives the following results:

    Binary Heap: added 4000 items.

    Time needed: 00:00:00

    Lowest F-score: 1

    Sorted ArrayList: added 4000 items.

    Time needed: 00:00:07.2968750

    Lowest F-score: 1

     

    Binary Heap: added 10000 items.

    Time needed: 00:00:00.0156250

    Lowest F-score: 1

    Sorted ArrayList: added 10000 items.

    Time needed: 00:00:56.1250000

    Lowest F-score: 1


    Inspiration and some images used from Patrick Lester.

    Read more...

  • A* Algorithm

    The A* algorithm works with two lists, an open-list and a closed-list. The open-list is the list of nodes to be checked, while the closed-list already has been checked. Each node also gets scored with F, G and H-scores.

     

    ·         F-score:   Total cost for a node (G-score + H-score).

    ·         G-score:   Movement cost.

    ·         H-score:   Estimated movement cost.

    In my demonstration program I used pixels as nodes in a grid-based map. A rule the pathfinder had to obey was it could only move horizontally and vertically.

    We start with a begin point and an endpoint, a map and we know which nodes are not passable.



    The first step in A* is to add the start point to the closed list, and examine its neighbors.

    We ignore it if it’s an obstacle or already on the closed list. When it’s not yet on the open-list, we add it to the open-list, and when it’s already on the list, we check of the G-score isn’t lower than the current G-score. If the score is lower, we change the parent of the node.



    These steps are repeated until the goal-node is added to the open-list.

    Thanks to the parent information of each node it is possible to reconstruct the shortest path from end to start.



    The most important information for the algorithm is that it has to know the node with the lowest F-score, because this is most likely the one leading to the shortest path, and the one which will be added to the closed-list during the next iteration.

    Because the pathfinder has to be fast, the data structure used to store these values has to be very fast as well. That’s why a binary heap is used in combination with A*.

    (Other data structures can be used, but this solution proved to be the fastest on a 200 * 200 map)

    Read more...

  • Day One

    The first task I got during my internship was to manage a meeting of the Microsoft Student Council. This was also the start of my internship, the real thing from the beginning.

    The Microsoft Student Council is a Microsoft program focused towards students. Its goals are to support dedicated students who are willing to work with new technologies and are passionate about learning new things. Every student is able to join the council, without any costs. The only requirement consists out of the students coming to Microsoft, instead of Microsoft asking students to join. In other words, if you are motivated, you can be part of it.

    The council organizes four meetings a year, each with a different theme. These students also get the opportunity to attend Microsoft seminars and to get involved in discussions with Microsoft developers. Nowadays there are about 100 students who are part of this council.

    Besides organizing training and meetings, the Microsoft Student Council also tries to get students involved in various competitions and challenges, trying to spark the students’ interest for new things. This results in a good community-feeling among the involved students, learning each other new things.

    On the 11th of February 2005 the second meeting took place, having Digital Entertainment as its theme. Due to an unexpected absence of the person organising it, I was assigned to manage this meeting during the day.

    Practically this meant I had to provide the required information for everyone on the SharePoint site used by the council, provide a route description, act as a contact person for the speakers, welcome everyone on the meeting, close the meeting at the end and make sure all speakers follow their assigned speaking times.

    I also was a speaker myself during this event. My talk was about Game Programming - AI in Games, in particular about the A* pathfinding algorithm and using a binary heap as data structure.

    Pathfinding is very important in gaming, because it is used a lot it has to be as fast and efficient as possible. A good pathfinder can be used to calculate distances as well.

    For navigation, the A* algorithm is used to find the shortest path.



    Note to blog readers: Because I'm writing all of this in Word, I can't paste it into .Text without the layout getting screwed up, so I removed some table formatting and images. I do try to make readable though ;)

    Read more...

  • Internship at Microsoft

    As some of you might now, I'll be doing my internship at Microsoft.

    One of the things I'm supposed to do, is blog about my time there.

    So, because of this, there is now an MS Internship category on my blog.

    Ofcourse not everything I do will be posted, but I'm sure there will be enough :)

    I'm really looking forward working there!

    Read more...

  • DevDays 2005 Belgium - Day 1 - Full Report

    Allright, currently it's a very busy time, but some people asked for more info about the previous DevDays 2005, so here is my attempt :)

    First of all, I haven't taken any pictures this time, because I had to give my bag away at the start, and the camera was in there.

    The first presentation after Bill Gates' keynote was by Philippe Destoop about Closing The Gap Between Development And Operations: A Developer's Perspective.

    The main problem lies withing a lack of communication between developers and operations. Depending on the size of a company Operations has either little power or unlimited power. In either case, not talking to Operations can lead to your company suffering loss when your application crashes, or when Ops have a lot of power, prevent your app from being deployed.

    The solution to this is to work together with Ops during development and to make them like your app ;)

    You do this by communication a lot and by implementing monitoring and control functionality into your app, to be used by Ops later on.

    The good thing is, a lot of the code needed to do this already exists, in the form of the Enterprise Library. More particulary, the Logging and Instrumentation Application Block.

    Using this block you can raise events and timed events to about anything you want. Making it possible for Ops to receive these events in their monitoring programs and do something with it.

    You can view some examples of code in the presentation.

    Next presentation was IT Fortress: Developing On A Secured Infrastructure by Raf Cox.

    He talked about security, first examine what you want to protect and why, then choose a technology to protect it with, and don't be shy of using built-in technology of the OS, it's better then re-inventing it.

    In a secure environment you have to be aware as a developer that your application isn't as "free" as it might be in your development environment. It can be run as a normal user, not fully trusted, with limited network access.

    You always have to think about possible security bugs, if you don't, they will be there and hackers will know them.

    After this he explained the possible authentication choices in Windows, how Basic Authentication, SSL and Kerberos works.

    You can use Windows for authorization as well. By using the Authorization Manager it is possible to define common roles in your organisation with common used operations and define their permissions in the manager in a central place. After this applications all can use this information.

    Last part of the presentation was about using least privilege. You can read all about it in the presentation.

    Third presentation of the day was by Clemens Vasters about Interop & Integration: Best Practices For SOA With Today's Technologies.

    During this presentation everything that has been shown is readily available, no future products were used, which is a nice thing for a presentation! :)

    The presentation was based on a demonstration example to explain how service-oriented architecture works.

    Basicly every functionality in the example is a service, when you take a look at the big overview it looks like a very modular system where each service has one well-defined task and works together with other services.

    Some properties of these services are autonomy, where each service control and hide their state, services also are never hard linked to each other and are platform independant, so no returning DataSets.

    Services also contain "edge code", which is code specifically written for the borders, and do nothing but forward to the real code that handles the logic, which are basic classes.

    This was a very energy-rich session, with a lot of new information, which is still being processed by my brain :)

    You can view all the diagrams in the presentation.

    Next presentation was Best Practices For Windows Forms Development by Marc Ghys and Bart Debeuckelaere.

    The first issue was to improve performance for Smart Clients. This can be done by using a lot of caching, compress the SOAP messages, and possibly use ngen.exe to precompile your assemblies. Also when you have to do something intensive, do it when the user expects it, for example, make a web-service call when a user clicks a submit button while showing a loading msg, and not when he leaves a textbox for example.

    Next was how to secure webservices, by using the integrated authentication mechanisms in Windows and by using WSE.

    Other things during this presentation were creating your own controls to provide a consistent look and feel in your application, using code generation to save time and to have consistent code. Then some info was given about ClickOnce, but the demo failed and then the time was up. But you can view the presentation for more info.

    At the end of the day there was a community block left. These were the Lightning Talks where I talked about Alternate Data Streams. And these are the only photos I have of the day, taken by Tom Mertens, tnx!



    This concludes day 1, tommorow I'll try to do the same for day 2, I also ran out of time now ;)

    Read more...

  • DevDays 2005 Day 2 - Exams & Internship

    The Developer & IT Pro Days 2005 are over, as well are my exams.

    During day 2 we saw what is going to come with the next .NET version (partial files, generics, ClickOnce, ...) and what mistakes an admin can make in his IT setup and how to fix them.

    The last one was really funny, but sadly enough those mistakes are often made, running SQL Server as SYSTEM, SQL Injection, simple passwords, no defense in depth, logging on as domain admin, ...

    My exams are also over now, the last one of my current education, coming up next is a 3-month internship at Microsoft.

    And just like Tom's doing, here is a picture of the Channel 9 guy, sitting together with the Azlan mascotte on the tower of stuff I had to learn these last 3 weeks for my exams :)

    Read more...