Sorting Algorithm Module

September 25, 2010

This is a continuation of the article “WonderBuilders Module Contributions,” written by Wonderland Architect and WonderBuilder partner, Jonathan Kaplan.

WonderBuilders Module Contributions – Sorting Algorithm Module for CS Education

By Jonathan Kaplan

Unlike the modules described in the previous post, which are applications or utilities that are intended for all Wonderland users, the Sorting Algorithms module is a special-purpose tool for use in Computer Science education. This application was inspired by the seminal algorithm animation work of Computer Science Professor Bob Sedgewick and his student Marc Brown, who Nicole worked with while at Brown University in the 1980s (see “Survey of Algorithm Animation Platforms“).

We created this module to demonstrate the utility of curriculum-specific interactive tools that can be easily added into a generic Wonderland installation. This particular module combines both 2D and 3D elements, integrating a multi-user Java code editor for writing sorting algorithms with a grid of 3D spheres that are the target of the sort operation.

Once you have installed the module on your Wonderland server, select “Object” from the Insert menu, select “Sorting Demo” from the list, and then click the “Insert” button. You will see a code editor window plus 8 red spheres.

Initial Sorting Algorithm configuration.

Initial Sorting Algorithm configuration.

Right-click on the editor window to “Take Control” of the application. Type in the code for your algorithm, noticing that a bit of the code is already written for you so that you can focus solely on the algorithm. For those of you who are not programmers, there are two sorting algorithms at the end of this post that you can copy and paste into the code editor for experimentation purposes.

Running a simple sort algorithm.

Running a simple sort algorithm.

Using the tool palette, you can click on the right arrow tool to step through your code one line at a time. As you do, you’ll notice that cubes indicate which items in the set are being compared or swapped.  Alternatively, you can click on the play button to run the sort. You can stop or pause this playback at any time. The randomize tool (second from the right) allows you to create a new random ordering of the objects. Notice that the two fields below the code pane provide information about the highlighted items and also about the overall gets and swaps.

If you wish to sort more than 8 items, click on the gears tool to open the sort settings dialog (we didn’t have a “settings” icon, so I used the “unsync” icon in a pinch).

Changing the settings to add more elements.

Changing the settings to add more elements.

These settings also allow you to change the color, size, and spacing of the spheres, as well as randomize the objects.

Try comparing two different sorting algorithms by inserting another copy of the Sort Demo into the world and entering different code.

Comparing two sort algorithms.

Comparing two sort algorithms.

With two people, you can click play at the same time and see which algorithm runs faster. Or two or more people can work on developing an algorithm together, either using the same code editor window, or using multiple windows side-by-side. It’s a perfect way to do remote pair programming.

In thinking about how this would be used in a class, an instructor can easily add instructional content to the world in the form of PDF or Open Office documents, give lectures in the virtual space, and walk around the space as multiple groups of students work on algorithm assignments. The virtual space allows the instructor to watch as students work, providing help when necessary. The addition of an in-world web browser can provide students with easy access to reference materials, or students can take advantage of the new Screen Sharer module described in the previous post to share content from their own computers.

In the future, we hope to see entire courses being taught in Wonderland worlds using a combination of the standard features and custom modules such as this one.

Jonathan Kaplan
Partner, Wonderland Architect, WonderBuilders LLC

Bubble Sort Algorithm

// bubble sort code
for (int i = s.getCount() - 1; i >= 0; i--) {
    for (int j = 0; j  s.get(j + 1)) {
            pause(j, j+1);
            s.swap(j, j + 1);
            pause(j, j + 1);
        }
    }
}

Quicksort Algorithm

// quicksort code
int lo = min;
int hi = max;

pause(lo, hi);

if (lo >= hi) {
    return;
} else if (lo == hi - 1) {
    if (s.get(lo) > s.get(hi)) {
        s.swap(lo, hi);
    }
    return;
}

int middle = (lo + hi) /2;
int pivot = s.get(middle);

pause(middle);
s.swap(middle, hi);

