Marble Maze 3D iOS Game

This is another 3D iOS game I completed the other day. Similar to the brick breaking game, it is also using SceneKit as the tool. One thing different is that this game uses game.scn as the main scene and references other scenes as child nodes, such as the ball here. Altering the properties of the scenes referenced will alter their appearance in the main scene as well.

Physical properties are again set with bit mask. The ball is configured with properties such as diffuse, specular, and normal maps. Lights on the ball indicate life. When the light is out, the ball dies. Players have to tilt their phone to get to where pearls are at in order to replenish their lives.

The camera is set to slowly follow the motions of the ball. Its position is also set relatively to the ball so that it follows at all times.

I might add more features to this game when I have time. Just like in the game Ballance, maybe I could add some ramps and springs so players can truly have fun with this game! SceneKit is so fascinating.

Day 1 Week 3 on JFLAP

Today I added one more function to right click menu – delete node. Now you can right click a node to delete it from the graph. I then reenabled the functionality of adding multiple nodes after one click of add nodes. To enhance user experience a little more, I added a cancelbutton which can cancel all temporary conditions of the graph. This button can also be activated by pressing the ESC key on the keyboard. However, for some reason I generated a but: adding edges function is not highlighting the first node clicked as before.

A new functionality was implemented today –FAFixer. This type of exercise provides a malformed finite state machine, a language and lets students fix the machine. There is also a tester for students to use. For creating this kind of exercise, I also added editing graph function in Exercise Generator. You can click on edit graph to edit the graph provided to students for that problem. The graphs are then saved in localStorageand transformed to JSON when users finish.

edit graph functionExercise Generator with Editing Graph

Day 5 Week 2 on JFLAP

This morning I found that there was a bug with yesterday’s work. In conversionExercise, if the problem was switched to another and then switched back, grade function would not work properly. This is because I did not use graph.clear() to clear the graph, and the reason for that is this function did not work. Today I realize that it is not this function does not work per se, instead this function deletes the html DOM element along with the graph, so the fix was easy: add the DOM element back using JavaScript after the graph is cleared. After this bug fix I spent the rest of the morning adding the grading feature to this conversion exercise. Now, the student gets one point for each state correct, loses 0.25 for each incorrect step. Their scores are shown continuously, meaning that after each operation they receive a feedback. Total possible score is the total states in the DFA converted, but the score itself is not shown to avoid hints. For score displaying, I disabled jsavscore provided by JSAV and used my own because I do not like to guess what functions do. I like to be in control.

Then I implemented this wonderful DFA exercise generator, which takes input of expressions and test cases and spits out a json file that can be used by the conversion exercise I implemented yesterday. This tool is supposed to help instructors create their own exercises. A screenshot is shown below. Instructors are able to add problems, add test cases, and when they finish click get JSON button. A download link will appear for them to download the json file.

exercise generatorediting exercise

download jsondownload JSON file

I am embarrassed to say that I spent most of the time implementing adding problem and adding test case functions. There are just too many details: name attribute for radio buttons have to be different so they don’t mess up with each other. I also have to update the indices for problems and test cases etc. I am so happy it is working.

It’s been a week since I started coding now. General impression of JavaScript: this keyword sucks! Avoid using this at all costs. Not only does it cause huge errors depending on the context, but it also confuses future developers on the project. I spent so much time reading other people’s code for a long time trying to figure out what this represents, because often times it is coming from another file, not to mention sometimes it is passed more than once. Naming and commenting are also so important that it can greatly influence the project. If a project is meant to be a coorperative effort, variables and comments have to be satisfying.

Day 4 Week 2 on JFLAP

I started this morning by fixing a bug in conversionExercise. There was no alert when the state label added by users is incorrect sometimes. After that I did a lot of restructuring of the code. I moved common functions such as serializeGraphToXML to a library-like js file serializableGraph.js. Declarations of functions bugged me a little. In JavaScript, if a function is defined as var x = function() then the calls of this function must be after the declaration, but if it is defined as function x() then it can be called everywhere. I also renamed some variables with regular expression search in Vim. I gave names with more practical meanings.

Then I added the multiple problem feature to conversionExercise just like what I did toFATester. The problems are loaded from an XML file using a synchronous ajax call. This gives me a warning in the console that says synchronous calls can harm user experience, but since problems are essential to the page, I ignored the warning. One thing to note is that in FATester I am using JSON files to store the problems because that exercise does not require the storage of graphs. I plan to develop an exercise editor for instructors which takes the input of graph or test cases and output json or XML files.

I also improved the performance of the right-click menu by highlighting the node chosen. “Change Label” and “Clear Label” buttons are added as well. The next step is to do the same for edge editing. It would also be nice to let users drag nodes to move them, but this will require the program to update positions of the node, labels and edges connected to it along the way. I am trying this tomorrow. Another form of exercise might also be implemented: take a malformed DFA and improve it.

Day 3 Week 2 on JFLAP