while (lo < hi) {
    while (s.get(lo) <= pivot && lo < hi) {
        lo++;
        pause(max, lo, hi);
    }

    while (pivot <= s.get(hi) && lo < hi) {
        hi--;
        pause(max, lo, hi);
    }

    pause(max, lo, hi);
    if( lo < hi ) {
        s.swap(lo, hi);
    }
}

pause(hi, max);
s.swap(hi, max);

sort(s, min, lo-1);
sort(s, hi+1, max);

Wonderland Wednesdays Subsnapshot Project

September 14, 2010

Today’s guest blog post is from Bob Potter. Bob leads the development effort of a small agile software house in Montreal, Canada and is interested in virtual worlds as an avenue for discussions and collaborative work for geographically distributed teams.

Subsnapshot Project

By Bob Potter

Most weeks around midday Wednesday in North America, evenings for those in Europe, a group of Wonderland enthusiasts have been assembling in-world to share insights, demonstrate modules, build worlds, and generally learn how to work with Wonderland. Here are the details for tomorrow’s session:

Wonderland Wednesday – Subsnapshot Development
Location: Community Server
Time: 1pm ET (check here for time in your time zone)

Ryan (aka Jagwire) has been leading these developer-focused sessions for the past few months, and through his capable hands, we have walked through the structure of Wonderland, the code, and debugging techniques. After having reviewed code, the group as a whole wanted to get our hands dirty and actually dig in and develop something.  We wanted to find a way to involve ourselves in the development of Wonderland.  Although many of us are strong Java developers (or not), the Wonderland architecture is not the easiest thing to wrap one’s brain around.  There are excellent tutorials on how to develop modules for Wonderland, but this can be nicely complemented with some hands on sessions.  Wonderland itself provides us with the perfect environment to work together as a team.

With the desire to develop something useful, discussion turned to what does Wonderland need.  Several of the participants are active world builders and expressed a need for a way to export a portion of the worlds they were working with.  For example, if the world builder had pieced together a collection of objects organized in a purposeful unit, it would be useful to be able to export this collection into a package that could be reused in another world without having to repeat the painstaking effort required to insert, manipulate, and align the objects. Hence the birth of the Subsnapshot project.  Wonderland already has the means to export the whole world, in the form of a snapshot, but this project would allow the export of selected portions of a world.

Planning the project was done in-world.  An instance of the Firefox browser was started in-world using the shared application functionality of Wonderland. We used the in-world whiteboard as well as Google Docs to capture our notes.

Planning the Subsnapshot module using the whiteboard.

Planning the Subsnapshot module using the whiteboard.

Our discussions centered around how to select the items to export and what would be involved in exporting cells.  We also decided to plan our work so we would get some working code quite early on in the process – it always feels good to get something useful working!

In the following session we actually started coding.  We used the Java IDE, Netbeans, again using the shared app functionality to work collaboratively.

Coding using the NetBeans development environment running in-world as a shared application.

Coding using the NetBeans development environment running in-world as a shared application.

We created the module skeleton with all the necessary directories, build, and proprieties files.  Our first task was to add the menu option for export. Jonathan (chief architect of the Open Wonderland Project) served as our guide and coach. He had us create a ContextMenuFactory class to add our “Export” option. Actual coding work was passed between a few members of the group and all done in-world! We later started work on the export process, extracting a list of the content (e.g. images) that a cell uses.  We took the time to explain all the various parts of the functionality we were creating, so coding progress was slow, but everyone had a chance to fully understand how the code was working.  In between live sessions, we continued our technical discussion in a Google Wave.

Subsnapshot group viewing Google Wave discussion while working on code in NetBeans.

Subsnapshot group viewing Google Wave discussion while working on code in NetBeans.

At the next session, we started by reviewing what had been accomplished during the last session. One member of the team had a chance to test the code that we had written, and he identified a few bugs.  He also proposed some fixes. To show us, he dropped an image (.jpg) of his corrected version of the code and another image of a test he ran to demonstrate the correctness of his fix. We then edited the master copy of the code with the corrections.

Subsnapshot group reviewing proposed bug fixes.

Subsnapshot group reviewing proposed bug fixes.

We were now ready to move on and add additional functionality. We already had the ability to extract a list of the content. The next step was to write the content into files that would later be packaged for export. Using a Sticky Note, we quickly outlined how we wanted to organize our export package.  By the end of the coding session, we were able to write the content files and save them to the client computer’s file system.

For the next session, coming up tomorrow, we are considering splitting up the group and working in parallel on two (or maybe more) separate instances of Netbeans. This will allow a few more of us to actively participate in the coding process.  It will also make Jonathan run around the world a bit! Wonderland is proving to be a productive environment not just to discuss and plan, but also to accomplish real work. Feedback so far has been very positive. In the words of one of our regulars, “this collab is ‘stunning’.”

If you are interested, come join us one Wednesday – check out the Wonderland forum or our Facebook events page to see what is on the Wednesday program – we don’t code every week, but usually there is something happening. One of us will be happy to bring you up-to-speed, so don’t feel like you can’t join in if you didn’t start on the project from the beginning. It’s a great way to learn about Wonderland development and also a great way to learn techniques for using Wonderland as a collaborative work environment.

We’ll be adding comments to this blog post after every meeting, so check back for updates on the progress of the subsnapshot project.

- Bob Potter

See the Open Wonderland Facebook events page for Wonderland Wednesday session details.


WonderBuilders Module Contributions

September 13, 2010

Today’s guest blog post was contributed by my business partner, Mike Gialis. The modules described in this post were demonstrated during last week’s Wonderland Wednesday session. See the album on the Open Wonderland Facebook site called ModuleShowcaseSept2010 for snapshots from the event.

WonderBuilders Contributes New Modules

By Michael Gialis

It’s been a busy summer at the newly formed WonderBuilders LLC partnership. This is a new consulting company doing for-profit, custom Open Wonderland development for clients. Our hope in starting this small business was that a number of us from the original Wonderland team, augmented with members of the open source community, could make a living by doing proprietary Wonderland development. We believe that by focusing on specific customer use cases, we can improve the robustness and stability of the platform for everyone. While some of the work we do in this endeavor will not be made public, we will be encouraging our clients to contribute as much as possible back to the community, either in source code form or in binary form as Wonderland Module Warehouse contributions. Our business model is to establish a win-win situation for both clients and for the community.

As you will see from the module descriptions below, so far this concept has been panning out nicely! We managed to make some money this summer, fix over 20 substantial bugs, and contribute this collection of new modules in both source code and binary format:

  • Screen Sharer - Lightweight tool for sharing a portion of your screen
  • Group Tools – Text chat and broadcast messages to groups of users
  • Admin Tools – Force Mute, Disconnect, Turn Invisible
  • Quickstart – Set of short user guides
  • Sorting Algorithms – Computer programming learning tool

The first four of these modules are described below. The Sorting Algorithm module, which requires a bit longer explanation, will be described in a subsequent article. We hope you will find these new modules useful in your own Wonderland projects, or as useful starting points for building new modules.

Screen Sharer

The Screen Sharer module is a light-weight tool for sharing a portion of your screen. Like the VNC application, you can see a remote desktop or portion of someone’s screen in-world. Unlike the VNC application, no additional software is required on the computer being shared. It’s simply a matter of selecting “Share screen” from the Tools menu. A red border will appear in the upper left corner of your screen.

Screen Sharer "share border."

Screen Sharer "share border."

You can resize or reposition this border to share any portion of your screen that you wish.

Shared screen displayed in-world.

Shared screen displayed in-world.

The tool works particularly well if you have a dual-monitor setup, but even without, you can make your main Wonderland window smaller or move it partially off the screen in order to share some other content on your desktop.

In order to keep this application light weight and conserve on bandwidth, we have pegged the screen update frame rate at 1 frame per second. This rate is sufficient for sharing terminal windows, text editors, spreadsheets, error messages, web pages, and other fairly static content. It doesn’t work as well for dynamic data that updates quickly, like video. For video, you’ll want to wait for the new Video Player module, which you can currently experiment with in source format (see the Forum thread “Video Preview 1“).