Today I continued the development of right-click menu by integrating it to FAEditor. I also did a nice thing to future developers. I moved the function of showing right-click menu to Commands.js so multiple html files can integrate this function. Then I moved on to improve funcionalities of conversion exercise. A bug in FA.js with lambda closure was fixed. The reason was different representations of lambda symbol. In one js file it was a string from char code but in another it was /$lambda;. Besides all these, I also fixed a bug in NFA to DFA which caused the exercise to fail after reset. The reason was multiple bindings of click handleers, similar to what I encountered yesterday.

I spent most of the day struggling with grading of the exercise. There is an exercise feature in JSAV but the documentation is written POORLY. For some reason if I add exercise.gradeableStep() to mark a step as part of grading, that step is executed forever in modelAnswer function. I am going to try one last time tomorrow morning. If I fail I am going to use my own method for grading. I am thinking letting the program solve the problem in a standard way along with the student. In this way the exercise can provide feedback whenever the student does something different from the standard answer. However, this will lose the functionality of a test, but rather is an exercise.

If you are a developer for JFLAP summer 2017 and you’re reading this. I’ve got one piece of advice for you: take good care of your neck. Make sure the muscles are not under too much pressure and take a break every other hour. My pain in the neck is greatly decreasing my efficiency this week.

Day 2 Week 2 on JFLAP

Today I added this wonderful feature into FATester – right-click menu! Now you can right click a node to toggle initial and final states. Sadly, I spent most of the time debugging. There are three main things that I learned today to remember:

1. jQuery selector returns an object different from a normal javascript object. When I used selector to select a node in the graph, the object returned can not simply be operated with methods provided by JSAV.

2. if an event is binded to an object for multiple times, the event will trigger the function as many times as the event is binded. This bothered me when I was trying to toggle initial and final states by clicking a button. If a state is toggle twice, then it is back to its original state!

3. offsets culumate. To make the right click menu appear, I am using a div and setting its position as absolute. However, I first used offset() function to do this, which made the menu move further and further to right and bottom. After searching online, I decided to switch to jQuery function .css() and changed the left and top attributes, which work as a charm.

 

Some screenshots of this new function:

earlier version

Before I developed this new function, users have to click Edit Node button and then click a node to change initial and final states.

toggle initial

Toggle initial state

toggle final

Toggle final state

toggle final

Having two initial states is not allowed

 

Besides this new function, I also added some exercises in the Linz book to the tester. There are now four problems and some test cases.

Day 1 Week 2 on JFLAP

Over the weekend I read chapter 7 of the Linz book. It is about Pushdown Automata. The major difference between Pushdown Automata and DFA is that PA uses a stack to hold relevant information. There are two kinds of PA, nondeterministic and deterministic. Generally, nondeterministic pushdown automata (NPDA) are used more frequently. Edges in NPDA include three pieces of information: input variable, top element in the stack, and element to replace the top of the stack. NPDA is proved to be equivalent to context-free grammars and context-free languages. There is a part in JFLAP that lets you transfrom from one to another.

Today is a day to celebrate: my office is finally ready! I have a big monitor in there. I spent most of my day implementing a Finite State Machine tester. This tester is modified from FAEditor created by Martin last summer. The tester, as shown below in a screenshot, is able to provide a whole exercise set. Clicking on different question indices will lead to different questions. Students are able to either create a new machine with the editor or load one from local machine. After they finish, the “test” button will begin the tests and the results are shown at the bottom of the page. Test cases, standard answers and test results are provided, just like how Duke CS classes’ APT testers. Test cases are provided because I believe it is harder for students to “hard code” them in the machine than to actually think about the problems.

FATester screenshot

Test problems are imported from a JSON file which can be modified by instructors. There will probably also be an exercise problem editor, in which users can create problems and save in JSON format. JSON file is read synchronously, because the exercise may only continue after the problems are loaded! I totally ignored the warning from jQuery about doing so would be detrimental to user experience. I had no choice. Another challenge that I faced was integrating the multiple problem feature. I solved it using a variable to store current exercise, and created an update function to update user interface and the tester.

Tomorrow I will probably be working on the problem editor, or implement a new kind of exercise.

3D iOS Brick Breaking Game

Today I made this brick breaking game on iOS with SceneKit following a tutorial. With SceneKit, an SCNView contains an SCNScene in which SCNNodes appear and animate. Nodes are added to SCNScene by adding it as a child node of rootNode. XCode also provides a very nice Scene Editor so 3D elements can be created there.

Physical collisions are represented using bitmask, just like SpriteKit. Delegates are also there to perform different actions at different stages of collisions. Contact nodes are passed in as parameters so developers can do whatever they want with nodes that are colliding.

In SCNScene, there are also very interesting features such as cameras. You can add multiple cameras and switch between them. You can also change camera positions based on how users interact with the game. Besides cameras, lights are there to make it more fun – professional photographers will find things familiar! In this game there are front light, back light and also a gradient light. These three lights are believed to provide the best user experience.

3D is so fun!

Day #5 on JFLAP

Today I read chapters 5 of 6 of the Linz book. Chapter 5 talks about context-free languages. Context-free language is a broader set of languages which is able to represent programming languages syntaxes, as opposed to regular languages only able to represent certain tokens. Regular language is a subset of context-free language. Further, I learned about parsing and ambiguity in 5.2 and how to use derivation trees to check ambiguity.

Chapter 6 is simplification of context-free grammars and normal forms of them. To simplify a context-free grammar, there are three goals: no unit productions, no useless variables, and no λ-productions. It is proved in the book that every context-free grammar can be transformed to achieve these three goals. Then the book gives definitions for two common normal forms: Chomsky Normal Form, which has at most two variables on the right side, and Greibach Normal Form, in which all productions have the form A → ax, where a is a terminal symbol and x is a star-union of variables. According to the book, Chomsky form is helpful for testing membership. I am still a little confused with this membership-testing algorithm, but I will be able to understand it.

The next chapter is about Pushdown Automata, which is similar to Finite Automata. The relationship between FA and regular languages is similar to the relationship between Pushdown Automata and context-free languages. I will read about this in the weekend.

I also read one paper by Shaffer that introduces JSAV library on which OpenDSA project is built on. Citation and summary can be found here. There goes my first week on JFLAP. Can’t wait to start coding!

Reading:

Karavirta, Ville and Shaffer, Clifford A. JSAV: The JavaScript Algorithm Visualization Library. ITiCSE Proceedings of the 18th ACM conference on Innovation and technology in computer science education (2013) 159-164

This paper introduces JSAV as a JavaScript library to implement algorithm visualizations. In the introduction the authors point out different levels of engagement in algorithm visualizations, and in the next section they illustrate how JSAV is able to achieve those interactions in detail. First, JSAV can present static images as well as modifying them without difficulties. Second, JSAV can provide slide-show functionalities, which can be used to make eTextbook. Last but not least, JSAV is able to offer different levels of feedbacks to students. The paper also talks briefly about the OpenDSA project, a eTextbook project aiming to help with DSA (Data Structures and Algorithms) education. OpenDSA project is built based on the development of JSAV.

The development of online version of JFLAP depends heavily on JSAV, so it is essential for me to understand the design patterns and concepts behind JSAV. The product that I contribute to this summer should conform to the general patterns of other eTextbooks in the OpenDSA projects.

Day #4 on JFLAP

Today I read three papers in the morning. One is about the difficulties students experience when learning formal languages and automata theory; one is a proposal during a conference that advocates XML-based tools development to visualize algorithms; the last one is about the available softwares there are in the field of algorithm visualization. Formal references and summareis are here.

I then downloaded all the code written by Martin and Sung-hoon last summer. Specifically I perusedFAEditor.js and FATraversal.js. I now understand the big structure of what they built and common tricks of doing things. This will help me in later work for sure.

One problem that I notice with JSAV library is that the arrows are too small to see. I visited the documentation of JSAV again but did not find any configuration options. Professor Rodger said she will complain this to the organization.

Later in the afternoon I updated the website to separate readings from blogs because I realize reading summaries kind of mess up with blogs. Right now there are “Blog” and “Reading” buttons on the navigation bar. Before there was only one “Blog” button. With a little effor, I also used jQuery to include the same header html in every page so I don’t have to copy and paste a chunk of html code and update links every week.

<script>
	$(function(){
		$("#header").load("header.html"); 
	});
</script>

Readings:

1. Shaffer, Clifford A. et al. Algorithm Visualization: The State of the Field. ACM Transactions on Computing Education (TOCE) 10.3 (2010)

This paper aims to provide an overview of the state of the field of algorithm visualization. The authors created a Wiki called AlgoViz and introduced common AV projects. They also collected the data of AV counts by topic. As a result, they find that a great majority of AV projects are about sorting algorithms, with only around 2% focusing on NP-Completeness algorithms and a small amount about compression algorithms. This unequal distribution across topics is quite worrying. The authors also point out that high-quality AVs are among a greater number of low-quality AVs, making it hard for instructors to find an effective AV for class.

2. Pillay, Nelishia. Learning Difficulties Experienced by Students in a Course on Formal Languages and Automata Theory. ACM SIGCSE Bulletin, 41.4 (2009) 48-52

This paper describes the result of a study on difficulties students experience when learning about formal languages and automata theory (FLAT). Students generally find that using visualization softwares such as JFLAP very helpful. However, they still face various kinds of challenges. For regular languages, when minimizing states in a DFA, some students combine two final states together when they are not indistinguashable. When converting NFA to a regular expression, a number of students forget that multiple simple paths can be between two nodes. Two difficulties described above are just examples from this paper. The author hopes to help with education of FLAT courses by identifying these difficulties.

3. Naps, Thomas et al. Development of XML-based Tools to Support User Interaction with Algorithm Visualization. ACM SIGCSE Bulletin 37.4 (2005) 123-138

The authors point out that AV is effective only when combined with a certain level of interaction. These interactions include viewing, resonding, changing, constructing and presenting, from minimum interaction to maximum. The methods to achieve these interactions include graphical primitives to visualize, hypertext documents, interactive questions and input generators. As there will be many softwares implementing these functions. The authors propose that a standard XML language be constructed to ensure portability across different AV systems. In this way the efficiency of the field of AV development will be greatly improved.