Group Tools

Group list

Group list

For some Wonderland use cases like conferences or meetings with breakout sessions, teams of people split up into groups and work in separate parts of the virtual world. The idea behind the Group Tools module is to enable group members to easily and privately communicate among themselves, and also to send messages to all the members of other groups. For example, it might be handy to broadcast a request for help to all the members of the “admin” group. Or an event organizer may want to broadcast a message to a team saying that they are needed back in the main conference area.

The Group Tools module adds a “groups” tab to the Users list window. For a group to appear in this list, you have to first set up groups using the Edit –> Groups command in world, or using the Groups section of the Server Admin console. Selecting a group name allows you to open the group chat window for that group or send a broadcast message to the members of the group.

Sending a Broadcast message.

Sending a Broadcast message.

Unlike the Text Chat All window, chat messages sent to a group persist so that a member of that group can see all messages sent to the group since the beginning of the current session.

Admin Tools

At times, it is helpful to have some “super-user” capabilities. For example, if someone has stepped away from their computer without muting their microphone, the background noise can be extremely disruptive to the rest of the virtual world participants. For reasons such as this, we created a set of Admin Tools which work only for members of the special “admin” group. These include two features, Force Mute and Disconnect, that are accessed by right-clicking on another person’s avatar. When an administrator selects “Force Mute,” the person being muted receives a message explaining what has happened:

Force Mute message.

Force Mute message.

That user may un-mute themselves at any time. If an administrator selects “Disconnect,” however, the user will immediately be disconnected from the session.

The third Admin Tool allows anyone in the “admin” group to “Turn Invisible.” This command, accessed by clicking on your own avatar, allows an administrator to walk around the world unseen by anyone not in the admin group. The administrator, plus other admins, will see an invisible avatar surrounded by animated spheres.

An invisible avatar is surrounded by shimmery spheres.

An invisible avatar is surrounded by shimmery spheres.

Right-clicking on your own avatar again will allow you to select “Turn Visible” to turn your avatar back on for others.

Quickstart

The Quickstart module installs a “Quickstart” item in the Help menu that launches an external browser window with this Quickstart Guide table of contents. From here, users can navigate to a selection of Quickstart Guides, covering topics such as the basic operation of the Wonderland environment to descriptions of how to use various applications.

Since the Quickstart module installs simple HTML pages on your Wonderland server, you can easily modify these guides or add a new Quickstart guide for your own Wonderland module.

[To Be Continued - The Sorting Algorithms module will be described in a subsequent post]

Michael Gialis
Partner, Business Development, WonderBuilders LLC

mike@wonderbuilders.com


Authenticating Wonderland against Facebook

September 10, 2010

(This blog posting describes how to install and use the Facebook Authentication module.)

Many developers already know that Wonderland supports three modes of authentication:

  • no authentication (the default);
  • “full” authentication (in which users must have a valid account);
  • and “optional” authentication (which allows guest users, but provides authenticated users with privileged access).

The module required to enable authentication is available on the module warehouse and the steps required to install it in Wonderland are clearly laid out in Jon Kaplan’s excellent tutorial. In addition, Jon’s tutorial includes a description of extending the authentication mechanism by using the LDAP authentication module, also available from the module warehouse. As always, the source code for these modules is available from the Open Wonderland modules workspace.

Readers of my earlier posts will be aware that I’ve been exploring how to integrate Wonderland with the wider web, including web-based social networking services such as Twitter. The 1000lb gorilla of social networking services is, of course, Facebook. For example, more than 25 million Britons, or one in three of the entire population, is now a member of Facebook. Given that so many of us have an account with Facebook, it appears to be becoming a common authentication service for many other applications via its Facebook Connect APIs. The obvious next step, then, is to extend Wonderland so that users can log in using their Facebook credentials. In the remainder of this blog posting, I’ll take you through the process to enable Facebook authentication for your Wonderland installation.

  1. Firstly, download and install the authentication module from the module warehouse, taking care to follow the instructions in Jon’s tutorial. Do not try to move on to the next step until you can demonstrate that authentication works for your installation.
  2. Read Jon’s instructions to add different authentication mechanisms.
  3. Download the Facebook Authentication module from the module warehouse, and deploy it to the wonderland server.
  4. Close down the Wonderland web server completely.
  5. The Facebook authentication module acts as a user plugin in a similar fashion to the LDAP plugin, and needs to be configured. Download an example plugin configuration file that includes using the Facebook authentication module and save it in your .wonderland-server directory.
  6. Now you just need to tell the Wonderland web server to use the configuration file. You do this by adding an entry to the my.run.properties file, as described in Jon’s tutorial.
  7. Now restart Wonderland and you should be able to login using your Facebook email address and Facebook password.

For an example of this in action, see the video below.

Facebook isn’t the only third-party authentication service that Wonderland could use. Google provides an authentication API that looks like it could be incorporated into Wonderland’s login mechanism, but I’ll leave that as an exercise for the reader!

The source for the module is available from the positive-spaces SVN repository, described in my last post: Wonderland a Twitter.


Wonderland Avatars Now Sit

September 7, 2010

Today’s guest blog post is from Morris Ford, one of the most active members of the OWL developer community. In addition to working on integrating scripting with OWL, Morris has just published a new module that I think everyone will like. We’ll be demo’ing Morris’ work along with quite a few other new modules in this week’s Wonderland Wednesday session.

Sitting Capability

By Morris Ford

I recently added a Sitting Capability to the Wonderland Module Warehouse and to the module source repository that will allow your avatar to sit on a “chair.” To sit, you choose an object that has been enabled for sitting and, using either the context menu or a mouse click, your avatar automatically navigates to the object and sits on it.

Enabling an object for sitting

To enable an object for sitting involves adding the Sittable capability to that object.

Chair context menu

Select "Properties" from the chair context menu.

Click the "plus" to add a capability

In the Properties dialog, click the "plus" to add a capability.

Select the Sittable capability

Select the Sittable capability and click "OK."

After enabling sitting, the sitting position can be adjusted using the property sheet for the Sittable capability.

Sittable Default Properties

Sittable Default Properties

There are two sitting adjustments, Heading and Sit Offset. The Heading adjustment is for setting the rotation of the avatar in relation to the chair. The heading value is in degrees and is in relation to the sittable object. This means it will remain consistent even if you rotate the chair. The Sit Offset is an amount the avatar sits forward or backward in relation to the sittable object. This value is in meters and is relative to the center of the object. It is a value along the heading line and will remain consistent when the object is rotated. I have found that a setting of about 0.5 is appropriate for most chairs, although the chair in this example is rather deep, so a setting of 1 works best.

Note: In this version of the capability, you need to turn off collision on the chair object before sitting will work properly. To do this, select the “Model Component” capability and uncheck “Collision Enabled.”

Making the avatar sit on the object

There are two possible ways to make the avatar sit. One is through the object’s context menu and the other is by mouse click. The context menu is displayed by clicking on the object with the right mouse button. After sitting has been enabled on an object, you will see a “Sit Here” command appear in the context menu.

"Sit Here" appears on the chair's context menu
“Sit Here” appears on the chair’s context menu.

The other way to have the avatar sit is by using a mouse click. Click the “Enable Mouse” button in the Sittable property sheet.

Sittable Mouse Settings

Sittable Mouse Settings

Next, select which mouse command you wish to map to sitting. If you select “Middle Mouse,” for example, clicking on the chair with the middle mouse button will cause your avatar to navigate to the chair and sit.

Avatar sitting on chair

Avatar sitting on chair.

For fun, walk a short distance away from your chair and select the “Chase Camera” from the View menu before you sit. There’s no special path following implemented yet, so be sure there are no obstacles in your avatar’s way before issuing a sit command.

- Morris Ford


Follow

Get every new post delivered to your Inbox.

Join 54 other followers

%d bloggers like this: